离线作业二

一、单项选择题（每小题 2 分，共20分）

（1）设Huffman树的叶子结点数为m，则结点总数为（　）。

A）2m B）2m-1

C）2m+1 D）m+1

（2）若顺序存储的循环队列的QueueMaxSize=n，则该队列最多可存储（　）个元素。

A）n B）n-1 C）n+1 D）不确定

（3）下述哪一条是顺序存储方式的优点？（　　　）

A）存储密度大 B）插入和删除运算方便

C）获取符合某种条件的元素方便 D）查找运算速度快

（4）设有一个二维数组A[m][n]，假设A[0][0]存放位置在600(10)，A[3][3]存放位置在678(10)，每个元素占一个空间，问A[2][3](10)存放在什么位置？（脚注(10)表示用10进制表示，m>3）（　　　）。

A）658 B）648 C）633 D）653

（5）下列关于二叉树遍历的叙述中，正确的是（　　　）。

A）若一个叶子是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点

B）若一个结点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点

C）若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点

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，77，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[-1:3,0:6,-2:3]，按行为主序存放在2000开始的连续空间中，如元素的长度是5，试计算出A[1,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

后序： c,b,e,f,d,a

按层： a,b,d,c,e,f

遍历序列为：abedc。

三、（本题8分）

树的遍历方法有先根序遍历和后根序遍历，它们分别对应于把树转变为二叉树后的先序遍历与中序遍历方法。

四、（本题8分）

A[1,1,1]的存储位置=2000+((1-(-1))*(6-0+1)*(3-(-2)+1)+(1-0)*(3-(-2)+1)+(1-(-2)))*5=2465。

五、（本题8分）

六、（本题15分）

本题只要在遍历二叉树的过程序中对叶子结点进行记数即可。

long LeafCount(BiTree T)

// 计算二叉树中叶子结点数目

{

if(T==NULL)

return 0; //空树返回0

else if(T->lchild==NULL&&T->rchild==NULL)

return 1; //只有一个结点的树返回1

else

//叶子结点数为左右子树的叶子结点数之和

return LeafCount(T->lchild)+LeafCount(T->rchild);

}