下载文档原格式
数据结构考试题及答案一、选择题（每题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）串变量 ：串变量和其它类型的变量⼀样，其取值是可以改变的。
（2）串常量 ：串常量和整常数、实常数⼀样，在程序中只能被引⽤但不能改变其值。
即只能读不能写。
（1）树形图表⽰： 树形图表⽰是树结构的主要表⽰⽅法。
（2）树的其他表⽰法① 嵌套集合表⽰法：是⽤集合的包含关系来描述树结构。
② 凹⼊表表⽰法：类似于书的⽬录③ ⼴义表表⽰法：⽤⼴义表的形式表⽰的。
上图 (a)树的⼴义表表⽰法如下：（A（B（E，F（I，J））， C，D（G，H）））1．中序遍历的递归算法定义：若⼆叉树⾮空，则依次执⾏如下操作：(1)遍历左⼦树； (2)访问根结点； (3)遍历右⼦树。
2．先序遍历的递归算法定义：若⼆叉树⾮空，则依次执⾏如下操作：(1) 访问根结点； (2) 遍历左⼦树； (3) 遍历右⼦树。
3．后序遍历得递归算法定义：若⼆叉树⾮空，则依次执⾏如下操作：(1)遍历左⼦树； (2)遍历右⼦树； (3)访问根结点。
2、链表具有的特点是B 插⼊、删除不需要移动元素C 不必事先估计存储空间D 所需空间与线性表长度成正⽐顺序队列（1）队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。
（2） 顺序队列的表⽰①和顺序表⼀样顺序队列⽤⼀个向量空间存放当前队列中的元素。
数据结构试题及答案一、选择题（每题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. 简述链表和数组的区别。
答案：链表和数组都是存储数据的线性数据结构，但它们在内存分配、访问方式、插入和删除操作等方面存在差异。
数组在内存中是连续存储的，可以通过索引快速访问任意元素，但插入和删除元素时可能需要移动大量元素。
链表在内存中是非连续存储的，每个元素包含数据和指向下一个元素的指针，不支持通过索引快速访问，但插入和删除操作只需要改变指针，不需要移动其他元素。
数据结构题库及答案详解一、选择题1. 在数据结构中，线性结构的特点是什么？A. 结构中存在唯一的开始结点和终端结点B. 结构中所有结点的前驱和后继都存在C. 结构中所有结点都只有一个直接前驱和一个直接后继D. 结构中存在多个开始结点和终端结点答案：C2. 栈是一种特殊的线性表，其特点是：A. 先进先出B. 先进后出C. 可以同时在两端进行插入和删除操作D. 只能在一端进行插入和删除操作答案：D3. 在二叉树的遍历算法中，先序遍历的顺序是：A. 先访问根结点，然后遍历左子树，最后遍历右子树B. 先遍历左子树，然后访问根结点，最后遍历右子树C. 先遍历右子树，然后访问根结点，最后遍历左子树D. 先遍历左右子树，最后访问根结点答案：A二、填空题4. 在图的遍历中，______算法可以避免重复访问同一顶点。
5. 哈希表的冲突可以通过______方法来解决。
答案：4. 深度优先搜索（DFS）5. 链地址法或开放地址法三、简答题6. 简述排序算法中的快速排序算法的基本原理。
答案：快速排序算法是一种分治算法，它通过选择一个元素作为“基准”，然后将数组分为两个子数组，一个包含小于基准的元素，另一个包含大于基准的元素。
然后对这两个子数组递归地应用快速排序算法。
7. 解释什么是递归，并给出一个递归函数的例子。
答案：递归是一种在函数中调用自身的编程技术。
递归函数必须有一个明确的终止条件，以避免无限递归。
例如，计算阶乘的递归函数如下：```int factorial(int n) {if (n == 0) return 1; // 终止条件return n * factorial(n - 1); // 递归调用}```四、编程题8. 编写一个函数，实现单链表的反转。
答案：```c// 假设ListNode是链表节点的定义ListNode* reverseList(ListNode* head) {ListNode* prev = NULL;ListNode* curr = head;ListNode* next = NULL;while (curr != NULL) {next = curr->next; // 保存下一个节点curr->next = prev; // 反转指针prev = curr; // 移动prevcurr = next; // 移动curr}return prev; // 新的头节点}```9. 给定一个整数数组，请实现一个函数来找到数组中的最长连续子序列的长度。
数据结构简答题引言概述：数据结构是计算机科学中的重要概念，用于组织和存储数据以便有效地访问和操作。
在计算机科学课程中，经常会遇到关于数据结构的简答题，考察学生对数据结构基本概念的理解。
本文将介绍一些常见的数据结构简答题，并提供详细的解答。
一、数组1.1 什么是数组？数组是一种数据结构，用于存储相同类型的数据元素。
数组中的元素通过索引访问，索引通常从0开始计数。
1.2 数组的优点是什么？- 数组具有快速的随机访问能力，可以通过索引快速定位元素。
- 数组在内存中是连续存储的，访问效率高。
- 数组支持快速的元素插入和删除操作。
1.3 数组的缺点是什么？- 数组的大小通常是固定的，无法动态调整。
- 插入和删除元素时需要移动其他元素，效率较低。
- 数组只能存储相同类型的数据，不适用于存储不同类型数据。
二、链表2.1 什么是链表？链表是一种线性数据结构，由节点组成，每个节点包含数据和指向下一个节点的指针。
链表中的节点可以动态分配内存，大小可动态调整。
2.2 链表的优点是什么？- 链表的大小可以动态调整，插入和删除元素效率高。
- 链表不需要连续的内存空间，更灵活。
- 链表支持快速的插入和删除操作，不需要移动其他元素。
2.3 链表的缺点是什么？- 链表需要额外的指针存储节点间的连接关系，占用额外空间。
- 链表的随机访问效率较低，需要从头节点开始逐个访问。
- 链表的操作需要更多的指针操作，可能引起指针丢失或内存泄漏。
三、栈3.1 什么是栈？栈是一种后进先出（LIFO）的数据结构，只允许在栈顶进行插入和删除操作。
栈常用于实现函数调用、表达式求值等场景。
3.2 栈的优点是什么？- 栈的插入和删除操作只在栈顶进行，操作简单高效。
- 栈支持递归调用，用于实现函数调用和内存管理。
- 栈可以有效地解决一些问题，如括号匹配、表达式求值等。
3.3 栈的缺点是什么？- 栈的大小通常是固定的，可能会发生栈溢出。
- 栈只能在栈顶进行操作，限制了数据的访问方式。
数据结构考试题及答案一、选择题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. 下列哪种数据结构是一种线性结构？A. 树B. 栈C. 图D. 队列答案：B. 栈2. 以下哪种不是二叉树的遍历方式？A. 先序遍历B. 层序遍历C. 后序遍历D. 中序遍历答案：B. 层序遍历3. 在队列中，哪种操作不是O(1)时间复杂度的？A. 入队B. 出队C. 判空D. 获取队首元素答案：D. 获取队首元素二、填空题4. 二叉查找树的中序遍历结果为_______。
答案：升序排列的序列5. 栈的特点是_______进，_______出。
答案：后进，先出6. 图中两点间存在边则称它们为_______。
答案：邻接点三、简答题7. 请简要介绍一下栈和队列的应用场景及区别。
答：栈和队列都是常用的数据结构，栈适合用于实现括号匹配、表达式求值等场景，而队列常用于实现广度优先搜索、缓存队列等。
栈是一种后进先出的数据结构，而队列是一种先进先出的数据结构。
8. 什么是哈希表？它的优缺点分别是什么？答：哈希表是一种通过哈希函数将关键字映射到数组位置的数据结构。
其优点是能够快速查找、插入、删除元素，时间复杂度接近O(1)；缺点是可能发生哈希冲突，导致性能下降。
四、综合题9. 给定以下无向图的邻接矩阵表示，请写出图的深度优先搜索（DFS）遍历路径。
```0 1 2 30 0 1 0 11 1 0 1 12 0 1 0 13 1 1 1 0```答：起始节点为0，路径：0 - 1 - 3 - 210. 写出以下树的层序遍历结果。
```1/ \2 3/ \ / \4 5 6 7```答：1 - 2 - 3 - 4 - 5 - 6 - 7以上就是数据结构考试题及答案，希望对您有所帮助。
如果有不清楚的地方，欢迎随时向老师询问。
祝您考试顺利！。
数据结构简答题第⼀章绪论1、数据结构是⼀门研究什么的学科？数据结构是⼀门研究⾮数值计算的程序设计问题中，计算机操作对象及对象间的关系和施加于对象的操作等的学科。
2、数据存储结构有哪⼏种类型？存储结构可分为顺序存储、链式存储、索引存储和散列存储。
3、数据逻辑结构包括哪⼏种类型？逻辑结构包括线性结构和⾮线性结构。
更细分的话可以说，逻辑结构包括集合、线性结构（线性表、栈、队列等）、树形结构和⽹状结构。
4、数据结构与数据类型有什么区别？答：数据结构这⼀术语有两种含义，⼀是作为⼀门课的名称，⼆是作为⼀个科学的概念，⽬前尚⽆公认定义，⼀般认为，数据结构包括三个⽅⾯数据的逻辑结构，数据的存储结构，数据的运算。
⽽数据类型是值的集合和操作的集合，可以看做是已实现了的数据结构，后者是前者的⼀种简化情况。
5、数据类型和抽象数据类型是如何定义的？⼆者有何相同和不同之处？抽象数据类型的主要特点是什么？使⽤抽象数据类型的主要好处是什么？数据类型和抽象数据类型是如何定义的？⼆者有何相同和不同之处？抽象数据类型的主要特点是什么？使⽤抽象数据类型的主要好处是什么？答：数据类型是程序设计语⾔中的⼀个概念，数据类型是值的集合和操作的集合，可以看做是已实现了的数据结构抽象数据类型指⼀个数学模型及定义在该模型上的⼀组操作。
抽象的意义在于数据类型的数学抽象特性。
抽象数据类型的定义仅取决于它的逻辑特性，⽽与其在计算机内部如何表⽰与实现⽆关。
⽆论其内部如何变化。
只要它的数学特性不变就不影响它的外部使⽤。
抽象数据类型和数据类型实质上是⼀个概念，但是抽象数据类型的范围更⼴，它已不再局限于机器已定义和实现的数据类型，还包括⽤户在设计软件系统时⾃⾏定义的数据类型。
使⽤抽象数据类型定义的软件模块含定义，表⽰和实现三部分，封装在⼀起，对⽤户透明(提供接⼝)，⽽不必了解实现细节。
6、名词解释数据：是对客观事物的符号表⽰，在计算机科学中指所有能输⼊到计算机并能被计算机程序处理的符号总称。
数据结构简答题数据结构是计算机科学中的重要概念，它用于组织和存储数据，以便能够高效地访问和操作数据。
以下是几个常见的数据结构简答题，详细解答如下：1. 什么是数据结构？数据结构是一种组织和存储数据的方式，它定义了数据元素之间的关系和操作。
数据结构可以分为线性结构（例如数组、链表）、树形结构（例如二叉树、堆）、图形结构（例如有向图、无向图）等。
2. 请简要介绍数组和链表的区别。
数组是一种线性结构，它将元素存储在连续的内存空间中。
数组的大小在创建时就确定，访问元素的时间复杂度为O(1)，但插入和删除元素的时间复杂度较高，为O(n)。
链表是另一种线性结构，它使用节点存储元素，并通过指针链接这些节点。
链表的大小可以动态改变，插入和删除元素的时间复杂度为O(1)，但访问元素的时间复杂度较高，为O(n)。
3. 请简要介绍栈和队列的特点和应用场景。
栈是一种后进先出（LIFO）的数据结构，只能在一端进行插入和删除操作。
栈的应用场景包括函数调用、表达式求值、括号匹配等。
队列是一种先进先出（FIFO）的数据结构，只能在一端进行插入操作，在另一端进行删除操作。
队列的应用场景包括任务调度、消息队列、广度优先搜索等。
4. 请简要介绍二叉树和图的特点和应用场景。
二叉树是一种树形结构，每一个节点最多有两个子节点。
二叉树的应用场景包括搜索树、哈夫曼编码、排序算法等。
图是一种复杂的非线性结构，由节点和边组成。
图的应用场景包括社交网络、路径规划、最小生成树等。
5. 请简要介绍哈希表的特点和应用场景。
哈希表是一种使用哈希函数将键映射到值的数据结构，通过哈希函数可以快速定位到对应的值。
哈希表的插入、删除和查找操作都具有常数时间复杂度，适合于需要快速查找的场景，如数据库索引、缓存系统等。
6. 请简要介绍堆的特点和应用场景。
堆是一种彻底二叉树，可以分为最大堆和最小堆。
最大堆中，父节点的值大于或者等于子节点的值；最小堆中，父节点的值小于或者等于子节点的值。
1.什么叫做数据结构？
答：数据结构是计算机储存、组织数据的方式。
数据结构是指相互间存在的一种或多种特定的关系的数据元素的集合。
数据结构分为逻辑结构（集合、线性结构、树形结构、图状结构）和物理结构（顺序储存、链式储存、索引储存、散列储存）。
2.什么事算法？5种特征。
答：算法是特定问题的求解步骤的描述，是指令的有限序列，其中每条指令表示一个或者多个操作。
1）有穷性2）确定性3）可行性4)输入5）输出。
3.排序的核心思想？（排序中什么是稳定的，什么是不稳定的？）
答：排序就是使一组记录，按照记录中某个或某些关键字的大小，递增或递减排列起来的操作，排序的最终目的是实现快速查找。
在待排序文件中，若存在关键字相同的多个记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的，若具有仙童关键字记录之间的相对次序发生变化，则称这种方法是不稳定的。
4.图遍历（逻辑结构的遍历出的结果不是唯一的）
图遍历是指从图的任一顶点出发，对图中的所有顶点访问一次且只访问一次。
图的遍历分为深度优先搜索和广度优先搜索。
（逻辑结构的遍历不是唯一的，如果确定其储存结构，那他们是唯一的因为在储存时人为的定义了第一个顶点以及各定点之间的领接关系的顺序。
若单从逻辑上考虑算法是不唯一的）。
5.什么是拓扑遍历？
答：给出有向图G=（V，E），对于V中顶点的线性序列（Vi1,Vi2…Vin），如果满足在G点的一个拓扑顶点Vi到Vj有一条路径，则在序列中顶点Vi必在Vj之前，则该序列称为G 的一个拓扑序列。
构造有向图的一个拓扑序列的过程称谓拓扑排序。
27．分别写出下图所示二叉树的前序、中序和后序表示。
28．已知图G=（V ，E ），其中：
V={a,b,c,d,e},
E={(a,b),(b,d),(c,b),(c,d),(d,e),(e,a),(e,c)}。
（1）画出图G ；
（2）画出图G 的邻接表。
29.以关键字序列(265, 301, 751, 129, 937, 863, 742, 694, 76, 438)为例，写出直接插入排序时各趟排序结束时关键字序列的状态。
30. 已知无向图G 的邻接矩阵如题图所示。
请画出该无向图，并写出按深度优先搜索时的访问序列。
31. 已知连通网的邻接矩阵
A=⎥⎥⎥⎥⎥⎥⎦
⎤⎢⎢⎢⎢⎢
⎢⎣
⎡∞∞
∞∞∞∞∞∞∞4
2
104962812981106121， 试画出它的最小生成树。
27. 每个序列2分。
前序：ABDCEFGH;中序：BDAFEHGC;后序：DBFHGECA
28.
3分，
邻接表包含表项：
a->b^;b->d^;c->b->d^;d->e^;e->a->c^ (3分)
29.
1.[265] 301 751 129 937 863 742 694 76 438
2.[265 301] 751 129 937 863 742 694 76 438
3.[265 301 751] 129 937 863 742 694 76 438
4.[129 265 301 751] 937 863 742 694 76 438
5.[129 265 301 751 937] 863 742 694 76 438
6.[129 265 301 751 863 937] 742 694 76 438
7.[129 265 301 742 751 863 937] 694 76 438
8.[129 265 301 694 742 751 863 937] 76 438
9.[76 129 265 301 694 742 751 863 937] 438 10.[76 129 265 301 438 694 742 751 863 937]
30.画出图（3分）并写出顺序：0，1，2，4，3（3分）
31.
//----------------------------------------------------------------------------------------------// 27．某广义表为（a,(b,c)），画出该广义表的图形表示。
28．写出题图所示的有向图的拓扑排序序列。
29.以关键字序列(265, 301, 751, 129, 937, 863, 742, 694, 76, 438)为例，写出希尔排序时各趟排序结束时关键字序列的状态。
30. 已知无向图G 的邻接矩阵如题图所示。
请画出该无向图，并写出按深度优先搜索时的访问序列。
31. 已知一棵二叉树的顺序存储结构如题图所示，其中∧表示虚结点，试构造该二叉树。
27. 首先将(a,(b,c))写为A(a,B(b,c))(2分)
4分
28.CABEDF
29.增量序列：4，2，1
初态.265 301 751 129 937 863 742 694 76 438
1.76 301 742 129 265 438 751 694 937 863
2.76 129 265 301 742 438 751 694 937 863
3. 76 129 265 301 438 694 742 751 863 937
30.画出图（3分）并写出顺序：0，1，2，4，3（3分）
31.
//--------------------------------------------------------------------------// 27．已知一棵度为m 的树中有n 1个度为1的结点，n 2个度为2的结点,…,n m 个度为m 的结点，问该树有多少个叶结点？
28．画出下图所示二叉树的中序线索链表的存储表示。
29.设散列函数H （key ）=key mod 11，给定键值序列为13、41、15、44、6、68、17、26、39、46，试画出相应的开散列表。
30. 从一个空的二叉排序树开始，依次插入关键字25、13、15、34、7、20、37，试分别画出每次插入关键字后的二叉排序树。
27.
02
2
1,21,2m m i m i i n n n im n n =
=+
=+
∑
∑
∑
，分分分
28.
29.题目中前5个数填对得2分，后4个数填对得4分
30.画出图（3分）并标出顺序（3分）
//---------------------------------------------------------------------// 27．某广义表的表头和表尾均为（a,(b,c), d ），画出该广义表的图形表示。
28．已知带权图的邻接表如下所示，其中边表结点的结构为：
依此邻接表从顶点C 出发进行深度优先遍历。
写出遍历序列以及遍历过程中得到的从顶点C 到其它各顶点的带权路径及其长度。
29.以关键字序列(265, 301, 751, 129, 937, 863, 742, 694, 76, 438)为例，写出基数排序时各趟排序结束时关键字序列的状态。
27. 首先将(a,(b,c),d)写为A(a,B(b,c),d)(2分)
(4分)
28.CDBAFE （3分）
C->D 20;C->D->B 40;C->D->B->A 51;C->D->B->F 49;C->D->B->F->E 63 (3分) 29.增量序列：4，2，1
初态.265 301 751 129 937 863 742 694 76 438 1.个位 301 751 742 863 694 265 76 937 438 129 2.十位 301 129 937 438 742 751 863 265 76 694 3.百位76 129 265 301 438 694 742 751 863 937
//-------------------------------------------------------------------------// 27．有一字符串序列为5*-x-y/x+2，利用栈的运算将其输出结果变为5x-*yx+/-2，试写出该操作的入栈和出栈过程（采用push(a)表示a 入栈，pop(a)表示a 出栈）。
29.已知树如图所示，是写出其顺序存储结构。
30. 关键字集合为{ 19, 01, 23, 14, 55, 68, 11, 82, 36 }，哈希函数为：
Hash(key)=key mod 7.试写出哈希表的拉链地址表示。
31. 已知二维数组如下，试写出其稀疏矩阵三元组表示。
27. push(5), pop(5), push(*), push(-), push(x), pop(x), pop(-), pop(*), push(-), push(y), pop(y),
push(/), push(x), pop(x), push(+), pop(+), pop(/), pop(-), push(2), pop(2)
31.
27．已知权值集合W={5，6，2，9，7}，试画出其Huffman 树。
28．对下图中的有向图，给出其邻接矩阵，并写出从顶点5开始的广度优先搜索序列。
30. 关键字集合为{ 19, 01, 23, 14, 55, 68, 11, 82, 36 }，哈希函数为：
Hash(key)=key mod 7.试写出开放地址线性探查的哈希表表示并写出计算过程。
27.
28.
111
1
11____1
1
1
_______1
⎡⎤⎢⎥⎢⎥⎢⎥
⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦
（3分） 5->1->4->2->3->6 (3分) //--------------------------------------------------------------------------------------------//
29.已知连通图的邻接矩阵如下，试根据普里姆算法写出其最小生成树构造过程中边集的变化过程。
（顶点集为{A, B, C, D, E}）
⎥⎥⎥⎥⎥⎥⎦
⎤⎢⎢⎢⎢⎢⎢⎣
⎡∞∞
∞∞∞∞∞∞∞
4
2
104962812981106121
31.如图所示二叉树是否为平衡二叉树？若是，说明理由；若不是，将其转换为平衡二叉树
（以顺序存储表示）。
29. {AB},{AB,AD},{AB,AD,DE},{AB,AD,DE,EC} 31.不是。
（2分）
（4分）
//-------------------------------------------------------------------//
30. 从一个空的二叉排序树开始，依次插入关键字25、13、15、34、7、20、37，试分别画出每次插入关键字后的二叉排序树。
31. 某二叉树的先根遍历序列为ABIJCDFGHE，中根遍历序列为IJBADGFHCE，试写出它
的后序遍历序列。
30.画出图（3分）并标出顺序（3分）
31.JIBGHFDEC。
