升研教育考研频道为23考研、24考研的同学们整理了“南京审计大学2022年考研真题：814数据结构”的相关信息，希望对正在备考的你有所帮助。考研复习效率不高怎么办？自己备考抓不住重点？想报考985/211等热门院校，但是没把握？升研教育推出考研集训营，全日制封闭式面授，10余年授课经验的老师，浓厚的学习氛围助你冲击目标、一战上研！

南京审计大学2022年考研真题：814数据结构

考试科目：814数据结构

适用专业：081200 计算机科学与技术

一.名词解释（共 6 小题，每题 5 分，共 30 分） 

1. 数据存储结构 

2. 平均查找长度 

3. 最小生成树 

4. 静态查找表 

5. 内部排序 

6. 有序树 

二. 简答题（共 4 小题，每题 10 分，共 40 分）

 1. 在单循环链表中，如果仅能设一个指针，你认为是设置头指针好还是尾指针好？说明原因。 

2. 为什么要将顺序队列臆造为一个环状的空间，也就是循环队列？ 

3. 二叉树就是度为 2 的有序树，这个结论对吗？为什么？ 

4. 具有 n 个结点的完全二叉树的深度为多少？为什么？ 

三. 综合应用题（共 8 小题，每题 10 分，共 80 分）

 1. 已知有如下 13 个数据的有序顺序表（关键字即为数据元素的值），从数组的 1 号单元保存到 13 号单 元：（03，05，08，13，16，20，26，36，42，48，56，64，72）。 

① 试画出描述折半查找过程的判定树；

② 给出查找关键字 21 的比较次数； 

③ 给出查找关键字 56 的比较次数； 

④ 给出查找成功时折半查找的平均查找长度；

⑤ 给出查找不成功时折半查找的平均查找长度。 

2. 已知单链表的存储结构定义为：

3. 已知如右图所示的有向图，请给出该图的: ① 每个顶点的入/出度； ② 邻接矩阵； ③ 邻接表； ④ 逆邻接表。

4. 画出下面这棵树的孩子-兄弟（或称二叉链表）表示法的存储结构示意图。并给出树的孩子-兄弟存储 表示（存储结构的定义）。

5. 设有正文 AADBAACACCDACACAAD,利用赫夫曼编码设计一套二进制编码，使得上述正文的编码 最短。 

6. 设有一组关键字（9,1,23,14,55,20,27），采用哈希函数：H(key)=key%7,存储到表长为 10（地址空 间为 0~9）的哈希表中，采用开放定址法的二次探测再散列法处理冲突。

要求： ①构造哈希表，画出哈希表的示意图； ②求出在查找每一个关键字概率相等情况下的平均查找长度。

 7. 已知二叉排序树的类型定义为：

补充下面的算法，对于给定的二叉排序树的结点 p，找出其左子树中的数据元素值最大的结点和右子树 中的数据元素值最小的结点。

8. 已知关键字序列（44，38，62，88，77，11，28，51，55，08，22），画出创建初始小顶堆的过程。 并要求给出每次调整后的序列和每次调整过程中的比较次数和交换次数。