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

1、55283,|65512I单选题I1 .邻接表是图的一种。AA顺序存储结构广B链式存储结构Cc索引存储结构DD散列存储结构I6550255281,I65502I单选题I2 .具有5个顶点的有向完全图有条弧。rA10BB16CC20rD25I6547555245,I65475I单选题3 .链表不具有的特点是。A可随机访问任一元素CB插入和删除不需要移动元素Cc不必事先估计存储空间DD所需空间和线性表长度成正比I6548555256,I65485单选题4 .作进栈操作时，应先判断栈是否为。CA空B满C上溢D下溢|6551555287,|65515I单选题I5 .下面关于图的存储的叙述中，哪一个是正

2、确的？A用相邻矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关B用相邻矩阵法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关Cc用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关DD用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关I6548655261,I65486I单选题I6 .当字符序列x5y作为字符堆栈的输入时，输出长度为3的且可以作为C语言标识符的个数是。(A3个BB4个CC5个DD6个I6547755253,I65477I单选题7 .树最适合用来表示。AA有序数据元素B无序数据元素C元素之间具有分支层次关系的数据DD元素

3、之间无联系的数据I6546055240,I65460I单选题8 .线性表按链式方式存储时，每个结点的存储包括两部分。AA数据值与符号CB数据与指针Cc数据与表名D数据项与符号|6549855268,|65498I单选题I9 .树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里我们把由树转化得到的二叉树叫做这棵树对应的二叉树。那么以下结论中是正确的。A树的先根遍历序列与其对应的二叉树的先序遍历序列相同BB树的后根遍历序列与其对应的二叉树的后序遍历序列相同Cc树的先根遍历序列与其对应的二叉树的中序遍历序列相同DD以上都不对I65503155271

4、,I65503I单选题10 .设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为(注意C和D中h为指数)。rA2h-1B2(h-1)CC2*h-1DId2*hI6549955272,I65499I单选题11 .关于二叉树的三种遍历，下列说法正确的是。AA任意两种遍历序列都不可以唯一决定该二叉树B任意两种遍历序列都可以唯一决定该二叉树Cc先序遍历序列和后序遍历序列可以唯一决定该二叉树DD先序遍历序列和中序遍历序列可以唯一决定该二叉树6546655235,I65466I,单选题12 .计算机算法是指。AA计算方法BB排序方法C调度方法D解决问题的有限运算序列65473

5、55239,|65473I,单选题I13 .若要求能快速地实现在链表的末尾插入和删除结点的运算，则选择最合适。A单链表BB带尾指针的单循环链表Cc双链表DD双循环链表I65519155291,I65519I单选题14 .下列关于图的生成树的唯一性，正确的是。CA生成树是唯一的广B生成树是不唯一的C生成树是唯一性不确定DD图的生成树有两棵I55289,I65516I单选题15 .一组记录的关键字为(46,79,56,38,40,84)，则利用快速排序的方法，以第一个记录为基准元素得到的一次划分结果为。JA38,40,46,56,79,84rB40,38,46,79,56,84C40,38,46,

6、56,79,84D40,38,46,84,56,796551055279,I65510I,单选题16 .设散列表长为14,散列函数是H(key尸key%11,表中已有数据的关键字为15,38,61,84共四个，现要将关键字为49的结点加到表中，用二次探测法解决冲突，则放入的位置是6548255267,单选题6548217 .如果某二叉树的先序遍历序列是abdcef,中序遍历序列是dbaefc,则其后序遍历序列是AdbafecBBfecdbaCCefcdbaDdbfecaI6550855273,I65508I单选题I18 .若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过。AAn/

7、2BIbnCC(n+1)/2rDn+1I6547155242,I65471单选题19 .设某二维数组A1.n,1.n,则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为。AAO(log2n)BO(n)CCO(nlog2n)DO(nA2)6548455252,I65484I,单选题20 .判断一个循环队列是空队列的条件是。AQrear=Q.frontBQ.front=0CQ.rear=0D(Q.rear+1)%maxsize=Q.front|6548755266,65487I单选题21 .有m个叶子结点的Huffman树所具有的结点总数为。Am+1B2m-1Ic2mCD2m+1I65511

8、55282,65511I单选题22 .在一个无向图中，所有顶点的度数之和等于所有边数的倍。rA1/2BB1C2dD4I6547855249,65478单选题23 .线性表采用链式存储时，其地址。AA必须是连续的B必须是不连续的C连续与否均可DD部分地址必须是连续的6545955234,65459单选题24 .在数据结构中，与所使用的方t算机无关的是数据的一结构。A存储B物理C逻辑DD物理与存储|65461155243,|65461I单选题I25 .向一个有115个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素。AA115B114C58DD57I65497155270,I654

9、97I单选题26 .任何一棵二叉树的叶结点在先序、中序和后序遍历的序列中的相对次序。AA不发生变化B发生变化C不能确定DD以上都不对I6550555275,I65505I,单选题27 .将10个元素散列到100000个单元的散列表中，则产生冲突。AA一定会BB一定不会CC仍可能会I6552255297,I65522单选题28 .一组记录的排序码为(20,29,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,74D20,29,3,8,11,35,

10、74,56I6550155277,65501I单选题29 .对线性表进行二分查找时，要求线性表必须。AA以顺序方式存储BB以顺序方式存储且元素有序广C以链式方式存储D以链式方式存储且元素有序6549255260,65492I单选题30 .若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是。aA根结点无右子树的二叉树CB根结点无左子树的二叉树CC根节点可能有左子树和右子树的二叉树DD各结点只有一个儿子的二叉树I6550055276,65500单选题31 .设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是Aa是b祖先BBa是b子孙Ca在b左方Da在b右方6549055258,单

11、选题32 .采用不带尾指针的单链表方式表示一个栈，便于结点的插入与删除。栈顶结点的插入与删除通常在链表的进行。A任意位置B链表头尾两端C链表头一端DD链表尾一端|65524155293,|65524I单选题I33 .用某种排序方法对线性表(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则所采用的排序方法是。AA选择排序B希尔排序C归并排序DD快速排序|6552355292,I655

12、23I,单选题I34 .关于无向连通图的最小生成树的个数。AA一定有多棵工B一定只有一棵CC有一棵或多棵D可能不存在I6552555298,I65525单选题35 .已知10个数据元素为(54,28,16,34,73,62,95,60,26,43),对该数列按从小到大排序，经过一趟冒泡排序后的序列为。AA16,28,34,54,73,62,60,26,43,95BB28,16,34,54,62,73,60,26,43,95C28,16,34,54,62,60,73,26,43,95rD16,28,34,54,62,60,73,26,43,956547255246,I65472单选题36 .在一

13、个长度为n的顺序表中，在第i个元素(1=inext=HeadBHead-next=NULLCHead!=NULLDDHead=NULLI65504155274,I65504I单选题54 .在顺序表2、5、7、10、14、15、18、23、35、41、52中，用二分法查找关键码12需做次关键码比较。A2JB3C4Id56546755238,I65467单选题55 .顺序表的特点是。aA逻辑上相邻的结点其物理位置不相邻B逻辑上相邻的结点其物理位置亦相邻C顺序表不是随机存储结构D在顺序表中插入和删除操作比在链表上方便|65506丁55280,|65506I,单选题I56 .设n个顶点e条边的图G用邻

14、接表存储，则求每个顶点入度的时间复杂度为AAO(n)BO(n+e)CCO(n*n)DDO(n*e)I65518丁55286,I65518I单选题57 .对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，邻接表中所有结点总数是。Ae/2B2eCCeDn+e|6549555265,I65495I单选题58 .某非空二叉树的前序序列和后序序列正好相反，则二叉树一定是的二叉树。A空或只有一个结点B高度等于其结点数C任一结点无左孩子DD任一结点无右孩子6550755288,I65507I,单选题59 .在待排序的元素序列基本有序的前提下，效率最高的排序方法是一。CA插入排序CB快速排序C归并排序D

15、选择排序6546255247,单选题6546260 .对顺序存储的线性表，设其长度为n,且在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的个元素。A n/2B (n+1)/2C (n-1)/265537I 55314,判断题6553761.通过关键字比较的方法进行排序，其时间复杂性至少是O(nlog2n)。错误6554055312,判断题6554062.5个顶点的无向图，若不连通，则最多可能有6条边。错误6553855308,判断题6553863 .由二叉树的前序和中序遍历序列可惟一构造这棵二叉树。错误6553255307,判断题6553264 .任何一个森林都可以唯一地

16、与一棵二叉树对应。错误6555355321,判断题6555365 .无向图各顶点度之和就等于边的数量。错误6554255318,判断题6554266 .图的深度优先遍历和广度优先遍历都包含了图的全部顶点。错误|6553055305,65530I判断题67 .有向图各顶点入度之和就等于边的数量。正确错误|65548丁55315,65548I判断题68 .在某个实例的排序结果看出，值相同的两个关键字排序前后领先关系不变，由此可知该排序方法是稳定的。正确c错误6552755303,65527I判断题69 .序列12,23,15,24,22,18,16,30,27是一个堆。正确c错误655315530

17、6,65531I判断题70 .判断顺序储存下队列q是空的条件是q.front=q.rear。C正确C错误I6553955310,65539I判断题71 .满二叉树一定是完全二叉树，反之不然。c正确c错误I6552955300,65529I判断题72 .所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界正确错误6553555304,判断题6553573 .树可以看成是连通的图。错误6554455313,判断题6554474 .用邻接矩阵表示图所用的存储空间大小与图的边数成正比。错误6551755290,判断题6551775 .判断顺序储存下堆栈s是空的条件是s.top=0。正确错误6554155316,判断题6554176 .若散列表的装载因子a0)个结点的树有n-1条边。正确错误I6553455302,65534I判断题78 .哈夫曼编码使一串文字的编码长度最短。1正确1错误I65533丁55299,65533I判断题79 .逻辑结构相同时物理结构也应该相同。正确错误I6554955322,65549I判断题80 .连通图的广度优先搜索中一般要采用队列来暂存刚