苏州大学2010年872试题

数据结构

简答题

1. 栈和队列有什么共同点和不同点?

   共同点: 都是一种特殊的线性表, 都仅允许顺序表的头/尾进行加入元素/删除元素的操作.

   不同点: 栈是一种 FILO 的数据结构, 只允许在栈顶进行加入或者删除操作, 因此最先加入的元素, 最后才会被推出. 队列是一种 FIFO 的数据结构, 只允许在队尾/队头加入元素, 队头/队尾删除元素, 因此最先加入的元素, 最先被推出.

2. 什么是矩阵的压缩存储, 试举例说明.

   矩阵的压缩存储指为多个值相同的元素只分配一个存储空间, 队零元素不分配存储空间. 目的是节省存储空间.

   例子: 对于一个 1000*1000 稀疏矩阵, 仅有 10 个非零数据. 若是用二维数组存储, 则会浪费大量的空间.但如果采用三元组顺序表方式存储, 则仅仅需要 10 组三元组就能存储存储数据.

判断, 并说明理由.

题目: 对任意一个图, 从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点.

错. 如果是无向图的连通图或者有向队强连通图, 则能够访问到该图队每个顶点. 对于非连通的无向图, 不可能一次遍历访问到所有顶点. 对于有向非强连通图则有可能一次遍历到所有顶点.

单链表剔除值为 x 的结点

def remove_x(node: Optional[ListNode], target: int):
    """
    删除所有节点值为target的节点, 需要注意应该判断cur.next的值.

    Args:
        node (Optional[ListNode]): 单链表
        target (int): 目标值

    Returns:
        [type]: 删除后的单链表
    """
    head = ListNode(val=-1, _next=node)
    cur = head
    while cur.next:
        if cur.next.val == target:
            cur.next = cur.next.next
        else:
            cur = cur.next
    return head.next

表达式树求值

def calculate(t: Optional[TreeNode]) -> int:
    """
    求解计算树的值.

    Args:
        t (Optional[TreeNode]): 计算树, 叶子节点为数值, 节点为运算符.

    Returns:
        int: 求解的值.
    """
    if not t:
        return -1

    if not t.left and not t.right:
        return t.val
    return eval(f"{calculate(t.left)}{t.val}{calculate(t.right)}")

按照奇偶重新组合

def com_even_odd(arr: List[int]) -> List[int]:
    """
    让所有的偶数位于数组的偶数下标上, 或者所有奇数位于数组的奇数下标上.

    由于一个整数必定是偶数或是奇数, 因此只需要让偶数/奇数其中一个排列正确, 则能保证满足题意.
    因此我选择修改偶数下标, 用两个指针分别指向了偶数下标和奇数下标, 并不断找到不符合题意的元
    素, 然后交换. 直到两个指针的其中一者超过属猪边界.


    Args:
        arr (List[int]): 数组

    Returns:
        List[int]: 重新排列后的数组
    """
    even, idx = 0, 1
    while even < len(arr) and idx < len(arr):
        while even < len(arr) and not arr[even] % 2:
            even += 2

        while idx < len(arr) and arr[idx] % 2:
            idx += 2

        if idx < len(arr) and even < len(arr):
            arr[idx], arr[even] = arr[even], arr[idx]
    return arr

操作系统

名次解释

1. 进程

   进程实体的运行过程, 是系统进行资源分配和调度的基本单位.

2. 虚拟地址

   通过某种虚拟技术模拟出来的地址空间的技术.

3. 多道程序设计

   在计算机内存中同时存放几道相互独立的程序, 使它们在管理程序的控制下, 相互穿插的运行. 两个或两个以上程序在计算机系统中同处于开始到结束之间的状态.

4. 分时操作系统

   多个用户通过终端同时共享一台主机, 这些终端连接在主机上, 用户可以同时与主机进行交互操作而互不干扰.

5. 动态重定位

   在程序运行过程中要访问数据时再进行逻辑地址与物理地址的变换(即在逐条指令执行时完成地址映射. 一般为了提高效率, 此工作由硬件地址映射机制完成. 硬件支持, 软硬件结合完成) 硬件上需要一对寄存器的支持.

叙述文件目录项, 文件目录, 目录文件之间的差别和关系.

文件目录项是为了使文件控制块与文件一一对应, 而其中的每一个文件控制块被称为文件目录项.

而把所有的文件目录项组织在一起, 就构成了文件目录, 即文件控制块的有序集合.

为了实现对文件目录的管理, 通常将文件目录以及文件的形式保存在外存, 这个文件就叫做目录文件.

三者之间的关系是包含与被包含的关系, 但也存在区别, 目录文件存储有文件目录项, 文件目录也包含文件目录项的相关信息, 但是目录文件并不包含全部的文件目录.

虚拟内存的目的和作用

目的: 在计算机系统中, 由于许多在程序运行中不用或暂时不用的程序和数据占据了大量的内存空间, 而一些需要运行的作业无法装入内存运行. 显然, 内存是十分宝贵的. 为了解决这个问题, 就需要虚拟内存技术. 即拿出一部分的硬盘空间来充当内存使用, 当内存占用紧张时, 系统就会自动调用硬盘来充当内存, 以缓解内存的紧张. 而在需要使用到相应的数据时, 才会将硬盘的数据重新读取进内存.

比较两种进程调度算法

1. 先来先服务算法

   优先执行最先进入就绪状态的进程, 在当前进程结束后才让出 CPU.

   利于长作业的工作, 但是不利于短作业的工作. 有利于 CPU 繁忙的作业, 而不利于 IO 繁忙的作业.

2. 优先级算法

   每个进程会有一个相应的优先级, 根据高优先级优先的原则, 优先级越高就会越先得到 CPU 资源.

   有利于重要的进程优先执行. 但是会造成低优先级的进程持续得不到处理的情况.

银行家算法

银行家算法是著名的死锁避免算法.

其思想是:把操作系统看做是银行家, 操作系统管理的资源相当于银行家管理的资金, 进程向操作系统请求分配资源相当于用户向银行贷款. 操作系统按照银行家指定的规则为进程分配资源, 当进程首次申请资源时, 要测试该进程对资源的最大需求量, 如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源, 否则推迟分配. 当进程在执行中继续申请资源时, 先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量. 若超过则拒绝分配资源, 若没有超过则再测试系统现存的资源能否满足该进行尚需的最大资源量, 若能满足则按当前的申请量分配资源, 否则也要推迟分配。