一、填空题（每空1分）
1、组成数据的基本单位是（数据元素）。
2、栈和队列的共同点是（只允许在端点处插入和删除元素）。
3、算法设计的原则是（正确性）、（可读性）、（健壮性）及（高效率与存储量）。
4、ADT（Abstract Data Type），即称为（抽象数据类型），是指一个数学模型及定义在该模型上的
一组操作（运算）；ADT只考虑数据的（类型）。
5、算法分析的两个主要方面是（空间复杂性）和（时间复杂性）。
6、所有能输入到计算机中去的描述客观事物的符号，称为（数据）。
7、线性表a是n 个类型相同数据元素的有限序列，通常记作（a0,a1,...ai-1,ai,ai+1,...,an）。
8、若线性表第一个元素的存储地址是102，每个元素的长度为4，则第5个元素的地址是：(118)
9、在插入排序、选择排序、快速排序和归并排序等方法中，平均查找长度最小的是：（快速排序）
10、线性表的链式存储结构是用一组任意的存储单元存储线性表的各个数据元素。为了表示线性表中
元素的先后关系，每个元素除了需要存储自身的信息外还需保存（直接前驱元素）或（直接后继元素）的存储位置。
11、数据元素及直接后继的存储位置（地址）组成一个数据元素的存储结构，称为：
（指针域）。
12、线性结构中元素之间存在（一对一）关系,树形结构中元素之间存在（一对多）关系,图形结构中
元素之间存在（多对多）关系。
13、数据结构是研究数据的（物理结构）与（逻辑结构）以及它们之间的相互关系。
14、线性的数据结构包括：（线性表）、（栈）、（队列）、（数组）和（串）。
15、在一棵高度为k的满二叉树中，结点总数为（2k-1）。
16、判定一个栈ST(最多元素为m0)为栈满的条件是（ST—> top= =0）。
17、头结点是指：（在单链表的第一个结点之前附设一个结点），称为头结点。
18、在线性结构中,第一个结点（没有）前驱结点,其余每个结点有且只有（一个）个前驱结点；最后
一个结点（没有）后续结点,其余每个结点有且只有（一个）个后续结点。
19、在树形结构中,树根结点没有（前驱）结点,其余每个结点有且只有（一个）个前驱结点；叶子结
点没有（后继）结点,其余每个结点的后续结点可以（任意个）。
20、数据结构被形式地定义为（D, R），其中D是(数据元素)的有限集合，R是D上的关系有限集合。21．在各种查找方法中,平均查找长度与结点个数n无关的查法方法是（哈希表查找法）
第1页共页
22、哈夫曼树是带权路径长度最小的二叉树，又称最优二叉树。
23、数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。
二、选择题（每题1分）
1、树是结点的集合，它的根结点数目是A。
A)有且只有1 B)1或多于 C)0或1 D)至少2
2、线性表L=(a1，a2，a3，…ai，…an)，下列说法正确的是D。
A) 每个元素都有一个直接前件和直接后件 B) 线性表中至少要有一个元素
C) 表中诸元素的排列顺序必须是由小到大或由大到小
D) 除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接后件
3、栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列
可能是B。
A) ABCED B) DCBEA C) DBCEA D) CDABE
4、 n个顶点的连通图中边的条数至少为C。
A) 0 B) 1 C) n-1 D) n
5、在待排序的元素序列基本有序的前提下，效率最高的排序方法是A。
A) 冒泡排序 B) 选择排序 C) 快速排序 D) 归并排序
6、希尔排序属于D。
A) 交换排序 B) 归并排序 C) 选择排序 D) 插入排序
7、由３个结点所构成的二叉树有 D种形态。
A）3 B）2 C） 1 D）5
8、非空的循环单链表head的尾结点(由p所指向)，满足C。
A) p→next==NULL B) p==NULL C) p→next=head D) P=head
9、数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及
A 。
A)数据的存储结构 B)计算方法 C)数据映象 D)逻辑存储
10、 n个顶点的强连通图的边数至少有 C。
A) n-1 B) n(n-1) C) n D) n+l
11、循环链表的主要优点是B。
A) 不再需要头指针了 B) 从表中任一结点出发都能访问到整个链表
C) 在进行插入、删除运算时，能更好的保证链表不断开
D) 已知某个结点的位置后，能够容易的找到它的直接前件
12、栈和队列的共同特点是 C。
A)都是先进先出 B)都是先进后出
C)只允许在端点处插入和删除元素 D)没有共同点
13、己知一个有序表为(12,18,20,25,29,32,40,62,83,90,95,98)，当顺序查找值为29和90的元素
时，分别需要A次比较才能查找成功。
（A）5次和10次（B）10次和5次（C）5次和9次（D）10次和4次
14、设一棵完全二叉树具有1000个结点，则此完全二叉树有 D 个叶子结点，度为2的结点有C
个。
（A）1000 （B）501 （C） 499 （D）500 （E）0 （F）1
15、用链表表示线性表的优点是 C 。
A)便于随机存取 B)花费的存储空间较顺序存储少
C)便于插入和删除操作 D)数据元素的物理顺序与逻辑顺序相同
16、下列叙述中正确的是 A。
A) 线性表是线性结构 B) 栈与队列是非线性结构
C) 线性链表是非线性结构 D) 二叉树是线性结构
17、深度为5的满二叉树中，叶子结点的个数为C。
A)32 B)31 C)16 D)15
18、一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是 C 。
（A） edcba（B）decba（C）dceab （D）abcde
19、为了方便插入一个元素,数据结构宜用B结构。
（A）顺序存储（B）链式存储（C）指针存储（D）数组存储
20、拓扑排序算法是通过重复选择具有0个前驱顶点的过程来完成的。图的BFS生成树的树高比DFS
生成树的树高 A 。
（A）小或相等（B）大或相等（C）小或不相等（D）大或不相等
21、数据结构的三要素是指_ B__。
（A）数据元素、顺序存储、存储结构（B）数据元素、逻辑结构、存储结构
（C）顺序存储、链式存储、存储结构（D）数据元素、逻辑结构、链式存储
22、己知一个有序表为(12,18,20,25,29,32,40,62,83,90,95,98),当二分查找值为29和90的元素时,分别需
要_ C __比较才能查找成功。
（A）4次和2次（B）3次和4次（C）4次和4次（D）3次和5次
23、在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动_ A__个
元素。
（A）n－i+1 （B）n+i+1 （C）n－i （D） n+1
24、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行B
（A）s->next=p;p->next=s; （B） s->next=p->next;p->next=s;
（C）s->next=p->next;p=s; （D）p->next=s;s->next=p;
25、设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过
PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_B __。
（A）16 （B）23 （C） 28 （D）20
26、设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的元素，最好用_ B__ 排
序法。
（A）快速排序（B）堆排序（C）插入排序（D）选择排序
27、设有一批数据元素,为了最快的存储某元素,数据结构宜用_ A__结构,
（A）顺序存储（B）链式存储（C）指针存储（D）数组存储
28、一棵具有２５７个结点的完全二叉树，它的深度为_ D__。
（A）6 （B）7 （C） 8（D）9
29、一个有n个顶点的无向图最多有_C__条边。
（A）n(n-1) （B）n /2 （C） n(n-1)/2 （D） (n-1)/2
30、在计算机中，算法是指_B__
A)加工方法 B)解题方案的准确而完整的描述 C)排序方法 D)查询方法
31. 引入二叉线索树的目的是（A）
A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除
C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一
32．设无向图的顶点个数为n，则该图最多有（B）条边。
A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2
33．下面哪一方法可以判断出一个有向图是否有环（B）：
A．广度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径
34、设计一个判别表达式中左，右括号是否配对出现的算法，采用__D__数据结构最佳。
A．线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈
35、已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为__A__。A．CBEFDA B． FEDCBA C． CBEDFA D．不定
36、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：__C___
A. 存储结构
B. 逻辑结构
C. 顺序存储结构
D. 链式存储结构
37、广度优先遍历类似于二叉树的__D____ 。
A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历
38、以下与数据的存储结构无关的术语是__D___。
A．循环队列 B. 链表 C. 哈希表 D. 栈
39、设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 , 则T中的叶子数为__D___ A．5 B．6 C．7 D．8
三、判断题（正确在括号内打“√”，错的打“X”。）
1、线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻（X）
2、对任何数据结构链式存储结构一定优于顺序存储结构。(X)
3、有向图的邻接矩阵必定不是对称矩阵。(X)
4、归并排序要求内存量比较大。(√)
5、栈和链表是两种相同的数据结构。(√)
6、线性表在物理存储空间中也不一定是连续的。(√)
7、数据的逻辑结构是指数据在计算机内的实际存储形式。(X)
8、树的后根遍历序列等同于该树对应的二叉树的中序遍历。(√)
9、栈是实现过程和函数等子程序所必需的结构。(√)
10、栈和队列的存储方式只能是链接方式。（X）
11、线性表在物理存储空间中也一定是连续的。（X）
12、栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。(√)
13、二叉树是一般树的特殊情形。(√ )
14、栈和队列是一种非线性数据结构。(X)
15、一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。(√ )
16、在中序线索二叉树中，每一非空的线索均指向其祖先结点。(√ )
17、必须把一般树转换成二叉树后才能进行存储。(X)
18、二叉树的遍历只是为了在应用中找到一种线性次序。(√ )
19、由一棵二叉树的前序序列和后序序列可以唯一确定它。(X)
20、数据的物理结构是指数据在计算机内的实际存储形式。(√)
21、栈和链表是两种不同的数据结构。（X）
22、数据元素是数据的最小单位。(X)
23、二叉树中每个结点的两棵子树是有序的。（√）
24、集合与线性表的区别在于是否按关键字排序。(X)
25、顺序存储方式只能用于存储线性结构（X）。
26、程序一定是算法。(X)
27、一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。(√ )
28、链表中的头结点仅起到标识的作用。(X)
29、健壮的算法不会因非法的输入数据而出现莫名其妙的状态。(√)
30、一个图按广度优先搜索法遍历的结果是惟一的。(X)
四、简答题
1、数据结构是一门研究什么内容的学科？
答：数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象及对象间的关系和施加于对象的操作等的学科。
2、设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元
素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。
答：设数组元素A[i][j]存放在起始地址为Loc ( i, j ) 的存储单元中.
∵Loc ( 2, 2 ) = Loc ( 0, 0 ) + 2 * n + 2 = 644 + 2 * n + 2 = 676.
∴n= ( 676 - 2 - 644 ) / 2 = 15
∴Loc ( 3, 3 ) = Loc ( 0, 0 ) + 3 * 15 + 3 = 644 + 45 + 3 = 692.
3、在结点个数为n (n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分
支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？
答：结点个数为n时，高度最小的树的高度为2，有2层；
它有n -1个叶结点，1个分支结点；
高度最大的树的高度为n ,有n层；它有1个叶结点，n-1个分支结点。
4、用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？
答：设图的顶点个数为n(n>1),则邻接矩阵元素的个数为n2，即顶点个数的平方，与图的边数无关。
5、已知某图的邻接表，如何建立该图的邻接矩阵？
6、如果一棵树有n1个度为1的结点, 有n2个度为2的结点, … , nm个度为m的结点, 试问有多
少个度为0的结点? 试推导之。
答：总结点数n = n0 + n1 + n2 + … + nm
总分支数e = n-1 = n0 + n1 + n2 + … + nm-1
= m*nm + (m-1)*nm-1 + … + 2*n2 + n1
则有n0=1+0*n1+1*n2+2*n3+...(m-1)*nm
7、有n个顶点的无向连通图至少有多少条边？有n个顶点的有向强连通图至少有多少条边？试举例
说明
答：n个顶点的无向连通图至少有n-1条边,n个顶点的有向强连通图至少有n条边.例如: 特例情况是当n = 1时,此时至少有0条边.
8、简述分块查找算法的思想。
答：（1）首先查找索引表，索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。（2）然后在已确定的块中进行顺序查找由于块内无序，只能用顺序查找。9、什么是AOV网的关键路径？
答：用顶点表示活动，用弧表示活动间的优先关系的有向图，叫顶点表示活动的网，简称AOV 网，在AOV-网中路径长度最长的路径叫关键路径。
10、试分别找出满足以下条件的所有二叉树:
(1) 二叉树的前序序列与中序序列相同;
(2) 二叉树的中序序列与后序序列相同;
(3) 二叉树的前序序列与后序序列相同。
答：1) 二叉树的前序序列与中序序列相同：空树或缺左子树的单支树；
(2) 二叉树的中序序列与后序序列相同：空树或缺右子树的单支树；
(3) 二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。
11、数据结构与数据类型有什么区别？
答：“数据结构”这一术语有两种含义，一是作为一门课程的名称；二是作为一个科学的概念。
作为科学概念，目前尚无公认定义，一般认为，讨论数据结构要包括三个方面，一是数据的逻辑
结构，二是数据的存储结构，三是对数据进行的操作（运算）。而数据类型是值的集合和操作的集合，可以看作是已实现了的数据结构，后者是前者的一种简化情况。
12、一棵度为2的树与一棵二叉树有何区别？
答：一棵度为二的有序树与一棵二叉树的区别在于:有序树的结点次序是相对于另一结点而言的，如果有序树中的子树只有一个孩子时，这个孩子结点就无须区分其左右次序，而二叉树无论其孩子数是否为2，均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结点而言而是确定的。
13、对于有n个顶点的无向图，采用邻接矩阵表示，如何判断以下问题：图中有多少条边？任意两
个顶点i和j之间是否有边相连？任意一个顶点的度是多少？
答：1）若有n个非零值，则边为n/2条边。
（2）设邻接矩阵为A，若aij=1，则i,j有边直接相连；若aik=1，akj=1则经过k有边直接相连。
（3）统计以该点为行的非零元素个数。
14、求网的最小生成树有哪些算法？各适用于哪些情况？为什么？
答：有普里姆算法和克鲁斯卡尔算法。
1）普里姆算法的时间复杂度为O(n2),与网中的边无关，因此适用于求边稀疏的网的生成树。
2）克鲁斯卡尔算法恰恰相反，他的时间复杂度为O(e log e)(e为网中的边数)，因此它相对于普里姆算法而言，适合于求边稀疏的网的最小生成树。
15、简述顺序查找法，折半（二分）查找法和分块查找法对被查找表中元素中的要求。
答：1）顺序查找法：表中元素可以任意次序存入。
2）二分查找法：表中元素必须以关键字的大小递增或递减的次序有序列且顺序表存储。
3）分块查找法：表中元素块内的元素可以任意次序存放，但块与块之间必须以关键字的大小递增（或递减）存放，即前一块内所有元素的关键字都不能大（或小）于后一块内任何元素的关键字。
16、一棵高度为h的满k叉树有如下性质: 第h层上的结点都是叶结点, 其余各层上每个结点都有
k棵非空子树, 如果按层次自顶向下, 同一层自左向右, 顺序从1开始对全部结点进行编号, 试问:
(1) 各层的结点个数是多少?
(2) 编号为i的结点的父结点(若存在)的编号是多少?
(3) 编号为i的结点的第m个孩子结点(若存在)的编号是多少?
(4) 编号为i的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少?
答：(1) k i ( i = 0, 1, ……, h ) (2) ??
????-+k 2k i (3) ( i -1)*k + m + 1 (4) ( i -1 ) % k ≠ 0 或 k *k 2k i i ??????-+≤ 时有右兄弟，右兄弟为i + 1。 17、在单链表中设置头结点的作用是什么？
【答案】主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必
另作判断。另外，不论链表是否为空，链表头指针不变。
18、一个有序表是采用链式存储的，那么你能采用什么样的查找技术从该表中查找某个给定的关键
字？ 【答案】顺序查找法进行查找。
19、 给定一组权值: 23, 15, 66, 07, 11, 45, 33, 52, 39, 26, 58, 试构造一棵具有最小带权外
部路径长度的扩充4叉树, 要求该4叉树中所有内部结点的度都是4, 所有外部结点的度都是0。这棵扩充4叉树的带权外部路径长度是多少?
20、 设有序顺序表中的元素依次为017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765,
897, 908。试画出对其进行折半搜索时的二叉搜索树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。
ASL succ = 114
12234474514(***)+++= ASL unsucc = 115
34145915(*)+=
21、有一份电文中共使用5个字符：a、b、c、d、e，它们的出现频率依次为4、7、5、2、4，试画
出对应的哈夫曼树，并求出每个字符的哈夫曼编码
五、写出下列各题的构造过程：
1、已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则构造出此二叉树并写其后序
遍历的结果。
2、请画出下图所示的树所对应的二叉树。
3、设一棵二叉树的先序、中序遍历序列分别为
先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C
（1）画出这棵二叉树。
（2）画出这棵二叉树的后序线索树。
（3）将这棵二叉树转换成对应的树（或森林）。
4、已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二
叉树。
5、设无向网络图G的邻接矩阵的上三角部分如下表，请回答：
（1）画出该网络图；
（2）求该网络图的最小生成树(只要给出生成树即可)；
（3）给出从顶点V5出发深度优先搜索遍历该图的顶点序列（顶点标号小者优先）。
V1 V2 V3 V4 V5 V6 V7
V1 ∞18 ∞∞ 23 4 6
V2 ∞ 5 8 12 ∞∞
V3 ∞ 10 ∞∞∞
G: V4 ∞∞ 15 ∞
V5 ∞ 25 ∞
V6 ∞ 7
V7 ∞
6、假定用于通信的电文仅由8个字母c1, c2, c3, c4, c5, c6, 组成, 各字母在电文中出现的频率
分别为5, 25, 3, 6, 10, 11,。试为这6个字母设计不等长Huffman编码, 并给出该电文的总码数。
7、给定权值集合{15, 03, 14,20，02, 06, 09, 16, 17}, 构造相应的霍夫曼树, 并计算它的带权外
部路径长度。
8、设有数据逻辑结构为：
B = (K, R), K = {k1, k2, …, k9}
R={
（1）画出这个逻辑结构的图示。
（2）相对于关系R, 指出所有的开始结点和终端结点。
（3）分别对关系R中的开始结点，举出一个拓扑序列的例子。
（4）分别画出该逻辑结构的正向邻接表和逆向邻接表。
9、已知序列{503，61， 512，87，122，908，170，897，275}，请给出采用快速排序法对该序列作
升序排列时每一趟的结果。（5分）
10．已知一个无向图如下图所示，要求用普鲁姆算法算法生成最小树
11、请写出如下无向连通图的最小生成树，写出prim算法执行过程示意图。
12、对如下图所示的二叉树进行遍历，分别画出先序、中序、后序线索二叉树的逻辑表示图。
六、算法分析题
1、简述以下关于二叉树某操作的算法的功能和主要思想。
typedef struct BiTNode {
char data ; // 结点信息是字符
struct BiTNode *lchild,*rchild; // 左右孩子指针
} *BiTree;
Status xxxx (BiTree T, Status(*Visit)(char e))
{ TStack S; BiTree p; InitStack(S);
if(T) Push(S,T);
while (!StackEmpty(S)){
Pop(S,p); Visit(p->data);
if(p->lchild) Push(S,p->lchild);
if(p->rchild) Push(S,p->rchild);
} return OK;
}
2、一线性表存储在带头结点的双向循环链表中，L为头指针，算法如下。
说明该算法的功能。
void unknown (BNODETP *L)
{ …
p=L->next; q=p->next; r=q->next；
while (q!=L)
{ while (p!=L) && (p->data>q->data) p=p->prior；
q->prior->next=r；r->prior=q->prior；
q->next=p->next；q->prior=p；
p->next->prior=q；p->next=q; q=r；p=q->prior；
r=r->next;或r=q->next;
3、分析下列算法，并简述其功能。
void conversion( )
{ InitStack(s);
scanf(“%d”,&x);
while(x!=0) {
push(s, x% 8);
x=x/8;
}
while(! StackEmpty(s) ) //输出存放在栈中
{ x=pop(s);
printf(“%d”,x);
}
}
4、写出以下递归算法功能。
typedef struct BiTNode {
char data ; // 结点信息是字符
struct BiTNode *lchild,*rchild; // 左右孩子指针
} *BiTree;
Status exchangelr(BiTree &T) // 算法用函数名exchangelr 表示{BiTree p; // 临时工作指针叉树某操作的算法的功能和主要思想。...... // 待完成的若干语句；
}
Status exchangelr(BiTree &T) // 算法用函数名exchangelr 表示{BiTree p; // 临时工作指针
if(!T) return OK; // 待完成的若干语句；
else{ p = T->lchild;
T->lchild = T->rchild;
T->rchild = p;
exchangelr(T->lchild);
exchangelr(T->rchild);
}
}
5、简述以下两个算法的功能并指出这两个算法在算法思想上的主要区别是什么。
typedef struct {
ElemType *elem;
int length;
int listsize;
}SqList;
(1) Status DK1(SqList &a, int i, int k)
{int j, count;
if (i<1 || k<0 || i+k > a.length) return INFEASIBLE; //参数不合法 else {
for (count = 0; count < k; count++){
for (j = i; j < a.length; j++) a.elem[j-1] = a.elem[j];
a.length--;
}
}
return OK;
} // DK1
(2) Status DK2(SqList &a, int i, int k)
{ int count;
if (i<1 || k<0 || i+k > a.length) return INFEASIBLE; // 参数不合法 else {
for (count = 0; count < a.length-(i+1); count++){
a.elem[i-1+count] = a.elem[i+k-1+count];
}
a.length -= k;
}
return OK;
} // DK2
6、简述以下算法的功能
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
pa=La->next; pb=Lb->next;
Lc=pc=La; //用La的头结点作为Lc的头结点
while (pa && pb){
if (pa->data<=pb->data){
pc->next=pa; pc=pa; pa=pa->next;
}
else {pc->next=pb; pc=pb; pb=pb->next;}
}
pc->next=pa?pa:pb; //插入剩余段
free(Lb); //释放Lb的头结点
}//MergeList_L
7、求下列算法段的语句频度及时间复杂度
for(i=1; i<=n; i++)
for(j =1; j <=i ; j++)
x=x+1;
8、分析下列算法段的时间频度及时间复杂度
for （i=1;i<=n;i++）
for (j=1;j<=i;j++)
for ( k=1;k<=j;k++)
x=i+j-k;
七、算法设计题(每题5分 )
1、若由键盘输入若干个整数，请写出按输入数据逆序建立一个带头结点的单链表的算法。
2、已知一个顺序存储的线性表的元素非递减有序排列，设计一个算法删除表中多余的值相同的元素
的算法。
3、有一个线性链表，其头指针为head，试编写一个函数计算数据域为X的结点个数。
4、设有一个由正整数组成的无序单链表，下列算法实现下列功能：
(1)、找出最小值结点，且打印该数值
（2）、若该数值是奇数则将其与直接后继结点的数值交换
（3）、若该数值是偶数则将其直接后继结点删除。
5、设从键盘输入一整数的序列：a1, a2, a3，…，a n,试编写算法实现：用栈结构存储输入的整数，当
a i≠-1时，将a i进栈；当a i=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出
相应的信息。