天任考研小编为大家整理了“暨南大学2022年848计算机基础综合考研自命题试题”相关内容，为报考计算机专业的考生们提供指导。更多有关计算机考研干货可关注考研备考栏目。
2022年招收攻读硕士学位研究生入学考试试题( B )
招生专业与代码： 试卷内容结构
l. 数据结构 (75 分)
2 操作系统或C语言程序设计 (75 分)
报考010 信息科学技术学院下述5个专业的考生请选择操作系统作答
081201 计算机系统结构
081 202 计算机软件与理论
081203 计算机应用技术
085400 电子信息(专业学位)下设 02(全日制)计算机技术
报考044 智能科学与工程学院下述 2 个专业的考生请选择C语言程序设计作答
0812 Z3 人工智能考试科目：848 计算机基础综合
085400 电子信息(专业学位)下设01(全日制)人工智能
考生注意： 所有答案必须写在答题纸(卷)上，写在本试题上一律不给分.
第一部分 数据结构 ( 75 分)
一、 单项选择题(每题 1 分 ，共 8 分)
1. 为了操作方便，用单链表表示的 链式队列的队头应设在链表的( )位置。
A. 表头 B. 表尾 C. 表头和表尾均可 D. 链中
2. 一棵完全二叉树上有2001 个结点，其 中叶子结点的个数是 ( )。
A.500 B.501 C.1000 D.1001
3. 采 用邻接表存储的图，其深 度优先遍历类似千二叉树的( )。
A. 先序遍历 B.中序遍历 C. 后序遍历 D. 按层次遍历
4. 在含有N 个结点的线索二叉树中线索的数目为( )。
A. 2N B. N C. N-1 D. N+l
5. 若有一个栈的输入序列是I , 2 , 3, ... , n, 输出序列的第一个元素是 n, 则第 i 个输出元素是( )。
A. n-i B.n-i-1 C. n-i+ l D不确定
6. 二维数组行下标的范围从0 到 5 , 列下标的范围从 0 到 4, M 按行存储时元素M[3][4]的地址与M 按列存储时元素( )的地址相同。
A.M[l][4] B.M[3][4] C.m[1][3] D.M[4][4]
7. 已知一个有序表为 (18 , 26, 35, 59, 63, 75, 81), 则折半查找35 需要比较( )次。
A.I B.2 C.3 0.4
8. 以下排序算法中，占用辅助空间最多的是 ( )。
A堆 排序 B希 尔排序 C快速排序 D归 并排序
二.判断题(每题1分，共10分， 正确的写True, 错误的写false)
l. 栈和字符串都是线性结构.
2. 线性表中的每一个元素都有一个前 驱和一个后继元素。
3. 一棵树转换为二叉树后， 根结点没有右孩子.
4. 拓扑排序是一种内部排序的仅法.
5. 在中序线索化链表中， 如果结点有右子树，则结点的后继为对右子树进行中序遴历时访问的第一个结点.
.6 在一个有向图的邻接表或逆邻接表中，如 果某个顶点的链表为空， 则该顶点的度一定为零。
7. 哈夫曼树中权值最小的结点离根最近.
8. 无向图的邻接矩阵一定是对称的.
9. 用邻接矩阵法存储一个图时，在 不考虑压缩存储的情况下， 所占用的存储空间大小与图中结点的个数有关，而与图的边数无关。
10. 由同一 组关键字集合构造的各棵二叉排序树的形态不一定相同， 但平均查找长度相同。
三.填空题(共5 空，每空2 分，共10 分)
1、一组记录的关键字为( 87, 41, 52, 47, 36, 23, 89, 7 ) , 则利用归并排序的方法对该序
列作递增排序时第一趟排序的结果为 (1) 。
2、高度为h 的完全二叉树至少有 (2) 个结点，最多有 (3) 个结点。
3、如果一颗二叉树MT 是由有序树T 转换而来的， 那么 MT 中结点的中序遍 历序列相当于树中结点的 (4) 序列。
4 、 一组记录的排序码为(45, 56, 49, 33, 20, 72, 87, 30), 则利用快速排序的方法，以 第一个记录为基准得到的第一次划分结果为 (5) 。
四.简答题(共 4 小题，每题6 分，共24 分)
1. 若二叉树中各结点值均不相同。已知一个二叉树的前序和中序分别为 ABCDEFGH 和BDCEAFHG, 请画出此二叉树。
2. 应用栈操作求解算术表达式： 7+3X (5+6), 画出栈的变化过程。
3. 设有6 个字符 ( a, b, c, d, e, f), 其权值为( 14, 13, 16, 12, 18, 17), 请构造其Huffman
树， 给出它们的Huffman 编码以及编码的平均长度。
4. 设关键字序列为(15, 27, 50, 73, 49, 61, 37, 60), 散列表长m= l 4, 哈希函数为H(k)=k
mod I J. ( 1 ) 试给出采用二次探测法处理冲突的散列表; ( 2 ) 查找关键字49 时， 需要依次与哪些关键字比较; (3 ) 求等概率下查找成功的平均查找长度。
五.编写算法 (共 3 小题，每小题 7-8分，共 23 分)
I. 假设二叉树采用二叉链表存储， 试写出中序遍历二叉树的非递归算法，要求：先描 述二叉树的数据类型。(7 分)
2. 编写实现栈的两个基本运算的函数：入栈和出栈 (要求 采用顺序存储结构)。(8 分)
3. 假设无向图G 采用邻接表存储，编 写程序， 判断图G 是否是连通图。如果是连通图返回I,否则 返回 0。要求先给出算法思想，再写出相应代 码。(8 分)
以上是天任考研小编为大家带来的“暨南大学2022年848计算机基础综合考研自命题试题”，希望考生们都能备考顺利，考上自己心仪的院校。
