数据结构

判断题

  1. 若有一个栈的输入序列是 1,2,3,…,100, 输出序列的第一个元素是 100, 则第 50 个输出元素是 50.

    错误, 第一个输出的是 100, 那么第 50 个输出的是 51.

  2. 在一个有向图中, 所有顶点的入度之和等于所有顶点的出度之和.

    正确, 对于每一条边, 都会增加一个出度和一个入度, 因此所有顶点的入度之和等于所有顶点的出度之和.

  3. 在拓扑排序序列中, 任意两个结点 i 和 j, 都存在从 i 到 j 的路径.

    错误, 如果在拓扑排序序列中, i 在 j 之前, 那么都存在从 i 到 j 的路径. 如果 i 在 j 之后, 那么不存在
    从 i 到 j 的路径.

  4. 在哈希表中, 装填因子的值越小, 存取元素时发生冲突的可能性就越小.

    正确, 装填因子 = 关键字个数 / 表长. 因此装填因子越小, 代表空间浪费越多, 冲突可能性越小.

  5. 任何一个无向连通图的最小生成树只有一棵.

    错误, 可能存在不同的最小生成树.

简答题

简述堆排序算法的基本思想. 对于快速排序而言, 堆排序有哪些优势? 对于归并排序而言堆排序有哪些优势? 假定
有 8000 个整数, 需要找出最大的 10 个数, 在堆排序、快速排序、基数排序方法中, 采用哪种方法最好? 请说明
理由.

堆排序是通过将关键字调整为堆, 然后依次将堆顶的元素和放入到有序区, 每次放入后都需要整理堆的结构. 直到
全部的元素都放入到有序区中.

对于快速排序, 堆排序在最坏的情况下时间复杂度也为 O(n*log(n)), 而快速排序在最坏情况下时间复杂度为
O(n^2), 并且堆排序的空间复杂度为 O(1), 而快速排序的空间复杂度为 O(log(n)).

对于归并排序, 堆排序的空间复杂度为 O(1), 而归并排序的空间复杂度为 O(n).

采用堆排序最好, 因为如果使用大顶堆, 只需要进行 1 次建堆, 10 次推出并调整堆就可以选出 10 个最大的数了
. 而不必等到全部数排序好后选出, 因此堆排序最快.

递归创建二叉树

def init_tree_by_list(
    chs: Optional[List[str]], idx: int = 0
) -> Optional[TreeNode]:
    """
    递归创建二叉树.

    Args:
        chs (Optional[List[str]]): 二叉树堆值的列表.
        idx (int, optional): 当前节点所在列表的下标. Defaults to 0.

    Returns:
        Optional[TreeNode]: 生成的二叉树.
    """
    if chs and idx < len(chs):
        return TreeNode(
            val=chs[idx],
            left=init_tree_by_list(chs, idx * 2 + 1),
            right=init_tree_by_list(chs, idx * 2 + 2),
        )

两数之和-链表版

def two_sum2(node: DulLinkedList, target: int) -> str:
    """
    两数之和, 双链表版.

    由于采用双链表, 并且有序, 因此可以使用双指针法.

    Args:
        node (DulLinkedList): 双链表.
        target (int): 目标数.

    Returns:
        str: 返回信息.
    """
    cur = node
    while cur.next:
        cur = cur.next
    tail, head = cur, node
    while tail and head and tail != head:
        if tail.val + head.val == target:
            return f"{target} = {head.val} + {tail.val}"
        elif tail.val + head.val < target:
            head = head.next
        else:
            tail = tail.pre
    return "not exist two numbers sum equals target."

两个有序顺序表的中间值

def two_order_list_median(lst1: list[int], lst2: list[int]) -> float:
    """
    二分法求解.

    对于两个有序数组, 可以划分为两部分, 一部分小于等于中位数, 一部分大于中位数. 而中位数
    就可以在这条边界旁取得. 因此我们可以通过二分的方法分别在两个数组中找到这条边界.

    Args:
        lst1 (list[int]): 顺序表1
        lst2 (list[int]): 顺序表2

    Returns:
        float: 中位数.
    """
    m, n = len(lst1), len(lst2)

    def get_Kth_element(k):
        idx1, idx2 = 0, 0
        while True:
            if idx1 == m:
                return lst2[idx1 + k - 1]
            if idx2 == n:
                return lst1[idx1 + k - 1]
            if k == 1:
                return min(lst1[idx1], lst2[idx2])

            new_idx1 = min(idx1 + k // 2 - 1, m - 1)
            new_idx2 = min(idx2 + k // 2 - 1, n - 1)
            pivot1, pivot2 = lst1[new_idx1], lst2[new_idx2]
            if pivot1 <= pivot2:
                k -= new_idx1 - idx1 + 1
                idx1 = new_idx1 - 1
            else:
                k -= new_idx2 - idx2 + 1
                idx2 = new_idx2 + 1

    total_length = m + n
    if total_length % 2 == 1:
        return get_Kth_element((total_length + 1) // 2)
    return (
        get_Kth_element(total_length // 2)
        + get_Kth_element(total_length // 2 + 1)
    ) / 2

操作系统

判断题

  1. 所有用户进程都必须常驻内存.

    错误, 并非所有进程都常驻于内存中的, 一般只有正在执行的进程在内存中.

  2. 有 m 个进程的操作系统出现死锁时, 死锁进程个数的范围为 1<k<=m.

    正确, 死锁是由两个或两个以上进程对于互斥资源的抢夺造成的. 因此死锁进程个数的范围为 1<k<=m.

  3. 除了 FCFS, 其它的磁盘调度算法都会出现饥饿现象.

    错误, SCAN 算法也不会出现饥饿现象.

  4. 増加内存中的进程数量, 可以提高 CPU 的利用率.

    错误, 增加内存中的进程数量, 可能会导致分配给现有正在运行的进程的内存减少, 从而使得需要花费更多的
    时间用于内存调度, 从而减少了 CPU 的利用率.

  5. 在分页式存储管理中, 引入 TLB 可减少每一次的内存访问时间.

    错误, 如果需要访问的内存地址不存在于 TLB 中(未命中), 会增加访问其的时间.

解答题

gtJD2U1NVKxPhrY

t\p P1 P2 P3 P4 P5
0s 8
1s 10 4
2s 9 6 6
3s 8 # 5 2
4s 7 4 # 10
5s 6 6 9
6s 5 8 8
7s 7 7 7
8s # 6 6
9s # 5
10s 7
11s #

因此 5 个进程执行的顺序图为: P1->P2->P2->P4->P3->P3->P1->P1->P3->P5->P5->P5

因为 周转时间 = 完成时间 - 到达时间, 并且 响应时间 = 第一次处理时间 - 到达时间.

因此每个进程的周转时间和响应时间为:

进程编号 P1 P2 P3 P4 P5
周转时间 8 2 7 1 7
响应时间 0 0 2 0 5

PV 操作

Semaphore msg = 1 // 用于实现对缓冲区的互斥操作, 初始值为1
Semaphore reader[n]=0 // 控制n个读者是否已经读取完消息, 全部初始为1

Procedure B(){  // 发送者进程/
    while(1){
        P(msg);
        // 清空缓冲区
        // 将消息发送至缓冲区
        int i;
        for(i=0;i<n;i++){
            V(reader[i]);
        }
        V(msg);
    }
}

Procedure A(int i){ // 接收者进程, i标记了为哪一个接收者.
    while(1){
         P(reader[i])
        P(msg);
        // 从缓冲区取出消息
        // 读取消息
        // 将消息放回缓冲区
        V(msg);
    }
}

分析题

对于每条记录, 需要大小为 4*2 + 2 + 128*2 + 18 + 2 + 4 = 290 Byte

文件的总大小为 290000000 Byte = 290000 KB = 290 MB

逻辑文件结构: 由于主要操作为根据姓名进行记录查询. 因此可以根据姓名对文件进行分目录存放. 相同长度姓名
的记录在同一个目录中, 这样可以方便根据姓名查找. 因此可以将这个文件的逻辑文件信息连续存放, 即采用顺序
文件的方式.

物理文件结构: 由于每条记录的大小相差不大. 因此可以采用连续分配的方式, 把逻辑文件中的记录顺序地存储在
相邻的物理盘块中; 这样查找速度快, 且没有太大的空间浪费.

(1) 因为每个磁盘块为 1KB, 因此文件需要 290000 个磁盘块.

(2) 平均需要 290000/2 = 145000 个磁盘块.


你在你的玫瑰花身上耗费的时间使得你的玫瑰花变得如此重要.