苏州大学2017年872试题

数据结构

线性表

用顺序存储结构实现线性表时, 在线性表中查找等于 x 的元素, 通常先在线性表尾部添加一个等于 x 的元素, 这样做可以加快查找速度, 为什么? 用单链表实现线性表时, 能否加快速度, 为什么?

之所以可以加快查找速度, 是因为如果不添加一个等于 x 的元素, 就需要在每次循环中判断数组是否越界. 而添加了一个等于 x 的元素后, 最后一定能找到等于 x 的元素, 因此就无需判断是否越界. 从而减少了每次循环的判断越界的 CPU 计算, 因此加快了查找速度.

而在用单链表实现的线性表中, 由于链表若是要在尾部添加一个等于 x 的元素, 就需要完全遍历一遍链表. 回消耗大量的时间, 因此无法加快查找速度.

基数排序

用基数排序堆关键字序列 012,321,234,543,456,765,678,987,890,109 从小到大排序,写出各趟排序结果.

第一趟: 890, 321, 012, 543, 234, 765, 456, 987, 678, 109

第二趟: 109, 012, 321, 234, 543, 456, 765, 678, 987, 890

第三趟: 012, 109, 234, 321, 456, 543, 678, 765, 890, 987

最小的 100 个数

def less_nums(n: int) -> List[int]:
    """
    一个序列有如下性质:
    1. 1 在序列中.
    2. 如果x在序列中, 那么2*x, 3*x, 5*x也在序列中.
    求这个序列中最小的n个数字.

    Args:
        n (int): 输入.

    Returns:
        List[int]: 序列中最小的n个数字.
    """
    res = [1]

    def dfs(idx: int):
        if any(not idx % item for item in [2, 3, 5]):
            res.append(idx)
            nonlocal n
            n -= 1
        if n != 1:
            dfs(idx + 1)

    dfs(1)
    return res

排序树中第 k 大元素

def max_k(node: Optional[SearchTree], k: int) -> Optional[SearchTree]:
    """
    求一个二叉排序树中第K大的元素. 每个结点有一个特殊的属性r_size, r_size = 右子树的结点
    个数 + 1.

    可以根据 r_size 求解. 对于每个节点, 可以求得右子树中比它本身大的个数, 那么就可以根据
    二叉排序树的性质进行递归求解了.

    Args:
        node (Optional[SearchTree]): 二叉排序树根结点.
        k (int): 第K大的数.

    Returns:
        Optional[SearchTree]: 返回第K大的结点.
    """
    if not node:
        return None
    if node.r_size == k:
        return node
    elif node.r_size < k:
        return max_k(node.left, k - node.r_size)
    else:
        return max_k(node.right, k)

邻接表的广度有限搜索算法

def bfs(ad_list: AdjacencyList, start: int, end: int)->bool:
    """
    使用广度优先算法搜索用邻接表实现的有向图是否存在一条从 start 出发, 到 end 结束的路径.

    简单的广度优先搜索, 比较困难的反而是构建数据结构并初始化一个图.

    Args:
        ad_list (AdjacencyList): 用邻接表实现的有向图.
        start (int): 出发点.
        end (int): 终点.

    Returns:
        bool: 是否存在这样一条路径.
    """
    from collections import deque

    dq = deque()
    dq.appendleft(start)
    path = set()
    while dq:
        idx = dq.pop()
        if idx == end:
            return True
        next_node = ad_list.get_next_node(idx)
        while next_node:
            if next_node not in path:
                dq.appendleft(next_node.val)
                path.add(next_node)
            next_node = next_node.next
    return False

操作系统

判断题

1. 操作系统实现双模式需要硬件支持.

   正确, 操作系统切换用户态和内核态需要通过中断、异常、陷入机制. 都需要硬件支持.

2. 操作系统通过人机接口和系统程序为用户提供服务.

   错误, 通过程序接口和操作接口.

3. 一个系统有 n 个进程, 最多有一个进程处于运行状态.

   错误, 多核操作系统可以使多个进程处于运行状态.

4. 线程是资源分配的基本单位。

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

5. 在有 m 个进程的系统中产生死锁时, 死锁进程的个数 k 满足条件 1<k<m.

   错误, 死锁进程的个数 k 满足条件 1<k<=m.

6. 触摸屏是个输出设备

   错误, 屏幕可以显示画面, 是输出设备, 而触摸可以进行操作, 是输入设备. 因此触摸屏即是输出设备又是输入设备.

7. 一个 1200RPM 磁盘的平均旋转延迟时间是 5ms

   错误, 平均旋转延迟为 60*1000/1200/2 = 2.5ms.

8. 磁盘上存储的文件一般组织为顺序文件.

   正确.

9. 产生颠簸的原因是内存中的进程太多.

   错误, 运行进程的大部分时间用于进行页面的换入和换出, 而几乎不能完成任何有效的工作, 称这时的进程处于“抖动”状态, 也称为系统颠簸. 因此产生颠簸的原因是可用内存过小, 内存中的进程太多仅仅是可能的一个因素.

10. 树形目录和无环图目录无法实现文件共享.

    错误, 树形目录只是不便于实现文件的共享. 无环图目录在树形目录的基础上, 更加方便的实现了多个用户间的文件共享.

PV 操作

使用管程来实现读者优先的读写者问题, 并写出管程的伪代码以及读写者的伪代码.

定义管程代码段

1. 定义过程 start_read()
2. 定义过程 end_read()
3. 定义过程 start_write()
4. 定义过程 end_write()

monitor RW{  // 定义管程的过程
    int read_count = 0;
    bool is_writing = false;
    condition r, w;

    void start_read(){
        if(is_writing){
            wait(r);
        }
        read_count++;
        signal(r);
    }

    void end_read(){
        read_count--;
        if(read_count==0){
            signal(w);
        }
    }

    void start_write(){
        if(read_count!=0 || is_writing){
            wait(w);
        }
        is_writing = true;
    }

    void end_write(){
        is_writing = false;
        signal(r);
    }
}

读写者代码段

void reader(){
    while(1){
        RW.start_read();
        // 读取文件操作
        RW.end_read();
    }
}

void writer(){
    while(1){
        RW.start_write();
        // 写入文件操作
        RW.end_write();
    }
}

逻辑地址和物理地址

一个进程 p 的空间为 64k, 运行在一个请求式分页系统中, 每个页面大小为 8k, 该进程的页表如下.

其中, 有效位=1 表示页面在内存, 0 表示页面不在内存, 请将逻辑地址 0x050c、0x1302、0x1f71、0x2c57、0x4400 转换为对应的物理地址并写出计算过程.

由于空间为 64K, 每个页面大小为 8K, 因此最多有 8 个页面. 因此虚拟地址中页号需要占用 3 位. 页内偏移占用 13 位.

因此:

1. 0x050c 二进制为: 000|0 0101 0000 1100, 页号为 0, 因此页框号为 12 = 1100, 因此转换为物理地址后为 0001 1000 0101 0000 1100 = 0x1850c
2. 0x1302 二进制为: 000|1 0011 0000 0010, 页号为 0, 因此页框号为 12 = 1100, 因此转换为物理地址后为 0001 1001 0011 0000 0010 = 0x19302
3. 0x1F71 二进制为: 000|1 1111 0111 0001, 页号为 0, 因此页框号为 12 = 1100, 因此转换为物理地址后为:0001 1001 1111 0111 0001 = 0x19F71
4. 0x2c57 二进制为: 001|0 1100 0101 0111, 页号为 1, 因此页框号为 3 = 0011, 因此转换为物理地址后为:0000 0110 1100 0101 0111 = 0x06c57
5. 0x4400 二进制为: 010|0 0100 0000 0000, 页号为 2, 因此页框号为 0 = 0000, 因此转换为物理地址后为:0000 0000 0100 0000 0000 = 0x00400

文件系统

一个文件系统采用索引方式分配磁盘, 其中磁盘块的大小为 4KB, 索引块大小为 32 位. 回答如下问题:

1. 一级索引的文件 A, 二级索引的文件 B, 三级索引的文件 C 容量最大为多少.

   索引项大小为 32/8 = 4B, 4KB/4B = 1024 块, 因此一个索引文件可以存放 1024 个索引项.

   因此 A 的最大容量为 1024*4KB = 4MB, B 的最大容量为 1024*1024*4KB = 4GB, C 的最大容量为 1024*1024*1024*4KB = 4TB.

2. 假设上述 A、B、C 文件控制块在内存, 则删除文件 A、B 和 C 的任意一块物理块需要读或写多少个磁盘块.

   删除 A 中的一块物理块: 首先通过文件控制块访问索引块删除目标物理块的索引. 因此需要访问 1 次.

   删除 B 中的一块物理块: 首先通过文件控制块访问一级索引块, 然后访问二级索引块删除目标物理块的索引.因此需要访问 2 次.

   删除 C 中的一块物理块: 首先通过文件控制块访问一级索引块, 然后访问二级索引块, 然后访问三级索引块删除目标物理块的索引, 因此需要访问 3 次.

3. 假设上述文件 A、B 和 C 的文件控制块在内存, 则在文件 A、B 和 C 尾部插入一个物理块最多需要读或写多少个磁盘块?

   在 A 中插入一块物理块: 首先通过文件控制块访问索引块, 然后通过索引项访问物理块 . 因此需要访问 2 次.

   在 B 中插入一块物理块: 首先通过文件控制块访问一级索引块, 然后访问二级索引块, 最后访问物理块. 因此需要访问 3 次.

   在 C 中插入一块物理块: 首先通过文件控制块访问一级索引块, 然后访问二级索引块, 然后访问三级索引块,最后访问物理块, 因此需要访问 4 次.

分析题

请举例说明, 和 FCFS 相比, SJF 可以获得更短的平均等待时间, RR 可以获得更短的平均响应时间.

有如下进程, 其加入时间和需要运行时间如下:

如果使用 FCFS 算法:

执行顺序为: P1->P2->P3

平均等待时间为: (0+2+5)/3 = 2.33

平均响应时间为: (0+2+5)/3 = 2.33

如果使用 SJF 算法:

执行顺序为: P1->P3->P2

平均等待时间为: (0+1+3)/3 = 1.33

平均响应时间为: (0+1+3)/3 = 1.33

如果使用 RR 算法:

假设时间片长度为 1.

那么执行顺序为: P1->P2->P3->P1->P2->P1->P2->P2

平均等待时间为: (3+3+0)/3 = 2

平均响应时间为: (0+0+0)/3 = 0

根据这个例子, 就能看出 SJF 相比于 FCFS 可以获得更短的平均等待时间, RR 相比于 FCFS 可以获得更短的平均响应时间.