全国2005年1月数据结构导论真题

一、单项选择题(本大题共15小题，每小题2分，共30分)

1.数据的四种基本逻辑结构是指( )

A.数组、链表、树、图形结构 B.线性表、链表、栈队列、数组广义表

C.线性结构、链表、树、图形结构 D.集合、线性结构、树、图形结构

2.数据结构中，通常采用两种方法衡量算法的时间复杂性，即( )

A.最大时间复杂性和最小时间复杂性

B.最好时间复杂性和最坏时间复杂性

C.部分时间复杂性和总体时间复杂性

D.平均时间复杂性和最坏时间复杂性

3.下列关于线性表的叙述中，不正确的是( )

A.线性表是n个结点的有穷序列

B.线性表可以为空表

C.线性表的每一个结点有且仅有一个前趋和一个后继

D.线性表结点间的逻辑关系是1:1的联系

4.在一个单链表中，若p所指结点不是最后结点，则删除p所指结点的后继结点的正确操作是( )

A.p=p->next B.p->next=p->next

C.p->next=p->next->next D.p->next=p

5.栈和队列( )

A.共同之处在于二者都是先进先出的特殊的线性表

B.共同之处在于二者都是先进后出的特殊的线性表

C.共同之处在于二者都只允许在顶端执行删除操作

D.没有共同之处

6.二维数组A［5］［6］采用按列为主序的存储方式，每个元素占3个存储单元，若A［0］［0］的存储地址是100，则A［4］［3］的存储地址是( )

A.127 B.142

C.150 D.157

7.深度为k的二叉树至多有( )

A.2k个结点 B.2k-1个结点

C.2k-1个结点 D.2k-1-1个结点

8.对于如图所示二叉树采用中根遍历，正确的遍历序列应为( )

A.ABCDEF B.ABECDF

C.CDFBEA D.CBDAEF

9.下面关于生成树的描述中，不正确的是( )

A.生成树是树的一种表现形式

B.生成树一定是连通的

C.生成树一定不含有环

D.若生成树顶点个数为n，则其边数一定为n-1

10.图的邻接表如下所示，从顶点V1出发采用深度优先搜索法遍历该图，则可能的顶点序列 是( )

A.V1V2V3V4V5 B.V1V2V3V5V4

C.V1V4V3V5V2 D.V1V3V4V5V2

11.下列查找方法中，不属于动态的查找方法是( )

A.二叉排序树法 B.平衡树法

C.散列法 D.斐波那契查找法

12.要解决散列引起的冲突问题，常采用的方法有( )

A.数字分析法、平方取中法

B.数字分析法、线性探测法

C.二次探测法、平方取中法

D.二次探测法、链地址法

13.用于外存储器的数据组织结构散列文件，主要适用于( )

A.顺序存取 B.随机存取

C.索引存取 D.以上三种都可以

14.堆排序属于一种选择排序，其时间复杂性为( )

A.O(1) B.O(nlog2n)

C.O(n) D.O(n2)

15.下列排序方法中，属于不稳定的排序方法是( )

A.直接插入排序法 B.冒泡排序法

C.基数排序法 D.归并排序法

二、填空题(本大题共13小题，每小题2分，共26分)

请在每小题的空格中填上正确答案。错填、不填均无分。

16.根据不同的描述方式，对数据的操作运算通常可分为加工型运算和__________两种基本类型。

17.数据结构中的算法，通常采用最坏时间复杂度和____________两种方法衡量其效率。

18.判断带头结点head的单链表为空的条件是___________。

19.若顺序表每个元素长度均为5，其中第一个元素的存储地址为30，则第6个元素的存储地址为___________。

20.若front和rear分别表示循环队列Q的头指针和尾指针，m0表示该队列的最大容量，则判断循环队列为满的条件是___________。

21.对于顺序存储结构的二维数组，通常采用___________两种存放方式存储数据元素。

22.若某二叉树的先根遍历序列为CEDBA，中根遍历序列为DEBAC，则其后根遍历序列为___________。

23.具有n个结点的完全二叉树，其深度为___________。

24.图主要采用___________两种存储结构存放。

25.索引顺序查找通常分两个阶段进行，首先采用顺序查找法或二分法确定所要查找的块，然后再用___________法在块中找到具体的元素值。

26.二叉排序树是一种特殊的有序表，若要保证输出序列其键值完全按递增排列，则应对二叉排序树采用___________法遍历。

27.文件常见的存储结构有顺序文件、链接文件、 索引文件和___________四种。

28.在各种内部排序中，占用存储空间较大的排序通常是___________排序。

三、应用题(本大题共5小题，每小题6分，共30分)

29.已知某二叉树的顺序存储结构如图所示，试画出该二叉树。

A

B

C

D

E

F

G

30.试用Prim算法构造下图的最小生成树，要求分步给出构造过程

31.已知散列函数为H(key)=key%7，散列表长度为7(散列地址空间为0..6)，待散列序列为：(25，48，32，50，68)。要求：

(1)根据以上条件构造一散列表，并用线性探测法解决有关地址冲突；

(2)若要用该散列表查找元素68，给出所需的比较次数。

32.已知一组键值序列为(38，64，73，52，40，37，56，43)，试采用快速排序法对该组序列作升序排序，并给出每一趟的排序结果。

33.已知一组键值序列(26，21，32，56，78，89，90)，试采用二路归并排序法对该组序列作升序排序，并给出每一趟的排序结果。

四、设计题(本大题共2小题，每小题7分，共14分)

34.试编写一算法，以完成在带头结点单链表L中第i个位置前插入元素X的操作。

35.二叉树是由所有度数不大于2的结点构成的一种特定树，若某结点度为2，则该结点有左右两个孩子，请编写算法计算一二叉树所有度数为2的结点个数。