2021知到答案 数据结构（山东大学） 智慧树网课章节测试答案

第一章 章节测试

1、选择题:数据结构的形式定义是（D, S），其中D是数据元素的有限集，S是D上的关系有限集。
选项：
A:错
B:对
答案: 【对】
2、选择题:在数据结构中，从层次上可以把数据结构分成        。
选项：
A:动态结构和静态结构
B:线性结构和非线性结构 
C:顺序存储结构和链式存储结构
D:逻辑结构和存储结构
答案: 【逻辑结构和存储结构】
3、选择题:线性表若采用链式存储结构时，要求内存中可用的存储章的地址        。
选项：
A:一定是不连续的
B:必须是连续的 
C:连续不连续都可以
D:部分地址必须是连续的
答案: 【连续不连续都可以】
4、选择题:下面程序的时间复杂度为        。

for（i=0; i<m; i++）

   for（j=0; j<n; j++）

      A[i][j]=i*j;
选项：
A:O（m²） 
B:O（n²）
C:O（m+n）
D:O（m×n）
答案: 【O（m×n）】

5、选择题:若需要利用形参直接访问实参，则应把形参变量说明为        参数。
选项：
A:void
B:值
 
C:引用
D:指针
答案: 【引用】

第二章 章节测试

1、选择题:带头结点的单链表L为空的判定条件是        。
选项：
A:L= =NULL 
B:L!=NULL
C:L→next= =L 
D:L→next= =NULL
答案: 【L→next= =NULL】
2、选择题:非空的循环单链表L的尾结点（由p所指向）满足        。
选项：
A:p→next = =NULL
B:p= =L
C:p→next= =L   
D:p= =NULL
答案: 【p→next= =L   】
3、选择题:在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行        。
选项：
A:p→next=s; s→next=q
B:q→next=s; s→next=p
C:s→next=p→next; p→next=s
D:p→next=s→next; s→next=p
答案: 【q→next=s; s→next=p】
4、选择题:在一个单链表中，若删除p所指结点的后继结点，则执行        。
选项：
A:p→next=p→next
B:p=p→next→next
C:q=p→next; p→next=q→next
D:p→next=p→next→next
答案: 【q=p→next; p→next=q→next】
5、选择题:在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的算法的时间复杂度为        。
选项：
A:O（n）
 
B:O（n²）
C:O（nlog₂n）
D:O（1） 
答案: 【O（n）
 
】

第三章 章节测试

1、选择题:一个栈的入栈序列是A，B，C，D，E，则栈的不可能的输出序列是        。
选项：
A:EDCBA
B:DCEAB
C:ABCDE
D:DECBA
答案: 【DCEAB】[$]
2、选择题:在一个链队中，假设f和r分别为队首和队尾指针，则插入s所指结点的运算是        。
选项：
A:f–>next=s; f=s
B:r–>next=s; r=s
C:s–>next=r; r=s
D:s–>next=f; f=s
答案: 【r–>next=s; r=s】
3、选择题:一个队列的入队序列是1，2，3，4，则队列的输出序列是        。
选项：
A:4，3，2，1 
B:1，4，3，2
C:3，2，4，1
D:1，2，3，4
答案: 【1，2，3，4】
4、选择题:一个中缀算术表达式为1+（3–x）*y，则其对应的后缀算术表达式为        。
选项：
A:13x–y*+
B:13+x–y*
C:13x+–y*
D:13xy–+*
答案: 【13x–y*+】
5、选择题:一个栈的入栈序列是A，B，C，D，E，f，出栈的序列是B，D，C，F，E，A，则栈的容量至少应（ ）
选项：
A:2
B:3
C:6
D:4
答案: 【3】

第四章 章节测试

1、选择题:如下图所示的4棵二叉树中，        不是完全二叉树。

选项：
A:D
B:B
C:C
D:A
答案: 【C】
2、选择题:在线索化二叉树中，t所指结点没有左子树的充要条件是        。
选项：
A:t–>ltag= =1且t–>left= =NULL
 
B:以上都不对
C:t–>left= =NULL
D:t–>ltag= =1 
答案: 【t–>ltag= =1 】
3、选择题:对一个满二叉树，m个树叶，n个结点，深度为h，则        。
选项：
A:h+m=2n
B:m=h–1 
C:n=2^h–1
D:n=h+m
答案: 【n=2^h–1】
4、选择题:一个具有1025个结点二叉树的高h 为（    ）
选项：
A:11
B:11~1025
C:10~1024
D:10 
答案: 【11~1025】
5、选择题:

一颗非空的二叉树的先序遍历序列和后序便利序列正好相反，则该二叉树满足（   ）
选项：
A:所有结点均无右孩子
B:只有一个叶子结点 
C:所有结点均无左孩子
D:任意二叉树
答案: 【只有一个叶子结点 】

第五章 章节测试

1、选择题:在一个图中，所以顶点度数之和等于所有边数之和的          倍。
选项：
A:2
B:1
C:4
D: 1/2 
答案: 【2】
2、选择题:对于如下图所示的图，若从顶点a出发深度优先搜索遍历，得到的顶点序列为        。

选项：
A:a,b,e,c,d,f
B:a,e,b,c,f,d
C:a,c,f,e,b,d
D:a,e,d,f,c,b
答案: 【a,e,d,f,c,b】
3、选择题:对于上图所示的图，若从顶点a出发进行广度优先搜索遍历，得到的顶点序列为      。
选项：
A: a,b,c,e,d,f 
B:a,e,b,c,f,d
C:a,b,c,e,f,d
D:a,c,f,d,e,b
答案: 【a,b,c,e,f,d】
4、选择题:已知一个有向图的邻接表存储结构如下图所示，若从顶点v1出发深度优先搜索遍历，所得到的顶点序列是         。
选项：
A:v1,v2,v3,v5,v4 
B:v1,v4,v3,v5,v2
C:v1,v2,v3,v4,v5 
D:v1,v3,v4,v5,v2
 
答案: 【v1,v3,v4,v5,v2
 
】
5、选择题:对于下图所示的邻接表，若从从顶点v1出发广度优先搜索遍历，所得到的顶点序列是         。
选项：
A:v1,v4,v3,v5,v2
B:v1,v3,v2,v4,v5 
C:v1,v2,v3,v4,v5 
D:v1,v2,v3,v5,v4 
答案: 【v1,v3,v2,v4,v5 】

第六章 章节测试

1、选择题:对查找表进行折半查找时，要求必须（     ）。
选项：
A:链接存储且按关键字有序
B:链接存储
C:顺序存储
D:顺序存储且按关键字有序 
答案: 【顺序存储且按关键字有序 】
2、选择题:顺序查找适合于存储结构为（    ）的查找表。
选项：
A:索引存储
B:散列结构
C:顺序存储或链接存储
D:压缩存储
答案: 【顺序存储或链接存储】
3、选择题:采用折半查找方法查找长度为n的查找表，平均查找长度为（   ）。
选项：
A: O（nlog₂n）
B:O（log₂n）
C: O（n）
D:O（n²）
答案: 【O（log₂n）】
4、选择题:如果要求一个查找表既能快速查找，又能适用动态变化的要求，可采用 （    ） 查找方法。
选项：
A: 折半
B: 散列
C: 顺序 
D:分块
答案: 【分块】
5、选择题:在散列存储中，装填因子的值越大则存取元素发生冲突的可能性（     ）。
选项：
A:越小
B:越大 
C:无关
D:难以确定
答案: 【越大 】
6、选择题:在平衡二叉树上查找的时间复杂性为（    ）。
选项：
A:O（n²）
B:O（n）
C:O（nlog₂n）
D:O（log₂n）
答案: 【O（log₂n）】
7、选择题:在m阶B-树上，非终端结点的关键字个数n的值为（    ）
选项：
A:m-1
 
B:m
C:
D:m/2
答案: 【】

第七章 章节测试

1、选择题:在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是        。
选项：
A:插入排序
B:起泡排序 
C:选择排序
D:希尔排序
答案: 【选择排序】
2、选择题:在待排序的元素序列基本有序的前提下，效率最高的排序方法是        。
选项：
A:插入排序
B:快速排序 
C:归并排序 
D:选择排序
答案: 【插入排序】
3、选择题:一组记录的关键字为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为        。
选项：
A:84，79，56，38，40，46
B:84，79，56，46，40，38  
C:84，56，79，40，46，38 
D:79，46，56，38，40，84  
答案: 【84，79，56，46，40，38  】
4、选择题:一组记录的关键字为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为        。
选项：
A:38，40，46，56，79，84
B:40，38，46，56，79，84 
C:40，38，46，79，56，84
D:40，38，46，84，56，79
答案: 【40，38，46，56，79，84 】
5、选择题: 5．快速排序在被排序的数据已基本有序情况下最不利于发挥其长处，在被排序的数据完全无序情况下最容易发挥其长处。
选项：
A:对
B:错
答案: 【对】[/$]