下载文档原格式
数据结构考试题及答案一、选择题（每题2分，共20分）1. 以下哪个不是线性数据结构？A. 数组B. 链表C. 树D. 图2. 在一个单链表中，删除一个节点的操作需要知道该节点的：A. 地址B. 值C. 索引D. 前驱节点的引用3. 栈（Stack）是一种：A. 线性表B. 树状结构C. 图结构D. 散列表4. 哈希表解决冲突最常用的方法是：A. 排序B. 链地址法C. 再散列D. 除留余数法5. 以下哪个排序算法是稳定的？A. 快速排序B. 冒泡排序C. 选择排序D. 堆排序二、简答题（每题10分，共30分）1. 简述数组和链表的区别。
2. 解释二叉搜索树的基本概念及其优势。
3. 什么是递归？请给出一个简单的递归算法例子。
三、计算题（每题25分，共50分）1. 给定一个无序数组，请写出一个时间复杂度为O(n log n)的排序算法，并说明其工作原理。
2. 描述如何使用队列来实现一个简单的文本编辑器的撤销和重做功能。
四、编程题（共30分）编写一个函数，该函数接受一个整数数组作为参数，返回数组中所有元素的和。
如果数组为空，返回0。
答案一、选择题1. 答案：C（树和图都是非线性结构）2. 答案：D（需要前驱节点的引用来删除节点）3. 答案：A（栈是一种后进先出的特殊线性表）4. 答案：B（链地址法是解决哈希冲突的常用方法）5. 答案：B（冒泡排序是稳定的排序算法）二、简答题1. 数组和链表的区别：- 数组是连续的内存空间，链表是非连续的。
- 数组的索引访问速度快，链表需要遍历。
- 数组的大小固定，链表动态可变。
2. 二叉搜索树的基本概念及其优势：- 二叉搜索树是一种特殊的二叉树，左子树上所有节点的值小于它的根节点的值，右子树上所有节点的值大于它的根节点的值。
- 优势：支持快速的查找、插入和删除操作。
3. 递归是函数自己调用自己的过程。
例如，计算n的阶乘的递归算法： ```cint factorial(int n) {if (n <= 1) return 1;return n * factorial(n - 1);}```三、计算题1. 快速排序算法：- 选择一个元素作为“基准”（pivot）。
数据结构试题集(包含答案-完整版)数据结构试题集（包含答案-完整版）1. 单选题1) 数据结构是一种（）。
a) 存储结构b) 算法c) 数据模型d) 网络答案：c) 数据模型解析：数据结构是一种用于组织和存储数据的方式，描述了数据之间的关系以及对数据的操作。
2) 以下哪种数据结构可以通过索引直接访问元素？a) 链表b) 队列c) 栈d) 数组答案：d) 数组解析：数组是一种线性数据结构，可以通过索引直接访问指定位置的元素。
2. 多选题1) 哪些数据结构属于非线性结构？（）a) 队列b) 树c) 栈d) 图答案：b) 树d) 图解析：线性结构中的元素存在一对一的关系，非线性结构中的元素存在一对多或多对多的关系，树和图属于非线性结构。
2) 下列哪些操作可以在栈上进行？（）a) 入栈b) 出栈c) 查找d) 删除答案：a) 入栈b) 出栈解析：栈是一种后进先出（LIFO）的数据结构，只能在栈顶进行插入和删除操作。
3. 简答题1) 请简要介绍线性表和非线性表。
答案：线性表是数据元素的一个有限序列，元素之间存在一对一的关系。
非线性表是指元素之间存在一对多或多对多的关系，如树和图。
2) 请解释什么是时间复杂度和空间复杂度。
答案：时间复杂度是衡量算法执行效率的度量，表示算法的运行时间随输入规模增长的速度。
空间复杂度是指算法执行过程中所需的存储空间随输入规模增长的速度。
4. 编程题题目：实现一个栈，包含push、pop和getMin三个操作，要求时间复杂度为O(1)。
答案：class MinStack:def __init__(self):self.stack = []self.min_stack = []def push(self, x):self.stack.append(x)if not self.min_stack or x <= self.min_stack[-1]:self.min_stack.append(x)def pop(self):if self.stack.pop() == self.min_stack[-1]:self.min_stack.pop()def getMin(self):return self.min_stack[-1]解析：在栈的基础上，使用一个辅助栈min_stack来记录当前栈中的最小值。
数据结构复习题及答案5篇第一篇：数据结构复习题及答案、数据结构复习题及答案中南大学现代远程教育课程考试（专科）复习题及参考答案数据结构一、判断题：1．数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。
（）2．链式存储在插人和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。
（）3．在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。
（）4．折半搜索只适用于有序表，包括有序的顺序表和有序的链表。
（）5．如果两个串含有相同的字符，则这两个串相等。
（）6．数组可以看成线性结构的一种推广，因此可以对它进行插入、删除等运算。
（）7．在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。
（）8．通常递归的算法简单、易懂、容易编写，而且执行的效率也高。
（）9．一个广义表的表尾总是一个广义表。
（）10．当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。
（）11．对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（h）。
（）12．存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。
（）13．直接选择排序是一种稳定的排序方法。
（）14．闭散列法通常比开散列法时间效率更高。
（）15．有n个结点的不同的二叉树有n!棵。
（）16．直接选择排序是一种不稳定的排序方法。
（）17．在2048个互不相同的关键码中选择最小的5个关键码，用堆排序比用锦标赛排序更快。
（）18．当3阶B_树中有255个关键码时,其最大高度(包括失败结点层)不超过8。
（）19．一棵3阶B_树是平衡的3路搜索树,反之,一棵平衡的3路搜索树是3阶非B_树。
（）20．在用散列表存储关键码集合时，可以用双散列法寻找下一个空桶。
一、单选题（每题 2 分，共20分）1.对一个算法的评价，不包括如下（B ）方面的内容。
A．健壮性和可读性B．并行性C．正确性D．时空复杂度2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。
A. p->next=HL->next; HL->next=p;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=HL;3.对线性表，在下列哪种情况下应当采用链表表示？( )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35.AOV网是一种（）。
A．有向图B．无向图C．无向无环图D．有向无环图6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。
A．低于链接法处理冲突 B. 高于链接法处理冲突C．与链接法处理冲突相同D．高于二分查找7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。
A．值B．函数C．指针D．引用8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。
A．行号B．列号C．元素值D．非零元素个数9.快速排序在最坏情况下的时间复杂度为（）。
A．O(log2n) B．O(nlog2n)C．0(n) D．0(n2)10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。
A. O(n)B. O(1)C. O(log2n)D. O(n2)二、运算题（每题 6 分，共24分）1.数据结构是指数据及其相互之间的______________。
当结点之间存在M对N （M：N）的联系时，称这种结构为_____________________。
数据结构复习题及答案一、选择题1. 在数据结构中，以下哪种数据结构允许在任何位置进行插入和删除操作？A. 栈B. 队列C. 链表D. 数组答案：C2. 以下哪个选项是二叉搜索树的特性？A. 所有左子树的节点值小于根节点值B. 所有右子树的节点值大于根节点值C. 所有左子树的节点值大于根节点值D. 所有右子树的节点值小于根节点值答案：A3. 在图的遍历中，深度优先搜索（DFS）使用的是哪种数据结构？A. 栈B. 队列C. 链表D. 数组答案：A二、填空题1. 在一个有n个节点的完全二叉树中，如果节点按层次从上到下、从左到右编号为1, 2, 3, ..., n，则第i个节点的左孩子节点的编号为____。
答案：2i2. 哈希表解决冲突的一种方法是使用链地址法，其中每个哈希表项是一个____。
答案：链表3. 在图的表示方法中，邻接矩阵适合表示____图，邻接表适合表示____图。
答案：稠密；稀疏三、简答题1. 描述什么是递归，并给出一个简单的递归算法的例子。
答案：递归是一种在算法中调用自身的方法，用于解决可以分解为相似子问题的问题。
一个简单的递归算法例子是计算阶乘：n! = n * (n-1)!，其中基本情况是0! = 1。
2. 解释什么是图的广度优先搜索（BFS）算法，并说明其在哪些情况下适用。
答案：广度优先搜索（BFS）是一种遍历或搜索树或图的算法，它从根节点开始，逐层遍历节点。
BFS适用于寻找最短路径或在层次结构中按层次顺序访问节点的情况。
四、编程题1. 给定一个单链表，请编写一个函数来反转该链表。
答案：（此处省略具体代码实现，只提供解题思路）要反转一个单链表，可以创建一个新的链表头节点，然后遍历原链表，将每个节点的next指针指向前一个节点，直到链表末尾。
最后，将新链表的头节点设置为原链表的最后一个节点的前驱节点。
数据结构试题及答案一、选择题（每题2分，共20分）1. 在数据结构中，线性结构的特点是元素之间存在一对一的线性关系。
以下哪个数据结构不属于线性结构？A. 栈B. 队列C. 树D. 链表答案：C2. 栈（Stack）是一种后进先出（LIFO）的数据结构，以下哪个操作不是栈的基本操作？A. PushB. PopC. TopD. Sort答案：D3. 在二叉树的遍历中，前序遍历的顺序是：A. 根-左-右B. 左-根-右C. 右-根-左D. 根-右-左答案：A4. 哈希表的冲突可以通过多种方法解决，以下哪个不是解决哈希表冲突的方法？A. 链地址法B. 开放地址法C. 再散列法D. 排序法答案：D5. 以下哪个排序算法是稳定的？A. 快速排序B. 堆排序C. 归并排序D. 选择排序答案：C6. 在图的遍历中，深度优先搜索（DFS）使用的是哪种数据结构来实现？A. 队列B. 栈C. 链表D. 哈希表答案：B7. 以下哪个是图的存储方式？A. 顺序存储B. 链式存储C. 散列表D. 矩阵存储答案：D8. 动态数组（如C++中的vector）在插入元素时可能需要进行的操作是：A. 原地扩展B. 复制元素C. 重新分配内存D. 释放内存答案：C9. 以下哪个不是算法的时间复杂度？A. O(1)B. O(log n)C. O(n^2)D. O(n!)答案：D10. 在查找算法中，二分查找法要求被查找的数据必须是：A. 无序的B. 有序的C. 随机分布的D. 唯一元素答案：B二、简答题（每题5分，共30分）1. 简述链表和数组的区别。
答案：链表和数组都是存储数据的线性数据结构，但它们在内存分配、访问方式、插入和删除操作等方面存在差异。
数组在内存中是连续存储的，可以通过索引快速访问任意元素，但插入和删除元素时可能需要移动大量元素。
链表在内存中是非连续存储的，每个元素包含数据和指向下一个元素的指针，不支持通过索引快速访问，但插入和删除操作只需要改变指针，不需要移动其他元素。
数据结构试卷试题及答案一、选择题（每题5分，共40分）1. 数据结构是研究数据元素的（）A. 存储结构B. 处理方法C. 逻辑结构D. 所有以上内容答案：D2. 在数据结构中，通常采用（）方式来表示数据元素之间的逻辑关系。
A. 顺序存储结构B. 链式存储结构C. 索引存储结构D. 散列存储结构答案：B3. 下面哪一个不是栈的基本操作？（）A. 入栈B. 出栈C. 判断栈空D. 获取栈顶元素答案：D4. 下面哪一个不是队列的基本操作？（）A. 入队B. 出队C. 判断队列空D. 获取队头元素答案：D5. 下面哪一个不是线性表的特点？（）A. 有且只有一个根节点B. 每个节点最多有一个前驱和一个后继C. 数据元素类型相同D. 数据元素类型可以不同答案：D6. 在下列哪种情况中，使用链式存储结构比顺序存储结构更合适？（）A. 数据元素经常插入和删除B. 数据元素大小不固定C. 数据元素个数不确定D. 所有以上情况答案：D7. 下面哪一个不是树的遍历方式？（）A. 前序遍历B. 中序遍历C. 后序遍历D. 翻转遍历答案：D8. 在下列哪种情况中，使用散列存储结构比其他存储结构更合适？（）A. 数据元素个数较少B. 数据元素查找频繁C. 数据元素插入和删除频繁D. 数据元素大小不固定答案：B二、填空题（每题5分，共30分）9. 栈是一种特殊的线性表，它的插入和删除操作都限定在表的一端进行，这一端称为______。
答案：栈顶10. 队列是一种特殊的线性表，它的插入操作在表的一端进行，这一端称为______，而删除操作在另一端进行，这一端称为______。
答案：队尾、队头11. 二叉树中的节点包括______和______。
答案：根节点、子节点12. 在图的存储结构中，邻接矩阵表示法用______个一维数组来表示图中各个顶点之间的关系。
答案：两个13. 散列存储结构中，关键码到存储地址的映射方法称为______。
《数据结构》期末考试试题及答案一、选择题（每题2分，共20分）1. 下列哪种数据结构是线性结构？A. 栈B. 树C. 队列D. 图答案：A2. 在计算机科学中，什么是最基本的数据结构？A. 数组B. 链表C. 栈D. 树答案：C3. 下列哪种操作的时间复杂度是O(1)?A. 在链表中插入元素B. 在数组中查找元素C. 在树中删除节点D. 在图中寻找最短路径答案：B4. 下列哪种数据结构常常用于实现栈和队列？A. 数组B. 链表C. 树D. 图答案：A5. 下列哪种数据结构是有序的？A. 栈B. 队列C. 链表D. 图答案：C二、填空题（每题2分，共20分）1. 在数据结构中，栈是一种后进先出（____）的数据结构。
答案：线性表2. 队列是一种先进先出（____）的数据结构。
答案：线性表3. 链表是一种____数据结构，由一系列节点组成。
答案：非线性4. 二叉树是一种特殊的树，它的每个节点最多有两个____。
答案：子节点5. 哈希表是通过____函数将关键字映射到表中的位置来访问数据。
答案：哈希三、判断题（每题2分，共20分）1. 树是一种线性结构。
（）答案：错误2. 链表的插入和删除操作时间复杂度都是O(1)。
（）答案：错误3. 图是一种线性结构。
（）答案：错误4. 哈希表是一种基于顺序结构的的数据结构。
（）答案：错误5. 在数据结构中，时间复杂度O(n)表示算法随着输入规模的增加而线性增长。
（）答案：正确四、简答题（每题10分，共30分）1. 请简述栈和队列的特点和应用场景。
答案：栈是一种后进先出（LIFO）的数据结构，应用场景包括函数调用栈、表达式求值等。
队列是一种先进先出（FIFO）的数据结构，应用场景包括任务队列、缓冲区等。
2. 请简述链表的优缺点。
答案：链表的优点包括动态扩容、插入和删除操作时间复杂度为O(1)、可以方便地实现各种复杂数据结构。
缺点包括占用内存空间较大、不如数组支持随机访问。
数据结构考试题及答案一、选择题1. 以下哪种数据结构在实现栈时最为高效？A. 链表B. 数组C. 树D. 图答案：B2. 快速排序算法的时间复杂度在最坏情况下是多少？A. O(n)B. O(nlogn)C. O(n^2)D. O(n^3)答案：C3. 在二叉搜索树中，若要查找给定值的节点，应该按照以下哪种方式进行？A. 从根节点开始，向左或向右子树交替进行B. 从根节点开始，始终向左子树进行C. 从根节点开始，始终向右子树进行D. 从最底层节点开始向上进行答案：A4. 哈希表的主要优点是什么？A. 有序存储数据B. 高效的查找、插入和删除操作C. 动态扩容D. 消耗内存小答案：B5. 下面哪种数据结构通常用于实现高效的多对一映射？A. 数组B. 链表C. 哈希表D. 树答案：C二、填空题1. 在平衡树中，AVL树通过_________来保持树的平衡。
答案：旋转2. 堆数据结构通常用来实现_________等优先队列。
答案：最大/最小3. 拓扑排序是针对有向无环图(DAG)的一种排序算法，它能够反映出任务间的_________关系。
答案：依赖4. 广度优先搜索(BFS)算法使用_________数据结构来实现。
答案：队列5. 斐波那契数列可以通过递归算法、动态规划以及_________等方法来计算。
答案：矩阵快速幂三、简答题1. 请简述链表和数组的区别及各自的优缺点。
答案：链表由一系列节点组成，每个节点包含数据和指向下一个节点的指针。
它的优点是能够在常数时间内在任意位置插入或删除元素，但随机访问效率较低。
数组是一段连续的内存空间，可以存储一系列相同类型的元素。
它的优点是支持高效的随机访问，但插入和删除操作通常需要移动大量元素，且大小固定或调整大小成本较高。
2. 描述二分查找的工作原理及其适用条件。
答案：二分查找是一种在有序数组中查找特定元素的算法。
它的工作原理是将数组分为两半，比较中间元素与目标值，如果相等则查找结束；如果目标值较小，则在左半部分继续查找；如果目标值较大，则在右半部分继续查找。
第一章概论自测题答案一、填空题1. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。
2. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。
3. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。
4. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。
5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。
6．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。
7. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。
8. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。
9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。
10. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。
11. 一个算法的效率可分为时间效率和空间效率。
二、单项选择题（B）1. 非线性结构是数据元素之间存在一种：A）一对多关系 B）多对多关系C）多对一关系 D）一对一关系（ C ）2. 数据结构中，与所使用的计算机无关的是数据的结构；A) 存储 B) 物理C) 逻辑 D) 物理和存储（C）3. 算法分析的目的是：A) 找出数据结构的合理性B) 研究算法中的输入和输出的关系C) 分析算法的效率以求改进D) 分析算法的易懂性和文档性（A）4. 算法分析的两个主要方面是：A) 空间复杂性和时间复杂性B) 正确性和简明性C) 可读性和文档性D) 数据复杂性和程序复杂性（C ）5. 计算机算法指的是：A) 计算方法B) 排序方法C) 解决问题的有限运算序列D) 调度方法（B）6. 计算机算法必须具备输入、输出和等5个特性。
数据结构复习题目一．是非题(线性结构)4线性表的链式存储结构具有可直接存取表中任一元素的优点。
5 线性表的顺序存储结构优于链式存储结构。
6. 在单链表P指针所指结点之后插入S结点的操作是：P->next= S ; S-> next = P->next;。
7 对于插入、删除而言，线性表的链式存储优于顺序存储。
8. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
10 线性表的顺序存储结构具有可直接存取表中任一元素的优点。
11. 栈和队列是操作上受限制的线性表。
12. 队列是与线性表完全不同的一种数据结构。
13. 队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进行。
15. 栈是限定仅在表头进行插入和表尾进行删除运算的线性表。
16队列是一种运算受限的线性表(树形结构)1. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。
2.二叉树是一棵结点的度最大为二的树。
3. 赫夫曼树中结点个数一定是奇数。
5. 假设B是一棵树，B′是对应的二叉树。
则B的后根遍历相当于B′的后序遍历。
6. 通常，二叉树的第i层上有2i-1个结点。
7. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。
8二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。
(图形结构)1 邻接多重表可以用以表示无向图，也可用以表示有向图。
2 可从任意有向图中得到关于所有顶点的拓扑次序。
6. 一个无向图的连通分量是其极大的连通子图。
7. 连通图的生成树是一个包含图G所有n个顶点和任意n-1条边的子图。
9. 邻接表可以表示有向图，也可以表示无向图。
（）（查找)1. 二叉排序树的平均查找长度为O(logｎ)。
2. 二叉排序树的最大查找长度与（LOG2N）同阶。
3 选用好的HASH函数可避免冲突。
4折半查找不适用于有序链表的查找。
5一般来说，折半查找不适用于有序链表的查找。
6二叉排序树的查找和折半查找的时间性能相同。
（排序)1. 对于目前所知的排序方法，快速排序具有最好的平均性能。
2 对于任何待排序序列来说，快速排序均快于冒泡排序。
3 在最坏情况下，堆排序的时间性能是O(nlogn),比快速排序好选择题。
（1-19是线性、树形、图形结构，20-29是查找和排序）1、从逻辑上可以把数据结构分成( )。
A. 动态结构和静态结构B. 顺序组织和链接组织C. 线性结构和非线性结构D. 基本类型和组合类型2、线性表L在( )情况下适于使用链表结构实现。
A. 不需修改L的结构B. 需不断对L进行删除、插入C. 需经常修改L中结点值D. L中含有大量结点3、若入栈顺序为A、B、C、D、E，则下列( )出栈序列是不可能的。
A．A、B、C、D、E B．B、C、D、A、EC．C、D、B、E、A D．D、E、C、A、B4、递归程序可借助于( )转化为非递归程序。
a.线性表b.队列 c: 栈 d.数组5、在下列数据结构中( )具有先进先出（FIFO）特性，( )具有先进后出(FILO）特性。
a．线性表 b．栈 c．队列 d．广义表6、若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到 ( ) 的序列。
a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,17、假设用于通讯的电文仅由6个字符组成，字母在电文中出现的频率分别为7, 19, 22, 6,32, 14。
若为这6个字母设计哈夫曼编码（设生成新的二叉树的规则是按给出的次序从左至右的结合，新生成的二叉树总是插入在最右），则频率为7的字符编码是（），频率为32的字符编码是（）。
a: 00 b: 01 c: 10 d: 11e: 011 f: 110 g: 1110 h:11118、对二叉排序树（）可得到有序序列。
a:按层遍历 b:前序遍历 c:中序遍历 d:后序遍历9、设一棵二叉树BT的存储结构如下:1 2 3 4 5 6 7 8lchild 2 3 0 0 6 0 0 0data A B C D E F G Hrchild 0 5 4 0 8 7 0 0其中lchild，rchild分别为结点的左、右孩子指针域，data为结点的数据域。
则该二叉树的高度为( )；第3层有( )个结点（根结点为第1层）。
A．2 B. 3 C. 4 D. 510、在有n个结点的二叉树的二叉链表表示中，空指针数（）。
a.不定b.n+1c.nd.n-111、若某二叉树有20个叶子结点，有20个结点仅有一个孩子，则该二叉树的总结点数是( )。
A．40 B. 55 C. 59 D. 6112、已知某二叉树的先序遍历次序为abcdefg中序遍历次序为badcgfe，则该二叉树的后序遍历次序为（）。
层次遍历次序为（）。
a: abcdefg b: cdebgfa c: bdgfeca d: edcgfba13、.图示的三棵二叉树中( )为最优二叉树。
A) B) C)c a2 7a b c d d b7 5 2 4 4 5a b c d7 5 2 414、对一棵完全二叉树进行层序编号。
则编号为n的结点若存在右孩子,其位序是( )。
编号为n的结点若存在双亲,其位置是( )。
a: n/2 b: 2n c:2n-1 d:2n+1 e:n f: 2(n+1)15、设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为m1、m2和m3，则与森林F对应的二叉树根结点的右子树上的结点个数是( )。
A. m1B. m1+m2C. m3D. m2+m316、下列二叉树中，( )可用于实现符号不等长高效编码。
a:最优二叉树 b:次优查找树 c:二叉平衡树 •••d:二叉排序树17、设无向图G = (V,E)和G’= (V’,E’)，若G’是G的生成树，则下面不正确的说法是( )。
A. G’是G的子图B. G’是G的连通分量C. G’是G的无环子图D. G’是G的极小连通子图且V’= V18、任何一个连通图的最小生成树( )。
A．只有一棵 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在19、已知某无向图的邻接表如下所示；( 19 )是其原图。
( 20 )是按该邻接表遍历所得深度优先生成树。
( 21 )是按该邻接表遍历所得广度优先生成树。
0 a 3 2 11 b 3 02 c 43 03 d 5 2 1 04 e5 25 f 4 3A. a bB. a bC. a bc d c d c de f e f e fD. a bE. a bF. a bc d c d c de f e f e f20、下列查找方法中（）适用于查找单链表。
A）顺序查找 B）折半查找 C）分块查找 D）hash查找21、哈希表的查找效率取决于（）。
a: 哈希函数 b:处理冲突的方法。
c:哈希表的装填因子。
d:以上都是22、在Hash函数H(k)=k MOD m中，一般来说，m应取( )。
A. 奇数B. 偶数C. 素数D. 充分大的数23、在顺序表查找中，为避免查找过程中每一步都检测整个表是否查找完毕，可采用方法。
A.设置监视哨B.链表存贮C.二分查找D.快速查找24、静态查找表和动态查找表的区别在于( )。
A. 前者是顺序存储，而后者是链式存储B. 前者只能进行查找操作，而后者可进行查找、插入和删除操作C. 前者只能顺序查找，而后者只能折半查找D. 前者可被排序，而后者不能被排序25、根据插入次序（80，90，100，110，85，70，75，60，72）建立二叉排序树。
图（）是最终变化的结果。
80 8070 90 75 9060 75 85 100 60 70 85 10072 110 72 110a: b:90 9075 100 80 10070 80 110 75 70 85 11060 72 85 60 72c: d:26、若有序表中关键字序列为：14，20，25，32，34，45，57，69，77，83，92。
对其进行折半查找，则在等概率情况下，查找成功时的平均查找长度是( )。
查找32时需进行( )次比较。
A. 1B. 2C. 3D. 427、已知哈希表地址空间为A[0..8]，哈希函数为H(k)=k mod 7，采用线性探测再散列处理冲突。
若依次将数据序列：76,45,88,21,94,77,17存入该散列表中，则元素17存储的下标为( )；在等概率情况下查找成功的平均查找长度为( )。
A. 0B. 1C. 2D. 3E. 4F. 5G. 6H. 728、若从二叉树的根结点到其它任一结点的路径上所经过的结点序列按其关键字递增有序，则该二叉树是( )。
A. 二叉排序树B. 赫夫曼树C. 堆D. 平衡二叉树29、已知一组待排序的记录关键字初始排列如下：56,26,86,35,75,19,77,58,48,42下列选择中（）是快速排序一趟排序的结果。
（）是归并排序一趟排序的结果。
（）是初始堆（大堆顶）。
A）86,75,77,58,42,19,56,35,48,26.B）26,56,35,75,19,77,58,48,42,86.C）35,26,19,42,58,48,56,75,86,77.D）42,26,48,35,19,56,77,58,75,86.三．填空题（1-13是线性、树形、图形结构，14-15是查找和排序）1、数据结构通常有下列4类基本结构：集合、、树型结构、图型结构。
2、线性表的顺序存储结构是以来表示数据元素之间的逻辑关系的。
3、递归过程可借助于数据结构( )改写成非递归过程。
4、设循环队列存于一维数组Ｑ[ｍ]中，尾指针rear指示队尾元素在队列中的当前位置，•头指针front指示队列中队头元素的前一个位置，则队列长度＝( )。
5、在二叉树的第i层上至少有_________个结点, 至多有_________个结点,深度为k的二叉树至多有_____________个结点.6、对树的遍历有先序遍历树和后序遍历树。
若以二叉链表作树的存储结构,则树的先序遍历可借用二叉树的遍历算法来实现,而树的后序遍历可借用二叉树的遍历算法来实现。
7、设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为m1、m2和m3，则与森林F对应的二叉树根结点的左子树上的结点个数是（），右子树上的结点个数是（）。
8、若某二叉树有n0个叶子结点，有n1个结点仅有一个孩子，则该二叉树的总结点数是（）。
9、如果对完全二叉树中结点从1开始按层进行编号，设最大编号为n；那么，可以断定编号为i (i>1)的结点的父结点编号为( )；所有编号（）的结点为叶子结点。
10、若某二叉树中，有20个结点没有孩子，有20个结点仅有一个孩子，则该二叉树的总结点数是。
