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

2021 年广东暨南大学计算机基础综合考研真题招生专业与代码：计算机系统结构 081201、计算机软件与理论 081202、计算机应用技术081203、电子信息(专业学位) 085400考试科目名称及代码：计算机基础综合 848考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。 第一部分 数据结构（75 分）一、 单项选择题(每题 2 分，共 20 分) 1. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。 A.单链表 B.仅有头指针的单向循环链表 C.双链表 D.仅有尾指针的单向循环链表2. 一个栈的输入序列为 1，2，3...，n，若输出序列的第一个元素是 n，那么输出第 i（1<=i<=n）个元素是（ ）。 A. n-i B. i C. n-i+1 D. 不确定3. 若一颗二叉树具有 15 个度为 2 的结点，10 个度为 1 的结点，则度为 0 的结点个数是（ ）。 A. 16 B. 25 C. 40 D. 不确定 4. 根据使用频率，为 5 个字符设计的哈夫曼编码不可能是（ ）。 A. 000，001，010，011，1 B. 000，001，01，10，11 C. 00，100，101，110，111 D. 0000，0001，001，01，15. 设 a，b 为一棵二叉树上的两个结点，在中序遍历时，a 在 b 前面的条件是（ ）。 A.a 在 b 的右方 B. a 在 b 的左方 C. a 是 b 的祖先 D. a 是 b 的子孙6. 对一棵二叉排序树按（ ）遍历，可得到结点值从小到大的排序序列。 A. 先序 B. 中序 C. 后序 D. 层次7. 已知一个有序表为(5，13，19，21，37，56，64，75，80，88，92)，则折半查找 64 需要比较（ ）次。 A. 1 B. 2 C. 3 D. 48. 在一个图中，所有顶点的度数之和等于所有边数的（ ）倍。 A. 1/2 B. 1 C. 2 D. 39. 一个序列中有 100000 个元素，若只想得到其中前 10 个最大元素，则最好采用（ ）方法。 A. 快速排序 B. 堆排序 C. 插入排序 D. 归并排序10. 下列四个序列中，哪一个是堆（ ）。 A. 70，60，40，10，30，25，20，15 B. 70，60，30，15，25，40，20，10 C. 70，40，60，10，25，30，20，15 D. 70，40，60，30，15，25，20，10二．判断题(每题 1 分，共 10 分，正确的打√，错误的打×)1. 数据结构研究的是数据的物理结构、逻辑结构以及它们之间的相互关系。2. 线性表的顺序存储结构适用于频繁插入或删除数据元素的情况。3. 一颗满二叉树同时又是一颗平衡树。4. 一棵 m 阶 B-树中每个结点最多有 m 棵子树，非终端结点最少有 2 棵子树。5. 带权无向图的最小生成树是唯一的。6. 在各种查找方法中，平均查找长度与结点个数无关的查找方法是哈希查找。7. 拓扑排序是按AOE网中每个结点事件的最早发生事件对结点进行排序。8. 存在这样的二叉树，对它采用任何次序进行遍历，结果相同。9. 对于n个记录的集合进行冒泡排序，在最坏情况下的时间复杂度是O(n2) 。10. 若网中有几条关键路径，提高一条关键路径上的活动的速度，不能导致整个工程缩短工期。三．简答题（共 3 小题，每题 8 分，共 24 分）1. 请按照关键字 24，13，20，32，29，53 的次序构造一棵二叉平衡树，并给出过程。（8 分）2. 由 n 个权值构成的哈夫曼树共有多少个结点？（4 分）为什么？（4 分）3. 一个有六个顶点{V0,V1,V2,V3,V4,V5}的网络的邻接矩阵如图 1 所示，求出从顶点 V0到其他各顶点之间的最短路径，并写出计算过程。（8 分）四. 编写算法（共 2 小题，第 1 小题 10 分，第 2 小题 11 分，共 21 分）1. 设树的存储结构为孩子兄弟链表，试编写算法，输出树中所有从根到叶子的路径。（10分） 2. 设一个带头结点的单链表 L，数据元素为整数，其中大部分为正数，少数为负数，编写函数，实现将负数结点移到链表尾部，并返回调整后链表中第一个负数结点的位置。要求先给出算法思想，再写出相应算法。（11 分）第二部分 操作系统（75 分）一、判断题(每小题 1 分，共 10 分，正确的打√，错误的打×) 1. 设备的独立性是指 I/O 设备具有独立执...