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

1、?单项选择题1.【第1章第2节】数据构造课程主要研究以下三方面的内容，它们是_。数据、数据元素、数据种类数据元素、数据种类、算法实现数据元素、数据的逻辑构造、数据的储藏构造数据的逻辑构造、数据的储藏构造、数据的运算正确答案:D?单项选择题2.【第1章第2节】在数据构造中，与所使用的计算机没关的是数据的_构造。?储藏物理逻辑物理与储藏正确答案:C?判断题【第1章第2节】逻辑构造相同时物理构造也应该相同。?正确错误正确答案:错?单项选择题【第1章第3节】设某二维数组A1.n，1.n，则在该数组中用次序查找法查找一个元素的时间复杂性的量级为_。O（log2n）O(n)O(nlog2n)O(n2)正确

2、答案:D?单项选择题5.【第1章第3节】计算机算法是指_。?计算方法排序方法调换方法解决问题的有限运算序列正确答案:D?判断题【第1章第3节】所谓时间复杂度是指最坏情况下，估计算法执行时间的一个上界?正确错误正确答案:对?单项选择题【第3章第2节】在长度为n的双链表中某结点（已知其地址）从前，插入一个新结点的时间复杂度是_。?AO(n)?BO(log2n)?CO(1)DO(n2)正确答案:C?单项选择题8.【第3章第2节】线性表按链式方式储藏时，每个结点的储藏包括_两部分。数据值与符号数据与指针数据与表名数据项与符号正确答案:B?单项选择题【第3章第2节】链表不拥有的特点是_。?A可随机接见任

3、一元素?插入和删除不需要搬动元素不用早先估计储藏空间所需空间和线性表长度成正比正确答案:A?单项选择题【第3章第2节】对次序储藏的线性表，设其长度为n，且在任何地址上插入或删除操作都是等概率的。则插入一个元素时平均要搬动表中的_个元素。n/2(n+1)/2(n-1)/2n正确答案:A?单项选择题?【第3章第2节】在一个拥有n个结点的有序单链表中，插入一个新的结点并使之依旧有序的时间复杂度是_。O(n)O(log2n)O(1)O(n2)正确答案:A?单项选择题【第3章第2节】线性表采用链式储藏时，其地址_。A必定是连续的B必定是不连续的C连续与否均可部分地址必定是连续的正确答案:C?单项选择题1

4、3.【第3章第2节】若要求能快速地实现在链表的尾端插入和删除结点的运算，则选择_最合适。单链表带尾指针的单循环链表双链表双循环链表正确答案:B?单项选择题14.【第3章第2节】带头结点的单链表Head为空表的判断条件是_。Head-next=HeadHead-next=NULLHead!=NULLHead=NULL正确答案:B?单项选择题15.【第3章第2节】次序表的特点是_。?逻辑上相邻的结点其物理地址不相邻逻辑上相邻的结点其物理地址亦相邻次序表不是随机储藏构造在次序表中插入和删除操作比在链表上方便正确答案:B?单项选择题【第3章第2节】在一个长度为n的次序表中，在第i个元素（1=i0)个结

5、点的树有n-1条边。?正确错误正确答案:对?单项选择题【第4章第3节】任何一棵二叉树的叶结点在先序、中序和后序遍历的序列中的相对次序_。不发生变化发生变化不能够确定?D以上都不对正确答案:A?单项选择题【第4章第3节】设二叉树根结点的层次为1，全部含有15个结点的二叉树中，最小高度是_。6543正确答案:C?单项选择题【第4章第3节】某非空二叉树的前序序列和后序序列正好相反，则二叉树必然是_的二叉树。空或只有一个结点高度等于其结点数?C.任一结点无左孩子?D任一结点无右孩子正确答案:A?单项选择题40.【第4章第3节】关于二叉树的三种遍历，以下说法正确的选项是_。?任意两种遍历序列都不能够够独

6、一决定该二叉树任意两种遍历序列都能够独一决定该二叉树先序遍历序列和后序遍历序列能够独一决定该二叉树先序遍历序列和中序遍历序列能够独一决定该二叉树正确答案:D?单项选择题【第4章第3节】已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是_。acbeddecab?Cdeabc?Dcedba正确答案:D?单项选择题【第4章第3节】设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包括的结点数至多为_(注意C和D中h是指数)。2h-12(h-1)2*h-12*h正确答案:A?单项选择题43.【第4章第3节】设a,b为一棵二叉树上的两个结点，在中序遍历时，a

7、在b前的条件是_。?Aa是b祖先?Ba是b后辈?a在b左方a在b右方正确答案:C?单项选择题【第4章第3节】树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里我们把由树转变获取的二叉树叫做这棵树对应的二叉树。那么以下结论中_是正确的。?树的先根遍历序列与其对应的二叉树的先序遍历序列相同树的后根遍历序列与其对应的二叉树的后序遍历序列相同树的先根遍历序列与其对应的二叉树的中序遍历序列相同以上都不对正确答案:A?单项选择题【第4章第3节】在某棵二叉树的一种序列中，若是发现其中每一结点的左孩子均是其前趋，则可判判断这种序列为中序序列。?A正确B不正确

8、正确答案:A?单项选择题【第4章第3节】设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包括的结点数最少为_(注意C和D中h为指数)。2h-12(h-1)2*h-12*h正确答案:A?单项选择题47.【第4章第3节】若是某二叉树的先序遍历序列是abdcef，中序遍历序列是dbaefc，则以后序遍历序列是_。?Adbafec?BfecdbaCefcdbaDdbfeca正确答案:D?判断题【第4章第3节】满二叉树必然是完好二叉树，反之不然。?正确错误正确答案:对?判断题49.【第4章第3节】任何二叉树的叶子数都要比度为2的结点数多。?正确错误正确答案:对?判断题【第4章第3节】由二叉

9、树的前序和中序遍历序列可独一构造这棵二叉树。?正确错误正确答案:对?单项选择题【第4章第4节】若构造一棵拥有n个结点的二叉排序树，最坏的情况下其深度不会高出_。?An/2?Bn?C(n+1)/2?Dn+1正确答案:B?判断题52.【第4章第4节】二叉排序树一般用于查找某个元素。?正确错误正确答案:对?判断题53.【第4章第4节】若是某二叉树的左右子树的高度差的绝对值不大于1，则必然是平衡二叉树。?正确错误正确答案:错?单项选择题【第4章第6节】有m个叶子结点的Huffman树所拥有的结点总数为_。Am+1B2m-1C2mD2m+1正确答案:B?判断题55.【第4章第6节】序列12,23,15,

10、24,22,18,16,30,27是一个堆。?正确错误正确答案:错?判断题【第4章第6节】哈夫曼编码使一串文字的编码长度最短。?正确错误正确答案:对?判断题【第5章第1节】哈希表是用于查找的技术之一。?正确错误正确答案:对?单项选择题?58【.第5章第2节】将10个元素散列到100000个单元的散列表中，则_产生矛盾。必然会必然不会仍可能会正确答案:C?判断题【第5章第2节】若散列表的装载因子1，则可防备矛盾的产生。?正确错误正确答案:错?单项选择题【第5章第3节】设散列表长为14，散列函数是H(key)=key%11,表中已有数据的要点字为15，38，61，84共四个，现要将要点字为49的结

11、点加到表中，用二次探测法解决矛盾，则放入的地址是_。?A8?B3?C5D9正确答案:D?单项选择题61.【第6章第2节】在一个无向图中，全部极点的度数之和等于全部边数的_倍。1/2124正确答案:C?单项选择题62.【第6章第2节】拥有5个极点的有向完好图有_条弧。?A10?B16C20D25正确答案:C?判断题【第6章第2节】树能够看作是连通的图。?正确错误正确答案:对?判断题64.【第6章第2节】5个极点的无向图，若不连通，则最多可能有6条边。?正确错误正确答案:对?判断题【第6章第2节】有向图各极点入度之和就等于边的数量。?正确错误正确答案:对?判断题【第6章第2节】无向图各极点度之和就

12、等于边的数量。?正确错误正确答案:错?单项选择题【第6章第3节】关于一个拥有n个极点和e条边的无向图，若采用毗邻表表示，毗邻表中全部结点总数是_。e/22ee?Dn+e正确答案:B?单项选择题68.【第6章第3节】设n个极点e条边的图G用毗邻表储藏，则求每个极点?入度的时间复杂度为_。O(n)O(n+e)O(n*n)O(n*e)正确答案:B?单项选择题【第6章第3节】下面关于图的储藏的表达中，哪一个是正确的？?A用相邻矩阵法储藏图,占用的储藏空间数只与图中结点个数有关,而与边数没关?B用相邻矩阵法储藏图,占用的储藏空间数只与图中边数有关,而与结点个数没关?用毗邻表法储藏图，占用的储藏空间数只与

13、图中结点个数有关，而与边数没关用毗邻表法储藏图，占用的储藏空间数只与图中边数有关，而与结点个数没关正确答案:A?单项选择题【第6章第3节】毗邻表是图的一种_。A次序储藏构造B链式储藏构造C索引储藏构造散列储藏构造正确答案:B?判断题71.【第6章第3节】用毗邻矩阵表示图所用的储藏空间大小与图的边数成正比。?正确错误正确答案:错?单项选择题【第6章第4节】若是无向图G必定进行二次广度优先找寻才能接见其全部极点，则以下说法中不正确的选项是_。?AG必然不是完好图?G必然不是连通图G中必然有回路G有2个连通重量正确答案:C?判断题73.【第6章第4节】连通图的广度优先找寻中一般要采用队列来暂存刚接见

14、过的极点。?正确错误正确答案:对?判断题74.【第6章第4节】图的深度优先遍历和广度优先遍历都包括了图的全部极点。?正确错误正确答案:对?单项选择题【第6章第5节】关于无向连通图的最小生成树的个数_。A必然有多棵B必然只有一棵C有一棵或多棵可能不存在正确答案:B?单项选择题76.【第6章第5节】以下关于图的生成树的独一性，正确的选项是_。?A生成树是独一的?生成树是不独一的生成树是独一性不确定图的生成树有两棵正确答案:C?单项选择题77.【第7章第2节】一组记录的排序码为（20,29,11,74,35,3,8,56），则利用堆排序方法建立的初始(小顶)堆为_。?A20,29,11,74,35,

15、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正确答案:B?单项选择题78.【第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则所采用的排序方法是_。选择排序希尔排序归并排序快速排序正确答案:D?判断题【第7章第3节】在某个实例的排序结果看出

16、，值相同的两个要点字排序前后当先关系不变，由此可知该排序方法是牢固的。?正确错误正确答案:错?单项选择题80.【第7章第4节】一组记录的要点字为（46,79,56,38,40,84）,则利用快速排序的方法，以第一个记录为基准元素获取的一次划分结果为。?A38,40,46,56,79,84?40,38,46,79,56,8440,38,46,56,79,8440,38,46,84,56,79正确答案:C?单项选择题【第7章第4节】已知10个数据元素为（54，28，16，34，73，62，95，60，26，43），对该数列按从小到大排序，经过一趟冒泡排序后的序列为_。16，28，34，54，73，62，60，26，43，9528，16，34，54，62，73，60，26，43，9528，16，34，54，62，60，73，26，43，9516，28，34，54，62，60，73，26，43，95正确答案:B?单项选择题【第7章第8节