智慧树知到答案数据结构（宁夏大学）最新答案

第三章 单元测试

1、单选题：
栈结构通常采用的两种存储结构是（  ）。
选项：
A:线性存储结构和非线性存储结构
B:链表存储结构和数组
C:散列方式和索引方式
D:线性存储结构和链表存储结构
答案:

2、单选题：
设循环队列Q[N]的头尾指针为F、R，头指针F总是指在队列中的第一个元素的前一位置，则队列中元素计数为（ ）。
选项：
A:(F-R+N)%N
B:R-F
C:(R-F+N)%N
D:N-(R-F)
答案:

3、单选题：
队列操作的原则是（  ）。
选项：
A:只能进行删除
B:后进先出
C:只能进行插入
D:先进先出
答案:

4、单选题：
一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（  ）。
选项：
A:2 3 4 1 5
B:2 3 1 4 5
C:1 5 4 3 2
D:5 4 1 3 2
答案:

5、单选题：
设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（  ）。
选项：
A:6
B:2
C:4
D:3
答案:

6、单选题：
设用链表作为栈的存储结构则退栈操作（  ）。
选项：
A:必须判别栈是否为满
B:对栈不作任何判别
C:判别栈元素的类型
D:必须判别栈是否为空
答案:

7、单选题：
设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（  ）。
选项：
A:O(1)
B:O(n)
C:O(n²)
D:O(log₂n)
答案:

8、单选题：
设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（  ）。
选项：
A:top=top+1;
B:top=top->next;
C:top=top-1;
D:top->next=top;
答案:

9、单选题：
以下属于队列的基本运算的是（  ）。
选项：
A:对队列中的元素排序
B:在队列中某元素之后插入元素
C:删除队头元素
D:取出最近进队元素
答案:

10、单选题：
以下各种不带头结点的链表中最不适合用作链队的（  ）。
选项：
A:只带队尾指针的循环双链表
B:只带队首指针的循环双链表
C:只带队尾指针的非循环双链表
D:只带队首指针的非循环双链表
答案:

11、判断题：
在链队列中，即使不设置尾指针也能进行入队操作。

选项：
A:对
B:错
答案:

12、判断题：
非空的双向循环链表中任何结点的前驱指针均不为空。

选项：
A:错
B:对
答案:

13、判断题：
走迷宫问题只能用队列来求解。

选项：
A:错
B:对
答案:

第四章 单元测试

1、单选题：
下面关于串的叙述中，哪一个是不正确的？（   ）。
选项：
A:串既可以采用顺序存储，也可以采用链式存储
B:模式匹配是串的一种重要运算
C:串是字符的有限序列
D:空串是由空格构成的串
答案:

2、单选题：
字符串采用结点大小为1的链表作为其存储结构，是指（   ）。
选项：
A:链表只存放1个字符
B:链表的每个链结点的数据域中不只存放了一个字符
C:链表的每个链结点的数据域中只存放了一个字符
D:链表的长度为1
答案:

3、单选题：
设串s1=’ABCDEFG’，s2=’PQRST’，下标从0开始，函数con(x,y)返回x和y串的连接串，subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的结果串是（  ）。
选项：
A:CDPQRST
B:CDEFG
C:CDEFGG
D:CDEFGFG
答案:

4、单选题：
模式串S=’aaab’，其Next数组值分别为（   ）。
选项：
A:-1，1，2，0
B:0，1，0，0
C:0，0，1，2
D:-1，0，1，2
答案:

5、单选题：
两个串相等必有串长度相等且（   ）。
选项：
A:串中各对应位置字符均相等
B:两个串含有相同的字符
C:串的各位置字符任意
D:两个串所含字符任意
答案:

6、单选题：
若有以下定义和语句:char *s1=”12345″,*s2=”1234″;printf(“%dn”,strlen(strcpy(s1,s2)));则输出结果是（   ）。
选项：
A:4
B:10
C:5

D:9
答案:

7、单选题：
printf函数中用到格式符%5s ,其中数字5表示输出的字符串占用5列。如果字符串长度小于5,则输出按方式（  ）。
选项：
A:输出错误信息
B:右对齐输出该字串,左补空格
C:按原字符长从左向右全部输出
D:从左起输出该字串,右补空格
答案:

8、单选题：
对于一个链串s，查找第i个元素的复杂度为（  ）。
选项：
A:O(n)
B:都不对
C:O(n²)
D:O(1)
答案:

9、判断题：
C语言中，char  c[4]=”abc”,d[4]=”abc”; 等价于char  c[4]=d[4]=”abc”;

选项：
A:错
B:对
答案:

10、判断题：

C语言中，语句static  char  c[ ]=“after”;执行后，数组c的长度为5。

选项：
A:错
B:对
答案:

第五章 单元测试

1、单选题：
设有一个二维数组A[10][15]，数组按行存放，假设A[0][0]存放位置在644，每个元素占1个空间，则A[4][5]在（   ）位置。
选项：
A:626
B:672
C:709
D:724
答案:

2、单选题：
设有一个n行n列的对称矩阵A将其下三角部分按行存放在一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于B中（   ）处。
选项：
A:(i+1)*i/2
B:(i+3)*i/2
C:(2n-i-1)*i/2
D:(2n-i+1)*i/2
答案:

3、单选题：
设已知一个稀疏矩阵的三元组如下：(1,2,3),(1,6,1),(3,1,5),(3,2,-1),(4,5,4),(5,1,-3),则其转置矩阵的三元组表中第3个三元组为（   ）。
选项：
A:(3,1,5)
B:(2,3,-1)
C:(3,2,-1)
D:(2,1,3)
答案:

4、单选题：
广义表L=((a,b,c))，则L的长度和深度分别为（   ）。
选项：
A:1和3
B:2和3
C:1和1
D:1和2
答案:

5、单选题：
广义表运算，Tail(Head(((a,b,c,d,e)))) =（   ）。
选项：
A:(b,c,d,e)
B:a
C:c,d
D:空表
答案:

6、单选题：
在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（  ）。
选项：
A:列号
B:行号
C:非零元素个数
D:元素值
答案:

7、单选题：
C语言中，合法的数组定义是（  ）。
选项：
A:string s=”string”;
B:int a[5]={0,1,2,3,4,5};
C:char a[]={0,1,2,3,4,5};
D:int a[]=”string”;
答案:

8、单选题：
若有以下定义和语句: int a[10]={1,2,3,4,5,6,7,8,9,10},*p=a;不能表示a数组元素的表达式是（  ）。
选项：
A:a[10]
B:a[p-a]
C:*p
D:*a
答案:

9、判断题：
C语言中，设int a[ ][4]={1,2,3,4,5,6,7,8,9};则数组a的第一维大小是5。

选项：
A:对
B:错
答案:

10、判断题：

C语言中，可以在赋值语句中通过赋值运算符”=”对字符数组整体赋值。

选项：
A:错
B:对
答案:

第六章 单元测试

1、单选题：
设二叉树根结点的层次为1，所有含有63个结点的二叉树中，最小高度是（  ）。
选项：
A:7
B:6
C:5
D:4
答案:

2、单选题：
设结点x和结点y是二叉树T中的任意两个结点，若在前序序列中x在y之前，而在后序序列中x在y之后，则x和y的关系是（  ）。
选项：
A:x是y的左兄弟
B:x是y的右兄弟
C: y是x的孩子
D:y是x的祖先
答案:

3、单选题：

选项：
A:A
B:C
C:B
D:D
答案:

4、单选题：
深度为5的二叉树至多有（  ）个结点。
选项：
A:32
B:16
C:10
D:31
答案:

5、单选题：
如图所示二叉树的后序遍历序列是（  ）。
选项：
A:gdbehfca
B:gdbfheca
C:abdgcefh
D:dgbafche
答案:

6、单选题：
如图所示二叉树的中序遍历序列是（  ）。
选项：
A:abdgcefh
B:dgbafche
C:gdbehfca
D:abcdefgh
答案:

7、单选题：
在有n个结点的二叉链表中，值为非空的链域的个数为（  ）。
选项：
A:2n+1
B:n-1
C:2n-1
D:n+1
答案:

8、单选题：
对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（  ）遍历实现编号。
选项：
A:后序
B:从根开始的层次遍历
C:无序
D:中序
答案:

9、单选题：
某二叉树的中序序列和后序序列正好相反，则该二叉树一定是（  ）的二叉树。
选项：
A:空或只有一个结点
B:任一结点无右孩子
C:任一结点无左孩子
D:高度等于其结点数
答案:

10、单选题：
一棵非空的二叉树的先序序列和后序序列正好相同，则该二叉树一定满足（  ）。
选项：
A:是任意一棵二叉树
B:其中任意一结点均无右孩子
C:其中任意一结点均无左孩子
D:其中只有一个结点
答案:

11、单选题：
一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为（  ）。
选项：
A:1
B:0
C:2
D:不确定
答案:

12、判断题：
给定一棵二叉树的前序和后序遍历序列，可以唯一地确定出这棵二叉树形态。

选项：
A:对
B:错
答案:

13、判断题：
二叉树就是度为2的树。

选项：
A:错
B:对
答案:

14、判断题：

把一棵树转换成二叉树后，这棵二叉树形态是唯一的。

选项：
A:错
B:对
答案:

15、判断题：
哈夫曼编码是一种前缀码。

选项：
A:对
B:错
答案:

第七章 单元测试

1、单选题：

具有n个顶点的无向完全图的边数为（  ）。
选项：
A: n(n-1)
B:n²
C:n²-1
D:n(n-1)/2
答案:

2、单选题：
对含有n个顶点e条边的有向图，Floyd算法的时间复杂度为（  ）
选项：
A:O(ne)
B: O(n²)
C:O(n)
D:O(n³)
答案:

3、单选题：
如果从无向图的任一顶点出发进行一次深度优先搜索可访问所有顶点，则该图一定是（  ）。
选项：
A:完全图
B:连通图
C:有回路的图
D:一棵树
答案:

4、单选题：
带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中（  ）。

选项：
A:第i行非∞且非0的元素个数
B:第i行非∞的元素之和
C:第i列非∞的元素之和
D:第i列非∞且非0的元素个数
答案:

5、单选题：
以下对AOV网的描述中，错误的是（  ）。
选项：
A:所有关键活动都提前完成，整个工程也将提前完成。
B:在AOV网中可能存在多条关键路径。
C:关键活动不近期完成就会影响整个工程的完成时间。
D:任何一个关键活动提前完成，整个工程也将提前完成。
答案:

6、单选题：
设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（  ）条有向边。
选项：
A:m-1
B:n-1
C:m
D:n
答案:

7、单选题：
设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（  ）。
选项：
A:O(n³)
B:O(ne)
C:O(n²)
D:O(n+e)
答案:

8、单选题：
用邻接表存储图所用的空间大小（  ）。
选项：
A:与图的顶点和边数与关
B:只与图的顶点数与关
C:与边数的平方有关
D:只与图的边数有关
答案:

9、单选题：
深度优先遍历类似于二叉树的（  ）。
选项：
A:中序遍历
B:后序遍历
C:层次遍历
D:先序遍历
答案:

10、单选题：
用 Prim和Kruskal两种算法构造同一连通图的最小生成树，所得的最小生成树（  ）。
选项：
A:其余都不对
B:是相同的
C:可能相同也可能不同
D:是不同的
答案:

11、判断题：
任一AOV网中至少有一条关键路径，且是从源点到汇点的路径中最长的一条。（  ）

选项：
A:对
B:错
答案:

12、判断题：
若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。

选项：
A:对
B:错
答案:

13、判断题：
邻接表比邻接矩阵更节省空间。

选项：
A:错
B:对
答案:

14、判断题：
任意一个AOV网都可以有拓扑排序。

选项：
A:对
B:错
答案:

15、判断题：
图的广度优先遍历算法中用到的辅助队列，每个顶点最多进队的次数不确定。

选项：
A:错
B:对
答案:

第八章 单元测试

1、单选题：
以下不稳定的排序方法是（     ）
选项：
A:直接选择排序
B:冒泡排序
C:直接插入排序
D:归并排序
答案:

2、单选题：
以下稳定的排序方法是（     ）
选项：
A:快速排序
B:堆排序
C:冒泡排序
D:直接选择排序
答案:

3、单选题：
以下时间复杂性不是O(n²)的排序方法是（     ）
选项：
A:直接插入排序
B:归并排序
C:冒泡排序
D:直接选择排序
答案:

4、单选题：
以下说法错误的是（     ）。
选项：
A:快速排序附加存储开销为O(log₂n)。
B:堆排序的空间复杂度为O(n)。
C:直接插入排序的空间复杂度为O(1)。
D:归并排序的空间复杂度为O(n),需要附加两倍的存储开销。
答案:

5、单选题：
以下时间复杂性不是O(nlog₂n)的排序方法是（     ）。
选项：
A:堆排序
B:二路归并排序
C:快速排序
D:直接插入排序
答案:

6、单选题：
在文件局部有序或文件长度较小的情况下，最佳的排序方法是（     ）。
选项：
A:直接选择排序
B:直接插入排序
C:冒泡排序
D:归并排序
答案:

7、单选题：
对于大文件的排序要研究在外设上的排序技术，即 （     ）。
选项：
A:内排序法
B:交叉排序法
C:外排序法
D:快速排序法
答案:

8、单选题：
排序的目的是为了以后对已排序的数据元数进行（     ）操作。
选项：
A:合并
B:分类
C:打印输出
D:查找
答案:

9、单选题：
当初始序列已按健值有序时，用直接插入算法进行排序，需要比较的次数为（     ）。
选项：
A:Dn²
B:log₂n
C:2log₂n
D:n-1
答案:

10、单选题：
快速排序在最坏的情况下的时间复杂度是（     ）。
选项：
A:O(n²)
B:O(nlog₂n)
C:O(n³)
D:O(log₂n)
答案: