数据结构课程习题汇编.docx

数据结构课程习题汇编.docx

《数据结构课程习题汇编.docx》由会员分享，可在线阅读，更多相关《数据结构课程习题汇编.docx（36页珍藏版）》请在冰点文库上搜索。

数据结构课程习题汇编

选择题

1、若入栈序列的元素顺序为A、B、C、D、E，判断下列哪一个出栈序列是不可能的。

（）

A．A、B、C、D、E　　　　B.B、C、D、E、A　　

C．E、A、B、C、DD.D、C、B、A、E

2、某程序的时间复杂度为（3n+nlog2n+n2+8）,其数量级表示为（）。

A．O（n）B．O（nlog2n）C．O（n2）D．O（log2n）

3、一个循环队列的队首和队尾指针分别是front和rear,则判别队空的条件是（）

A．front+1==rearB．front==rear+1

C．front==0D．front==rear

4、一个非空广义表的表头（　　）

A．不可能是子表　B．只能是子表　C．只能是原子　D.可以是子表或原子

5、一个有顺序表有255个对象，采用顺序搜索法查表，平均搜索长度为（）

A128B127C126D255

6、设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过1.5，则散列存储空间应能够至少容纳（）个表项。

（搜索成功的平均搜索长度为Snl=（1+1/（1-a））/2,其中a为装填因子

A400B526C624D676

7、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（）。

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

8．以下哪个数据结构不是多型数据类型（）

A．栈B．广义表C．有向图D．字符串

9．以下数据结构中，（）是非线性数据结构

A．树B．字符串C．队D．栈

10.下列数据中，（）是非线性数据结构。

A．栈B.队列C.完全二叉树D.堆

11．连续存储设计时，存储单元的地址（）。

A．一定连续B．一定不连续C．不一定连续D．部分连续，部分不连续

12．对稀疏矩阵进行压缩存储目的是（）。

A．便于进行矩阵运算B．便于输入和输出

C．节省存储空间D．降低运算的时间复杂度

13．以下属于逻辑结构的是（）。

A．顺序表B.哈希表C.有序表D.单链表

14．从一棵B_树删除元素的过程中，若最终引起树根结点的合并，则新树高度是（）。

A．原树高度加1B．原树高度减1

C．原树高度D．不确定

15．在一个具有n个顶点的无向图中，要连通所有顶点则至少需要（）条边。

A．nB．2nC．n-1D．n+1

16．在某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

A单链表B、仅有头指针的单循环链表C、双链表D、仅有尾指针的单循环链表

17．下列4种排序方法中，不稳定的方法是（　　）。

A．直接插入排序　　B．冒泡排序　　C．归并排序　　D．直接选择排序

18．串是一种特殊的线性表，其特殊性体现在（）

A.可以顺序存储B.数据元素是一个字符

C.可以链接存储D.数据元素可以是多个字符

19．在一个图中，所有顶点的度数之和等于所有边数的（）倍。

A.1/2B.1C.2D.4

20．有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，（）次比较后查找成功。

A.1B.2C.4D.8

21．一棵左右子树不空的二叉树在先序线索化后，其空指针域数为（）。

A.0B.1C.2D.不确定

22．在下列排序算法中，在待排序的数据表已经为有序时，花费时间反而最多的是（）。

A.快速排序B.希尔排序C.冒泡排序D.堆排序

23．向顺序栈中压入新元素时，应当（）。

A．先移动栈顶指针，再存入元素B．先存入元素，再移动栈顶指针

C．先后次序无关紧要D．同时进行

24．在线索二叉树中，下面说法不正确的是（）

A.在中序线索树中，若某结点有右孩子，则其后继结点是它的右子树的左支末端结点。

B.线索二叉树是利用二叉树的n+1个空指针来存放结点前驱和后继信息的。

C.每个结点通过线索都可以直接找到它的前驱和后继

D.在中序线索树中，若某结点有左孩子，则其前驱结点是它的左子树的右支末端结点。

25．广义表A=（a,b,（c,d）,（e,（f,g）））,则下面式子的值为（）。

Head（Tail（Head（Tail（Tail（A）））））

A.（g）B.（d）C.cD.d

26．有三个数字1,2,3,将它们构成二叉树，中序遍历序列为1,2,3的不同二叉树有（）种。

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

27．一个算法应该是（）。

A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C.

28.下面关于算法说法错误的是（）

A．算法最终必须由计算机程序实现

B.为解决某问题的算法同为该问题编写的程序含义是相同的

C.算法的可行性是指指令不能有二义性

D.以上几个都是错误的

29.下面说法错误的是（）

（1）算法原地工作的含义是指不需要任何额外的辅助空间

（2）在相同的规模n下，复杂度O（n）的算法在时间上总是优于复杂度O（2n）的算法

（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界

（4）同一个算法，实现语言的级别越高，执行效率就越低

A．

（1）B.

（1）,

（2）C.

（1）,（4）D.（3）

30．从逻辑上可以把数据结构分为（）两大类。

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

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

31．以下与数据的存储结构无关的术语是（）。

A．循环队列B.链表C.哈希表D.栈

32．以下数据结构中，哪一个是线性结构（）？

A．广义表B.二叉树C.稀疏矩阵D.串

33．以下那一个术语与数据的存储结构无关？

（）

A．栈B.哈希表C.线索树D.双向链表

34．一棵左右子树不空的二叉树在先序线索化后，其空指针域数为（）。

A.0B.1C.2D不确定

35．在一棵二叉树中，第4层上的结点数最多为（）。

A．31B．8C．15D．16

36．向堆中插入一个元素的时间复杂度为（）。

A．O（log2n）B．O（n）C．O

（1）D．O（nlog2n）

37．广义表L=（a，（b，c）），进行Tail（L）操作后的结果为（）。

A.cB.b，cC.（b，c）D.（（b，c））

38．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）

A．250B、500C．254D、501

39．计算机算法必具备输入、输出和（）等五个特性

A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性

C.确定性、有穷性和稳定性D.易读性、稳定性和安全性

40.下面的叙述不正确的是（）

A．线性表在链式存储时，查找第i个元素的时间同i的值成正比

B.线性表在链式存储时，查找第i个元素的时间同i的值无关

C.线性表在顺序存储时，查找第i个元素的时间同i的值成正比

D.线性表在顺序存储时，查找第i个元素的时间同i的值无关

41．在长度为n的顺序表的第i（1≤i≤n+1）个位置上插入一个元素，元素的移动次数为（）

An-i+1B.n-iC.iD.i-1

42．对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（）

A.顺序表B.用头指针表示的单循环链表

C.用尾指针表示的单循环链表D.单链表

43．若一个具有N个顶点，K条边的无向图是一个森林（N>K），则该森林中必有（）棵树。

A.KB.NC.N-KD.1

44．若已知一个栈的入栈序列是1，2，3，....，n，其输出序列为p1,p2,p3,…pn,若p1是n，则pi是（）

A.iB.n-iC.n-i+1D.不确定

45．表达式a*（b+c）-d的后缀表达式是（）

A.abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd

46．在倒排文件中，通常包含有（）倒排表。

A.一个B.多个C.两个D.一个或两个

47．二维数组M[i,j]的元素占三个字节，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3，5]的起始地址与M按列存储时元素（）的起始地址相同。

A、M[2,4]B、M[3,4]C、M[3,5]D、M[4,4]

48．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（　　）。

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

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

49．非空的循环链表head的尾结点*p满足（）

A.p->next=NULLB.p=NULLC.p->next=headD.p=head

50．若要尽可能快地完成对实数数组的排序，且要求排序是稳定的，则应选（）

A快速排序B堆排序C归并排序D基数排序。

51．二叉树在线索化后，仍不能有效求解的问题是（）。

A.先序线索二叉树中求先序后继B.中序线索二叉树中求中序后继

C.中序线索二叉树中求中序前驱D.后序线索二叉树中求后序后继

52．在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点为A，并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则做（）型调整以使其平衡。

A.LLB.LRC.RLD.RR

53．对有18个元素的有序表做折半查找，则查找A[3]的比较序列的下标依次（）。

A.1-2-3B.9-5-2-3C.9-5-3D.9-4-2-3

54．计算机算法指的是（）

A．计算方法B．.排序方法

C．解决问题的有限运算序列D．调度方法

55．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。

与森林F对应的二叉树根结点的右子树上的结点个数是（）。

A．M1B．M1+M2C．M3D．M2+M3

56．以下叙述正确的是（）

A．线性表的线性存储结构优于链表存储结构

B．二维数组是其数据元素为线性表的线性表

C．栈的操作方式是先进先出

D．队列的操作方式是先进后出

57．一个顺序存储的线性表的第一个元素的存储地址是100，每个元素的长度是2，则第5个元素的地址是（）

A．100B．108C．110D．120

58．判定一个栈ST（最多元素为m）为空的条件是（）

A．ST->top<>0B．ST->top=0

C．ST->top<>mD．ST->top=m

59．静态链表中指针表示的是（）.

A．内存地址B．数组下标C．下一元素地址D．左、右孩子地址

60．.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（）

A．acbedB．decabC．deabcD．cedba

61．有n个叶子的哈夫曼树的结点总数为（）。

A．不确定B．2nC．2n+1D．2n-1

62．在一非空二叉树的中序遍历序列中，根结点的右边（）

A．只有右子树上的所有结点B．只有右子树上的部分结点

C．只有左子树上的部分结点D．只有左子树上的所有结点

63．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）

A．nB．（n－1）2C．n－1D．n2

64.下面的叙述中，不正确的是（）

A．关键活动不按期完成就会影响整个工程的完成时间

B．任何一个关键活动提前完成，将使整个工程提前完成

C．所有关键活动若提前完成，则整个工程将提前完成

D．某些关键活动若提前完成，将使整个工程提前完成

65.二叉树上叶结点数等于（）。

A．分支结点数加1B．单分支结点数加1

C．双分支结点数加1D．双分支结点数减1

66．若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（）遍历方法最合适。

A．前序B．中序C．后序D．按层次

67.每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做（）排序

A．插入B．交换C．选择D．归并

68.设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素个数为（）。

A．r-fB．r-f+1C．（r-f）modn+1D．（r-f+n）modn

69.二叉树在线索化后，仍不能有效求解的问题是（）。

A．先序线索二叉树中求先序后继B．中序线索二叉树中求中序后继

C．中序线索二叉树中求中序前驱D．后序线索二叉树中求后序后继

70下面说法正确的为（）

（1）二叉树按某种方式线索化后，任一结点均有指向前驱和后继的线索

（2）二叉树的前序遍列序列中，任意一个结点均处在子孙结点前

（3）二叉排序树中任一结点的值大于其左孩子的值，小于右孩子的值

A．

（1）

（2）（3）B．

（1）

（2）

C．

（1）（3）D．前面的可选答案都不对

71下面的说法中正确的是（）

（1）任何一棵二叉树的叶结点在三种遍历中的相对次序不变;

（2）按二叉树定义,具有三个结点的二叉树共有6种;

A．

（1）,

（2）B．

（1）C．

（2）D．

（1）,

（2）都错

72.一棵二叉树高度为h,所有结点的度或为0,或为2,则这棵二叉树最少有（）个结点

A．2hB．2h-1C．2h+1D．h+1

73．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是（）排序

A．冒泡B．希尔C．快速D．堆

74．与链表不相适宜的叙述是（　　）

A、动态存储分配　　B、可表示任何类型的数据结构　　

C、插入和删除操作灵活　D、查找速度快

75．设i为n个结点的二叉树结点编号，i=1,2,…,n；若i<=（n-1）/2时，结点i的右子女为（　　）

A、2iB、2i+1C、2i-1D、i+1

76．队列的插入操作是在（）进行。

A、队首B、队尾C、队前D、对后

77、下面关于二分查找的叙述正确的是（）

A.表必须有序，表可以顺序方式存储，也可以链表方式存储

B.表必须有序，而且只能从小到大排列

C.表必须有序且表中数据必须是整型，实型或字符型

D.表必须有序，且表只能以顺序方式存储

78．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（　　）。

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

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

79．S=‘software’，其子串的数目是（）

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

80．下面的说法中正确的是（）.

（1）任何一棵二叉树的叶子结点在三种遍历中的相对次序不变；

（2）按二叉树定义，具有三个结点的二叉树共有6种。

A．

（1）

（2）B．

（1）C．

（2）D．

（1）、

（2）都错

81．二维数组M[i,j]的元素占三个字节，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3，5]的起始地址与M按列存储时元素（）的起始地址相同。

A、M[2,4]B、M[3,4]C、M[3,5]D、M[4,4]

82．下列几种排序方法中，平均查找长度最小的是（）

A、插入排序B、选择排序C、快速排序D、归并排序

83．采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）

A、nB、n/2C、（n＋1）/2D、（n－1）/2

84．下述几种排序方法中，要求内存量最大的是（）

A、插入排序B、选择排序C、快速排序D、归并排序

85．数据结构是一门研究非数值计算的程序设计问题中计算机的（），以及它们之间的（）和运算等的学科。

A、操作对象关系B、计算方法结构

C、逻辑存储运算D、数据映象算法

86．下述哪一条是顺序存储结构的优点？

（）

A．存储密度大B．插入运算方便

C．删除运算方便D．可方便地用于各种逻辑结构的存储表示

87．计算机算法必须具备输入、输出、（）等五个特性。

A、可行性、可移植性和可扩充性B、可行性、确定性和有穷性

C、确定性、有穷性和稳定性D、易读性、稳定性和安全性

88．栈和队列的共同点是（）

A、都是先进后出B、都是先进先出

C、只允许在端点处插入和删除元素D、没有共同点

89．在一个单链表中，若删除p所指结点的后续结点，则执行（）

A、p->next=p->next->next;B、p=p->next;p->next=p->next->next

C、p->next=p->next;D、p=p->next->next;

90．深度为5的二叉树至多有（）个结点

A、16B、32C、31D、10

91．设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素个数为（）。

A、r-fB、r-f+1C、（r-f）modn+1D、（r-f+n）modn

92．递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。

A．队列B．多维数组C．栈D.线性表

93．对一棵二叉排序树进行（）遍历得到的结点序列是一个有序序列。

A、前序B、中序C、后序D、层序

94．任何一个无向连通图的最小生成树（）。

A、有一棵或多棵B、只有一棵C、一定有多棵D、可能不存在

95．数组A[1..5,1..6]的每个元素占5个单元，将其按行优先顺序存储在起始地址为1000的连续的内存单元中，则元素A[5,5]的地址为（）。

A.1140B.1145C.1120D1125

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

A.堆排序B.冒泡排序C.快速排序D.直接插入排序

97．设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是（）。

A．6B.4C.3D.2

100．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）

A．所有的结点均无左孩子B．所有的结点均无右孩子

C．只有一个叶子结点D．是任意一棵二叉树

101．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）

A．都不相同　　B．完全相同

C．先序和中序相同，而与后序不同D．中序和后序相同，而与先序不同

102．某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。

A．空或只有一个结点B．任一结点无左子树

C．高度等于其结点数D．任一结点无右子树

103．若线性表最常用的操作是存取第i个元素及其前驱的值，则采用（）存储方式节省时间。

A.单向链表B.双向链表C.单循环链表D.顺序表

104．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一双亲的左、右孩子中，左孩子的编号小于右孩子的编号，则可采用（）顺序实现编号。

A.前序遍历B.中序遍历C.后序遍历D.层序遍历

105．设连通图G的顶点数n，则G的生成树的边数为（）。

A.nB.n-1C.2nD，2n-1

106．若长度为n的线性表采用顺序存储结构，删除一元素需要移动元素的平均个数为（）

A（n-1）/2BnCn-1Dn/2

107．设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n（n+1）/2]中，对上述任一元素aij（1≤i，j≤n，且i≤j）在B中的位置为（）。

A.i（i-l）/2+jB.j（j-l）/2+iC.j（j-l）/2+i-1D.i（i-l）/2+j-1

108．设栈的输入序列为（1，2，3，4），则不可能的出栈序列为（）

A1234B2134C1432D4312

109．从一棵深度为h的二叉排序树中查找一个元素时，其时间复杂度为（）。

A．O（h）B．O（h2）C．O（log2h）D．O（n*log2h）

110．一个循环队列的队首和队尾指针分别是front和rear,则判别队空的条件是（）

A.front+1==rearB.front==rear+1

C.front==0D.front==rear

111．由两个栈共享一个向量空间的好处是（　　）

A、减少存取时间，降低下溢发生的机率

B、节省存取空间，降低上溢发生的机率

C、减少存取时间，降低上溢发生的机率

D、节省存取空间，降低下溢发生的机率

112．如下陈述中正确的是（　　）

A、串是一种特殊的线性表　　B、串的长度必须大于零　　

C、串中元素只能是字母D、空串就是空白串

113．引入二叉线索树的目的是（）

A．加快查找结点的前驱或后继的速度B．为了能在二叉树中方便的进行插入与删除

C．为了能方便的找到双亲D．使二叉树的遍历结果唯一

114．线索二叉树是一种（）结构。

A．逻辑B．逻辑和存储C．物理D．线性

115．n个结点的线索二叉树上含有的线索数为（）

A．2nB．n－lC．n＋lD．n

116．二叉树在线索后，仍不能有效求解的问题是（）。

A．前（先）序线索二叉树中求前（先）序后继B．中序线索二叉树中求中序后继

C．中序线索二叉树中求中序前驱D．后序线索二叉树中求后序后继

117．设F是一个森林，B是由F变换得的二叉树。

若F中有n个非终端结点，则B中右指针域为空的结点有（）个。

A．n-1B．nC．n+1D．n+2

118．如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的（）。

A．先序B．中序C．后序D．层次序

119、无向图G=（V，E），其中：

V={a,b,c,d,e,f},E={（a,b）,（a,e）,（a,c）,（b,e）,（c,f）,（f,d）,（e,d）}对该图进行深度优先遍历，得到的顶点序列正确的是（　　）

A.a,b,e,c,d,fB.a,c,f,e,b,d

C.a,e,b,c,f,dD.a,e,d,f,c,b

120．对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（）排序。

A.选择B.快速C.希尔D.冒泡

121