智慧树知到《数据结构与算法（天津理工大学）》章节测试答案

智慧树知到《数据结构与算法（天津理工大学）》章节测试答案
绪论单元测试
1、数据结构主要研究内存中数据组织和数据处理方法。
A.正确
B.错误
正确答案：正确
2、数据结构与算法课程的学习目标是（）。
A.提高计算思维能力
B.能利用所学数据结构和算法知识解决实际问题。
C.理解并掌握典型数据结构及七本运算的实现算法。
D.具备基本的算法设计与分析能力。
正确答案：提高计算思维能力；能利用所学数据结构和算法知识解决实际问题。理解并掌握典型数据结构及七本运算的实现算法。具备基本的算法设计与分析能力。
3、数据结构课程的学习重点是（）
A.掌握基本的算法分析方法。
B.掌握基本的算法设计方法
C.掌握各种数据结构的存储结构的设计与实现。
D.掌握各种数据结构的逻辑特性
正确答案：掌握基本的算法分析方法。掌握基本的算法设计方法；掌握各种数据结构的存储结构的设计与实现。掌握各种数据结构的逻辑特性
第一章单元测试
1、算法分析主要分析的是算法的（）
A.空间复杂性
B.正确性
C.可读性
D.时间复杂性
正确答案：空间复杂性；时间复杂性
2、数据结构是数据对象与对象中数据元素之间关系的集合。
A.正确
B.错误
正确答案：正确
3、数据元素是数据的最小单位。
A.正确
B.错误
正确答案：错误
4、数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要而建立的。
A.正确
B.错误
正确答案：正确
5、算法和程序没有区别，所以在数据结构中二者是通用的。
A.正确
B.错误
正确答案：错误
6、数据结构中，与所使用的计算机无关的是数据的（）结构
A.存储
B.逻辑
C.物理
D.物理与存储
正确答案：逻辑
7、算法分析的目的是（）
A.研究算法中的输入和输出的关系
B.分析算法的效率以求改进
C.分析算法的易懂性和文档性
D.找出数据结构的合理性
正确答案：分析算法的效率以求改进
8、设x，y，n为正整数，下列程序片段的渐进时间复杂度是（）
x=1；y=1； while（x + y <= n）{ if（x > y）y++； else x++；}
A.O（（2/3 ）n）
B.O（log2n）
C.O（n2）
D.O（n）
正确答案：O（n）
9、在数据结构中，从逻辑上可以把数据结构分成（）
A.动态结构
B.静态结构
C.线性结构
D.非线性结构
正确答案：线性结构；非线性结构
10、计算机算法必须具备输入、输出和（）、（）、（）5个特性。
A.可行性
B.有穷性
C.可扩充性
D.确定性
正确答案：可行性；有穷性；确定性
第二章单元测试
1、链表的物理存储结构具有同链表一样的顺序。
A.正确
B.错误
正确答案：错误
2、顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
A.正确
B.错误
正确答案：错误
3、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
A.正确
B.错误
正确答案：错误
4、在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。
A.正确
B.错误
正确答案：正确
5、一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）
A.110
B.108
C.120
D.100
正确答案：108
6、 链式存储结构所占存储空间（）
A.分两部分，一部分存结点值，另一部分存表示结点间关系的指针
B.只有一部分，存放结点值
C.分两部分，一部分存放结点值，另一部分存放结点所占单元数
D.只有一部分，存储表示结点间关系的指针
正确答案：分两部分，一部分存结点值，另一部分存表示结点间关系的指针
7、单链表的每个结点中包括一个指针next，它指向该结点的后继结点。现要将指针q指向的新结点插入到指针p指向的单链表结点之后，下面的操作序列中哪一个是正确的？
A.p->next=q->next； q=p->next
B.q->next=p->next； p->next=q
C.q=p->next； p->next=q->next
D.p->next=q； q->next=q->next
正确答案：q->next=p->next； p->next=q
8、设单链表中结点的结构为（data， next）。若想删除结点p的直接后继，则应执行下列哪一个操作？
A.p->next = p->next->next
B.p->next = p->next
C.p= p->next；p->next = p->next->next
D.p = p->next->next
正确答案：p->next = p->next->next
9、设单循环链表中结点的结构为（data， next），且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作？
A.s = rear；rear = rear->next；free（s）
B.rear = rear->next；free（rear）
C.rear = rear->next->next； free（rear）
D.s = rear->next->next；rear->next = s->next；free（s）
正确答案：s = rear->next->next；rear->next = s->next；free（s）
10、设双向循环链表中结点的结构为（data， prior， next）。若想在指针p所指结点之后插入指针s所指结点，则应执行下列哪一个操作？
A.p->next=s；p->next->prior=s；s->prior=p；s->next=p->next
B.s->prior=p；s->next=p->next；p->next=s；p->next->prior=s
C.s->prior=p；s->next=p->next；p->next->prior=s；p->next=s
D.p->next=s；s->prior=p；p->next->prior=s；s->next=p->next
正确答案：s->prior=p；s->next=p->next；p->next->prior=s；p->next=s
第三章单元测试
1、 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。
A.正确
B.错误
正确答案：正确
2、队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
A.正确
B.错误
正确答案：错误
3、对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。
A.正确
B.错误
正确答案：正确
4、一个栈的输入序列是12345，则栈的输出序列不可能是12345。
A.正确
B.错误
正确答案：错误
5、两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
A.正确
B.错误
正确答案：正确
6、向栈顺序输入以下元素6，5，4，3，2，1，问下列（）是合法的出栈序列。
A.4，3，1，2，6，5
B.3，5，1， 2，4，6
C.5，4，3，6，1，2
D.3，4，6，5，2，1
正确答案：5，4，3，6，1，2
7、设链式栈中结点结构为（data，next），且top是指顶指针。要在链式栈中插入一个由指针s所指的结点，应执行下列哪个操作？
A.s->next=top->next；top->next=s
B.s->next=top；top=s
C.s->next=top；top=top->next
D.top->next=s
正确答案：s->next=top；top=s
8、数组Q[n］用来表示一个循环队列，front为当前队列头元素位置，rear为队尾元素的下一个位置，试问判断队列满的条件应是下列哪一个语句？
A.Q.front-Q.rear==n
B.Q.front+Q.rear==n
C.Q.front ==（Q.rear+1）% n
D.Q.front==Q.rear
正确答案：Q.front ==（Q.rear+1）% n
9、字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成多少个不同的字符串？
A.5
B.4
C.2
D.6
正确答案：5
10、数组Q[n]用来表示一个循环队列，front为当前队列头元素位置，rear为队尾元素的下一个位置，试问判断队列空的条件应是下列哪一个语句？
A.Q.front+Q.rear==n
B.Q.front ==（Q.rear+1）% n
C.Q.front-Q.rear==n
D.Q.front==Q.rear
正确答案：Q.front==Q.rear
第四章单元测试
1、插入和删除操作是数据结构中基本的两种操作，所以这两种操作在数组中也经常使用。
A.正确
B.错误
正确答案：错误
2、数组中的所有数据元素具有相同的数据类型。
A.正确
B.错误
正确答案：正确
3、数组是同类型值的集合。
A.正确
B.错误
正确答案：错误
4、数组中的每个数据元素都有一组唯一的下标。
A.正确
B.错误
正确答案：正确
5、数组是一种随机存储结构。可随机存取数组中的任意数据元素。
A.正确
B.错误
正确答案：正确
6、稀疏矩阵的压缩存储方法是只存储非零元素。
A.正确
B.错误
正确答案：正确
7、一维数组与线性表的区别是（）
A.两者长度均可变
B.前者长度固定，后者长度可变
C.两者长度均固定
D.后者长度固定，前者长度可变
正确答案：前者长度固定，后者长度可变
8、有一个二维数组A，行下标的范围是0到8，列下标的范围是1到5，每个数组元素用相邻的4个字节存储。存储器按字节编址。假设存储数组元素A[0，1]的第一个字节的地址是0，存储数组A的最后一个元素的第一个字节的地址是（）
A.176
B.184
C.132
D.188
正确答案：176
9、设有一个10阶的对称矩阵A采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每个元素占1个地址空间，则a85的地址为（）
A.40
B.18
C.33
D.13
正确答案：33
10、一个稀疏矩阵采用压缩后，和直接采用二维数组存储相比会失去（）特性。
A.随机存取
B.不失去特性
C.输入输出
D.顺序存储
正确答案：随机存取
第五章单元测试
1、在定义一个过程或函数时，出现直接或者间接调用自己的成分，称之为递归。
A.正确
B.错误
正确答案：正确
2、单链表可以看作是一种递归数据结构。
A.正确
B.错误
正确答案：正确
3、递归算法一定比非递归算法花费更多的时间。
A.正确
B.错误
正确答案：错误
4、递归求解过程要把一个不能或不好直接求解的“大问题”随意分解为一个或几个“小问题”来解决。
A.正确
B.错误
正确答案：错误
5、递归出口是递归的结束，是可以直接求解的问题。
A.正确
B.错误
正确答案：正确
6、一个问题如能用“分治法”解决，就可以用递归算法实现。
A.正确
B.错误
正确答案：正确
7、递归数据结构的数据处理特别适合用递归算法实现。
A.正确
B.错误
正确答案：正确
8、递归函数的基本结构是一个（）结构的结构
A.顺序
B.if-else
C.do-while
D.for循环
正确答案：if-else
9、递归算法如何转换为非递归算法？
A.可以用队列模拟执行过程来转换
B.可以直接将递归项去掉
C.可以用栈模拟执行过程来转换
D.可以直接用循环代替递归项
正确答案：可以用栈模拟执行过程来转换
10、一个递归模型由哪两部分构成？
A.函数名
B.形参
C.递归出口
D.递归项
正确答案：递归出口；递归项
第六章单元测试
1、二叉树中每个结点的两棵子树是有序的。
A.正确
B.错误
正确答案：正确
2、用二叉链表存储包含n个结点的二叉树，结点的2n个指针区域中有n-1个为空指针。
A.正确
B.错误
正确答案：错误
3、对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i-1个结点。
A.正确
B.错误
正确答案：错误
4、具有12个结点的完全二叉树有5个度为2的结点。
A.正确
B.错误
正确答案：正确
5、下面关于二叉树的叙述正确的是（）
A.二叉树中，任何一个结点的左子树和右子树上的结点个数一定相等
B.一棵二叉树中叶子结点的个数等于度为2的结点个数加1
C.一棵二叉树中的结点个数大于0
D.二叉树中任何一个结点要么是叶，要么恰有两个子女
正确答案：一棵二叉树中叶子结点的个数等于度为2的结点个数加1
6、二叉树是非线性数据结构，所以（）
A.顺序存储结构和链式存储结构都能存储
B.顺序存储结构和链式存储结构都不能使用
C.它不能用链式存储结构存储
D.它不能用顺序存储结构存储
正确答案：顺序存储结构和链式存储结构都能存储
7、把一棵树转换为二叉树后，这棵二叉树的形态是（）
A.唯一的
B.有多种
C.有多种，但根结点都没有右孩子
D.有多种，但根结点都没有左孩子
正确答案：唯一的
8、在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序（）
A.中序和后序相同，而与先序不同
B.先序和中序相同，而与后序不同
C.完全相同
D.都不相同
正确答案：完全相同
9、二叉树的先序遍历为EFHIGJK，中序遍历为HFIEJKG，则该二叉树根的右子树的根是（）
A.F
B.E
C.G
D.H
正确答案：G
10、在下列存储形式中，哪个是树的存储形式（）
A.孩子兄弟示法
B.顺序存储表示法
C.孩子链表表示法
D.双亲表示法
正确答案：孩子兄弟示法；孩子链表表示法；双亲表示法
第七章单元测试
1、有向图中顶点的入度是指以该顶点为尾的弧的数目。
A.正确
B.错误
正确答案：错误
2、用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。
A.正确
B.错误
正确答案：正确
3、有n（n≥1） 个顶点的无向图最少有n-1条边。
A.正确
B.错误
正确答案：错误
4、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。
A.1/2
B.4
C.1
D.2
正确答案：1
5、有8个结点的无向连通图最少有（）条边。
A.8
B.6
C.5
D.7
正确答案：7
6、用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的。
A.树
B.队列
C.栈
D.图
正确答案：队列
7、任何一个无向连通图的最小生成树（）
A.可能不存在
B.一棵或多棵
C.一定有多棵
D.只有一棵
正确答案：一棵或多棵
8、下列哪一种图的邻接矩阵是对称矩阵？
A.AOV网
B.AOE网
C.有向图
D.无向图
正确答案：无向图
9、图的深度优先遍历类似于二叉树的（）
A.中序遍历
B.层序遍历
C.先序遍历
D.后序遍历
正确答案：先序遍历
10、对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则有边链表中边结点的总数为（）
A.e/2
B.e
C.2e
D.n+e
正确答案：2e
第八章单元测试
1、对关键字值有序的链表进行查找的最佳方法是折半查找。
A.正确
B.错误
正确答案：错误
2、散列法存储的基本思想是由关键字的值决定数据的存储地址。
A.正确
B.错误
正确答案：正确
3、在表长为ｎ的链表中进行线性查找，它的平均查找长度为（）
A.n2
B.（ｎ＋１）/２
C.log2（n+1）-1
D.n
正确答案：（ｎ＋１）/２
4、对23个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字。
A.6
B.5
C.4
D.3
正确答案：4
5、链表适用于（）查找
A.二分
B.随机
C.顺序，也能二分法
D.顺序
正确答案：顺序
6、设有100个节点，用二分法查找时，最大比较次数是多少？
A.10
B.9
C.8
D.7
正确答案：7
7、折半查找与二叉搜索树的时间性能（）
A.完全不同
B.相同
C.有时不相同
D.数量级都是O（log2n）
正确答案：有时不相同
8、在二叉排序树中，每个结点的关键码值（）
A.比左子树所有结点的关键码值大，比右子树所有结点的关键码值小
B.比左子树所有结点的关键码值小，比右子树所有结点的关键码值大
C.比左右子树的所有结点的关键码值都大
D.与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系
正确答案：比左子树所有结点的关键码值大，比右子树所有结点的关键码值小
9、散列存储中碰撞（冲突）指的是（）
A.两个元素具有相同序号
B.两个元素的关键码值不同，而非码属性相同
C.负载因子过大
D.不同关键码值对应到相同的存储地址
正确答案：不同关键码值对应到相同的存储地址
10、下列处理冲突的方法是（）
A.除余法
B.线性探查法
C.链地址法
D.二次探查法
正确答案：线性探查法；链地址法；二次探查法
第九章单元测试
1、大多数排序算法都有两个基本的操作：比较和移动。
A.正确
B.错误
正确答案：正确
2、对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是O（nlog2n）。
A.正确
B.错误
正确答案：错误
3、将5个不同的数据进行排序，至多需要比较多少次？
A.10
B.20
C.8
D.9
正确答案：10
4、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）
A.插入排序
B.希尔排序
C.冒泡排序
D.选择排序
正确答案：插入排序
5、对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。
A.元素基本有序
B.元素无序
C.从大到小排列好的
D.从小到大排列好的
正确答案：从大到小排列好的
6、快速排序在下列哪种情况下最易发挥其长处。
A.被排序的数据中的最大值和最小值相差悬殊
B.被排序的数据完全无序
C.被排序的数据中含有多个相同排序码
D.被排序的数据已基本有序
正确答案：被排序的数据完全无序
7、若一组记录的排序码为（46， 79， 56， 38， 40， 84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）
A.40， 38，46， 56， 79， 84
B.40， 38， 46， 84， 56， 79
C.40， 38， 46， 79， 56， 84
D.38， 40， 46， 56， 79， 84
正确答案：40， 38，46， 56， 79， 84
8、若一组记录的排序码为（46， 79， 56， 38， 40， 84），则利用堆排序的方法建立的初始堆为（）。
A.79， 46， 56， 38， 40， 84
B.84， 56， 79， 40， 46， 38
C.84， 79， 56， 38， 40， 46
D.84， 79， 56， 46， 40， 38
正确答案：84， 79， 56， 38， 40， 46
9、在所有排序算法中，关键码比较次数与记录的初始排序次序无关的是哪个？
A.冒泡排序
B.直接选择排序
C.直接插入排序
D.希尔排序
正确答案：直接选择排序
10、在下面内部排序中，要求附加的内存容量最大的是（）。
A.堆排序
B.归并排序
C.冒泡排序
D.希尔排序
正确答案：归并排序