苏州大学2008年872试题

数据结构

名词解释

线索二叉树:

对于一个二叉树, 可以根据某种遍历顺序(一般为中序遍历)将二叉树的所有节点形成一个列表. 因此每个节点就会有对应的前驱和后继. 线索二叉树是将二叉树中原本为空的左指针指向前驱节点, 将原本为空的右指针指向后继节点的二叉树.
堆:

堆是一种特别的完全二叉树. 若是其所有父节点总是大于对应的子节点, 则为最大堆; 若是起所有父节点总是小于对应的子节点, 则为最小堆.
邻接矩阵:

用一个二维数组表示图的结构. 对于二维数组中的某点 M[i][j] 的值表示点 i 到点 j 是否有边, 以及边的权值为多少.
稳定排序:

如果待排序表中存在两个元素 R1, R2. 其对应的关键词为 key1=key2, 且在排序前 R1 在 R2 之前, 如果使用某一算法排序后, R1 一定也在 R2 前面, 则称这个排序算法是稳定排序算法.
析构函数:

当对象的生命周期结束时, 自动调用运行函数. 它的目的是清空并释放对象先前占用的存储器资源.

已知不完整的前序遍历和中序遍历, 请填完前序遍历和中序遍历, 并画出二叉树结构.

已知:

前序遍历: AB_E_ICFJ_G
中序遍历: D_HEIA_FKC_

解法: 根据前序遍历和中序遍历的特点: 前序遍历的第一个节点一定是根节点, 因此可以将中序遍历分为两个部分, 分别是左子树和右子树. 然后在前序遍历中找到相应的节点, 然后再找到对应的根节点, 依次递归进行. 直到子树中只有一个节点.

结果:

前序遍历: ABDEHICFJKG
中序遍历: DBHEIAJFKCG
结构:

括号匹配

def bracket_matching(string: str) -> List[Tuple[int, int]]:
    """
    括号匹配, 给一个包含多种括号的字符串, 返回各个括号及其反括号的下标.

    使用栈匹配括号. 具体算法如下:
    - 如果当前字符是括号, 则压入栈.
    - 如果是反括号, 则判断其和栈顶的括号是否匹配. 如果匹配则记录两者的下标, 并推出栈顶的括号
      如果不匹配, 说明字符串是非法的括号字符串.

    Args:
        string (str): 一个包含多种括号的字符串.

    Returns:
        List[Tuple[int, int]]: 返回匹配括号的下标数组·
    """
    res, stack = [], []
    start = {"(": 1, "[": 2, "{": 3}
    end = {")": 1, "]": 2, "}": 3}
    for i, ch in enumerate(string):
        if ch in start:
            stack.append((ch, i))
        if ch in end:
            if end[ch] != start[stack[-1][0]]:
                return None
            else:
                res.append((stack[-1][1], i))
                stack.pop()
    return res if not stack else None

Dijkstra（以后考试不做要求）

def dijkstra(target_map: Map, node: int):
    point_dict = {node: 0}  # 表示起始点到目标点的最小路径长度
    pre_node = {node: node}  # 记录路径中的前驱
    v = {node}  # 记录节点是否已经有了最短路径

    for line_node, line_cost in target_map.get_lines(node):  # 先将起始点能直接遍历到的点记入dict中
        point_dict[line_node] = line_cost
        pre_node[line_node] = node

    for _ in range(target_map.size - 1):
        cost, min_node = float('inf'), None  # 寻找当前最小路径的点
        for index_node in point_dict:
            if index_node not in v and cost > point_dict[index_node]:
                cost = point_dict[index_node]
                min_node = index_node

        v.add(min_node)

        for line_node, line_cost in target_map.get_lines(min_node):  # 更新dict
            if line_node not in point_dict or point_dict[line_node] > line_cost + cost:
                point_dict[line_node] = line_cost + cost
                pre_node[line_node] = min_node

    return format_res(point_dict, pre_node)


def format_res(cost, pre):
    res_dict = {}
    for node in cost:
        res_dict[node] = {'cost': cost[node]}
        path = [str(node)]
        idx = node
        while pre[idx] != idx:
            idx = pre[idx]
            path.append(str(idx))
        res_dict[node]['path'] = '->'.join(path[::-1])
    return res_dict

编写 shell 排序算法

def shell_sort(arr: List[int]) -> List[int]:
    """
    希尔排序.

    Args:
        arr (List[int]): 待排序数组.

    Returns:
        List[int]: 排序完成后的数组.
    """
    length = len(arr)
    for sub in range(length // 2, 0, -1):
        for idx in range(0, length, sub):
            min_idx = idx
            for i in range(idx, length, sub):
                if arr[i] < arr[min_idx]:
                    min_idx = i
            arr[idx], arr[min_idx] = arr[min_idx], arr[idx]
    return arr

操作系统

判断对错, 并分析原因

磁盘访问的最小单位是扇区, OS 以扇区为单位存储和读取数据.

错误, 最小单位是字节; 磁盘储存的最小单位是扇区, 不是 OS.
处于用户态的进程可以访问一切内存和执行一切指令.

错误, 机器处于用户态时, 程序只能执行非特权指令.
系统处于不安全状态不一定是死锁状态

正确
虚拟存储系统中，只要磁盘空间无限大，则作业就能拥有做任意的编址空间.

错误, 编址空间与地址码有关, 与磁盘空间无关.

说明缺页中断, 并说明与硬件中断的区别.

(1) 缺页中断:

若系统发现所要访问的页面不在内存中, 这时就产生一个缺页信号, 即缺页中断。其过程为 : 首先转到操作系统的缺页中断处理程序; 然后程序根据该页在外存的位置将其调入内在中。在调页过程中, 如果内存张有空闲空间,则程序只把缺页装入任何一个空闲存储块中, 再对页表中的相应表现进行修改即可: 若内存中无空闲空间、则必须先淘汰内存中的某些页面 , 若被淘汰页曾被修改过, 则将其写回外存.

(2) 区别

缺页中断在指令的执行期间产生和处理中断; 一条指令可以产生多个缺页中断。

电子转账解决死锁问题

系统会死锁, 是因为对两个账户进行加锁操作时可以分割进行的, 若此时有两个用户同时进行转账, 进程 P1 先对账户 A 进行加锁, 再申请账户 B; 进程 P2 先对账户 B 进行加锁再申请账户 A, 此时产生死锁。解决方法: 可以采用资源顺序分配法对 A、B 账户进行编号, 用户转账时只能按照编号由小到大进行加锁; 也可以采用资源预分配法, 要求用户在使用资源之前将所有资源一次性申请到.