数据结构试卷.pdfVIP

数据结构试卷--第1页

数据结构试卷（A）

一、填空题（每空1分，1*20）

1、在二叉树的第i层上至多有()个结点，深度为k的二叉树至多有()个结点，任何一棵二叉树

中，度为2的结点个数为n则叶子结点个数为()。

2、队列是一种限定()的线性表，它只允许在表的一端插入，在另一端删除，允许插入的一端叫()，

允许删除的一端叫做()。

3、N个结点的连通图至多有()条边，至少有()条边。

4、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为，所有

顶点邻接表中的结点总数为()。

5、若一个广义表为（a，（a，b），d，e，（（i，j），k）），则该表深度为（），而表长度为（）。

6、锦标赛排序的时间复杂度为()从稳定性上讲是一个()的排序方法。堆排序的时间复杂度为()

是一个()（稳定或不稳定）的排序方法。

7、在结点为N的各棵树中，高度最小的树的高度为()，它有()个叶结点，高度最大的树的高度

是()，它有()个叶子结点。

二、判断题（正确为T，错误为F，每小题2分，共10分）

1、数据结构、数据元素和数据项在计算机中的映像分别为存储结构、结点和数据域。

（）

2、顺序表和单链表都是随机存取的线性存储结构。（）

3、两棵具有相同关键字集合而形状不同的二叉排序树，按中序遍历得到的序列顺序是相同的。

（）

4、在任何情况下归并排序都比直接插入排序快。（）

5、拓扑排序就是从某个集合的偏序得到该集合的一个全序。（）

三、选择题（每题2分，共10分）

1、若循环链表的结点具有数据域data和指针域next，H指向其头结点，该表具有一个元素结点

的条件是（）为真值。

A.H==H-nextB.H==H-next-nextC.H-nextD.!(H-next)

2、折半查找算法的时间复杂度是（）。

A.O(n2)B.O(n)C.O(nlog2n)D.O(log2n)

3、m阶B树中的m是指（）。

A.每个结点至少有m棵子树B.非终端结点中关键字的个数

C.每个结点至多有m棵子树D.m阶B树的深度（或高度）

数据结构试卷--第1页

数据结构试卷--第2页

4、三个结点的二叉树的形态有（）种

A.3B.4C.5D.6

5、采用链表方式表示一个栈，栈顶结点的插入与删除能在链表的（）进行

A.任意位置B.一端C.两端D.中间进行

四、画图及填空（每题5分，共15分）

1、将下列二叉树在顺序存储结构A[0..15]中存放。

2、已知一棵二叉树的前序遍历的结果是ABCEDFGHIJ，中序遍历结果是BECADFHIGJ，试画

出这棵二叉树，并写出它的后序遍历结果。

3、画出广义表L=((()),a,((b,c),(),d),(((e))))的存储结构图。

五、应用题（45分）

下面的算法是将整形数组A[0..n-1]中的元素划分为两部分，使得左边元素均为奇数，右边元素均

为偶数，请在＿＿中填入恰当的语句，完成本算法。（10分）

voidPartition(intA[])

{i=0;j=n-1;

while＿＿＿＿

{while(ij＿＿＿＿)i++;

while(ij＿＿＿＿)j++;

if(ij)＿＿＿＿;

}