数据结构期终复习精选.doc

一、单项选择题（每小题 2 分，共20分） （1）以下数据结构中哪一个是线性结构？（　　　） A）有向图 　　 B）队列 C）线索二叉树 　　 D）B树 （2）在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下（　　　）语句序列。 A）p=q; p-next=q; B）p-next=q; q-next=p; C）p-next=q-next; p=q; D）q-next=p-next; p-next=q; （3）（　　　）不是队列的基本运算。 A）在队列第i个元素之后插入一个元素 B）从队头删除一个元素 C）判断一个队列是否为空 D）读取队头元素的值 （4）字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（　　　）个不同的字符串。 A）14 B）5 　　 C）6 　　 D）8 （5）由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（　　　）。 A）11 B）35 C）19 D）53 以下6-8题基于下图： （6）该二叉树结点的前序遍历的序列为（　　　）。 E、G、F、A、C、D、B B）E、A、G、C、F、B、D C）E、A、C、B、D、G、F D）E、G、A、C、D、F、B （7）该二叉树结点的中序遍历的序列为（　　　）。 AE、A、G、C、F、B、D C）E、A、C、B、D、G、F D）B、D、C、A、F、G、EA）E、G、F、A、C、D、B B）E、A、C、B、D、G、F C）E、A、G、C、F、B、D D）E、G、A、C、D、F、B （9）下面关于图的存储的叙述中正确的是（　　　）。 A B）用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C）用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D）用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 （10）设有关键码序列(q,g,m,z,a,n,p,x,h)，下面哪一个序列是从上述序列出发建堆的结果?（　　　） A）a,g,h,m,n,p,q,x,z B）a,g,m,h,q,n,p,x,z C）g,m,q,a,n,p,x,h,z D）h,g,m,p,a,n,q,x,z 六、（本题8分） 对于序列{8,18,6,16,29,28}，试写出堆顶元素最小的初始堆。 七、（本题8分） 一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出空格处的内容，并画出该二叉树。 先序序列： B F ICEH G 中序序列：D KFIA EJC 后序序列： K FBHJ G A 八、（每小题2分，共8分） 设有序列：w={23,24,27,80,28}，试给出： （1）二叉排序树； （2）哈夫曼树； （3）平衡二叉树； （4）对于增量d=2按降序执行一遍希尔排序的结果。 十、（本题15分） 假设二叉树中每个结点所含数据元素均为单字母，以二叉链表为存储结构，试编写算法按如下图所示的树状显示二叉树。 一、单项选择题 （1）B （2）D （3）A （4）B （5）B （6）C （7）A （8）C （9）B （10）B 六、（本题8分） 所构造的堆如下图所示： 七、（本题8分） 在先序序列空格中依次填ADKJ，中序中依次填BHG，后序中依次填DIEC。 八、（每小题2分，共8分） （1）二叉排序树如下图所示： （2）哈夫曼树如下图所示： （3）平衡二叉树如下图所示： （4）对于增量d=2按降序执行一遍希尔排序的结果：28,80,27,24,23 十、（本题15分） 从上图来看，二叉树的第一层显示在第一列，第二层显示在第二列，第三层显示在第三列；每行显示一个结点，从上至下是先显示右子树，再显示根，最后最左子树，也就是以先遍历右子树，最后遍历左子树的中序遍历次序显示各结点。 C语言版测试程序见exam1\10c，具体算当如下： void DisplayBTWithTreeShape(BiTree T,int level=1) // 按树状形式显示二叉树，level为层次数，可设根结点的层次数为1 { if(T) { //空树不显式，只显式非空树 DisplayBTWithTreeShape(T-rchild,level+1); //显示右子树 coutendl; //显示新行 for(int i=0;ilevel-1;i++)