数据结构复习题

选择

1、线性结构是数据元素之间存在一种（）

A．一对多关系 B、多对多关系C、多对一关系 D、一对一关系2、树结构是数据元素之间存在一种（）

A．一对多关系 B、多对多关系C、多对一关系 D、一对一关系3、从逻辑上可以把数据结构分为（）两大类。

A．动态结构、静态结构 B．顺序结构、链式结构

C．线性结构、非线性结构 D．初等结构、构造型结构

4、设语句x++的时间是单位时间，则语句：

for(I=1;I<=n;I++)

x++;

时间复杂度为（）

A、O（1）

B、O（n）

C、O（n2）

D、O（n3）

5、下面关于线性表的叙述中，错误的是哪一个？（）

A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

6、下列说法错误的是（）

A、求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低。

B、顺序存储的线性表可以随机存取。

C、由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活。

D、线性表的链式存储结构优于顺序存储结构。

7、设有一个顺序栈S，元素A,B,C,D,E,F,依次进栈，如果六个元素出栈的顺序

是B，D，C，F，E，A，则栈的容量至少应是 ( )。

A、3

B、4

C、5

D、 6

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

A. 2 3 4 1 5

B. 5 4 1 3 2

C. 2 3 1 4 5

D. 1 5 4 3 2

9、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别

为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front 的值分别为多少？( )

A、1和 5

B、2和4

C、4和2

D、5和1

10、若串S=’software’,其子串的数目是（）。

A．8 B．9 C．36 D．37

11、按二叉树的定义，具有3个结点的二叉树有( ) 种。

A、3

B、4

C、5

D、6

12、对一个满二叉树，m个树叶，n个结点，深度为h,则（）。

A、n = h + m

B、 h + m = 2n

C、 m = h -1

D、 n = 2h– 1

13、有8个结点的无向图最多有( ) 条边。

A．14 B．28 C．56 D．112

14、已知串a=‘JING’,b=‘BEIJING’, 则a在b中的位置是（）。

A、1

B、 3

C、4

D、 5

15、适用于折半查找的表的存储方式及元素排列要求为( )。

A．链接方式存储，元素无序 B．链接方式存储，元素有序

C．顺序方式存储，元素无序 D．顺序方式存储，元素有序。

16、假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（）个。

A、 15

B、 16

C、 17

D、 47

17、已知图的表示如下，若从顶点a出发按深度搜索法进行遍历，则可能得到

的一种顶点序列为（）。

A、abecdf

B、acfebd

C、aebcfd

D、aedfcb

18、对有14个数据元素的有序表R[14]（假设下标从1开始）进行二分查找，

搜索到R[4]的关键码等于给定值，此时元素比较顺序依次为（）。

A、R[1]，R[2]，R[3]，R[4]

B、R[1]，R[13]，R[2]，R[3]

C、R[7]，R[3]，R[5]，R[4]

D、R[7]，R[4]，R[2]，R[3]

19、下面给出的四种排序法中( )排序法是不稳定性排序法。

A. 堆

B. 冒泡

C. 二路归并

D. 插入

1、在双向链表结构中，若要求在p 指针所指的结点之前插入指针为s 所指的结点，则需执行下列语句：

s->next=p； s->prior= ；p->prior=s； =s；

1、已知一棵二叉树先序遍历序列、中序遍历序列（1）画出这棵二叉树。（2）画出这棵二叉树的后序线索树。

2、克鲁斯卡尔算法从顶点0开始求最小生成树，画出按次序产生最小生成树的过程。

3、广度优先遍历。

4、已知关键字序列（19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79）,哈希函数为H(key)=key mod 13, 采用链地址法处理冲突，构造出哈希表并给构造过程，并求平均查找长度ASL。

5、设哈希函数H（k）=K mod 11，有9个数据{19, 01, 23, 14, 55, 68, 11, 82, 36}，将它们存储在如下表长为11的哈希表中，发生冲突时利用线性再散列解

d取5）。写出试写出以第一个记录为枢轴进行快速排序的过程及结果（即只写完成第一趟排序的过程和结果）。

编程

1、利用C语言定义一个顺序存储线性表结构体，实现线性表的初始化、插入和遍历三种操作。。

3、写出深度优先遍历算法。

4、常用排序方法。