苏州大学2016年872试题

数据结构

散列表

什么是哈希函数? 什么是哈希查找? 如何解决冲突? 分析影响哈希查找算法的性能的因素.

哈希函数: 根据给定的关键字来计算出关键字再给定点哈希表中的地址的函数.

哈希查找: 是根据哈希函数并结合冲突解决方法在已构造的哈希表中查找关键字的一种查找方法. 哈希查找的时间复杂度一般为 O(1)

解决冲突可以通过多种方法进行解决. 比如: 开放定址法, 链地址法; 线性探测法式从发生冲突的地址开始依次查找下一个地址, 直到找到一个空位置为止. 而链地址法是将地址相同的元素使用一个链表记录下来, 这样访问的时候就只需要遍历链表.

影响哈希查找算法性能的因素: 哈希表的性能主要看平均查找长度, 与关键字个数无关, 与装填因此有关.

二叉查找树

什么是二叉查找树? 什么是 AML 树? 将关键字 50,40,30,60,70,10,20,80 依次插入一棵初始为空的 AML 树, 画出最后所得的 AML 树.

二叉查找树又称二叉排序树, 它是一棵空树或者是具有下列性质的二叉树: 1. 若它的左子树不为空, 则左子树的所有节点的值均小于它的根结点的值. 2. 若它的右子树不为空, 则右子树上所有结点的值均大于它的根结点的值. 3. 它的左, 右子树也为二叉排序树.

AVL 树: 以树中所有结点为根的树的左右子树高度之差的绝对值不超过 1 的特殊的二叉查找树.

最后构建的 AVL 树为:

去除链表重复的元素

def copy_without_same_node(node: ListNode) -> ListNode:
    """
    去除链表的重复结点.

    采用set去重.

    Args:
        node (ListNode): 链表.

    Returns:
        ListNode: 去重后的链表.
    """
    new_node = node
    node_map = {node.val}
    while node.next:
        if node.next.val in node_map:
            node.next = node.next.next
        else:
            node_map.add(node.next.val)
            node = node.next
    return new_node

数组中最小连续序列

def min_subsequence(arr: list[int]) -> int:
    """
    求顺序表中连续序列的最小值.

    和求连续序列的最大值相同的做法, 只需要遍历一次顺序表, 在遍历过程中, 记录当前总和,
    如果大于零则丢弃前面的序列, 因为大于零的之前的序列无法在最后获得最小值.

    Args:
        arr (List[int]): 顺序表

    Returns:
        int: 顺序表中连续序列的最小值.
    """
    res, idx = 0, 0
    for x in arr:
        idx += x
        if idx > 0:
            idx = 0
        else:
            res = min(idx, res)
    return res

n 个结点有多少种不同二叉树

from functools import lru_cache


@lru_cache()
def n_node_tree_num(n: int) -> int:
    """
    n 个结点可以有多少种不同的二叉树.

    由于该问题具有重复子结构的特性, 具体为

    f(n) = f(0)*f(n-1) + f(1)*f(n-2) ... f(n-2)*f(1) + f(n-1)*f(0)

    由于题目要求使用递归函数的形式编写, 而若是普通递归会造成大量的重复计算, 因此采用
    Python的函数缓存, 将函数结果保存下载, 避免重复计算.

    Args:
        n (int): n 个结点.

    Returns:
        int: 可以构成的二叉树个数.
    """
    if n == 0:
        return 1
    return sum(
        n_node_tree_num(i) * n_node_tree_num(n - i - 1) for i in range(n)
    )

操作系统

判断题

操作系统最主要的目标是运行程序.

操作系统最主要的目标是方便性和有效性.
进程 A 和 B 共享变量 x, 需要互斥执行; 进程 B 和 C 共享变量 y, 需要互斥执行. 因此, 进程 A 和 C 也必须互斥执行.

错误, A 和 C 可以同时执行.
存在外碎片的内存分配机制有连续分配和段页式分配两种。

错误, 连续分配不会存在外碎片, 会存在已经分配的内存却不会使用的内碎片.
如果一个计算机的硬盘为 4GB,每个块的大小为 512B,用位示图来管理该硬盘的空间,则位示图的大小为 8MB。

4*1024*1024*1024/512 = 8MB, 所以正确.
当时间片轮转算法的时间片足够大时, 该算法等同于先来先服务算法.

正确, 时间片足够大, 说明可以在一个时间片完成一个进程. 也就相当于先来先服务算法.
Unix 所采用的设计结构是模块化结构.

错误, Unix 采用的设计结构是整体结构.
用户级线程适合运行在多处理器架构下.

错误, 用户级线程是由程序自己控制调度的, 因此内核一次只会为一个进程分配一个处理器. 因此是内核级线程更适合运行在多处理器架构下.
一个操作系统有 20 个进程, 竞争使用 30 个同类资源. 资源申请方式是每次申请一个, 一旦某个进程获得了它需要的全部该类资源, 就可以马上运行完并归还所有申请的资源 . 假设每个进程最多需要该类资源 30 个,最少需要 1 个, 并且 20 个进程需要的资源总数小于 50. 如果仅考虑这类资源, 系统不会产生死锁.

正确, 不可能会产生死锁. 最极端的例子中: 19 个进程需要 2 个资源, 1 个进程需要 11 个资源. 那么当 19 个进程都占有 1 个资源, 最后一个资源占有 10 个资源的时候, 有 29 个资源已经被分配, 还有 1 个资源可以被分配, 而任一一个进程分配到资源都会马上运行完并归还所有申请的资源. 因此不会发生死锁.
在 I/O 设备管理中, 假脱机(Spooling)和缓冲技术均以内存为基础来设置缓冲空问.

错误, Spooling 技术还可以使用磁盘来设置缓冲空间.
在一个请求式分页系统中, 采用最近使用先淘次页面置换算法(和 LRU 相反, 先淘汰最近使用的页面)时, 假如一个进程的页面走向为 4、3、2、1、4、3、5、4、3、2、1、5, 当分配给该作业的物理块数为 3 时, 访问过程中发生的缺页次数为 13.

缺页次数为 7, 不为 13. 因此错误. 访问过程如下图:

1	2	3	change
4			√
4	3		√
4	3	2	√
4	3	1	√
4	3	1
4	3	1
4	5	1	√
4	5	1
3	5	1	√
2	5	1	√
2	5	1
2	5	1

内存访问

由于缺页率为 0, 因此都是访问内存需要先访问页表再访问内存地址, 因此有效访问时间为 200ns.
磁盘访问时间 = 寻道时间+旋转延迟时间+传输时间. 寻道时间 = 5ms. 旋转访问延迟时间 = (1/r)/2 =(60/7200)/2 s = 4.133ms. 传输时间 = 4KB/(1024*1024 KB/s) = 4000/(1024*1024) = 0.004ms. 因此平均磁盘访问时间为 9.137ms
(1-0.01)*200 + 0.01*(100+((1-0.2)*0.1*1000+0.29.1371000)+100) = 408.74ns.

文件检索

提高效率方案:

文件的目录结构方面: 采用树型目录结构, 树型目录结构具有能有效提高对目录的检索速度;
文件的逻辑结构方面:由于对此文件的操作主要是根据姓名和身份证号进行检索, 因此可以根据姓名的长度(字数相同的)对文件进行分目录存储或者根据姓名的姓的拼音首字母分目录存储, 身份证号(同一个省份的每个身份的前几位都相同)按前几位分目录存储. 文件中的个人身份信息属性一致, 所以可以认为每个人的身份信息大小相同, 因此可以将这个文件的逻辑文件信息连续存放, 即采用顺序文件的方式.
文件的物理结构方面: 可以采用连续分配的方式, 把逻辑文件中的个人身份信息顺序地存锗到相邻的物理盘块中; 这样查找速度快, 且基本没有空间浪费.

PV 操作

任务图大致为:

Semaphore s2=2, s1=0, r1=0, r2=0; // 初始化各个进程的信号量. 从s2开始运行.
Semaphore mutex = 1; // 代表缓冲区读写权限的信号量.


Procedure S1(){
    while(1){
        P(s1);
        P(mutex);
        // 将s1的消息发送到缓冲区
        V(mutex);
        V(r1);
        V(r2);
    }
}

Procedure S2(){
    while(1){
        P(s2);
        P(s2);
        P(mutex);
        // 将s2的消息发送到缓冲区
        V(mutex);
        V(s1);
    }
}

Procedure R1(){
    while(1){
        P(r1);
        P(mutex);
        // 读取s1的消息.
        V(mutex);
        V(s2);
    }
}

Procedure R2(){
    while(1){
        P(r2);
        P(mutex);
        // 读取s1和s2的消息.
        V(mutex);
        V(s2);
    }
}