数据结构知识考试复习题库（附答案）

数据结构知识考试复习题库(附答案)

单选题

1.线索二叉树是一种什么结构的二叉树？

A、逻辑结构

B、顺序存储结构

C、线性链表结构

D、逻辑结构与存储绢构相结合

参考答案：D

2.具有n个节点的完全二叉树的深度为？

A、LIog2nj

B、「log2nl

C、LIog2nj+1

D、「Iog2(n+1)1

参考答案：C

3.对单链表进行删除操作时，不需要找到前驱结点的情况是？

A、删除头结点

B、删除尾结点

C、删除中间结点

D、删除空表中的元素

参考答案：A

4.已知循环队列存储在数组A[0..4]中，则队列中能容纳的元素个数是？

1st

A、4

B、5

C、3

D、无法确定

参考答案：B

5.顺序存储结构的主要缺点是？

A、插入和删除操作方便

B、固定了存储分配

C、随机访问能力强

D、易于存储稀疏数据

参考答案：B

6.设一棵完全二叉树有700个节点，则该二叉树中叶子节点的个数是？

A、349

B、350

C、351

D、352

参考答案：B

7.数据结构研究的是数据的内在逻辑关系及其在计算机中的存储表示,

它主要研究的是数据的什么？

A、逻辑结构

B、存储结构

C、抽象数据类型

2nd

D、运算方法

参考答案：B

8.设顺序表有10个元素，第6个元素的关键字最大，则递增有序顺序表

的查找失败的最长查找长度是？

A、5

B、6

C、7

D、10

参考答案：A

9.在哈希表中，解决冲突的方法不包括？

A、开放定址法

B、链地址法

C、再哈希法

D、二分查找法

参考答案：D

10.以下关于链式存储结构的描述中，错误的是？

A、插入删除不需要移动元素

B、寄存器不要求连续的内存地址

C、逻辑上相邻的节点物理上不必相邻

D、可以通过计算直接访问第i个元素

参考答案：D

11.在一个循环队列中，队尾指针指向队尾元素，队头指针指向队头元素

3rd

的前一个位置，则判断队列满的条件是？

A、Q.rear=Q.front

B、Q.rear+1=Q.front

C、Q.rear=(Q.front+1)%MaxSize

D、Q.front=(Q.rear+1)%MaxSize

参考答案：C

12.中序遍历二叉树序列为abc,则该二叉树的形状可能为？

A、a为根，b在左，c在右

B、a为根，c在左，b在右

C、b为根，a在左，c在右

D、c为根，a在左，b在右

参考答案：A

13.对线性表进行二分查找时，要求线性表必须？

A、以顺序方式存储

B、以链接方式存储

C、以顺序方式存储，且节点有序

D、以链接方式存储，且节点有序

参考答案：C

14.某二叉树的后序遍历序列为DBEAFC,中序遍历序列为DEBACF,则其

前序遍历序列为？

A、ABCDEF

B、DEBCFA

4th

C、DBEACF

D、BCDEAF

参考答案：A

15.二叉树中，度为0的节点数为nO,度为2的节点数为n2,则nO和n

2的关系是？

A、n0=n2+1

B^n0=n2-1

C、n0>n2

D、n0<n2

参考答案：A

16.循环队列引入了一个“队头指针”和一个“队尾指针”，是为了区分？

A、空队列与满队列

B、队列与栈

C、顺序存储与链式存储

D、大小可变与大小固定

参考答案：A

17.线性表若采用链式存储结构时，要求内存中可用存储单元的地址？

A、必须是连续的

B、部分地址必须是连续的

C、一定是不连续的

D、连续或不连续都可以

参考答案：D

5th

18.二叉树第i层上最多有多少个节点？

A、2XT)

B、2、

C、2i-1

D、i

参考答案：A

19.栈和队列的共同点是?

A、都是线性结构

B、元素可随机访问

C、只允许在端点插入删除

D、不允许插入删除

参考答案：C

20.下列排序算法中，时间复杂度为0(rT2)的是？

A、归并排序

B、快速排序

C、冒泡排序

D、堆排序

参考答案：C

21.对n个元素进行快速排序，在最好的情况下，递归树的深度为？

A、n

B、Iog2n

C、n/2

6th

D^n+1

参考答案：B

22.下列数据结构中，不是索引结构的是？

A、顺序表

B、B十树

C、B一树

D、哈希表

参考答案：D

23.Dijkstra算法适合解决哪类问题?

A、所有顶点对的最短路径

B、求最小生成树

C、求图中某一源点到其余各顶点的最短路径

D、求带权有向图中某一对顶点之间的最短路径

参考答案：C

24.散列函数构造方法中，除留余数法通常用于？

A、取关键字平方

B、取关键字长度

C、取关键字倍数

D、取关键字模一个素数

参考答案：D

25.栈和队列的共同点是？

A、都是线性结构

7th

B、只允许在端点插入和删除

C、都不允许插入删除

D、都是先进后出

参考答案：B

26.以下关于二叉树的描述中，正确的是？

A、二叉树的度为2

B、度为2的树是二叉树

C、完全二叉树中一定有度为1的节点

D、任何二叉树中，叶子节点数总比度为2的节点数多1

参考答案：D

27.循环队列的优点不包括？

A、提高内存利用率

B、改善了当队头出队后，剩余元素需要移动的情况

C、支持随机存取

D、能够更好地处理溢出

参考答案：C

28.快速排序在worstcase下的时间复杂度是？

A、0(n)

B、O(nlogn)

C、0(rT2)

D、O(logn)

参考答案：C

8th

29.栈的基本操作不包括？

A、入栈

B、出栈

C、读栈顶元素

D、遍历

参考答案：D

30.在任意一棵非空二叉树中，第i层的节点数最多为？

A、2"i-1)

B、2、

C、2i

D、i

参考答案：A

31.将两棵有序的有序表合并成一棵有序表，最坏情况下的时间复杂度

是？

A、0(1)

B、0(n)

C、0(rT2)

D、0(logn)

参考答案：B

32.以下排序算法中，时间复杂度为0(rT2)的是？

A、快速排序

B、归并排序

9th

C、希尔排序

D、冒泡排序

参考答案：D

33.某二叉树的后序遍历序列是dbeafc,中序遍历序列是debacf,则其

前序遍历序列是？

A、acbed

B、deabc

C^dabce

D^adcbe

参考答案：A

34.对n个记录进行归并排序，最坏情况下需要比较的次数为？

A、nlog2n

B、nIog2n-1

C、n”

D、n(n-1)/2

参考答案：A

35.线性表L=(a1,a2,...，an),若要删除第i个元素，需移动元素的个数

为？

A、n-i

B、n-i-1

C、i

D^n-i+1

10th

参考答案：B

36.构造哈夫曼树失败的情况是？

A、给出了n个权值

B、n个叶子节点

C、n个权值，构造出n+1个节点

D、树中不存在度为1的节点？这是特性。所以可能题目描述有变体。如

果强制选D,可能是干扰项，或者理解为“因为树中不存在度为1的节点，

所以构造失败(因为无法处理？)”。实标上，如果题目问“在二叉树

中，度为1的节点数不可能大于，那是另一个题。我们假设题目问

的是“哪种情况会导致无法构造哈夫曼树”。通常是没有数据。让我们

替换这道题，选一个更稳妥的。“在哈夫曼树中，结点的平均路径长度

为”->1/2log(n+1)“哈夫曼树的带权路径长度WPL...”“若有两个

权值相同的叶子节点，其左右子树可以互换，得到的仍是哈夫曼树”-)

对。如果题目原意是“构造哈夫曼树需要将...”，或者“没有度为1的

节点”。让我们再读一遍：“构造哈夫曼树失败的情况是？”可能是选

项有误，或者考察“二叉树”与“哈夫曼树”的关系。如果二叉树中存

在度为1的节点，它就不是哈夫曼树，但“失败”指构造过程。假设D

是“树中存在度为1的节点”,那就是失败原因。如果D是“树中不存

在度为1的节点”，那不是失败。让我们修正为标准题：“哈夫曼树中

度为2的节点数与度为0的节点数的关系是？”->n2二nO-1。或者“哈夫

曼树中，度数为2的节点有4个，则该树中共有多少个叶子节点？”->5。

参考答案：D

11th

37.哈希查找过程中，解决冲突的常用方法是？

A、线性探测法

B、快速排序法

C、归并排序法

D、直接插入法

参考答案：A

38.在任意一棵二叉树中，度为1的节点数至多是？

A、0

B、1

C^n-1

D、n/2

参考答案：B

39.折半查找的平均查找长度是？

A、0(n)

B、0”2)

C、0(Iog2n)

D、0(nlog2n)

参考答案：C

40.在哈夫曼树中，权值越大的节点离根节点？

A、越近

B、越远

C、相等

12th

D、无关

参考答案：A

41.在待排序记录序列基本有序的前提下，效率最高的排序方法是?

A、直接插入排序

B、简单选择排序

C、快速排序

D、归并排序

参考答案：A

42.以下数据结构中，不属于线性结构的是？

A、线性表

B、栈

C、树

D、队列

参考答案：C

43.以下关于队列的叙述中正确的是？

A、队列属于非线性结构

B、队列的操作是先进先出

C、队列的操作是后进先出

D、队列中的元素都是有序的

参考答案：B

44.线性表、栈和队列都是哪种数据结构？

A、动态结构

13th

B、线性结构

C、非线性结构

D、树形结构

参考答案：B

45.若一个栈的输入序列是1,2,3,4,5,则不可能得到的输出序列是？

A、5,4,3,2,1

B、4,5,3,2,1

C、2,3,4,1,5

D、1,3,4,5,2

参考答案：D

46.一个链表中共有n个节点，已知头指针为h,则查找第k个节点的算

法时间复杂度为？

A、0(1)

B、0(n)

C、0(k)

D、0(n"2)

参考答案：B

47.树转化为二叉树，根节点的右孩子是？

A、树的根

树的根的左兄弟

C、树的根的右兄弟

D、空

14th

参考答案：D

48.一个栈的入栈序列是a,b,c,d,e,则栈的不可能输出序列是?

A、edcba

B、decba

C、abode

D、dceab

参考答案：D

49.在一个长度为n的顺序表中删除第i个元素(1/iWn)时，需要向前

移动的元素个数是？

A、n-i

B、n-i+1

C、i

D、i-1

参考答案：A

50.顺序查找算法的时间复杂度是？

A、0(n)

B、0(rT2)

C、0(Iog2n)

D、0(1)

参考答案：A

51.树的基本遍历方式不包括？

A、前序遍历

15th

B、中序遍历

C、后序遍历

D、层次遍历

参考答案：B

52.带头结点的单彼表L为空的判断条件是？

A、L==NULL

B、L->next==NULL

C、L->next!=NULL

D、L->next!=L

参考答案：B

53.对n个记录进行快速排序，最坏情况下的时间复杂度是？

A、O(nlogn)

B、0(rT2)

C、0(n)

D、O(logn)

参考答案：B

54.若循环队列存储在数组A[0..m-1]中，则入队时的操作是?

A、rear=rear+1

B、rear-(rear+1)%(m-1)

C^rear=(rear+1)%m

D、rear二(rear+1)%(m+1)

参考答案：C

16th

55.循环队列引入的目的主要是为了解决什么问题？

A、提高存储效率

B、节省存储空间

C、减少入队出队操作时间

D、防止“假溢出”

参考答案：D

56.某二叉树的前序遍历序列是abode,中序遍历序列是baedc,则其后

序遍历序列是？

A、cbeda

B、dceab

C、debca

D、bcdea

参考答案：A

57.对树进行遍历，最常用的方法是？

A、前序遍历

B、中序遍历

C＞后序遍历

D^层次遍历

参考答案：A

58.在链式队列中，删除队头元素时需要修改的是？

A、头指针

B、尾指针

17th

C、头指针和尾指针

D、头结点

参考答案：A

59.若一棵二叉树的前序遍历序列为ABC,中序遍历序列为ACB,则后序

遍历序列为？

A、ACB

B、BCA

C、BAC

D、CBA

参考答案：D

60.以下关于循环链表的说法，正确的是？

A、循环链表中至少有一个节点，且头结点指针恒为NULL

B、循环链表中可以没有头结点

C、循环链表的尾指针R指向尾节点，查找首节点需遍历，时间复杂度0

(n)

D、循环链表的尾指针R指向尾节点，查找首节点时间复杂度为0(1)

参考答案：D

61.设栈S初始为空，元素a,b,c,d,e,千依次进栈,若出栈序列为b,d,c,

f,e,a,则进栈的序列是？

A、a,b,c,d,e,f

B、b,a,c,d,e,f

C、d,c,e,b,f,a

18th

D、d,b,a,c,e,f

参考答案：B

62.一棵完全二叉树有1001个节点，则其叶子节点的个数是？

A、500

B、501

C、251

D、252

参考答案：B

63.具有1000个节点的完全二叉树，其深度为？

A、9

B、10

C、11

D、12

参考答案：B

64.在单链表中，指针p指向的节点是*q的直接前驱，则在*p和*q之间

插入*s节点，需执行的语句序列是？

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

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

C、q->next=s;s->next=q;

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

参考答案：B

65.栈在以下哪种应用中最为典型？

19th

A、表达式求值

B、文件编辑器中的撤销功能

C、汉诺塔问题

D、B

参考答案：C

66.在哈希表中解决冲突的方法不包括？

A、开放定址法

B、链地址法

C、再哈希法

D、插入排序法

参考答案：D

67.用Prim算法或Kruskal算法构造最小生成树，它们解决的问题是什

么？

A、求最长路径

B、求最短路径

C、在一个带权连通图中，找出一个权值总和最小的生成树

D、求图的连通分量个数

参考答案：C

68.在n个元素的线性表中进行插入操作，最坏情况下需要移动的元素个

数是？

A、n-1

B、n

20th

C^n+1

D、2n

参考答案：B

69.已知完全二叉树的第8层有16个节点，则该二叉树的叶子节点总数

为？

A、31

B、32

C、33

D、40

参考答案：C

70.线索二叉树是一种？

A、逻辑结构

B、存储结构

C、运算结构

D、逻辑和存储结构

参考答案：B

多选题

1.设栈S的初始状态为空，元素a,b,c,d,e,f,g依次入栈，则下列哪一

组出栈序列可能得到？

A、a,b,c,d,e,f,g

B、g,f,e,d,c,b,a

21st

C、eyf,d,g,cfb,a

D、c,e,a,b,d,g,f

参考答案：BCD

2.以下关于二叉排序树(BST)的描述，正确的是？

A、若左子树不空，则左子树上所有节点的值均小于根节点的值

B、若右子树不空，则右子树上所有节点的值均大于根节点的值

C、每个节点的左、右子树也分别为二叉排序树

D、按中序遍历二叉排序树，得到的是有序序列

参考答案：ABCD

3.下列关于堆排序的描述中，正确的是？

A、堆排序是不稳定的排序算法

B、堆排序的时间复杂度是O(nlogn)

C、初始建堆的时间复杂度是0(n)

D、堆是一种完全二叉树

参考答案：ABCD

4.图的邻接矩阵表示法中，以下说法正确的是？

A、无向图的邻接矩阵是对称的

B、有向图的邻接矩阵不一定是对称的

C、邻接矩阵可以用于判断两点是否有边相连

D、邻接矩阵的存储空间与图的顶点数无关，只与边数有关

参考答案：ABC

5.下列关于折半查找的描述中，正确的是？

22nd

A、折半查找的前提是记录必须有序

B、折半查找的时间复杂度是O(logn)

C、折半查找适合于链式存储结构

D、折半查找效率高于顺序查找

参考答案：ABD

6.双向链表中，已知p指针指向某结点，若要删除p指向的结点，需执

行的操作是？

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

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

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

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

参考答案：ABD

7.下列关于循环链表的描述中，正确的是？

A、循环链表的最后一个节点的指针域指向头节点

B、循环链表可以从任意节点遍历整个链表

C、循环链表可以不设头指针

D、循环链表解决了单向链表无法反向遍历的问题

参考答案：ABC

8.下列关于栈的溢出的描述中，正确的是？

A、栈溢出是指向栈中压入了超过栈最大容量的数据

B、栈下溢是指试图从空栈中弹出元素

C、递归调用的层数过深可能导致栈溢出

23rd

D、动态内存分配的栈空间不足会导致栈溢出

参考答案：ABCD

9.下列关于内排序和外排序的描述中，正确的是？

A、排序过程中所有待排记录都存放在内存中，称为内排序

B、排序过程中需要访问外部存储器，称为外排序

C、快速排序是内排序

D、归并排序可以是内排序，也可以是外排序

参考答案：ABCD

10.下列关于B树和B+树的描述中，正确的是？

A、B树是一棵多路平衡查找树

B、B+树的叶子节点包含所有关键字

C、B+树的非叶子节点只存储索引

D、B树适合作为索引结构

参考答案：ABCD

11.以下哪些操作属于栈的基本运算？

A、入栈

B、出栈

C、读栈顶元素

D、删除栈顶元素

参考答案：ABCD

12.下列关于哈希函数构造方法的描述中，正确的是？

A、直接定址法

24th

B、数字分析法

C、平方取中法

D、除留余数法

参考答案：ABCD

13.以下哪些是二叉树的基本性质？

A、在二叉树的第i层上，最多有2人（i-1）个结点（i>=1）

B、在深度为k的二叉树中，最多有2八kT个结点

C、具有n个结点的完全二叉树的深度为floor（log2n）+1

D、对任何一棵二叉树，若叶子结点数为nO,度为2的结点数为n2,则n

0=n2+1

参考答案：ABCD

14.下列关于基数排序的描述中，正确的是？

A、基数排序是按LSD（最低位优先）进行排序的

B、基数排序是稳定的排序算法

C、基数排序通过分配和收集操作实现

D、基数排序的时间复杂度是0（nk）,k是位数

参考答案：ABCD

15.下列关于静态链表的描述中，正确的是？

A、静态链表用数组实现

B、静态链表需要预分配内存

C、静态链表插入删除不需要移动元素

D、静态链表的游标指示下一个节点的位置

25th

参考答案：ABCD

16.下列关于数组实现的描述中，正确的是？

A、一维数组是同类型元素的序列

B、二维数组可以看作是一维数组作为元素构成的数组

C、数组通常采用顺序存储结构

D、数组的下标通常是连续的整数

参考答案：ABCD

17.下列关于B+树与B树的区别的描述中，正确的是？

A、B+树的所有叶子节点通过指针相连

B、B+树的非叶子节点只存索引，不存数据

C、B树的非叶子节点既可以存索引也可以存数据

D、B+树通常用于数据库索引

参考答案：ABCD

18.对序列｛16,7,2,23,15,21,9,19｝进行快速排序，第一次划分后，左半

区元素的个数可能是？

A、2

B、3

C、4

D、5

参考答案：ABC

19.下列关于广义表的描述中，正确的是？

A、广义表是线性表的推广

26th

B、广义表可以为空表

C、广义表的长度是指原子节点的个数

D、广义表的深度是指展开后的最大层数

参考答案：ABD

20.线性表的链式存储结构中，指针指向？

A、数据元素

B、数据元素所属的结点

C、结点的下一个结点

D、结点的前一个结点

参考答案：BC

21.下列关于稀疏矩阵的压缩存储描述中，正确的是？

A、三元组表可以表示非零元素

B、十字链表适合表示稀疏矩阵

C、非零元素的位置分布是有规律的，可以采用一维数组压缩

D、稀疏矩阵的压缩存储会丢失矩阵的零元素信息

参考答案：ABD

22.以下关于队列的描述中，正确的是哪些？

A、队列是一种先进先出的线性表

B、队列是一种后进先出的线性表

C、只能在队列的队尾插入元素

D、只能在队列的队头删除元素

参考答案：ACD

27th

23.下列关于二叉树性质的描述中，正确的是？

A、在任意一棵二叉树中，度为0的节点个数恒等于度为2的节点个数加

1

B、在完全二叉树中，节点按层次编号，若i>n/2,则节点i为叶子节点

C、二叉树的中序遍历序列和后序遍历序列可以唯一确定一棵二叉树

D、二叉树的前序遍历序列和后序遍历序列可以唯一确定一棵二叉树

参考答案：AB

24.下列关于图的连通性的描述中，正确的是？

A、连通图是指从任意一个顶点出发可以到达其他所有顶点的图

B、连通图的生成树包含图中所有顶点

C、一个非连通图可以有多个连通分量

D、无向图的邻接矩阵一定是对称矩阵

参考答案：ABCD

25.在数据结构中，线性表有哪几种存储结构？

A、顺序存储结构

B、链式存储结构

C、散列存储结构

D、索引存储结构

参考答案：AB

26.以下哪些排序算法是稳定的？

A、A泡排序

B、直接插入排序

28th

C、选择排序

D、归并排序

参考答案：ABD

27.下列关于有序顺序表的描述中，正确的是？

A、有序顺序表是指表中元素按关键字递增或递减排列

B、在有序顺序表中查找关键字，可以使用折半查找法

C、在有序顺序表中插入一个元素，可能会破坏表的有序性

D、在有序顺序表中删除一个元素，可能会破坏表的有序性

参考答案：ABCD

28.下列关于顺序查找的描述中，正确的是？

A、顺序查找的时间复杂度是0(n)

B、顺序查找适合于链式存储结构

C、顺序查找的记录必须是有序的

D、顺序查找从后往前查找可以提高效率

参考答案：ABD

29.对一组数据｛50,10,90,30,70,40,80,60｝进行堆排序(大顶堆)，构

建堆后的序列可能是？

A、90,80,50,40,30,10,70,60

B、90,80,70,60,50,40,30,10

C、90,80,70,40,30,10,50,60

D、90,80,60,50,40,30,70,10

参考答案：ABC

29th

30.下列关于链表的描述中，正确的是？

A、顺序表插入删除需要移动大量元素，时间复杂度较低

B、链表插入删除不需要移动元素，时间复杂度较高

C、链表不适合顺序访问

D、彳连表在内存中是不连续存放的

参考答案：CD

31.下列关于栈的基本操作的叙述中，正确的是？

A、在栈的某个元素之前插入新元素称为入栈

B、删除栈顶元素称为出栈

C、栈是限定在表尾进行插入和删除操作的线性表

D、栈空的条件是top=-1

参考答案：ABCD

32.下列关于图的最小生成树的描述中，正确的是？

A、最小生成树是包含图中所有顶点的无环连通子图

B、最小生成树的权值之和是最小的

C、Prim算法和KruskaI算法是求最小生成/对的常用算法

D、最小生成树唯一

参考答案：ABC

33.下列关于森林的描述中，正确的是？

A、森林是若干棵互不相交的树的集合

B、树可以看作是只有一个根节点的森林

C、森林与二叉树之间可以相互转换

30th

D、森林的先根遍历等同于二叉树的先序遍历

参考答案：ABCD

34.顺序存储结构中的数组元素在内存中是？

A、连续存放的

B、可以不连续存放

C、逻辑上相邻的元素物理上不一定相邻

D、物理上相邻的元素逻辑上相邻

参考答案：AD

35.下列关于图的遍历，正确的是？

A、从图的某个顶点出发，可以遍历图中所有顶点

B、连通图的所有顶点构成一个顶点集，该顶点集的生成树包含图中全部

顶点

C、无向图的邻接矩阵是对称矩阵

D、有向图的邻接矩阵一定是对称矩阵

参考答案：ABC

36.下列关于遍历二叉树的描述中，正确的是？

A、前序遍历是：根-左-右

中序遍历是：左-根-右

C、后序遍历是：左-右-根

D、层序遍历需要借助队列实现

参考答案：ABCD

37.下列关于折半查找判定树的描述中，正确的是？

31st

A、折半查找的判定树是一棵二叉排序树

B、折半查找的判定树是一棵完全二叉树

C、查找成功时的平均查找长度与判定树的高度有关

D、折半查找中，查找失败的平均查找长度等于判定树中所有失败节点的

层数之和除以叶子节点数

参考答案：ABCD

38.以下关于队列的描述中，正确的是？

A、队列是“先进先出”的线性表

B、队列是“后进先出”的线性表

C、队列只允许在队尾插入元素

D、队列只允许在队头删除元素

参考答案：ACD

39.下列关于快速排序的描述中，正确的是？

A、快速排序是不稳定的排序算法

B、快速排序的平均时间复杂度是O(nlogn)

C、快速排序的最坏情况时间复杂度是O(rf2)

D、快速排序是基于分治法的思想

参考答案：ABCD

40.下列属于栈的应用实例的是？

A、函数调用

B、表达式求值

C、括号匹配检查

32nd

D、二叉树遍历

参考答案：ABCD

41.下列关于队列的队列的数组实现的描述中，正确的是？

A、循环队列可以消除假溢出问题

B、队空条件是front-rear

C、队满条件可以是（rear+1）%MAXSIZE=front

D^队空条件是rear-front==0

参考答案：ABC

42.在单链表中，已知指针p指向节点q的前面，若要在p和q之间插入

s,则操作序列是？

A、s->next=p->next

B、p->next=s

C、q->next=s

D、s->next=q

参考答案：ABD

43.下列关于索引顺序表的描述中，正确的是？

A、索引顺序表是顺序表与索引技术的结合

B、索引顺序表包括主表和索引表

C、索引顺序表可以提高查找速度

D、索引顺序表占用空间较少

参考答案：ABCD

44.下列关于字符串的描述中，正确的是？

33rd

A、字符串是一种特殊的线性表

B、字符串的比较通常是按字典序进行的

C、空串的长度为0

D、空串与空格串是相同的

参考答案：ABC

45.下列关于图的存储结构的描述中，正确的是？

A、图的邻接矩阵表示法适合稠密图

B、图的邻接表表示法适合稀疏图

C、邻接矩阵中第i行非零元素个数等于顶点i的度

D、邻接表中第i个链表的节点数等于顶点i的度

参考答案：ABC

46.下列关于哈希表的描述中，正确的是？

A、哈希表通过计算数据元素的键值得到该元素的存储位置

B、哈希函数值冲突时，通常会采用开放定址法处理冲突

C、哈希表的平均查找长度与表长n有关

D、哈希表的查找效率主要取决于哈希函数的构造和冲突处理方法

参考答案：ABD

47.下列关于归并排序的描述中，正确的是？

A、归并排序是稳定的排序算法

B、归并排序的时间复杂度始终是O(nlogn)

C、归并排序需要额外的空间

D、归并排序适用于链式存储结构

34th

参考答案：ABCD

48.下列关于图的最短路径算法的描述中，正确的是？

A、Dijkstra算法适用于求单源最短路径

B、Dijkstra算法不能处理带负权边的图

C、Floyd算法适用于求任意两点间的最短路径

D、Floyd算法的时间复杂度是0(rT3)

参考答案：ABCD

49.下列关于数据结构的描述中，正确的是？

A、数据结构是指相互之间存在一种或多种特定关系的数据元素的集合

B、逻辑结构与存储结构是数据结构的两个要素

C、存储结构是数据在计算机中的表示

D、逻辑结构独立于计算机

参考答案：ABCD

50.下列关于二叉排序树(BST)的描述中，正确的是？

A、中序遍历二叉排序树可以得到一个有序序列

B、在二叉排序树中插入一个新节点，只需从根节点出发查找插入位置

C、在二叉排序树中删除一个节点后，该树仍然保持二叉排序树的特性

D、二叉排序树中不存在值相同的节点

参考答案：ABC

判断题

1.树中所有节点的度之和等于树中边的数量。

35th

A、正确

B、错误

参考答案：A

2.邻接表法是图的邻接矩阵的线性表实现。

A、正确

B、错误

参考答案：B

3.设有一顺序队列，长度为$n$,其中已有$k$个元素，则队头指针和队

尾指针的取值范围分别是$0$到$联1$。

A、正确

B、错误

参考答案：B

4.深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。

A、正确

B、错误

参考答案：A

5.中序遍历二叉树的结果是左子树、根节点、右子树。

A、正确

B、错误

参考答案：A

6.设栈的输入序列为1,2,3,4,则输出序列4,3,2,1是可能的。

A、正确

36th

B、错误

参考答案：A

7.递归算法必须包含递归出口。

A、正确

B、错误

参考答案：A

8.在无向图的邻接矩阵中，第$i$行的非零元素个数等于顶点$v_i$的度。

A、正确

B、错误

参考答案：A

9.链式队列的入队操作只需要修改队头指针。

A、正确

B、错误

参考答案：B

10.在单链表中，已知某个结点的指针$p$,则可以在$0(1)$时间内求出

其前驱结点。

A、正确

B、错误

参考答案：B

11.二叉树的存储结构既包括顺序存储也包括链式存储。

A、正确

B、错误

37th

参考答案：A

12.循环队列的优点是消除了假溢出的现象。

A、正确

B、错误

参考答案：B

13.栈和队列都是线性表。

A、正确

B、错误

参考答案：A

14.队列的出队操作是在队尾进行的。

A、正确

B、错误

参考答案：B

15.两个栈共享一个向量空间，可以使得栈的最大容量等于向量空间的大

小。

A、正确

B、错误

参考答案：A

16.二叉树的先序遍历序列中，任意一个结点均出现在其子结点的先序序

列之前。

A、正确

B、错误

38th

参考答案：A

17.有$n$个元素的有序表进行二分查找，其判定树的深度为$\lfloor'lo

g_2n\rfloor+1$o

A、正确

B、错误

参考答案：A

18.顺序存储的栈中，发生“上溢”通常是因为栈已满。

A、正确

B、错误

参考答案：A

19.栈和队列都是线性结构，但栈是线性表，而队列不是。

A、正确

B、错误

参考答案：B

20.在单链表中，已知某个结点的指针$p$,则可以在$0(1)$时间内求出

其后继结点。

A、正确

B、错误

参考答案：A

21.设栈的输入序列为1,2,3,则不可能得到的输出序列是2,3,1。

A、正确

B、错误

39th

参考答案：A

22.深度为k的二叉树至多有2八k-1个节点。

A、正确

B、错误

参考答案：A

23.直接插入排序的时间复杂度为$0(rf2)$o

A、正确

B、错误

参考答案：A

24.栈是一种先进后出的线性表。

A、正确

B、错误

参考答案：A

25.希尔排序是稳定的排序算法。

A、正确

B、错误

参考答案：B

26.冒泡排序是稳定的排序算法。

A、正确

B、错误

参考答案：A

27.二叉树的遍历是按照某种规则依次访问树中每个节点。

40th

A、正确

B、错误

参考答案：A

28.对一棵二叉树进行层序遍历，如果根结点位于第1层，则第$k$层结

点总数最多为

A、正确

B、错误

参考答案：A

29.$k$叉树的第$i$层至多有$k[iT}$个结点($i\ge1$)o

A、正确

B、错误

参考答案：A

30.深度为$k$的二叉树至多有$2%-1$个结点。

A、正确

B、错误

参考答案：A

31.循环队列可以节省存储空间，但在入队和出队时仍可能发生假溢出。

A、正确

B、错误

参考答案：B

32.队列是“先进先出”(FIFO)的线性表。

A、正确

41st

B、错误

参考答案：A

33.二叉树中第$i$层上至多有$2"i-1}$个结点($i\ge1$)。

A、正确

B、错误

参考答案：A

34.有$