数据结构（山东大学）知到章节答案智慧树2023年

数据结构（山东大学）知到章节测试答案智慧树2023年最新第一章测试

数据结构的形式定义是（D,S），其中D是数据元素的有限集，S是D上的关系有限集。

参考答案:

对

在数据结构中，从层次上可以把数据结构分成

。

参考答案:

逻辑结构和存储结构

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

。

参考答案:

连续不连续都可以

下面程序的时间复杂度为

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

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

A[i][j]=i*j;

参考答案:

O（m×n）

若需要利用形参直接访问实参，则应把形参变量说明为

参数。

参考答案:

引用

第二章测试

带头结点的单链表L为空的判定条件是

。

参考答案:

L→next==NULL

非空的循环单链表L的尾结点（由p所指向）满足

。

参考答案:

p→next==L

在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行

。

参考答案:

q→next=s;s→next=p

在一个单链表中，若删除p所指结点的后继结点，则执行

。

参考答案:

q=p→next;p→next=q→next

在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的算法的时间复杂度为

。

参考答案:

O（n）

第三章测试

一个栈的入栈序列是A，B，C，D，E，则栈的不可能的输出序列是

。

参考答案:

DCEAB

在一个链队中，假设f和r分别为队首和队尾指针，则插入s所指结点的运算是

。

参考答案:

r->next=s;r=s

一个队列的入队序列是1，2，3，4，则队列的输出序列是

。

参考答案:

1，2，3，4

一个中缀算术表达式为1+（3-x）*y，则其对应的后缀算术表达式为

。

参考答案:

13x-y*+

一个栈的入栈序列是A，B，C，D，E，f，出栈的序列是B，D，C，F，E，A，则栈的容量至少应（）

参考答案:

3

第四章测试

如下图所示的4棵二叉树中，

不是完全二叉树。

参考答案:

C

在线索化二叉树中，t所指结点没有左子树的充要条件是

。

参考答案:

t->ltag==1

对一个满二叉树，m个树叶，n个结点，深度为h，则

。

参考答案:

n=2h-1

一个具有1025个结点二叉树的高h为（

）

参考答案:

11~1025

一颗非空的二叉树的先序遍历序列和后序便利序列正好相反，则该二叉树满足（

）

参考答案:

只有一个叶子结点

第五章测试

在一个图中，所以顶点度数之和等于所有边数之和的

倍。

参考答案:

2

对于如下图所示的图，若从顶点a出发深度优先搜索遍历，得到的顶点序列为

。

参考答案:

a,e,d,f,c,b

对于上图所示的图，若从顶点a出发进行广度优先搜索遍历，得到的顶点序列为

。

参考答案:

a,b,c,e,f,d

已知一个有向图的邻接表存储结构如下图所示，若从顶点v1出发深度优先搜索遍历，所得到的顶点序列是

。

参考答案:

v1,v3,v4,v5,v2

对于下图所示的邻接表，若从从顶点v1出发广度优先搜索遍历，所得到的顶点序列是

。

参考答案:

v1,v3,v2,v4,v5

第六章测试

对查找表进行折半查找时，要求必须（

）。

参考答案:

顺序存储且按关键字有序

顺序查找适合于存储结构为（

）的查找表。

参考答案:

顺序存储或链接存储

采用折半查找方法查找长度为n的查找表，平均查找长度为（

）。

参考答案:

O（log2n）

如果要求一个查找表既能快速查找，又能适用动态变化的要求，可采用

（

）

查找方法。

参考答案:

分块

在散列存储中，装填因子的值越大则存取元素发生冲突的可能性（

）。

参考答案:

越大

在平衡二叉树上查找的时间复杂性为（

）。

参考答案:

O（log2n）

在m阶B-树上，非终端结点的关键字个数n的值为（

）

参考答案:

第七章测试

在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是

。

参考答案:

选择排序

在待排序的元素序列基本有序的前提下，效率最高的排序方法是

。

参考答案:

插入排序

一组记录的关键字为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为

。

参考答案:

84，79，56，46，40，38

一组记录的关键字为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到