《数据结构复习题》判断、填空、选择、名词解释.docx

数据结构复习题判断、填空、选择、名词解释判断题（下列各题，你认为正确的，请在前面的括号内打，错误（ ）。一、 的打×。每题1分，共10分）1. n个权值可以构造对应唯一颗哈夫曼树。 判断题 *对错(正确答案)2. 数据的物理结构是指数据在计算机内的实际的存储形式。 判断题 *对(正确答案)错3. 对于单链表来说，只有从头结点开始才能扫描表中全部结点。 判断题 *对错(正确答案)4. 栈是一种对进栈、出栈操作总次数做了限制的线性表。 判断题 *对错(正确答案)5. n个元素进队列的顺序和出队列的顺序总是一致的。 判断题 *对(正确答案)错6. 数据的逻辑结构与各数据元素在计算机中如何存储有关。 判断题 *对错(正确答案)7. 任何递归算法都有递归出口。 判断题 *对(正确答案)错8. 完全二叉树没有度为一的结点。 判断题 *对错(正确答案)9. 在先序遍历二叉树的序列中，任何结点其子树的所有结点都是直接跟在该结点之后的。 判断题 *对(正确答案)错10. 在有向图中，各顶点的入度之和等于各顶点的出度之和。 判断题 *对(正确答案)错11. 从长度为n的顺序表中删除一个元素，所需时间都是O(n)。 判断题 *对(正确答案)错12. 双链表的特点是找结点的前驱和后继都很容易。 判断题 *对(正确答案)错13. 顺序栈中元素值的大小是有序的。 判断题 *对错(正确答案)14. 栈和队列都是限制存取端的线性表。 判断题 *对(正确答案)错15. 递归算法不能转换成对应的非递归算法 判断题 *对错(正确答案)16. 完全二叉树中的每个结点或者没有孩子或者有2个孩子。 判断题 *对错(正确答案)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答案：有向无环图25. 普里姆算法适用于求_网的最小生成树。 填空题 *空1答案：边稠密26. 用邻接矩阵A1n，1n存储有向图G,，其第i行的所有元素之和等于顶点i的_。 填空题 *空1答案：出度|出度之和27. 判断有向图中是否存在回路的方法是图中结点能否进行_排序。 填空题 *空1答案：拓扑28. 对二叉排序树进行_遍历，可以达到按关键字从小到大排列的结点序列。 填空题 *空1答案：中序29. 在排序中，任何情况下都不比较关键字的排序是_排序。 填空题 *空1答案：基数30. 一个算法具有5个特性: （1） _（2） _ （3）_ ，有零个或多个输入、有一个或多个输出。 填空题 *空1答案：有穷性|确定性|可行性空2答案：确定性|有穷性|可行性空3答案：可行性|有穷性|确定性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-&gt;next=null|head->nextnull37. 栈是一种具有_特性的线性表 填空题 *空1答案：先进后出|先进后出，后进先出|后进先出，先进后出38. 顺序队列在实现的时候，通常将数组看成是一个首尾相连的环，这样做的目的是为避免产生 _ 现象。 填空题 *空1答案：假溢出39. n个结点的二叉树中如果有m个树叶，则一定有_个度为1的结点，_个度为2的结点。 填空题 *空1答案：n-2m+1空2答案：m-140. 数据结构是一组数据元素的集合和_集合。 填空题 *空1答案：多种特定关系的|多种特定关系41. 采用哈希存储方法时，用于计算结点存储地址的是_ 。 填空题 *空1答案：哈希函数42. 二分查找要求查找表中数据元素_。 填空题 *空1答案：按关键字有序排列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个元素（0<in+1）之前插入一个新元素时，需要向后移动 （）个元素。 单选题 *A. n-iB. n-i+1(正确答案)C. n-i-1D. i48. 折半查找要求查找表中各元素的关键字值必须是（）_排列。 单选题 *A. 递增或递减(正确答案)B.递增C.递减 （D.无序49. 递归函数f(n)=f(n-1)+n(n>1)，f(0)=0,则f(3)的值为（）。 单选题 *A. 3B. 0C. 6(正确答案)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个结点的线索二叉树中线索的数目为（）。 单选题 *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. 内部结构和外部结构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.哈希查找65. 在下列排序方法中，关键字比较的次数与记录的初始排列次序无关的是_ 。 填空题 *空1答案：选择排序66. 前缀编码 单选题 *任何一个字符的编码都不是另一个字符编码的前缀。(正确答案)67. 满二叉树 单选题 *深度为K的二叉树，总共有2的k次方-1个结点。(正确答案)68. 完全图 单选题 *有1/2n(n-1)条边的无向图称完全图。分为有向完全图和无向完全图。(正确答案)69. 抽象数据类型 单选题 *是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性,而与其在计算机内部如何表示和实现无关。(正确答案)70. 顺序线性表 单选题 *用一组地址连续的存储单元依次存储线性表的数据元素。(正确答案)71. 完全二叉树 单选题 *深度为k，结点为n的二叉树，当且仅当每一个结点与深度为k的满二叉树中编号从1至n结点编号一一对应时，称为完全二叉树。(正确答案)72. 堆数列 单选题 *首先将根结点的记录与当前树中具有最大序号的记录交换,把交换后具有最大序号的记录输出,得到一个排序的结果。这时的树不再是堆树,排序暂时停止。然后,必须把树重新调整成堆树,再重复上述过程,直到所有记录都排好序。(正确答案)73. 二叉排序树 单选题 *或是一棵空树，或若左与右子树不空，左子树所有结点值小于根结点，右子树所对称该无向图是连通图。(正确答案)74. 连通图 单选题 *对于无向图，若V1到V2有路径，成V1 V2是连通的，若图中任意两点都是连通的，则称该无向图是连通图。(正确答案)75. 生成树 单选题 *一个连通图的生成树是指一个极小连通子图，它含有途中的全部顶点，N-1条边。(正确答案)