《数据结构复习题》.docx

《《数据结构复习题》.docx》由会员分享，可在线阅读，更多相关《《数据结构复习题》.docx（9页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据结构复习题判断题（下列各题，你认为正确的，请在前面的括号内打，错误（ ）。一、 的打。每题1分，共10分）1. n个权值可以构造对应唯一颗哈夫曼树。 对错(正确答案)2. 数据的物理结构是指数据在计算机内的实际的存储形式。 对(正确答案)错3. 对于单链表来说，只有从头结点开始才能扫描表中全部结点。 对错(正确答案)4. 栈是一种对进栈、出栈操作总次数做了限制的线性表。 对错(正确答案)5. n个元素进队列的顺序和出队列的顺序总是一致的。 对(正确答案)错6. 数据的逻辑结构与各数据元素在计算机中如何存储有关。 对错(正确答案)7. 任何递归算法都有递归出口。 对(正确答案)错8. 完全二

2、叉树没有度为一的结点。 对错(正确答案)9. 在先序遍历二叉树的序列中，任何结点其子树的所有结点都是直接跟在该结点之后的。 对(正确答案)错10. 在有向图中，各顶点的入度之和等于各顶点的出度之和。 对(正确答案)错11. 从长度为n的顺序表中删除一个元素，所需时间都是O(n)。 对(正确答案)错12. 双链表的特点是找结点的前驱和后继都很容易。 对(正确答案)错13. 顺序栈中元素值的大小是有序的。 对错(正确答案)14. 栈和队列都是限制存取端的线性表。 对(正确答案)错15. 递归算法不能转换成对应的非递归算法 对错(正确答案)16. 完全二叉树中的每个结点或者没有孩子或者有2个孩子。

3、对错(正确答案)17. 二叉树中至少有一个度为2的结点。 对错(正确答案)18. 强连通分量是有向图中的极大强连通子图。 对(正确答案)错19. 对二叉查找树先序遍历得到一个有序结点序列。 对错(正确答案)二、填空题20. 算法的执行时间是:_ 的函数。 空1答案：问题规模21. 在有n个元素的顺序表中任意位置插入一个元素所需移动结点的平均次数为 _ 。: 空1答案：n/222. 有n个结点的无向图最多有 _ 条边。 空1答案：n(n-1)/2|1/2n(n-1)|1/2(n-1)n23. 无向图的连通分量是指 _ 。 空1答案：极大连通子图24. 可以进行拓扑排序的有向图一定是_ 。 空1答

4、案：有向无环图25. 普里姆算法适用于求_网的最小生成树。 空1答案：边稠密26. 用邻接矩阵A1n，1n存储有向图G,，其第i行的所有元素之和等于顶点i的_。 空1答案：出度|出度之和27. 判断有向图中是否存在回路的方法是图中结点能否进行_排序。 空1答案：拓扑28. 对二叉排序树进行_遍历，可以达到按关键字从小到大排列的结点序列。 空1答案：中序29. 在排序中，任何情况下都不比较关键字的排序是_排序。 空1答案：基数30. 一个算法具有5个特性: （1） _（2） _ （3）_ ，有零个或多个输入、有一个或多个输出。 空1答案：有穷性|确定性|可行性空2答案：确定性|有穷性|可行性空3

5、答案：可行性|有穷性|确定性31. 顺序栈S的栈顶为top, 栈空间地址为0n，则栈空的条件是:（1）_, 栈满的条件是:（2）_ 。 空1答案：top=-1|top-1空2答案：top=n|topn32. 如果一个有向图中没有环，则该图的全部结点可以排成一个_序列。 空1答案：拓扑33. 无向图的邻接矩阵是一个_矩阵。 空1答案：对称34. 具有64个结点的完全二叉树的深度为 _ 空1答案：735. 数据的逻辑结构是指_ 。 空1答案：反映数据元素之间逻辑关系的数据结构|数据元素之间逻辑关系的数据结构36. 带头结点的单链表head为空的判定条件是_。 空1答案：head->next=

6、null|head-nextnull37. 栈是一种具有_特性的线性表 空1答案：先进后出|先进后出，后进先出|后进先出，先进后出38. 顺序队列在实现的时候，通常将数组看成是一个首尾相连的环，这样做的目的是为避免产生 _ 现象。 空1答案：假溢出39. n个结点的二叉树中如果有m个树叶，则一定有_个度为1的结点，_个度为2的结点。 空1答案：n-2m+1空2答案：m-140. 数据结构是一组数据元素的集合和_集合。 空1答案：多种特定关系的|多种特定关系41. 采用哈希存储方法时，用于计算结点存储地址的是_ 。 空1答案：哈希函数42. 二分查找要求查找表中数据元素_。 空1答案：按关键字有

7、序排列43. 克鲁斯卡尔算法适用于求_网的最小生成树。 空1答案：边稀疏44. 在有n个顶点的有向图中，每个顶点的度最大可达_。 空1答案：2(n-1)45. 排序按在排序过程中是否访问内存分为_ 。 空1答案：内排序和外排序46. 设数组A0.M作为循环队列SQ的存储空间，front 为队头指针，rear为对尾指针，则执行出队操作的语句为（） Afront=front+1Bfront=(front+1)%m(正确答案)Crear=rear+1Drear=(rear+1)%m47. 在一个长度为n的顺序表中向第i个元素（01)，f(0)=0,则f(3)的值为（）。 A. 3B. 0C. 6(正

8、确答案)D.150. 所谓简单路径是指（）。 A任何一条边在这条路径上不重复出现B任何一个顶点在这条路径上不重复出现(正确答案)C这条路径由一个顶点序列构成，不包含边D这条路径由一个边的序列构成，不包含顶点51. 对于含有n个顶点的带权连通图，它的最小生成树是指图中任意一个（）。 A由n-1条权值最小的边构成的子图B由n-1条权值之和最小的边构成的子图C由n-1权值之和最小的边构成的连通子图D由n个顶点构成的边的权值之和最小的连通子图(正确答案)52. 在二叉排序树中，凡是新插入的结点，都是没有（）的。 A孩子(正确答案)B.关键字C.平衡因子D.赋值53. 在n个结点的线索二叉树中线索的数目

9、为（）。 An-1B.nC.n+1(正确答案)D.2n54. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少?（） A. 1和 5B. 2和4(正确答案)C. 4和2D. 5和155. 设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是（）。 AXYZB. YZXC. ZXY(正确答案)D. ZYX56. 在数据结构中，从逻辑上可以把数据结构分为（）两类。 A动态结构和静态结构B. 紧凑结构和非紧凑结构C线性结构和非线性结构(正确答案)D. 内部结构和外部结

10、构57. 算法的时间复杂度与（）有关。 A. 问题规模(正确答案)B. 计算机硬件性能C. 编译程序质量D. 程序设计语言58. 在一个单链表中，删除p结点之后的一个结点的操作是 （） 。 A. p-next=p;B. p-next-next=p-next;(正确答案)C. p-next-next=p;D. p-next=p-next-next;59. 经过以下栈运算后，x的值是（） 。InitStack(s); Push(s,a); Push(s,b); Pop(s,x);GetTop(s,x); A.a(正确答案)B.bC.1D.060. 设有13个值组成的哈夫曼树，则有 （）个结点。 A. 13B. 12C. 26D. 25(正确答案)61. 对于一棵具有n个结点的二叉树、高度的最大值为（） 。 A. n(正确答案)B.n-1C.log2nD.n/262. 在一个无向图中，所有顶点的度之和等于边数的 （）倍。 A1/2B。1C。2(正确答案)D。463. 关键路径是事件结点网络（） 。 A从源点到汇点的最长路径(正确答案)B从源点到汇点的最短路径C最长的回路D最短的回路64. 在数据元素有序，元素个数较多而且固定不变的情况下，宜采用 （） 法。 A顺序查找(正确答案)B.二分查找C.树型查找D.哈希查找