第一章 三、计算下列程序段中X=X+1 的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; [提示]：

i=1 时： 1 = (1+1)×1/2 = (1+1 )/2 i=2 时： 1+2 = (1+2)×2/2 = (2+22)/2 i=3 时： 1+2+3 = (1+3)×3/2 = (3+32)/2 ?

i=n时： 1+2+3+??+n = (1+n)×n/2 = (n+n )/2

f(n) = [ (1+2+3+……+n) + (1 + 2 + 3 + …… + n ) ] / 2 =[ (1+n)×n/2 + n(n+1)(2n+1)/6 ] / 2 =n(n+1)(n+2)/6 =n /6+n /2+n/3

区分语句频度和算法复杂度： O(f(n)) = O(n )

四、试编写算法求一元多项式Pn(x)=a +a x+a x +a x +?a x 的值P (x )，并确定算法中的每 一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能 使用求幂函数。注意：本题中的输入a (i=0,1,?,n), x和n，输出为P (x ).通常算法的输入和输出可采用下列两种方式之一：

（1）通过参数表中的参数显式传递； （2 ）通过全局变量隐式传递。

试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。 [提示]：float PolyValue(float a[ ], float x, int n) {??} 核心语句：

p=1; (x 的零次幂) s=0;

i 从0 到n 循环 s=s+a[i]*p; p=p*x; 或：

p=x; (x 的一次幂) s=a[0];

i 从 1 到n 循环 s=s+a[i]*p; p=p*x;

第二章

2.1 描述以下三个概念的区别：头指针，头结点，首元素结点。 2.2 填空：

（1） 在顺序表中插入或删除一个元素，需要平均移动 一半 元素，具体移动的元素个数与 插入或删除的位置 有关。

（2 ） 在顺序表中，逻辑上相邻的元素，其物理位置 相邻。在单链表中，逻辑上

相邻的元素，其物理位置 相邻。

（3） 在带头结点的非空单链表中，头结点的存储位置由 指示，首元素结点的存储位置由 指示，除首元素结点外，其它任一元素结点的存储位置由 其直接前趋的next 域 指示。

2.3 已知L 是无表头结点的单链表，且P 结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。

a. 在P结点后插入S结点的语句序列是： （4 ）、（1） 。 b. 在P结点前插入S结点的语句序列是： （7）、（11）、（8）、（4 ）、（1）。 c. 在表首插入S结点的语句序列是： （5）、（12）。 d. 在表尾插入S结点的语句序列是： （11）、（9）、（1）、（6）。 供选择的语句有： （1）P->next=S;

（2 ）P->next= P->next->next; （3）P->next= S->next; （4 ）S->next= P->next; （5）S->next= L;

（6）S->next= NULL; （7）Q= P;

（8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P;

2.4 已知线性表L 递增有序。试写一算法，将 X 插入到 L 的适当位置上，以保持线性表L的有序性。

[提示]：void insert(SeqList *L; ElemType x) < 方法 1 >

（1）找出应插入位置i，（2 ）移位，（3）?? < 方法2 > 参P. 229

2.5 写一算法，从顺序表中删除自第i 个元素开始的k 个元素。 [提示]：注意检查i 和k 的合法性。（集体搬迁，“新房”、“旧房”） < 方法 1 > 以待移动元素下标m（“旧房号”）为中心，计算应移入位置（“新房号”）： for ( m= i －1+k; m<= L－>last; m++) L －>elem[ m－k ] = L－>elem[ m ];

< 方法2 > 同时以待移动元素下标m 和应移入位置j 为中心： < 方法2 > 以应移入位置j 为中心，计算待移动元素下标：

2.6 已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink 且小于maxk 的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink 和maxk 是给定的两个参变量，它们的值为任意的整数）。 [提示]：注意检查mink 和maxk 的合法性：mink < maxk不要一个一个的删除（多次修改next 域）。

（1）找到第一个应删结点的前驱pre pre=L; p=L －>next;

while (p!=NULL && p －>data <= mink) { pre=p; p=p －>next; }

（2 ）找到最后一个应删结点的后继s，边找边释放应删结点 s=p;

while (s!=NULL && s－>data < mink) { t =s; s=s －>next; free(t); } （3）pre －>next = s;

2.7 试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a ..., a ）逆置为（a , a ,..., a ）。

（1） 以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum 个分量中。 （2 ） 以单链表作存储结构。 [方法 1]:在原头结点后重新头插一遍

[方法2]:可设三个同步移动的指针p, q, r，将q 的后继r 改为p

2.8 假设两个按元素值递增有序排列的线性表A 和B，均以单链表作为存储结构，请编写算法，将A 表和B 表归并成一个按元素值递减有序的排列的线性表 C，并要求利用原表（即A 表和B 表的）结点空间存放表 C. [提示]：参P.28 例2-1 < 方法 1 >

void merge(LinkList A; LinkList B; LinkList *C) { ……

pa=A －>next; pb=B－>next; *C=A; (*C)－>next=NULL; while ( pa!=NULL && pb!=NULL ) { if ( pa －>data <= pb－>data ) { smaller=pa; pa=pa－>next;

smaller－>next = (*C)－>next; /* 头插法 */ (*C) －>next = smaller; } else

{ smaller=pb; pb=pb－>next; smaller－>next = (*C)－>next; (*C) －>next = smaller; }

while ( pa!=NULL)

{ smaller=pa; pa=pa－>next; smaller －>next = (*C)－>next; (*C) －>next = smaller; }

while ( pb!=NULL)

{ smaller=pb; pb=pb－>next; smaller －>next = (*C)－>next; (*C) －>next = smaller; }

< 方法2 >

LinkList merge(LinkList A; LinkList B) { ……

LinkList C；

pa=A －>next; pb=B－>next; C=A; C－>next=NULL; ?? ??

return C;

2.9 假设有一个循环链表的长度大于 1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针 s 所指结点的前趋结点。 [提示]：设指针p 指向 s 结点的前趋的前趋，则p 与s 有何关系？

2.10 已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。

2.11 设线性表A=(a, a ,?,a )，B=(b, b ,?,b )，试写一个按下列规则合并A、B为线性表C的算法，使得：

C= (a , b ,?,a , b , b ?,b ) 当m≤n时； 或者 C= (a , b ,?,a , b , a ?,a ) 当m>n时。

线性表 A、B、C 均以单链表作为存储结构，且 C 表利用 A 表和 B 表中的结点空间构成。

注意：单链表的长度值m 和n 均未显式存储。

[提示]：void merge(LinkList A; LinkList B; LinkList *C) 或：LinkList merge(LinkList A; LinkList B)

2.12 将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间来构成这两个链表。 [提示]：注明用头指针还是尾指针。

2.13 建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的 data 域存放一个二进制位。并在此链表上实现对二进制数加 1 的运算 。 [提示]：可将低位放在前面。

2.14 设多项式P(x)采用课本中所述链接方法存储。写一算法，对给定的x 值，求P(x)的值。 [提示]：float PolyValue(Polylist p; float x) {??} 第三章

1. 按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：

⑴ 如进站的车厢序列为 123，则可能得到的出站车厢序列是什么？ 123、213、132、231、321 （312）

⑵如进站的车厢序列为 123456，能否得到435612 和 135426 的出站序列，并说明原因。（即 写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。 SXSS XSSX XXSX 或 S1X1S2S3X3S4S5X5X4X2S6X6

2. 设队列中有A、B、C、D、E 这 5 个元素，其中队首元素为A 。如果对这个队列重复执行下列4 步操作：

（1） 输出队首元素；

（2 ） 把队首元素值插入到队尾； （3） 删除队首元素；

（4 ） 再次删除队首元素。

直到队列成为空队列为止，则是否可能得到输出序列：

（1） A、C、E、C、C （2） A、C、E （3） A、C、E、C、C、C （4 ） A、C、E、C [提示]：

A、B、C、D、E （输出队首元素A ）

A、B、C、D、E、A （把队首元素A 插入到队尾） B、C、D、E、A （删除队首元素A ） C、D、E、A （再次删除队首元素B） C、D、E、A （输出队首元素C）

C、D、E、A、C （把队首元素C 插入到队尾） D、E、A、C （删除队首元素C） E、A、C （再次删除队首元素D ）

3. 给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？ 4. 按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程： A －B ＊Ｃ／Ｄ＋Ｅ↑Ｆ

5. 试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1&序列2’模式的字符序列。其中序列1 和序列2 中都不含字符’&’，且序列2 是序列 1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘１+ ３& ３－１’则不是。 [提示]：

（1） 边读边入栈，直到&

（2 ） 边读边出栈边比较，直到??

6. 假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式（中缀）且书写正确的表达式转换为逆波兰式（后缀）。 [提示]： 例：

中缀表达式：a+b 后缀表达式: ab+

中缀表达式：a+b×c 后缀表达式: abc×+ 中缀表达式：a+b×c-d 后缀表达式: abc×+d- 中缀表达式：a+b×c-d/e 后缀表达式: abc×+de/- 中缀表达式：a+b×(c-d)-e/f 后缀表达式: abcd-×+ef/- ? 后缀表达式的计算过程：（简便） 顺序扫描表达式，

（1） 如果是操作数，直接入栈；

（2 ） 如果是操作符op，则连续退栈两次，得操作数X, Y，计算X op Y，并将结果入栈。

? 如何将中缀表达式转换为后缀表达式？ 顺序扫描中缀表达式，

（1）如果是操作数，直接输出；

（2 ）如果是操作符op ，则与栈顶操作符op 比较： 如果op > op ，则op 入栈； 如果op = op ，则脱括号； 如果op < op ，则输出op ；

7. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设