试题一
一、单项选择题（每小题 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）该二叉树结点的前序遍历的序列为（  　）。
A）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）该二叉树结点的中序遍历的序列为（  　）。
A）A、B、C、D、E、G、F            B）E、A、G、C、F、B、D
C）E、A、C、B、D、G、F         D）B、D、C、A、F、G、E                                             
（8）该二叉树的按层遍历的序列为（  　）。
A）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。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。