智慧树知到《算法与数据结构》章节测试答案

智慧树知到《算法与数据结构》章节测试答案
绪论单元测试
1、学好算法与数据结构的关键在于多多实践。
A.正确
B.错误
正确答案：正确
第一章单元测试
1、数据结构是（）
A.一种数据类型
B.数据的存储结构
C.一组性质相同的数据元素的集合
D.相互之间存在一种或多种特定关系的数据元素的集合
正确答案：相互之间存在一种或多种特定关系的数据元素的集合
2、下列说法错误的是（）
A.数据是指描述客观事物的特征及活动所采用的符号形式
B.数据元素是数据的基本单位
C.数据在计算机存储器内的存在形式称为机外表示
D.数据处理方式总是与数据的表示形式相联系
正确答案：数据在计算机存储器内的存在形式称为机外表示
3、算法的描述方法只有语言方式。
A.正确
B.错误
正确答案：错误
4、下列关于算法说法错误的是（）
A.算法是对特定问题求解步骤的一种描述
B.算法是指令的有限序列
C.算法是在存储结构上的操作实现方法
D.算法就是数学中的计算方法
正确答案：算法就是数学中的计算方法
5、有哪几种存储结构？
A.顺序存储方式
B.链式存储方式
C.索引存储方式
D.散列存储方式
正确答案：顺序存储方式；链式存储方式；索引存储方式；散列存储方式
6、算法的效率主要是指（）
A.算法的空间效率
B.算法的时间效率
C.算法的空间效率和时间效率
D.其他选项都不对
正确答案：算法的空间效率和时间效率
7、 在数据结构的讨论中把数据结构从逻辑上分为（）
A.内部结构与外部结构
B.静态结构与动态结构
C.紧凑结构与非紧凑结构
D.线性结构与非线性结构
正确答案：线性结构与非线性结构
8、指出下列程序段的时间复杂度（）
sum=1；for（i=0；sumsum+=1。
A.O（n）
B.O（n*n）
C.O（1）
D.O（0）
正确答案：O（n）
9、树形结构中元素之间存在（）关系
A.一对一
B.一对多
C.多对多
D.没有关系
正确答案：一对多
10、图形结构中元素之间存在（）关系
A.一对一
B.一对多
C.多对多
D.没有关系
正确答案：多对多
第二章单元测试
1、带头结点的单链表head为空的判定条件是（）
A.head= =NULL
B.head->next= =NULL
C.head->next= =head
D.head!=NULL
正确答案：head->next= =NULL
2、循环链表的主要优点是（）。
A.不再需要头指针
B.已知某结点位置后能容易找到其直接前驱
C.在进行插入、删除运算时能保证链表不断开
D.在表中任一结点出发都能扫描整个链表
正确答案：在表中任一结点出发都能扫描整个链表
3、线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）
A.必须是连续的
B.部分地址必须是连续的
C.一定是不连续的
D.连续或不连续都可以
正确答案：连续或不连续都可以
4、若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。
A.顺序表
B.单链表
C.双链表
D.循环单链表
正确答案：顺序表
5、在一个长度为n的顺序表中，在第i个元素之前插入一个新元素时，需向后移动（）个元素
A.n-i
B.n-i+1
C.n-i-1
D.i
正确答案：n-i+1
6、线性表的顺序存储结构是一种（）存储结构。
A.随机存取
B.顺序存取
C.索引存取
D.散列存取
正确答案：随机存取
7、在双向循环链表中，在p指针所指的结点后插入一个指针q所指向的新结点，修改指针的操作是（）。
A.p->next=q；q->prior=p；p->next->prior=q；q->next=q
B.p->next=q；p->next->prior=q；q->prior=p；q->next=p->next
C.q->prior=p；q->next=p->next；p->next->prior=q；p->next=q
D.q->next=p->next；q->prior=p；p->next=q；p->next=q
正确答案：q->prior=p；q->next=p->next；p->next->prior=q；p->next=q
8、在下列对顺序表进行的操作中，算法时间复杂度为O（1）的是（）。（答案中的i均为合法输入）
A.访问第i个元素的前驱
B.在第i个元素之后插入一个新元素
C.删除第i个元素
D.对顺序表中元素进行排序
正确答案：访问第i个元素的前驱
9、已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（）。
A.s->next=p；q->next=s->next
B.p->next=s->next；s->next=q
C.s->next=q；p->next=s->next
D.q->next=s->next；s->next=p
正确答案：q->next=s->next；s->next=p
10、在表长为n的顺序表中，当在任何位置删除一个元素的概率相同时，删除一个元素所需移动的平均个数为（）。
A.（n-1）/2
B.（n+1）/2
C.n/2
D.n
正确答案：（n-1）/2
第三章单元测试
1、栈和队列的共同点是（）
A.都是先进后出
B.都是先进先出
C.只允许在端点处插入和删除元素
D.没有共同点
正确答案：只允许在端点处插入和删除元素
2、一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是（）
A.edcba
B.decba
C.dceab
D.abcde
正确答案：dceab
3、设计一个判别表达式中括号是否配对的算法，采用（）数据结构最佳。
A.顺序表
B.链表
C.队列
D.栈
正确答案：栈
4、若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0，3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（）。
A.1和5
B.2和4
C.4和2
D.5和1
正确答案：2和4
5、循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（）
A.（rear-front+m）%m
B.rear-front+1
C.rear-front-1
D.rear-front
正确答案：（rear-front+m）%m
6、一个顺序栈S，其栈顶指针为top，则将元素e入栈的操作是（）。（注：top指向待插入位置）
A.*S->top=e；S->top++
B.S->top++；*S->top=e
C.*S->top=e
D.S->top=e
正确答案：*S->top=e；S->top++
7、在解决计算机主机和打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（）结构。
A.堆栈
B.队列
C.数组
D.线性表
正确答案：队列
8、当用大小为N的数组存储顺序循环队列时，该队列的最大长度为（）。
A.N
B.N+1
C.N-1
D.N-2
正确答案：N-1
9、依次在初始为空的队列中插入元素a，b，c，d以后，紧接着做了两次删除操作，此时的队头元素是（）。
A.a
B.b
C.c
D.d
正确答案：c
10、向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行（）。（不带空的头结点）
A.HS->next=s
B.s->next= HS->next； HS->next=s
C.s->next= HS； HS= HS->next
D.s->next= HS； HS=s
正确答案：s->next= HS； HS=s
第四章单元测试
1、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a[1][1]为第一元素，其存储地址为1，每个元素占一个地址空间，则a[8][5]的地址为（）。
A.13
B.33
C.18
D.40
正确答案：33
2、设有数组A[i，j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为（）
A.BA+141
B.BA+180
C.BA+222
D.BA+225
正确答案：BA+180
3、将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A[66][65]（即该元素下标i=66，j=65），在B数组中的位置K为（）。
A.198
B.195
C.197
D.193
正确答案：195
4、二维数组A的每个元素是由6个字符组成的串，其行下标i=0，1，…，8，列下标j=1，2，…，10。若A按行先存储，元素A[8，5]的起始地址与当A按列先存储时的元素（）的起始地址相同。设每个字符占一个字节
A.8
B.5
C.3
D.10
正确答案：5
5、设二维数组A[1..m，1..n]（即m行n列）按行存储在数组B[1..m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为（）
A.（i-1）*n+j
B.（i-1）*n+j-1
C.i*（j-1）
D.j*m+i-1
正确答案：（i-1）*n+j
6、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）
A.60
B.66
C.18000
D.33
正确答案：66
7、设有两个串p和q，求q在p中首次出现的位置的运算称作（）。
A.连接
B.模式匹配
C.求子串
D.求串长
正确答案：模式匹配
8、常对数组进行的两种基本操作是（）。
A.建立与删除
B.索引和修改
C.对数据元素的存取和修改
D.查找与索引
正确答案：对数据元素的存取和修改
9、二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是（）。
A.80
B.100
C.240
D.270
正确答案：240
10、二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为（）。
A.SA+141
B.SA+180
C.SA+222
D.SA+225
正确答案：SA+180
第五章单元测试
1、引入二叉线索树的目的是（）。
A.加快查找结点的前驱或后继的速度
B.为了能在二叉树中方便的进行插入与删除
C.为了能方便的找到双亲
D.使二叉树的遍历结果唯一
正确答案：加快查找结点的前驱或后继的速度
2、n个结点的线索二叉树上含有的线索数为（）。
A.2n
B.n－l
C.n＋l
D.n
正确答案：n＋l
3、由3 个结点可以构造出多少种不同的二叉树（）。
A.2
B.3
C.4
D.5
正确答案：5
4、已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为（）。
A.-A+B*C/DE
B.-A+B*CD/E
C.-+*ABC/DE
D.-+A*BC/DE
正确答案：-+A*BC/DE
5、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）。
A.9
B.11
C.15
D.不确定
正确答案：11
6、有关二叉树下列说法正确的是（）。
A.二叉树的度为2
B.一棵二叉树的度可以小于2
C.二叉树中至少有一个结点的度为2
D.二叉树中任何一个结点的度都为2
正确答案：一棵二叉树的度可以小于2
7、一个具有1025个结点的二叉树的高h为（）。
A.11
B.10
C.11至1025之间
D.10至1024之间
正确答案：11至1025之间
8、若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（）遍历方法最合适。
A.前序
B.中序
C.后序
D.按层次
正确答案：后序
9、若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为（）
A.X的双亲
B.X的右子树中最左的结点
C.X的右子树的根
D.X的左子树中最右结点
正确答案：X的左子树中最右结点
10、二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历：HFIEJKG 。该二叉树根的右子树的根是（）。
A.E
B.F
C.G
D.H
正确答案：G
第六章单元测试
1、无向图G=（V，E），其中：V={a，b，c，d，e，f}，E={（a，b），（a，e），（a，c），（b，e），（c，f），（f，d），（e，d）}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。
A.a，b，e，c，d，f
B.a，c，f，e，b，d
C.a，e，b，c，f，d
D.a，e，d，f，c，b
正确答案：a，e，d，f，c，b
2、已知有向图G=（V，E），其中V={V1，V2，V3，V4，V5，V6，V7}，
E={，，，，，，，，}，G的拓扑序列是（）。
A.V1，V3，V4，V6，V2，V5，V7
B.V1，V3，V2，V6，V4，V5，V7
C.V1，V3，V4，V5，V2，V6，V7
D.V1，V2，V5，V3，V4，V6，V7
正确答案：V1，V3，V4，V6，V2，V5，V7
3、要连通具有n个顶点的有向图，至少需要（）条边。
A.n-l
B.n
C.n+1
D.2n
正确答案：n
4、在n个结点的无向图中，若边数大于n-1，则该图必是连通图。（）
A.正确
B.错误
正确答案：错误
5、邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。（）
A.正确
B.错误
正确答案：错误
6、设无向图的顶点个数为n，则该图最多有（）条边。
A.n-1
B.n（n-1）/2
C.n（n+1）/2
D.n*n
正确答案：n（n-1）/2
7、下列哪一种图的邻接矩阵是对称矩阵？（）
A.有向图
B.无向图
C.AOV网
D.AOE网
正确答案：无向图
8、下面哪一方法可以判断出一个有向图是否有环（回路）：（）。
A.深度优先遍历
B.拓扑排序
C.求最短路径
D.求关键路径
正确答案：拓扑排序
9、对于一个有向图，若一个顶点的入度为k1，、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为
A.k1
B.k2
C.k1+k2
D.k1-k2
正确答案：k1
10、下列说法不正确的是（）。
A.图的遍历是从给定的源点出发每一个顶点仅被访问一次
B.遍历的基本算法有两种：深度遍历和广度遍历
C.图的深度遍历不适用于有向图
D.图的深度遍历是一个递归过程
正确答案：图的深度遍历不适用于有向图
第七章单元测试
1、一个有序表为（1，3，9，12，32，41，45，62，75，77，82，95，100），当采用折半查找方法查找值32时，查找成功需要的比较次数是（）。
A.2
B.3
C.4
D.8
正确答案：3
2、设散列表长m=14，散列函数H（K）=K％11，已知表中已有4个结点：r（15）=4； r（38）=5； r（61）=6；r（84）=7，其他地址为空，如用二次探测法处理冲突，关键字为49的结点地址是（）。
A.8
B.3
C.5
D.9
正确答案：9
3、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0右孩子的平衡因子为1，则应作（）型调整以使其平衡。
A.LL
B.LR
C.RL
D.RR
正确答案：RL
4、当在一个有序的顺序表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（）。
A.必定快
B.不一定
C.取决于表递增还是递减
D.在大部分情况下要快
正确答案：在大部分情况下要快
5、如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则应采用的查找方法是（）
A.顺序查找
B.二分法查找
C.分块查找
D.都不行
正确答案：分块查找
6、在采用线性探查法处理冲突的散列表中进行查找，查找成功时所探测位置上的键值（）
A.一定都是同义词
B.一定都不是同义词
C.不一定是同义词
D.无任何关系
正确答案：不一定是同义词
7、对一棵二叉排序树进行（） 遍历，可以得到一个键值从小到大次序排列的有序序列。
A.先序
B.中序
C.后序
D.层序
正确答案：中序
8、分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（）。
A.（100，80， 90， 60， 120，110，130）
B.（100，60， 80， 90， 120，110，130）
C.（100，120，110，130，80， 60， 90）
D.（100，80， 60， 90， 120，130，110）
正确答案：（100，60， 80， 90， 120，110，130）
9、在查找过程中，若同时还要做插入、删除操作，这种查找称为
A.静态查找
B.动态查找
C.内部查找
D.外部查找
正确答案：动态查找
第八章单元测试
1、对n个不同的关键字由小到大进行冒泡排序，在下列（）情况下比较的次数最多。
A.从小到大排列好的
B.从大到小排列好的
C.元素无序
D.元素基本有序
正确答案：从大到小排列好的
2、下列关键字序列中，（）是堆。
A.16，72，31，23，94，53
B.94，23，31，72，16，53
C.16，23，53，31，94，72
D.16，53，23，94，31，72
正确答案：16，23，53，31，94，72
3、下列排序算法中，（）不能保证每趟排序至少能将一个元素放到其最终的位置上。
A.希尔排序
B.快速排序
C.冒泡排序
D.堆排序
正确答案：希尔排序
4、数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的（）的两趟排序后的结果。
A.选择排序
B.冒泡排序
C.插入排序
D.堆排序
正确答案：插入排序
5、稳定的排序方法是（）。
A.直接插入排序和快速排序
B.折半插入排序和起泡排序
C.简单选择排序和四路归并排序
D.树形选择排序和shell排序
正确答案：折半插入排序和起泡排序
6、设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用（）排序法。
A.冒泡排序
B.快速排序
C.堆排序
D.基数排序
正确答案：堆排序
7、 一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。
A.38，40，46，56，79，84
B.40，38，46，79，56，84
C.40，38，46，56，79，84
D.40，38，46，84，56，79
正确答案：40，38，46，56，79，84
8、下述几种排序方法中，平均查找长度最小的是（）。
A.插入排序
B.快速排序
C.选择排序
D.归并排序
正确答案：快速排序
9、在待排序的元素序列基本有序的前提下，效率最高的排序方法是（）。
A.插入排序
B.快速排序
C.选择排序
D.归并排序
正确答案：插入排序
10、排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列的一端的方法，称为（）。
A.希尔排序
B.快速排序
C.选择排序
D.归并排序
正确答案：选择排序