2010年数据结构试题集（10套题并附带答案）

2010年数据结构考试复习资料-杀虫剂

(A) 40，42，45，55，80，83 85，88

(B) 42，40，45，80，

for(exchange=0,j=0;

j<_____________;j++)

if

(r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;}

if (exchange==0) return； } }

10. 下面程序段的功能是实现二分查找算法，请在

下划线处填上正确的语句。 struct record{int key; int others;}; int bisearch(struct record r[ ], int k) {

int low=0,mid,high=n-1; while(low<=high) {

________________________________; if(r[mid].key==k) } return(0); }

三、应用题(32分) 1.

设某棵二叉树的中序遍历序列为DBEAC，前序遍历序列为ABDEC，要求给出该二叉树的的后序遍历序列。 2.

设无向图G（如右图所示），给出该图的最小生成树上边的集合并计算最小生成树各边上的权值之和。 3.

设一组初始记录关键字序列为(15，17，18，22，35，51，60)，要求计算出成功查找时的平均查找长度。 4.

设散列表的长度为8，散列函数H(k)=k mod 7，初始记录关键字序列为(25，31，8，27，13，68)，要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。

四、算法设计题(28分)

1． 设计判断两个二叉树是否相同的算法。 2． 设计两个有序单链表的合并排序算法。

return(mid+1);

else

if(____________) high=mid-1;else low=mid+1;

(C) 42，40，45，55，80，85 55，80

(D) 42，40，45，85，

二、填空题(共20分) 1.

设有一个顺序共享栈S[0：n-1]，其中第一个栈项指针top1的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是____________________。 2. 3.

在图的邻接表中用顺序存储结构存储表头结点的优点是____________________。 设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_______个数据元素。 4.

栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为__________表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为_________表。 5.

设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为___________，中序遍历序列为___________，后序遍历序列为___________。 6.

设一棵完全二叉树有128个结点，则该完全二叉树的深度为________，有__________个叶子结点。 7.

设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数之和等于顶点i的________，第i列中所有非零元素个数之和等于顶点i的__________。 8.

设一组初始记录关键字序列(k1，k2，??，kn)是堆，则对i=1，2，?，n/2而言满足的条件为_______________________________。 9.

下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。 void bubble(int r[n]) {

for(i=1;i<=n-1; i++) {

数据结构试卷（六）

- 8 -

2010年数据结构考试复习资料-杀虫剂

一、选择题(30分)

1． 设一组权值集合W={2，3，4，5，6}，则由该

权值集合构造的哈夫曼树中带权路径长度之和为（ ）。

(A) 20 (C) 40

(B) (D) 45

30

变量s指向将要入队列的结点X，则入队列的操作序列为（ ）。 (A) (C)

front->next=srear->next=s

；；

front=srear=s

；；

(B) s->next=rear；rear=s； (D) s->next=front；front=s；

12.设某无向图中有n个顶点e条边，则建立该图

邻接表的时间复杂度为（ ）。

(A) O(n+e) (C) O(ne)

(B) (D) O(n)

3

2．执行一趟快速排序能够得到的序列是（ ）。

(A) [41，12，34，45，27] 55 [72，63] (B) [45，34，12，41] 55 [72，63，27] (C) [63，12，34，45，27] 55 [41，72] (D) [12，27，45，41] 55 [34，63，72]

O(n)

2

13.设某哈夫曼树中有199个结点，则该哈夫曼树

中有（ ）个叶子结点。

(A) 99

(B) head->next==0 (C) 101

(B) (D) 102

100

3．设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（ ）。

(A) head==0

(C) head->next==head (D) head!=0 4．时间复杂度不受数据初始状态影响而恒为

O(nlog2n)的是（ ）。

(A) 堆排序 (C) 希尔排序

(B)

冒

泡

排

序

(D) 快速排序

14.设二叉排序树上有n个结点，则在二叉排序树

上查找结点的平均时间复杂度为（ ）。 (A) O(n) (C) O(nlog2n)

(B)

(D) O(1og2n)

O(n)

2

15.设用邻接矩阵A表示有向图G的存储结构，则

有向图G中顶点i的入度为（ ）。

点

子

二、判断题(20分)

1．调用一次深度优先遍历可以访问到图中的所有

顶点。（ ）

2．分块查找的平均查找长度不仅与索引表的长度

有关，而且与块的长度有关。（ ）

3．冒泡排序在初始关键字序列为逆序的情况下执

行的交换次数最多。（ ）

4．满二叉树一定是完全二叉树，完全二叉树不一

定是满二叉树。（ ）

5．设一棵二叉树的先序序列和后序序列，则能够

O(n)

2

5．设二叉树的先序遍历序列和后序遍历序列正好

相反，则该二叉树满足的条件是（ ）。

(A) (C)

空任

或一

只结

有点

一无

个左

结孩

(B) 高度等于其结点数 (D) 任一结点无右孩子 其最终位置上的是（ ）。

(A) 堆排序 (C) 快速排序

(B)

冒

泡

排

序

(D) 希尔排序

(A) 第i行非0元素的个数之和 (B) 第i列非0元素的个数之和 (C) 第i行0元素的个数之和 元素的个数之和

(D) 第i列0

6．一趟排序结束后不一定能够选出一个元素放在

7．设某棵三叉树中有40个结点，则该三叉树的最小高度为（ ）。

(A) 3 (C) 5

(B) (D) 6

4

8．顺序查找不论在顺序线性表中还是在链式线性

表中的时间复杂度为（ ）。

(A) O(n) (C) O(n) (A) O(n) (C) O(nlog2n) (A) 2-1 (C) 2+1

k-1k-1

1/2

(B)

(D) O(1og2n) (B)

(D) O(1og2n) (B) (D) 2-1

k

唯一确定出该二叉树的形状。（ ）

6．层次遍历初始堆可以得到一个有序的序列。（ ） 7．设一棵树T可以转化成二叉树BT，则二叉树BT

9．二路归并排序的时间复杂度为（ ）。

O(n)

2

中一定没有右子树。（ ）

8．线性表的顺序存储结构比链式存储结构更好。

（ ）

9．中序遍历二叉排序树可以得到一个有序的序列。

（ ）

10.快速排序是排序算法中平均性能最好的一种排

序。（ ）

- 9 -

10. 深度为k的完全二叉树中最少有（ ）个结点。

2

k-1

11.设指针变量front表示链式队列的队头指针，

指针变量rear表示链式队列的队尾指针，指针

2010年数据结构考试复习资料-杀虫剂

三、填空题(30分)

1．for(i=1，t=1，s=0；i<=n；i++) {t=t*i；s=s+t；}

的时间复杂度为_________。

2．设指针变量p指向单链表中结点A，指针变量s

指向被插入的新结点X，则进行插入操作的语句序列为__________________________（设结点的指针域为next）。

3．设有向图G的二元组形式表示为G =（D，R），

D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，则给出该图的一种拓扑排序序列__________。

4．设无向图G中有n个顶点，则该无向图中每个

顶点的度数最多是_________。

5．设二叉树中度数为0的结点数为50，度数为1

的结点数为30，则该二叉树中总共有_______个结点数。

6．设F和R分别表示顺序循环队列的头指针和尾

指针，则判断该循环队列为空的条件为_____________________。

7．设二叉树中结点的两个指针域分别为lchild和

rchild，则判断指针变量p所指向的结点为叶子结点的条件是

_____________________________________________。

8．简单选择排序和直接插入排序算法的平均时间

复杂度为___________。

9．快速排序算法的空间复杂度平均情况下为

__________，最坏的情况下为__________。 10.散列表中解决冲突的两种方法是

_____________和_____________。

四、算法设计题(20分)

１． 设计在顺序有序表中实现二分查找的算法。 ２． 设计判断二叉树是否为二叉排序树的算法。 ３． 在链式存储结构上设计直接插入排序算法

一、选择题(30分)

1．设某无向图有n个顶点，则该无向图的邻接表

中有（ ）个表头结点。

(A) 2n (C) n/2

(B) (D) n(n-1)

n

2．设无向图G中有n个顶点，则该无向图的最小

生成树上有（ ）条边。

(A) n (C) 2n

(B) (D) 2n-1

n-1

3．设一组初始记录关键字序列为(60，80，55，40，

42，85)，则以第一个关键字45为基准而得到的一趟快速排序结果是（ ）。

(A) 40，42，60，55，80，85 (B) 42，45，55，60，85，80

(C) 42，40，55，60，80，85 (D) 42，40，60，85，55，80

4．（ ）二叉排序树可以得到一个从小到大的有序

序列。

(A) 先序遍历 (C) 后序遍历

(B)

中

序

遍

历

(D) 层次遍历

5．设按照从上到下、从左到右的顺序从1开始对

完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（ ）。

(A) 2i+1 (C) i/2

(B) (D) 2i-1

2i

6．程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；

的时间复杂度为（ ）。

(A) O(n) (C) O(n)

2

(B) (D) O(n/2)

3

O(nlog2n)

7．设带有头结点的单向循环链表的头指针变量为

head，则其判空条件是（ ）。

(A) head==0 (B) head->next==0

(C) head->next==head (D) head!=0 结点最多有（ ）。

(A) 20 (C) 512

(B) (D) 1024

256

8．设某棵二叉树的高度为10，则该二叉树上叶子

数据结构试卷（七）

9．设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（ ）。

(A) 1 (C) 3

(B) (D) 4

2

- 10 -

2010年数据结构考试复习资料-杀虫剂

10.设指针变量top指向当前链式栈的栈顶，则删

除栈顶元素的操作序列为（ ）。

二、判断题(20分)

1．不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（ ） 2．当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（ ）

3．设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。（ ）

4．完全二叉树中的叶子结点只可能在最后两层中出现。（ ）

5．哈夫曼树中没有度数为1的结点。（ ） 6．对连通图进行深度优先遍历可以访问到该图中

的所有顶点。（ ）

7．先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（ ）

8．由树转化成二叉树，该二叉树的右子树不一定为空。（ ）

9．线性表中的所有元素都有一个前驱元素和后继元素。（ ）

10.带权无向图的最小生成树是唯一的。（ ）

三、填空题(30分)

1. 设指针变量p指向双向链表中的结点A，指针

变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为_________=p；s->right=p->right

；

__________=s

；

p->right->left=s；（设结点中的两个指针域分别为left和right）。

2. 设完全有向图中有n个顶点，则该完全有向图

中共有________条有向条；设完全无向图中有n个顶点，则该完全无向图中共有________条无向边。

3. 设关键字序列为(Kl，K2，?，Kn)，则用筛选

法建初始堆必须从第______个元素开始进行筛选。

4. 解决散列表冲突的两种方法是

________________和__________________。 5. 设一棵三叉树中有50个度数为0的结点，21

个度数为2的结点，则该二叉树中度数为3的结点数有______个。 (A) top=top+1; (B) top=top-1;

(C) top->next=top; (D) top=top->next;

6. 高度为h的完全二叉树中最少有________个

结点，最多有________个结点。

7. 设有一组初始关键字序列为(24，35，12，27，

18，26)，则第3趟直接插入排序结束后的结果

的

是

__________________________________。 8. 设有一组初始关键字序列为(24，35，12，27，

18，26)，则第3趟简单选择排序结束后的结果

的

是

__________________________________。 9. 设一棵二叉树的前序序列为ABC，则有

______________种不同的二叉树可以得到这种序列。

10. 下面程序段的功能是实现一趟快速排序，请在

下划线处填上正确的语句。 struct record {int key;datatype others;};

void quickpass(struct record r[], int s, int t, int &i)

{

int j=t; struct record x=r[s]; i=s; while(i

while (ix.key) j=j-1; if (i

while (____________________) i=i+1; if (i

}

_________________; }

四、算法设计题(20分) 1. 2. 3.

设计在链式结构上实现简单选择排序算法。 设计在顺序存储结构上实现求子串算法。 设计求结点在二叉排序树中层次的算法。

数据结构试卷（八）

一、选择题(30分) 1.

字符串的长度是指（ ）。

(A) 串中不同字符的个数(B) 串中不同字母的个数

(C) 串中所含字符的个数(D) 串中不同数字的个数

- 11 -