算法与数据结构（山东联盟）智慧树知到课后章节答案2023年下烟台大学

算法与数据结构（山东联盟）智慧树知到课后章节答案2023年下烟台大学烟台大学

绪论单元测试

数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的____和运算等的学科。

A:结构B:关系C:算法D:运算

答案:关系

算法的描述形式包括

A:N-S图B:类程序设计语言C:流程图

D:自然语言

答案:N-S图;类程序设计语言;流程图

;自然语言

算法的特征包括有穷性、确定性、可行性和输入输出。

A:错B:对

答案:对

对算法的描述包括程序形式和描述形式。

A:错B:对

答案:对

描述形式是算法的最终形式

A:对B:错

答案:错

“数据结构”是介于()、()和()三者之间的一门核心课程。

A:计算机硬件B:语句C:计算机软件D:数学

答案:计算机硬件;计算机软件;数学

著名计算机科学家沃思教授提出的公式：

程序 = (

) + (

)，也说明了数据结构的重要性。

A:算法B:编程环境C:语法D:数据结构

答案:算法;数据结构

描述非数值计算问题的数学模型不再是数学方程，而是数据结构(

)。

A:表B:集合C:树D:图

答案:表;集合;树;图

数据结构是一门研究(

)程序设计问题中计算机的(

)以及它们之间的(

)和(

)等的学科。

A:关系B:非数值计算C:操作D:操作对象

答案:关系;非数值计算;操作;操作对象

顺序存储结构:借助元素在存储器中的(

)来表示数据元素间的逻辑关系。

A:相对位置B:地址C:结构D:数值

答案:相对位置

第一章测试

（）是一种最简单的线性结构。

A:集合B:线性表C:树D:图

答案:线性表

（

）线性表的数据元素可以由所描述对象的各种特征的数据项组成。

A:顺序存储B:链式存储C:散列存储D:有序存储

答案:链式存储

已知单向链表中指针p指向结点A，(

）表示删除A的后继结点（若存在）的链操作（不考虑回收）。

A:p=p—>next—>nextB:p=p—>nextC:p—>next=pD:p—>next=p—>next—>next

答案:p—>next=p—>next—>next

已知last指向单向简单链表的尾结点，将s所指结点加在表尾，不正确的操作是____。

A:last->next=s,s->next=NULL,last=s;B:s->next=NULL,last->next=s,last=s;C:last->next=s,last=s,last->next=NULL;D:s->next=NULL,last->next=s,s=last;

答案:s->next=NULL,last->next=s,s=last;

已知h是指向单向加头链表的首指针，删除表头结点的操作是_____。

A:p=h,h=p->next;free(p);B:p=h->next;free(p);h=h->next;C:free(h->next);h=h->next;D:p=h->next,h->next=p->next;free(p);

答案:p=h->next,h->next=p->next;free(p);

有N个元素组成的线性表，我们说此线性表的长度为（）

A:0B:nC:n-1D:n+1

答案:n

对线性表中的数据元素进行（

）和（

）等操作，实现表的长度的增长或缩短。

A:插入B:访问C:删除D:遍历

答案:插入;删除

线性表的抽象数据类型定义

A:基本操作B:数据对象C:数据关系D:函数关系

答案:基本操作;数据对象;数据关系

我们使用（

），实现线性表的顺序存储。

A:数值B:函数C:语句D:数组

答案:数组

线性表的基本操作是用C语言中的（

）对其进行表示的。

A:结构体B:循环语句C:条件语句D:函数

答案:函数

在链表中第i

个结点之前插入新的元素

e，表的逻辑结构不变。

A:对B:错

答案:错

在单链表中插入结点只需要（）。但同时，若要在第（）个结点之前插入元素，修改的是第

（）个结点的指针。

A:i+1

B:

i

C:修改指针D:i-1

答案:

i

;修改指针;i-1

单链表和线性表中所有基本操作相同，且编程实现方法相同。

A:对B:错

答案:错

数字钟程序中使用的时间，可以是系统时间。

A:对B:错

答案:对

和单链表的差别仅在于，判别链表中最后一个结点的条件不再是(

)，而是（

)。

A:“后继是否为头结点”B:“后继是否为空”C:“前继是否为头结点”D:“前继是否为空”

答案:“后继是否为头结点”;“后继是否为空”

双向链表的“删除”

时需要同时修改两个方向上的指针,改变结点之间的逻辑关系。

A:对B:错

答案:对

双向链表的“插入”

时不需要同时修改两个方向上的指针,改变结点之间的逻辑关系。

A:对B:错

答案:错

双向链表中，当指针p指向非空表中的非头尾结点时，以下哪个式子是正确的（）

A:p->next

=p->prior

B:p=p->next

C:p->next->prior=p

D:p=p->prior->next

答案:p->next->prior=p

;p=p->prior->next

双向链表中，当指针p指向非空表中的非头尾结点时，以下哪个式子是正确的（）

A:p=p->priorB:p->next=p

->priorC:p->prior=p->nextD:p->next->prior=p

答案:p->next->prior=p

双向链表需要在结点中设两个指针域(

)

A:parent指针域B:prior指针域C:数据域D:next指针域

答案:prior指针域;next指针域

第二章测试

队列是一种（

）的线性表。

A:只能插入B:只能删除C:先进后出D:先进先出

答案:先进先出

设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（

）。

A:

front->next=s；front=s；B:

s->next=front；front=s；C:

s->next=rear；rear=s；D:

rear->next=s；rear=s；

答案:

rear->next=s；rear=s；

栈操作数据的原则是（

）。

A:后进后出B:后进先出C:先进先出D:不分顺序

答案:后进先出

栈与队列是一种特殊操作的线性表（

）

A:错B:对

答案:对

和链栈类似，用单链表来实现链队。根据队的先入先出(FIFO)原则，为了操作上的方便，使用一个()和()。

A:数据域B:头指针C:指针域D:尾指针

答案:头指针;尾指针

队列的顺序存储结构用C语言中（）数据类型实现。

A:一维数组实现B:结构体C:枚举型D:二维数组实现

答案:一维数组实现

栈和队列不能进行再分配了。

A:对B:错

答案:错

队列允许在表的一端进行插入操作和删除操作。

A:对B:错

答案:错

入栈需要修改地址指针。

A:对B:错

答案:对

链栈主要的运算，如插入、删除是在栈顶执行的。

链表的头部作栈顶是最方便的，需要像单链表那样为了运算方便附加一个头结点。

A:对B:错

答案:错

链栈的结点结构与单链表的结点结构相同，由（）和（）组成。

A:数据域

指针域B:孩子域

指针域C:双亲域D:指针域

双亲域

答案:数据域

指针域

构造一个空栈S

时，不需要用动态存储空间分配函数。

A:对B:错

答案:错

顺序栈中数据元素与栈顶指针的变化：非空栈中的栈顶指针top始终在的

（）下一个位置

A:栈顶元素B:栈中元素C:栈中任意元素D:栈底元素

答案:栈顶元素

在初始化空顺序栈时一般不限定栈的最大容量，因为，栈在使用过程中所需最大空间的大小很难估计。

A:错B:对

答案:对

利用（）的存储单元依次存放自栈底到栈顶的数据元素，这种形式的栈称为顺序栈。

A:一组地址断开B:一组地址相同C:一组地址连续D:一组地址不连续

答案:一组地址连续

第三章测试

串(即字符串)是一种特殊的线性表，它的数据元素是（）。

A:表B:单个字符C:数字

D:图

答案:单个字符

包含零个字符(n=0)的串称为空串，通常记为Ф，其长度为零；空串是任意串的子串。

A:对B:错

答案:对

空串与空格串相同

A:对B:错

答案:错

串比较是按字符的ASCII值比较的，而不是按串的长度比较的。

StrCompare('data','structures')

________

0；

A:等于B:小于C:大于D:小于等于

答案:小于

SubString(sub,'commander',1,9)

求得

sub='_______'；

A:coanderB:commanrC:commanderD:comander

答案:commander

串的基本操作中，操作对象大多为“串的整体”。

A:对B:错

答案:对

在串的表示和实现过程中，用一组地址不连续的存储单元存储串值中的字符序列，称为串的定长顺序存储方式。

A:错B:对

答案:错

在顺序串中，用一个指针来指向最后一个字符，C语言的表示如下：typedefstruct{

char

data[MAXSIZE];

int

curlen;}SeqString;

请定义一个串变量：

A:

structgsB:SqStrings；C:SeqStrings；D:typedefstructs；

答案:SeqStrings；

在C语言中，存在一个称为“堆”的自由存储区，并由C语言的动态分配函数________来管理。

A:free()B:malloc()和free()C:malloc()D:main()

答案:malloc()和free()

堆分配存储结构的串有顺序存储结构的特点，在操作中对串长又没有任何限制，因而在串处理的应用程序中常被选用。

A:错B:对

答案:对

第四章测试

设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（

）。

A:

2i+1

B:

i/2

C:

2i

D:2i-1

答案:

2i

设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（

）。

A:任一结点无右孩子B:任一结点无左孩子

C:高度等于其结点数D:空或只有一个结点

答案:任一结点无右孩子

二叉树的第k层的结点数最多为()

A:2K+1B:2的k-1次幂C:2的k次幂-1D:2K-1

答案:2的k-1次幂

设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列

为（

）。

A:BCDAB:BADCC:CDABD:CBDA

答案:BADC

满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（）

A:对B:错

答案:对

设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（）

A:错B:对

答案:错

设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（

）。

A:空或只有一个结点

B:任一结点无右孩子C:高度等于其结点数D:

任一结点无左孩子

答案:任一结点无右孩子

树的带权路径长度定义为，树中所有叶子结点的带权路径长度之和(对所有叶子结点)。（）

A:错B:对

答案:对

第五章测试

设某无向图有n个顶点，则该无向图的邻接表中有（

）个表头结点。

A:

n(n-1)B:n/2

C:2n

D:n

答案:n

设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（

）。

A:第i行0元素的个数之和

B:第i列非0或非∞元素的个数之和C:

第i列0元素的个数之和D:第i行非0或非∞元素的个数之和

答案:第i列非0或非∞元素的个数之和

设某完全无向图中有n个顶点，则该完全无向图中有（）条边

A:n的2次幂-1B:n的2次幂C:n(n-1)D:n(n-1)/2

答案:n(n-1)/2

子串“ABC”在主串“AABCABCD”中的位置为2。(

)

A:错B:对

答案:对

对链表进行插入和删除操作时不必移动链表中结点。(

)

A:对B:错

答案:对

深度为k的完全二叉树中最少有（

）个结点。

A:

2k-1-1

B:

2k-1C:

2k-1+1

答案:

2k-1

设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（

）。

A:N0=2N1+lB:N0=N1+1

C:N0=N2+1

D:N0=Nl+N2

答案:N0=N2+1

设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（

）。

A:第i列非0或非∞元素的个数之和B:第i行非0或非∞元素的个数之和

C:第i行0元素的个数之和

D:第i列0元素的个数之和

答案:第i列非0或非∞元素的个数之和

简单回路就是回路。

A:错B:对

答案:错

图中任两点有路径相通，该图称为连通图（）

A:错B:对

答案:对

第六章测试

设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（

）。

A:20

B:30C:40D:45

答案:45

连通图的最小生成树的边上的权值之和是唯一的。(

)

A:错B:对

答案:对

以数据集{1，3，5，7}为叶结点的权值，构造一棵哈夫曼树，求出带权路径长度WPL（）。

A:26B:30C:28D:29

答案:29

查找表可分为两类（）

A:静态查找表B:顺序查找表C:起泡查找表D:动态查找表

答案:静态查找表;动态查找表

使用折半方法进行查找的表是一个有序表。

A:错B:对

答案:对

第七章测试

执行一趟快速排序能够得到的序列是（

）。

A:

[41，12，34，45，27]55[72，63]B:[45，34，12，41]55[72，63，27]C:

[63，12，34，45，27]55[41，72]D:[12，27，45，41]55[34，63，72]

答案:

[41，12，34，45，27]55[72，63]

排序分稳定排序和不稳定排序。（

）

A:错B:对

答案:对

设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（）

A:30B:20C:40D:45

答案:45

冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（）

A:错B:对

答案:对

设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为基准而得到一趟快速排序的结果是（

）。

A:42，40，45，85，55，80B:42，40，45，80，85