苏州大学2012年872试题

数据结构

简述题

1. 连通分量

   无向图中的极大连通子图称为连通分量. 连通分量主要用于确定从图中的一个顶点能否到达图中的另一个顶点.

2. 最小生成树

   对于一个带权连通图 G=(V,E) 从中得到一个 G1=(V1,E1) 的子图. 并且这个子图为一棵树, 则称子图为生成树. 最小生成树则表示在 G 的所有生成树中, 权值最小的那一类生成树.

3. 堆排序

   将 arr[1…n] 看成一颗完全二叉树的顺序存储结构, 利用完全二叉树中双亲结点和子结点的关系, 每次在当前无序区中选择关键词最大的元素.

4. 双端队列

   双端队列是指两端都可以进行入队和出队操作的队列.

5. 稀疏矩阵的压缩存储方法

   为多个值相同的元素只分配一个存储空间, 对零元素不分配存储空间.

散列表

假定一个待散列存储的线性表为(37,65,25,73,42,91,45,361875), 散列地址空间为 HT[12] 若采用除留余数法构造散列函数和链接法处理冲突, 试求出每一元素的散列地址, 画出最后得到的散列表, 求出平均查找长度.

由于采用除留余数法, 可得散列函数为: H(n) = n % 11. 散列地址和元素的关系如下:

因此散列表为:

因此平均查找长度为: ASL = (1*6+2*3+3*1)/10 =1.5

单链表结点与前驱结点交换位置

def change(node: Optional[ListNode], i: int) -> Optional[ListNode]:
    """
    将单链表中编号为 i (从 0 开始)的节点和它的前驱节点交换位置.

    因为为单链表, 所以需要在cur.next.next为目标节点时, 才能操作如何指向前驱节点.

    Args:
        node (Optional[ListNode]): 单链表.
        i (int): 目标节点编号.

    Returns:
        Optional[ListNode]: 交换后的链表.
    """
    idx = 1
    head = ListNode(val=0, next=node)
    cur = head
    while cur.next:
        if idx == i:
            target = cur.next.next
            cur.next.next, cur.next, target.next = target.next, target, cur.next
            break
        idx += 1
        cur = cur.next
    return head.next

构造平衡二叉查找树

def init_balance_search_tree(n: int) -> TreeNode:
    """
    将自然数range(1,n+1)作为树的节点的值, 构造一棵平衡二叉查找树.

    采用递归的方法, 由于自然数是递增有序的, 因此可以选择中间节点作为子树的父节点, 左边的
    元素作为左子树, 右边的节点作为右子树. 递归下去就可以构建成一颗平衡的二叉查找树.

    Args:
        n (int): 自然数.

    Returns:
        TreeNode: 平衡的二叉查找树.
    """

    def dfs(le: int, ri: int) -> TreeNode:
        mid = (le + ri) // 2
        return TreeNode(
            val=mid,
            left=dfs(le, mid - 1) if le != mid else None,
            right=dfs(mid + 1, ri) if ri != mid else None,
        )

    return dfs(1, n)

操作系统

名词解释

1. 内碎片

   内碎片是指已经分配给某进程, 但是无法被利用的内存空间.

2. 微内核

   将内核中最基本的功能保留在内核, 将那些不需要在核心态下执行的功能移到用户态下执行.

3. 中级调度

   即内存调度, 为了提高内存利用率和系统吞吐量, 将那些不能运行的进程调至外存上等待.

4. 用户级线程

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

5. 死锁

   多个进程因竞争资源而造成的一种僵局, 若无外力作用, 这些进程都将无法向前推进.

分析请求式分页系统需要解决的核心问题, 并谈谈如何提高请求式分页系统的效率.

1. 地址转换

   由于分页系统需要频繁地访问内存, 因此地址转行速度越快, 访问内存的速度也就越快, 分页系统的效率也就越高.

2. 缺页率

   缺页率越高, 就会增大分页系统在访问内存的时间. 进而降低分页系统的效率.

3. 内存分配

   选择合理的内存分配方式, 可以为特定的进程分配适度的主存空间. 减少内存的访问次数, 因此提升分页系统的效率.

4. 为提高请求式分页系统的效率, 可以为地址转换增设一个具有并行查找能力的高速缓冲的快表, 用来存放当前访问的若干页表项, 以加速地址转换的过程. 选择合适的页面置换算法, 降低缺页率. 根据每个进程在运行时的缺页情况, 为每个进程分配适当的物理块, 使进程所谓缺页率趋于适当程度.

PV 操作

规则如下:

1. S1 发送消息, R1, R2, R3 接收消息.
2. 消息的缓冲区大小为 1
3. 每个消息需要被 R1, R2, R3 各接收一次.
4. 只有在消息被 R1, R2, R3 都接收后, S1 才能发送下一个消息.

Semaphore SR1=SR2=SR3=1;
Semaphore R1=R2=R3=0;

Procedure S1(){
    while(1){
        // Generate message

        P(SR1);
        P(SR2);
        P(SR3);

        // Send messages to buffer

        V(R1);
        V(R2);
        V(R3);
    }
}

Procedure R1(){
    while(1){
         P(R1);

        // Receive messages from buffer

        V(SR1);
    }
}

Procedure R2(){
    while(1){
        P(R2);
        // Receive messages from buffer

        V(SR2);
    }
}

Procedure R3(){
    while(1){
        P(R3);

        // Receive messages from buffer

        V(SR3);
    }
}

磁盘 IO 操作

一个文件有 10 个磁盘块, 假设文件控制块在内存 (如果文件采用索引分配, 索引表也在内存 ). 在下列情況下,请计算在连续分配, 链接分配, 单级索引分配三种分配方式下分别需要多少次磁盘 I/O 操作?(每读入或写出一个磁盘块需要一次磁盘 I/O 操作,另外,假设在连续分配方式下, 文件头部无空闲的磁盘块, 但文件尾部有空闲的磁盘块.)

在文件开始处删除一个磁盘块

• 连续分配

  连续分配可以直接通过指针加法获得下一个磁盘块的地址, 因此可以不需进行 IO 操作. 因此 IO 操作次数为 0.

• 链接分配

  需要分为两种情况: 隐式链接和显式链接

  隐式链接: 由于下一块磁盘块的地址存储在第一块磁盘块的物理块中, 需要访问 1 次磁盘快来获得第二块磁盘块的地址. 因此 IO 操作次数为 1.

  显式链接: 因为链接表存储已经在文件系统装载时装入内存. 则仅需要修改链接表即可. 因此 IO 操作次数为 0.

• 单级索引分配

  由于索引表已经在内存中, 只需删除其第一个物理块的地址 . 因此 IO 操作次数为 0.

在文件结尾处添加一个磁盘块

• 连续分配

  由于知道文件的第一个磁盘的地址, 并知道文件的物理块的个数, 只需要在末尾添加一个磁盘块. 因此 IO 操作的次数为 1.

• 链接分配

  需要分为两种情况: 隐式链接和显式链接

  隐式链接: 根据文件结束块读取最后一块物理块的内容, 获得新的物理块, 最后将读取的最后一个物理块的指针指向新的物理块. 因此 IO 操作的次数为 3.

  显式链接: 由于链接表已经放入内存, 只需要获得新的物理块, 并将其地址加入链接表. 因此 IO 操作的次数为 1.

• 单级索引分配

  由于索引表已经存在于内存, 只需在获得新的物理块, 并将其地址加入索引表. 因此 IO 操作的次数为 1.

在文件结尾处删除一个磁盘块

• 连续分配

  直接修改文件长度即可, 不需要进行 IO 操作. 因此 IO 操作次数为 0.

• 链接分配

  需要分为两种情况: 隐式链接和显式链接

  隐式链接: 需要从第一个物理块一直读取到倒数第二个物理块, 然后将倒数第二个物理块的指针内容修改为-1,需要读取 9 个指针, 并修改倒数第二个物理块的指针. 因此 IO 操作的次数为 10.

  显式链接: 由于链接表已经存在于内存, 只需要删除最后一个地址块的地址. 不需要进行 IO 操作. 因此 IO 操作的次数为 0.

• 单级索引分配

  由于索引表已经存在于内存中. 只需要读取索引快, 并删除最后一个条目. 因此 IO 操作的次数为 0.

开放题

随着多核时代的米临,操作系统也需要适应 CPU 的这个变化。请从目前的操作系统的功能入手, 谈谈如何使得现代操作系统适合多核计算环境。