2021知到答案 算法与数据结构 智慧树网课章节测试答案

绪论 章节测试

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;sum<n;i++) <br=””> sum+=1;</n;i++)>
选项：
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={<v1,v2>,<v1,v3>,<v1,v4>,<v2,v5>,<v3,v5>,<v3,v6>,<v4,v6>,<v5,v7>,<v6,v7>},G</v6,v7></v5,v7></v4,v6></v3,v6></v3,v5></v2,v5></v1,v4></v1,v3></v1,v2>的拓扑序列是（ ）。
选项：
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:归并排序
答案: 【选择排序】[/$]