浙江大学大数据结构与算法课程自我测试问题详解

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

2、意C和D中h是指数)。X正确答案点评rA 2h-1rB 2(h-1)rC 2*h-1D 2*h正确答案：A窗体底端窗体顶端4. 一个栈的入栈序列是 a,b,c,d,则下列序列中不可能的输出序列是 X正确答案点评厂 A acbd厂 B dcba厂 C acdb厂 D dbac正确答案：D 窗体底端窗体顶端5. 计算机算法是指。X正确答案点评厂A计算方法厂B排序方法厂C调度方法D解决问题的有限运算序列正确答案：D窗体底端窗体顶端6. 关于二叉树的三种遍历，下列说法正确的是 。X正确答案点评厂A任意两种遍历序列都不可以唯一决定该二叉树厂B任意两种遍历序列都可以唯一决定该二叉树厂C先序遍历序列和后序遍

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

4、度为n且在任何位置上插入或删除操作都是等概率的。则插入一个元素时平均要移动表中的 个元素。X正确答案点评cA n/2CB (n+1)/2rC (n -1)/2rD n正确答案：A窗体底端窗体顶端10. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里我们把由树转化得到的二叉树叫做这棵树对应的二叉树。那么以下结论中是正确的。X正确答案点评厂A树的先根遍历序列与其对应的二叉树的先序遍历序列相同厂B树的后根遍历序列与其对应的二叉树的后序遍历序列相同厂 C树的先根遍历序列与其对应的二叉树的中序遍历序列相同厂 D以上都不对正确答案：A 窗体底端窗体顶

5、端11. 在一个无向图中，所有顶点的度数之和等于所有边数的 倍。X正确答案点评” A 1/2厂B 1厂C 2厂D 4正确答案：C 窗体底端窗体顶端12. 如果某二叉树的先序遍历序列是abdcef,中序遍历序列是 dbaefc，则其后序遍历序列X正确答案点评A dbafecB fecdbaC efcdbaD dbfeca正确答案：D窗体底端窗体顶端13. 向一个有115个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素。X正确答案点评厂 A 115厂 B 114rC 58CD 57正确答案：C窗体底端窗体顶端14. 某非空二叉树的前序序列和后序序列正好相反，则二叉树一定是的二叉树

6、。X正确答案点评厂 A空或只有一个结点厂B高度等于其结点数厂C.任一结点无左孩子厂D任一结点无右孩子正确答案：A窗体底端窗体顶端15. 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，邻接表中所有结点总数是。X正确答案点评厂 A e/2厂B 2e厂C eD n+e正确答案：B窗体底端窗体顶端16. 当字符序列x5y作为字符堆栈的输入时，输出长度为3的且可以作为C语言标识符的个数是。X正确答案点评厂A 3个厂B 4个厂C 5个厂D 6个正确答案：A窗体底端窗体顶端17. 用某种排序方法对线性表(25,84,21,47,15,27,68,35,20) 进行排序时，元素序列的变化情 况 如

7、下 (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则所采用的排序方法是 。X正确答案点评厂A选择排序厂B希尔排序厂C归并排序厂D快速排序正确答案：D 窗体底端窗体顶端18. 树最适合用来表示 。X正确答案点评厂A有序数据元素厂B无序数据元素“ C元素之间具有分支层次关系的数据D元素之间无联系的数据正确答案：C 窗体底端窗体顶端19. 设有1000个无序的元素，希望用最快的速度挑选出其中前10排序法。X正确答案点评厂A起泡排序厂B快速排序C堆排序厂D基数排序正确答案：C

8、 窗体底端窗体顶端20. 如果无向图G必须进行二次广度优先搜索才能访问其所有顶点,是。X正确答案点评厂AG肯定不是完全图厂 BG一定不是连通图厂 CG中一定有回路厂 D G有2个连通分量个最大的元素，最好则下列说法中不正确的正确答案：C 窗体底端窗体顶端21. 有m个叶子结点的Huffman树所具有的结点总数为 X正确答案点评r A dA m+1rB 2m-1rC 2mD 2m+1正确答案：B窗体底端12窗体顶端22. 在顺序表2、5、7、10、14、15、18、23、35、41、52中，用二分法查找关键码需做次关键码比较。X正确答案点评cA 2厂B 3厂C 4厂D 5正确答案：C窗体底端窗体

9、顶端23. 将10个元素散列到100000个单元的散列表中，则 产生冲突。X正确答案点评A 一定会厂 B 一定不会厂C仍可能会正确答案：C窗体底端窗体顶端24. 已知某二叉树的后序遍历序列是dabec,中序遍历序列是 debac,它的前序遍历序列是。X正确答案点评厂 A A acbedB decabrC deabcrD cedba正确答案：D 窗体底端窗体顶端25. 一个栈的进栈序列是 a,b,c,d,e, 则栈的不可能的出栈序列是 X正确答案点评cA edcba广B dceabrC decbaCD abcde正确答案：B 窗体底端窗体顶端43),对该数列按从小26. 已知 10 个数据元素为

10、(54, 28, 16，34, 73, 62, 95, 60，26,到大排序，经过一趟冒泡排序后的序列为 。X正确答案点评A 16 , 28, 34, 54, 73, 62, 60, 26, 43, 95rB 28 , 16, 34, 54, 62, 73, 60, 26, 43, 95rC 28, 16, 34, 54, 62, 60, 73, 26, 43, 95rD 16, 28, 34, 54, 62, 60, 73, 26, 43, 95正确答案:B窗体底端窗体顶端27.作进栈操作时，应先判断栈是否为。X正确答案点评CA空CB满CC上溢CD下溢正确答案:B窗体底端窗体顶端最合适。28

11、. 若要求能快速地实现在链表的末尾插入和删除结点的运算，则选择X正确答案点评厂A单链表厂B带尾指针的单循环链表厂C双链表厂D双循环链表正确答案：B窗体底端窗体顶端29. 判断一个循环队列是空队列的条件是 。X正确答案点评cA Q.rear=Q.frontCB Q.fro nt=0C Q.rear=0rD (Q.rear+1)%maxsize=Q.fro nt正确答案：A窗体底端窗体顶端30. 任何一棵二叉树的叶结点在先序、中序和后序遍历的序列中的相对次序X正确答案点评厂 A不发生变化厂B发生变化厂 C不能确定厂 D以上都不对正确答案：A窗体底端窗体顶端31. 下面关于图的存储的叙述中，哪一个是

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

13、的前面，下次的查找区间为从原开始位置至 。X正确答案点评 厂 A该中间位置厂 B该中间位置一1厂 C该中间位置+ 1厂 D该中间位置/ 2正确答案：B窗体底端窗体顶端34. 线性表按链式方式存储时，每个结点的存储包括 两部分。A数据值与符号厂B数据与指针厂C数据与表名D数据项与符号正确答案：B窗体底端窗体顶端35. 下列排序算法的时间复杂度最小的是X正确答案点评厂A冒泡排序厂B希尔排序厂C简单选择排序厂D归并排序正确答案：D窗体底端窗体顶端36. 线性表采用链式存储时，其地址 _X正确答案点评厂 A必须是连续的厂 B必须是不连续的厂C连续与否均可厂D部分地址必须是连续的正确答案：C窗体底端窗体

14、顶端条弧。37. 具有5个顶点的有向完全图有 A 10CC 20CD 25正确答案：C窗体底端窗体顶端38. 设某二维数组 A : 1.n , 1.n ,则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为。X正确答案点评厂 A O( log2n )厂 B 0(n)厂 C O(nl og2 n)厂 D 0(n A2)正确答案：D窗体底端窗体顶端39. 关于无向连通图的最小生成树的个数 。X正确答案点评 厂A 一定有多棵厂 B 一定只有一棵C有一棵或多棵CD可能不存在正确答案：B窗体底端窗体顶端40. 设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为(注意C和

15、D中h为指数)。X正确答案点评A 2h-1厂 C 2*h-1厂 D 2*h正确答案：A窗体底端窗体顶端41. 若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过 X正确答案点评厂 A n/2厂B n厂 C (n+1)/2厂 D n+1正确答案：B 窗体底端窗体顶端42. 若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是。X正确答案点评A根结点无右子树的二叉树厂B根结点无左子树的二叉树厂C根节点可能有左子树和右子树的二叉树厂D各结点只有一个儿子的二叉树正确答案：C窗体底端窗体顶端43. 在长度为n的双链表中某结点(已知其地址)之前，插入一个新结点的时间复杂度是。X正确答案点评r

16、A O( n)B O(log2 n)D 0(n A2)正确答案：C 窗体底端窗体顶端44. 设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是 。X正确答案点评厂 A a是b祖先厂 B a是b子孙厂 C a在b左方C D a在b右方正确答案：C窗体底端窗体顶端45. 若某堆栈的输入序列为1, 2, 3,，n-1 , n,输出序列的第1个元素为n,则第i个输出元素为。X正确答案点评厂 A n-i+l厂 B n-i厂C i“ D哪个元素无所谓正确答案：A窗体底端窗体顶端46. 数据结构课程主要研究以下三方面的内容，它们是 。X正确答案点评 厂 A数据、数据元素、数据类型 厂B数据元素

17、、数据类型、算法实现C数据元素、数据的逻辑结构、数据的存储结构D数据的逻辑结构、数据的存储结构、数据的运算正确答案：D窗体底端窗体顶端则可判断定47. 在某棵二叉树的一种序列中，如果发现其中每一结点的左孩子均是其前趋，这种序列为中序序列。X正确答案点评厂A正确广B不正确正确答案：A窗体底端窗体顶端48. 设二叉树根结点的层次为 1所有含有15个结点的二叉树中，最小高度是 X正确答案点评厂A 6厂B 5厂C 4厂D 3正确答案：C窗体底端窗体顶端49. 设n个顶点e条边的图G用邻接表存储，则求每个顶点入度的时间复杂度为 X正确答案点评CA 0( n)rB 0(n+e)CC 0( n*n)rD 0

18、( n*e)正确答案：B 窗体底端窗体顶端50. 在待排序的兀素序列基本有序的前提下，效率最高的排序方法是 X正确答案点评厂A插入排序厂B快速排序C归并排序厂D选择排序正确答案：A窗体底端窗体顶端51. 下列关于图的生成树的唯一性，正确的是 X正确答案点评厂A生成树是唯一的厂 B生成树是不唯一的厂 C生成树是唯一性不确定厂D图的生成树有两棵正确答案：C窗体底端窗体顶端52. 栈结构通常采用的两种存储结构是 。X正确答案点评厂A线性存储结构和链表存储结构厂B散列方式和索引方式厂C链表存储结构和数组厂D线性存储结构和非线性存储结构正确答案：D窗体底端窗体顶端53. 队列的操作原则是。X正确答案点评

19、c A先进先出厂B先进后出厂C只能进行插入厂D只能进行删除正确答案：A窗体底端窗体顶端54. 一组记录的排序码为(20,29,11,74,35,3,8,56)，则利用堆排序方法建立的初始(小顶)堆为。X正确答案点评厂 A 20,29,11,74,35,3,8,56厂 B 3,29,8,56,35,20,11,74厂 C 3,8,11,20,29,35,56,74厂 D 20,29,3,8,11,35,74,56正确答案：B 窗体底端窗体顶端55. 在一个具有n个结点的有序单链表中，插入一个新的结点并使之仍然有序的时间复杂度是。X正确答案点评rA 0( n)rB O(log2 n)rC 0(1)

20、cD O(n A2)正确答案：A窗体底端窗体顶端56. 在一个长度为n的顺序表中，在第i个元素(1<=i<=n )之前插入一个新元素时需向后移动个元素。X正确答案点评cA 1CB n-i厂 C n-i-1厂 D n-i+1正确答案：D窗体底端窗体顶端结构。57. 在数据结构中，与所使用的计算机无关的是数据的X正确答案点评c A存储厂B物理厂C逻辑厂D物理与存储正确答案：C窗体底端窗体顶端58. 对线性表进行二分查找时，要求线性表必须_X正确答案点评厂A以顺序方式存储厂B以顺序方式存储且元素有序厂C以链式方式存储D以链式方式存储且元素有序正确答案：B窗体底端窗体顶端59. 带头结点的

21、单链表 Head为空表的判定条件是.A Head->n ext=Head 厂 B Head-> next=NULL 厂 C Head!=NULL 厂 D Head=NULL正确答案：B 窗体底端窗体顶端栈顶结点的插入与60. 采用不带尾指针的单链表方式表示一个栈，便于结点的插入与删除。删除通常在链表的 进行。X正确答案点评 厂 A任意位置厂B链表头尾两端厂C链表头一端厂 D链表尾一端正确答案：C窗体底端2、判断题窗体顶端61. 用邻接矩阵表示图所用的存储空间大小与图的边数成正比。X正确答案点评r r对 错正确答案：错窗体底端窗体顶端62. 哈希表是用于查找的技术之一。X正确答案点评

22、正确答案：对窗体底端窗体顶端63. 判断顺序储存下堆栈 s是空的条件是s.top=0 。X正确答案点评对错正确答案：对窗体底端窗体顶端64. 若散列表的装载因子a <1,则可避免冲突的产生。X正确答案点评对错正确答案：错窗体底端窗体顶端65. 二叉排序树一般用于查找某个元素。X正确答案点评c c对 错正确答案：对窗体底端窗体顶端66. 满二叉树一定是完全二叉树，反之不然。X正确答案点评r r对 错正确答案：对窗体底端窗体顶端67. 哈夫曼编码使一串文字的编码长度最短。正确答案：对窗体底端窗体顶端68. 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界X正确答案点评对错正确答案：对窗体底端窗体顶端69. 连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点。X正确答案点评对错正确答案：对窗体底端窗体顶端70. n(n>0)个结点的树有n-1条边。X正确答案点评c c对 错正确答案：对窗体底端窗体顶端71. 5个顶点的无向图，若不连通，则最多可能有6条边。X正确答案点评对广错 正确答案：对窗体底端窗体顶端72. 任何一个森林都可