下载文档原格式
请将答案按序写在学校统一印制的专用答题卷上，写在本卷或自备纸上者一律不得分。
一．单项选择题(本题含25个小题，每个小题2分，计50分)二．综合应用题(含5个小题，每小题10分，计50分)1．设LinkList是链表存储结构，试分析下列算法的时间复杂度，并简述程序的主要功能。
void CrList( LinkList &L, int n ){LinkList p, q=L;for ( i =0; i<n; ++i ){p=( LinkList ) malloc( sizeof( int ) );q->next=p;p->data=rand( ); // rand( )：产生一个随机整数q=p;}p->next=NULL;} // 算法结束[参考答案]该算法的时间复杂度主要由for ( i = 0；i < n；++ i )命令决定(即主要由链表长度决定)，因此算法的时间复杂度为O(n)。
程序的主要功能：创建一个含有n个结点的线性链表L，其中数据元素由随机函数产生。
2．画出与下列两个已知遍历序列对应的一颗二叉树：先序遍历序列：A B G E K C F H J D中序遍历序列：G B K E A H F J C D[参考答案]3．已知无向图如下，试绘制一棵从A 点开始的广度优先生成树。
[参考答案]从A 点开始的一棵广度优先生成树如下(六种情况之一)： A →B →C →D 时：A →C →D →B 时：A →D →B →C 时：A →B →D →C 时：A →C →B →D 时：A →D →C →B 时：4．已知关键字集={ 19，23，55，11，30，47，28，38，15，51，42 }，表长m=7，哈希函数H(key)=key%7+1。
试给出由链表地址法产生的哈希地址和哈希链表示意图。
[参考答案]由链表地址法产生的哈希地址是：6，3，7，5，3，6，1，4，2，3，1哈希链表示意图如下：5．设n个整数存放在数组a中。
数据结构与算法设计课后习题及答案详解1. 习题一：数组求和题目描述：给定一个整数数组，编写一个函数来计算它的所有元素之和。
解题思路：遍历数组，将每个元素累加到一个变量中，最后返回累加和。
代码实现：```pythondef sum_array(arr):result = 0for num in arr:result += numreturn result```2. 习题二：链表反转题目描述：给定一个单链表，反转它的节点顺序。
解题思路：采用三指针法，依次将当前节点的下一个节点指向上一个节点，然后更新三个指针的位置，直到链表反转完毕。
代码实现：```pythonclass ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef reverse_list(head):prev = Nonecurr = headwhile curr:next_node = curr.nextcurr.next = prevprev = currcurr = next_nodereturn prev```3. 习题三：二叉树的层序遍历题目描述：给定一个二叉树，返回其节点值的层序遍历结果。
解题思路：采用队列来实现层序遍历，先将根节点入队，然后循环出队并访问出队节点的值，同时将出队节点的左右子节点入队。
代码实现：```pythonclass TreeNode:def __init__(self, val=0, left=None, right=None): self.val = valself.left = leftself.right = rightdef level_order(root):if not root:return []result = []queue = [root]while queue:level = []for _ in range(len(queue)):node = queue.pop(0)level.append(node.val)if node.left:queue.append(node.left)queue.append(node.right)result.append(level)return result```4. 习题四：堆排序题目描述：给定一个无序数组，使用堆排序算法对其进行排序。
《数据结构与算法》习题与答案（解答仅供参考）一、名词解释：1. 数据结构：数据结构是计算机存储、组织数据的方式，它不仅包括数据的逻辑结构（如线性结构、树形结构、图状结构等），还包括物理结构（如顺序存储、链式存储等）。
它是算法设计与分析的基础，对程序的效率和功能实现有直接影响。
2. 栈：栈是一种特殊的线性表，其操作遵循“后进先出”（Last In First Out, LIFO）原则。
在栈中，允许进行的操作主要有两种：压栈（Push），将元素添加到栈顶；弹栈（Pop），将栈顶元素移除。
3. 队列：队列是一种先进先出（First In First Out, FIFO）的数据结构，允许在其一端插入元素（称为入队），而在另一端删除元素（称为出队）。
常见的实现方式有顺序队列和循环队列。
4. 二叉排序树（又称二叉查找树）：二叉排序树是一种二叉树，其每个节点的左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值都大于该节点的值。
这种特性使得能在O(log n)的时间复杂度内完成搜索、插入和删除操作。
5. 图：图是一种非线性数据结构，由顶点（Vertex）和边（Edge）组成，用于表示对象之间的多种关系。
根据边是否有方向，可分为有向图和无向图；根据是否存在环路，又可分为有环图和无环图。
二、填空题：1. 在一个长度为n的顺序表中，插入一个新元素平均需要移动______个元素。
答案：(n/2)2. 哈希表利用______函数来确定元素的存储位置，通过解决哈希冲突以达到快速查找的目的。
答案：哈希（Hash）3. ______是最小生成树的一种算法，采用贪心策略，每次都选择当前未加入生成树且连接两个未连通集合的最小权重边。
答案：Prim算法4. 在深度优先搜索（DFS）过程中，使用______数据结构来记录已经被访问过的顶点，防止重复访问。
答案：栈或标记数组5. 快速排序算法在最坏情况下的时间复杂度为______。
单选题（每题 2 分，共20分）1. 对一个算法的评价，不包括如下（B ）方面的内容。
A．健壮性和可读性B．并行性C．正确性D．时空复杂度2. 在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( A )。
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. 对线性表，在下列哪种情况下应当采用链表表示？( B )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4. 一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 36. 若需要利用形参直接访问实参时，应将形参变量说明为（D ）参数。
A．值B．函数C．指针D．引用8. 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（A ）。
A．行号B．列号C．元素值D．非零元素个数10. 从二叉搜索树中查找一个元素时，其时间复杂度大致为(C )。
A. O(n)B. O(1)C. O(log2n)D. O(n2)二、运算题（每题6 分，共24分）1. 数据结构是指数据及其相互之间的_联系。
当结点之间存在M对N（M：N）的联系时，称这种结构为__图__。
2. 队列的插入操作是在队列的___尾_进行，删除操作是在队列的_首_进行。
3. 当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是___top==0___(要超出才为满)_______________。
4. 对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为___ O（1）__，在表尾插入元素的时间复杂度为___ O（n）___。
作业：1-1,7,8 2-1，2,4,7,9,11,13，19 3-2,3，7,8,13,144-3,9,13 5-1,2,6,8 5-1,2,6,7，8，12,14,17习题1 绪论1-1 名词解释：数据结构。
数据结构：相互之间存在一定关系的数据元素的集合1-2 数据结构的基本逻辑结构包括哪四种?⑴集合：数据元素之间就是“属于同一个集合”⑵线性结构：数据元素之间存在着一对一的线性关系⑶树结构：数据元素之间存在着一对多的层次关系⑷图结构：数据元素之间存在着多对多的任意关系1-3 数据结构一般研究的内容不包括( )。
(A) 集合的基本运算(B) 数据元素之间的逻辑关系(C) 在计算机中实现对数据元素的操作(D) 数据元素及其关系在计算机中的表示选D数据的逻辑结构、数据的存储结构、数据的运算1-4 算法包括哪五种特性?2. 算法的五大特性：√⑴输入：一个算法有零个或多个输入。
⑵输出：一个算法有一个或多个输出。
⑶有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
⑷确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。
⑸可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。
1-5 简述算法及其时间复杂度。
1.算法（Algorithm）:是对特定问题求解步骤的一种描述，是指令的有限序列。
算法复杂度(Algorithm Complexity)：算法占用机器资源的多少，主要有算法运行所需的机器时间和所占用的存储空间。
时间复杂度(Time Complexity)：算法运行所需要的执行时间，T(n)= O(f(n))。
空间复杂度(Space Complexity)：算法运行所需要的存储空间度量，S(n)= O(f(n))。
1-6 设数组A中只存放正数和负数。
试设计算法，将A中的负数调整到前半区间，正数调整到后半区间。
分析算法的时间复杂度。
A[n+1]For(int i=n-1,j=0;i>j;i--){If(a[i]>0) continue;Else {A[n]=A[i];A[i]=A[j];A[j]=A[n];J++;}}时间复杂度为O(n)1-7 将上三角矩阵A=(aij)n n 的非0元素逐行存于B[(n*(n+1)/2]中，使得B[k]=aij 且k=f1(i)+f2(j)+c (f1, f2不含常数项)，试推导函数f1, f2和常数c。
第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。
如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。
数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。
在有些情况下，数据元素也称为元素、结点、记录等。
数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。
数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。
例如，学生基本信息表中的学号、姓名、性别等都是数据项。
数据对象：是性质相同的数据元素的集合，是数据的一个子集。
例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。
逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。
因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
存储结构：数据对象在计算机中的存储表示，也称为物理结构。
抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。
具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。
2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。
答案：例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。
每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。
第一章1.数据结构研究的主要内容包括逻辑结构、存储结构和算法。
2.数据元素是数据的基本单位，数据项是数据的最小标示单位。
3.根据数据元素之间关系的不同，数据的逻辑结构可以分为集合、树形、线性、图状。
4.常见的数据存储结构有四种类型：顺序、链式、索引、散列。
5.可以从正确性、可读性、健壮性、高效性四方面评价算法的质量。
6.在一般情况下，一个算法的时间复杂度是问题规模的函数。
7.常见时间复杂度有：常数阶O（1）、线性阶O（n）、对数阶O（log2 n）、平方阶O（n²）和指数阶O（2ⁿ）。
通常认为，具有常数阶量级的算法是好算法，而具有指数阶量级的算法是差算法。
8.时间复杂度排序由大到小（n+2）！>2ⁿ＋²>（n+2）4次方>nlog2 n>100000.问答题：1.什么叫数据元素？数据元素是数据的基本单位，是数据这个集合的个体，也称为元素、结点、顶点、记录。
2.什么叫数据逻辑结构？什么叫数据存储结构？数据逻辑结构：指数据元素之间存在的固有的逻辑结构。
数据存储结构：数据元素及其关系在计算机内的表示。
3.什么叫抽象数据类型？抽象数据类型是指数据元素集合以及定义在该集合上的一组操作。
4.数据元素之间的关系在计算机中有几种表示方法？顺序、链式、索引、散列。
5.数据的逻辑结构与数据的存储结构之间存在着怎样的关系？相辅相成，不可分割。
6.什么叫算法？算法的性质有哪些？算法：求解问题的一系列步骤的集合。
可行性、有容性、确定性、有输入、有输出。
7.评价一个算法的好坏应该从哪几方面入手？正确性、可读性、健壮性、高效性。
第二章1.线性表中，第一个元素没有直接前驱，最后一个元素没有直接后继。
2.线性表常用的两种存储结构分别是顺序存储结构和链式存储结构。
3.在长度为n的顺序表中，插入一个新元素平均需要移动表中的n/2个元素，删除一个元素平均需要移动（n-1）/2个元素。
4.在长度为n的顺序表的表头插入一个新元素的时间复杂度为O（n），在表尾插入一个新元素的时间复杂度为O（1）。
第1章绪论习题1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。
3．简述逻辑结构的四种基本关系并画出它们的关系图。
4．存储结构由哪两种基本的存储方法实现？5．选择题（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．树B．字符串C．队D．栈6．试分析下面各程序段的时间复杂度。
（1）x=90; y=100;while(y>0)if(x>100){x=x-10;y--;}else x++;（2）for (i=0; i<n; i++)for (j=0; j<m; j++)a[i][j]=0;（3）s=0;for i=0; i<n; i++)for(j=0; j<n; j++)s+=B[i][j];sum=s;（4）i=1;while(i<=n)i=i*3;（5）x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;（6）x=n; //n>1y=0;while(x≥(y+1)* (y+1))y++;（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O（n2）（6）O(n)第2章线性表1．选择题（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。
2.3 课后习题解答2.3.2 判断题1．线性表的逻辑顺序与存储顺序总是一致的。
（×）2．顺序存储的线性表可以按序号随机存取。
（√）3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。
（×）4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。
（√）5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。
（×）6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。
（√）7．线性表的链式存储结构优于顺序存储结构。
（×）8．在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。
（√）9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。
（√）10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。
（×）11．静态链表既有顺序存储的优点，又有动态链表的优点。
所以它存取表中第i个元素的时间与i无关。
（×）12．线性表的特点是每个元素都有一个前驱和一个后继。
（×）2.3.3 算法设计题1．设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。
试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。
【提示】直接用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的相邻，不一定将向量和表示线性表长度的变量封装成一个结构体），因为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性，来确定插入元素的插入位置，后面的元素为它让出位置，（也可以从高下标端开始一边比较，一边移位）然后插入x ，最后修改表示表长的变量。
int insert (datatype A[],int *elenum,datatype x) /*设elenum为表的最大下标*/ {if (*elenum==arrsize-1) return 0; /*表已满，无法插入*/else {i=*elenum;while (i>=0 && A[i]>x) /*边找位置边移动*/{A[i+1]=A[i];i--;}A[i+1]=x; /*找到的位置是插入位的下一位*/(*elenum)++;return 1; /*插入成功*/}}时间复杂度为O(n)。
1. 数据元素是数据的基本单位，有些情况下也称为元素、结点、顶点、记录等。
2 何谓算法?它与程序有何区别?算法是解决某一特定类型问题的有限运算序列。
程序＝数据结构＋算法3. 算法分析是对一种算法所消耗的计算机资源的估算，其中包括计算机运行时间的长短和占据空间的大小。
4. 何谓频度、时间复杂度、空间复杂度？说明其含义。
算法中语句的重复次数称为该语句的频度。
时间复杂度是算法执行所需要的时间，也就是算法中每一个语句的执行次数乘以每一次执行所需的时间的总和。
空间复杂度是算法对空间占用的量度。
（一般在考虑空间复杂度时，只估算算法所需增添的辅助空间，而对问题中原始数据所占的空间，由于与算法无关，不予考虑。
）5. 时间复杂度的计算：语句2的频度为n-l，语句4的额度为(n-1)(2n+1)＝2n2-n-l，因此时间复杂度T(n)＝O(n2)。
语句3的频度为n，语句7的频度为n2，因此时间复杂度为T(n)＝O(n2)。
【解】语句3的频度不仅与n有关，而且和x及数组A中各分量的值有关。
这时通常考虑最坏的情况，由于while循环的最大次数为n-1，因此时间复杂度为T(n)＝O(n)。
i=1;while(i<=n)i=i*5;【解】设语句“i=i*5;”的频度为x，则5x<=n，x<=log5n，O(log5n)i=0;s=0;while(s<n){i++; s+=i;}【解】i=1,s=1i=2,s=1+2i=3,s=1+2+3,s就是对等差数列求和，因此s=i(i+1)/2<n，其中i就是循环语句的频度，因此O(n)6. 在一个具有n个结点的有序单链表中插入一个新结点，使得链表仍然有序，该算法的时间复杂度是( )A.O(log2n)B.O(1)C.O(n2)D.O(n)(D)7. 如果某线性表中最常用的操作是取第i个结点及其前驱，则采用（）存储方式最节省时间。
A.单链表B.双向链表C.单循环链表D.顺序表（D）8. 写出带头结点的双向循环链表L为空表的条件（假设结点包括data, next, prior三个域）：(L==L->Next) && (L==L->Prior)注：L->Next==L->Prior不行，因为表长为1时该条件也成立。
作业：1-1,7,8 2-1，2,4,7,9,11,13，19 3-2,3，7,8,13,14 4-3,9,13 5-1,2,6,8 5-1,2,6,7，8，12,14,17习题1 绪论1-1 名词解释：数据结构。
数据结构：相互之间存在一定关系的数据元素的集合1-2 数据结构的基本逻辑结构包括哪四种?⑴集合：数据元素之间就是“属于同一个集合”⑵线性结构：数据元素之间存在着一对一的线性关系⑶树结构：数据元素之间存在着一对多的层次关系⑷图结构：数据元素之间存在着多对多的任意关系1-3 数据结构一般研究的容不包括( )。
(A) 集合的基本运算(B) 数据元素之间的逻辑关系(C) 在计算机中实现对数据元素的操作(D) 数据元素及其关系在计算机中的表示选D数据的逻辑结构、数据的存储结构、数据的运算1-4 算法包括哪五种特性?2. 算法的五大特性：√⑴输入：一个算法有零个或多个输入。
⑵输出：一个算法有一个或多个输出。
⑶有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间完成。
⑷确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。
⑸可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。
1-5 简述算法及其时间复杂度。
1.算法（Algorithm）:是对特定问题求解步骤的一种描述，是指令的有限序列。
算法复杂度(Algorithm Complexity)：算法占用机器资源的多少，主要有算法运行所需的机器时间和所占用的存储空间。
时间复杂度(Time Complexity)：算法运行所需要的执行时间，T(n)= O(f(n))。
空间复杂度(Space Complexity)：算法运行所需要的存储空间度量，S(n)= O(f(n))。
1-6 设数组A中只存放正数和负数。
试设计算法，将A中的负数调整到前半区间，正数调整到后半区间。
分析算法的时间复杂度。
A[n+1]For(int i=n-1,j=0;i>j;i--){If(a[i]>0) continue;Else {A[n]=A[i];A[i]=A[j];A[j]=A[n];J++;}}时间复杂度为O(n)1-7 将上三角矩阵A=(aij)n n 的非0元素逐行存于B[(n*(n+1)/2]中，使得B[k]=aij 且k=f1(i)+f2(j)+c (f1, f2不含常数项)，试推导函数f1, f2和常数c。
k+1=1+2+3+…+(i-1)+jk=1/2*i*(i-1)+j-1;1-8 描述下列递归函数的功能。
int F(int m, int n){if (n>m) return F(n, m);else if (n==0) return m;else{r=m%n;return F(n, r);}}求m与n的最大公约数1-9 编写递归算法：0，m=0且n≥0g(m,n)=g(m-1, 2n)+n，m>0且n≥0double g(double m,double n){If(m==0&&n>=0)return 0;elsereturn g(m-1,2*n)+n;}1-10 将下列递归过程改写为非递归过程。
void test(int &s){int x;scanf (“%d”, &x);if (x==0) s=0;else{test(s);s+=x;}}习题2 表2-1 如果长度为n的线性表采用顺序存储结构存储，则在第i (1≤i≤n+1)个位置插入一个新元素的算法的时间复杂度为( )。
(A)O(1) (B) O(n) (C) O(nlog2n) (D) O(n2)B需要让线性表移动n+1-i个2-2 在一个有127个元素的顺序表中插入一个新元素，要求保持顺序表元素的原有(相对)顺序不变，则平均要移动( )个元素。
(A) 7 (B) 32 (C) 64 (D) 127C n/2+12-3 将关键字2，4，6，8，10，12，14，16依次存放于一维数组A[0...7]中，如果采用折半查找方法查找关键字，在等概率情况下查找成功时的平均查找长度为( )。
(A) 21/8 (B) 7/2 (C) 4 (D) 9/2A3,2,3,1,3,2,3,4公式法1*2^0+2*2^1+3*2^2+…+i*2^(n-1);2-4 已知顺序表L递增有序。
设计一个算法，将a和b插入L中，要求保持L 递增有序且以较高的效率实现。
先用折半查找法查询位置，然后移动void insert(int L[],int a,int b)//a<b{int i=0,p,q;n= length(L);//L现有长度//查找确定a、b的位置for(;i<n;i++){if( L[i]<=a&&(a<L[i+1]||i==n-1) ){p = i+1; //a的最终位置n++;break;}}for(;i<n;i++){if( L[i]<=b&&(b<L[i+1]||i==n-1) ){q = i+2; //b的最终位置n++;break;}}//移动元素，插入a，bfor(i=n+1;i>q;i--)L[i] = L[i-2];L[q] = b;//插入bfor(i=q-1;i>p;i--)L[i] = L[i-1];L[p] = a;//插入a}2-5 简单描述静态查找和动态查找的区别。
A 静态查找表只查找B、静态查找表不改变数据元素集合的数据元素C、动态查找表不只查找D、动态查找表还插入或删除集合的数据元素2-6 综合比较顺序表和链表。
(1)存储空间利用率高——只存储元素值。
(2)随机存取——可以通过计算来确定顺序表中第i个数据元素的存储地址Li = L0+(i-1)*m,其中，L0为第一个数据元素的存储地址，m为每个数据元素所占用的存储单元数。
(3)插入和删除数据元素会引起大量结点移动.顺序表：存中地址连续长度不可变更支持随机查找可以在O(1)查找元素适用于需要大量访问元素的而少量增添/删除元素的程序链表：存中地址非连续长度可以实时变化不支持随机查找查找元素时间复杂度O（n）适用于需要进行大量增添/删除元素操作而对访问元素无要求的程序2-7 解释链表的“头指针、头结点和首元素结点”三个概念。
“头指针”是指向头结点的指针。
"头结点"是为了操作的统一、方便而设立的，放在首元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等）。
“首元结点”也就是第一元素结点，它是头结点后边的第一个结点。
2-8 描述下列算法的主要功能是( )。
①构造头结点L，取q=L;②产生1个结点p;③q−>next=p;④输入p−>data的值;⑤取q=p;⑥重复执行②至⑤n次;⑦p−>next=NULL;(A) 通过输入n个数据元素构建链表L(B) 采用前插法，在链表L中输入n个数据元素(C) 通过产生n个结点构建链栈L，q为栈顶指针(D) 在链队列L中输入n个数据元素，q为队尾指针A2-9 设L是不带头结点的单链表的头指针，k是一个正整数，则下列算法的主要功能是( )。
LinkSearch (LinkList L, int k){k0=0;p=L->next; // next为单链表的指针域q=p;while ( p ){if (k0<=k) k0++;else q=q->next;p=p->next;}q->next=0;}(A) 计算单链表L的长度(B) 查找单链表L中倒数第k个结点(C) 删除单链表L中最后面的k个结点(D) 将单链表L中第k个结点q的指针置0只遍历一次的高效算法（排除法）B2-10 设链表L不带头结点，试分析算法的功能。
A(Linklist &L){if (L && L->next){Q=L;L=L->next;P=L;while (P->next) P=P->next;P->next=Q;Q->next=NULL;}} //A算法结束将链表的第一个结点接到最后一个结点后面2-11 设两个循环链表的长度分别为n和m，则将这两个循环链表连接成一个循环链表，最好的时间复杂度为( )。
(A) O(1) (B) O(n) (C) O(m) (D) O(min(n，m))A首先取一个指针p指向la的第一个节点（不包括头节点，头节点是空），然后让la头指针指向lb的第二个节点，接着用lb的第一个节点填充lb的头节点，最后将la头节点next指向p如下图：还是不明白请自己看ppt第二章P652-12 设有6个数据元素A，B，C，D，E，F依次进栈。
如果6个数据元素的出栈顺序为B，C，D，F，E，A，则该栈的最小容量为( )。
(A) 2 (B) 3 (C) 4 (D) 5B操作栈元素出栈顺序A，B入栈A,BB出栈 A BC入栈A,CC出栈 A B,CD入栈A,DD出栈 A B,C,DE,F入栈A,E,FF出栈A,E B,C,D,FE出栈 A B,C,D,F,EA出栈B,C,D,F,E,A因此栈的最小容量只需32-13 设进栈序列为123，试给出所有可能的出栈序列。
所有可能的出栈序列为：1,2,3 （1入栈，1出栈，2入栈，2出栈，3入栈，3出栈）1,3,2 （1入栈，1出栈，2,3,入栈，3出栈，2出栈）2,1,3 （1,2入栈，2出栈，1出栈，3入栈，3出栈）2,3,1 （1,2入栈，2出栈，3入栈，3出栈，1出栈）3,2,1 （1,2,3入栈，3出栈，2出栈，1出栈）注意：唯一只有3,1,2不可能出现，因为3要先出栈，前面1,2,3要按顺序一起入栈，因此不可能出现1在2的前面，后面的题目也是一样。
原则就是只要后入栈的先出栈，那么这个元素前面入栈的元素一定按照入栈顺序的反序排列2-14 如果进栈序列为123456，能否得到出栈序列435612和135426? 435612 不能得到6的后面不可能出现1,2的出栈顺序135426 能够得到2-15 简述算法的功能(设数据元素类型为int)：void proc(LinkQueue *Q){LinkStack S;InitStack(S);while(!EmptyQueue(Q) ){DeleteQueue(Q, d);Push(S,d);}while(!EmptyStack(S) ){Pop(S, d);InsertQueue(Q, d);}}将链队列中的顺序倒过来如原来ABCDEF，执行完这个算法之后是FEDCBA2-16 按照格式要求给出调用F(3,'A','B','C')的运行结果：void F(int n, char x, char y, char z){if (n==1) printf("1 %c %c\n", x, z);else{F(n-1, x, z, y);printf("%d %c %c\n", n, x, z);F(n-1, y, x, z);}}自己去计算，类似汉诺塔1 A->C2 A->B1 C->B3 A->C1 B->A2 B->C1 A->C2-17 已知一维数组B[0..20]用于存储一个下三角矩阵A元素。
