下载文档原格式
数据结构复习题及答案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．在用散列表存储关键码集合时，可以用双散列法寻找下一个空桶。
《数据结构-C语言版》第一章绪论单项选择题1．在数据结构中，数据的基本单位是_____ ____。
A. 数据项B. 数据类型C. 数据元素D. 数据变量2．数据结构中数据元素之间的逻辑关系被称为__ ____。
A. 数据的存储结构B. 数据的基本操作C. 程序的算法D. 数据的逻辑结构3．在数据结构中，与所使用计算机无关的是数据的____ ___。
A. 存储结构B. 逻辑和物理结构C. 逻辑结构D. 物理结构4．在链式存储结构中，数据之间的关系是通过____ ____体现的。
A. 数据在内存的相对位置B. 指示数据元素的指针C. 数据的存储地址D. 指针5．计算算法的时间复杂度是属于一种____ ___。
A. 事前统计的方法B. 事前分析估算的方法C. 事后统计的方法D. 事后分析估算的方法6．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是____ __。
A. n2B. nlognC. nD. logn7．设使用某算法对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为____ ___。
A. O(1)B. O(n)C. O(200n)D. O(nlog2n)CDCBBDD第二章线性表单项选择题1．链表不具有的特点是____ ____。
A. 可随机访问任一元素B. 插入和删除时不需要移动元素C. 不必事先估计存储空间D. 所需空间与线性表的长度正比2．设顺序表的每个元素占8个存储单元。
第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为。
A. 139B. 140C. 147D. 1483．在线性链表存储结构下，插入操作算法。
A. 需要判断是否表满B. 需要判断是否表空C. 不需要判断表满D. 需要判断是否表空和表满4．在一个单链表中，若删除p所指结点的后继结点，则执行。
A. p->next = p->next->next;B. p->next = p->next;C. p = p->next->next;D. p = p->next; p->next = p->next->next;5．将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为。
数据结构复习题及答案一、选择题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指针指向前一个节点，直到链表末尾。
最后，将新链表的头节点设置为原链表的最后一个节点的前驱节点。
数据结构考试复习题答案1. 什么是数据结构？数据结构是计算机存储、组织数据的方式。
它包括数据的逻辑结构和物理结构。
逻辑结构描述数据元素之间的关系，而物理结构描述数据在计算机中的存储方式。
2. 线性表有哪些基本操作？线性表的基本操作包括：插入、删除、查找和排序。
插入操作是在表的指定位置添加一个元素；删除操作是从表中移除一个元素；查找操作是确定一个元素是否存在于表中；排序操作是将表中的元素按照一定的顺序排列。
3. 栈和队列的主要区别是什么？栈是一种后进先出（LIFO）的数据结构，而队列是一种先进先出（FIFO）的数据结构。
在栈中，最后加入的元素最先被移除，而在队列中，最先加入的元素最先被移除。
4. 什么是二叉树？二叉树是一种树形数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。
二叉树的根节点没有父节点，而每个非根节点只有一个父节点。
5. 什么是哈希表？哈希表是一种通过哈希函数将键映射到表中一个位置以便快速访问数据的数据结构。
它通过计算键的哈希值来快速定位数据，从而实现高效的查找、插入和删除操作。
6. 图的遍历算法有哪些？图的遍历算法主要有深度优先搜索（DFS）和广度优先搜索（BFS）。
DFS从图中的一个顶点开始，尽可能深地搜索图的分支；BFS从图中的一个顶点开始，先访问所有相邻的顶点，然后再逐层向外扩展。
7. 什么是最小生成树？最小生成树是连接图中所有顶点的边的子集，它构成了一棵树，并且包含了图中所有的顶点，同时这棵树的总权重是所有可能的生成树中最小的。
8. 排序算法有哪些？常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序。
每种排序算法都有其特定的应用场景和效率。
9. 什么是递归？递归是一种在函数中调用自身的编程技术，用于解决可以分解为相似子问题的问题。
递归需要有一个明确的结束条件，以避免无限递归。
10. 什么是动态规划？动态规划是一种通过将复杂问题分解为更简单的子问题来求解的方法。
最新版《数据结构》各章习题及答案第一章绪论一、选择题1.组成数据的基本单位是（）（A）数据项（B）数据类型（C）数据元素（D）数据变量2.数据结构是研究数据的（）以及它们之间的相互关系。
（A）理想结构，物理结构（B）理想结构，抽象结构（C）物理结构，逻辑结构（D）抽象结构，逻辑结构3.在数据结构中，从逻辑上可以把数据结构分成（）（A）动态结构和静态结构（B）紧凑结构和非紧凑结构（C）线性结构和非线性结构（D）内部结构和外部结构4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。
① （A）数据元素（B）计算方法（C）逻辑存储（D）数据映像② （A）结构（B）关系（C）运算（D）算法5.算法分析的目的是（）。
（A）找出数据结构的合理性（B）研究算法中的输入和输出的关系（C）分析算法的效率以求改进（D）分析算法的易懂性和文档性6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5 个特性。
① （A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法② （A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性（C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性二、判断题1.数据的机内表示称为数据的存储结构。
（）2.算法就是程序。
（）3.数据元素是数据的最小单位。
（）4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。
（）5.算法的时间复杂度取决于问题的规模和待处理数据的初态。
（）三、填空题1.数据逻辑结构包括________、________、_________ 和__________ 四种类型,其中树形结构和图形结构合称为_____ 。
2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______ 个前驱结点；最后一个结点______后续结点,其余每个结点有且只有 _______ 个后续结点。
3.在树形结构中,树根结点没有_______ 结点,其余每个结点有且只有_______个前驱结点；叶子结点没有 ________ 结点,其余每个结点的后续结点可以_________。
数据结构题库及答案详解一、选择题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. 给定一个整数数组，如何找到数组中的最大值和最小值？答案：可以使用遍历数组的方式，依次比较每个元素与当前的最大值和最小值，更新最大值和最小值即可。
2. 给定一个整数数组和一个目标值，如何判断数组中是否存在两个数的和等于目标值？答案：可以使用两层循环遍历数组，依次判断每两个数的和是否等于目标值。
二、链表1. 如何反转一个单链表？答案：可以使用三个指针prev、curr和next，分别表示当前节点的前一个节点、当前节点和当前节点的下一个节点。
通过遍历链表，每次将当前节点的next指针指向prev节点，然后更新prev、curr和next指针，直到遍历到链表的末尾。
2. 如何判断一个链表是否有环？答案：可以使用快慢指针的方法。
定义两个指针slow和fast，初始时都指向链表的头节点。
slow指针每次移动一步，fast指针每次移动两步。
如果链表中存在环，那么两个指针最终会相遇；如果链表中不存在环，那么fast指针会先到达链表的末尾。
三、栈和队列1. 如何使用栈实现队列？答案：可以使用两个栈来实现队列。
一个栈用来存储入队的元素，另一个栈用来存储出队的元素。
当需要入队时，直接将元素压入第一个栈；当需要出队时，如果第二个栈为空，则将第一个栈中的元素依次弹出并压入第二个栈，然后从第二个栈中弹出元素；如果第二个栈不为空，则直接从第二个栈中弹出元素。
2. 如何使用队列实现栈？答案：可以使用两个队列来实现栈。
一个队列用来存储元素，另一个队列用来辅助操作。
当需要入栈时，直接将元素入队；当需要出栈时，将队列中的元素依次出队并入辅助队列，直到队列中只剩下一个元素，然后将该元素出队；然后交换两个队列的角色，使得辅助队列成为主队列，主队列成为辅助队列。
数据结构复习题(附答案)数据结构复习题(附答案)数据结构是计算机科学中非常重要的一门课程，其涉及到对数据的组织、存储和管理方法的研究。
在学习数据结构的过程中，我们通常需要进行大量的练习和复习以加深对各种数据结构和算法的理解。
本文将为大家提供一些数据结构的复习题，并附有详细的答案解析。
一、栈和队列1. 给定一个字符串，判断其中的括号序列是否合法。
例如，"{([])}"是合法的括号序列，而"{[)]}"则是非法的。
答案：使用栈的数据结构可以很方便地解决这个问题。
遍历字符串，遇到左括号就将其入栈，遇到右括号就判断对应的左括号是否与栈顶元素相匹配，如果匹配则将栈顶元素出栈，继续比较下一个字符。
最后，栈为空则表示括号序列合法。
2. 设计一个队列，实现队列的基本操作：入队、出队、获取队头元素和判断队列是否为空。
答案：可以使用一个数组来实现队列，使用两个指针front和rear分别指示队头和队尾的位置。
入队操作时，将元素添加到rear指向的位置，并将rear后移一位；出队操作时，将front后移一位；获取队头元素时，返回front指向的位置的元素；判断队列是否为空可以通过比较front和rear来确定。
3. 反转一个单链表。
答案：使用三个指针prev、curr和next来实现链表的反转。
初始时，将prev指向null，curr指向头节点，next指向curr的下一个节点。
然后，将curr的next指向prev，将prev指向curr，将curr指向next，再将next指向next的下一个节点。
重复这个操作，直到链表反转完成。
4. 判断一个单链表中是否存在环。
答案：使用快慢指针的方法可以判断一个单链表中是否存在环。
如果存在环，那么快指针最终会追上慢指针；如果不存在环，那么快指针最终会达到链表的末尾。
三、树和图5. 给定一个二叉树，编写一个算法来判断它是否是平衡二叉树。
答案：平衡二叉树的定义是指二叉树的每个节点的左子树和右子树的高度差不超过1。
数据结构复习题及答案数据结构习题一、名词解释1.数据、数据元素、数据项、数据结构、数据的逻辑结构、数据物理结构、顺序存储、链式存储、算法、时间复杂度、空间复杂度。
2.线性表、顺序表、单链表、双向链表、循环链表、双向循环链表、三个概念的区别：头指针、头结点、首元结点(第1个元素结点)。
3.栈（顺序栈、链栈）、队列（顺序队、链队）、循环队列、递归、稀疏矩阵、三元组。
4.树、叶子结点、结点的度、树的度、树的高(深)度、二叉树、遍历、满二叉树、完全二叉树、哈夫曼树、WPL、哈夫曼编码。
5.图（有向、无向）、网、边、弧、度、入度、出度、完全图（有向、无向）、（强）连通图（分量）、（最小）生成树、邻接矩阵、邻接表、DFS、BFS。
6.查找表、关键字、静态查找、动态查找、ASL、顺序查找、折半查找、分块查找、二叉排序树。
7、排序、内（外）排序、稳定性、插入（直接、希尔），交换（起泡、快速），选择（直接、堆），2路归并。
一、填空题1.数据结构是研究数据的_逻辑结构__和___物理结构__，并在这种结构上定义相关的运算，设计实现这些运算的算法，分析算法的效率。
算法的效率包括时间和空间两个方面，分别称为___时间复杂度____和__空间复杂度___。
2.数据的基本单元是__数据元素__，数据的最小单元是__数据项_。
3.算法是对特定问题求解___步骤___的一种描述，是指令的有限序列。
4.一个算法的时间复杂度为(3n3+2n—7)，其数量级表示为O（n3）_。
5.一个算法具有5个特性：确定性、可行性、有穷性、输入和输出。
6.算法机能的阐发和怀抱，能够从算法的工夫庞大度和空间庞大度来评判算法的好坏。
7.数据的逻辑布局包孕调集布局、线性布局、树形布局和图型布局四品种型。
8.数据布局在计较机中的表示称为数据的物理布局，它能够采用__按次存储___或__链式存储_两种存储方法。
9.线性表有两种存储布局，划分为按次存储和链式存储。
问答题121.算法和程序的区别是什么呢？3【参考答案】：算法的含义与程序十分相似，但又有区别。
一个程序不一定满足有穷性。
例如，操作系统，只要整个系统不遭破坏，它将永远不会停止，即45使没有作业需要处理，它仍处于动态等待中。
因此，操作系统不是一个算法。
6另一方面，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。
7算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。
一个算法8若用程序设计语言来描述，则它就是一个程序。
9算法与数据结构是相辅相承的。
解决某一特定类型问题的算法可以选定不同10的数据结构，而且选择恰当与否直接影响算法的效率。
反之，一种数据结构的11优劣由各种算法的执行来体现。
12要设计一个好的算法通常要考虑以下的要求。
13⑴正确。
算法的执行结果应当满足预先规定的功能和性能要求。
14⑵可读。
一个算法应当思路清晰、层次分明、简单明了、易读易懂。
15⑶健壮。
当输入不合法数据时，应能作适当处理，不至引起严重后果。
⑷高效。
有效使用存储空间和有较高的时间效率。
1617182. 抽象数据类型的定义由哪几部分组成？19【参考答案】：数据对象、数据关系和基本操作三部分。
203. 按数据元素之间的逻辑关系不同，数据结构有哪几类？【参考答案】：线性结构、树型结构、图状结构和集合四类。
21224. 你能举出几个你熟悉的"序列"的例子来吗？23【参考答案】：如："0，1，2，…，9","A，B，C，…，Z"。
5. 简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据2425类型和抽象数据类型。
266.数据结构和数据类型两个概念之间有区别吗？27【参考答案】：简单地说，数据结构定义了一组按某些关系结合在一起的数组28元素。
数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组29操作。
307. 简述线性结构与非线性结构的不同点。
31【参考答案】：线性结构反映结点间的逻辑关系是一对一的，非线性结构反32映结点间的逻辑关系是多对多的。
338. 有下列两段描述：34（1）void pro1( ) (2)void pro2( )35{ {36n=2; y=0;37While(n%2==0) x=5/y;38n=n+2;printf(“%d,%d\n,x,y);3940printf(“%d\n”,n); }}4142这两段描述均不能满足算法的特征，试问它们违反了算法的那些特征？43【参考答案】：（1）是一个死循环，违反了算法的有穷性特征。
（2）出现除零44错误，违反了算法的可行性特征。
459. 分析并写出下面的各语句组所代表的算法的时间复杂度。
46(1) for (i=0; i<n; i++)47for (j=0; j<m; j++)48A[i][j]=0;49【参考答案】：O（m*n）5051(2) k=0;52for( i=1; i<=n; i++) {53for (j=i ; j<=n; j++)54k++;55}56【参考答案】：O（n2）5758(3) i=1;59while(i<=n)i=i*3;60【参考答案】：3 T(n)≤n即：T(n) ≤log3n =O（log3n）所以：T(n)= O（log3n）6162(4) k=0;63for( i=1; i<=n; i++) {64for (j=i ; j<=n; j++)65for (k=j ; k<=n; k++)66x += delta;;67}68【参考答案】：O（n3）6970(5) for(i=0,j=n-1;i<j;i++,j- -)71{t=a[i]; a[i]= a[j]; a[i]=t;}72【参考答案】：基本语句共执行了n/2次，T(n)=O（n）737410．讨论线性表的逻辑结构和存储结构的关系，以及不同存储结构的比较。
75【答案】存储结构分为：76⑴顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻77辑关系7879链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系80⑵数据的逻辑结构—只抽象反映数据元素的逻辑关系81数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的实现82⑶数据的逻辑结构与存储结构密切相关：83算法设计→逻辑结构84算法实现→存储结构85⑷顺序表：86可以实现随机存取：(1)87插入和删除时需要移动元素：(n)88需要预分配存储空间;适用于“不常进行修改操作、表中元素相对稳定”的场8990合。
91链表：只能进行顺序存取：(n)9293插入和删除时只需修改指针：(1)94不需要预分配存储空间;95适用于“修改操作频繁、事先无法估计最大表长”的场合。
96——应用问题的算法时间复杂度的比较97例如，以线性表表示集合进行运算的时间复杂度为(n2),98而以有序表表示集合进行运算的时间复杂度为99(n)10010111．判断下列概念的正确性102(1) 线性表在物理存储空间中也一定是连续的。
103(2) 链表的物理存储结构具有同链表一样的顺序。
104(3) 链表的删除算法很简单，因为当删去链表中某个结点后，计算机105会自动地将后继的各个单元向前移动。
10610712．试比较顺序存储结构和链式存储结构的优缺点。
108答：109顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构110是统一的，，要求内存中存储单元的地址必须是连续的。
111优点：一般情况下，存储密度大，存储空间利用率高。
112缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，113必须预先分配较大的空间，往往使存储空间不能得到充分利用；（3）表的容量114难以扩充。
115链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分116存放结点值，另一部分存放表示结点间关系的指针。
优点：插入和删除元素时很方便，使用灵活。
117118缺点：存储密度小，存储空间利用率低。
11913．试写出一个计算链表中结点个数的算法，其中指针ｐ指向该链表的第一个120结点。
121答：int linklist_num(linklist L,Lnode *p) 122{ int n=0; 123While(p){n++;p=p->next;} 124Return n: 125} 12614．试设计实现在单链表中删去值相同的多余结点的算法。
(a)为删除前，(b)127为删除后。
128129130131132133134答：void Deletaz(Linklist L) 135{ Lnode *p,*q,*r,*s; 136P=l->next; 137while (p) {q=p;r=q->next; 138while(r){if(r->data!=p->data){q=r;r=r->next}; 139else{s=r->next;q->next=s;free(r);r=s;}140141}142P=p->next;143}144}14514615. 设有两个单链表A、B，其中元素递增有序，编写算法将A、B归并成147一个按元素值递减（允许有相同值）有序的链表C，要求用A、B中的原结点148形成，不能重新申请结点。
149答：void unit(Linklist A,Linklist B,Linklist C)150{Lnode *p,*q,*r,*s;151P=A->next;q=>next;C=A;r=C;152While(p&&q)153{if(p->dada<=q->dada){r=p;p=p->next;}154Else{s=q;q=q->next;s->next=r->next;r->next=s;r=s;}155}16. 如果输入序列为1 2 3 4 5 6,试问能否通过栈结构得到以下两个序列:4 3 1561575 6 1 2和1 3 5 4 2 6;请说明为什么不能实现或如何才能得到。
15817. 设输入序列为2，3，4，5，6，利用一个栈能得到序列2，5，3，4，6吗？159160栈可以用单链表实现吗？【答案】1611、输入序列为123456，不能得出435612，其理由是，输出序列最后两元素162是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能栈163底元素1在栈顶元素2之前出栈。
164得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和1653入栈，3出栈，部分输出序列变为：13；接着4和5入栈，5，4和2依次出栈，166部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。
1672、不能得到序列2，5，3，4，6。
栈可以用单链表实现，这就是链栈。
由于168栈只在栈顶操作，所以链栈通常不设头结点。
16917017117218．填空173（1）一个字符串相等的充要条件是和。
174（2）串是指的序列；空串是指的串；空格串是指175的串。
176（3）设s=“I︺AM︺A︺TEACHER”,其长度是___。
177（4）若n为主串长，m为子串长，则串的古典匹配算法最坏的情况下需要178比较字符的总次数为。
17918018118218319．设s=”00001000010100001”, t =”0001”,说明其在朴素模式匹配算法184中的匹配过程。
185186答：187i=3188第一趟匹配 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1189(1) 0 0 0 1190j=3191192i=5193第二趟匹配0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1194(2) 0 0 0 1195j=419619719819920020、已知一个二叉树的先序和中序序列，能否唯一确定一棵二叉树？并举例。
201若给定先序遍历序列和后序遍历序列，能否唯一确定，说明理由（或举例说明）。
202【参考答案】：前一个可以唯一确定一个二叉树，前序abdghcefi 中序203gdhbaecif204205若只知道前序和后序序列是不能确定唯一的二叉树的，如图中为二棵不同的206二叉树，其先序和后序的序列相同，分别为：ba和ab：20720820921021121、假定用于通信的电文由8个字母A，B，C，D，E，F，G，H组成，各字母212在电文中出现的概率为5％，25％，3％，7％，10％，12％，30％，8％，试为213这8个字线设计哈夫曼编码。
