2020年广东暨南大学计算机基础综合考研真题

2020 年广东暨南大学计算机基础综合考研真题招生专业与代码：计算机系统结构 081201、计算机软件与理论 081202、计算机应用技术081203、电子信息(专业学位) 085400考试科目名称及代码：计算机基础综合 848考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。 第一部分 数据结构（75 分）一、单项选择题(每题 2 分，共 20 分) 1. 含有 m 个结点的二叉树链式存储结构中空指针的个数为 ( )。A．2m B．m-1 C．m+1 D．m2. 下列排序算法中元素的移动次数和关键字的初始排列次序无关的是（ ）。A. 快速排序 B. 插入排序 C. 选择排序 D. 希尔排序3. 一个栈的进栈序列是 a b c d e，则栈的输出序列不可能的是（ ）。 A．a b c d e B．e d c b a C．d e c b a D．d c e a b4. 需要的辅助空间最多的排序算法为（ ）。 A. 归并排序 B. 快速排序 C. 基数排序 D. 堆排序5. 哈希表的平均查找长度说法错误的是 ( )。 A. 与处理冲突方法有关而与表的长度无关 B. 与选用的哈希函数有关 C. 与哈希表的饱和程度有关 D. 与表中填入的记录数有关6. 有 n 个顶点 、e 条边且使用了邻接表存储的有向图进行深度优先遍历，其算法的时间复杂度是（ ）。 A. O（n+e） B. O（n2） C. O（n+2e） D. O（n*e）7. 已知一个长度为 11 的顺序表，其元素按关键字有序排列，若采用折半查找查找一个其中不存存在的元素，则关键字的比较次数最多是（ ）。A．3 B．4 C．5 D．68. 一棵完全二叉树上有 3001 个结点，其中叶子结点的个数是（ ）。 A. 1500 B.1501 C. 1000 D.10019. 若一棵二叉树度为 2 的结点有 18 个，度为 1 的结点有 10 个，则度为 0 的结点个数是（ ）。 A. 46 B. 28 C. 19 D. 1710. m 阶 B-树是一棵（ ）。A .m 叉排序树 B. m-1 叉平衡排序树 C. m 叉平衡排序树 D. m+1 叉平衡排序树二、填空题(每空 2 分，共 14 分)1. 已知一棵二叉树的中序遍历序列为GDHBAECIF，后序遍历序列为GHDBEIFCA，那么先序遍历序序列为 。2. 若某记录的关键字序列是（491，77，572，16，996，101，863，258，689，325），以第一个关键字为枢轴，写出采用快速排序算法第一趟排序的结果 。3. 将对称矩阵 A[8][8]的下三角部分逐行存储到起始地址为 2000 的内存单元中，已知每个元 素 占 4 个 单 元 ， 假 设 第 一 个 元 素 是 A[0][0] ， 则 A[4][6] 的 地 址 是 。4. 在顺序表中插入一个元素，需要平均移动表中一半元素，具体移动元素的个数与 有关。5.在哈希查找方法中，要解决两方面的问题，它们是 和 。6. 循环队列中，Q.rear == Q.front表示循环队列空，表示循环队列满的条件是 。三、简答题（共 3 小题，每题 7 分，共 21 分）1. 将下面的森林转换为二叉树（3 分），并给出该二叉树的中序线索链表（4 分）。 2. 设 Huffman 编码的长度不超过 4，若已对两个字符编码为 01 和 11，则最多还可以对多少个字符编码，为什么？(7 分）3. 假设图的顶点是 A、B、C、D、E，请根据下面的邻接矩阵画出相应的有向图（3 分），然后画出图的邻接表和逆邻接表（4 分）。考试科目：计算机基础综合 共 4 页，第 1 页ABCDEFGH四、编写算法（共 2 小题，每题 10 分，共 20 分）1. 试编写一个算法完成下面的功能：对于输入的任意一个非负十进制整数，输出与其等值的八进制数。（10 分）2. 试编写一个算法，在有向图 G 中，判定从顶点 Vi 到顶点 Vj 是否有通路。（10 分）第二部分 操作系统（75 分）五、判断题(每小题 1 分，共 10 分，正确的打√，错误的打×) 1. 系统调用中的被调用程序运行在系统态。2. 银行家算法采用了死锁预防的方法。3. 文件系统采用树形目录结构可以节省内存空间。4. 虚存管理允许用户程序大于主存容量，而且还可以提高系统的吞吐量。5. SPOOLing 系统实现了设备的独立性。6. 分时系统的时间片越小，用户的满意度就越高。7. 管程每次只允许一...