三、（本题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分）

本题只要在遍历二叉树的过程序中对叶子结点进行记数即可。 C语言版测试程序见exam2\\10c，具体算当如下：

long LeafCount(BiTree T) // { }

if(T==NULL) else

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

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

return 0;

//空树返回0

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

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

return 1;

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

试题三

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

（1）对一个算法的评价，不包括如下（ ）方面的内容。

A）健壮性和可读性 B）并行性 C）正确性 D）时空复杂度

（2）在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行（ ）。 A）p->next=HL->next; HL->next=p C）p->next=HL; p=HL

（3）对线性表，在下列哪种情况下应当采用链表表示？（ ） A）经常需要随机地存取元素

B）经常需要进行插入和删除操作

C）表中元素需要占据一片连续的存储空间 D）表中元素的个数不变

（4）一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是（ ）。 A）2 3 1

（5）每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（ ）。 A）冒泡排序 B）简单选择排序C）希尔排序 D）直接插入排序

（6）采用开放定址法处理散列表的冲突时，其平均查找长度（ ）。 A）低于链接法处理冲突 B）高于链接法处理冲突 C）与链接法处理冲突相同 D）高于二分查找

（7）若需要利用形参直接访问实参时，应将形参变量说明为（ ）参数。 A）值

B）函数 C）指针 D）引用

（8）在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（ ）。 A）行号 B）列号 C）元素值 D）非零元素个数

B）3 2 1

C）3 1 2

D）1 2 3

B）p->next=HL; HL=p D）HL=p; p->next=HL

（9）快速排序在最坏情况下的时间复杂度为（ ）。 A）O(log2n)

（10）从二叉搜索树中查找一个元素时，其时间复杂度大致为（ ）。 A）O(n) B）O(1) C）O(log2n) D）O(n2)

B）O(nlog2n)

C）O(n) D）O(n2)

二、（本题8分）

如果在1000000个记录中找出两个最小的记录，你认为采用什么样的排序方法所需的关键字比较次数最少？最多比较多少次？

三、（本题8分）

假设把n个元素的序列（a1,a2,…an）满足条件akaj(i

四、（每小题4分，共8分）

设内存有大小为6个记录的缓冲区供内排序使用，文件的关键字序列为

｛29,50,70,33,38,60,28,31,43,36,25,9,80,100,57,18,65,2,78,30,14,20,17,99），试列出： （1）用内排序求出初始归并段； （2）用置换一选择排序求初始归并段。

五、（本题9分）

已知关键字序列{23，13，5，28，14，25}，试构造二叉排序树。

六、（本题15分）

编写一个算法求二又树的深度。

【答案】==================================

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

（1）B （2）A （3）B （4）C （6）B （7）D （8）A （9）D （10）C

二、（本题8分）

采用树形选择排序方法所需的关键字比较次数最少，最多比较次数=999999+?（5）B

log21000000?=1000019次。

三、（本题8分）

不对，例如序列｛3、3、4、2、l｝的“逆序元素”个数是2，2和1是“逆序元素”；但是将第二个3和2交换后，成为｛3、2、4、3、l｝，此时“逆序元素”个数是3，2、3和1是“逆序元素”。然而交换后一定减少的是“逆序对”的个数，例如上例中｛3、3、4、2、l｝的逆序对的个数是 7，交换第二个 3和2后，｛3、2、4、3、1｝的逆序对的个数是6。

四、（每小题4分，共8分） （1）用内排序求出初始归并段为： 归并段1：29,33,38,50,60,70: 归并段2：9,25,28,31,36,43 归并段3：2,18,57,65,80,100:

归并段4：14,17,20,30,78,99.

（2）用置换一选择排序求初始归并段为： 归并段1：29,33,38,50,60,70,80,100 归并段2：9,18,25,28,31,36,57,65,78,99; 归并段3：2,14,17,20,30.

五、（本题9分）

构造二叉排序树的过程如下图所示。