2016年暨南大学数据结构考研试题答案
- 格式：pdf
- 大小：493.77 KB
- 文档页数：7
文档推荐
-
暨南大学2018考研真题之830数据结构页数:10
-
2016年暨南大学数据结构考研试题答案页数:7
下载文档原格式
合集下载
暨南大学软件工程830数据结构2016年真题
(1)构造赫夫曼树(Huffman)的算法。（8分）
(2)求各字符赫夫曼编码的算法。（7分）
考试科目：数据结构共5页，第5页
1.已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，求解下列问题：
(1)画出此二叉树。（4分）
(2)将该二叉树转换成森林。（4分）
2.设有一组关键字（71,23,73,14,55,89,33,43,48）,采用哈希函数：H(key)=key %10，采
用开放地址的二次探测再散列方法解决冲突，试在散列地址空间中对该关键字序列(按从左
else
return Find((10), item );
}
}
六．编写算法（25分）
1.设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。（10分）
2.设有一整型数组w保存n个字符的权值（均大于0），请写出
7.向二叉排序树中插入一个新结点，需要比较的次数可能大于此二叉树的高度h。（）
8.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树高度为原树的高度加1。（）
9.无向图的邻接矩阵一定是对称阵。( )
10.对小根堆进行层次遍历可以得到一个有序序列。（）
考试科目：数据结构共5页，第2页
四.简答题（45分）
{
BiThrNode *p;
p=(3)
while(p!=T){ //空树或遍历结束时p==T
while(p->LTag==Link)(4)
if(!Visit(p->data)) return ERROR;
(2)求各字符赫夫曼编码的算法。（7分）
考试科目：数据结构共5页，第5页
1.已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，求解下列问题：
(1)画出此二叉树。（4分）
(2)将该二叉树转换成森林。（4分）
2.设有一组关键字（71,23,73,14,55,89,33,43,48）,采用哈希函数：H(key)=key %10，采
用开放地址的二次探测再散列方法解决冲突，试在散列地址空间中对该关键字序列(按从左
else
return Find((10), item );
}
}
六．编写算法（25分）
1.设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。（10分）
2.设有一整型数组w保存n个字符的权值（均大于0），请写出
7.向二叉排序树中插入一个新结点，需要比较的次数可能大于此二叉树的高度h。（）
8.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树高度为原树的高度加1。（）
9.无向图的邻接矩阵一定是对称阵。( )
10.对小根堆进行层次遍历可以得到一个有序序列。（）
考试科目：数据结构共5页，第2页
四.简答题（45分）
{
BiThrNode *p;
p=(3)
while(p!=T){ //空树或遍历结束时p==T
while(p->LTag==Link)(4)
if(!Visit(p->data)) return ERROR;
02331 - 2016年04月 - 数据结构试题及答案
2016年4月高等教育自学考试全国统一命题考试数据结构试卷(课程代码02331)注意事项：1．本试卷分为两部分，第一部分为选择题，第二部分为非选择题。
2．应考者必须按试题顺序在答题卡(纸)指定位置上作答，答在试卷上无效。
3．涂写部分、画图部分必须使用2B铅笔书写部分必须使用黑色字迹签字笔。
第一部分选择题一、单项选择题（本大题共15小题，每小题2分，共30分）1．下列选项中，属于非线性数据结构的是（）A．队列B．栈C．二叉排序树D．线性表2．瑞士计算机科学家沃思教授曾指出：算法+数据结构=程序．这里的数据结构指的是（）A．数据的逻辑结构和存储结构B．数据的线性结构和非线性结构C．数据的紧凑结构和非紧凑结构D．数据的顺序结构和链式结构3．线性表顺序存储时，逻辑上相邻的两个数据元素，其存储地址（）A．一定相邻B．一定不相邻C．不一定相邻D．可能不相邻4．数据元素1，2，3，4，5依次入栈，则不可能得到的出栈序列是（）A．4，5，3，2，1 B．1，2，3，4，5C．4，3，5，1，2 D．5，4，3，2，15．设顺序表首元素A[0]的存储地址是4000，每个数据元素占5个存储单元，则元素A[20]的起始存储地址是（）A．4005 B．4020 C．4100 D．41056．广义表 A=(a，(b，c，(e，f)))，函数 head(head(tail(A)))的运算结果是（）A．a B．b C．c D．e7．设高度为h的二叉树中，只有度为0和2的结点，则此类二叉树包含的结点数至少是（）A．2h B．2h-1 C．2h+1 D．h+18．—棵非空二叉树T的前序遍历和后序遍历序列正好相反，则T一定满足（）A．所有结点均无左孩子B．所有结点均无右孩子C．只有一个叶子结点D．是一棵满二叉树9．设图的邻接矩阵A如下所示。
各顶点的度依次是（）A．1，2，1，2 B．2，2，1，1 C．3，4，2，3 D．4，4，2，21O．无向图G如题10图所示，从顶点a开始进行深度优先遍历，下列遍历序列中，正确的是（）A．a，b，e，c，d，f B．a，c，f，e，d，bC．a，c，b，e，f，d D．a，e，d，f，c，b11．设带权连通图G中含有n（n>1）个顶点，下列关于G的最小生成树T的叙述中，正确的是（）A．T中可能含有回路B．T中含有图G的所有边C．T是唯一的，且含有n-1条边D．T可能不唯一，但权一定相等12．若要求对序列进行稳定的排序，则在下列选项中应选择（）A．希尔排序B．快速排序C．直接插入排序D．直接选择排序13．下列排序算法中，空间复杂度最差的是（）A．归并排序B．希尔排序C．冒泡排序D．堆排序14．下列排序算法中，初始数据有序时，花费的时间反而更多的算法是（）A．插入排序B．冒泡排序C．快速排序D．希尔排序15．对线性表L进行二分查找时，要求L必须满足（）A．以顺序方式存储B．以顺序方式存储，且数据元素有序C．以链接方式存储D．以链接方式存储，且数据元素有序第二部分非选择题二、填空题（本大题共10小题，每小题2分，共20分）16．下面程序段的时间复杂度是_________。
数据结构习题解答
数据结构习题解答信息工程学院徐燕萍第1章绪论一、基本内容数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念术语的确定含义；抽象数据类型的定义、表示和实现方法；描述算法的类C语言；算法设计的基本要求以及从时间和空间角度分析算法的方法。
二、学习要点1．熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。
分清哪些是逻辑结构的性质，哪些是存储结构的性质。
2．了解抽象数据类型的定义、表示和实现方法。
3．熟悉类C语言的书写规范，特别要注意值调用和引用调用的区别，输入、输出的方式以及错误处理方式。
4．理解算法五个要素的确切含义：①动态有穷性（能执行结束）；②确定性（对于相同的输入执行相同的路径）；③有输入；④有输出；⑤可行性（用以描述算法的操作都是足够基本的）。
5．掌握计算语句频度和估算算法时间复杂度的方法。
三、基础知识题1.1简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。
答：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
数据对象是性质相同的数据元素的集合，是数据的一个子集。
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
存储结构是数据结构在计算机中的表示（又称映像）。
数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。
1.2试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。
答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。
数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。
程序设计语言中的数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
而抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。
数据结构暨南大学期末试卷试题
数据结构暨南大学期末试卷试题一、判断题(共10分)1. 当静态链表采用数组实现时，插入与删除操作仍需移动元素。
2. 栈也是一种线性表，也同样有顺序存储结构和链式存储结构。
3. 二叉树的三种遍历算法区别仅在于对树根、左右子树访问先后顺序的不同。
4. 邻接表是图的一种顺序存储结构。
5. 二叉树就是度数为2的树。
6. 在哈希表中勿需比较就可找到记录在表中的位置。
7. 线性表的链式存储结构既方便其存取操作，也方便其插入与删除操作。
8. 顺序存储结构既适合于完全二叉树，也同样适合于一般的二叉树。
9.一个算法是正确的、高效率的，还不能说它就是一个“好”的算法。
10. 快速排序与堆排序的平均时间复杂度相同。
二、概念填空(共20分，每题2分)1.对顺序存储结构的线性表，设表长为La;在各元素插入为等概率条件下，插入一个数据元素需平均移动表中元素_______ 个;在最坏情况下需移动表中元素_______ 个。
2.从逻辑角度看，四种基本的数据结构可分为__________、___________、____________和____________;两种存储结构为_____________和_________________。
3.一个深度为,的满k(k>2)叉树，其第i层(若存在)有________个结点;编号为p(p>1)的结点其父结点(父结点为非根结点)编号是___________________。
4.具有n个结点的完全二叉树的深度为____________;编号为p(<n)的结点其右孩子(若存在)结点编号是___________。
5.堆栈被称为一个_____________的线性表;队列被称为一个_____________的线性表。
6.静态查找表的查找方法主要有:有序表查找及________________________;在n个记录中进行折半查找，当查找不成功时，与关键字比较次数最多为_____________________。
数据结构习题参考答案与解析
习题1 参考答案1至8题答案略。
9.（1）【解】该逻辑结构为线性结构，其图形表示如下：（2）【解】该逻辑结构为树型结构，其图形表示如下：（3）【解】该逻辑结构为图型结构，其图形表示如下：（4）【解】该逻辑结构为线性结构，其图形表示如下：10.【解】该图书库存管理系统所要处理的数据对象为图书，所以该问题中涉及的数据元素为图书，设数据元素类型为bookType 类型。
每个数据元素应包含的数据项有图书编号、书名、作者、出版社、出版日期等。
可用一个表格（如下表）的形式表示图书间的逻辑关系，即该问题数学模型可采用简单的线性结构来表示。
根据问题需求功能目标，此模型的所需的主要处理操作有插入、删除、查找和修改等基本操作。
所以，现用抽象数据类型bookList 表示问题模型，其逻辑结构与基本操作的定义如下： （1）逻辑结构bookList=( D, {r} )D={b i | b i 为bookType 类型的元素，i=1,2,3, ....., n ，n ≥0} r ={ <bk i ,b i+1>| i=1,2,…, n -1, n ≥0 } （2）基本操作 ①初始化操作函数：InitBookList(&BL)。
……初始条件：图书表BL 不存在。
操作结果：构造一个空的图书表BL 。
②求图书表长度操作函数：bookListLength(BL)。
初始条件：图书表BL 已存在。
操作结果：返回图书表BL 中所包含的数据元素（图书）的个数。
③取图书表中元素操作函数：getBook(BL, i, &b)。
初始条件：图书表BL 已存在，且1≤i ≤bookListLength(BL)。
操作结果：用b 返回图书表BL 中的第i 个数据元素的值。
④按编号查找操作函数：locateById(BL, id)。
初始条件：图书表BL 已存在，id 是给定的一个图书编号。
操作结果：返回图书表BL 中图书编号为id 的数据元素的位序，若这样的数据元素不存在，则返回0。
《数据结构》考研辅导练习题答案
第1章绪论参考答案四、应用题1.（1）数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。
数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，和存储结构无关，而运算的实现则是依赖于存储结构。
（2）逻辑结构相同但存储不同，可以是不同的数据结构。
例如，线性表的逻辑结构属于线性结构，采用顺序存储结构为顺序表，而采用链式存储结构称为线性链表。
（3）栈和队列的逻辑结构相同，其存储表示也可相同（顺序存储和链式存储），但由于其运算集合不同而成为不同的数据结构。
（4）数据结构的评价非常复杂，可以考虑两个方面，一是所选数据结构是否准确、完整的刻划了问题的基本特征；二是是否容易实现（如对数据分解是否恰当；逻辑结构的选择是否适合于运算的功能，是否有利于运算的实现；基本运算的选择是否恰当。
）2．评价好的算法有四个方面。
一是算法的正确性；二是算法的易读性；三是算法的健壮性；四是算法的时空效率（运行）。
3．略4．“数据结构”这一术语有两种含义，一是作为一门课程的名称；二是作为一个科学的概念。
作为科学概念，目前尚无公认定义，一般认为，讨论数据结构要包括三个方面，一是数据的逻辑结构，二是数据的存储结构，三是对数据进行的操作（运算）。
而数据类型是值的集合和操作的集合，可以看作是已实现了的数据结构，后者是前者的一种简化情况。
5．（1）顺序存储方式。
数据元素顺序存放，每个存储结点只含一个元素。
存储位置反映数据元素间的逻辑关系。
存储密度大，但有些操作（如插入、删除）效率较差。
（2）链式存储方式。
每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。
指针反映数据元素间的逻辑关系。
这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），另外不能折半查找等。
（3）索引存储方式。
除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标），兼有静态和动态特性。
自考《数据结构》真题和答案
2016年10月高等教育自学考试全国统一命题考试数据结构试卷(课程代码02331)本试卷共7页，满分l00分，考试时间l50分钟。
考生答题注意事项：1．本卷所有试题必须在答题卡上作答。
答在试卷上无效，试卷空白处和背面均可作草稿纸。
2．第一部分为选择题。
必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。
3．第二部分为非选择题。
毖须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。
4．合理安排答题空间，超出答题区域无效。
第一部分选择题(共30分)一、单项选择题(本大题共l5小题，每小题2分，共30分>在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡”的相应代码涂黑。
错涂、多涂或未涂均无分。
1．下列选项中，不属于线性结构特征的是A．数据元素之间存在线性关系 B．结构中只有一个开始结点C．结构中只有一个终端结点 D．每个结点都仅有一个直接前趋2．设l7个元素的顺序表中，若将第个元素e移动到第个位置，不改变除e外其他元素之间的相对次序，则需移动的表中元素个数是3．若用一个大小为7的数组作为循环队列的存储结构，且当前rew和盘0nt的值分别为2和4，在此之前的操作是从队列中删除了一个元素及加入两个元素，请问这3个操作之前rear和矗0nt的值分别是A．0和l B．0和3 C．3和6 D．4和54．已知广义表LS=(((a))，((b，(c))，(d，(e，f)))，0)，LS的长度是A．2 B．3 C．4 D. 55．一棵完全二叉树T的全部k个叶结点都在同一层中且每个分支结点都有两个孩子结点。
于中包含的结点数是A．k B. 2k-1 C．k2 D．2k-16．如果某二叉树的前序遍历序列为abced，中序遍历序列为cebda，则该二叉树的后序遍历序列是A．cedba B．decba C．ecdba D．ecbad7．一个森林有m棵树，顶点总数为n，则森林中含有的总边数是A．m B. n-l C．n-m D．n+m8．设图的邻接矩阵A如下所示。
2016年考研核心题型【数据结构部分】【第7章 排序】
温馨提示：快速排序主要考查两点：1、快速排序算法的特点；2、快速排序算法实现； 3、快速排序的过程或者一趟排序的结果。本考点历年考查很多，是复习的重点，请同学们 务必掌握。
接插入排序每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍
然有序。
折半插入排序是对直接插入排序算法的一种改进。由于前半部分为已排好序的数列，
这样我们可以不用按顺序依次寻找插入点，而是采用折半查找的方法来加快寻找插入点的
速度。折半查找的方法来寻找插入位置，可以减少比较次数。但不影响排序的趟数（仍然
本题只剩下希尔排序了，事实上，本题是利用增量为 d=5、3、1 来对关键字｛50 , 26 , 38 , 80 , 70 , 90 , 8 , 30 , 40 , 20 ｝进行希尔排序。其排序过程如图 7.2 所示。
我方慎重声明，各盈利机构若采用我方资料，必追究法律责任
102
2016 年考研核心考点命题思路解密 数据结构 梦享团队主编
1. 对一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是
（
）。
A. 排序的总趟数
B. 元素的移动次数
C. 使用辅助空间的数量
D. 元素之间的比较次数
【2012 年统考——第 11 题】
【考查内容】直接插入排序和折半插入排序的区别。
【解析】所谓排序算法过程，就是不断的依次将元素插入前面已排好序的序列中。直
一趟冒泡排序结束。
整个排序过程如下图所示。
其过程如图 7.1 所示。
50 40 95 20 15 70 60 45 80
50>40，50和40交换
40 50 95 20 15 70 60 45 80
《暨南大学830数据结构2011-2019年考研真题及答案解析》
Ⅱ 历年考研真题试卷答案解析.............................................................................................49
暨南大学 2011 年招收攻读硕士学位研究生入学考试试题答案解析................................ 49 暨南大学 2012 年招收攻读硕士学位研究生入学考试试题答案解析................................ 64 暨南大学 2013 年招收攻读硕士学位研究生入学考试试题答案解析................................ 79 暨南大学 2014 年招收攻读硕士学位研究生入学考试试题答案解析（A 卷）..................... 96 暨南大学 2015 年招收攻读硕士学位研究生入学考试试题答案解析（B 卷）................... 113 暨南大学 2016 年招收攻读硕士学位研究生入学考试试题答案解析（A 卷）................... 130 暨南大学 2017 年招收攻读硕士学位研究生入学考试试题答案解析（A 卷）................... 144
3. 线性表的动态链表存储结构与顺序存储结构相比，优点是（ ）。
A. 所有的操作算法实现简单
B. 便于随机存取
C. 便于插入与删除
D. 便于节省存储器空间
4．若进栈序列为 1，2，3，4，5，6， 且进栈和出栈可以穿插进行，则可能出现的出
栈序列为（ ）。
A． 3，2，6，1，4，5
B．5，6，4，2，3，1
五、算法填空， （每空 2 分，共 16 分）
1.下面的算法是一个在元素按值递增排列，并以带头结点的单链表作存储结构的线性表
暨南大学 2011 年招收攻读硕士学位研究生入学考试试题答案解析................................ 49 暨南大学 2012 年招收攻读硕士学位研究生入学考试试题答案解析................................ 64 暨南大学 2013 年招收攻读硕士学位研究生入学考试试题答案解析................................ 79 暨南大学 2014 年招收攻读硕士学位研究生入学考试试题答案解析（A 卷）..................... 96 暨南大学 2015 年招收攻读硕士学位研究生入学考试试题答案解析（B 卷）................... 113 暨南大学 2016 年招收攻读硕士学位研究生入学考试试题答案解析（A 卷）................... 130 暨南大学 2017 年招收攻读硕士学位研究生入学考试试题答案解析（A 卷）................... 144
3. 线性表的动态链表存储结构与顺序存储结构相比，优点是（ ）。
A. 所有的操作算法实现简单
B. 便于随机存取
C. 便于插入与删除
D. 便于节省存储器空间
4．若进栈序列为 1，2，3，4，5，6， 且进栈和出栈可以穿插进行，则可能出现的出
栈序列为（ ）。
A． 3，2，6，1，4，5
B．5，6，4，2，3，1
五、算法填空， （每空 2 分，共 16 分）
1.下面的算法是一个在元素按值递增排列，并以带头结点的单链表作存储结构的线性表
暨南大学830数据结构2010,2012--2020年考研专业课真题
2020年全国硕士研究生统一入学考试自命题试题B卷********************************************************************************************学科、专业名称：网络空间安全研究方向：网络空间安全083900考试科目名称及代码：数据结构830考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。
一、单项选择题(每题2分，共30分)1. 下述关于顺序存储结构优点的说法，哪个是正确的（）A. 插入运算方便B. 可方便地用于各种逻辑结构的存储表示C. 存储密度大D. 删除运算方便2. 假设根结点为第1层，深度为h层的二叉树至少有( ) 个结点(h>1)；A. 2hB. 2h-1C. 2h+1D. 2h-13. 用单向链表来实现容量为n的堆栈时，链表头指针指向堆栈顶部元素，链表尾指针指向堆栈底部元素，则以下说法错误的是( )A. 入栈操作的复杂度为O(1)B. 出栈操作的复杂度为O(1)C. 删除底部元素的复杂度为O(1)D. 插入一个新的堆栈底部元素复杂度为O(1)4. 以下关于递归算法的论述，不正确的是( )A. 递归算法的代码可读性好B. 递归算法可以提高程序运行效率C. 递归调用层次太深有可能造成堆栈溢出D. 递归调用层次太深会占用大量内存5. 设有字符集合{4,6,3,W,S}，将字符序列6W43S中的字符按顺序进入堆栈，出栈可发生在任何时刻。
则以下的出栈序列错误的是（）。
A. 64WS3B. 4W36SC. 6W34SD. WS4366. 在管理城市道路交通网络据时，最适合采用（）数据结构来对其进行存储。
A．有向图B．无向图C．树D．矩阵7. 具有k个顶点的完全有向图的边数为( )。
A. k(k-1)B. k(k-1)/2C. k2-1D. k2+18. 若线性表最常用的操作是增加或者删除某个元素, 则采用( )存储方式节省时间.A. 单链表B. 双链表C. 单循环链表D. 顺序表9. 由权为6,3,2,8的四个叶子结点构造一个哈夫曼树，该树的带权路径长度为（）。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
}
void traverse(Tree T,int deepth,int &ans){//递归遍历二叉树，累加计算带权路径长度
if(T == NULL) return;
if(T->lchild == NULL && T->rchild == NULL){
ans += T->weight*deepth;
7. X
8. √
9. √
10. X
四、
简答题
1. （1）画出二叉树如下：
（2）将该数转换为森林得：
2. 画出散列之后的 hash 表得：
0
1
48
71
2
3
4
5
6
7
8
9
23
73
14
55
33
43
89
成功查找的平均查找长度为：（1+1+2+2+2+1+5+6+3）/7=23/7
3. 平衡二叉树构造过程如下：
五、
算法填空
1. （1）p->next=L->next
（2）L->next=p
2.
（3）T->lchild
（4）p=p->lchild
（5）p->rchild!=T
（6）p=p->rchild
（7）p=p->rchild
3. （8）T==NULL
（9）T->lchid
（10）T->rchild
六、编写算法
a[low]=a[high];
while(low<high&&a[low]<key])
low++;
a[high]=a[low];
}
a[low]=p;
}
2. （1）构建 Huffman 树的代码如下：
#include <iostream>
#include <cstdlib>
using namespace std;
int min,second_min;
min = 0;
for(int k = 0; k < length; k++){
if(T[k]->weight < T[min]->weight){
min = k;
}
}
if(min == 0){
second_min = 1;
}else{
second_min = 0;
//在节点数组中删除原节点 j
for(int k = j-1; k < length-1; k++){
T[k] = T[k+1];
}
length--;
//将合并后的节点存储起来
T[length++] = temp;
}
void findMin(Tree* T,int &length, int &i, int &j){//寻找权值最小的两个节点
Tree t[n];
int length = n;
for(int i = 0; i < n; i++){
t[i] = (Tree)malloc(sizeof(TreeNode));
cin >> t[i]->weight;
t[i]->lchild = NULL;
t[i]->rchild = NULL;
typedef struct BinTreeNode{
int weight;
BinTreeNode *lchild;
BinTreeNode *rchild;
}TreeNode,*Tree;
void mergeTreeNode(Tree* T, int &length, int i, int j);//合并树的节点
4.（1）邻接表如下：
（2）按克鲁斯卡尔（Kruskal）算法求其最小生成树，其过程如下：
5. （1）若采用 shell 排序，第一趟结构为：
(142,111,123,65,102,879,572,434,543,242,811,453)。
（2）初始堆为：
初始堆第一趟排序的结果为：(142,543,123,65,453,879,572,434,111,242,811,102)。
}
while(length>1){//数组中节点个数大于 1 时循环
int i,j;
findMin(t,length,i,j);
mergeTreeNode(t,length,i,j);
}
int ans = 0;
traverse(t[0],0,ans);
cout << endl;
cout << "ans=" << ans << endl;
temp->weight = T[i]->weight + T[j]->weight;
temp->lchild = T[i];
temp->rchild = T[j];
//在节点数组中删除原节点 i
for(int k ++){
T[k] = T[k+1];
}
length--;
return 0;
}
void mergeTreeNode(Tree* T, int &length, int i, int j){//合并树的节点
if(length <= 1)
return;
//生成合并后的节点
Tree temp;
temp = (Tree)malloc(sizeof(TreeNode));
}
traverse(T->lchild,deepth+1,ans);
traverse(T->rchild,deepth+1,ans);
}
（2）在求得 Huffman 树的情况下，我们可以采用中序遍历非递归，当遇到叶子结点的时候，我们遍
历栈中的内容，即为该叶子结点的 Huffman 编码。
void findMin(Tree* T,int &length, int &i, int &j);//寻找权值最小的两个节点
void traverse(Tree T,int deepth,int &ans);//递归遍历二叉树，累加计算带权路径长度
int main(void){
int n;
cin >> n;
1. 算法思想：基于快速排序
//假设关键字都是存储在 a[]数组中
void division(int a[],int n,int key){
int low=0，high=n-1;
int p=a[low]
while(low<=high){
while(low<high&&a[high]>=key])
high--;
一、
选择题
1. B
【解答】线索二叉树的构成
2. B
3. A
4. C
5. A
6. 1200
【解答】因为是按照行优先次序存储，根据规则，可得：
A[5,5]的地址为：1000+[5*(6+1)+5]*5=1200
7. A
【解答】结点数最小的情况是：前 n-1 层都是满的，第 n 层就一个节点
8. B
9. C
}
for(int k = 0; k < length; k++){
if(k!=min && T[k]->weight < T[second_min]->weight){
second_min = k;
}
}
i = min > second_min ? second_min:min;
j = min > second_min ? min:second_min;
10. D
11. D
12. A
【解答】无向图没有方向,所以相应的邻接矩阵是对称的
13. D
14. C
15. A
二、
填空题
1. n-i
2. (SQ.front+1)%(m+1)
3. p->next=q->next
free(q)
4. (n+1)
5. 89
6. O(log2 )
O(nlog2 )
7. d
8. (1,4,2,3)
三、
判断题
1. X
【解答】在 n 个结点的无向图中,若该图是连通图,则其边数大于等于 n-1,
在 n 个结点的无向图中,若边数大于(n-2)(n-1)/2,则该图必是连通图。
2. √
3. X
4. √
5. X
【解答】数据元素是数据的基本单位
6. X
【解答】Prim 算法适用于求解边稠密的图的最小生成树
void traverse(Tree T,int deepth,int &ans){//递归遍历二叉树，累加计算带权路径长度
if(T == NULL) return;
if(T->lchild == NULL && T->rchild == NULL){
ans += T->weight*deepth;
7. X
8. √
9. √
10. X
四、
简答题
1. （1）画出二叉树如下：
（2）将该数转换为森林得：
2. 画出散列之后的 hash 表得：
0
1
48
71
2
3
4
5
6
7
8
9
23
73
14
55
33
43
89
成功查找的平均查找长度为：（1+1+2+2+2+1+5+6+3）/7=23/7
3. 平衡二叉树构造过程如下：
五、
算法填空
1. （1）p->next=L->next
（2）L->next=p
2.
（3）T->lchild
（4）p=p->lchild
（5）p->rchild!=T
（6）p=p->rchild
（7）p=p->rchild
3. （8）T==NULL
（9）T->lchid
（10）T->rchild
六、编写算法
a[low]=a[high];
while(low<high&&a[low]<key])
low++;
a[high]=a[low];
}
a[low]=p;
}
2. （1）构建 Huffman 树的代码如下：
#include <iostream>
#include <cstdlib>
using namespace std;
int min,second_min;
min = 0;
for(int k = 0; k < length; k++){
if(T[k]->weight < T[min]->weight){
min = k;
}
}
if(min == 0){
second_min = 1;
}else{
second_min = 0;
//在节点数组中删除原节点 j
for(int k = j-1; k < length-1; k++){
T[k] = T[k+1];
}
length--;
//将合并后的节点存储起来
T[length++] = temp;
}
void findMin(Tree* T,int &length, int &i, int &j){//寻找权值最小的两个节点
Tree t[n];
int length = n;
for(int i = 0; i < n; i++){
t[i] = (Tree)malloc(sizeof(TreeNode));
cin >> t[i]->weight;
t[i]->lchild = NULL;
t[i]->rchild = NULL;
typedef struct BinTreeNode{
int weight;
BinTreeNode *lchild;
BinTreeNode *rchild;
}TreeNode,*Tree;
void mergeTreeNode(Tree* T, int &length, int i, int j);//合并树的节点
4.（1）邻接表如下：
（2）按克鲁斯卡尔（Kruskal）算法求其最小生成树，其过程如下：
5. （1）若采用 shell 排序，第一趟结构为：
(142,111,123,65,102,879,572,434,543,242,811,453)。
（2）初始堆为：
初始堆第一趟排序的结果为：(142,543,123,65,453,879,572,434,111,242,811,102)。
}
while(length>1){//数组中节点个数大于 1 时循环
int i,j;
findMin(t,length,i,j);
mergeTreeNode(t,length,i,j);
}
int ans = 0;
traverse(t[0],0,ans);
cout << endl;
cout << "ans=" << ans << endl;
temp->weight = T[i]->weight + T[j]->weight;
temp->lchild = T[i];
temp->rchild = T[j];
//在节点数组中删除原节点 i
for(int k ++){
T[k] = T[k+1];
}
length--;
return 0;
}
void mergeTreeNode(Tree* T, int &length, int i, int j){//合并树的节点
if(length <= 1)
return;
//生成合并后的节点
Tree temp;
temp = (Tree)malloc(sizeof(TreeNode));
}
traverse(T->lchild,deepth+1,ans);
traverse(T->rchild,deepth+1,ans);
}
（2）在求得 Huffman 树的情况下，我们可以采用中序遍历非递归，当遇到叶子结点的时候，我们遍
历栈中的内容，即为该叶子结点的 Huffman 编码。
void findMin(Tree* T,int &length, int &i, int &j);//寻找权值最小的两个节点
void traverse(Tree T,int deepth,int &ans);//递归遍历二叉树，累加计算带权路径长度
int main(void){
int n;
cin >> n;
1. 算法思想：基于快速排序
//假设关键字都是存储在 a[]数组中
void division(int a[],int n,int key){
int low=0，high=n-1;
int p=a[low]
while(low<=high){
while(low<high&&a[high]>=key])
high--;
一、
选择题
1. B
【解答】线索二叉树的构成
2. B
3. A
4. C
5. A
6. 1200
【解答】因为是按照行优先次序存储，根据规则，可得：
A[5,5]的地址为：1000+[5*(6+1)+5]*5=1200
7. A
【解答】结点数最小的情况是：前 n-1 层都是满的，第 n 层就一个节点
8. B
9. C
}
for(int k = 0; k < length; k++){
if(k!=min && T[k]->weight < T[second_min]->weight){
second_min = k;
}
}
i = min > second_min ? second_min:min;
j = min > second_min ? min:second_min;
10. D
11. D
12. A
【解答】无向图没有方向,所以相应的邻接矩阵是对称的
13. D
14. C
15. A
二、
填空题
1. n-i
2. (SQ.front+1)%(m+1)
3. p->next=q->next
free(q)
4. (n+1)
5. 89
6. O(log2 )
O(nlog2 )
7. d
8. (1,4,2,3)
三、
判断题
1. X
【解答】在 n 个结点的无向图中,若该图是连通图,则其边数大于等于 n-1,
在 n 个结点的无向图中,若边数大于(n-2)(n-1)/2,则该图必是连通图。
2. √
3. X
4. √
5. X
【解答】数据元素是数据的基本单位
6. X
【解答】Prim 算法适用于求解边稠密的图的最小生成树