苏州大学2006年872试题

数据结构

名词解释

堆栈:

只允许在一端进行插入和删除操作的线性表
最小生成树:

对一个带权连通无向图 G=(V, E), 生成树不同, 每棵树的权也可能不同. 设 R 为 G 的所有生成树的集合, 若
T 为 R 中边的权值之和最小的那棵生成树, 则 T 称为 G 的最小生成树.
折半查找:

用于有序的顺序表, 首先将给定的 key 与表中中间位置的元素的关键字比较, 若相等, 则查找成功, 返回该元
素的存储位置, 若不等, 则所需查找的元素只能在中间元素以外的前半部分或后半部分中, 缩小范围, 继续查
找.
堆排序:

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

无向图的极大连通子图

依次像队列和双端队列输入[1, 2 , 3, 4, 5, 6], 是否可以得到一下输出.

略.

二叉树叶结点放入动态分配顺序存储结构的顺序表

def leaves_list(tree: TreeNode) -> list:
    """
    二叉树叶结点放入动态分配顺序存储结构的顺序表.
    采用dfs算法搜索从左到右搜索叶结点.
    由于python的list本身就为动态分配的顺序存储结构, 其他语言需要在加入新元素后扩大容量
    每次扩大为当前容量大两倍.

    Args:
        tree (TreeNode): 树根节点.

    Returns:
        list: 动态分配的保存叶结点顺序存储结构.
    """
    head = []

    def dfs(root: TreeNode):
        if not root.left and not root.right and root.val != -1:
            head.append(root.val)
        else:
            if root.left:
                dfs(root.left)
            if root.right:
                dfs(root.right)

    dfs(tree)
    return head

字符串匹配（以后的考试不做要求）

def index(source: str, target: str) -> int:
    """
    字符串定位操作.
    在字符串中找到目标字符串的起始下标.
    在定位操作过程中, 首先定位目标字符串的首尾, 如果首位字符符合, 再匹配中间字符.

    Args:
        source (str): 源字符串.
        target (str): 目标字符串.

    Returns:
        int: 目标字符串在源字符串的起始下标.
    """
    len_s = len(source)
    len_t = len(target)
    if len_t == 0 or len_s == 0:
        return -1
    for i in range(0, len_s - len_t - 1):
        if source[i] == target[0] and source[i + len_t - 1] == target[-1]:
            if source[i:i + len_t] == target:
                return i
    return -1

归并排序链表

def merge_sort_ln(head: ListNode) -> Optional[ListNode]:
    """
    归并排序算法排序单链表.

    Args:
        head (ListNode): 单链表的头结点.

    Returns:
        Optional[ListNode]: 排序后的单链表头结点.
    """

    def merge_ln(h1: Optional[ListNode],
                 h2: Optional[ListNode]) -> Optional[ListNode]:
        """
        合并函数. 将两个排序好的单链表合并为一个排序好的单链表.

        Args:
            h1 (Optional[ListNode]): 第一个排序好的单链表.
            h2 (Optional[ListNode]): 第二个排序好的单链表.

        Returns:
            Optional[ListNode]: 合并完成的单链表.
        """
        d_h = ListNode()
        t, t1, t2 = d_h, h1, h2
        while t1 and t2:
            if t1.val <= t2.val:
                t.next, t1 = t1, t1.next
            else:
                t.next, t2 = t2, t2.next
            t = t.next
        if t1:
            t.next = t1
        else:
            t.next = t2
        if not d_h.next:
            return None
        return d_h.next

    def sort_func(h: Optional[ListNode],
                  tail: Optional[ListNode] = None) -> Optional[ListNode]:
        """
        递归拆分函数. 拆分直到头结点和尾结点中间仅剩一个结点, 或者没有结点.
        采用快慢指针的方式找到头尾结点的中间结点, 然后拆分为两部分.

        Args:
            h (Optional[ListNode]): 拆分的头结点
            tail (Optional[ListNode], optional): 拆分的尾结点. Defaults to None.

        Returns:
            Optional[ListNode]: 返回合并好的单链表.
        """
        if not h:
            return h
        if h.next == tail:
            h.next = None
            return h
        slow = fast = h
        while slow and fast and fast != tail:
            slow, fast = slow.next, fast.next
            if fast != tail and fast:
                fast = fast.next
        mid = slow
        return merge_ln(sort_func(h, mid), sort_func(mid, tail))

    return sort_func(head)

操作系统

判断下列说法是否正确, 并说明理由

在单 CPU 的计算机系统中, 进程是不能并行操作的.

正确, 单 CPU 只能并发操作, 无法做到真正的并行操作.

在死锁发生后, 参与死锁的所有进程都占有资源.

错误, 参与死锁的所有进程均等待资源, 参与死锁的进程至少有两个已经占有资源.

存储管理中的请求分页系统必定需要重新定位机制的支持.

错误, 重定位机制用于连续分配方式中.

解释以下概念

中断:

也称为外中断, 来自 CPU 执行指令以外的时间的发生, 如设备发出的 I/O 结束中断, 表示设备输入/输出处理
已经完成, 希望处理机能够向设备发出下一个输入/输出的请求, 同时让完成输入/输出后的程序继续运行. 这
一类中断通常是与当前程序运行无关的事件 , 即它们与当前处理机运行的程序无关.
虚拟设备:

通过某种虚拟技术, 将一台无力设备变成若干台逻辑设备, 从而实现对多个用户对该物理设备的同时分享.
中级调度:

内存调度. 为了提高内存利用率和系统吞吐率. 中级调度用于把进程从内存移到外存, 当内存有足够空间时,
再将合适的进程换入内存.
Cache:

访问速度比一般随机存储器快的一种存储器, 用于让数据访问速度适应 CPU 处理速度.
LRU 算法:

选择最近最长未访问过的页面予以淘汰的算法.

在虚拟存储技术中, 系统将进行进程运行时所缺的页面调入内存的时机有预调页策略和请求式调页策略两种. 请说明这两种策略的原理, 并结合具体的实例比较这两种策略的优劣.

预调页技术
- 以预测为基准, 将预计在不久后便会访问的程序或数据所在的页, 预先调入内存.
- 优点: 一次调入若干页, 效率较好.
- 缺点: 预测不一定准确, 预调入的页面可能根本不被执行到. 主要用于进程的首次调入 , 由程序员指出应该
  先调入哪些页.
请求调页策略:
- 进程在运行中提出调页请求后, 系统将其所需的页面调入内存.
- 优点: 由该请求调页策略所确定调入的页, 一定会被访问; 比较容易实现.
- 缺点: 每次仅调入一页, 需要花费较大的系统开销, 增加了磁盘 I/O 的频率.

PV 操作

Semaphore s = 1 // 表示缓冲区是否为空, 初始为1
Semaphore d1 = 0;  // 表示是否有D1在缓冲区
Semaphore d2 = 0;  // 表示第二个进入缓冲区的数据是否是D2
Semaphore d3 = 0;  // 表示第二个进入缓冲区的数据是否是D3

// D1
Procedure D1(){
    while(1){
        P(s);
        将d1数据写入缓冲区;
        V(d1);
    }
}

// D2
Procedure D2(){
    while(1){
        P(d1);
        将d2数据写入缓冲区;
        V(d2);
    }
}

// D3
Procedure D3(){
    while(1){
        P(d1);
        将d3数据写入缓冲区;
        V(d3);
    }
}

// H1
Procedure H1(){
    while(1){
        P(d2);
        把d1, d2数据从缓冲区拿出, 并处理.
        V(s);
    }
}

// H2
Procedure H2(){
    while(1){
        P(d3);
        把d1, d3数据从缓冲区拿出, 并处理.
        V(s);
    }
}

文件管理

根据题意, 可知每条记录所需的长度. 姓名(8 byte) + 地址(100 byte) + 年龄(1 byte) + 专业(20 byte) = 129
byte 一共有 32000 条记录, 故总共需要 4128000 byte = 4128 KB = 1032 * 4KB = 1032 个物理块.

设计的方案:

文件的逻辑结构: 由于对此文件的操作主要是根据姓名进行记录的查询, 因此可以根据姓名的首字母对文件进
行分目录存储, 即姓名首字母相同的分在同一个目录, 最多有 26 个目录. 每个目录中的文件长度差不多, 因
此可以将这个文件的逻辑文件信息连续存放, 即采用顺序文件的方式.
文件的物理结构: 由于该文件的大小已知, 故可以采用连续分配的方式, 把逻辑文件中的记录顺序地存储到相
邻的物理盘块中; 这样查找速度快, 且没有增加其他额外空间.

在该结构下, 每次检索平均需要访问 1032 / 2 = 516 个物理块