数据结构与算法分析_六套期末复习题(含答案)(3)

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

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

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

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

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

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

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

B）O(1)

C）O(log2n)

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

（5）B

（6）B （7）D （8）A （9）D （10）C

二、（本题8分）

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

log21000000?

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

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

构造的二叉排序树如下图所示：

六、（本题15分）

若二叉树为空，深度为0；若二叉树不空，则二叉树的深度为左右子树深度的最大值加1。本题最简单算法是递归算法。

C语言版测试程序见exam3\\10c，具体算当如下：

int BiTreeDepth(BiTree T) // { }

if(T==NULL)

else {

int d_lsub,d_rsub;

d_lsub=BiTreeDepth(T->lchild); d_rsub=BiTreeDepth(T->rchild); //返回左右子树的深度最大值加1

//左子树的深度 //右子树的深度

return 0;

//空二叉树的深度为0

求二叉树的深度

return ((d_lsub>d_rsub)?d_lsub:d_rsub)+1; }

试题四

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

（1）以下数据结构中哪一个是线性结构？（ ） A）有向图

（2）若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（ ）存储方式最节省时间。 A）单链表

B）双链表

C）带头结点的双循环链表

D）单循环链表

（3）（ ）不是队列的基本运算。

A）在队列第i个元素之后插入一个元素 B）从队头删除一个元素 C）判断一个队列是否为空 D）读取队头元素的值

（4）字符A、B、C、D依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（ ）个不同的字符串？ A）15 B）14 C）16 D）21

（5）由权值分别为4,7,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（ ）。 A）11

以下6-8题基于下面的叙述：

若某二叉树结点的中序遍历的序列为A、B、C、D、E、F、G，后序遍历的序列为B、D、C、A、F、G、E。

B）37

C）19

D）53

B）栈 C）二叉树

D）B树