苏州大学2013年872试题

数据结构

问答题

1. 如何将图表示为邻接矩阵? 给出其类型定义.

   图是由点和边组成的, 而用邻接矩阵表示图, 就是用一个二维数组表示图中的点和边. 具体而言就是用二维数组的下标表示点, 然后二维数组中的值表示两点之间是否有边. 具体类型定义如下:

    class AdjacencyMatrix(object):
        def __init__(self) -> None:
            self.matrix = []  # 邻接矩阵, 边表
            self.points = []  # 顶点表
            self.sides_num = 0  # 当前边点条数
   

2. 迪杰斯特拉(Dijkstra)算法中, 集合 S 的作用是什么? 算法时间复杂度是多少?

   集合 S 是已经求得的最短路径的顶点的集合. 用于记录哪些点为已经求得的点, 避免点重复求得相同的点. 也是用于结束算法的标志, 当所有点都位于集合 S 中时, 即表明 Dijkstra 算法求解完成.

   Dijkstra 算法的时间复杂度为 O(|V|^2) 其中 V 为图中边的数量.

解决哈希冲突

已知一组关键字为 (10,24,32,17,31,30,46,43,40,63), 设哈希函数 H(key) = key%13.

(1) 请画出用线性探测法处理冲突构造所得来的哈希表.

因此通过线性探测法处理冲突构造来的哈希表为:

(2) 简述查找关键字 43 的查找过程.

首先通过 43%13=4 找到哈希表中的地址为 4 的值 17. 不为 43, 继续找到地址为 5 的 值 31, 不为 43, 继续找到地址为 6 的值 32, 不会 43, 继续找到地址为 7 的值 30, 不会 43, 继续找到地址为 8 的值 46, 不会 43,最后找到地址为 9 的值 43. 最终找 到该关键字.

孩子兄弟法存储的树的结点个数

class CSTree(object):
    """
    孩子兄弟存储法表示的树.
    """

    def __init__(
        self,
        val: Any = None,
        child: Optional["CSTree"] = None,
        next_sibling: Optional["CSTree"] = None,
    ) -> None:
        self.val = val
        self.child = child
        self.next_sibling = next_sibling


def get_node_number(node: Optional[CSTree]) -> int:
    """
    返回节点数量.

    当前节点的子树的节点数量 = 1 + 所有孩子的节点子树的节点数量.

    Args:
        node (Optional[CSTree]): 孩子兄弟法表示的树结构.

    Returns:
        int: 节点总数.
    """
    return (
        1 + get_node_number(node.next_sibling) + get_node_number(node.child)
        if node
        else 0
    )

递归删除单链表中值为 item 的结点

def remove_item(node: Optional[ListNode], target) -> Optional[ListNode]:
    """
    递归删除单链表中值为target的节点.

    如果当前节点的值为target则丢弃当前节点, 返回处理完之后节点的单链表.
    如果当前节点的值不会target, 则处理完之后的节点, 并修改当前节点的next指针, 最后返回当前节点.

    Args:
        node (Optional[ListNode]): 当前节点.
        target ([type]): 要删除的目标值.

    Returns:
        Optional[ListNode]: 删除所有值为target的节点的单链表.
    """
    if node:
        if node.val == target:
            return remove_item(node.next, target)
        node.next = remove_item(node.next, target)
        return node

每位相加的新值的个数

def get_number(n: int) -> int:
    """
    输入一个数, 返回它通过一种运算可以得到所有正整数的个数.

    这种运算的规则是, 对于这个数 n , 可以在其前加一个小于等于 n 一半的数 m , 来构成一个新的数 mn
    , 对于 mn , 可以递归取得一个小于等于 m 一半的数 p, 构成一个新的数 pmn. 依次递推.

    解决方法:
    使用动态规划的思想, 由底至上的递归方法. 因为我们可以看出, 该运算具有重复子结构, 因此可以依次
    取得1-n的所有数的可以得到的个数.

    由于使用了一个 pre 变量来保存需要的前序和, 因此实际上的时间复杂度为O(n), 由于需要大小为 n 的
    数组来保存之前的数据, 因此空间复杂度为O(n).

    Args:
        n (int): 输入的数.

    Returns:
        int: 通过这种运算可以得到正整数的个数.
    """
    dp = [0] * (n + 1)
    pre = 0
    for i in range(1, n + 1):
        if i & 1 == 0:
            pre += dp[i >> 1]

        dp[i] = 1 + pre
    return dp[n]

操作系统

名词解释

1. 磁盘寻道时间

   磁盘寻道时间是指磁盘在读取信息前, 将磁头移动到指定磁道所需要的时间, 这个时间除了跨越 n 条磁道所需要的时间 n*m(m 为跨越一条磁道的时间), 还包括启动磁臂的时间 s.

2. 程序动态装入

   程序动态装入是指把装入模块装入内存后, 并不立即把装入模块中的相对地址转换为绝对地址, 而是把这种地址转换对迟到程序真正要执行才进行. 因此, 装入内存后的所有地址为相对地址.

3. 用户态线程

   有关线程管理的所有工作都由应用程序完成, 内核意识不到线程的存在.

4. 内碎片

   内部碎片是指一片内存空间已经被分配给了某进程, 但不会被利用. 从而造成空降浪费.

5. 临界区

   访问临界资源的那部分代码称为临界区.

判断题

1. 存在 m 个进程的系统中, 死锁进程的个数 k 在 1<k<=m 区间内.

   正确, 死锁是指两个或两个以上的进程在执行过程中, 由于竞争资源或者由于彼此通信而造成的一种阻塞的现象, 若无外力作用, 它们都将无法推进下去. 此时称系统处于死锁状态或系统产生了死锁, 这些永远在互相等待的进程称为死锁进程. 因此死锁进程的个数一定大于 1 且小于 m.

2. 分页引入 TLB 能减少每一次内存的访问时间

   错误, 不一定能减少每一次内存的访问时间. 只有当 TLB 中命中才会减少内存的访问时间, 否则会增加内存访问时间.

3. 在引入虚存的系统中, 磁盘无限大, 进程就能拥有任意大的编址空间.

   错误, 虚拟存储的容量有两个限制条件, 一个是在物理上无法大于内存容量+外存容量. 另一个则是要小于计算机的地址位数能容纳的最大容量. 因此并不是外村容量无限大, 就能够让进程拥有任意大的编址空间.

4. 文件目录一般存放在外存中.

   正确, 系统中文件很多时, 文件目录可能占用大量的空间, 因此文件目录通常存放在磁盘上.

5. 进程从等待到就绪, 一定有就绪到运行.

   错误, 进程从等待到就绪一般是由于除 CPU 外的资源得到分配, 等待 CPU 处理. 与是否有进程从就绪到运行无关.

分析题

在一个请求式分页系统中, 目前系统的利用率如下

• CPU 操作:3%
• 分页磁盘的 I/O 操作:97%
• 其它 I/O 设备:5%

下列方法是否可以提高 CPU 利用率,请分别说明理由。

通过题意分析得出, 分页磁盘的 I/O 操作非常高, 而 CPU 和其他 I/O 设备的利用率非常低, 因此可以判断得出,导致 CPU 利用率低的主要原因是由于进程频繁地切换. 导致正在执行的进程无法充分利用 CPU.

1. 安装一个更加快速的 CPU

   无法提高 CPU 利用率, 因为安装一个更快速的 CPU 无法改变进程频繁切换的现状. 无法增加 CPU 利用率.

2. 撤销内存中的进程

   可以提高 CPU 利用率. 内存中的进程减少, 因此就会多出内存来存放正在运行的内存, 因此就减少了进程的切换, 因此 CPU 就能得到更充分的利用.

3. 增加内存容量

   可以提高 CPU 利用率. 因为内存容量增大, 就可以有更多空间来存放进程数据, 因此就会减少进程的切换的开销, 从而使得 CPU 能够得到充分的利用.

4. 换一个容量更加大的硬盘

   无法提高 CPU 利用率. 内存容量大不出无法通过增加硬盘的容量来解决.

5. 换一个更加快速的硬盘。

   无法提高 CPU 利用率. 更加快速的硬盘也无法减少进程切换的开销.

分析题 2

有一请求式分页系统, 其页表存放在主存中, 对主存的一次存取需要 1.5 微秒, 如果需要访问磁盘,每次磁盘访问时间是 100 微秒. 请回答以下问题:

1. 假如缺页率为 0, 访问一次内存数据的存取时间是多少?

   由于缺页率为零, 因此只需要访问一次内存. 存取时间为: 1.5 微秒

2. 假如缺页率为 0, 系统引入联想寄存器, 平均命中率为 80%. 当页表项在联想寄存器中时, 其査找时间忽略为 0. 访问一次内存数据的平均存取时间为多少?

   平均存取时间为: 0.2*(1.5) = 0.3 微秒

3. 假如系统不采用联想寄存器, 缺页率为 20%, 其中一半需要进行页面置換. 访问一次内存数据的平均存取时间为多少?

   由于不采用联想寄存器, 且缺页率为 20%, 因此访问一次内存的平均存取时间为: 0.2*(1.5+100+1.5) +0.8*(1.5) = 21.8 微秒

论述题

在文件系统中, 目录的作用是什么? 有哪些不同的目录组织形式? 试举一个例子说明根据文件名在目录中査找该文件的创建日期的过程.

文件目录与文件管理和文件集合相关联, 它包含有文件的信息, 用于标识系统中的文件及其物理地址, 供检索时使用.

目录的结构有: 单级目录结构, 两级目录结构, 多级目录结构和无环目录结构.

将用户给定的文件名与目录中的文件名逐次比较, 锁定时, 在访问文件对应的控制块, 在控制块的使用信息中找到文件的创建日期.