下载文档原格式
数据结构复习题及参考答案《数据结构》课程复习资料一、填空题:1.设需要对5个不同的记录关键字进行排序，则至少需要比较________次，至多需要比较__________次。
2.设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较_________次。
3.设在长度为20的有序表中进行二分查找，则比较一次查找成功的结点数有_________个，比较两次查找成功有结点数有_________个。
4.数据结构从逻辑上划分为三种基本类型：___________、__________和___________。
5.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。
6.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度___________。
7.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序过程的时间复杂度为________。
8.在快速排序、堆排序、归并排序中，_________排序是稳定的。
9.在有n个叶子结点的哈夫曼树中，总结点数是_______。
10.一棵树T采用二叉链表存储，如果树T中某结点为叶子结点，则在二叉链表BT中所对应的结点一定_______。
11.3.已知数组A［10］［10］为对称矩阵，其中每个元素占5个单元。
现将其下三角部分按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A［5，6］对应的地址是_______。
12.在有n个结点的无向图中，其边数最多为_______。
13.取出广义表A=(x,(a,b,c,d))中原子x的函数是_______。
14.对矩阵采用压缩存储是为了___ ____。
15.带头结点的双循环链表L为空表的条件是_______。
16.设线性表中元素的类型是实型，其首地址为1024，则线性表中第6个元素的存储位置是。
（完整版）数据结构复习题（附答案）⼀、算法设计题（每题15分，共60分）答题要求：①⽤⾃然语⾔说明所采⽤算法的思想；②给出每个算法所需的数据结构定义，并做必要说明；③写出对应的算法程序，并做必要的注释。
1、有⼀个带头结点的单链表，每个结点包括两个域，⼀个是整型域info，另⼀个是指向下⼀个结点的指针域next。
假设单链表已建⽴，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保留⼀个。
3、约瑟夫环问题（Josephus问题）是指编号为1、2、…，n的n（n>0）个⼈按顺时针⽅向围坐成⼀圈，现从第s个⼈开始按顺时针⽅向报数，数到第m个⼈出列，然后从出列的下⼀个⼈重新开始报数，数到第m的⼈⼜出列，…，如此重复直到所有的⼈全部出列为⽌。
现要求采⽤循环链表结构设计⼀个算法，模拟此过程。
4、编程实现单链表的就地逆置。
23．在数组 A[1..n]中有n个数据，试建⽴⼀个带有头结点的循环链表，头指针为h，要求链中数据从⼩到⼤排列，重复的数据在链中只保存⼀个.5、设计⼀个尽可能的⾼效算法输出单链表的倒数第K个元素。
3、假设以I和O分别表⽰⼊栈和出栈操作。
栈的初态和终态均为空，⼊栈和出栈的操作序列可表⽰为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为⾮法序列。
（15分）（1）下⾯所⽰的序列中哪些是合法的？A. IOIIOIOOB. IOOIOIIOC. IIIOIOIOD. IIIOOIOO（2）通过对（1）的分析，写出⼀个算法，判定所给的操作序列是否合法。
若合法，返回true，否则返回false（假定被判定的操作序列已存⼊⼀维数组中）。
5、设从键盘输⼊⼀整数的序列：a1, a2, a3，…，an,试编写算法实现：⽤栈结构存储输⼊的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。
算法应对异常情况（⼊栈满等）给出相应的信息。
设有⼀个背包可以放⼊的物品重量为S，现有n件物品，重量分别为W1，W2，...，W n。
2015年考研必备资料2015年考研计算机数据结构试题及答案目录2015年考研计算机数据结构试题及答案（1） (2)2015年考研计算机数据结构试题（1） (2)2015年考研计算机数据结构试题答案（1） (5)2015年考研计算机数据结构试题及答案（2） (6)2015年考研计算机数据结构试题（2） (6)2015年考研计算机数据结构试题答案（2） (9)2015年考研计算机数据结构试题及答案（3） (11)2015年考研计算机数据结构试题（3） (11)2015年考研计算机数据结构试题答案（3） (13)2015年考研计算机数据结构试题及答案（4） (15)2015年考研计算机数据结构试题（4） (15)2015年考研计算机数据结构试题答案（4） (17)2015年考研计算机数据结构试题及答案（5） (19)2015年考研计算机数据结构试题（5） (19)2015年考研计算机数据结构试题答案（5） (21)2015年考研计算机数据结构试题及答案（1）2015年考研计算机数据结构试题（1）一、选择题(24分)1.下列程序段的时间复杂度为( )。
i=0，s=0; while (s(A) O(n1/2) (B) O(n1/3) (C) O(n) (D) O(n2)2.设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列( )存储方式最节省运算时间。
(A) 单向链表 (B) 单向循环链表(C) 双向链表 (D) 双向循环链表3.设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为( )。
(A) s->next=p->next;p->next=-s; (B) q->next=s; s->next=p;(C) p->next=s->next;s->next=p; (D) p->next=s;s->next=q;4.设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为( )。
数据结构复习样题答案一. 单项选择题1. B2. A3. A4. D5. C6. D7. B8. C二. 填空题9. 基本操作10. 从表中任一结点出发均可找到表中其他结点 11. 栈 12. 队尾13. 各结点均无左孩子三. 解答题17．后序线索; 后序遍历序列……省略18.已知一个长度为12的表为（Jan ，Feb ，Mar ，Apr ，May ，June ，July ，Aug ，Sep ，Oct ，Nov ，Dec ） （1） 试将表中元素依次插入到一棵初始为空的二叉排序树（字符串之间按字典顺序比较大小）。
画出该二叉排序树，并求出等概率情况下查找成功的平均查找长度。
（2） 设哈希表长度为13，哈希函数H （k ）= ⎣i/2⎦，其中i 为关键字k 中第一个字母在字母表中的序号（例如A 和D 的序号分别为1和4），用链地址法解决冲突。
请画出通过依次插入表中元素所构造的散列表，并求出在等概率情况下查找成功的平均查找长度。
19.假设电文中仅由a 到h 共8个字母组成，字母在电文中出现的频度依次为JanFebMarAprJune MayJulyAugSepOct NovDec成功的平均查找长度＝42/12成功的平均查找长度＝18/127，19，2，6，32，3，21，10请画出由此构造的哈夫曼树（要求树中所有结点的左右孩子必须是左大右小），并写出这8个字母相应的哈夫曼编码。
20.若对序列（25，19，7，41，29，12，23，26）按升序排序，请分别给出 （1） 步长为4的一趟希尔排序的结果； （2） 初始大根堆。
答：（1） （25，12，7，26，29，19，23，41） （2） （41，29，23，26，25，12，7，19）21.对于右边的带权图G ，请 （1） 画出G 的邻接矩阵；（2） 画出G 的最小生成树。
答：（1） （2）⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡∞∞∞∞072377098290638047640四. 算法题22．函数f22定义如下，其中函数调用Insert(L, i, k)在顺序表L的第i位置插入k。
2015年数据结构期末考试题及答案,推荐文档(word版可编辑修改) 编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（2015年数据结构期末考试题及答案,推荐文档(word版可编辑修改)）的内容能够给您的工作和学习带来便利。
同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。
本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快业绩进步，以下为2015年数据结构期末考试题及答案,推荐文档(word版可编辑修改)的全部内容。
2012年数据结构期末考试题及答案一、选择题1．在数据结构中，从逻辑上可以把数据结构分为 C 。
A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．内部结构和外部结构2．数据结构在计算机内存中的表示是指 A 。
A．数据的存储结构B．数据结构C．数据的逻辑结构 D．数据元素之间的关系3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。
A．逻辑B．存储C．逻辑和存储D．物理4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C .A．数据的处理方法B．数据元素的类型C．数据元素之间的关系D．数据的存储方法5．在决定选取何种存储结构时，一般不考虑 A 。
A．各结点的值如何B．结点个数的多少C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便.6．以下说法正确的是 D 。
A．数据项是数据的基本单位B．数据元素是数据的最小单位C．数据结构是带结构的数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构7．算法分析的目的是 C ，算法分析的两个主要方面是 A .（1）A．找出数据结构的合理性 B．研究算法中的输入和输出的关系C．分析算法的效率以求改进 C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度 B．正确性和简明性C．可读性和文档性 D．数据复杂性和程序复杂性8．下面程序段的时间复杂度是O(n2) 。
数据结构复习题及答案数据结构复习题及答案数据结构是计算机科学中的重要基础，它涉及到存储、组织和管理数据的方法和技术。
在学习数据结构的过程中，我们经常会遇到各种复习题，通过解答这些题目可以巩固对数据结构的理解和掌握。
本文将给出一些常见的数据结构复习题及其答案，希望对读者的学习有所帮助。
一、数组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分，共10分）1. _数据_即信息的载体，是对客观事物的符合表示，指能输入到计算机中并能被计算机程序处理的符合的总称。
2. 线性结构中元素之间存在_一对一_关系；树型结构中元素之间存在_一对多_关系；图型结构中元素之间存在_多对多_关系。
3. 在双向链表中，每个结点含有两个指针域，一个指向_直接前趋_结点，另一个指向_直接后继_结点。
4. 两个字符串相等的条件是两串长度相等和_各个对应位置的字符相等。
5. 对于一个有n个结点的二叉树，当它为一棵_完全_二叉树时具有最小高度，当它为一棵单支树具有最大高度，其最大高度为_n_。
二、选择题（每题2分，共24分）1.A2.B3.A4.A5.D6.C7.C8.D9.C 10.C 11.B 12.D三、判断题（每题1分，共10分）1.√2.×3.×4.×5.×6.×7.√8.√9.√ 10.×四、简答题（共16分）1．简述什么是数据结构，并说明有哪几类基本结构。
（7分）答：数据结构是数据元素的组织形式，或数据元素相互之间存在的一种或多种特定关系的集合。
（3分）数据结构有四类基本形式：集合、线性结构、树型结构和图状结构。
（4分）2．比较对一般线性表、栈和队列三种结构数据进行操作的不同之处？（9分）答：一般线性表可在表的任意位置进行插入和删除操作；（3分）栈限定仅在表的一端进行插入或删除操作，栈的修改是按“后进先出”的原则进行的；（3分）队列限定只能在表的一端进行插入，在表的另一端进行删除，是一种“先进先出”的线性表。
（3分）五、分析题（共40分）1. 已知一棵树边的集合为{<i，m>，<i，n>，<e，i>，<b，e>，<b，d>，<a，b>，<g，j>，<g，k>，<c，g>，<c，f>，<h，l>，<c，h>，<a，c>}，请画出这棵树，并回答下列问题：（12分）（1）哪个是根结点？ a (1分)（2）哪些是叶子结点？ d m n f j k l (1分)（3）哪个是结点f的双亲？ c (1分)（4）哪些是结点g的孩子？ j k (1分)（5）哪些是结点e的兄弟？ d (1分)（6）哪些是结点h的祖先？ a c (1分)（7）结点c的度是多少？ 3 (1分)（8）结点i的层次号分别是什么？ 4 (1分)（9）树的深度是多少？ 5 (1分)（10）以结点e为根的子树深度是多少？3 (1分)(2分) 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个特性。
（完整版）数据结构复习题目及答案数据结构 -C 语言版》第一章绪论单项选择题1．在数据结构中，数据的基本单位是 ________2．数据结构中数据元素之间的逻辑关系被称为__ ___ 。
A. 数据的存储结构B. 数据的基本操作C. 程序的算法3．在数据结构中，与所使用计算机无关的是数据的________ ___。
A. 存储结构B. 逻辑和物理结构C. 逻辑结构4．在链式存储结构中，数据之间的关系是通过 _______ ___ 体现的。
A. 数据在内存的相对位置B. 指示数据元素的指针C. 数据的存储地址D. 指针5．计算算法的时间复杂度是属于一种 ______ ___。
A. 事前统计的方法B. 事前分析估算的方法C. 事后统计的方法D. 事后分析估算的方法6．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是A. n 2B. nlognC. nD. logn 7.设使用某算法对 n 个元素进行处理，所需的时间是T(n)=100nlog 2n+200n+2000，则该算法的渐近时间复杂度为 _____ ___。
A. 数据项B. 数据类型C. 数据元素D. 数据变量D. 数据的逻辑结构D. 物理结构A. O(1)B. O(n)C. O(200n)D. O(nlog2n)CDCBBDD第二章线性表单项选择题1 ?链表不具有的特点是 __________ 。
A.可随机访问任一元素B.插入和删除时不需要移动元素C.不必事先估计存储空间D.所需空间与线性表的长度正比2.设顺序表的每个元素占 8个存储单元。
第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为 ______________ 。
3 ?在线性链表存储结构下，插入操作算法_______________ B. p_>next = p_>n ext;D. p = p->n ext; p->n ext = p->n ext- >n ext;5 .将长度为n 的单链表接在长度为 m 的单链表之后的算法时间复杂度为 __________________ A. 0( n)B. 0(1)C. 0(m)D. 0(m+n)6 ?需要预分较大空间，插入和删除不需要移动元素的线性表，其存储结构是 ________A.单链表B.静态链表C.线性链表D.顺序存储方式ACCABB 填空题1 ?在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的 ____ 结点。
《数据结构-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的单链表之后的算法时间复杂度为。
A. O(n) B. O(1) C. O(m) D. O(m+n)6．需要预分较大空间，插入和删除不需要移动元素的线性表，其存储结构是。
A. 单链表B. 静态链表C. 线性链表D. 顺序存储方式ACCABB填空题1．在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的_____结点。
2．在单链表中，指针p所指结点为最后一个结点的条件是。
3．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。
4．在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动元素的个数是。
5．在长度为n的顺序表中插入一个元素的时间复杂度为。
1前驱2 p->next==NULL3.14.n-i+15.O(n)例题解析【例2-1】 编写一个算法将一个单链表逆转，要求在原表上进行，不允许重新建链表。
解：该算法可以在遍历原表的时候将各结点的指针逆转，从原表的第一个结点开始，头结点的指针在最后修改成指向原表的最后一个结点，即新表的第一个结点。
实现本题功能的函数如下：void inverse(Lnode *h){s=h->next;if(s==NULL) return;q=NULL;p=s;while(p!=NULL){ p=p->next;s->next=q; /*逆转指针*/q=s; /*指针前移*/s=p;}h->next=q; /*头指针h 的后继是p*/}【例2-2】 编写一算法将两个按元素值递增有序排列的单链表A 和B 归并成一个按元素值递增有序排列的单链表C 。
解：对于两个或两个以上的，结点按元素值有序排列的单链表进行操作时，应采用“指针平行移动，依次扫描完成”的方法。
从两表的第一个结点开始顺链表逐个将对应数据元素进行比较，复制小的并插入c 表尾。
当两表中之一已到表尾，则复制另一个链表的剩余部分，插入到c 表尾。
设pa 、pb 分别指向两表当前结点，p 指向c 表的当前表尾结点。
若设A 中当前所指的元素为a ，B 中当前所指的元素为b ，则当前应插入到 C 中的元素c 为⎩⎨⎧>≤=ba bb a ac 例如：A=(3,5,8,11)B=(2,6,8,9,11,15,20)则 C=(2,3,5,6,8,8,9,11,11,15,20)实现本题功能的函数如下：Lnode *hb(Lnode *pa,Lnode *pb){Lnode *p,*q,*pc; pc=(Lnode*)malloc(sizeof(Lnode)); /*建立表c 的头结点pc*/p=pc; /*p指向C表头结点*/while(pa!=NULL&&pb!=NULL){q=(Lnode*)malloc(sizeof(Lnode)); /*建立新结点q*/if(pb->data<pa->data) /*比较A、B表中当前结点的数据域值的大小*/{q->data=pb->data; /*B中结点值小，将其值赋给q的数据域*/pb=pb->next; /*B中指针pb后移*/}else{q->data=pa->data; /*相反，将A结点值赋给q的数据域*/pa=pa->next; /*A中指针pa后移*/}p->next=q; /*将q接在p的后面*/p=q; /*p始终指向C表当前尾结点*/}while(pa!=NULL) /*若表A比B长，将A余下的结点链在C表尾*/{q=(Lnode*)malloc(sizeof(Lnode));q->data=pa->data;pa=pa->next;p->next=q;p=q;}while(pb!=NULL) /*若表B比A长，将B余下的结点链在C表尾*/{q=(Lnode*)malloc(sizeof(Lnode));q->data=pb->data;pb=pb->next;p->next=q;p=q;}p->next=NULL;p=pc; /*p指向表C的头结点pc*/pc=p->next; /*改变指针状态，使pc指向p的后继*/free(p); /*释放p空间*/return (pc);}此算法的时间复杂度为O(m+n)，其中m，n分别是两个被合并表的表长。
第三章栈和队列单项选择题1．在初始为空的堆栈中依次插入元素f，e，d，c，b，a以后，连续进行了三次删除操作，此时栈顶元素是。
A. ｃB.ｄC.ｂD. ｅ2．若某堆栈的输入序列是1，2，3，...，n，输出序列的第一个元素为n，则第i个输出元素为。
A. iB. n-iC. n-i+1D. 哪个元素无所谓3．向一个栈顶指针为h的带头结点链栈中插入指针s所指的结点时，应执行。
A. h->next = s;B. s->next = h;C. s->next = h; h = h->next;D. s->next = h->next; h->next=s;4．一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是。
A. edcbaB. decbaC. dceabD. abcde5．栈和队列的共同点是。
A. 都是先进后出B. 都是先进先出C. 只允许在端点处插入和删除元素D. 没有共同点6．对于循环队列。
A. 无法判断队列是否为空B. 无法判断队列是否为满C. 队列不可能满D. 以上说法都不是7. 若用一个大小为6的数组来实现循环队列，且当前队尾指针rear和队头指针front的值分别为0和3。
当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为。
A. 1和5B. 2和4C. 4和2D. 5和18. 判定一个循环队列QU（最多元素为m0）为满队列的条件是。
A. QU->front==QU->rearB. QU->front!=QU->rearC. QU->front==(QU->rear+1) % m0D. QU->front!=(QU->rear+1) % m09.判定一个循环队列QU（最多元素为m0）为空的条件是。
A. QU->front==QU->rearB. QU->front!=QU->rearC. QU->front==(QU->rear+1) % m0D. QU->front!=(QU->rear+1) % m0BCDCCDACA填空题1．在求表达式值的算符优先算法中使用的主要数据结构是。
2．设有一个空栈，现输入序列为1，2，3，4，5。
经过push，push，pop，push，pop，push，pop，push后，输出序列是。
3．仅允许在同一端进行插入和删除的线性表称为。
7．在顺序栈s中，栈为空的条件是，栈为满的条件是_____。
4．用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺序，相应的S 、X 操作串为 。
5．用一个大小为1000的数组来实现循环队列，当前rear 和front 的值分别为0和994，若要达到队满的条件，还需要继续入队的元素个数是 。
1.栈2. 2 3 43.栈4.s.top==s.base, s.top-s.base>=s.stacksize SXSSXSXX5.993例题解析【例3-1】 编程实现：用除法把十进制数转换成二进制数。
解：算法思想：用初始十进制数除以2把余数记录下来并且若商不为0则再用商去除以2直到商为0，这时把所有的余数按出现的逆序排列起来（先出现的余数排在后面，后出现的余数排在前面）就得到了相应的二进制数，如把十进制数35转换成二进制数的过程如图3-1所示。
图3-1 十进制数转换成二进制数的过程由题意可知，我们可以用一个栈来保存所有的余数，当商为0时则让栈里的所有余数出栈则可以得到正确的二进制数，算法可描述如下：void conversion(){Stack S;int n;InitStack(&S);printf("Input a number to convert:\n");scanf("%d",&n);if(n<0){printf("\nThe number must be over 0."); 35 17 8 4 2 1 0 1 1 0 0 1 余数 结果：10011return;}if(n==0) Push(S,0);while(n!=0){Push(S,n%2);n=n/2;}printf("the result is: ");while(!StackEmpty(*S)){printf("%d", Pop(S));}}}第四章串单项选择题1．串是一种特殊的线性表，其特殊性体现在。
