资源描述：
《数据结构复习题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、复习一一、填空：1、抽象数据类型的三要素是，，。2、队列是。3、线索二叉树是。4、数据的逻辑结构是。5、在大根堆中，关键值最大的元素是。6、在记录集{2、5、7、10、14、15、18、20、22}中，进行二分查找，若要查找元素18，共需要比较次关键字。7、分层依次将一棵有n个结点的完全二叉树的所有结点从1到n编号，那么树的深度为。8、在一个长度为n的顺序表中第i个位置插入新元素时，需向后移动元素个数是 。9、在直接插入排序中使用监视哨的作用是。10、在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为。二、判断题（正确在
2、题后括号内划“√”，错误划“×”）1、在拓扑排序中，拓扑序列的第一个顶点必定是出度为零的顶点。（）2、算法DFS应用于一个带权连通图时，所经过的边形成一棵最小生成树。（）3、（101，88，46，70，34，39，45，58，66，10）是堆。（）4、n个结点的树的各结点度数之和为n-1。（）5、由二叉树的前序序列和中序序列能唯一确定一棵二叉树。（）6、有向图中一个顶点i的出度等于其邻接矩阵中第i列的非0元素的个数。（）7、哈夫曼树的带权路径长度WPL等于各叶子结点的带权路径长度之和（）8、所谓冲突即是两个关键字的值不同的元素
3、，其散列地址相同。（）9、设一个9阶的上三角矩阵A按列优先顺序压缩存储在一维数组B中，其中B[1]存储矩阵中第一个元素a[1,1],则B[5]中存放的元素是a[2,3]。（）10、在串S="structure"中，以t为首字符的子串有8个。（）三、求解与简答题：1、以数据集{2，6，13，17，20，30}为叶子结点的权值。（1）构造一棵哈夫曼树。（2）计算其带权路径长度。2、从一棵空的二叉排序树开始，将以下关键字值依次插入：28,20，13,15,31,7,23,37，请画出插入全部完成后的二叉排序树。假定每个数据的查询概率
4、相等，试计算查找成功的平均查找长度ASL的值。3、请比较队列与栈两种数据结构异同点，举例说明其应用场合。4、对关键字序列(72,87,61,23,100,15,7,60)进行堆排序，结果应按关键字递减次序排列（采用小根堆排序）。（1）试以二叉树的形式给出得到初始堆的过程；（2）写出经过二趟排序后关键字序列状态。5、设有下列无向图：V3V1V2V4V5V6（1）请写出图的邻接矩阵与该图的邻接表。（2）从V1出发，以邻接矩阵为存储结构，给出其ＤＦＳ序列。（3）从V1出发，以邻接表为存储结构，给出其ＢＦＳ序列。四、算法与编程题：１、
5、采用顺序存储结构，写出对n个记录进行简单选择排序的算法。２、假设以数组seq[Maxqsize]循环存放队列的元素，同时设立队头指针front,队尾指针rear。（1）用typedef定义出使用的存储结构；（2）给出初始化队列的算法；（3）给出入队的算法； ３、以二叉链表为存储结构，给出分层遍历二叉树的算法（从上至下、从左到右）。参考答案一、填空：1、数据对象、数据关系、数据上的基本操作。2、先进先出的线性表（FIFO）。插入在表的一端进行，删除在在表的另一端进行。3、加上线索的二叉树，线索是指向结点的前驱与后续的指针。4、数
6、据元素之间的逻辑关系。5、根元素6、27、[log2n]+18、n-i+19、减少比较次数、提高算法效率。10、n2–2e二、判断题（正确在题后括号内划“√”，错误划“×”）1、×2、×3、√4、√5、√6、×7、√8、√9、√10、×8851373021172013826三、求解与简答题：1、解：（1）哈夫曼树为：（6分）（2）带权路径长度WPL=(2+6)*4+13*3+(17+20+30)*2=2052、（10分）（1）二叉排序树为：（6分）282031132337715（2）查找成功的平均查找长度ASL=（4*2+3*
7、3+2*2+1）/8=11/43、相同点：都是一种线性表；不同点：对操作进行了不同限制，队列具有：FIFO特性，栈具有：LIFO特性。（3分）函数递归调用情况用栈，图的BFS遍历用队列。（）4、（1）初始堆为：（）7231560100728761（2）二趟排序后关键字序列状态为：{23，60，61，87，100，72，15，7}（）5、（15分）（1）邻接矩阵为：（4分）011100100001100010101011001100010100A=邻接表：V1V2V4V3V5V631244656411532V（2）从V1出发，以
8、邻接矩阵为存储结构，给出其ＤＦＳ序列为：V1,V2,V6,V4,V5,V3;（3）从V1出发，以邻接表为存储结构，给出其ＢＦＳ序列为：V1,V2,V3,V4,V6,V5;四、算法与编程题：1、简单选择排序的算法：Typedefstruct{Keytypekey;Infotyp
