苏州大学2007年872试题

数据结构

名词解释

逆波兰式:

后缀表达式, 运算符在操作数后面.
自由树:

无回路的连通图.
外部排序:

将待排序的记录存储在外存上, 排序时再把数据一部分一部分地调入内存进行排序. 在排序过程中需要多次进行外存和内存之间的交换, 对外存文件中的记录进行的结果仍然放到原有文件中.
邻接表:

对图 G 中的每个顶点 V1 建立一个单链表, 第 i 个单链表中的结点表示依附于顶点 Vi 的边. 边表的头指针和顶点的数据信息采用顺序存储.
占位程序:

缺失或未经测试的函数的简化版, 用于产生足以用于测试的值.

队列的实现方法有哪些? 试比较各种实现方法的优缺点, 并距离说明队列在计算机系统中有何应用?

队列的实现方法有:
1. 顺序队列, 即采用顺序存储结构存储队列.
2. 链式队列, 即采用链式存储结构存储队列.
各有什么优缺点:
1. 顺序队列
  1. 优点: 可以一次性分配保证够用的空间, 效率高, 因为是基于数组的, 长度也是固定的. 可以实现动态容量.
  2. 缺点: 动态分配长度时, 效率低下.
2. 链表队列
  1. 优点: 可以方便快速地动态增长.
  2. 缺点: 由于基于链表, 要动态创建和删除节点, 效率较低.
应用
1. 解决主机于外部设备之间的速度不匹配的问题.
2. 解决由多用户引起的资源竞争问题.

链表的交集

def intersection(l1: ListNode, l2: ListNode) -> ListNode:
    """
    求两个有序单链表的交集, 存放在l1中.
    设置两个指针分别指向两个链表的开头, 如果两个指针指向的结点的值相同, 则表示位于交集内.
    如果不相同, 则比较两个结点的值的大小, 如果l1的大, 则移动l2的指针. 否则删除当前l1的结点.

    Args:
        l1 (ListNode): 有序单链表1
        l2 (ListNode): 有序单链表2

    Returns:
        ListNode: 交集的单链表
    """
    if not l1 or not l2:
        return l1
    h1, h2 = ListNode(0, l1), ListNode(0, l2)
    t1, t2 = h1, h2
    while t1.next and t2.next:
        # 如果相等则t1,t2移动到下一格
        if t1.next.val == t2.next.val:
            t1, t2 = t1.next, t2.next
        # 如果大于则移动t2, 直到相等或者大于t1.val
        elif t1.next.val > t2.next.val:
            t2 = t2.next
        # 如果t1.val < t2.val 则移动t1, 且跳过当前结点
        else:
            t1.next = t1.next.next
    return l1

合并二叉排序树

def insert_node(tree: TreeNode, target: TreeNode):
    """
    将一个节点插入到二叉排序树中.

    Args:
        tree (TreeNode): 二叉排序树
        target (TreeNode): 目标节点
    """
    if target.val == tree.val:
        return
    elif target.val < tree.val:
        if tree.left:
            insert_node(tree.left, target)
        else:
            tree.left = target
    else:
        if tree.right:
            insert_node(tree.right, target)
        else:
            tree.right = target


def merge_search_tree(tree: TreeNode, target: TreeNode) -> TreeNode:
    """
    合并两个二叉排序树.

    后序遍历第二个二叉排序树, 对于遍历到的每个节点, 将其作为单个节点插入到第一个二叉排序树中,
    然后返回第一个二叉排序树.

    Args:
        tree (TreeNode): 第一个二叉排序树
        target (TreeNode): 二个二叉排序树

    Returns:
        TreeNode: 合并后的二叉排序树
    """

    def post_order(idx: TreeNode):
        """
        后序遍历

        Args:
            idx (TreeNode): 遍历的当前节点
        """
        if idx.left:
            post_order(idx.left)
        if idx.right:
            post_order(idx.right)
        idx.left, idx.right = None, None
        insert_node(tree, idx)

    post_order(target)
    return tree

有向无环图的最长路径

def longest_path(_map: dict, start: int = 0):
    """
    求DAG的单源最长路径.

    可以转换成求所有权值为相反数的最短路径. 最短路径可以使用Dijkstra求出.

    Args:
        _map (dict): DAG
    """
    length = [float('inf') for _ in range(len(_map))]
    pre = [start for _ in range(len(_map))]
    que = [[-v[0], v[1], v[2]] for v in _map[start]]
    heapq.heapify(que)

    for _ in range(len(_map) - 1):
        idx_len, idx_node, idx_pre = heapq.heappop(que)
        length[idx_node] = idx_len
        pre[idx_node] = idx_pre
        for v in _map[idx_node]:
            heapq.heappush(que, [-v[0] + idx_len, v[1], v[2]])

    max_node = start
    for i in range(len(length)):
        if length[i] < length[max_node]:
            max_node = i

    print(f'The longest path length is {-length[max_node]}')

    path = [str(max_node)]
    while pre[max_node] != max_node:
        max_node = pre[max_node]
        path.append(str(max_node))
    path_str = '->'.join(path[::-1])
    print(f'The path is {path_str}')

由于使用到了最小堆, 并且每条边都会进行加入最小堆操作, 因此时间复杂度为 O(E+V*log(V))

操作系统

请判断下属说法的对错, 并说明原因

分时操作系统必然建立在多道程序技术的基础之上

错误, 多道程序设计引入的目的是提高 CPU 的使用率, 两者无关.
进程是指令的集合

错误, 进程是任务的执行者, 程序是机器指令和数据的集合, 进程可以被看作正在运行的计算机程序.
存储保护的功能是限制内存存取

错误, 保证进入内存的各道作业都在自己的存储空间内运行, 互补干扰.
位示图可用于主存空间的共享

错误, 用于管理磁盘空间和主存空间.

内存管理(非连续)

略

连续分配、链接分配、UNIX inode 分配. 详细说明下列的文件访问需求, 采用那种分配方案最合适.

大文件顺序访问

连续分配, 因为每个文件占据磁盘上的一组连续的块, 适合文件顺序访问.

大文件直接访问

UNIX inode, 可以将所有的数据块指针集中到索引块中, 方便直接访问文件.

小文件直接访问

链接分配: 可以直接访问文件, 适合小文件直接访问.

[连续分配] :

每个文件在磁盘上占有一组连续的块。
优点: 实现简单, 用于连续分配文件的所需寻道数量最小, 在确实需要寻道时所需的寻道时间也最小.
缺点: 为新文件找到足够可分配空间较为困难, 会存在外部碎片.

[链接分配] :

采用链接分配, 每个文件是磁盘块的链表, 一个链表包含一个文件的内容.
优点: 解决了连续分配的分配文件困难的问题, 因为可以随机散布一个文件内容, 所以不要求文件保存的连续性.
缺点: 仅能有效用于顺序访问文件, 要找到文件的 i 块, 就必须冲文件开始起, 跟着指针一直到第 i 块. 不能有效地支持文件直接访问. 在空间利用上, 指针也占用了额外的空间.

[索引分配(UNIX inode)] :

索引分配在链接分配基础上, 将所有指针放在一起, 依次排列, 形成索引块. 解决了链接分配不能直接访问的问题.
优点: 既没有外部碎片, 让文件可以在磁盘上随机存储, 又解决了直接访问的问题.
缺点: 浪费空间, 每个文件都需要有一个索引块, 而当文件过小时, 也需要分配一个完整的索引块. 而索引块的大小也有不同的机制进行管理.

什么是虚拟设备, 为什么在操作系统中要引入虚拟设备?

将一台物理 I/O 设备虚拟为多台逻辑上的 I/O 设备, 并允许每个用户占用一台逻辑上的 I/O 设备.

这样可以使原来仅允许在一段时间内由一个用户访问的设备(临界资源), 变为在一段时间内允许多个用户同时访问的共享设备.

哲学家就餐问题

概述: 每个哲学家会优先去去拿序号低的一侧的筷子, 然后去拿序号高的一侧的筷子. 不去拿中间的筷子.

// 表示哲学家周围的筷子资源, 初始都为 1, 表示都未被占用.
Semaphore chopsticks[5] = {1,1,1,1,1};

// 表示编号为 i 的哲学见的行动
Procedure philosopher(int i){
    while(true){
        int priority_chopstick = 0;
        thinking();
        if i != 4{
            P(chopsticks[i]);
            P(chopsticks[i+1]);
            eating();
            V(chopsticks[i+1]);
            V(chopsticks[i]);
        } else {
            P(chopsticks[0]);
            P(chopsticks[4]);
            eating();
            V(chopsticks[0]);
            V(chopsticks[4]);
        }
    }
}