数据结构

简答题

  1. 什么是队列, 什么是循环队列?

    只允许在线性表点一端进行插入, 另一端进行删除操作的线性表, 被称为队列.

    循环队列是指将顺序队列假想为一个环状的空间, 即把存储队列元素的表从逻辑上看成一个环.

  2. 什么是最小生成树, 如何构造最小生成树?

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

    最小生成树有两种构造方法, 分别是 Prim 算法和 Kruskal 算法.

    Prim 算法是从某一点开始, 不断找到与当前子图相连且不构成环的权值最小的边, 并将其加入到子图中, 直到所有点均加入到子图中, 即可构成最小生成树.

    Kruskal 算法则是不断寻找 G 中权值最小且不构成环的边, 直到所有点均在子图中, 即可构成最小生成树.

选择排序算法

  1. 以随机顺序排列的 n 个记录的链表, 其中 n>1000.

    应该采用归并排序.

    因为要达到最好的时间复杂度 O(n*log(n))的排序算法, 比较方便且适用于链表的为归并排序算法, 并且归并排序说是非递归实现, 也能使空间复杂度为 O(1).

  2. 以随机顺序排列的 n 个记录的数组, 其中 n>1000.

    应该采用归并排序.

    采用快速排序, 因为当排序元素较多, 且随机排列时, 快速排序的时间复杂度较低. 为 O(n*log(n)).

  3. n 个记录的数组, 其中所有记录都距离正确位置至多两个位置.

    应该采用冒泡排序, 因为距离至多为 2, 冒泡排序的时间复杂度为 O(2*n)

二叉树的层次遍历

def level_order(node: Optional[TreeNode]) -> Generator:
    """
    二叉树的层序遍历.

    Args:
        node (Optional[TreeNode]): 二叉树.

    Yields:
        Generator: 返回一个层序遍历二叉树的生成器.
    """
    if node is None:
        return None
    level = [node]
    while level:
        new_level = []
        for item in level:
            yield item
            if item.left:
                new_level.append(item.left)
            if item.right:
                new_level.append(item.right)
        level = new_level

按照奇偶拆分单链表

def split_linked_list(node: Optional[ListNode]) -> tuple[ListNode, ListNode]:
    """
    将单链表拆分为全为奇数和全为偶数的两个单链表.

    Args:
        node (Optional[ListNode]): 单链表.

    Returns:
        tuple[ListNode, ListNode]: 全为奇数的单链表和全为偶数的单链表
    """
    even_list, head = ListNode(), ListNode(val=0, next=node)
    cur = head
    while cur and cur.next:
        if cur.next.val % 2 == 0:
            tmp, cur.next = cur.next, cur.next.next
            even_list.next, tmp.next = tmp, even_list.next
        cur = cur.next
    return head.next, even_list.next

有序矩阵搜索

def matrix_search(arr: List[List[int]], target: int) -> bool:
    """
    有序二维数组中查找目标值.

    由于是在行递增, 列递减的二维数组中, 因此我们可以将初始点位于第一行的最后一列中,
    然后判断其是否与目标值相等:

    - 如果相等则退出
    - 如果大于, 则减少列数
    - 如果小于, 则增加行数

    因此可以遍历到二维数组中所有的数.

    Args:
        arr (List[List[int]]): 有序二维数组.
        target (int): 目标值.

    Returns:
        bool: 是否存在.
    """
    row, col = len(arr), len(arr[0])
    i, j = 0, col - 1
    while i < row and col >= 0:
        idx = arr[i][j]
        if idx == target:
            return True
        elif idx > target:
            j -= 1
        else:
            i += 1
    return False

操作系统

判断题

  1. 一个运行时需要 300MB 存储空间的程序, 是不可能在一台只有 256MB 的内存的计算机上运行起来的.

    错误, 因为可以使用虚拟存储技术, 使得该进程不会在运行时一次性地将全部数据读取进内存, 而是将部分未使用的内存存放在外存中, 待使用到时再读取进内存.

  2. 死锁将导致计算资源的使用效率不高, 所以在设计操作系统时, 不应该让死锁发生.

    正确, 死锁是指两个或两个以上的进程在执行过程中, 因争夺资源而造成的一种互相等待的现象, 若无外力作用, 它们都将无法推进下去. 在计算机系统中资源是有限的, 而处于死锁的进程往往占有大量的资源且不能被剥夺, 造成系统资源利用率降低. 甚至有些死锁的出现会使系统无法正常运行, 给系统造成极大危害 因此在设计操作系统时, 不应该让死锁发生.

简答题

  1. 举例说明进程和线程的联系与区别.

    调度: 进程是操作系统分配资源的基本单位, 而线程是独立调度的基本单位. 在同一进程中, 线程的切换不会导致进程的切换, 而在不同进程中, 线程的切换会引起进程的切换.

    资源: 由于进程时分配资源的基本单位. 进程拥有资源, 而线程基本不拥有资源. 但是线程可以访问其隶属进程的系统资源.

    并发: 进程之间可以并发执行, 同一进程中的线程也可以并发执行.

    系统开销: 由于进程相较于线程更加庞大. 因此创建一个进程消耗的系统资源远大于创建一个线程消耗的资源,特别地, 当在一个进程中创建多个线程时, 由于线程可以共同拥有其隶属进程的资源, 因此消耗的资源不大.在切换方面, 切换同一进程中线程所消耗的时间远比切换进程消耗的时间短, 但若是切换到不同进程的线程,由于也会引发进程的切换, 因此也会消耗一定到时间.

    通信: 进程之间通信需要进行同步和互斥手段进行辅助, 以保障数据的一致性. 而线程间可以直接读写进程数据段来进行通信.

  2. 说明操作系统对于应用程序开发来说的必要性和重要性.

    必要性: 从系统的观点来看, 操作系统时计算机系统中的一个系统软件, 它管理和控制计算机系统的四大类资源: 处理器, 存储器, 外设和信息, 任何的应用软件和开发都需要借助于操作系统来对计算机的资源进行调用.

    重要性: 操作系统的主要功能为处理器管理, 存储器管理, 设备管理, 文件管理, 用户接口. 从层次的角度来说, 操作系统是与计算机硬件之间联系的一层, 本身已经实现了复杂的对硬件资源进行操作的功能, 而且还提供了方便的接口, 可以让应用软件的开发更加注重于软件本身的功能, 使软件的开发更加便捷. 另外操作系统具有四大特性: 并发行, 共享性, 虚拟性和异步性. 这些特性可以让开发的软件具有更加强大的功能, 软件质量更高.

设计一个进程同步解决的问题, 并采用同步源语 wait/signal 来解决问题.

读者写者问题: 一个数据库可以为多个并发进程所共享. 可以供多位读者同时读取. 但若是被一个写者读取时, 其他人不能读/写该文件.

semaphore r, w;  // r为读者信号量, w为写者信号量. 初始值均为1.
int read_count;  // 记录有多少个读者正在读

Procedure reader() {
  while (1) {
    wait(r);
    if (read_count == 0) {
      wait(w);
    }
    read_count++;
    signal(r);

    // read something

    wait(r);
    read_count--;
    if (read_count == 0) {
      signal(w);
    }
    signal(r);
  }
  return;
}

Procedure writer() {
  while (1) {
    wait(w);

    // update/read something...

    signal(w);
  }
  return;
}

简述处理死锁一般有哪些策略

  1. 预防死锁

    设置某些限制条件, 破坏产生死锁的四个必要条件中的一个或几个, 以防止发生死锁.

    • 优点:适用于做突发式处理的进程, 不必进行剥夺.
    • 缺点: 效率低,进程初始化时间延长。

  2. 避免死锁

    在资源的动态分配过程中, 用某种方法防止系统进入不安全状态从而避免死锁.

    • 优点:不必进行剥夺/
    • 缺点:必须知道将来的资源需求,进程不能被长时间阻塞.

  3. 死锁的检测和解除

    无需采取任何限制性措施, 允许进程在执行过程中发生死锁. 通过系统的检测机构及时检测出死锁的发生, 然后采取某种措施解除死锁.

    • 优点:不延长进程初始化时间, 允许对死锁进行现场处理.
    • 缺点:通过剥夺解除死锁造成损失.
赏

正是你花费在玫瑰上的时间才使得你的玫瑰花珍贵无比