2023年浙江大学远程教育数据结构与算法在线作业答案

您的本次作业分数为：99分.【第1章第2节】数据结构课程重要研究以下三方面的内容，它们是orA数据、数据元素、数据类型rB数据元素、数据类型、算法实现rC数据元素、数据的逻辑结构、数据的存储结构注D数据的逻辑结构、数据的存储结构、数据的运算对的答案：D.【第1章第2节】在数据结构中，与所使用的计算机无关的是数据的结构。「A存储「B物理⑤C逻辑rD物理与存储对的答案：C.【第1章第2节】逻辑结构相同时物理结构也应当相同。「对的方错误.【第1章第3节】计算机算法是指oCA计算方法IB排序方法「C调度方法仃D解决问题的有限运算序列对的答案：D.【第1章第3节】设某二维数组A[1..n,L,则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为oAO(log2n)D2*h对的答案:A我感觉对的答案应当是C,但是系统给的答案是A38.【第4章第3节】在某棵二叉树的一种序列中，假如发现其中每一结点的左孩子均是其前趋,则可判断定这种序列为中序序列。⑸A对的「B不对的对的答案:A39.【第4章第3节】已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是oAacbed「Bdecab「Cdeabc♦Dcedba对的答案:D40.【第4章第3节】假如某二叉树的先序遍历序列是abdcef,中序遍历序列是dbaefc,则其后序遍历序列是o「AdbafecBfecdba「Cefcdba.Ddbfeca对的答案:D41.【第4章第3节】任何一棵二叉树的叶结点在先序、中序和后序遍历的序列中的相对顺序o0A不发生变化rB发生变化rC不能拟定rD以上都不对对的答案:A42.【第4章第3节】某非空二叉树的前序序列和后序序列正好相反，则二叉树一定是—的二叉树。⑸A空或只有一个结点-B高度等于其结点数CC.任一结点无左孩子「D任一结点无右孩子对的答案：A43.【第4章第3节】树的基本遍历策略可分为先根遍历和后根遍历;二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里我们把由树转化得到的二叉树叫做这棵树相应的二叉树。那么以下结论中是对的的。"A树的先根遍历序列与其相应的二叉树的先序遍历序列相同CB树的后根遍历序列与其相应的二叉树的后序遍历序列相同「C树的先根遍历序列与其相应的二叉树的中序遍历序列相同rD以上都不对对的答案：A44.【第4章第3节】设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（注意C和D中h为指数）。A2h-1B2(h-1)C2*h-1「D2*h对的答案:A.【第4章第3节】关于二叉树的三种遍历，下列说法对的的是—o「A任意两种遍历序列都不可以唯一决定该二叉树丁B任意两种遍历序列都可以唯一决定该二叉树rC先序遍历序列和后序遍历序列可以唯一决定该二叉树■D先序遍历序列和中序遍历序列可以唯一决定该二叉树对的答案:D.【第4章第3节】设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是O「Aa是b祖先「Ba是b子孙"Ca在b左方「Da在b右方对的答案:C.【第4章第3节】设二叉树根结点的层次为1,所有具有15个结点的二叉树中，最小高度是O「A6「B5♦C4D3对的答案:c48.【第4章第3节】由二叉树的前序和中序遍历序列可惟一构造这棵二叉树。⑸对的C错误对的答案：对9.【第4章第3节】满二叉树一定是完全二叉树，反之不然。⑥对的「错误对的答案：对.【第4章第3节】任何二叉树的叶子数都要比度为2的结点数多。⑥对的「错误对的答案：对.【第4章第4节】若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过O「An/2%BnrC(n+l)/2「Dn+1对的答案:B52.【第4章第4节】假如某二叉树的左右子树的高度差的绝对值不大于1,则一定是平衡二叉树。「对的6错误对的答案：错.【第4章第4节】二叉排序树一般用于查找某个元素。作对的「错误对的答案：对.【第4章第6节】有m个叶子结点的Huffman树所具有的结点总数为。「Am+1♦B2m-1「C2m「D2m+1对的答案:B55.【第4章第6节】哈夫曼编码使一串文字的编码长度最短。作对的C错误对的答案：对56.【第4章第6节】序列｛12,23,15,24,22,18,16,30,27｝是一个堆。「对的⑥错误对的答案：错57.【第5章第1节】哈希表是用于查找的技术之一。作对的C错误对的答案：对58.【第5章第2节】将10个元素散列到100000个单元的散列表中，则产生冲突。rA一定会「B一定不会eC仍也许会对的答案:C.【第5章第2节】若散列表的装载因子则可避免冲突的产生。「对的作错误对的答案：错.【第5章第3节】设散列表长为14,散列函数是H(key)=key%l1,表中已有数据的关键字为15,38,61,84共四个，现要将关键字为49的结点加到表中，用二次探测法解决冲突,则放入的位置是o「A8B3「C5*D9对的答案:D61.【第6章第2节】在一个无向图中，所有顶点的度数之和等于所有边数的一倍。「A1/2「B1"C2「D4对的答案：C.【第6章第2节】具有5个顶点的有向完全图有一条弧。CA10广B16"C20D25对的答案:C.【第6章第2节】无向图各顶点度之和就等于边的数量。「对的⑥错误对的答案：错.【第6章第2节】有向图各顶点入度之和就等于边的数量。

对的错误对的答案：对对的错误.【第6章第2节】5个顶点的无向图，若不连通，则最多也许有6条边。对的C错误对的答案：对.【第6章第2节】树可以当作是连通的图。④对的「错误对的答案：对.【第6章第3节】设n个顶点e条边的图G用邻接表存储，则求每个顶点入度的时间复杂度为—o「AO(n)‘BO(n+e)「CO(n*n)「DO(n*e)对的答案:B.【第6章第3节】对于一个具有n个顶点和e条边的无向图，若采用邻接表表达，邻接表中所有结点总数是。CAe/2④B2erCe-Dn+e对的答案:B69.【第6章第3节】下面关于图的存储的叙述中，哪一个是对的的？A用相邻矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关1B用相邻矩阵法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关rC用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关rD用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关对的答案:A70.【第6章第3节】邻接表是图的一种—oCA顺序存储结构"B链式存储结构「C索引存储结构rD散列存储结构对的答案:B.【第6章第3节】用邻接矩阵表达图所用的存储空间大小与图的边数成正比。r对的作错误对的答案：错.【第6章第4节】假如无向图G必须进行二次广度优先搜索才干访问其所有顶点，则下列说法中不对的的是o「AG肯定不是完全图「BG一定不是连通图«CG中一定有回路「DG有2个连通分量对的答案:C.【第6章第4节】连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点。作对的「错误对的答案：对.【第6章第4节】图的深度优先遍历和广度优先遍历都包含了图的所有顶点。e对的r错误对的答案：对.【第6章第5节】关于无向连通图的最小生成树的个数o「A一定有多棵"B一定只有一棵「C有一棵或多棵广D也许不存在对的答案:B76.【第6章第5节】下列关于图的生成树的唯一性，对的的是1A生成树是唯一的「B生成树是不唯一的口C生成树是唯一性不拟定rD图的生成树有两棵对的答案:C77.【第7章第2节】一组记录的排序码为(20,29,11,74,35,3,8,56)，则运用堆排序方法建立的初始(小顶)堆为o「A20,29,11,74,35,3,8,56“B3,29,8,56,35,20,11,74「C3,8,11,20,29,35,56,74*D20,29,3,8,11,35,74,56对的答案:B78.【第7章第3节】用某种排序方法对线性表(25,84,21,47,15,27,68,35,20)进行排序时,元素序列的变化情况如下(1)20,15,21,25,47,27,68,35,84(2)15,20,21,25,35,27,47,68,84(3)15,20,21,25,27,35,47,68,84则所采用的排序方法是。A选择排序1B希尔排序rc归并排序6D快速排序对的答案:D79.【第7章第3节】在某个实例的排序结果看出，值相同的两个关键字排序前后领先关系不变，由此可知该排序方法是稳定的。r对的6错误对的答案：错80.【第7章第4节】一组记录的关键字为(46,79,56,38,40,84),则运用快速排序的方法，以第一个记录为基准元素得到的一次划分结果为。rA38,40,46,56,79,84「B40,38,46,79,56,84.C40,38,46,56,79,84rD40,38,46,84,56,79对的答案:C81.【第7章第4节】已知10个数据元素为(54,28,16,34,73,62,95,60,26,43),对该数列按从小到大排序，通过一趟冒泡排序后的序列为o「A16,28,34,54,73,62,60,26,43,95“B28,16,34,54,62,73,60,26,43,95「C28,l6,34,54,62,60,73,26,43,95「D16,28,34,54,62,60,73,26,43,95对的答案:B82.【第7章第8节】下列排序算法的时间复杂度最小的是oB0(n)「C0(nlog2n)♦DO(nA2)对的答案:D.【第1章第3节】所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界伶对的C错误对的答案：对.【第3章第2节】向一个有115个元素的顺序表中插入一个新元素并保持本来顺序不变,平均要移动个元素。CA115「b114'C58rD57对的答案:c.【第3章第2节】在一个具有n个结点的有序单链表中，插入一个新的结点并使之仍然有序的时间复杂度是o.AO(n)「BO(log2n)「C0(1)「DO(nA2)对的答案:A.【第3章第2节】若规定能快速地实现在链表的末尾插入和删除结点的运算，则选择—最合适。A单链表'A冒泡排序厂B希尔排序「C简朴选择排序"D归并排序对的答案:D83.【第7章第8节】在待排序的元素序列基本有序的前提下，效率最高的排序方法是O⑥A插入排序B快速排序「C归并排序广D选择排序对的答案：A84.【第7章第8节】设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最佳—排序法。「A起泡排序「B快速排序6C堆排序CD基数排序对的答案:C85.【第7章第8节】通过关键字比较的方法进行排序，其时间复杂性至少是O(n1og2n)o⑥对的「错误对的答案：对加入错题集关闭窗体底端B带尾指针的单循环链表1C双链表广D双循环链表对的答案:B10.【第3章第2节】在长度为n的双链表中某结点(已知其地址)之前，插入一个新结点的时间复杂度是o「AO(n)「BO(log2n)♦CO(1)「DO(n八2)对的答案:C11.【第3章第2节】在一个长度为n的顺序表中，在第i个元素(IV=iV=n)之前插入一个新元素时需向后移动个元素。「A1「Bn-i「Cn-i-1“Dn-i+l对的答案：D12.【第3章第2节】对顺序存储的线性表，设其长度为n,且在任何位置上插入或删除操作都是等概率的。则插入一个元素时平均要移动表中的个元素。“An/2「B(n+1)/2对的答案：A.【第3章第2节】顺序表的特点是orA逻辑上相邻的结点其物理位置不相邻作B逻辑上相邻的结点其物理位置亦相邻CC顺序表不是随机存储结构CD在顺序表中插入和删除操作比在链表上方便.【第3章第2节】带头结点的单链表Head为空表的鉴定条件是「TTAHead—>next==Head"BHead->next==NULL「CHead!=NULLDHead==NULL对的答案:B.【第3章第2节】线性表采用链式存储时，其地址rA必须是连续的CB必须是不连续的④C连续与否均可「D部分地址必须是连续的对的答案:C.【第3章第2节】链表不具有的特点是o作A可随机访问任一元素CB插入和删除不需要移动元素C不必事先估计存储空间1D所需空间和线性表长度成正比对的答案:A17.【第3章第2节】线性表按链式方式存储时,每个结点的存储涉及两部分。CA数据值与符号eB数据与指针「C数据与表名广D数据项与符号对的答案:B.【第3章第2节】在n个元素的顺序表中删除第i个元素，需要移动n-i个元素。作对的C错误对的答案：对.【第3章第3节】一个栈的进栈序列是a,b,c,d,e,则栈的不也许的出栈序列是AedcbaBdceab『Cdecba「Dabcde对的答案:B20.【第3章第3节】栈结构通常采用的两种存储结构是rA线性存储结构和链表存储结构「B散列方式和索引方式CC链表存储结构和数组注D线性存储结构和非线性存储结构对的答案:D21.【第3章第3节】当字符序列x5y作为字符堆栈的输入时，输出长度为3的且可以作为C语言标记符的个数是—Oba3个「B4个「C5个「D6个对的答案：A22.【第3章第3节】一个栈的入栈序列是a,b,c,d,则下列序列中不也许的输出序列是Aacbd「Bdcba「Cacdb“Ddbac对的答案:D.【第3章第3节】作进栈操作时，应先判断栈是否为o「A空6B满rC上溢「d下溢对的答案:B.【第3章第3节】若某堆栈的输入序列为1,2,3,…再一1,n,输出序列的第1个元素为n,则第i个输出元素为o♦An-i+1Bn—iCiD哪个元素无所谓对的答案:A5.【第3章第3节】采用不带尾指针的单链表方式表达一个栈，便于结点的插入与删除。栈顶结点的插入与删除通常在链表的进行。「A任意位置「B链表头尾两端"C链表头一端CD链表尾一端对的答案:C.【第3章第3节】判断顺序储存下堆栈s是空的条件是s.t。p==0。6对的一错误对的答案：对.【第3章第4节】判断一个循环队列是空队列的条件是o"AQ.rear==Q.front「BQ・front==0「CQ.rear==0D(Q.rear+l)%maxsize==Q.front对的答案：A.【第3章第4节】队列的操作原则是o付A先进先出B先进后出C