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

《2023年浙江大学远程教育数据结构与算法在线作业答案.docx》由会员分享，可在线阅读，更多相关《2023年浙江大学远程教育数据结构与算法在线作业答案.docx（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、您的本次作业分数为：99分.【第1章第2节】数据结构课程重要研究以下三方面的内容，它们是or A数据、数据元素、数据类型r B数据元素、数据类型、算法实现r C数据元素、数据的逻辑结构、数据的存储结构注D数据的逻辑结构、数据的存储结构、数据的运算对的答案：D.【第1章第2节】在数据结构中，与所使用的计算机无关的是数据的 结构。A存储B物理C逻辑r D物理与存储对的答案：C.【第1章第2节】逻辑结构相同时物理结构也应当相同。对的方错误.【第1章第3节】计算机算法是指 oC A计算方法I B排序方法 C调度方法仃D解决问题的有限运算序列对的答案：D.【第1章第3节】设某二维数组A 1. n,L,则

2、在该数组中用顺序查找法查找一个元素的时间复杂性的量级为 oA O(log 2 n)D 2*h对的答案:A我感觉对的答案应当是C,但是系统给的答案是A38.【第4章第3节】在某棵二叉树的一种序列中，假如发现其中每一结点的左孩子均是其 前趋,则可判断定这种序列为中序序列。A对的B不对的对的答案:A3 9.【第4章第3节】已知某二叉树的后序遍历序列是dab ec,中序遍历序列是deb a c,它的前序遍历序列是oA a cbedB d e cab C deabc D ced b a对的答案:D40.【第4章第3节】假如某二叉树的先序遍历序列是abdcef,中序遍历序列是db a e f c, 则其后

3、序遍历序列是 oA dbafe cB fecdb aC ef c d ba. D dbfe c a对的答案:D41 .【第4章第3节】任何一棵二叉树的叶结点在先序、中序和后序遍历的序列中的相对顺序 o0 A不发生变化r B发生变化r C不能拟定r D以上都不对对的答案:A42.【第4章第3节】某非空二叉树的前序序列和后序序列正好相反，则二叉树一定是的二叉树。A空或只有一个结点-B高度等于其结点数C C.任一结点无左孩子D任一结点无右孩子对的答案：A43.【第4章第3节】树的基本遍历策略可分为先根遍历和后根遍历;二叉树的基本遍历策略 可分为先序遍历、中序遍历和后序遍历。这里我们把由树转化得到的二

4、叉树叫做这棵树相应 的二叉树。那么以下结论中 是对的的。 A树的先根遍历序列与其相应的二叉树的先序遍历序列相同C B树的后根遍历序列与其相应的二叉树的后序遍历序列相同 C树的先根遍历序列与其相应的二叉树的中序遍历序列相同rD以上都不对对的答案：A4 4.【第4章第3节】设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中 所包含的结点数至少为（注意C和D中h为指数）。A 2h- 1B 2( h - 1 )C2*h-1D 2*h对的答案:A.【第4章第3节】关于二叉树的三种遍历，下列说法对的的是o A任意两种遍历序列都不可以唯一决定该二叉树丁B任意两种遍历序列都可以唯一决定该二叉树r C

5、先序遍历序列和后序遍历序列可以唯一决定该二叉树 D先序遍历序列和中序遍历序列可以唯一决定该二叉树对的答案:D.【第4章第3节】设a, b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是 OA a是b祖先B a是b子孙Ca在b左方D a在b右方对的答案:C45 .【第4章第3节】设二叉树根结点的层次为1,所有具有1 5个结点的二叉树中，最小高度是 OA 6B 5 C4D3对的答案:c48 .【第4章第3节】由二叉树的前序和中序遍历序列可惟一构造这棵二叉树。对的C错误对的答案：对4 9 .【第4章第3节】满二叉树一定是完全二叉树，反之不然。对的错误对的答案：对50 .【第4章第3节】任何二

6、叉树的叶子数都要比度为2的结点数多。对的错误对的答案：对51 .【第4章第4节】若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过 OAn/2% B nr C(n+l)/2D n+1对的答案:B5 2 .【第4章第4节】假如某二叉树的左右子树的高度差的绝对值不大于1,则一定是平衡二叉树。对的6错误对的答案：错53 .【第4章第4节】二叉排序树一般用于查找某个元素。作对的错误 对的答案：对.【第4章第6节】有m个叶子结点的Huffman树所具有的结点总数为。A m+1 B2m-1C2mD 2m+1对的答案:B5 5.【第4章第6节】哈夫曼编码使一串文字的编码长度最短。作对的C错误对的

7、答案：对5 6.【第 4 章第 6 节】序列 1 2, 2 3, 1 5,24, 22, 18, 16, 3 0 ,27是一个堆。对的错误对的答案：错57.【第5章第1节】哈希表是用于查找的技术之一。作对的C错误对的答案：对5 8.【第5章第2节】将10个元素散列到100000个单元的散列表中，则 产生冲突。r A 一定会 B 一定不会e C仍也许会对的答案:C59 .【第5章第2节】若散列表的装载因子则可避免冲突的产生。对的作错误 对的答案：错.【第5章第3节】设散列表长为14,散列函数是H(ke y ) =key%l 1,表中已有数据的关键字为1 5,38, 61,84共四个，现要将关键字

8、为49的结点加到表中，用二次探测法解决冲突,则放入的位置是 oA 8B 3C5*D 9对的答案:D6 1 .【第6章第2节】在一个无向图中，所有顶点的度数之和等于所有边数的一倍。A1 /2B 1C 2D4对的答案：C.【第6章第2节】具有5个顶点的有向完全图有一条弧。C A 1 0广B 16C 20D 25对的答案:C62 .【第6章第2节】无向图各顶点度之和就等于边的数量。对的错误对的答案：错63 .【第6章第2节】有向图各顶点入度之和就等于边的数量。对的错误对的答案：对64 .【第6章第2节】5个顶点的无向图，若不连通，则最多也许有6条边。对的C错误对的答案：对65 .【第6章第2节】树可

9、以当作是连通的图。对的错误对的答案：对66 .【第6章第3节】设n个顶点e条边的图G用邻接表存储，则求每个顶点入度的时间复 杂度为oAO ( n)BO (n+e)CO (n*n)D O(n*e)对的答案:B67 .【第6章第3节】对于一个具有n个顶点和e条边的无向图，若采用邻接表表达，邻接表 中所有结点总数是。C A e/2B2er C e- D n+e对的答案:B69 .【第6章第3节】下面关于图的存储的叙述中，哪一个是对的的？A用相邻矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关1 B用相邻矩阵法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关 r C用邻接表法

10、存储图，占用的存储空间数只与图中结点个数有关，而与边数无关r D用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关 对的答案:A7 0 .【第6章第3节】邻接表是图的一种oC A顺序存储结构B链式存储结构C索引存储结构r D散列存储结构对的答案:B.【第6章第3节】用邻接矩阵表达图所用的存储空间大小与图的边数成正比。r对的作错误对的答案：错71 .【第6章第4节】假如无向图G必须进行二次广度优先搜索才干访问其所有顶点，则下列说法中不对的的是 oA G肯定不是完全图 B G一定不是连通图 C G中一定有回路D G有2个连通分量对的答案:C.【第6章第4节】连通图的广度优先搜索中

11、一般要采用队列来暂存刚访问过的顶点。作对的错误对的答案：对72 .【第6章第4节】图的深度优先遍历和广度优先遍历都包含了图的所有顶点。e对的r错误对的答案：对73 .【第6章第5节】关于无向连通图的最小生成树的个数 oA 一定有多棵B 一定只有一棵 C有一棵或多棵广D也许不存在对的答案:B7 6.【第6章第5节】下列关于图的生成树的唯一性，对的的是 1 A生成树是唯一的B生成树是不唯一的口 C生成树是唯一性不拟定r D图的生成树有两棵对的答案:C77.【第7章第2节】一组记录的排序码为(20,29,11,74,3 5,3,8,5 6 )，则运用堆排序方法建 立的初始(小顶)堆为 oA 20,2

12、9, 1 1 ,74,35,3,8, 56“ B 3,2 9,8,56,35,2 0,11, 74 C 3,8, 1 1 ,20,2 9 , 3 5,56,7 4*D20, 2 9,3,8,11,35,74,56对的答案:B7 8.【第7章第3节】用某种排序方法对线性表(25,8 4,2 1, 47,1 5 , 2 7,68,3 5 , 20)进行 排序时,元素序列的变化情况如下(1)2 0,1 5,2 1 , 25,47,27,6 8,3 5,84 ( 2 )1 5,2 0, 2 1 ,25,35,27,47,68,84 (3)1 5,2 0,2 1 ,25,27, 35,47, 6 8,

13、84 则所采用的排序方法是 。A选择排序 1 B希尔排序r c归并排序6 D快速排序对的答案:D79.【第7章第3节】在某个实例的排序结果看出，值相同的两个关键字排序前后领先关系 不变，由此可知该排序方法是稳定的。r对的6错误对的答案：错8 0.【第7章第4节】一组记录的关键字为(4 6, 7 9,56, 3 8 , 40, 8 4),则运用快速排序的方法，以第一个记录为基准元素得到的一次划分结果为。r A 3 8, 4 0,46, 5 6,79, 84B 40,3 8 ,46,7 9 ,56, 8 4. C40, 3 8,4 6 , 56,79,84r D 40,38,46,84, 5 6,

14、79对的答案:C81 .【第7章第4节】已知1 0个数据元素为(54,28, 16, 3 4 , 73, 6 2, 9 5,60, 26,43),对该数列按从小到大排序，通过一趟冒泡排序后的序列为 oA 16, 2 8,34, 54, 73,62, 6 0,2 6 , 4 3,9 5“ B 2 8,1 6 , 34, 54, 62, 73,60,26,43,95C28,l 6 , 34 , 5 4, 62, 60, 7 3 , 26,4 3 ,95D 1 6,28, 3 4,5 4 , 62, 60,73,2 6, 43,9 5对的答案:B8 2 .【第7章第8节】下列排序算法的时间复杂度最小

15、的是 oB 0(n)C 0 ( nl o g2n) D O (nA2)对的答案:D6 .【第1章第3节】所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界伶对的C错误对的答案：对.【第3章第2节】向一个有1 15个元素的顺序表中插入一个新元素并保持本来顺序不变,平均要移动 个元素。C A 1 15b 114 C58r D57对的答案:c7 .【第3章第2节】在一个具有n个结点的有序单链表中，插入一个新的结点并使之仍然有 序的时间复杂度是 o. AO (n)BO (log2n)C 0(1)DO ( nA2)对的答案:A8 .【第3章第2节】若规定能快速地实现在链表的末尾插入和删除结点的运算

16、，则选择 最合适。A单链表A冒泡排序厂B希尔排序C简朴选择排序D归并排序对的答案:D83.【第7章第8节】在待排序的元素序列基本有序的前提下，效率最高的排序方法是 OA插入排序B快速排序C归并排序广D选择排序对的答案：A8 4.【第7章第8节】设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大 的元素，最佳排序法。A起泡排序B快速排序6 C堆排序C D基数排序对的答案:C8 5 .【第7章第8节】通过关键字比较的方法进行排序，其时间复杂性至少是O(n 1 og2n)o对的错误对的答案：对加入错题集关闭 窗体底端B带尾指针的单循环链表 1 C双链表广D双循环链表对的答案:B10.【

17、第3章第2节】在长度为n的双链表中某结点(已知其地址)之前，插入一个新结点的 时间复杂度是 oA O (n)BO (log2 n) C O (1)DO(n 八 2)对的答案:C11 .【第3章第2节】在一个长度为n的顺序表中，在第i个元素(IV=i V=n)之前插入一个新元素时需向后移动 个元素。A 1 B n-iC n-i-1“D n-i+l对的答案：D1 2 .【第3章第2节】对顺序存储的线性表，设其长度为n,且在任何位置上插入或删除操作 都是等概率的。则插入一个元素时平均要移动表中的 个元素。“A n/2B ( n + 1 )/2对的答案：A.【第3章第2节】顺序表的特点是 orA逻辑上

18、相邻的结点其物理位置不相邻作B逻辑上相邻的结点其物理位置亦相邻C C顺序表不是随机存储结构C D在顺序表中插入和删除操作比在链表上方便13 .【第3章第2节】带头结点的单链表He a d为空表的鉴定条件是TTA H ead next=Head B Hea d -next= = NULLC Head! =NULLDHead = =NULL对的答案:B14 .【第3章第2节】线性表采用链式存储时，其地址r A必须是连续的C B必须是不连续的C连续与否均可D部分地址必须是连续的对的答案:C15 .【第3章第2节】链表不具有的特点是 o作A可随机访问任一元素C B插入和删除不需要移动元素C不必事先估计

19、存储空间1 D所需空间和线性表长度成正比对的答案:A1 7 .【第3章第2节】线性表按链式方式存储时,每个结点的存储涉及 两部分。C A数据值与符号eB数据与指针 C数据与表名广D数据项与符号对的答案:B.【第3章第2节】在n个元素的顺序表中删除第i个元素，需要移动n-i个元素。作对的C错误对的答案：对18 .【第3章第3节】一个栈的进栈序列是a, b,c,d,e,则栈的不也许的出栈序列是A e d cb aB d ceabC d e c baDa bcde对的答案:B2 0.【第3章第3节】栈结构通常采用的两种存储结构是r A线性存储结构和链表存储结构B散列方式和索引方式C C链表存储结构和

20、数组注D线性存储结构和非线性存储结构对的答案:D2 1.【第3章第3节】当字符序列x5y作为字符堆栈的输入时，输出长度为3的且可以作为C语言标记符的个数是Oba 3个B 4个C5个D6个对的答案：A2 2 .【第3章第3节】一个栈的入栈序列是a,b,c, d,则下列序列中不也许的输出序列是A a cbdB d cbaC ac d b“D d bac对的答案:D.【第3章第3节】作进栈操作时，应先判断栈是否为 oA空6B满r C上溢d下溢对的答案:B.【第3章第3节】若某堆栈的输入序列为1, 2, 3,再一1, n,输出序列的第1个元素为n,则第i个输出元素为 o A n-i + 1B n iC

21、iD哪个元素无所谓对的答案:A5 .【第3章第3节】采用不带尾指针的单链表方式表达一个栈，便于结点的插入与删除。栈顶结点的插入与删除通常在链表的 进行。A任意位置B链表头尾两端C链表头一端C D链表尾一端对的答案:C.【第3章第3节】判断顺序储存下堆栈s是空的条件是s.t。p = = 0。6对的一错误对的答案：对26 .【第3章第4节】判断一个循环队列是空队列的条件是 oA Q . r e ar=Q. f ro n tB Q front=0C Q.rear=0D (Q .re a r +l)%maxs i ze=Q.fro n t对的答案：A27 .【第3章第4节】队列的操作原则是 o付A先进

22、先出B先进后出C只能进行插入D只能进行删除对的答案:A.【第3章第4节】判断顺序储存下队列q是空的条件是q-f ront= q .rear。e对的C错误对的答案：对28 .【第4章第1节】对线性表进行二分查找时，规定线性表必须 or A以顺序方式存储口 B以顺序方式存储且元素有序 C以链式方式存储r D以链式方式存储且元素有序对的答案:B29 .【第4章第1节】若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至 or A 该中间位置B该中间位置一1C该中间位置+1rD该中间位置/2对的答案:B30 .【第4章第1节】在顺序表2、5、7

23、、10、14、15、18、2 3、35、4 1、52中,用二分法查找关键码12需做 次关键码比较。B3C 4D5对的答案:c31 .【第4章第2节】树最适合用来表达 oC A有序数据元素C B无序数据元素作C元素之间具有分支层次关系的数据r D元素之间无联系的数据对的答案:C3 4.【第4章第2节】若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是 oC A根结点无右子树的二叉树C B根结点无左子树的二叉树口 C根节点也许有左子树和右子树的二叉树广D各结点只有一个儿子的二叉树对的答案:C35.【第4章第2节】任何一个森林都可以唯一地与一棵二叉树相应。作对的错误对的答案：对3 6 .【第4章第2节】n(n0)个结点的树有n-1条边。注对的错误对的答案：对3 7.【第4章第3节】设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树 中所包含的结点数至多为(注意C和D中h是指数)。A2h- 1B 2 (h-1)C 2*h1