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）读取队头元素的值（4）字符 A、B
2、、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、DC）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、DC）E、A、C、B、D、G、F D）B、D、C
3、 、A、F、G、E （8）该二叉树的按层遍历的序列为（ ）。A）E、G、F、A、C、D、B B）E、A、C 、B、D、G 、FC）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)，下面哪一个序
4、列是从上述序列出发建堆的结果? （ ）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）二叉
5、排序树；（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）平衡二叉树如
6、下图所示：（4）对于增量 d=2 按降序执行一遍希尔排序的结果：28,80,27,24,23五、 （本题 15 分）从上图来看，二叉树的第一层显示在第一列，第二层显示在第二列，第三层显示在第三列；每行显示一个结点，从上至下是先显示右子树，再显示根，最后最左子树，也就是以先遍历右子树，最后遍历左子树的中序遍历次序显示各结点。C 语言版测试程序见 exam110c，具体算当如下：void DisplayBTWithTreeShape(BiTree T,int level=1)/ 按树状形式显示二叉树，level 为层次数，可设根结点的层次数为 1if(T) /空树不显式，只显式非空树Display
7、BTWithTreeShape(T-rchild,level+1);/显示右子树coutdata; /显示结点DisplayBTWithTreeShape(T-lchild,level+1); /显示左子树=试 题 二一、单项选择题（每小题 2 分，共 20 分）（1）设 Huffman 树的叶子结点数为 m，则结点总数为（ ）。A）2m B）2m-1C）2m+1 D）m+1（2）若顺序存储的循环队列的 QueueMaxSize=n，则该队列最多可存储（ ）个元素。A）n B）n-1 C）n+1 D）不确定（3）下述哪一条是顺序存储方式的优点？（ ）A）存储密度大 B）插入和删除运算方便 C）
8、获取符合某种条件的元素方便 D）查找运算速度快（4）设有一个二维数组 Amn，假设 A00存放位置在 600(10)，A33存放位置在678(10)，每个元素占一个空间，问 A23(10)存放在什么位置？（脚注(10)表示用 10 进制表示，m3）（ ）。A）658 B）648 C）633 D）653（5）下列关于二叉树遍历的叙述中，正确的是（ ）。A）若一个叶子是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点B）若一个结点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点C）若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序
9、最后一个结点D）若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点（6）k 层二叉树的结点总数最多为（ ）。A）2k-1 B）2k+1 C）K-1 D）k-1（7）对线性表进行二分法查找，其前提条件是（ ）。A）线性表以链接方式存储，并且按关键码值排好序 B）线性表以顺序方式存储，并且按关键码值的检索频率排好序C）线性表以顺序方式存储，并且按关键码值排好序D）线性表以链接方式存储，并且按关键码值的检索频率排好序（8）对 n 个记录进行堆排序，所需要的辅助存储空间为（ ）。A）O(1og2n) B）O(n) C）O(1) D）O(n2)（9）对于线性表（7 ，34，7
10、7，25 ，64，49 ，20，14）进行散列存储时，若选用 H（K）=K%7 作为散列函数，则散列地址为 0 的元素有（ ）个。A）1 B）2 C）3 D）4（10）下列关于数据结构的叙述中，正确的是（ ）。A）数组是不同类型值的集合 B）递归算法的程序结构比迭代算法的程序结构更为精炼C）树是一种线性结构D）用一维数组存储一棵完全二叉树是有效的存储方法二、（本题 8 分）假定一棵二叉树广义表表示为 a(b(c),d(e,f)，分别写出对它进行先序、中序、后序、按层遍历的结果。三、（本题 8 分）树有哪些遍历方法？它们分别对应于把树转变为二叉树的哪些遍历方法？四、（本题 8 分）设有数组 A-
11、1:3,0:6,-2:3，按行为主序存放在 2000 开始的连续空间中，如元素的长度是 5，试计算出 A1,1,1的存储位置。五、（本题 8 分）设有一个输入数据的序列是 46, 25, 78, 62, 12, 80 , 试画出从空树起，逐个输入各个数据而生成的二叉搜索树。六、（本题 15 分）以二叉链表作存储结构，试编写计算二叉树中叶子结点数目的递归算法。【答案】=一、单项选择题（每小题 2 分，共 20 分）（1）B （2）B （3）A （4）D （5）A （6）A （7）C （8）C （9）D （10）D二、（本题 8 分）先序： a,b,c,d,e,f 中序： c,b,a,e,d,f
12、后序： c,b,e,f,d,a 按层： a,b,d,c,e,f 遍历序列为：abedc。三、（本题 8 分）树的遍历方法有先根序遍历和后根序遍历，它们分别对应于把树转变为二叉树后的先序遍历与中序遍历方法。四、（本题 8 分）A1,1,1的存储位置=2000+(1-(-1)*(6-0+1)*(3-(-2)+1)+(1-0)*(3-(-2)+1)+(1-(-2)*5=2465。五、（本题 8 分）六、（本题 15 分）本题只要在遍历二叉树的过程序中对叶子结点进行记数即可。C 语言版测试程序见 exam210c，具体算当如下：long LeafCount(BiTree T)/ 计算二叉树中叶子结点数
13、目if(T=NULL)return 0; /空树返回 0else if(T-lchild=NULL /只有一个结点的树返回 1else/叶子结点数为左右子树的叶子结点数之和return LeafCount(T-lchild)+LeafCount(T-rchild);试 题 三一、单项选择题（每小题 2 分，共 20 分）（1）对一个算法的评价，不包括如下（ ）方面的内容。A）健壮性和可读性 B）并行性 C）正确性 D）时空复杂度（2）在带有头结点的单链表 HL 中，要向表头插入一个由指针 p 指向的结点，则执行（ ）。A）p-next=HL-next; HL-next=p B）p-next=HL; HL=pC）p-next=HL; p=HL D）HL=p; p-next=HL（3）对线性表，在下列哪种情况下应当采用链表表示？（ ）A）经常需要随机地存取元素 B）经常需要进行插入和删除操作
