2024年4月30日发(作者：)

数据结构复习题

一、单项选择题

1．数据结构在计算机中的表示称为数据的（ ）。

A）存储结构 B）抽象结构 C）顺序结构 D）逻辑结构

2．对于下面程序段的时间复杂度为（ ）。

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

for(j=1;j<=i;j++)

x=x+1;

A）O(n) B）O(n2) C）O(n*i) D）O(n+i)

9．数据类型为（ ）。

A）数据项的集合 B）值的集合及定义在其上的一组操作的总称

C）数据元素的集合 D）关键字的集合

10．网状结构的特征是（ ）。

A）结

D）正确性、可读性、健壮性及确定性

12．在下列序列中，不是线性表的是（ ）。

A）('a','b','c') B）('AB','CD') C）('a',true,'c') D）(a,b,c,d)

13．线性链表中各链结点之间的地址（ ）。

A）必须连续 B）部分地址必须连续 C）不一定连续 D）连续与否无所谓

14．如某链表中最常用的操作是在最后一个结点后插入一个结点和删除最后一个结点，

则（ ）存储方式最节省运行时间。

A）单链表 B）带头结点的单链表 C）单循环链表 D）带头结点的双循环链表

15．在非空线性链表中由p所指的链结点后面插入一个由q所指的链结点的过程是依次

执行动作（ ）。

A）q->next=p;p->next=q; B）q->next=p->next;p->next=q

C）q->next=p->next;p=q; D）p->next=q;q->next=p;

16．线性表的顺序存储结构具有的特点是（ ）。

A）可直接随机访问任一元素 B）插入删除不需要移动元素

C）不必26．从一个具有头结点的单链表中查找数据元素值为x的结点时，在查找成功

的情况下，平均比较次数是（ ）。

A）n B）n/2 C）(n-1)/2 D）(n+1)/2

27．对于长度为n的顺序线性表进行删除元素操作，如删除每个元素的概率相同，则删

除一个元素移动元素的平均次数是（ ）。

A）n/2 B）(n-1)/2 C）(n+1)/2 D）Dn

28．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的

平均时间复杂度为（ ）。

A）

A）abed B）32lAB C）"abcABC" D）"21AB"

38．串是（ ）。

A）不少于一个字符的序列 B）有限个字符的序列

C）不少于一个字母的序列 D）任意个字母的序列

39．初始为空的堆栈中依次插入元素:f 、e、d、c、b、a以后，连续进行了3次删除操

作，此时的栈顶元素是（ ）。

A）c B）d C）b D）e

40．当矩阵非零元素的位置或个数经常变动时，采用（ ）存储结构更为恰当。

A）顺序表 B）三元组表 C）十字链表 D）广义表

41．一个三对角矩阵A

n

×

n

已按行压缩存储到一维数组B中，则B的长度至少为（ ）。

A）3n+1 B）3n C）3n-1 D）3n-2

42．广义表((a,b),(c,d))的表尾是( )。

A）(c,d) B）((c,d)) C）(d) D）d

43．设某二叉树前序为abdcef，中序为dbaecf，则此二叉树的后序为 ( )。

A）dbefca B）debfca C）dfebca D）dbfeca

44．设一棵二叉树中没有度为1的结点，已知叶子结点数为n，此树的结点数为（ ）。

A）2n+2 B）2n+1 C）2n D）2n-1

45．设二叉树中有n

2

个度为2的结点，n

1

个度为1的结点，n

0

个叶子结点，则此二叉树

中空指针域个数为（ ）。

A）n

0

+n

1

+n

2

B）n

2

+n

1

+2n

0

C）2n

2

+n

1

D）2n

0

+n

1

46．用权值分别为15，2，4，5的四个结点，构造出的哈夫曼树为（ ）。

47．由带权9、1、3、5、6的五个叶子结点生成的哈夫曼树的带权路径长度为（ ）。

A）50 B）60 C）52 D）65

48． A、B两个结点可以构成（ ）棵不等价的二叉树。

A）2 B）3 C）4 D）5

49．设哈夫曼树的叶结点数为n，则它的结点总数为（ ）。

A）2n-1 B）2n C）2n+1 D）不确定

50．采用邻接表存储的图按深度优先搜索方法进行遍历的算法类似于二叉树的

（ ）。

A）先序遍历 B）中序遍历 C）后序遍历 D）层次遍历

59．快速排序执行一遍之后，已经到位的元素个数是（ ）。

A）1 B）3 C）

n

4

D）

n

2

60．在下列算法中，操作时间不随文件的初始状态变化的排序算法是（ ）。

A）堆排序 B）折半插入排序 C）基数排序 D）快速排序

61．数据表中有10000个元素，如果仅需求出其中最大的10个元素，则采用（ ）

排序算法最节省时间。

A）快速排序 B）希尔排序 C）堆排序 D）直接选择排序

62．快速排序在最坏情况下时间复杂度是O(n

2

)，比（ ）的性能差。

A）堆排序 B）起泡排序 C）选择排序 D）直接插入排序

63．下列排序算法中，一趟结束后未必能选出一个元素放在其最终位置上的算法是（ ）。

A）快速排序 B）冒泡排序 C）树形选择排序 D）归并排序

64．若需在O(nlogn)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排

序方法是（ ）。

A）快速排序 B）堆排序 C）归并排序 D）直接插入排序

65．初始文件中有两个关键字相同的记录，通过不稳定的排序方法排序后，（ ）。

A）使得领先关系不发生变化 B）领先关系一定发生变化

C）两个位置都不会发生变化 D）领先关系可能发生变化

66．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，

用（ ）方法平均时间最少。

A）起泡排序 B）简单选择排序 C）Shell排序 D）堆排序

67．如

77．一组记录的排序码为(48,24,18,53,16,26,40)，采用冒泡排序法进行排序，则第一趟排

序需要进行记录交换的次数是（ ）。

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

78．在下列排序方式中，关键码比较次数与记录的初始排列无关的是（ ）。

A）直接选择排序 B）冒泡排序 C）堆排序 D）归并排序

79．倒排文件的最大优点是（ ）。

A）便于进行文件的归并 B）有利于文件的插入与删除

C）能大大地提高主关键字的查找速度 D）能大大地提高次关键字的查找速度

80．文件中可使用的数据的最小单位是（ ）。

A）记录 B）字符 C）数据项 D）数据元素

81．ISAM文件和VASM文件属于（ ）。

A）索引非顺序文件 B）索引顺序文件 C）顺序文件 D）散列文件

A）先序遍历 B）中序遍历 C）后序遍历 D）按层遍历

90．对于如下图所示的二叉树，后序遍历结果序列为（ ）。

A）A，B，C，D，E，F，G

C）D，F，B，A，C，G，E

91．已知某二叉树前序遍历序列为ABDCE，它可能的中序遍历序列为（ ）。

A）BDAEC B）BCADE C）CBADE D）BEACD

92．具有127个结点的完全二叉树其深度为（ ）。

A）8 B）7 C）6 D）5

93．有一棵非空的二叉树（假设第0层为根结点），其第i层上至多有（ ）个结点？

A）2

i

B）2

i

-1 C）2

i

+1 D）i

94．二叉树的先序遍历和中序遍历如下：

B）A，B，D，F，C，E，G

D）F，D，B，G，E，C，A

D={1,2,3,4}

S=={R}

R={<1,2>,<1,3>,<2,3>,<2,4>,<3,4>}

}

1

121．要借助栈由输入序列是输入1,2,3,…,n得到的输出序列为p

1

,p

2

,p

3

,…,p

n

(此输出序列

是输

试给出：

（1）G的邻接矩阵表示；

（2）从V

1

开始的深度优先遍历；

（3）从V

1

开始的广度优先遍历；

（4）从V

1

开始执行的普里姆（Prim）算法过程中所选边的序列。

172．对如图6-10所示的有向图G试给出：

（1）各顶点的入/出度；

（2）逆邻接表；

（3）强连通分量。

173．有如下数据结构的形式定义，试画出此结构的图形表示。（南方名校经典试题）

DS={D,S}，其中：

D={1,2,3,4}

S=={R}

R={<1,2>,<1,3>,<2,3>,<2,4>,<3,4>}

1

181．使用散列函数hashf(x)=x MOD 11，把一个整数值转换成散列表下标，现要把数据

1、13、12、34、38、33、27、22插入到散列表中。

（1）使用线性探查再散列法来构造散列表并同时列出每个数据的比较次数。

（2）使用链地址法来构造散列表。

182．已知二叉排序树采用二叉链表存储结构，根结点的指针为T，请写出递归算法，从

小到大输出该二叉排序树中所有关键字值≥K的结点的关键字的值。

183．我们知道，待排序记录序列的初始排列状态会影响某些排序算法的时间量级（包

括记录的比软次数和移动次数两个方面）。请在表8-1的空格内，填上“是”或“否”，以表

明使用相应的排序算法时记录的比较次数和移动次数之量级是否受影响，即当待排序记录序

列处于某种初始排列状态时排序时间是一个量级；当处于另一种初始排列状态时排序时间又

变成另一个量级。另外，在每行的最后一个空格中亦请标明相应的算法是否是稳定的排序算

法。（南方名校经典试题）

填写表格

005

叶宏 系主任 教授

006

周芳 教员 教授

007

刘光 系主任 教授

008

黄兵 教员 讲师

009

李民 室主任 教授

010

赵松 教员 副教授

…… …… …… ……

192．简单比较文件的多重表和倒排表组织方式各有什么优缺点。

193．简述栈与队列的异同。

194．试说明用栈求表达式值的基本思想。

195．栈的定义及特性。

196．试列举出数据结构栈的至少五种基本操作。

197．栈的特点是什么？试举出栈的两个应用实例。

198.用一维数组sq[0:m-1]存储循环队列的元素时，怎样另设一个标志tag来区分尾指针

（rear）和头指针（front）相等时队列的状态是空还是满？

199．何谓顺序队列的上溢现象？有哪些解决方法？

200．设有一个输入序列ABCD，元素经过一个栈到达输出序列，并且元素一旦离开输

入序列不再回到输入序列，试写出经过这个栈后可以得到各种输出序列。