苏州大学2005年872试题

数据结构

什么叫平衡二叉树? 一棵结点数为 n 的平衡二叉树的平均查找时间为多少? 请简述.

它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1, 并且左右两个子树都是一个平衡二叉树.
平均查找时间为 O(logN)

[ 递归的描述方式, 当前高度差不超过 1, 或为空树, 子树也满足同样的条件 ]

有 1000 个无序的数值, 希望从快速排序、基数排序、堆排序、归并排序中选一种排序算法, 能以最快的速度排出 10 个最大的数据来. 试问选哪一种排序算法? 为什么?

应该选择堆排序
快速排序、堆排序、归并排序的平均时间复杂度都为 O(logN) 的排序算法, 基数排序的平均时间复杂度为 O(d(n+rd)), 故首先排除基数排序. 由于只需要选择前 10 大的数, 而堆排序每一次可以取出未排序的数组中的最大数, 故只需要取出 1 次就可以排出最大的 10 个数据.

[ 考察了对于各种排序算法的区别的认识. 考察了最大堆每次可以取出最大数的性质 ]

删除链表中相同的节点

def remove_same(node: Optional[ListNode]) -> Optional[ListNode]:
    """
    删除链表中相同的节点.
    创建一个集合, 然后遍历链表, 如果当前值不在集合中, 则将其加入集合, 如果存在, 则跳过当前结点.
    因为需要跳过结点, 因此指针应该位于当前结点的前驱结点, 跳过结点也就是前驱结点的next指向了后继结点.

    Args:
        node (Optional[ListNode]): 待去重的链表

    Returns:
        Optional[ListNode]: 去重后的链表
    """
    if not node:
        return node
    point_s, idx = set(), node
    while idx.next:
        if idx.next.val in point_s:
            idx.next = idx.next.next
        else:
            point_s.add(idx.next.val)
            idx = idx.next

三元表顺序表转置矩阵，快速转置算法

def fast_transpose(ts: TSMatrix) -> TSMatrix:
    """
    三元组顺序表快速转置算法.
    转置的算法并不复杂, 只需要互换x, y的坐标即可. 但真正困难的是将排序后的坐标排序形成顺序表.
    快速转置算法的原理是利用开始时已经排序好的三元组顺序表的信息, 在常数时间内将其放入新的三元组中.
    具体如下:
        1. 已知未排序的三元组顺序表是先根据x排序, 若x相同, 再根据y排序. 则转置后y一定是从上到下依次
           递增的, 因此我们可以利用这一点.
        2. 先遍历一遍转置后的顺序表, 记录不同的x的分组各有多少个. 将其保存至一个数组中. 这是为了
           在遍历到一个三元组时, 可以方便地知道要将其放入在什么位置.
        3. 最后便利一遍待转置的三元组顺序表, 每次将当前三元组转置后放入目标顺序表中.

    Args:
        ts (TSMatrix): 待转置的三元组顺序表

    Returns:
        TSMatrix: 转置完成的三元组顺序表
    """
    nums = [0 for _ in range(ts.nu + 1)]
    for item in ts.triple_list:
        nums[item.j] += 1
    pot = [0, 1]
    for item in nums[1:]:
        pot.append(pot[-1] + item)
    res = TSMatrix(mu=ts.nu, nu=ts.mu, tu=ts.tu)
    for triple in ts.triple_list:
        triple.i, triple.j = triple.j, triple.i
        res.triple_list[pot[triple.i] - 1] = triple
        pot[triple.i] += 1
    ts = res
    return ts

全排列

def permutations(lst: list) -> List[int]:
    """
    输出数组的全排列.
    使用dfs算法输出数组的全排列.
    在每次调用函数时, for循环遍历所有arr[le]的情况, 然后递归去寻找 (le+1, ri)的全排列.
    直到le==ri, 则保存当前的arr为一个排列.
    这是一种自顶向下的实现方法.

    Args:
        lst (list): 输入的数组

    Returns:
        List[int]: 全排列的结果
    """
    res = []

    def dfs(arr: list, le: int, ri: int):
        if le == ri:
            res.append(arr[:])
        else:
            i = le
            for num in range(le, ri):
                arr[num], arr[i] = arr[i], arr[num]
                dfs(arr, le + 1, ri)
                arr[num], arr[i] = arr[i], arr[num]

    dfs(lst, 0, len(lst))
    return res

操作系统

请解释并比较以下概念

共享设备和独占设备

共享设备: 通过分时共享使用的设备.
在申请设备时, 如果设备空闲, 就将其独占, 不再允许其他进程申请使用.

SMP 和 ASMP

SMP: Symmetric multiprocessing, 对称多处理器结构, 在一个计算机上汇集了一组处理器(多 CPU), 每个处理器之间共享子系统和总线结构.
ASMP: Asymmetric multiprocessing, 非对称多处理器结构, CPU 被不平等对待.

物理地址和逻辑地址

物理地址: 内存中物理单元的集合.
面向用户和程序员的地址空间.

简答题

目录在文件系统中的作用是什么?

使文件控制块与文件一一对应

在操作系统中引入线程有什么好处?

减小程序在并发执行时的时空开销, 提高操作系统并发性能.

在设计操作系统时, 主要哪几种结构可供选择?

大内核系统将操作系统的主要功能模块都作为一个紧密联系的整体运行在核心态, 从而为应用提供高性能的系统服务.
微内核系统将内核中最基本的功能(进程管理等)保留在内核, 将那些不需要在核心态执行的功能移动到用户态执行, 降低了内核设计的复杂性.

进程调度

内存有 3 页数据区 [2, 3, 4, 5, 3, 4, 1, 2, 3, 5, 1, 4, 1, 4, 5, 1, 3, 2, 1, 3] 采用一下算法的缺页次数和发生缺页的时间.

FIFO
LRL
OPT

PV 操作

服务员放香蕉和草莓, 男人吃草莓, 女人吃香蕉. 水果盘只有一个空位.

Semaphore cap = 1;  // 表示水果盘的剩余容量
Semaphore stra = 0;  // 表示水果盘中草莓的剩余数量
Semaphore bana = 0;  // 表示水果盘中香蕉的剩余数量

// 服务员进程
Procedure Waiter{
    while(true){
        P(cap);
        将水果放入水果盘中;
        if(放入的是草莓){
            V(stra);
        }else if(放入的是香蕉){
            V(bana);
        }
    }
}

// 男人进程
Procedure Man{
    while(true){
        P(stra);
        从水果盘中取出草莓;
        V(cap);
        吃掉草莓;
    }
}

// 女人进程
Procedure Woman{
    while(true){
        P(bana);
        从水果盘中取出香蕉;
        V(cap);
        吃掉香蕉;
    }
}