数据结构与算法在线作业答案

1、1 .邻接表是图的一种AA顺序存储结构rB链式存储结构r，c索引存储结构DD散列存储结构单选题2 .具有5个顶点的有向完全图有条弧。rA10rB16rC20rD25单选题3 .链表不具有的特点是CA可随机访问任一元素rB插入和删除不需要移动元素rc不必事先估计存储空间rD所需空间和线性表长度成正比单选题4 .作进栈操作时，应先判断栈是否为crA空rB满rc上溢D下溢单选题5 .下面关于图的存储的叙述中，哪一个是正确的？A用相邻矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关B用相邻矩阵法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关厂C用邻接表法存储图，占用的存储空

2、间数只与图中结点个数有关，而与边数无关厂D用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关单选题6 .当字符序列x5y作为字符堆栈的输入时，输出长度为3的且可以作为C语言标识符的个数是r人A3个rB4个r人C5个r_人D6个单选题7 .树最适合用来表示CA有序数据元素rB无序数据元素rc元素之间具有分支层次关系的数据rD元素之间无联系的数据单选题8 .线性表按链式方式存储时，每个结点的存储包括两部分。rA数据值与符号rB数据与指针rc数据与表名rD数据项与符号单选题9 .树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里我

3、们把由树转化得到的二叉树叫做这棵树对应的二叉树。那么以下结论中是正确的。C一A树的先根遍历序列与其对应的二叉树的先序遍历序列相同r,一B树的后根遍历序列与其对应的二叉树的后序遍历序列相同C-C树的先根遍历序列与其对应的二叉树的中序遍历序列相同r-一，D以上都不对单选题10 .设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为娃意C和D中h为指数)。rA2h-1rB2(h-1)rC2*h-1rID2*h单选题11 .关于二叉树的三种遍历，下列说法正确的是OCA任意两种遍历序列都不可以唯一决定该二叉树rB任意两种遍历序列都可以唯一决定该二叉树rc先序遍历序列和后序遍历

4、序列可以唯一决定该二叉树rD先序遍历序列和中序遍历序列可以唯一决定该二叉树单选题12 .计算机算法是指rA计算方法B排序方法C调度方法r-.D解决问题的有限运算序列单选题13 .若要求能快速地实现在链表的末尾插入和删除结点的运算，则选择最合适。AA单链表广B带尾指针的单循环链表rc双链表r-D双循环链表单选题14 .下列关于图的生成树的唯一性，正确的是CaA生成树是唯一的rB生成树是不唯一的r口一c生成树是唯一性不确定rD图的生成树有两棵单选题15 .一组记录的关键字为(46,79,56,38,40,84)，则利用快速排序的方法，以第一个记录为基准元素得到的一次划分结果为。rA38,40,46

5、,56,79,84rB40,38,46,79,56,84rC40,38,46,56,79,84rD40,38,46,84,56,79单选题16 .设散列表长为14,散列函数是H(key)=key%11,表中已有数据的关键字为15,38,61,84共四个，现要将关键字为49的结点加到表中，用二次探测法解决冲突，则放入的位置是B3rC5rD9单选题17 .如果某二叉树的先序遍历序列是abdcef,中序遍历序列是dbaefc,则其后序遍历序列是rAdbafecrBfecdbarCefcdbarDdbfeca单选题18 .若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过?rAn/2rBn

6、rC(n+1)/2rDn+1单选题19 .设某二维数组A1.n,1.n,则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为rAO(log2n)rBO(n)rCO(nlog2n)rDO(nA2)单选题20 .判断一个循环队列是空队列的条件是。AQ.rear=Q.frontBQ.front=0rCQ.rear=0rD(Q.rear+1)%maxsize=Q.front单选题21 .有m个叶子结点的Huffman树所具有的结点总数为rAm+1rB2m-1rC2mrD2m+1单选题22 .在一个无向图中，所有顶点的度数之和等于所有边数的一信。rA1/2rB1rC2rD4单选题23 .线性表采用链

7、式存储时，其地址rA必须是连续的rB必须是不连续的rc连续与否均可rD部分地址必须是连续的单选题结构。24 .在数据结构中，与所使用的计算机无关的是数据的A存储B物理C逻辑rD物理与存储单选题25 .向一个有115个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素。rA115rB114rC58rD57单选题26 .任何一棵二叉树的叶结点在先序、中序和后序遍历的序列中的相对次序?rA不发生变化rB发生变化rc不能确定rD以上都不对单选题27 .将10个元素散列到100000个单元的散列表中，则产生冲突。rA一定会rB一定不会rc仍可能会单选题28 .一组记录的排序码为(20,29

8、,11,74,35,3,8,56),则利用堆排序方法建立的初始(小顶)堆为A20,29,11,74,35,3,8,56B3,29,8,56,35,20,11,74C3,8,11,20,29,35,56,74rD20,29,3,8,11,35,74,56单选题29 .对线性表进行二分查找时，要求线性表必须?AA以顺序方式存储r，、，一B以顺序方式存储且兀素有序r，、，.c以链式方式存储r，、，一上一D以链式方式存储且兀素有序单选题30 .若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是?rA根结点无右子树的二叉树r一B根结点无左子树的二叉树rc根节点可能有左子树和右子树的二叉树rD各结点只

9、有一个儿子的二叉树单选题31 .设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是?rAa是b祖先rBa是b子孙rCa在b左方rDa在b右方单选题32 .采用不带尾指针的单链表方式表示一个栈，便于结点的插入与删除。栈顶结点的插入与删除通常在链表的进行。A任意位置B链表头尾两端r-，、“c链表头一端r.一、D链表尾一端单选题33 .用某种排序方法对线性表(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,2

10、5,27,35,47,68,84则所采用的排序方法是。rA选择排序rB希尔排序厂C归并排序r，一D快速排序单选题34 .关于无向连通图的最小生成树的个数。rA一定有多棵rB一定只有一棵厂C有一棵或多棵rD可能不存在单选题35 .已知10个数据元素为(54,28,16,34,73,62,95,60,26,43),对该数列按从小到大排序，经过一趟冒泡排序后的序列为?rA16,28,34,54,73,62,60,26,43,95oIB28,16,34,54,62,73,60,26,43,95C28,16,34,54,62,60,73,26,43,95D16,28,34,54,62,60,73,26,

11、43,95单选题个元素。36 .在一个长度为n的顺序表中，在第i个元素（1<=i<=n）之前插入一个新元素时需向后移动Bn-iCn-i-1Dn-i+1单选题37 .若某堆栈的输入序列为1,2,3,，n-1,n,输出序列的第1个元素为n,则第i个输出元素为An-i+lBn-iD哪个元素无所谓单选题38 .在一个具有n个结点的有序单链表中，插入一个新的结点并使之仍然有序的时间复杂度是AO(n)BO(log2n)CO(1)DO(nA2)单选题39 .数据结构课程主要研究以下三方面的内容，它们是A数据、数据元素、数据类型B数据元素、数据类型、算法实现C数据元素、数据的逻辑结构、数据的存储结

12、构D数据的逻辑结构、数据的存储结构、数据的运算单选题40 .在某棵二叉树的一种序列中，如果发现其中每一结点的左孩子均是其前趋，则可判断定这种序列为中序序列。r-A正确C_.B不正确单选题41 .一个栈的入栈序列是a,b,c,d,则下列序列中不可能的输出序列是rAacbdrBdcbarCacdbrDdbac单选题42 .已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是?rIAacbedrBdecabrCdeabcrDcedba单选题43 .一个栈的进栈序列是a,b,c,d,e,则栈的不可能的出栈序列是?rAedcbarBdceabrCdecbarIDabcde

13、单选题44 .栈结构通常采用的两种存储结构是A线性存储结构和链表存储结构B散列方式和索引方式C链表存储结构和数组厂D线性存储结构和非线性存储结构单选题45 .设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大白元素，最好排序法。rA起泡排序rB快速排序厂C堆排序厂D基数排序单选题46 .若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至?rA该中间位置rB该中间位置一1rc该中间位置+1rD该中间位置/2单选题47 .在长度为n的双链表中某结点（已知其地址）之前，插入一个新结点的时间复杂度是AO(n)BO(log2n)C

14、O(1)DO(nA2)单选题48 .队列的操作原则是rA先进先出r，一B先进后出厂C只能进行插入0D只能进行删除单选题49 .设二叉树根结点的层次为1,所有含有15个结点的二叉树中，最小高度是CA6rB5rC4rD3单选题50 .设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至多为D中h是指数)。rA2h-1rB2(h-1)rC2*h-1rD2*h单选题51 .下列排序算法的时间复杂度最小的是。rA冒泡排序rB希尔排序C简单选择排序D归并排序单选题52 .如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是r一AG肯定不是完全图rBG一定不是连通图r_,CG中一定有回路r_人DG有2个连通分量单选题53 .带头结点的单链表Head为空表的判定条件是rAHead->next=HeadrBHead->next=NULLrCHead!=NULLrDHead=NULL单选题54 .在顺序表2、5、7、10、14、15、18、23、35、41、52中，用二分法