下载文档原格式
数据结构考试题及答案一、选择题（每题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来记录当前栈中的最小值。
数据结构考试试题一、选择题（每题2分，共20分）1. 在数据结构中，队列是一种______。
A. 线性结构B. 非线性结构C. 树形结构D. 图结构2. 对于长度为n的线性表，在顺序存储结构中，从第i个元素（1≤i≤n）开始，连续做m（1≤m≤n-i+1）个元素的删除操作，需要进行的移动元素次数为______。
A. mB. n-mC. i+m-1D. m+n-m-13. 在二叉树的遍历中，先序遍历的顺序是______。
A. 根左右B. 左右根C. 左根右D. 左右根4. 哈希表的冲突可以通过多种方式解决，其中不是解决冲突的方法是______。
A. 开放寻址法B. 链地址法C. 建立一个公共溢出区D. 二分查找法5. 排序算法中，时间复杂度为O(nlogn)的算法是______。
A. 选择排序B. 冒泡排序C. 快速排序D. 插入排序6. 在图的遍历中，深度优先搜索（DFS）使用的是______。
A. 栈B. 队列C. 哈希表D. 数组7. 堆排序算法中，将堆中的最后一个元素和第一个元素交换，然后重新调整堆的过程称为______。
A. 堆调整B. 堆缩小C. 堆替换D. 堆重建8. 一个长度为n的链表，删除已知第k个元素的时间复杂度是______。
A. O(1)B. O(n)C. O(k)D. O(nk)9. 字符串“Knuth”在一棵二叉查找树中，按照K->n->u->t->h的顺序插入后，使用中序遍历得到的结果是______。
A. hKnuctB. hnKutC. hKnutD. hnuct10. 对于长度为n的数组，如果使用归并排序算法进行排序，其时间复杂度为______。
A. O(n)B. O(n^2)C. O(nlogn)D. O(logn)二、简答题（每题5分，共30分）11. 请简述什么是时间复杂度，并给出最好、最坏和平均时间复杂度的定义。
12. 解释一下什么是平衡二叉树，并说明它在数据结构中的重要性。
数据结构考试题及答案一、选择题1. 下列哪个不属于线性数据结构？A. 栈B. 队列C. 数组D. 链表答案：C2. 在单链表中，删除一个节点的时间复杂度是多少？A. O(1)B. O(n)C. O(logn)D. O(nlogn)答案：A3. 以下哪种数据结构的插入和删除操作都具有O(logn)的时间复杂度？A. 树B. 堆C. 栈D. 队列答案：B二、填空题1. 栈是一种__________（后进先出）的数据结构。
答案：后进先出2. 在链表中，头节点的前驱指针指向__________。
答案：空指针或者NULL3. 哈希表中冲突解决的方法有__________和开放地址法。
答案：链地址法三、简答题1. 请简述树与图的区别。
答案：树是一种特殊的图，它们的主要区别在于图中任意两个节点之间都可能存在边，而树中任意两个节点之间只有一条路径。
此外，树是无环图，而图可以有环。
2. 请解释栈的应用场景，并举例说明。
答案：栈常用于函数调用和表达式求值等场景。
例如，在编程中，当一个函数被调用时，相关的信息会被压入栈中，执行完毕后再弹出。
另外，栈还可以用于实现撤销操作，在文本编辑器中，当我们进行一系列操作后，可以将每一步的操作记录在栈中，需要撤销时，只需要依次弹出栈顶元素即可。
四、编程题请使用C语言实现一个栈的数据结构，并实现栈的基本操作（入栈、出栈、判空、获取栈顶元素等）。
答案略。
结语本文包含了数据结构考试题及答案，从选择题到填空题再到简答题和编程题，涵盖了数据结构的各个方面。
希望能对你的学习和复习有所帮助。
数据结构是计算机科学的基础，掌握好数据结构对于编程能力的提升至关重要。
加油！。
数据结构试题一、单选题1、在数据结构的讨论中把数据结构从逻辑上分为（C ）A 内部结构与外部结构B 静态结构与动态结构C 线性结构与非线性结构D 紧凑结构与非紧凑结构。
2、采用线性链表表示一个向量时，要求占用的存储空间地址（D ）A 必须是连续的B 部分地址必须是连续的C 一定是不连续的D 可连续可不连续3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ D ）。
A nB n/2C (n-1)/2D (n+1)/2？4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。
A s→link = p→link;p→link = s;B p→link = s; s→link = q;C p→link = s→link;s→link = p;D q→link = s;s→link = p;5、如果想在4092个数据中只需要选择其中最小的5个，采用（ C ）方法最好。
A 起泡排序B 堆排序C 锦标赛排序D 快速排序6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（ B ）。
A 求子串B 模式匹配C 串替换D 串连接7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。
所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（ C ）。
）A 80B 100C 240D 2708、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。
A 栈B 队列C 循环队列D 优先队列9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。
10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。
A ( front - rear + 1) % mB ( rear - front + 1) % mC ( front - rear + m) % mD ( rear - front + m) % m11、一个数组元素a[i]与（ A ）的表示等价。
数据结构考试题及答案一、选择题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. 在数据结构中，栈（Stack）是一种特殊的线性表，其特点是：A. 允许在表的任意位置插入和删除元素B. 只能在表的一端进行插入和删除操作C. 只能在表的两端进行插入和删除操作D. 只能在表的中间进行插入和删除操作答案：B2. 假设有一个单链表，头结点的指针域为head，链表中每个结点包含一个数据域data和指向下一个结点的指针域next。
若要删除指针p所指向的结点，以下哪个操作是正确的？A. p = p->nextB. p->next = p->next->nextC. p = p->next->nextD. p = NULL答案：B3. 在二叉树的遍历算法中，先序遍历的顺序是：A. 先访问根节点，然后遍历左子树，最后遍历右子树B. 先遍历左子树，然后访问根节点，最后遍历右子树C. 先遍历右子树，然后访问根节点，最后遍历左子树D. 同时遍历左子树和右子树答案：A4. 哈希表的冲突可以通过多种方式解决，以下哪种不是解决哈希表冲突的方法？A. 链地址法B. 开放地址法C. 再哈希法D. 排序法答案：D5. 快速排序算法的时间复杂度在最好、最坏和平均情况下分别是：A. O(n log n), O(n^2), O(n)B. O(n), O(n log n), O(n^2)C. O(n log n), O(n), O(n log n)D. O(n^2), O(n log n), O(n)答案：A二、简答题1. 请简述什么是图，并说明图的两种基本表示方法。
答案：图是一种数据结构，由顶点（或称为节点）和边组成。
图可以表示为有向图或无向图。
图的两种基本表示方法为邻接矩阵和邻接表。
邻接矩阵是一个二维数组，其元素表示顶点之间的连接关系；邻接表则使用链表存储每个顶点的邻接点。
2. 什么是二叉搜索树（BST）？请简述其特点。
答案：二叉搜索树是一种特殊的二叉树，其中每个节点的值都大于或等于其左子树中所有节点的值，并且小于或等于其右子树中所有节点的值。
数据结构试题（含答案）1．数据逻辑结构包括线性结构、树形结构和图状结构三种类型，树形结构和图状结构合称非线性结构2．数据的逻辑结构分为集合、线性结构、树形结构和图状结构4种。
3．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。
4．线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。
5．在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没．6．数据结构的基本存储方法是顺序、链式、索引和散列存储。
有后续结点，其余每个结点的后续结点可以任意多个。
7．衡量一个算法的优劣主要考虑正确性、可读性、健壮性和时间复杂度与空间复杂度。
8．评估一个算法的优劣，通常从时间复杂度和空间复杂度两个方面考察。
9．算法的5个重要特性是有穷性、确定性、可行性、输入和输出。
10．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。
11．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。
12．在双链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后继结点。
13．在顺序表中插入或删除一个数据元素，需要平均移动n 个数据元素，移动数据元素的个数与位置有关14．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表的元素是，应采用顺序存储结构15．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成单链表和双链表。
16．顺序存储结构是通过下标表示元素之间的关系的；链式存储结构是通过指针表示元素之间的关系的17．带头结点的循环链表L中只有一个元素结点的条件是L->next->next=L18．栈是限定仅在表尾进行插入或删除操作的线性表，其运算遵循后进先出的原则。
19．空串是零个字符的串，其长度等于零。
数据结构试题（含答案）一．是非题（勾选“√“用于更正和勾选”√1.数据结构可用三元公式（D，s，P）表示，其中：D为数据对象，s为D上的关系，p是对d的基本操作集。
×2.线性表的链式存储结构具有直接访问表中任何元素的优点。
×3. 字符串是特定于数据对象的线性表。
4.二叉树是一棵结点的度最大为二的树。
×5.邻接多表可用于表示无向图或有向图。
×6. 所有顶点的拓扑序都可以从任何有向图中得到。
× 7. 无向连通图的生成树是其最大连通子图。
× 8. 二叉排序树的搜索长度最多为log2n。
×9．对于一棵m阶的b-树.树中每个结点至多有m个关键字。
除根之外的所有非终端结点至几乎没有┌ M/2┌ 关键词。
×10．对于目前所知的排序方法，快速排序具有最好的平均性能。
11.顺序存储模式具有存储密度高、插入和删除操作效率高的优点。
× 12. 二维数组是一个线性表，其数据元素是线性表。
13.连通图g的生成树是一个包含g的所有n个顶点和n-1条边的子图。
×14.折半查找不适用于有序链表的查找。
15.完全二叉树必定是平衡二叉树。
16.中间顺序线索二叉树的优点是，在中间顺序下很容易找到直接前导节点和直接后继节点。
17.队列是一种完全不同于线性表的数据结构。
× 18. 平均搜索长度与记录的搜索概率有关。
19.二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。
×20.算法的时间复杂度越高，可读性越差；相反，算法的可读性越好，时间复杂度越差。
×二．选择题1.如果编号为1、2和3的列车车厢依次通过开关堆调度，则无法获得（E）的顺序。
a:1,2,3b:1,3,2c:2,1,3d:2,3,1e:3,1,2f:3,2,12.递归程序可借助于(b)转化为非递归程序。
a:线性表B:堆栈C:队列D:数组3.在下列数据结构中(c)具有先进先出（fifo）特性，（b）它具有先进先出的特点。
一、选择题（共15题，每题2分，共计30分）1、单链表的一个存储结点包含（ C ）A.指针域和链域B.指针域或链域C.数据域或指针域D.数据域和链域2、采用线性链表表示一个向量时，要求占用的存储空间地址（ D ）。
A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、可连续可不连续3、当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（ B ）。
A. n-2B. n-1C. nD. n+14、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。
A、s→next = p→next; p→next = s;B、p→next = s; s→next k = q;C、p→next = s→next; s→next = p;D、q→next = s; s→next = p;5、在数组A中，每一个数组元素A[i, j] 占用3个存储字，行下标i从1到8，列下标j 从1到10。
所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（ C ）。
A、 80B、 100C、 240D、 2706、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。
A、栈B、队列C、循环队列D、优先队列7、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。
A、4, 3, 2, 1B、2, 4, 3, 1C、1, 2, 3, 4D、3, 2, 1, 48.下述各类表中可以随机访问的是（D ）。
A. 单向链表B. 双向链表C.单向循环链表D.顺序表9.在一个长度为n的顺序表中为了删除第5个元素，从前到后依次移动了15个元素。
则原顺序表的长度为（ B ）。
A. 21B. 20C. 19D. 2510.元素1，3，5按顺序依次进栈，则该栈的不可能的输出序列是（ B ）。
A. 5 3 1B. 5 1 3C. 3 1 5D. 1 5 311.一个队列的入队序列是5，6，7，8，则队列的输出序列是（ A ）。
A. 5 6 7 8B. 8 7 6 5C. 7 8 6 5D.可能有多种情况12．在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（C ）。
A．p=q->next B．p->next=q C．p->next=q->next D．q->next=NULL13.设一棵哈夫曼树共有n个非叶结点，则该树一共有（ B ）个结点。
A. 2*n-1B. 2*n +1C. 2*nD. 2*(n-1)14.对如图1所示二叉树进行中序遍历，结果是（ A ）。
A. dfebagcB. defbagcC. defbacgD.dbaefcg15 . 一组记录的关键字序列为（37，70，47，29，31，85），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（ D ）。
A ．31，29，37，85，47，70B ．29，31，37，47，70，85C ．31，29，37，70，47，85D ．31，29，37，47，70，85 一、选择题（共15题，每题2分，共计30分）1. 一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。
A 、4, 3, 2, 1B 、2, 4, 3, 1C 、1, 2, 3, 4D 、3, 2, 1, 4 2.下述各类表中可以随机访问的是（ D ）。
A. 单向链表B. 双向链表C.单向循环链表D.顺序表3.在一个长度为n 的顺序表中为了删除第5个元素，从前到后依次移动了15个元素。
则原顺序表的长度为（B ）。
A. 21B. 20C. 19D. 254.元素2，4，6按顺序依次进栈，则该栈的不可能的输出序列是（ B ）。
A. 6 4 2B. 6 2 4C. 4 2 6D. 2 6 4 5.一个队列的入队序列是5，6，7，8，则队列的输出序列是（A ）。
A. 5 6 7 8B. 8 7 6 5C. 7 8 6 5D.可能有多种情况 6、在数组A 中，每一个数组元素A[i, j] 占用3个存储字，行下标i 从1到8，列下标j 从1到10。
所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（ C ）。
A 、 80B 、 100C 、 240D 、 2707、在一个单链表中，p 、q 分别指向表中两个相邻的结点，且q 所指结点是p 所指结点的直接后继，现要删除q 所指结点，可用语句（ C ）。
A ．p=q->next B ．p->next=q C ．p->next=q->next D ．q->next=NULL 8、数据结构中，与所使用的计算机无关的是数据的（A ）结构。
A. 逻辑B. 物理C. 存储D. 逻辑与物理 9.设一棵哈夫曼树共有n 个非叶结点，则该树一共有（ B ）个结点。
A. 2*n-1B. 2*n +1C. 2*nD. 2*(n-1) 10．与中缀表达式a+b*c-d 等价的前缀表达式是_c__。
A.+a-*bcdB.*+-abcdC.-+a*bcdD.abcd+*-11．带头结点的单向链表为空的判断条件是（D ）（设头指针为head ）。
图1 c b c d e f g aA ．head = =NULLB ．head!=NULLC ．head->next= =headD ．head->next= =NULL 12．链表所具备的特点是（ C ）。
A ．可以随机访问任一结点B ．占用连续的存储空间C ．插入删除元素的操作不需要移动元素结点D ．可以通过下标对链表进行直接访问 13．设有一个长度为n 的顺序表，要在第i 个元素之前插入一个元素（也就是插入元素作为新表的第i 个元素），则移动元素个数为（ A ）。
A ．n-i+1 B ．n-i C ．n-i-1 D ．i 14．下列算法suanfa2的时间复杂度为__c__。
int suanfa2(int n) { int t=1； while(t<=n) t=t*2； return t ； }A ．O(n)B ．O(n 2) C ．O(log2n) D ．O(1) 15.广义表(a,(b),c,(d,(e)))的表尾是_D___。
A.(d,(e))B.(d,(e))）C.(b),c,(d,(e))D.((b),c,(d,(e)))二、填空题（每空1分，共13分）1. 树中结点A 的 ________分支数____________ 称为结点A 的度。
2. 一棵深度为4的二叉树最多有 ___15____ 个结点。
3. 具有10个顶点的无向图,边的总数最多为 _____45________ 。
4．结构中的数据元素存在 一对多 的关系称为树形结构。
6．如图1所示的二叉树，其先序遍历序列为___abdefcg______。
7．如图1所示的二叉树，其后序遍历序列为___fedbagc______。
8．如图2所示的二叉树，其前序遍历序列为___abdefcg______。
g fab d ec9．n 个元素进行冒泡法排序，通常需要进行___n-1_____趟冒泡，第j 趟冒泡要进行_n-j_____次元素间的比较。
10．哈希函数是记录 数据元素 与该记录存储地址之间所构造的对应关系。
二、填空题（每空1分，共15分）1．1.把数据存储到计算机中,并具体体现数据之间的逻辑结构称为__存储结构____ __。
2.在一棵树中____根__结点没有前驱结点，_叶子__结点没有后继结点。
3. n 个元素进行冒泡法排序，通常需要进行__n-1______趟冒泡，第j 趟冒泡要进行__n-j____次元素间的比较。
4．一棵深度为6的满二叉树有__31____个非终端结点。
5．结构中的数据元素存在 一对多 的关系称为树形结构。
2． 6．在一个单向链表中p 所指结点之后插入一个s 所指向的结点时，应执行s->next=p->next;和 p->next=s 的操作。
7．队列的插入操作在 队尾 进行，删除操作在 队头 进行。
8．在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是_左孩子指针_ 、 数据、 右孩子指针 。
3． 9．中序遍历二叉排序树可得到一个 递增有序序列 。
4． 10．如图所示的二叉树，其中序遍历序列为___dgbaechif_____ _。
三、阅读理解题 （第1题4分，第2，3题各3分，共计10分）1．给出下列递归过程的执行结果。
(1) void unknown ( int w ) {if ( w ) {unknown ( w-1 );for ( int i = 1; i <= w; i++ ) printf (“%d ”, w);printf (“\n ”); } }调用语句为 unknown (4). 执行结果为： 1 2 23 3 34 4 4 4ef gi b a c h d(2) void unknown ( int m ) {printf (“%d ”, n % 10) ;if ( int ( n / 10 ) ) unknown ( int ( n / 10 ) ); }调用语句为unknown ( 582 )。
执行结果为：2852．以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。
void Inorder (struct BTreeNode *BT){ if(BT!=NULL){① Inorder(BT->left);② printf(“%c”,BT->data);③ Inorder(BT->right);}}3. 以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中，左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。
void Postorder (struct BTreeNode *BT){ if(BT!=NULL){① postorder(BT->left);② postorder(BT->right);③ printf(“%c”,BT->data);}3．设有序顺序表为 { 10, 20, 30, 40, 50, 60, 70 }，采用折半搜索时，搜索成功的平均搜索长度是多少？17/7四、简答题（每题4分，共16分）(1) 在一个有n个元素的顺序表的第i个元素（1 ≤ i ≤ n）之前插入一个新元素时，需要向后移动多少个元素？n- i + 1(2) 当一个栈的进栈序列为1234567时，可能的出栈序列有多少种？6457321是否是合理的出栈序列？不合理(3) 数据结构的逻辑结构和存储结构由哪些具体结构组成？逻辑结构：线性结构，树型结构，图形结构，集合存储结构：顺序存储，链式存储，散列存储，索引存储(4) 试述线性结构中顺序存储和链式存储的优缺点？顺序存储：存储实现简单，读取数据方便，插入删除数据复杂度高，存储空间冗余大链式存储：存储实现稍复杂，读取数据必须从头开始，插入删除数据复杂度低，存储空间冗余小。
