2020年智慧树知道网课《算法与数据结构》课后章节测试满分答案

绪论单元测试'【判断题】Q分）【判断题】（1分）学好算法与数据结构的关键在于多多实践A.对B.错第一章测试【单选题】（1分）数据结构是（ ）A.一组性质相同的数据元素的集合B.一种数据类型C.数据的存储结构D.相互之间存在一种或多种特定关系的数据元素的集合会考答案【单选题】（1分）下列说法的是（）A.数据在计算机存储器内的存在形式称为机外表示B.数据元素是数据的基本单位C.数据处理方式总是与数据的表示形式相联系D.数据是指描述客观事物的特征及活动所采用的符号形式参考答案【判断题】（1分）算法的描述方法只有语言方式。A.错B.对参考答案4【单选题】（1分）下列关于算法说法的是（）A.算法就是数学中的计算方法B.算法是指令的有限序列C.算法是对特定问题求解步骤的一种描述D.算法是在存储结构上的操作实现方法参考答案【多选题】（1分）有哪几种存储结构?AA.链式存储方式BB.散列存储方式C.索引存储方式D.顺序存储方式参考答案\Bcr）6【单选题】（1分）算法的效率主要是指（）A.其他选项都不对B.算法的空间效率C.算法的时间效率D.算法的空间效率和时间效率会考答案【单选题】（1分）在数据结构的讨论中把数据结构从逻辑上分为（）A.静态结构与动态结构B.内部结构与外部结构C.紧凑结构与非紧凑结构D.线性结构与非线性结构参考答案8【单选题】（1分）指出下列程序段的时间复杂度（）sum=1；for（i=0;sum<n;i++）sum+=1;A.O（1）B.O(n)C.O(0)D.O(n*n)参考答案B【单选题】（1分）树形结构中元素之间存在（）关系A.一对一B.没有关系C.多对多D.一对多参考答案D【单选题】（1分）图形结构中元素之间存在（）关系A.一对多B.没有关系C.多对多D.一对一参考答案第二章测试【单选题】（1分）带头结点的单链表head为空的判定条件是（）A.head->next==NULLB.head==NULLC.head->next==headD.head!=NULL参考答案【单选题】（1分）循环链表的主要优点是（）。A.在进行插入、删除运算时能保证链表不断开B.巳知某结点位置后能容易找到其直接前驱C.在表中任一结点出发都能扫描整个链表D.不再需要头指针参考答案【单选题】（1分）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）A.必须是连续的B.一定是不连续的C.连续或不连续都可以D.部分地址必须是连续的参考答案【单选题】（1分）若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。A.循环单链表B.单链表C.顺序表D.双链表参考答案5【单选题】（1分）在一个长度为n的顺序表中，在第i个元素之前插入一个新元素时，需向后移动（）个元素A.n-i-1B.n-i+1C.iD.n-i会考答案6【单选题】（1分）线性表的顺序存储结构是一种（）存储结构。A.索引存取B.顺序存取C.散列存取D.随机存取参考答案【单选题】（1分）在双向循环链表中，在p指针所指的结点后插入一个指针q所指向的新结点，修改指针的操作是（）。A.p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;B.p->next=q;q->prior=p;p->next->prior=q;q->next=q;C.q->next=p->next;q->prior=p;p->next=q;p->next=q;D.q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;参考答案8【单选题】（1分）在下列对顺序表进行的操作中，算法时间复杂度为0（1）的是（）。（答案中的i均为合法输入）A.访问第i个元素的前驱B.在第i个元素之后插入一个新元素C.对顺序表中元素进行排序D.删除第i个元素参考答案9【单选题】（1分）已知指针P和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（）。A.q->next=s->nexts->next=p；B.s->next=p；q->next=s->nextC.p->next=s->next；s->next=q；D.s->next=q；p->next=s->next；参考答案10【单选题】（1分）在表长为n的顺序表中，当在任何位置删除一个元素的概率相同时，删除一个元素所需移动的平均个数为（）。A.(n-1)/2B.(n+1)/2C.n/2D.n参考答案第三章测试【单选题】（1分）栈和队列的共同点是（）A.没有共同点B.都是先进先出C.都是先进后出D.只允许在端点处插入和删除元素会考答案

一个栈的入栈序列a,b,c,d,e，则栈的不可能的输出序列是（）A.edcbaB.abcdeC.decbaD.dceab参考答案【单选题】（1分）设计一个判别表达式中括号是否配对的算法，采用（）数据结构最佳。A.栈B.顺序表C.队列D.链表参考答案4【单选题】（1分）若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0,3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（）。A.5和1B.4和2C.1和5D.2和4参考答案D【单选题】（1分）循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（）A.rear-front+1B.rear-frontC.（rear-front+m）%mD.rear-front-1会考答案【单选题】（1分）一个顺序栈S,其栈顶指针为top,则将元素e入栈的操作是（）。（注：top指向待插入位置）A.*S->top=e;S->top++;B.*S->top=eC.S->top++;*S->top=e;D.S->top=e;参考答案【单选题】（1分）在解决计算机主机和打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（）结构。A.数组B.堆栈C.队列D.线性表8【单选题】（1分）当用大小为N的数组存储顺序循环队列时，该队列的最大长度为（）。A.N+1B.N-1C.ND.N-2参考答案9【单选题】（1分）依次在初始为空的队列中插入元素a,b,c,d以后，紧接着做了两次删除操作，此时的队头元素是（）。A.bB.aC.cD.d10【单选题】（1分）向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行（）。不带空的头结点）A.s->next=HS;HS=s;B.s->next=HS->next;HS->next=s;C.HS->next=s;D.s->next=HS;HS=HS->next;参考答案第四章测试1【单选题】（1分）设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a[1][1为第一元素，其存储地址为1，每个元素占一个地址空间，则a[8][5的地址为（）。A.33B.40C.18D.参考答案【单选题】（1分）设有数组A[i,j]数组的每个元素长度为3字节，i的值为1到8,j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为（）A.BA+141B.BA+225C.BA+180D.BA+222会考答案3【单选题】（1分）将一个A[1..100,1..100的三对角矩阵，按行优先存入一维数组B[1・・298]中，A中元素A[66][65]（即该元素下标i=66，j=65），在B数组中的位置K为（）。A.193B.197C.195D.参考答案【单选题】（1分）二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,...,8,列下标j=1,2,...,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（）的起始地址相同。设每个字符占一个字节A.B.10C.D.5会考答案5【单选题】（1分）设二维数组A[1..m，1..n]（即m行n列）按行存储在数组B[1..m*n]中，则二维数组元素A[i[在一维数组B中的下标为（）A.i*（j-DB.（i-D*n+jC.（i-D*n+j-1D.j*m+i-1参考答案B【单选题】（1分）有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）A.18000B.66C.33D.60会考答案7【单选题】（1分）设有两个串P和q，求q在p中首次出现的位置的运算称作（）。A.连接B.求子串C.求串长D.模式匹配参考答案【单选题】（1分）常对数组进行的两种基本操作是（）。A.对数据元素的存取和修改B.索引和修改C.查找与索引D.建立与删除参考答案9【单选题】（1分）二维数组A中，每个元素的长度为3个字节，行下标i从0到7,列下标j从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是（）。A.80B.270C.D.240参考答案D【单选题】（1分）二维数组A中，每个元素A的长度为3个字节，行下标i从0到7,列下标j从0到9,从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7的起始地址为（）。A.SA+222B.SA+225C.SA+141D.SA+180参考答案第五章测试【单选题】（1分）引入二叉线索树的目的是（）A.使二叉树的遍历结果唯一B.为了能方便的找到双亲C.加快查找结点的前驱或后继的速度D.为了能在二叉树中方便的进行插入与删除参考答案【单选题】（1分）n个结点的线索二叉树上含有的线索数为（）。A.n+lB.n一1C.nD.2n参考答案3【单选题】（1分）由3个结点可以构造出多少种不同的二叉树（）。A.3B.C.2D.5参考答案【单选题】（1分）已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为（）。A.-+A*BC/DEB.-+*ABC/DEC.-A+B*CD/ED.-A+B*C/DE参考答案5【单选题】（1分）若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）。A.9B.15C.不确定D.11参考答案D【单选题】（1分）有关二叉树下列说法正确的是（）。A.二叉树中任何一个结点的度都为2B.二叉树的度为2C.一棵二叉树的度可以小于2D.二叉树中至少有一个结点的度为2参考答案7【单选题】（1分）一个具有1025个结点的二叉树的高h为（）。A.10至1024之间B.11C.11至1025之间D.10参考答案【单选题】（1分）若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（遍历方法最合适。A.后序B.按层次C.前序D.中序参考答案9【单选题】（1分）若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为（）A.X的双亲B.X的右子树的根C.X的右子树中最左的结点D.X的左子树中最右结点参考答案【单选题】(1分)二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历:HFIEJKG。该二叉树根的右子树的根是()。A.B.C.D.参号答案第六章测试1【单选题】(1分)无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),，f对■该Sd)}进行深度优先遍历，得到的顶点序列正确的是()。A.a,c,f,e,b,dB.a,e,d,f,c,bC.a,e,b,c,f,dD.a,b,e,c,d,f会考答案【单选题】（1分）已知有向图G=（V,E），其中V={V1,V2,V3,V4,V5,V6,V7},E={,,,,,,,,的拓扑序列是（）。A.V1,V2,V5,V3,V4,V6,V7B.V1,V3,V2,V6,V4,V5,V7C.V1,V3,V4,V5,V2,V6,V7D.V1,V3,V4,V6,V2,V5,V7参考答案3【单选题】（1分）要连通具有n个顶点的有向图，至少需要（）条边A.n+1B.2nC.nD.n-l参考答案【判断题】（1分）在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（）A.对B.错参考答案5【判断题】（1分）邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。（）A.错B.对6【单选题】（1分）设无向图的顶点个数为n,则该图最多有（）条边。A.n（n+1）/2B.n*nC.n-1D.n（n-1）/2参考答案7【单选题】（1分）下列哪一种图的邻接矩阵是对称矩阵？（）A.无向图B.AOE网C.有向图D.AOV网8【单选题】（1分）下面哪一方法可以判断出一个有向图是否有环（回路）：（）。A.求最短路径B.深度优先遍历C.求关键路径D.拓扑排序参考答案9【单选题】（1分）对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为A.k2B.k1+k2C.k1-k2D.参考答案D【单选题】（1分）下列说法不正确的是（）。A.图的深度遍历不适用于有向图B.遍历的基本算法有两种：深度遍历和广度遍历C.图的深度遍历是一个递归过程D.图的遍历是从给定的源点出发每一个顶点仅被访问一次参考答案第七章测试【单选题】（1分）一个有序表为（1，3，9，12，32，41，45，62，75，77，82，95，100），当采用折半查找方法查找值32时，查找成功需要的比较次数是（）。A.B.C.D.【单选题】(1分)设散列表长m=14,散列函数H(K)=K%11,已知表中已有4个结点：r(15)=4;r(38)=5;r(61)=6;r(84)=7其他地址为空，如用二次探测法处理冲突，关键字为49的结点地址是()。A.B.9C.D.5参考答案3【单选题】(1分)在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0右孩子的平衡因子为1，则应作()型调整以使其平衡。A.LLB.RRC.RLD.LR参考答案【单选题】（1分）当在一个有序的顺序表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（）。A.在大部分情况下要快B.取决于表递增还是递减C.不一定D.必定快参考答案5【单选题】（1分）如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则应采用的查找方法是A.都不行B.顺序查找C.分块查找D.二分法查找参考答案6【单选题】（1分）在长度为n的顺序表中进行顺序查找，查找失败时需与键值比较次数是（）A.n+1B.nC.n-1D.参考答案7【单选题】（1分）在采用线性探查法处理冲突的散列表中进行查找，查找成功时所探测位置上的键值（）A.无任何关系B.一定都不是同义词C.一定都是同义词D.不一定是同义词参考答案【单选题】（1分）对一棵二叉排序树进行（遍历，可以得到一个键值从小到大次序排列的有序序列。A.层序B.后序C.中序D.先序参考答案9【单选题】（1分）分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（）。A.（100，60，80，90，120，110，130）B.（100，80，60，90，120，130，110）C.（100，80，90，60，120，110，130）D.参考答案10【单选题】（1分）在查找过程中，若同时还要做插入、删除操作，这种查找称为A.动态查找B.静态查找C.内部查找D.外部查找参考答案第八章测试1【单选题】（1分）对n个不同的关键字由小到大进行冒泡排序，在下列（）情况下比较的次数最多。A.从大到小排列好的B.元素无序C.从小到大排列好的D.元素基本有序参考答案【单选题】（1分）下列关键字序列中，（）是堆。A.16,53,23,94,31,72B.16,72,31,23,