数据结构复习题(答案)

1、1长度为N的线性表，实施顺序查找，在查找不成功时，与关键字的比较次数为（ ）A1 BN+1 CN-1 DN E以上都不是答案：C2已知一个无向图G=（V，E），其中V= V1，V2，V3，V4，V5，V6，其邻接矩阵如下所示：（1） 请还原图G，并写出图G的邻接表；（2） 根据写出的邻接表，求出从V1开始的BFS和DFS遍历序列及生成树；（3） 根据写出的邻接表，画出图G的最小生成树。答案：(1-1)(1-2)(3)(3)3已知一棵二叉树的中序遍历序列为BAFDJGCKHLEIM，后续遍历序列为：BFJGDKLHMIECA。请完成：（1） 构造出这棵二叉树；（2） 画出这棵二叉树中序线索化后的

2、结构。答案：(1)(2)4什么叫冲突？解决冲突的方法有哪些？答案：5设一段正文为“THIS-IS-THE-THESTT-THAT-IT-TITHET-TETTEE”，其中所使用的字符集C=T，H，I，S，E，A，-，请用huffman算法设计一套C中字符的二进制编码，使上述正文的二进制编码最短，并计算出存储上述正文的二进制编码所需的字节数（设每一位字节是由8位组成）。答案：6设二叉树用二叉链表结构存储，请写出一个递归算法，实现判断二叉树T是否为二叉排序树的函数。答案：7已知二叉树如图所示，此二叉树的顺序存储结构是（ ）答案：C8对于图所示的带权有向图，从顶点1到顶点5的最短路径为（ ）A1，4

3、，5 B1，2，3，5C1，4，3，5 D1，2，4，3，5答案：D9答案：B、C10设G1=（V1，E1）和G2=（V2，E2）为两个图，如果VI V2，E1 E2，则称（ ）AG1是G2的子图 BG2是G1的子图CG1是G2的连通分量 DG2是G1的连通分量答案：A11由五个分别带权值为9，2，5，7，14的叶子结点构造一棵哈夫曼树，该树的带权路径长度为_。答案：8112当增量d为1时，该趟希尔排序与_排序基本一致。答案：直接插入13已知二叉树的二叉链表（如图所示），请写出该二叉树的后序遍历序列，并将二叉链表改为后序线索链表。答案：14设a1，a2，a3，是不同的关键字且a1a2a3，可组

4、成6种不同的输入顺序。问其中哪几种输入顺序所构造的二叉排序树的高度为3？答案：15已知二叉树以二叉链表作存储结构，阅读下列算法，说出它的功能。答案：由参数n返回二叉树p的叶子结点总数。16某百货公司仓库中电视机的价格和数量信息，按其价格从低到高存储在一个带头结点的循环链表中。链表中的结点由价格、数量和指针三个域组成： 现新到m台价格为c的电视机需入库，试为此编写修改循环链表中存储的电视机信息的算法，并进行算法分析。答案：17答案：18判断：在一个有向图中，所以顶点的入度之和等于所有顶点的出度之和。答案：对19-1某二叉树的先序序列和后序序列正好相反，则该二叉树一定是_的二叉树 A.空或只有一结

5、点 B.高度等于其结点数 C.任一结点无左孩子 D.任一结点无右孩子19-2在有n个叶子结点的哈夫曼树中，其结点总数为_ A.不确定 B.2n C.2n+1 D.2n-119-3一个有n结点的无向图最多有_条边 A. n B. n（n-1） C. n（n-1）/2 D. 2n19-4任何一个无向连通图的最小生成树_ A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在答案：B、D、C、B20一组记录的关键字为（46，79，56，38，40，84）；利用快速排序的方法，以第一个记录为基准得到的一次划分结果为_A. 38, 49, 46, 56, 79, 84 B.40, 38, 46,

6、 79, 56, 84C. 40, 38, 46, 56, 79, 84 D. 40, 38, 46, 84, 56, 79答案：C21答案：B、C、B22答案：23答案：24从空树开始，逐个读入并插入下列关键字，构造一棵二叉排序树：（24，88，42，97，22，15，7，13）。答案：25对长度为8的有序表，给出折半查找的判定树，给出等概率下的平均查找长度。答案：ASL=21/826答案：27答案：D28答案：29答案：30答案：31答案：32答案：32用Dijkstra算法思想计算源点A到各顶点的最短路径。答案：33快速排序的基本思想是什么？答案：34试用下列三种表示法画出图1所示图G的存储结