浙江大学数据结构与算法课程自我测试答案

窗体顶端1. 邻接表是图的一种 ____。正确答案 点评顺序存储结构链式存储结构索引存储结构散列存储结构正确答案： B答案讲解：无【试题出处】第6章第3节1窗体底端窗体顶端一组记录的关键字为（46,79,56,38,40,84）,则利用快速排序的方法，以第一个记录为基准元素得到的一次划分结果为。正确答案点评38,40,46,56,79,8440,38,46,79,56,8440,38,46,56,79,8440,38,46,84,56,79正确答案： C窗体底端窗体顶端设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至多为_____(注意C和D中h是指数)。正确答案点评2h-12(h-1)2*h-1D2*h正确答案： A窗体底端窗体顶端4. 一个栈的入栈序列是正确答案 点评

a,b,c,d,

则下列序列中不可能的输出序列是

_______

。acbddcbaacdbdbac正确答案： D窗体底端窗体顶端5. 计算机算法是指 ______。正确答案 点评计算方法排序方法调度方法解决问题的有限运算序列正确答案：D窗体底端窗体顶端6. 关于二叉树的三种遍历，下列说法正确的是正确答案 点评

____。任意两种遍历序列都不可以唯一决定该二叉树任意两种遍历序列都可以唯一决定该二叉树先序遍历序列和后序遍历序列可以唯一决定该二叉树先序遍历序列和中序遍历序列可以唯一决定该二叉树正确答案：D窗体底端窗体顶端7. 顺序表的特点是 ______。正确答案 点评逻辑上相邻的结点其物理位置不相邻逻辑上相邻的结点其物理位置亦相邻顺序表不是随机存储结构在顺序表中插入和删除操作比在链表上方便正确答案：B窗体底端窗体顶端8. 设散列表长为 14，散列函数是 H(key)=key%11,表中已有数据的关键字为 15，38，61，共四个，现要将关键字为 49的结点加到表中，用二次探测法解决冲突，则放入的位置是

84____________

。正确答案

点评8359正确答案： D窗体底端窗体顶端9. 对顺序存储的线性表， 设其长度为 n，且在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的 _____个元素。

则正确答案

点评n/2(n+1)/2(n-1)/2n正确答案： A窗体底端窗体顶端树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。 这里我们把由树转化得到的二叉树叫做这棵树对应的二叉树。 那么以下结论中 _____是正确的。正确答案 点评树的先根遍历序列与其对应的二叉树的先序遍历序列相同树的后根遍历序列与其对应的二叉树的后序遍历序列相同树的先根遍历序列与其对应的二叉树的中序遍历序列相同以上都不对正确答案： A窗体底端窗体顶端11.在一个无向图中，所有顶点的度数之和等于所有边数的 ____倍。正确答案 点评1/2124正确答案： C窗体底端窗体顶端12.如果某二叉树的先序遍历序列是 abdcef，中序遍历序列是 dbaefc，则其后序遍历序列是____。正确答案 点评dbafecfecdbaefcdbaDdbfeca正确答案： D窗体底端窗体顶端13.向一个有 115个元素的顺序表中插入一个新元素并保持原来顺序不变， 平均要移动 _____个元素。正确答案 点评1151145857正确答案： C窗体底端窗体顶端14.某非空二叉树的前序序列和后序序列正好相反，则二叉树一定是 _____的二叉树。正确答案 点评空或只有一个结点高度等于其结点数.任一结点无左孩子任一结点无右孩子正确答案：A窗体底端窗体顶端15.对于一个具有 n个顶点和 e条边的无向图， 若采用邻接表表示， 邻接表中所有结点总数是_____。正确答案点评e/22eeDn+e正确答案： B窗体底端窗体顶端16.当字符序列 x5y 作为字符堆栈的输入时，输出长度为 3的且可以作为 C语言标识符的个数是____。正确答案 点评A3个B4个C5个D6个正确答案： A窗体底端窗体顶端17. 用某种排序方法对线性表 (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窗体底端窗体顶端18.树最适合用来表示 _____。正确答案 点评有序数据元素无序数据元素元素之间具有分支层次关系的数据元素之间无联系的数据正确答案： C窗体底端窗体顶端19.设有 1000个无序的元素 ,希望用最快的速度挑选出其中前 10个最大的元素 ,最好____排序法。正确答案 点评起泡排序快速排序堆排序基数排序正确答案：C窗体底端窗体顶端20.如果无向图 G必须进行二次广度优先搜索才能访问其所有顶点， 则下列说法中不正确的是_____。正确答案点评AG肯定不是完全图BG一定不是连通图CG中一定有回路DG有2个连通分量正确答案： C窗体底端窗体顶端21.有m个叶子结点的 Huffman 树所具有的结点总数为 ____。正确答案 点评m+12m-12mD2m+1正确答案： B窗体底端窗体顶端22.在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找关键码12需做____次关键码比较。正确答案点评2345正确答案： C窗体底端窗体顶端23.将10个元素散列到正确答案 点评

100000

个单元的散列表中，则

__________

产生冲突。一定会一定不会仍可能会正确答案：C窗体底端窗体顶端24. 已知某二叉树的后序遍历序列是____。

dabec,

中序遍历序列是

debac,

它的前序遍历序列是正确答案

点评acbeddecabdeabccedba正确答案： D窗体底端窗体顶端25.一个栈的进栈序列是 a,b,c,d,e, 则栈的不可能的出栈序列是 _____。正确答案 点评edcbadceabdecbaabcde正确答案： B窗体底端窗体顶端26.已知 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窗体底端窗体顶端27.作进栈操作时，应先判断栈是否为 _____。正确答案 点评空满上溢下溢正确答案：B窗体底端窗体顶端28.若要求能快速地实现在链表的末尾插入和删除结点的运算，则选择 _____最合适。正确答案 点评单链表带尾指针的单循环链表双链表双循环链表正确答案：B窗体底端窗体顶端29.判断一个循环队列是空队列的条件是正确答案 点评

_____

。Q.rear==Q.frontQ.front==0Q.rear==0(Q.rear+1)%maxsize==Q.front正确答案： A窗体底端窗体顶端30.任何一棵二叉树的叶结点在先序、中序和后序遍历的序列中的相对次序正确答案 点评

____。不发生变化发生变化不能确定以上都不对正确答案：A窗体底端窗体顶端下面关于图的存储的叙述中，哪一个是正确的？正确答案A

点评用相邻矩阵法存储图

,占用的存储空间数只与图中结点个数有关

,而与边数无关B用相邻矩阵法存储图

,占用的存储空间数只与图中边数有关

,而与结点个数无关用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关正确答案：A窗体底端窗体顶端32.链表不具有的特点是 _____。正确答案 点评可随机访问任一元素插入和删除不需要移动元素不必事先估计存储空间所需空间和线性表长度成正比正确答案：A窗体底端窗体顶端33.若用二分查找法取得的中间位置元素键值大于被查找值，

说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至

____。正确答案

点评该中间位置该中间位置－1该中间位置＋1该中间位置／2正确答案： B窗体底端窗体顶端34.线性表按链式方式存储时，每个结点的存储包括正确答案 点评

_____

两部分。数据值与符号数据与指针数据与表名数据项与符号正确答案：B窗体底端窗体顶端35.下列排序算法的时间复杂度最小的是 ____。正确答案 点评冒泡排序希尔排序简单选择排序归并排序正确答案：D窗体底端窗体顶端36.线性表采用链式存储时，其地址 _____。正确答案 点评必须是连续的必须是不连续的连续与否均可部分地址必须是连续的正确答案：C窗体底端窗体顶端37.具有 5个顶点的有向完全图有 ____条弧。正确答案 点评A10162025正确答案： C窗体底端窗体顶端设某二维数组A［1..n，1..n］，则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为______。正确答案点评AO（log2n）O(n)O(nlog2n)O(n^2)正确答案： D窗体底端窗体顶端39.关于无向连通图的最小生成树的个数 _____。正确答案 点评一定有多棵一定只有一棵有一棵或多棵可能不存在正确答案：B窗体底端窗体顶端设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为____(注意C和D中h为指数)。正确答案点评A2h-12(h-1)2*h-12*h正确答案： A窗体底端窗体顶端41.若构造一棵具有 n个结点的二叉排序树，最坏的情况下其深度不会超过 ____。正确答案 点评n/2n(n+1)/2n+1正确答案： B窗体底端窗体顶端42.若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是 ____。正确答案 点评根结点无右子树的二叉树根结点无左子树的二叉树根节点可能有左子树和右子树的二叉树各结点只有一个儿子的二叉树正确答案：C窗体底端窗体顶端在长度为n的双链表中某结点（已知其地址）之前，插入一个新结点的时间复杂度是_____ 。正确答案 点评AO(n)BO(log2n)O(1)O(n^2)正确答案： C窗体底端窗体顶端44.设a,b为一棵二叉树上的两个结点，在中序遍历时， a在b前的条件是 ____。正确答案 点评Aa是b祖先Ba是b子孙Ca在b左方Da在b右方正确答案： C窗体底端窗体顶端45.若某堆栈的输入序列为 1，2，3，⋯，n-1，n，输出序列的第 1个元素为 n，则第 i个输出元素为 ______。正确答案 点评n-i+ln-ii哪个元素无所谓正确答案：A窗体底端窗体顶端46.数据结构课程主要研究以下三方面的内容，它们是 ______。正确答案 点评数据、数据元素、数据类型数据元素、数据类型、算法实现数据元素、数据的逻辑结构、数据的存储结构数据的逻辑结构、数据的存储结构、数据的运算正确答案：D窗体底端窗体顶端在某棵二叉树的一种序列中，如果发现其中每一结点的左孩子均是其前趋，则可判断定这种序列为中序序列。正确答案点评正确不正确正确答案：A窗体底端窗体顶端48.设二叉树根结点的层次为 1，所有含有 15个结点的二叉树中，最小高度是 _____。正确答案 点评6543正确答案： C窗体底端窗体顶端49.设n个顶点 e条边的图 G用邻接表存储，则求每个顶点入度的时间复杂度为 ____。正确答案 点评O(n)O(n+e)O(n*n)O(n*e)正确答案： B窗体底端窗体顶端50.在待排序的元素序列基本有序的前提下，效率最高的排序方法是

____

。正确答案 点评插入排序快速排序归并排序选择排序正确答案：A窗体底端窗体顶端51.下列关于图的生成树的唯一性，正确的是正确答案 点评

_____

。生成树是唯一的生成树是不唯一的生成树是唯一性不确定图的生成树有两棵正确答案：C窗体底端窗体顶端52.栈结构通常采用的两种存储结构是正确答案 点评

_____。线性存储结构和链表存储结构散列方式和索引方式链表存储结构和数组线性存储结构和非线性存储结构正确答案：D窗体底端窗体顶端53.队列的操作原则是 _____。正确答案 点评先进先出先进后出只能进行插入只能进行删除正确答案：A窗体底端窗体顶端54.一组记录的排序码为（____。

20,29,11,74,35,3,8,56

），则利用堆排序方法建立的初始

(小顶

)堆为正确答案

点评20,29,11,74,35,3,8,563,29,8,56,35,20,11,743,8,11,20,29,35,56,7420,29,3,8,11,35,74,56正确答案： B窗体底端窗体顶端55.在一个具有

n个结点的有序单链表中，

插入一个新的结点并使之仍然有序的时间复杂度是______。正确答案点评O(n)O(log2n)O(1)O(n^2)正确答案： A窗体底端窗体顶端56.在一个长度为

n的顺序表中，在第

i个元素（

1<=i<=n

）之前插入一个新元素时需向后移动_______个元素。正确答案点评1n-in-i-1n-i+1正确答案： D窗体底端窗体顶端57.在数据结构中，与所使用的计算机无关的是数据的正确答案 点评

____结构。存储物理逻辑物理与存储正确答案：C窗体底端窗体顶端58.对线性表进行二分查找时，要求线性表必须正确答案 点评

____。以顺序方式存储以顺序方式存储且元素有序以链式方式存储以链式方式存储且元素有序正确答案：B窗体底端窗体顶端59.带头结点的单链表正确答案 点评

Head

为空表的判定条件是

______

。Head->next==HeadHead->next==NULLHead!=NULLHead==NULL正确答案： B窗体底端窗体顶端采用不带尾指针的单链表方式表示一个栈，便于结点的插入与删除。栈顶结点的插入与删除通常在链表的 _____进行。正确答案 点评任意位置链表头尾两端链表头一端链表尾一端正确答案： C窗体底端2、 判断题窗体顶端用邻接矩阵表示图所用的存储空间大小与图的边数成正比。正确答案点评对 错正确答案：错窗体底端窗体顶端哈希表是用于查找的技术之一。正确答案点评对 错正确答案：对窗体底端窗体顶端63.判断顺序储存下堆栈 s是空的条件是 s.top==0。正确答案 点评对 错正确答案：对窗体底端窗体顶端64.若散列表的装载因子 α<1，则可避免冲突的产生。正确答案 点评对 错正确答案：错窗体底端窗体顶端二叉排序树一般用于查找某个元素。正确答案点评对 错正确答案：对窗体底端窗体顶端满二叉树一定是完全二叉树，反之不然。正确答案点评对 错正确答案：对窗体底端窗体顶端哈夫曼编码使一串文字的编码长度最短。正确答案点评对 错正确答案：对窗体底端窗体顶端所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界正确答案点评对 错正确答案：对窗体底端窗体顶端69.连通图的广度优先搜索中一般要采用队列 来暂存刚访问过的顶点。正确答案 点评对 错正确答案：对窗体底端窗体顶端n(n>0)个结点的树有n-1条边。正确答案点评对 错正确答案：对窗体底端窗体顶端71.5个顶点的无向图，若不连通，则最多可能有 6条边。正确答案 点评对 错正确答案：对窗体