智慧树知到答案数据结构(上海电力大学) 最新答案

第三章 单元测试

1、单选题：
若将整数1、2、3、4依次进栈，则不可能得到的出栈序列是
选项：
A:4321
B:1324
C:1423
D:1234
答案:

2、单选题：
在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize，则顺序栈的判空条件是
选项：
A:top==maxSize-1
B:top==maxSize
C:top==0
D:top==-1
答案:

3、单选题：
在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，front指向队首元素，rear指向队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判满条件是
选项：
A:front==rear
B:front==rear+1
C:front!=rear
D:front==(rear+1)% maxSize
答案:

4、单选题：
在链栈中，进行出栈操作时
选项：
A:无需对栈作任何差别
B:需要判断栈是否满
C:需要判断栈元素的类型
D:需要判断栈是否为空
答案:

5、判断题：
栈和队列是一种非线性数据结构
选项：
A:错
B:对
答案:

6、单选题：
在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判空条件是
选项：
A:front==rear
B:front==rear+1
C:front==(rear+1)% maxSize
D:front!=rear
答案:

7、单选题：
循环顺序队列是将顺序队列的存储区域看成是一个首尾相连的环，首尾相连的状态是通过数学上的哪种运算实现的？
选项：
A:求和
B:除运算
C:求余
D:减运算
答案:

8、单选题：
设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为
选项：
A:front=(front+1)%(m+1)
B:front=(front+1)% m
C:front=front+1
D:rear=(rear+1)%m
答案:

9、单选题：
假定利用数组a[n]顺序存储一个栈，用top表示栈顶指针，top==-1表示栈空，并已知栈未满，当元素x进栈时所执行的操作为
选项：
A:a[–top]=x
B:a[top–]=x
C:a[++top]=x
D:a[top++]=x
答案:

10、单选题：
在不带表头结点的链栈中，若栈顶指针top直接指向栈顶元素，则将一个新结点p入栈时修改链的两条对应语句为
选项：
A:

top=p;p.next=top;

B:

p.next=top;top=p;

C:

top.next=p;p=top;

D:

p=top;top.next=p.next;

答案:

第四章 单元测试

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

2、单选题：
串的长度是指( )
选项：
A:串中包含的不同字符个数
B:串中包含的不同字母个数
C:串中包含的字符个数
D:串中除空格以外的字符个数
答案:

3、单选题：
设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为( )
选项：
A:联接
B:求子串
C:求串长
D:模式匹配
答案:

4、单选题：
设主串的长度为n，模式串的长度为m，则串匹配的KMP算法时间复杂度是( )
选项：
A:O(n + m)
B:O(n)
C:O(m)
D:O(n×m)
答案:

5、单选题：
串也是一种线性表，只不过( )
选项：
A:表长受到限制
B:数据元素数据类型不受限制
C:数据元素均为字符
D:数据元素是子串
答案:

6、判断题：
一个串的任意连续字符组成的子序列称为串的 子串，该串称为主串。
选项：
A:错
B:对
答案:

7、判断题：
空串和空格串的串长度都为0。
选项：
A:对
B:错
答案:

8、判断题：
若两个串的长度相等且对应位置上的字符也相等，则称两个串相等。
选项：
A:对
B:错
答案:

9、判断题：
寻找子串在主串中的位置，称为模式匹配。其中，主串又称为模式串。
选项：
A:对
B:错
答案:

10、判断题：
模式串t=”ababaab”的next[]数组值依次为-1、0、0、1、2、1、1。
选项：
A:对
B:错
答案:

第五章 单元测试

1、单选题：
设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主进行存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）
选项：
A:13
B:33
C:40
D:18
答案:

2、单选题：
有一个二维数组A[1..6, 0..7] ，每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组占用的存储空间大小是（ ）个字节
选项：
A:252
B:48
C:96
D:288
答案:

3、单选题：
设有数组A[1..8,1..10]，数组的每个元素占3字节，数组从内存首地址BA开始以列序为主序顺序存放，则数组元素 A[5，8]的存储首地址为（ ）
选项：
A:BA+141
B:BA+222
C:BA+225
D:BA+180
答案:

4、单选题：
稀疏矩阵的三元组存储表示方法（ ）
选项：
A:比十字链表更高效
B:实现转置操作很简单，只需将每个三元组中行下标和列下标交换即可
C:矩阵的非零元素个数和位置在操作过程中变化不大时较有效
D:是一种链式存储方法
答案:

5、单选题：
用十字链表表示一个稀疏矩阵，每个非零元素一般用一个含有（ ）域的结点表示
选项：
A:5
B:4
C:3
D:2
答案:

6、判断题：
设数组A[1..5,1..6]的基地址为1000，每个元素占5个存储单元，若以行序为主序顺序存储，则元素A[5,5]的存储地址为1170。
选项：
A:错
B:对
答案:

7、判断题：
在稀疏矩阵的三元组顺序表存储结构中，除表示非零元的三元组表以外，还需要表示矩阵的行数、列数和非零元个数。
选项：
A:对
B:错
答案:

8、判断题：
一个n×n的对称矩阵，如果以相同的元素只存储一次的原则进行压缩存储，则其元素压缩后所需的存储容量为n(n-1)/2。
选项：
A:错
B:对
答案:

9、判断题：
对矩阵压缩的目的是为了节省存储空间。
选项：
A:错
B:对
答案:

10、判断题：
对于稀疏矩阵采用的三元组表和十字链表两种方法，其中非零元素的表示方法都是一样的。
选项：
A:错
B:对
答案:

第六章 单元测试

1、单选题：
有关二叉树下列说法正确的是（ ）
选项：
A:二叉树中任何一个结点的度都为2
B:二叉树中至少有一个结点的度为2
C:一棵二叉树的度可以小于2
D:二叉树的度为2
答案:

2、单选题：
由3 个结点可以构造出多少种不同的二叉树？（ ）
选项：
A:2
B:3
C:5
D:4
答案:

3、单选题：
若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）
选项：
A:11
B:15
C:不确定
D:9
答案:

4、单选题：
利用二叉链表存储树时，根结点的右指针是（ ）
选项：
A:非空
B:指向最左孩子
C:空
D:指向最右孩子
答案:

5、判断题：
完全二叉树一定存在度为1的结点（ ）
选项：
A:对
B:错
答案:

6、判断题：
用二叉链表存储n个结点的二叉树时，结点的2n个指针中有n+1个空指针（     ）
选项：
A:错
B:对
答案:

7、判断题：
完全二叉树中，若一个结点没有左孩子，则它必是树叶（ ）
选项：
A:对
B:错
答案:

8、单选题：
一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）
选项：
A:只有一个叶子结点
B:所有的结点均无左孩子
C:是任意一棵二叉树
D:所有的结点均无右孩子
答案:

9、单选题：
已知一棵二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC，则它的先序遍历序列为（ ）
选项：
A:DEABC
B:ACBED
C:CEDBA
D:DECAB
答案:

10、判断题：
哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近（ ）
选项：
A:对
B:错
答案:

第七章 单元测试

1、判断题：
在AOE网中一定只有一条关键路径。
选项：
A:错
B:对
答案:

2、判断题：
对任意一个图，从某顶点出发进行一次广度优先遍历或深度优先遍历，可访问图的所有顶点。
选项：
A:错
B:对
答案:

3、单选题：
在一个有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为（ ）。
选项：
A:s-1
B:n
C:s+1
D:s
答案:

4、单选题：
对某个无向图的邻接矩阵来说，下列叙述正确的是( )。
选项：
A:矩阵中非全零行的行数等于图中的顶点数
B:第i行上的非零元素个数和第i列上的非零元素个数一定相等
C:矩阵中的非零元素个数等于图中的边数
D: 第i行与第i列上的非零元素的总数等于顶点vi的度数
答案:

5、单选题：
已知一个有向图的邻接矩阵，要删除所有以第i个顶点为孤尾的边，应该（ ） 。
选项：
A:将邻接矩阵的第i列元素全部置为0
B:将邻接矩阵的第i列删除
C:将邻接矩阵的第i行元素全部置为0
D:将邻接矩阵的第i行删除
答案:

6、多选题：
以下说法正确的是：（　　）。
选项：
A:图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点
B: 有向图的遍历不可以采用广度优先搜索方法
C:无向图中的极大连通子图称为连通分量
D:图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点
答案:

7、判断题：
有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。
选项：
A:对
B:错
答案:

8、单选题：
含有n个顶点的连通图中的任意一条简单路径，其长度不可能超过（ ）。
选项：
A:n-1
B:1
C:n/2
D:n
答案:

9、单选题：
设无向图G=（V，E）和G´=（V´，E´），如果G´是G的生成树，则下面说法错误的是（ ）。
选项：
A:G´为G的连通分量
B:G´为G的子图
C:G´为G的极小连通子图，且V=V´
D:G´为G的无环子图
答案:

10、多选题：
判断一个有向图是否存在回路，可以用（ ）。
选项：
A:广度优先遍历算法
B:拓扑排序方法
C:求最短路径的方法
D:深度优先遍历算法
答案:

第八章 单元测试

1、单选题：
在表长为ｎ的链表中进行线性查找，它的平均查找长度为
选项：
A:ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１
B:ＡＳＬ＝ｎ
C:ＡＳＬ＝（ｎ＋１）／２
D:ＡＳＬ＝ ＋１
答案:

2、单选题：
折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中 比较大小，查找结果是失败。
选项：
A:20，70，30，50
B:20，50
C:30，88，70，50
D:30，88，50
答案:

3、单选题：
用线性探测法解决冲突问题时，所产生的一系列后继散列地址
选项：
A:必须大于或等于原散列地址
B:可以大于或小于但不能等于原散列地址
C:无具体限制
D:必须小于或等于原散列地址
答案:

4、单选题：
在关键字序列（12，23，34，45，56，67，78，89，91）中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为（　　）。
选项：
A:4，3，3
B:3,4,4
C:4，4，3
D:3,3,4
答案:

5、单选题：
由同一关键字集合构造的各棵二叉排序树（　　）。
选项：
A:其形态均相同，平均查找长度也都相同
B:其形态不一定相同，但平均查找长度相同
C:其形态均相同，但平均查找长度不一定相同
D:其形态不一定相同，平均查找长度也不一定相同
答案:

6、单选题：
对于哈希函数H(key) = key%13，被称为同义词的关键字是（　　）。
选项：
A:15和44
B:23和39
C:25和51
D:35和41
答案:

7、单选题：
设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为（　　）。
选项：
A:23
B:41
C:21
D:62
答案:

8、单选题：
已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于（　　）。
选项：
A:5.5
B:3.4
C:2.9
D:1.0
答案:

9、多选题：

构造散列函数时通常考虑的因素有
选项：
A:计算函数的工作量
B:关键字的分布情况
C:关键字的长度
D:散列表长
答案:

10、判断题：
二叉树为二叉排序树的充要条件是，其任意结点的值均大于其左孩子的值且小于其右孩子的值
选项：
A:错
B:对
答案:

第九章 单元测试

1、单选题：
排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为
选项：
A:选择排序
B:冒泡排序
C:插入排序
D:希尔排序
答案:

2、单选题：
下列关键字序列中， 是堆。
选项：
A:16, 23, 53,31, 94, 72
B:94,23, 31, 72, 16, 53
C:16, 53, 23,94,31, 72
D:16,72,31,23,94,53
答案:

3、单选题：
在下列算法中，（　　）算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。
选项：
A:堆排序
B:冒泡排序
C:快速排序
D:插入排序
答案:

4、单选题：
一个序列中有10 000个元素，若只想得到其中前10个最小元素，最好采用（　　）方法。
选项：
A:二路归并排序
B:快速排序
C:插入排序
D:堆排序
答案:

5、单选题：
直接插入排序在最好情况下的时间复杂度为（　　）。
选项：
A:O（n2）
B:O（n）
C:O（nlog n）
D:O（log n）
答案:

6、单选题：
下列排序算法中，哪一种算法的时间复杂度与初始排序序列无关（ ）。
选项：
A:快速排序
B:直接选择排序
C:冒泡排序
D:直接插入排序
答案:

7、单选题：
下述几种排序方法中，平均查找长度（ASL）最小的是
选项：
A:快速排序
B:插入排序
C:归并排序
D:选择排序
答案:

8、多选题：
以下排序方法中，不稳定的排序方法是（　　）。
选项：
A:快速排序
B:直接选择排序
C:二分法插入排序
D:堆排序
答案:

9、多选题：
所需要的平均时间是 O(nlog2n) 有哪些排序算法？
选项：
A:希尔排序
B:快速排序
C:堆排序
D:归并排序
答案:

10、判断题：
快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。
选项：
A:对
B:错
答案: