资源描述：
《数据结构与算法分析-六套期末复习题.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、试题一一、单项选择题（每小题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
2、）读取队头元素的值（4）字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（ ）个不同的字符串。A）14B）5 C）6 D）8（5）由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（ ）。A）11B）35C）19D）53以下6-8题基于下图：（6）该二叉树结点的前序遍历的序列为（ ）。A）E、G、F、A、C、D、BB）E、A、G、C、F、B、DC）E、A、C、B、D、G、FD）E、G、A、C、D、F、B（7）该二叉树结点的中序遍历的序列为（ ）。A）A、B、C、D、E、G、FB
3、）E、A、G、C、F、B、DC）E、A、C、B、D、G、FD）B、D、C、A、F、G、E（8）该二叉树的按层遍历的序列为（ ）。A）E、G、F、A、C、D、BB）E、A、C、B、D、G、FC）E、A、G、C、F、B、DD）E、G、A、C、D、F、B（9）下面关于图的存储的叙述中正确的是（ ）。A）用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B）用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关C）用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关D）用邻接矩阵法存储图，占用的存储空间
4、大小只与图中边数有关，而与结点个数无关（10）设有关键码序列(q,g,m,z,a,n,p,x,h)，下面哪一个序列是从上述序列出发建堆的结果?（ ）A）a,g,h,m,n,p,q,x,zB）a,g,m,h,q,n,p,x,zC）g,m,q,a,n,p,x,h,zD）h,g,m,p,a,n,q,x,z二、（本题8分）对于序列{8,18,6,16,29,28}，试写出堆顶元素最小的初始堆。三、（本题8分）一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出空格处的内容，并画出该二叉树。先序序列：BFICEHG中序序列：DK
5、FIAEJC后序序列：KFBHJGA四、（每小题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分）所构造的堆如下图
6、所示：三、（本题8分）在先序序列空格中依次填ADKJ，中序中依次填BHG，后序中依次填DIEC。四、（每小题2分，共8分）（1）二叉排序树如下图所示：（2）哈夫曼树如下图所示：（3）平衡二叉树如下图所示：（4）对于增量d=2按降序执行一遍希尔排序的结果：28,80,27,24,23五、（本题15分）从上图来看，二叉树的第一层显示在第一列，第二层显示在第二列，第三层显示在第三列；每行显示一个结点，从上至下是先显示右子树，再显示根，最后最左子树，也就是以先遍历右子树，最后遍历左子树的中序遍历次序显示各结点。C语言版测试程序见exam110c，具
7、体算当如下：voidDisplayBTWithTreeShape(BiTreeT,intlevel=1)//按树状形式显示二叉树，level为层次数，可设根结点的层次数为1{if(T){//空树不显式，只显式非空树DisplayBTWithTreeShape(T->rchild,level+1);//显示右子树cout<data;//显示结点DisplayBTWithTreeShape(T->lchil
8、d,level+1);//显示左子树}}==============================================================
