2024知到网课 数据结构（山东联盟-青岛大学）智慧树答案

第一章 单元测试

1、单选题：在Data_Structure=(D，R)中，D是（）的有限集合。
A:数据元素
B:算法
C:数据对象
D:数据操作
正确答案:【数据元素】

2、单选题：计算机所处理的数据一般具有某种关系， 这是指（）。
A:数据与数据之间存在的某种关系
B:数据元素与数据元素之间存在的某种关系
C:数据文件内记录与记录之间存在的某种关系
D:元素内数据项与数据项之间存在的某种关系
正确答案:【数据元素与数据元素之间存在的某种关系】

3、单选题：算法的时间复杂度与（   ）有关。

A:源程序的长度

B:编译后执行程序的质量
C:计算机硬件的运行速度
D:问题规模

正确答案:【问题规模
】

4、单选题：

以下关于数据结构的说法正确的是（  ）。
A:数据结构仅由其逻辑结构和存储结构决定
B:数据结构的逻辑结构独立于其存储结构
C:数据结构的存储结构独立于该数据结构的逻辑结构
D:数据结构的逻辑结构唯一地决定了该数据结构的存储结构
正确答案:【数据结构的逻辑结构独立于其存储结构】

5、单选题：

某算法的时间复杂度是O(n²)，表明该算法（ ）。
A:问题规模与n^2成正比
B:问题规模是n^2
C:执行时间等于n^2
D:执行时间与n^2成正比
正确答案:【执行时间与n^2成正比】

6、单选题：从逻辑上可将数据结构分为（）。
A:内部结构和外部结构
B:动态结构和静态结构
C:线性结构和非线性结构
D:紧凑结构和非紧凑结构
正确答案:【线性结构和非线性结构】

7、判断题：数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。
A:错
B:对
正确答案:【对】

8、判断题：数据的物理结构是指数据结构在计算机内的实际存储形式。
A:错
B:对
正确答案:【对】

9、判断题：每种数据结构都具备三种基本运算：插入、删除和查找。
A:错
B:对
正确答案:【错】

10、判断题：算法的时间效率和空间效率往往相互冲突，有时很难两全其美。
A:错
B:对
正确答案:【对】

第二章 单元测试

1、单选题：线性表是一个（）。
A:数据元素的有限序列，数据元素的类型可以不同
B:数据元素的无限序列，元素个数可以是零个，也可以有多个
C:数据元素的有限序列，元素不可以是线性表
D:数据元素的有限序列，数据元素还可以是线性表
正确答案:【数据元素的有限序列，元素不可以是线性表】

2、单选题：以下关于线性表的说法中正确的是（）。
A:线性表中至少有一个元素
B:线性表中所有的元素都可以直接（或随机）存取
C:线性表中的元素必须按照从小到大或从大到小的次序排列
D:除第一个元素和最后一个元素外，其他每个元素有且仅有一个直接前趋元素和一个直接后继元素
正确答案:【除第一个元素和最后一个元素外，其他每个元素有且仅有一个直接前趋元素和一个直接后继元素】

3、单选题：以下关于线性表的说法中正确的是（)。
A:线性表中的元素还可以是线性表，但数据类型必须相同
B:每个元素有且仅有一个直接前趋，有且仅有一个直接后继
C:每个元素最少有一个直接前趋和一个直接后继
D:每个元素最多有一个直接前趋和一个直接后继
正确答案:【每个元素最多有一个直接前趋和一个直接后继】

4、单选题：如果线性表中的表元素既没有直接前趋，也没有直接后继，则该线性表中应有（）个表元素。
A:1
B:2
C:0

D:n
正确答案:【1】

5、单选题：在线性表中的每一个表元素都是数据对象，它们是不可再分的（）。
A:数据字段
B:数据记录
C:数据元素
D:数据项
正确答案:【数据元素】

6、单选题：顺序表是线性表的（）表示。
A:连续
B:有序
C:顺序存取
D:顺序存储
正确答案:【顺序存储】

7、单选题：以下关于顺序表的说法中正确的是（）。
A:顺序表和一维数组一样，都可以按下标随机（或直接）访问，顺序表还可以从某一指定元素开始，向前或向后逐个元素顺序访问
B:在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻
C:在顺序表中每一表元素的数据类型还可以是顺序表
D:顺序表利用一维数组表示，因此顺序表与一维数组在结构上一致，它们可以通用
正确答案:【顺序表和一维数组一样，都可以按下标随机（或直接）访问，顺序表还可以从某一指定元素开始，向前或向后逐个元素顺序访问】

8、单选题：顺序表的优点是（）。
A:插入操作的时间效率高
B:存储密度（存储利用率）高
C:删除操作的时间效率高
D:适用于各种逻辑结构的存储表示
正确答案:【存储密度（存储利用率）高】

9、单选题：以下关于单链表的叙述中错误的是（）。
A:结点的数据域用于存储线性表的一个数据元素
B:所有数据通过指针的链接而组织成单链表
C:结点的指针域用于存放一个指针，指示本结点所存储数据元素的直接后继元素所在结点的地址
D:单链表中各结点地址不可能连续
正确答案:【单链表中各结点地址不可能连续】

10、单选题：在单链表上实施插入和删除操作（）。
A:只需移动结点，不需改变结点指针
B:既需移动结点，又需改变结点指针
C:不需移动结点，不需改变结点指针
D:不需移动结点，只需改变结点指针
正确答案:【不需移动结点，只需改变结点指针】

11、单选题：在单链表最终增加头结点的目的是（ )。
A:使得链表遍历有一个终结结点
B:标识链表首元结点的位置
C:方便对链表的统一命名
D:方便插入、删除等运算的实现
正确答案:【方便插入、删除等运算的实现】

12、单选题：已知单链表中结点*q是结点*p的直接前趋，若在*q与*p之间插入结点*s,则应执行以下（）操作。
A:p->next=s->next;s->next=p;
B:q->next=s;s->next=p;
C:p->next=s;s->next=q;
D:s->next=p->next;p->next=s;
正确答案:【q->next=s;s->next=p;】

13、单选题：已知单链表中结点*p不是链尾结点，若在*p之后插入结点*s，则应执行以下（）操作。

A:s->next=p;p->next=s；
B:s->next=p->next;p=s;
C:s->next=p->next;p->next=s;
D:p->next=s；s->next=p;
正确答案:【s->next=p->next;p->next=s;】

14、判断题：顺序表中元素的逻辑顺序和物理顺序总是一致的。

A:对
B:错
正确答案:【对】

15、判断题：在单链表中插入新元素时， 必须先找到要插入位置的前一个结点。

A:错
B:对
正确答案:【对】

16、判断题：顺序表是静态存储结构 ， 而链表是动态存储结构。

A:对
B:错
正确答案:【错】

17、判断题：循环单链表可以仅在链表尾部设置链尾指针。

A:对
B:错
正确答案:【对】

18、判断题：在为顺序表分配连续的存储空间时， 必须预估该空间的最大容量。 但想估计得准确很不容易 ， 而为链表分配存储空间则不会为此烦恼。

A:错
B:对
正确答案:【对】

19、判断题：在顺序表中插入和删除时效率太低， 因此它不如链表好。

A:对
B:错
正确答案:【错】

第三章 单元测试

1、单选题：栈的插入和删除操作在（  ）进行。

A:任意位置
B:栈底
C:指定位置
D:栈顶
正确答案:【栈顶】

2、单选题：对一个初始为空的栈s执行操作Push(s,5),Push(s,2),Push(s,4),Pop(s,x),getTop(s,x)后，x的值应是（  ）。

A:5
B:0
C:4
D:2
正确答案:【2】

3、单选题：用S表示进栈操作，用X表示出栈操作，若元素的进栈顺序是1234，为了得到1342出栈顺序，相应的S和X的操作序列为（  ）。
A:SXSXSSXX
B:SXSSXXSX
C:SSSXXSXX
D:SXSSXSXX
正确答案:【SXSSXSXX】

4、单选题：假设一个栈的输入序列是1,2,3,4，则不可能得到的输出序列是（  ）。

A:4,3,2,1
B:1,2,3,4
C:1,3,4,2
D:4,1,2,3
正确答案:【4,1,2,3】

5、单选题：已知一个栈的进栈序列为1,2,3,…,n，其输出序列的第一个元素是i，则第j个出栈元素是（  ）。

A:不确定
B:j-i
C:n-i
D:j-i+1
正确答案:【不确定】

6、单选题：已知一个栈的进栈序列为1,2,3,…,n，其输出序列是p1,p2,p3,…,pn。若p1=n，则pi的值是（  ）。
A:不确定
B:n-i
C:i
D:n-i+1
正确答案:【n-i+1】

7、单选题：已知一个栈的进栈序列为1,2,3,…,n，其输出序列是p1,p2,p3,…,pn。若p1=3，则p2的值（  ）。

A:一定是1
B:一定是2
C:可能是1
D:可能是2
正确答案:【可能是2】

8、单选题：已知一个栈的进栈序列为p1,p2,p3,…,pn，其输出序列是1,2,3,…,n。若p3=1，则p1的值（  ）。

A:一定是3
B:可能是2
C:不可能是2
D:一定是2
正确答案:【不可能是2】

9、单选题：设一个循环队列Q[maxSize]的队头指针为front，队尾指针为rear，队列最大容量为maxSize，除此之外该队列再没有其他数据成员，则该队列的队满条件是（  ）。

A:Q.front==(Q.rear+1)%maxSize
B:Q.front==Q.rear
C:Q.front+Q.rear>=maxSize
D:Q.rear==(Q.front+1)%maxSize
正确答案:【Q.front==(Q.rear+1)%maxSize】

10、单选题：设循环队列的存储容量为maxSize，队头和队尾指针分别为front和rear。若有一个循环队列Q，可应用下列语句（  ）计算队列元素个数？
A:(Q.rear-Q.front+maxSize)%maxSize
B:(Q.rear-Q.front)%maxSize+1
C:Q.rear-Q.front+1
D:Q.rear-Q.front
正确答案:【(Q.rear-Q.front+maxSize)%maxSize】

11、单选题：一个队列的进队顺序是1,2,3,4，则该队列可能的输出序列是（  ）。

A:1,2,3,4
B:4,3,2,1
C:1,4,2,3
D:1,3,2,4
正确答案:【1,2,3,4】

12、单选题：对于链式队列，在执行插入操作时（  ）。

A:头、尾指针都要修改
B:头、尾指针可能都要修改
C:仅修改尾指针
D:仅修改头指针
正确答案:【头、尾指针可能都要修改】

13、单选题：最适合用作链式队列的链表是（  ）。

A:只带队头指针的循环单链表
B:带有队头指针和队尾指针的非循环单链表
C:只带队头指针的非循环单链表
D:带有队头指针和队尾指针的循环单链表
正确答案:【带有队头指针和队尾指针的非循环单链表】

14、单选题：最不适合用作链式队列的链表是（  ）。

A:带有队头指针的双向非循环链表
B:带有队头指针的双向循环链表
C:只带队尾指针的循环单链表
D:只带队尾指针的双向循环链表
正确答案:【带有队头指针的双向非循环链表】

15、单选题：设一个链式队列q的队头指针和队尾指针分别为front和rear，则判断队列空的条件是（  ）。
A:q.front!=NULL
B:q.rear==NULL
C:q.front==q.rear
D:q.front==NULL
正确答案:【q.front==NULL】

16、单选题：将递归算法转换成非递归算法时， 通常要借助的数据结构是（   ）。

A:队列
B:树
C:栈
D:线性表
正确答案:【栈】

17、单选题：栈与一般线性表的区别在于（）。
A:数据元素的类型不同
B:逻辑数据不同
C:运算是否受限制
D:数据元素的个数不同
正确答案:【运算是否受限制】

18、判断题：栈和队列都是顺序存取结构。

A:错
B:对
正确答案:【对】

19、判断题：对循环队列初始化时 · 要求队头指针与队尾指针指向同一个位置， 不论队列存储中什么位置都可以。

A:错
B:对
正确答案:【对】

20、判断题：栈 是 实 现 过 程 和 函 数 等 子 程 序 调 用 所 必 需 的 结 构。

A:对
B:错
正确答案:【对】

第四章 单元测试

1、单选题：字符串可定义为n(n≥0)个字符的有限（         ），其中，n是字符串的长度，表明字符串中字符的个数。

A:序列
B:集合
C:聚合
D:数列
正确答案:【序列】

2、单选题：串是一种特殊的线性表，其特殊性体现在（  ）。

A:可以顺序存储
B:数据元素是一个字符
C:数据元素可以是多个字符
D:可以链接存储
正确答案:【数据元素是一个字符】

3、单选题：有n个字符的字符串的非空子串个数最多有（     ）。
A:n(n+1)/2
B:n-1
C:n(n-1)/2
D:n
正确答案:【n(n+1)/2】

4、单选题：两个字符串相等的条件是（      ）。

A:两个串的长度相等，并且两个串包含的字符相同
B:两个串的长度相等
C:两个串包含的字符相等
D:两个串的长度相等，并且对应位置上的字符相同
正确答案:【两个串的长度相等，并且对应位置上的字符相同】

5、单选题：设有两个串：T和P，求P在T中首次出现的位置的运算叫做（     ）。

A:模式匹配
B:串替换
C:求子串
D:串连接
正确答案:【模式匹配】

6、单选题：在以下关于串的说法中正确的是（）。

A:用块链存储表示实现的串的结点大小为4,说明每个结点可存储4个字符
B:串长度是指串中不同字符的个数
C:子串是从串中抽取出若干字符组成的串
D:空串是由空格组成的串
正确答案:【用块链存储表示实现的串的结点大小为4,说明每个结点可存储4个字符】

7、单选题：设有两个串T和P，求P在T中首次出现的位置的运算叫做（）。
A:模式匹配
B:串替换
C:串连接
D:求子串
正确答案:【模式匹配】

8、单选题：设T=”aaaaaacaaaca”，P=“aaac”，使用BF算法的模式匹配过程需要执行的趟数为（）。
A:3
B:2
C:7
D:4
正确答案:【4】

9、判断题：应用 KMP 算法进行模式匹配时，next 函数值序列的产生仅与模式串有关。

A:错
B:对
正确答案:【对】

10、判断题：KMP 算法的特点是在模式匹配时指示目标串当前比对位置的指针不会回退。

A:错
B:对
正确答案:【对】

第五章 单元测试

1、单选题：

对稀疏矩阵进行压缩存储的目的是（  ）。

A:便于进行矩阵运算
B:降低运算的时间复杂度
C:节省存储空间
D:便于输入和输出
正确答案:【节省存储空间】

2、单选题：

一个稀疏矩阵采用压缩后，和直接采用二维数组存储相比会失去（   ）特性。

A:输入输出
B:顺序存储
C:其余选项都不对
D:随机存取
正确答案:【随机存取】

3、单选题：

稀疏矩阵常用的压缩存储方法有（   ）。

A:二维数组
B:三元组和散列表
C:散列表和十字链表
D:三元组和十字链表
正确答案:【三元组和十字链表          】

4、单选题：以下关于一维数组与顺序表不同之处的说法中错误的是（）。
A:前者的元素可以不连续存放，后者的元素必须相继存放
B:前者的元素数据类型相同，后者的元素数据类型可以不相同
C:前者既可以是逻辑结构也可以是存储结构，后者是线性表的存储结构
D:前者的长度不变，后者的长度可变
正确答案:【前者的元素数据类型相同，后者的元素数据类型可以不相同】

5、单选题：将一个n*n的对称矩阵A的对角线和对角线以上的部分按列优先存放于一个一维数组中，那么A有(    )个矩阵元素未被存于sa中。
A:n^2/2

B:n(n-1)/2
C:n(n+1)/2

D:n(n-1)
正确答案:【n(n-1)/2】

6、单选题：设一维数组 A[n]中每个元素占用 6 个存储单元，若A[5]的存储地址从 100 开始，则该数组的首地址是（ )。

A:30
B:76

C:64
D:95
正确答案:【64】

7、单选题：在二维数组A[9][10]中，每个数组元素占用3个存储单元，从首地址SA开始按行优先连续存放。在这种情况下，元素A[8][5]的起始地址为 （  ）。
A:SA+144
B:SA+255
C:SA+222
D:SA+141
正确答案:【SA+255】

8、单选题：设一个稀疏矩阵有1000行850列，其中有1000个非零元素。设每个整数占2字节，数据占4字节。则用三元组表存储该矩阵时所需字节数是（）。
A:8000

B:1000

C:18000
D:4000
正确答案:【8000
】

9、判断题：

二维数组是其数组元素为线性表的线性表。

A:错
B:对
正确答案:【错】

10、判断题：用一维数组存储特殊矩阵，可以简化对矩阵的存取操作。
A:错
B:对
正确答案:【错】

第六章 单元测试

1、单选题：树最合适用来表示（   ）。

A:有序数据元素
B:元素之间具有分支层次关系的数据
C:无序数据元素
D:元素之间无联系的数据
正确答案:【元素之间具有分支层次关系的数据】

2、单选题：一棵有n个结点的树的所有结点的度数之和为（   ）。

A:n-1
B:n+1
C:2n
D:n
正确答案:【n-1】

3、单选题：设树中某结点不是根结点，则离它最近的祖先结点是（      ）。

A:父结点的父结点
B:父结点
C:该结点本身
D:根结点
正确答案:【父结点】

4、单选题：在二叉树中某一结点的深度为3,高度为4,该树的髙度至少为（          ）。
A:7
B:6
C:5
D:8
正确答案:【6】

5、单选题：设一棵高度为h的满二叉树有n个结点，其中有m个叶结点，则（          ）。

A:h+m=2n
B:m=h-1
C:n=2^h-1
D:n=h+m
正确答案:【n=2^h-1】

6、单选题：具有33个结点的完全二叉树，有（    ）个度为1的结点。

A:1
B:12
C:16
D:0
正确答案:【0】

7、单选题：一颗有124个叶子结点的完全二叉树最多有（       ）个结点。
A:250
B:248
C:249
D:247
正确答案:【248】

8、单选题：一颗有129个叶结点的完全二叉树最少有（   ）个结点。
A:255
B:258
C:254
D:257
正确答案:【257】

9、单选题：如果二叉树T₂是由一棵树T₁转换而来的二叉树，那么T₁中结点的先根序列对应T₂的（     ）序列。

A:中序遍历
B:层次遍历
C:后序遍历
D:先序遍历
正确答案:【先序遍历          】

10、单选题：如果二叉树T₂是由一棵树T₁转换而来的二叉树，那么T₁中结点的后根序列对应T₂的（   ）序列。

A:层次遍历
B:先序遍历
C:后序遍历
D:中序遍历
正确答案:【中序遍历          】

11、单选题：一个深度为k且只有k个结点的二叉树，按照完全二叉树顺序存储的方式存放于一个一维数组A[n]中，那么n应至少是（）。

A:2^k-1
B:2k
C:2k+1
D:2^k
正确答案:【2^k-1】

12、单选题：二叉树的叶子结点在前序、中序和后序遍历过程中的相对顺序（  ）。
A:其余选项都不对
B:发生改变
C:无法确定
D:不发生改变
正确答案:【不发生改变】

13、单选题：设n、m为一棵二叉树上的两个结点，在中序遍历序列中，n在m前的条件是（）。

A:n在m右方
B:n是m的祖先
C:n是m的子孙
D:n在m左方
正确答案:【n在m左方】

14、单选题：在一棵二叉树中有两个结点n和m。在该二叉树的前序遍历序列中n在m之前，而在其后序遍历序列中n在m之后，则n和m的关系是（）。
A:n是m的子孙
B:n是m的左兄弟
C:n是m的祖先
D:n是m的右兄弟
正确答案:【n是m的祖先】

15、单选题：前序序列与中序序列正好相反的非空二叉树是（）。
A:右单支树
B:完全二叉树
C:满二叉树
D:左单支树
正确答案:【左单支树】

16、单选题：在中序线索二叉树中，指针 t 所指结点的左子树为空的充要条件是（） 。
A:其余选项都不对
B:t->ltag==1 且 t->lchild==NULL
C:t->ltag==1
D:t->lchild== NULL
正确答案:【t->ltag==1 且 t->lchild==NULL】

17、单选题：设森林F对应的二叉树为A，它有m个结点。A的根为p，p的右子树中结点个数为n，则森林F中第一棵树的结点个数是（）。
A:m-n
B:n+1
C:无法确定
D:m-n-1

正确答案:【m-n】

18、单选题：设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（）个。
A:n-1

B:n+1
C:n
D:n+2
正确答案:【n+1】

19、单选题：用n个权重构造出来的Huffman 树共有（）个结点。
A:2n-1

B:n+1
C:2n
D:2n+1
正确答案:【2n-1
】

20、单选题：设T是Huffman树，具有5个叶结点，树T的高度最高可以是（）。
A:3
B:4
C:6
D:5
正确答案:【5】

第七章 单元测试

1、单选题：在无向图中定义顶点的度为与它相关联的（    ）的数目。
A:边
B:权值
C:权
D:顶点
正确答案:【边】

2、单选题：具有 n 个顶点且每一对不同的顶点之间都有一条边的无向图被称为（）。