石大 《数据结构》 在线作业试题题库及参考答案

注：找到所考试题直接看该试题所有题目和答案即可。

查找按键：Ctrl+F

1(5.0分)最大容量为n的循环队列，队尾指针是rear,队头是front,则队空的

条件是()

A)(rear+1)%n=front

B)rear=front

C)rear+l=front

D)(rear-1)%n=front

参考答案：B

2(5.0分)在有序表中使用折半查找法的平均时间是()

A)0(1)B)0(n)C)O(log2n)D)0(n2)参考答案：C

3(5.0分)用堆栈求算术表达式ab*(c-d)-e/f的后缀表达式为()

A)abed-*ef/-

B)ab*(c-d)-e/f

C)abedef-*/-

D)abc-d*ef/-

参考答案：A

4(5.0分)以下说法错误的是()

A)散列法存储的基本思想是由关键码的值决定数据的存储地址。

B)散列表的结点中只包含数据元素自身的信息，不包含任何指针。

C)装填因子是散列法的一个重要参数，它反映散列表的装填程度。

D)散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的

方法。

参考答案：B

5(5.0分)已知广义表LS=((a,b,c),(d,e,f)),运用head和tail函数取出LS中元素e

的运算是()

A)head(tail(LS))B)tail(head(LS))C)head(tail(head(tail(LS))))D)

head(tail(tail(head(LS))))参考答案：C

6（5.0分）在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的

语句是（）

A）p=p-＞；next；

B）p-＞；next=p-＞；next-＞；next；

C）p-＞；next=p；

D）p=p-＞；next-＞；next；

参考答案：B

7（5.0分）在最好和最坏情况下的时间复杂度均为O（nlogn）且稳定的排序方法是

（）

A）快速排序

B）堆排序

C）归并排序

D）基数排序

参考答案：C

8（5.0分）在顺序存储（空间大小为m）的循环队列q中，下列判满正确的是

（）

A）q.front%m=0；

B）q.rear%m=0；

C）q.front=q.rear；

D）（q.front+1）%m=q.rear；

参考答案：D

9（5.0分）已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在

等概率情况下查找成功的平均查找长度等于（）

A）1.0

B）2.9

C）3.4

D）5.5

参考答案：B

10（5.0分）以下判断不正确的是（）

A)顺序存储的线性表可随机存取。

B)同一线性表中的数据元素应具有相同的特性。

C)顺序存储方式的优点是存储密度大，插入、删除操效率高。

D)在线性表的链式存储结构中，逻辑上相邻的数据元素在物理位置上不一定

相邻。

参考答案：C

11(5.0分)在线索二叉树中，t所指结点没有左子树的充要条件是()

A)t->lchild!=NULL

B)t->ltag==l

C)t->ltag==l且t->left!=NULL

D)以上都不对

参考答案：C

12(5.0分)已知广义表:A=(a,b),B=(A,A),C=(a,(b,A),B),求下列运算的结果：

tail(head(tail(C)))=()A)(a)

B)A

C)(b)D)(A)参考答案：D

13(5.0分)以下说法错误的是()

A)对循环链表来说，从表中任一结点出发都能通过前后操作而扫描整个循环

链表。

B)对单链表来说，只有从头结点开始才能扫描表中全部结点。

C)双链表的特点是找结点的前趋和后继都很容易。

D)对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域

中，也存放在它的后继结点的前趋指针域中。

参考答案：A

14(5.0分)在线性表的顺序存储结构中，逻辑上相邻的数据元素的物理位置

(),在链式存储结构中，逻辑上相邻的数据元素的物理位置()

A)必相邻必相邻

B)必相邻不一定相邻

C)不一定相邻必相邻

D）不一定相邻不一定相邻

参考答案：B

15（5.0分）以下说法错误的是（）

A）哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近

B）若一个二叉树的树叶是某子树中序遍历序列中的第一个结点，则它必是该

子树后序遍历序列中的第一个结点

C）已知二叉树的前序遍历和后序遍历并不能唯一地确定这棵树，因为不知道

树的根结点是哪一个

D）前序遍历二叉树的序列中，任何结点其子树的所有结点都是直接跟在该结

点之后的

参考答案：C

16（5.0分）一维数组和线性表的区别为（）

A）前者长度固定，后者长度可变

B）两者长度均固定

C）前者长度可变，后者长度固定

D）两者长度均可变

参考答案：A

17（5.0分）在数据结构中，从逻辑上可以把数据结构分成（）

A）动态结构和静态结构

B）紧凑结构和非紧凑结构

C）线性结构和非线性结构

D）内部结构和外部结构

参考答案：C

18（5.0分）在具有n个结点的二叉树（二叉链表表示）中，值为空的链域数为

（）

A）n-1

B）2n-1

C）n1

D）2n1

参考答案：B

19（5.0分）有六个元素6,5,4,3,2,1的顺序进栈，问下列哪一个不是合法

的出栈序列？（）

A）543612

B）453126

0346521

D）234156

参考答案：C

20（5.0分）在二叉树的先序遍历，中序遍历和后序遍历算法中，所有叶子结点

的先后顺序（）

A）都不相同

B）完全相同

C）前序遍历和中序遍历相同，而与后序遍历不同

D）前序遍历和后序遍历相同，而与中序遍历不同

参考答案：B

1（5.0分）下面关于图的存储的叙述中正确的是（）

A）用相邻矩阵法存储图，占用的存储空间大小只与图中结点个数有关，而与

边数无关

B）用相邻矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点

个数无关

C）用邻接表法存储图，占用的存储空间大小只与图中结点个数有关，而与边

数无关

D）用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个

数无关

参考答案：A

2（5.0分）一个堆栈的入栈序列为abcde,若出栈和入栈操作可间隔进行，则出

栈序列不可能的为（）

A)edcba

B）decba

C）decab

D）abcde

参考答案：c

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

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

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

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

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

参考答案：B

4（5.0分）下面关于数据结构的叙述中，正确的叙述是（）

A）顺序存储方式的优点是存储密度大，且插、删除运算效率高

B）链表中每个结点都恰好包含一个指针

C）包含n个结点的二叉排序树的最大检索长度为log2n

D）将一棵树转为二叉树后，根结点无右子树

参考答案：D

5（5.0分）下列说法正确的是（）

A）树的先根遍历序列与其对应的二叉树的先根遍历序列相同

B）树的先根遍历序列与其对应的二叉树的后根遍历序列相同

C）树的后根遍历序列与其对应的二叉树的先根遍历序列相同

D）树的后根遍历序列与其对应的二叉树的后根遍历序列相同

参考答案：A

6（5.0分）图结构的广度优先搜索遍历算法中使用了（）

A）堆栈

B）队列

C）堆栈和队列

D）以上都不正确。

参考答案：B

7（5.0分）一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是:

（）

A）edcba

B）decba

C）dceab

D）abcde

参考答案：c

8（5.0分）希尔排序和快速排序分别属于（）

A）交换排序选择排序

B）插入排序选择排序

C）选择排序归并排序

D）交换排序选择排序

参考答案：B

9（5.0分）一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则

计算该有向图中某个顶点出度的时间复杂度为（）

A）O（n）B）0（e）C）O（ne）D）O（n2）参考答案：B

10（5.0分）下面哪一种方法可以判断出一个有向图中是否有环（回路）（）

A）深度优先遍历

B）拓扑排序

C）求最短路径

D）求关键路径

参考答案：B

11（5.0分）下列哪一个关键码序列不符合堆的定义？（）

A）（102,87,100,79,82,62,84,42,22,12,68）B）（102,100,

87,84,82,79,68,62,42,22,12）C）（12,22,42,62,68,79,82,

84,87,100,102）D）（102,87,42,79,82,62,68,100,84,12,22）

参考答案：D

12（5.0分）下面关于完全二叉树的特点叙述不正确的是（）

A）只有最后一层是不满的，不满层的结点首先出现在左边；

B）至多只有最下面的两层结点的度小于2；

C）左子树的高度不会小于右子树的高度，且左、右子树高度最大相差±1；

D）叶子只能出现在最后两层上；

参考答案：C

13（5.0分）下列排序方法中，哪一个是稳定的排序方法？（）

A）直接选择排序

B）堆排序

C）希尔排序

D）快速排序

参考答案：A

14（5.0分）下面程序段的时间复杂度是（）for（i=0;ifor（j=l;jA[i][j]=0；

A）O（n）B）O（mn1）C）O（mn）D）O（m*n）参考答案：D

15（5.0分）下列关于递归特点的描述不正确的是：

A）结构清晰、可读性强。

B）算法正确性易证明。

C）时间效率高。

D）空间效率低。

参考答案：C

16（5.0分）下面关于哈希（Hash,杂凑）查找的说法正确的是（）

A）哈希函数构造的越复杂越好，因为这样随机性好，冲突小

B）除留余数法是所有哈希函数中最好的

C）不存在特别好与坏的哈希函数，要视情况而定

D）在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元

素删去即可

参考答案：C

17（5.0分）下程序段的时间复杂度为（）oi=0;k=0;while（i<N）{i;k=k

10*i;}

A)O(1)

B)O(n)

C）0（n2）

D）0（n3）

参考答案：B

18（5.0分）下列判断正确的是（）

A）二叉树是树的特例。

B）具有n个结点的完全二叉树的深度为n/2o

©Huffman树是带权路径长度最小的二叉树，树中权值越大的叶子结点距离

根结点越远。

D）栈和队列都是限制存取点的线性结构。

参考答案：D

19（5.0分）线性结构中的一个结点代表一个（）

A）数据元素

B）数据项

C）数据

D）数据结构

参考答案：A

20（5.0分）下列说法不正确的是（）

A）图的遍历是从给定的源点出发每一个顶点仅被访问一次

B）图的深度遍历不适用于有向图

C）遍历的基本算法有两种：深度遍历和广度遍历

D）图的深度遍历是一个递归过程

参考答案：B

1（5.0分）下面关于图的存储的叙述中正确的是（）

A）用相邻矩阵法存储图，占用的存储空间大小只与图中结点个数有关，而与

边数无关

B）用相邻矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点

个数无关

C）用邻接表法存储图，占用的存储空间大小只与图中结点个数有关，而与边

数无关

D）用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个

数无关

参考答案：A

2（5.0分）一个堆栈的入栈序列为abcde,若出栈和入栈操作可间隔进行，则出

栈序列不可能的为（）

A）edcba

B）decba

C）decab

D）abcde

参考答案：C

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

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

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

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

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

参考答案：B

4（5.0分）下面关于数据结构的叙述中，正确的叙述是（）

A）顺序存储方式的优点是存储密度大，且插、删除运算效率高

B）链表中每个结点都恰好包含一个指针

C）包含n个结点的二叉排序树的最大检索长度为log2n

D）将一棵树转为二叉树后，根结点无右子树

参考答案：D

5（5.0分）下列说法正确的是（）

A）树的先根遍历序列与其对应的二叉树的先根遍历序列相同

B）树的先根遍历序列与其对应的二叉树的后根遍历序列相同

C）树的后根遍历序列与其对应的二叉树的先根遍历序列相同

D）树的后根遍历序列与其对应的二叉树的后根遍历序列相同

参考答案：A

6（5.0分）图结构的广度优先搜索遍历算法中使用了（）

A）堆栈

B）队列

C）堆栈和队列

D）以上都不正确。

参考答案：B

7（5.0分）一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是：

（）

A）edcba

B）decba

C）dceab

D）abcde

参考答案：C

8（5.0分）希尔排序和快速排序分别属于（）

A）交换排序选择排序

B）插入排序选择排序

C）选择排序归并排序

D）交换排序选择排序

参考答案：B

9（5.0分）一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则

计算该有向图中某个顶点出度的时间复杂度为（）

A）O（n）B）0（e）C）O（ne）D）O（n2）参考答案：B

10（5.0分）下面哪一种方法可以判断出一个有向图中是否有环（回路）（）

A）深度优先遍历

B）拓扑排序

C）求最短路径

D）求关键路径

参考答案：B

11（5.0分）下列哪一个关键码序列不符合堆的定义？（）

A）（102,87,100,79,82,62,84,42,22,12,68）B）（102,100,

87,84,82,79,68,62,42,22,12）C）（12,22,42,62,68,79,82,

84,87,100,102）D）（102,87,42,79,82,62,68,100,84,12,22）

参考答案：D

12（5。分）下面关于完全二叉树的特点叙述不正确的是（）

A）只有最后一层是不满的，不满层的结点首先出现在左边；

B）至多只有最下面的两层结点的度小于2；

C）左子树的高度不会小于右子树的高度，且左、右子树高度最大相差±1；

D）叶子只能出现在最后两层上；

参考答案：C

13（5.0分）下列排序方法中，哪一个是稳定的排序方法？（）

A）直接选择排序

B）堆排序

C）希尔排序

D）快速排序

参考答案：A

14（5.0分）下面程序段的时间复杂度是