苏州大学2014年872试题

数据结构

判断题

1. 在一个图中,所有顶点的度数之和等于所有边的总数.

   错误, 所有顶点的度数只和等于所有边的总数的两倍.

2. 快速排序在被排序数据已基本有序的情况下最易发挥其长处.

   错误, 快速排序在基本无序的情况下发挥其长处. 冒泡排序在数据已基本有序的情况下最易发挥其长处.

3. 求子串的定位操作称为串的模式匹配.

   正确. 串的模式匹配, 就是求模式串在主串中的位置.

Dijkstra

迪杰斯特拉(Dijkstra)算法的用途是什么? 说明其基本思想, 并验证该算法的正确性. 为实现该算法, 如何设计图的数据结构?

1. 用途是求图中充某一个点开始的, 到其他点的最短路径.
2. 基本思想是通过不断找到从已求点集 v 出发的一条最短且不成环的边, 并不断将边的终点加入到点集 v 中,并用一个数组记录其最短路径长度和边的出发点. 直到所有点都并入了点集 v 中, 则表示算法求解完成. 其中数组记录的是每个点的最短路径长度, 而边点出发点则记录了最短路径的上一步的点, 因此可以根据上一步的点推导出最短路径.
3. 如果存在这样的一个点 v1: v1 已经被并入了点集 v, 而在算法之后的过程中, 存在一点 v2, 使得 源点->v2->v1 的路径比 源点->v1 的路径更短. 那么就必须保证 源点 ->v2 的长度比 源点->v1 的长度更短, 而这样就会导致 v2 应该先于 v1 并入点集 v, 与假设矛盾. 因此通过反证法可以证明 Dijkstra 算法的正确性.

4. 可以设计如下数据结构:

   class graph(object):
       def __init__(self):
           self.vexs = []
           self.edge_num = 0
           self.matix = []
   

分解质因数为单链表

def get_prime_factor(num: int) -> ListNode:
    """
    将一个正整数分解其质因数由到小组成的链表.

    例如对于 2100 可以分解成 7 5 5 3 2 2,
    因此就返回链表: 7->5->5->3->2->2.

    Args:
        num (int): 输入的正整数.

    Returns:
        ListNode: 质因数由大到小组成的链表.
    """
    head = ListNode()
    cur, idx = head, num // 2
    while num > 1 and idx > 1:
        if num % idx == 0:
            for i in range(2, idx // 2 + 1):
                if idx % i == 0:
                    break
            else:
                cur.next = ListNode(idx)
                cur = cur.next
                num //= idx
                idx += 1
        idx -= 1
    return head.next

验证二叉树是否严格

def is_strict_binary(node: TreeNode) -> bool:
    """
    判断一个二叉树是否严格二叉(指节点的出度只能为 0 或 2, 不存在出度为 1 的节点)

    采用递归求解.

    判断一个节点作为根节点的子树是否严格二叉的判定过程为:

    1. 若出度为 2, 则需要保证左右子树都为严格的二叉树
    2. 若出度为 1, 则不为严格二叉树.
    3. 若出度为 0, 则为严格的二叉树.

    Args:
        node (TreeNode): 输入的二叉树根节点.

    Returns:
        bool: 该二叉树是否严格二叉.
    """
    if node.left and node.right:
        return is_strict_binary(node.left) and is_strict_binary(node.right)
    elif node.left or node.right:
        return False
    return True

求顺序表第四分之一小的元素

def get_quarter(arr: List[int], lo: int = 0, hi: int = 0) -> int:
    """
    求顺序表中第 1/4 小的元素.

    最优算法: 快速排序分组 + 二分
    基本思路如下: 通过一趟快速排序将整个顺序表分为两部分, 然后根据分界点的位置判定下次
    分组是在哪一组或者是否得到答案. 这样可以最小地比较顺序表中的元素, 就得到答案.

    Args:
        arr (List[int]): 顺序表
        lo (int, optional): 左区间. Defaults to 0.
        hi (int, optional): 右区间. Defaults to 0.

    Returns:
        int: 第 1/4 小的元素.
    """
    # 初始化变量
    k = len(arr) // 4
    if not hi:
        hi = len(arr) - 1
    if lo >= hi or len(arr) < 4:
        return -1
    key = arr[lo]
    left, right = lo, hi

    # 进行快速排序的一次遍历
    while left < right:
        while left < right and key < arr[right]:
            right -= 1
        arr[left] = arr[right]
        while left < right and key > arr[left]:
            left += 1
        arr[right] = arr[left]
    arr[left] = key

    # 二分
    if left == k:
        return arr[left]
    elif left < k:
        return get_quarter(arr, left + 1, hi)
    else:
        return get_quarter(arr, lo, left)

操作系统

判断题

1. 在任何操作系统中, 系统资源分配的最小单位是线程.

   错误, 系统资源分配的最小单位是进程. 线程是 CPU 调度的最小单位.

2. 处于死锁状态的进程必然拥有至少ー个互斥资源.

   错误, 处于死锁状态的进程可能在等待其他进程释放互斥资源, 不一定拥有至少一个互斥资源.

3. 虚拟存储器的最大容量是内存和外存的容量之和.

   错误, 虚拟存储器的最大容量受到两个条件的限制, 一是内存和外存容量之和的物理限制, 二是计算机的地址位数能容纳的最大容量的限制.

4. 决定文件访问效率的因素有 2 个, 分别是文件的物理结构和逻辑结构.

   正确.

5. 假脱机(Spooling)技术可以减少进程的上下文切换次数.

   正确. Spooling 技术是在内存和设备之间添加缓存区. 减少了等待设备 IO 所引起的进程切换, 也就减少了进程上下文切换次数.

简答题 1

分别从文件的逻辑结构、物理结构和文件目录三个不同角度入手, 举一个实例谈谈如何提高文件存取的效率.

文件的逻辑结构是从用户观点出发看到的文件组织形式.文件的物理结构是从实际观点出发 , 又称文件的存储结构, 是指文件在外存上的组织形式.

按逻辑结构, 文件有无结构文件和有结构文件两个类型. 有结构文件又包括顺序文件、索引文件、索引顺序文件和直接文件和散列文件.顺序文件对顺序文件的效率是所有逻辑文件中最高的; 索引文件建立了一张索引表以加快索引速度索引顺序文件是顺序和索引两种组织形式的结合; 索引顺序文件和直接文件和散列文件给定记录的键值或通过 Hash 函数转换的键值直接记录的物理地址, 从而提高了存取效率, 但可能会起冲突.

文件目录实现按名存取, 提高目录的检索速度, 将对系统性能的提高有极大的帮助.

简答题 2

从资源共享、创建和结束三个方面分别谈谈进程和它创建的子进程、进程和它创建的线程之间的关系.

1. 进程和它创建的子进程

   一个进程创建另一个进程, 此时创建者为父进程, 被创建的进程称为子进程. 子进程可以进程父进程所拥有的资源. 当子进程被撤销时应将从父进程那里获得的资源归还给父进程. 此外在撤销父进程时也必须撤销其所有子进程.

2. 进程和它创建的线程

   进程是分配资源的基本单位, 而线程不拥有系统资源. 但线程可以访问其隶属的进程的系统资源. 一个线程被创建后便开始了它的生命周期, 直到终止. 线程在生命周期内会经历阻塞态、就绪态和运行态等各种状态.

解答题

一个分页存储系统(采用二级页表), 页表存放在内存:

1. 如果访问一次内存需要 200ns, 则访问一个内存单元需要多少时间?

   由于采用分页存储系统, 因此如果想要访问一个内存单元, 就需要先在第一级页表得到内存单元在第二级页表的位置, 然后再访问第二级页表找到内存单元的存储地址, 最后通过地址访问内存单元. 因此需要 (2+1)*200= 600ns

2. 如果该系统采用三级页表, 则访问一个内存单元需要多少时间?

   如果采用三级页表, 就需要多访问一个页表, 因此需要 (3+1)*200 = 800ns

3. 如果该系统引入联想寄存器, 90% 的页表项可以在快表中命中, 则访问一个内存单元平均需要多少时间?(假设访问一次快表需要 10ns)

   访问一个内存单元的平均时间为 0.9(10+200) + 0.1(600+10) = 250ns

4. 如果该系统采用虚拟存储技术, 页面的命中率为 80%, 每次缺页处理平均需要花费 50000s, 则访问一个内存单元平均需要多少时间?

   访问一个内存单元的平均时间为: 0.8(600)+0.2(400+200+50000+200) = 10640

5. 如果该系统同样采用虚拟存储技术, 页面的命中率为 80%, 但缺页时有 10% 的页面需要进行页面置换(不需要页面置换的缺页处理需要花费 40000ns,需要页面置换的缺页处理需要花费 80000ns), 则访问一个内存单元平均需要多少时间?

   访问一个内存单元平均需要的时间为 0.8(600)+0.2(400+200+0.180000+0.940000+200) = 9440ns

PV 操作

有四个进程 S1、R1、R2 和 R3, 其中 S1 向缓冲区 BUFF 发送消息, R1、R2 和 R3 分别从缓冲区中接收消息. 发送和接收的规则如下:

1. 缓冲区 BUFF 大小为 1.
2. 只有当缓冲区有消息时, R1、R2 和 R3 才能从缓冲区中取出消息.
3. 每个消息 R1、R2 和 R3 必须各取 1 次. 只有当它们都取过后, 才能清空缓冲区.
4. 每个消息 R1、R2 和 R3 只能取 1 次请用信号量机制来实现这 4 个进程间的同步.

Semaphore SR1=SR2=SR3=1;
Semaphore R1=R2=R3=0;

Procedure S1(){
    while(1){
        // Generate message

        P(SR1);
        P(SR2);
        P(SR3);

        // Send messages to buffer

        V(R1);
        V(R2);
        V(R3);
    }
}

Procedure R1(){
    while(1){
         P(R1);

        // Receive messages from buffer

        V(SR1);
    }
}

Procedure R2(){
    while(1){
        P(R2);
        // Receive messages from buffer

        V(SR2);
    }
}

Procedure R3(){
    while(1){
        P(R3);

        // Receive messages from buffer

        V(SR3);
    }
}