苏州大学2015年872试题

数据结构

判断题

1. 若有一个栈的输入序列是 1,2,3,…,100, 输出序列的第一个元素是 100, 则第 50 个输出元素是 50.

   错误, 第一个输出的是 100, 那么第 50 个输出的是 51.

2. 在一个有向图中, 所有顶点的入度之和等于所有顶点的出度之和.

   正确, 对于每一条边, 都会增加一个出度和一个入度, 因此所有顶点的入度之和等于所有顶点的出度之和.

3. 在拓扑排序序列中, 任意两个结点 i 和 j, 都存在从 i 到 j 的路径.

   错误, 如果在拓扑排序序列中, i 在 j 之前, 那么都存在从 i 到 j 的路径. 如果 i 在 j 之后, 那么不存在
   从 i 到 j 的路径.

4. 在哈希表中, 装填因子的值越小, 存取元素时发生冲突的可能性就越小.

   正确, 装填因子 = 关键字个数 / 表长. 因此装填因子越小, 代表空间浪费越多, 冲突可能性越小.

5. 任何一个无向连通图的最小生成树只有一棵.

   错误, 可能存在不同的最小生成树.

简答题

简述堆排序算法的基本思想. 对于快速排序而言, 堆排序有哪些优势? 对于归并排序而言堆排序有哪些优势? 假定
有 8000 个整数, 需要找出最大的 10 个数, 在堆排序、快速排序、基数排序方法中, 采用哪种方法最好? 请说明
理由.

堆排序是通过将关键字调整为堆, 然后依次将堆顶的元素和放入到有序区, 每次放入后都需要整理堆的结构. 直到
全部的元素都放入到有序区中.

对于快速排序, 堆排序在最坏的情况下时间复杂度也为 O(n*log(n)), 而快速排序在最坏情况下时间复杂度为
O(n^2), 并且堆排序的空间复杂度为 O(1), 而快速排序的空间复杂度为 O(log(n)).

对于归并排序, 堆排序的空间复杂度为 O(1), 而归并排序的空间复杂度为 O(n).

采用堆排序最好, 因为如果使用大顶堆, 只需要进行 1 次建堆, 10 次推出并调整堆就可以选出 10 个最大的数了
. 而不必等到全部数排序好后选出, 因此堆排序最快.

递归创建二叉树

def init_tree_by_list(
    chs: Optional[List[str]], idx: int = 0
) -> Optional[TreeNode]:
    """
    递归创建二叉树.

    Args:
        chs (Optional[List[str]]): 二叉树堆值的列表.
        idx (int, optional): 当前节点所在列表的下标. Defaults to 0.

    Returns:
        Optional[TreeNode]: 生成的二叉树.
    """
    if chs and idx < len(chs):
        return TreeNode(
            val=chs[idx],
            left=init_tree_by_list(chs, idx * 2 + 1),
            right=init_tree_by_list(chs, idx * 2 + 2),
        )

两数之和-链表版

def two_sum2(node: DulLinkedList, target: int) -> str:
    """
    两数之和, 双链表版.

    由于采用双链表, 并且有序, 因此可以使用双指针法.

    Args:
        node (DulLinkedList): 双链表.
        target (int): 目标数.

    Returns:
        str: 返回信息.
    """
    cur = node
    while cur.next:
        cur = cur.next
    tail, head = cur, node
    while tail and head and tail != head:
        if tail.val + head.val == target:
            return f"{target} = {head.val} + {tail.val}"
        elif tail.val + head.val < target:
            head = head.next
        else:
            tail = tail.pre
    return "not exist two numbers sum equals target."

两个有序顺序表的中间值

def two_order_list_median(lst1: list[int], lst2: list[int]) -> float:
    """
    二分法求解.

    对于两个有序数组, 可以划分为两部分, 一部分小于等于中位数, 一部分大于中位数. 而中位数
    就可以在这条边界旁取得. 因此我们可以通过二分的方法分别在两个数组中找到这条边界.

    Args:
        lst1 (list[int]): 顺序表1
        lst2 (list[int]): 顺序表2

    Returns:
        float: 中位数.
    """
    m, n = len(lst1), len(lst2)

    def get_Kth_element(k):
        idx1, idx2 = 0, 0
        while True:
            if idx1 == m:
                return lst2[idx1 + k - 1]
            if idx2 == n:
                return lst1[idx1 + k - 1]
            if k == 1:
                return min(lst1[idx1], lst2[idx2])

            new_idx1 = min(idx1 + k // 2 - 1, m - 1)
            new_idx2 = min(idx2 + k // 2 - 1, n - 1)
            pivot1, pivot2 = lst1[new_idx1], lst2[new_idx2]
            if pivot1 <= pivot2:
                k -= new_idx1 - idx1 + 1
                idx1 = new_idx1 - 1
            else:
                k -= new_idx2 - idx2 + 1
                idx2 = new_idx2 + 1

    total_length = m + n
    if total_length % 2 == 1:
        return get_Kth_element((total_length + 1) // 2)
    return (
        get_Kth_element(total_length // 2)
        + get_Kth_element(total_length // 2 + 1)
    ) / 2

操作系统

判断题

1. 所有用户进程都必须常驻内存.

   错误, 并非所有进程都常驻于内存中的, 一般只有正在执行的进程在内存中.

2. 有 m 个进程的操作系统出现死锁时, 死锁进程个数的范围为 1<k<=m.

   正确, 死锁是由两个或两个以上进程对于互斥资源的抢夺造成的. 因此死锁进程个数的范围为 1<k<=m.

3. 除了 FCFS, 其它的磁盘调度算法都会出现饥饿现象.

   错误, SCAN 算法也不会出现饥饿现象.

4. 増加内存中的进程数量, 可以提高 CPU 的利用率.

   错误, 增加内存中的进程数量, 可能会导致分配给现有正在运行的进程的内存减少, 从而使得需要花费更多的
   时间用于内存调度, 从而减少了 CPU 的利用率.

5. 在分页式存储管理中, 引入 TLB 可减少每一次的内存访问时间.

   错误, 如果需要访问的内存地址不存在于 TLB 中(未命中), 会增加访问其的时间.

解答题

因此 5 个进程执行的顺序图为: P1->P2->P2->P4->P3->P3->P1->P1->P3->P5->P5->P5

因为 周转时间 = 完成时间 - 到达时间, 并且 响应时间 = 第一次处理时间 - 到达时间.

因此每个进程的周转时间和响应时间为:

PV 操作

Semaphore msg = 1 // 用于实现对缓冲区的互斥操作, 初始值为1
Semaphore reader[n]=0 // 控制n个读者是否已经读取完消息, 全部初始为1

Procedure B(){  // 发送者进程/
    while(1){
        P(msg);
        // 清空缓冲区
        // 将消息发送至缓冲区
        int i;
        for(i=0;i<n;i++){
            V(reader[i]);
        }
        V(msg);
    }
}

Procedure A(int i){ // 接收者进程, i标记了为哪一个接收者.
    while(1){
         P(reader[i])
        P(msg);
        // 从缓冲区取出消息
        // 读取消息
        // 将消息放回缓冲区
        V(msg);
    }
}

分析题

对于每条记录, 需要大小为 4*2 + 2 + 128*2 + 18 + 2 + 4 = 290 Byte

文件的总大小为 290000000 Byte = 290000 KB = 290 MB

逻辑文件结构: 由于主要操作为根据姓名进行记录查询. 因此可以根据姓名对文件进行分目录存放. 相同长度姓名
的记录在同一个目录中, 这样可以方便根据姓名查找. 因此可以将这个文件的逻辑文件信息连续存放, 即采用顺序
文件的方式.

物理文件结构: 由于每条记录的大小相差不大. 因此可以采用连续分配的方式, 把逻辑文件中的记录顺序地存储在
相邻的物理盘块中; 这样查找速度快, 且没有太大的空间浪费.

(1) 因为每个磁盘块为 1KB, 因此文件需要 290000 个磁盘块.

(2) 平均需要 290000/2 = 145000 个磁盘块.