2016年春数据结构和算法在线作业

1、您的本次作业分数为：99分单选题1.【第1章第2节】数据结构课程主要研究以下三方面的内容，它们是。A数据、数据元素、数据类型B数据元素、数据类型、算法实现C数据元素、数据的逻辑结构、数据的存储结构D数据的逻辑结构、数据的存储结构、数据的运算正确答案:D单选题2.【第1章第2节】在数据结构中，与所使用的at算机无关的是数据的一结构。A存储B物理C逻辑D物理与存储正确答案:C判断题3.第1章第2节】逻辑结构相同时物理结构也应该相同。正确错误正确答案：错单选题4.【第1章第3节】设某二维数组A：1.n,1.n,则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为。AO(log2n)BO(n)CO

2、(nlog2n)DO(nA2)正确答案:D单选题5.【第1章第3节】计算机算法是指。A计算方法B排序方法C调度方法D解决问题的有限运算序列正确答案:D判断题6.第1章第3节】所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界正确错误正确答案：对单选题7.【第3章第2节】向一个有115个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素。A115B114C58D57正确答案:C单选题8.【第3章第2节】在长度为n的双链表中某结点(已知其地址)之前，插入一个新结点的时间复杂度是。AO(n)BO(log2n)CO(1)DO(nA2)正确答案:C单选题9.【第3章第2节】在一个长度

3、为n的顺序表中，在第i个元素(1<=i<=n)之前插入一个新元素时需向后移动个元素。A1Bn-iCn-i-1Dn-i+1正确答案:D单选题10.第3章第2节】在一个具有n个结点的有序单链表中，插入一个新的结点并使之仍然有序的时间复杂度是。AO(n)BO(log2n)CO(1)DO(nA2)正确答案:A单选题11.第3章第2节】线性表按链式方式存储时，每个结点的存储包括两部分。A数据值与符号B数据与指针C数据与表名D数据项与符号正确答案:B单选题12.第3章第2节】线性表采用链式存储时，其地址。A必须是连续的B必须是不连续的C连续与否均可D部分地址必须是连续的正确答案:C单选题13.

4、第3章第2节】若要求能快速地实现在链表的末尾插入和删除结点的运算，则选择最合适。A单链表B带尾指针的单循环链表C双链表D双循环链表正确答案:B单选题14.第3章第2节】顺序表的特点是。A逻辑上相邻的结点其物理位置不相邻B逻辑上相邻的结点其物理位置亦相邻C顺序表不是随机存储结构D在顺序表中插入和删除操作比在链表上方便正确答案:B单选题15.第3章第2节】链表不具有的特点是。A可随机访问任一元素B插入和删除不需要移动元素C不必事先估计存储空间D所需空间和线性表长度成正比正确答案:A单选题16.第3章第2节】对顺序存储的线性表，设其长度为n,且在任何位置上插入或删除操作都是等概率的。则插入一个元素时

5、平均要移动表中的个元素。An/2B(n+1)/2C(n-1)/2Dn正确答案:A单选题17.第3章第2节】带头结点的单链表Head为空表的判定条件是。AHead->next=HeadBHead->next=NULLCHead!=NULLDHead=NULL正确答案:B判断题18.【第3章第2节】在n个元素的顺序表中删除第i个元素，需要移动n-i个元素。正确错误正确答案：对单选题19.第3章第3节】若某堆栈的输入序列为1,2,3,，n-1,n,输出序列的第1个元素为n,则第i个输出元素为。An-i+lBn-iCiD哪个元素无所谓正确答案:A单选题20.第3章第3节】作进栈操作时，应先

6、判断栈是否为。A空B满C上溢D下溢正确答案:B单选题21.第3章第3节】当字符序列x5y作为字符堆栈的输入时，输出长度为3的且可以作为C语言标识符的个数是。A3个B4个C5个D6个正确答案：A单选题22.第3章第3节】栈结构通常采用的两种存储结构是。A线性存储结构和链表存储结构B散列方式和索引方式C链表存储结构和数组D线性存储结构和非线性存储结构正确答案:D单选题23.第3章第3节】一个栈的进栈序列是a,b,c,d,e,则栈的不可能的出栈序列是。AedcbaBdceabCdecbaDabcde正确答案:B单选题24.第3章第3节】采用不带尾指针的单链表方式表示一个栈，便于结点的插入与删除。栈顶

7、结点的插入与删除通常在链表的进行。A任意位置B链表头尾两端C链表头一端D链表尾一端正确答案:C单选题25.第3章第3节】一个栈的入栈序列是a,b,c,d,则下列序列中不可能的输出序列是。AacbdBdcbaCacdbDdbac正确答案:D判断题26.【第3章第3节】判断顺序储存下堆栈s是空的条件是s.top=0。正确错误正确答案：对单选题27.第3章第4节】队列的操作原则是。A先进先出B先进后出C只能进行插入D只能进行删除正确答案:A单选题28.第3章第4节】判断一个循环队列是空队列的条件是。AQ.rear=Q.frontBQ.front=0CQ.rear=0D(Q.rear+1)%maxsi

8、ze=Q.front正确答案:A判断题29.【第3章第4节】判断顺序储存下队列q是空的条件是q.front=q.rear。正确错误正确答案：对单选题30.第4章第1节】在顺序表2、5、7、10、14、15、18、23、35、41、52中，用二分法查找关键码12需做次关键码比较。A2B3C4D5正确答案:C单选题31.第4章第1节】若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至。A该中间位置B该中间位置一1C该中间位置+1D该中间位置/2正确答案:B单选题32.第4章第1节】对线性表进行二分查找时，要求线性表必须。A以顺序方式存储B

9、以顺序方式存储且元素有序C以链式方式存储D以链式方式存储且元素有序正确答案:B单选题33.第4章第2节】若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是。A根结点无右子树的二叉树B根结点无左子树的二叉树C根节点可能有左子树和右子树的二叉树D各结点只有一个儿子白二叉树正确答案:C单选题34.第4章第2节】树最适合用来表示。A有序数据元素B无序数据元素C元素之间具有分支层次关系的数据D元素之间无联系的数据正确答案:C判断题35.第4章第2节】任何一个森林都可以唯一地与一棵二叉树对应。正确错误正确答案：对判断题36.【第4章第2节】n(n>0)个结点的树有n-1条边。正确错误正确答案：对

10、单选题37.第4章第3节】设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至多为(注意C和D中h是指数)。A2h-1B2(h-1)C2*h-1D2*h正确答案:A单选题38.第4章第3节】在某棵二叉树的一种序列中，如果发现其中每一结点的左孩子均是其前趋，则可判断定这种序列为中序序列。A正确B不正确正确答案:A单选题39.第4章第3节】设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是。Aa是b祖先Ba是b子孙Ca在b左方Da在b右方正确答案:C单选题40.第4章第3节】关于二叉树的三种遍历，下列说法正确的是。A任意两种遍历序列都不可以唯一决定该二叉树B任

11、意两种遍历序列都可以唯一决定该二叉树C先序遍历序列和后序遍历序列可以唯一决定该二叉树D先序遍历序列和中序遍历序列可以口t一决定该二叉树正确答案:D单选题41.【第4章第3节】某非空二叉树的前序序列和后序序列正好相反，则二叉树一定是的二叉树。A空或只有一个结点B高度等于其结点数C任一结点无左孩子D任一结点无右孩子正确答案:A单选题42.第4章第3节】如果某二叉树的先序遍历序列是abdcef,中序遍历序列是dbaefc,则其后序遍历序列是。AdbafecBfecdbaCefcdbaDdbfeca正确答案:D单选题43.第4章第3节】树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分

12、为先序遍历、中序遍历和后序遍历。这里我们把由树转化得到的二叉树叫做这棵树对应的二叉树。那么以下结论中是正确的。A树的先根遍历序列与其对应的二叉树的先序遍历序列相同B树的后根遍历序列与其对应的二叉树的后序遍历序列相同C树的先根遍历序列与其对应的二叉树的中序遍历序列相同D以上都不对正确答案:A单选题44.第4章第3节】已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是。AacbedBdecabCdeabcDcedba正确答案:D单选题45.第4章第3节】设二叉树根结点的层次为1,所有含有15个结点的二叉树中，最小高度是。A6B5C4D3正确答案:C单选题46.第4

13、章第3节】任何一棵二叉树的叶结点在先序、中序和后序遍历的序列中的相对次序。A不发生变化B发生变化C不能确定D以上都不对正确答案:A单选题47.第4章第3节】设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为(注意C和D中h为指数)。A2h-1B2(h-1)C2*h-1D2*h正确答案:A判断题48.【第4章第3节】满二叉树一定是完全二叉树，反之不然。正确错误正确答案：对判断题49.【第4章第3节】任何二叉树的叶子数都要比度为2的结点数多。正确错误正确答案：对判断题50.【第4章第3节】由二叉树的前序和中序遍历序列可惟一构造这棵二叉树。正确错误正确答案：对单选题51

14、.第4章第4节】若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过。An/2BnC(n+1)/2Dn+1正确答案:B判断题52.【第4章第4节】二叉排序树一般用于查找某个元素。正确错误正确答案：对判断题53.第4章第4节】如果某二叉树的左右子树的高度差的绝对值不大于1,则一定是平衡二叉树。正确错误正确答案：错单选题54.第4章第6节】有m个叶子结点的Huffman树所具有的结点总数为。Am+1B2m-1C2mD2m+1正确答案：B判断题55.【第4章第6节】序列12,23,15,24,22,18,16,30,27是一个堆。正确错误正确答案：错判断题56.第4章第6节】哈夫曼编码使一

15、串文字的编码长度最短。正确错误正确答案：对判断题57.【第5章第1节】哈希表是用于查找的技术之一。正确错误正确答案：对单选题58.第5章第2节】将10个元素散列到100000个单元的散列表中，则产生冲突。A一定会B一定不会C仍可能会正确答案：C判断题59.【第5章第2节】若散列表的装载因子a<1,则可避免冲突的产生。正确错误正确答案：错单选题60.第5章第3节】设散列表长为14,散列函数是H(key尸key%11,表中已有数据的关键字为15,38,61,84共四个，现要将关键字为49的结点加到表中，用二次探测法解决冲突，则放入的位置是。A8B3C5D9正确答案:D单选题61.第6章第2节

16、】具有5个顶点的有向完全图有条弧。A10B16C20D25正确答案:C单选题62.第6章第2节】在一个无向图中，所有顶点的度数之和等于所有边数的倍。A1/2B1C2D4正确答案:C判断题63.【第6章第2节】有向图各顶点入度之和就等于边的数量。正确错误正确答案：对判断题64.【第6章第2节】无向图各顶点度之和就等于边的数量。正确错误正确答案：错判断题65.【第6章第2节】树可以看成是连通的图。正确错误正确答案：对判断题66.【第6章第2节】5个顶点的无向图，若不连通，则最多可能有6条边。正确错误正确答案：对单选题67.第6章第3节】下面关于图的存储的叙述中，哪一个是正确的？A用相邻矩阵法存储图

17、，占用的存储空间数只与图中结点个数有关，而与边数无关B用相邻矩阵法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关C用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关D用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关正确答案:A单选题68.第6章第3节】邻接表是图的一种。A顺序存储结构B链式存储结构C索引存储结构D散列存储结构正确答案:B单选题69.第6章第3节】对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，邻接表中所有结点总数是。Ae/2B2eCeDn+e正确答案:B单选题70.第6章第3节】设n个顶点e条边的图G用邻接表存储，则求每

18、个顶点入度的时间复杂度为。AO(n)BO(n+e)CO(n*n)DO(n*e)正确答案:B判断题71.【第6章第3节】用邻接矩阵表示图所用的存储空间大小与图的边数成正比。正确错误正确答案：错单选题72.第6章第4节】如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是。AG肯定不是完全图BG一定不是连通图CG中一定有回路DG有2个连通分量正确答案:C判断题73.【第6章第4节】连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点。正确错误正确答案：对判断题74.【第6章第4节】图的深度优先遍历和广度优先遍历都包含了图的全部顶点。正确错误正确答案：对单选题75.【第

19、6章第5节】下列关于图的生成树的唯一性，正确的是。A生成树是唯一的B生成树是不唯一的C生成树是唯一性不确定D图的生成树有两棵正确答案:C单选题76.第6章第5节】关于无向连通图的最小生成树的个数。A一定有多棵B一定只有一棵C有一棵或多棵D可能不存在正确答案:B单选题77.第7章第2节】一组记录的排序码为(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,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则所采用的排序方法是。A选择排序B希尔排序C归并排序D快速排序正确答案:D判断题79.【第7章第3节】在某个实例的排序结果看出，值相同的两个关键字排序前后领先关系不