第一章三、计算下列程序段中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+12)/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+n2)/2
f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2
=[ (1+n)×n/2 + n(n+1)(2n+1)/6 ] / 2
=n(n+1)(n+2)/6
=n3/6+n2/2+n/3
区分语句频度和算法复杂度：
O(f(n)) = O(n3)
四、试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能使用求幂函数。注意：本题中的输入ai(i=0,1,…,n),x和n，输出为Pn(x0).通常算法的输入和输出可采用下列两种方式之一：
通过参数表中的参数显式传递；
通过全局变量隐式传递。
试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。
[提示]：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;
第二章描述以下三个概念的区别：头指针，头结点，首元素结点。
填空：
在顺序表中插入或删除一个元素，需要平均移动＿＿一半＿＿元素，具体移动的元素个数与＿＿插入或删除的位置＿＿有关。
在顺序表中，逻辑上相邻的元素，其物理位置＿＿＿＿＿＿相邻。在单链表中，逻辑上相邻的元素，其物理位置＿＿＿＿＿＿相邻。
在带头结点的非空单链表中，头结点的存储位置由＿＿＿＿＿＿指示，首元素结点的存储位置由＿＿＿＿＿＿指示，除首元素结点外，其它任一元素结点的存储位置由＿＿其直接前趋的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域）。
找到第一个应删结点的前驱pre
pre=L; p=L－>next;
while (p!=NULL && p－>data <= mink)
{ pre=p; p=p－>next; }
找到最后一个应删结点的后继s，边找边释放应删结点
s=p;
while (s!=NULL && s－>data < mink)
{ t =s; s=s－>next; free(t); }
pre－>next = s;
2.7试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1,a2...,an）逆置为（an,an-1,...,a1）。
以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。
以单链表作存储结构。
[方法1]:在原头结点后重新头插一遍
[方法2]:可设三个同步移动的指针p,q,r，将q的后继r改为p
假设两个按元素值递增有序排列的线性表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;
假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前趋结点。
[提示]：设指针p指向s结点的前趋的前趋，则p与s有何关系？
2.10 已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。
2.11 设线性表A=(a1,a2,…,am)，B=(b1,b2,…,bn)，试写一个按下列规则合并A、B为线性表C的算法，使得：
C= (a1,b1,…,am,bm,bm+1,…,bn) 当m≤n时；
或者 C= (a1,b1,…,an,bn,an+1,…,am) 当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) {……}
第三章按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：
⑴ 如进站的车厢序列为123，则可能得到的出站车厢序列是什么？ 123、213、132、231、321（312）
⑵如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。
SXSS XSSX XXSX 或 S1X1S2S3X3S4S5X5X4X2S6X6
设队列中有A、B、C、D、E这5个元素，其中队首元素为A。如果对这个队列重复执行下列4步操作：
输出队首元素；
把队首元素值插入到队尾；
删除队首元素；
再次删除队首元素。
直到队列成为空队列为止，则是否可能得到输出序列：
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）
给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？
按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：
A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ
试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1 & 序列2’模式的字符序列。其中序列1和序列2 中都不含字符’&’，且序列2 是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。
[提示]：
边读边入栈，直到&
边读边出栈边比较，直到……
假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式（中缀）且书写正确的表达式转换为逆波兰式（后缀）。
[提示],
例：
中缀表达式：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/-
后缀表达式的计算过程：（简便）
顺序扫描表达式，
如果是操作数，直接入栈；
如果是操作符op，则连续退栈两次，得操作数X,Y，计算X op Y，并将结果入栈。
如何将中缀表达式转换为后缀表达式？
顺序扫描中缀表达式，
（1）如果是操作数，直接输出；
（2）如果是操作符op2，则与栈顶操作符op1比较：
如果op2 > op1，则op2入栈；
如果op2 = op1，则脱括号；
如果op2 < op1，则输出op1；
假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。
[提示],参P.56 P.70 先画图.
typedef LinkList CLQueue;
int InitQueue(CLQueue * Q)
int EnterQueue(CLQueue Q,QueueElementType x)
int DeleteQueue(CLQueue Q,QueueElementType *x)
要求循环队列不损失一个空间全部都能得到利用,设置一个标志域tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。
[提示],
初始状态：front==0,rear==0,tag==0
队空条件：front==rear,tag==0
队满条件：front==rear,tag==1
其它状态：front !=rear,tag==0（或1、2）
入队操作：
…
…（入队）
if (front==rear) tag=1；（或直接tag=1）
出队操作：
…
…（出队）
tag=0；
[问题]：如何明确区分队空、队满、非空非满三种情况？
简述以下算法的功能（其中栈和队列的元素类型均为int）：
（1）void proc_1(Stack S)
{ int i,n,A[255];
n=0;
while(!EmptyStack(S))
{n++; Pop(&S,&A[n]);}
for(i=1; i<=n; i++)
Push(&S,A[i]);
}
将栈S逆序。
（2）void proc_2(Stack S,int e)
{ Stack T; int d;
InitStack(&T);
while(!EmptyStack(S))
{ Pop(&S,&d);
if (d!=e) Push( &T,d);
}
while(!EmptyStack(T))
{ Pop(&T,&d);
Push( &S,d);
}
}
删除栈S中所有等于e的元素。
（3）void proc_3(Queue *Q)
{ Stack S; int d;
InitStack(&S);
while(!EmptyQueue(*Q))
{
DeleteQueue(Q,&d);
Push( &S,d);
}
while(!EmptyStack(S))
{ Pop(&S,&d);
EnterQueue(Q，d)
}
}
将队列Q逆序。
第四章
1,设s=’I AM A STUDENT’,t=’GOOD’,q=’WORKER’。给出下列操作的结果：
StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1);
StrIndex(s,’A’,4); StrReplace(s,’STUDENT’,q);
StrCat(StrCat(sub1,t),StrCat(sub2,q));
[参考答案]
StrLength(s)=14; sub1= ’I AM A_’; sub2= ’_’; StrIndex(s,’A’,4)=6;
StrReplace(s,’STUDENT’,q)= ’I AM A WORKER’;
StrCat(StrCat(sub1,t),StrCat(sub2,q))= ’I AM A GOOD WORKER’;
2,编写算法，实现串的基本操作StrReplace(S,T,V)。
3,假设以块链结构表示串，块的大小为1，且附设头结点。
试编写算法，实现串的下列基本操作：
StrAsign(S,chars)； StrCopy(S,T)； StrCompare(S,T)； StrLength(S)； StrCat(S,T)； SubString(Sub,S,pos,len)。
[说明]：用单链表实现。
叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。
已知：S=”(xyz)*”,T=”(x+z)*y”。试利用联接、求子串和置换等操作，将S转换为T.
S和T是用结点大小为1的单链表存储的两个串，设计一个算法将串S中首次与T匹配的子串逆置。
S是用结点大小为4的单链表存储的串,分别编写算法在第k个字符后插入串T，及从第k个字符删除len个字符。
以下算法用定长顺序串：
写下列算法：
将顺序串r中所有值为ch1的字符换成ch2的字符。
将顺序串r中所有字符按照相反的次序仍存放在r中。
从顺序串r中删除其值等于ch的所有字符。
从顺序串r1中第index 个字符起求出首次与串r2相同的子串的起始位置。
从顺序串r中删除所有与串r1相同的子串。
写一个函数将顺序串s1中的第i个字符到第j个字符之间的字符用s2串替换。
[提示]：（1）用静态顺序串 （2）先移位，后复制写算法，实现顺序串的基本操作StrCompare(s,t)。
写算法，实现顺序串的基本操作StrReplace(&s,t,v)。
[提示]：
被替换子串定位（相当于第9题中i）
被替换子串后面的字符左移或右移（为替换子串准备房间）
替换子串入住（复制）
重复上述，直到……
第五章假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址。已知A的基地址为1000，计算：
数组A共占用多少字节； （288）
数组A的最后一个元素的地址； （1282）
按行存储时，元素A36的地址； （1126）
按列存储时，元素A36的地址； （1192）
[注意]：本章自定义数组的下标从1开始。
2,设有三对角矩阵（aij）n×n,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得B[k]= aij,求：
用i,j表示k的下标变换公式；
用k表示i,j的下标变换公式。
i = k/3 + 1,j = k%3 + i - 1 = k%3 + k/3
或：
i = k/3 + 1,j = k - 2×( k/3 )
假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放结果矩阵。
[提示]：参考P.28例、P.47例。
4．在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个辅助向量空间。
5．写一个在十字链表中删除非零元素aij的算法。
[提示]：“删除”两次，释放一次。
6．画出下面广义表的两种存储结构图示：
((((a),b)),((( ),d),(e,f)))
7．求下列广义表运算的结果：
HEAD[((a,b),(c,d))];
TAIL[((a,b),(c,d))];
TAIL[HEAD[((a,b),(c,d))]];
HEAD[TAIL[HEAD[((a,b),(c,d))]]]; b
TAIL[HEAD[TAIL[((a,b),(c,d))]]]; (d)
第六章
1．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
2．对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。
3．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，nk个度为k的结点，则该树中有多少个叶子结点？
[提示]：参考 P.116 性质3
∵ n=n0 + n1 + …… + nk
B=n1 + 2n2 + 3n3 + …… + knk
n= B + 1
∴ n0 + n1 + …… + nk = n1 + 2n2 + 3n3 + …… + knk + 1
∴ n0 = n2 + 2n3 + …… + (k-1)nk + 1
4.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。
[提示]：参考 P.148
已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？
[提示]：一个叶子结点，总结点数至多有多少个？可压缩一度结点。
给出满足下列条件的所有二叉树：
前序和中序相同中序和后序相同前序和后序相同
[提示]：去异存同。
D L R 与L D R 的相同点：D R，如果无 L，则完全相同,如果无 LR，…。
L D R 与L R D 的相同点：L D，如果无 R，则完全相同。
D L R 与L R D 的相同点：D，如果无 L R，则完全相同。
（如果去D，则为空树）
7,n个结点的K叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的Child域有多少个？
[提示]：参考 P.119
8．画出与下列已知序列对应的树Ｔ：
树的先根次序访问序列为GFKDAIEBCHJ；
树的后根次序访问序列为DIAEKFCJHBG。
[提示]：
（1）先画出对应的二叉树
（2）树的后根序列与对应二叉树的中序序列相同
9．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为：
0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10
（1）请为这8个字母设计哈夫曼编码，
（2）求平均编码长度。
10．已知二叉树采用二叉链表存放,要求返回二叉树T的后序序列中的第一个结点的指针,是否可不用递归且不用栈来完成?请简述原因.
[提示]：无右子的“左下端”
11,画出和下列树对应的二叉树：
12．已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。
13．编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。
[提示]：
[方法1]：（1）按先序查找；（2）超前查看子结点（3）按后序释放；
void DelSubTree(BiTree *bt,DataType x)
{
if ( *bt != NULL && (*bt) ->data==x )
{ FreeTree(*bt);
*bt =NULL;
}
else DelTree( *bt,x)
void DelTree(BiTree bt,DataType x)
{ if ( bt )
{ if (bt->LChild && bt->LChild->data==x)
{ FreeTree(bt->LChild);
bt->LChild=NULL;
}
if (bt->RChild && bt->RChild->data==x)
{ FreeTree(bt->RChild);
bt->RChild=NULL;
}
DelTree(bt->LChild,x);
DelTree(bt->RChild,x);
}
}
[方法2]：（1）先序查找；（2）直接查看当前根结点（3）用指针参数；
[方法3]：（1）先序查找；（2）直接查看当前根结点
（3）通过函数值，返回删除后结果；
（参示例程序）
14．分别写函数完成：在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。
[提示]：
（1）先查看线索，无线索时用下面规律：
（2）结点*p在先序序列中的后继为其左子或右子；
（3）结点*p在后序序列中的前驱也是其左子或右子。
15．分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。（参例题）
16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。
[提示]：
（1）可将孩子-兄弟链表划分为根、首子树、兄弟树，递归处理。
（2）可利用返回值，或全局变量。
17．对以孩子-兄弟链表表示的树编写计算树的深度的算法。
18．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出后序遍历非递归的算法。 （参课本）
19．设二叉树按二叉链表存放，写算法判别一棵二叉树是否是一棵正则二叉树。正则二叉树是指：在二叉树中不存在子树个数为1的结点。
[提示]：可利用任何递归、非递归遍历算法。
20．计算二叉树最大宽度的算法。二叉树的最大宽度是指：二叉树所有层中结点个数的最大值。
[提示]：
[方法一]：
（1）利用队列，初值为根
（2）出队访问，并将左、右子入队，直到队空
（3）记录每一层中最后一个结点在队中的位置
（4）第i层最后一个结点的右子，必是第i+1层的最后一个结点
（5）第1层最后一个结点在队中的位置为0
[方法二]：利用层号和全局数组，任意遍历、统计
21．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。
22,证明：给定一棵二叉树的前序序列与中序序列，可唯一确定这棵二叉树；
给定一棵二叉树的后序序列与中序序列，可唯一确定这棵二叉树；
23,二叉树按照二叉链表方式存储，编写算法将二叉树左右子树进行交换。
第七章已知如图所示的有向图，请给出该图的：
每个顶点的入度、出度；
邻接矩阵；
邻接表；
逆邻接表；
十字链表；
强连通分量。
已知如图所示的无向图，请给出该图的：
邻接多重表；（要求每个边结点中第一个顶点号小于第二个顶点号，且每个顶点的各邻接边的链接顺序，为它所邻接到的顶点序号由小到大的顺序。）
从顶点1开始，深度优先遍历该图所得顶点序列和边的序列；（给出深度优先搜索树）
从顶点1开始，广度优先遍历该图所得顶点序列和边的序列。（给出广度优先搜索树）
已知如图7.31所示的AOE-网，试求：
每个事件的最早发生时间和最晚发生时间；
每个活动的最早开始时间和最晚开始时间；
给出关键路径。
已知如图7.30所示的有向网，试利用Dijkstra算法求顶点1到其余顶点的最短路径，并给出算法执行过程中各步的状态。
编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。
[参例题]
试在邻接矩阵存储结构上实现图的基本操作：InsertVertex(G,v); InsertArc(G,v,w); DeleteVertex(G,v)和DeleteArc(G,v,w)。
试对邻接表存储结构重做题6。
试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中，是否存在由顶点vi到顶点vj的路径（i≠j）。注意：算法中涉及的图的基本操作必须在此存储结构上实现。
同上题要求。试基于图的广度优先搜索策略写一算法。
试利用栈的基本操作，编写按深度优先策略遍历一个强连通图的、非递归形式的算法。算法中不规定具体的存储结构，而将图Graph看成是一种抽象数据类型。
采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径（指顶点序列中不含有重现的顶点）的算法。
[提示]：利用深度搜索，增设一个深度参数，深度超过k 则停止对该结点的搜索。
下图是带权的有向图G的邻接表表示法。从结点V1出发，深度遍历图G所得结点序列为（ A ），广度遍历图G所得结点序列为（ B ）；G的一个拓扑序列是（ C ）；从结点V1到结点V8的最短路径为（ D ）；从结点V1到结点V8的关键路径为（ E ）。
其中A、B、C的选择有：
V1,V2,V3,V4,V5,V6,V7,V8
V1,V2,V4,V6,V5,V3,V7,V8
V1,V2,V4,V6,V3,V5,V7,V8
V1,V2,V4,V6,V7,V3,V5,V8
V1,V2,V3,V8,V4,V5,V6,V7
V1,V2,V3,V8,V4,V5,V7,V6
V1,V2,V3,V8,V5,V7,V4,V6
D、E的选择有：
V1,V2,V4,V5,V3,V8
V1,V6,V5,V3,V8
V1,V6,V7,V8
V1,V2,V5,V7,V8
第八章
8.1 若对大小均为n的有序的顺序表和无序的顺序表分别进行查找，试在下列三种情况下分别讨论两者在等概率时的平均查找长度是否相同？
查找不成功，即表中没有关键字等于给定值K的记录。
查找成功，且表中只有一个关键字等于给定值K的记录。
查找成功，且表中有若干个关键字等于给定值K的记录，一次查找要求找出所有记录。
[提示]：均用顺序查找法。
画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。
[提示]：根据P.191 ASL定义计算平均查找长度。
试推导含12个结点的平衡二叉树的最大深度并画出一棵这样的树。
[提示]：沿最左分支生长，前提是：其任一祖先的右分支与左分支等深，如不等深，则先生长右分支，而生长右分支的前提是：其任一祖先的左分支与右分支等深，如不等深，则先生长左分支，如此交互考虑，逐步生长，直到12个结点。
试从空树开始，画出按以下次序向2-3树，即3阶B-树中插入关键码的建树过程：20，30，50，52，60，68，70。如果此后删除50和68，画出每一步执行后2-3树的状态。
选取哈希函数H(k)=(3k)%11，用线性探测再散列法处理冲突。试在0～10的散列地址空间中，对关键字序列（22，41，53，46，30，13，01，67）构造哈希表，并求等概率情况下查找成功与不成功时的平均查找长度。
[提示]：平均查找长度参考P.225。
0
1
2
3
4
5
6
7
8
9
10
22
41
30
01
53
46
13
67
1
1
2
2
1
1
2
6
ASLsucc = (1×4 + 2×3 + 6) / 8 = 2
ASLunsucc = ( 2 + 1 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 1 ) / 11 = 40 / 11
试为下列关键字建立一个装载因子不小于0.75的哈希表，并计算你所构造的哈希表的平均查找长度。
（ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG，CHANG，CHAO，YANG，JIN）
[提示]：（1）由装填因子求出表长，（2）可利用字母序号设计哈希函数，
（3）确定解决冲突的方法。
试编写利用折半查找确定记录所在块的分块查找算法。
试写一个判别给定二叉树是否为二叉排序树的算法。设此二叉树以二叉链表作存储结构，且树中结点的关键字均不同。
[提示]：检验中序遍历序列是否递增有序？
[方法1]：用非递归中序遍历算法，设双指针pre,p
一旦pre->data > p->data 则返回假
[方法2]：用递归中序遍历算法，设全局指针pre，（参中序线索化算法）
一旦pre->data > p->data 则返回假
[方法3]：用递归（中序或后序）算法
（1）空树是（2）单根树是（3）左递归真（4）右递归真
（5）左子树的右端小于根（6）右子树的左端大于根
编写算法，求出指定结点在给定的二叉排序树中所在的层数。
8.10 编写算法，在给定的二叉排序树上找出任意两个不同结点的最近公共祖先（若在两结点A、B中，A是B的祖先，则认为A是A、B的最近公共祖先）。
[提示]：
假设A<=B，
从根开始，左走或右走，直到A在左（或根），B在右（或根）。
8.11 编写一个函数，利用二分查找算法在一个有序表中插入一个元素x，并保持表的有序性。
[提示]：（1）表中已经有x，（2）表中没有x
参P,231
8.12 已知长度为12的表：
（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）。
试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树并求其等概率的情况下查找成功的平均查找长度。
若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。
按表中元素的顺序依次构造一棵平衡二叉排序树，并求其等概率的情况下查找成功的平均查找长度。
[提示]：画出判定树或排序树，根据P.191 ASL定义计算平均查找长度。
8.13 含有9个叶子结点的3阶B-树中至少有多少个非叶子结点？含有10个叶子结点的3阶B-树中至少有多少个非叶子结点？
[提示]：叶子结点对应空指针。
8.14 写一时间复杂度为O(log2n + m)的算法，删除二叉排序树中所有关键字不小于x的结点，并释放结点空间。其中n为树中的结点个数，m为被删除的结点个数。
[提示]：
p=root
如果p->key大于、等于x，则删除p->rchild和p，
左走一步，转（2）
如果p->key小于x，则反复右走，
转（2）
直到p==NULL
8.15 在平衡二叉排序树的每个结点中增加一个lsize域，其值为它的左子树中的结点数加1。编写一时间复杂度为O(log n)的算法，确定树中第k个结点的位置。
[提示]：先画图手工求。
（1）sum=0,
（2）从当前根开始沿左链找sum + lsize<=k的最大结点a，
（3）沿a的右链求sum=sum + lsize，直到结点b，sum + lsize(b)>=k
重复（2）、（3），直到sum=k
第九章以关键码序列（503，087，512，061，908，170，897，275，653，426）为例，手工执行以下排序算法，写出（前三趟）每一趟排序结束时的关键码状态：
（1）直接插入排序； （2）希尔排序（增量d[1]=5）；
（3）快速排序； （4）堆排序；
（5）归并排序； （6）基数排序。
9.2 一组关键字码，40，27，28，12，15，50，7，采用快速排序或堆排序，写出每趟排序结果。
不难看出，对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n个元素的初始排列。
n=7时在最好情况下需进行多少次比较？请说明理由。
对n=7给出一个最好情况的初始排列实例。
（保证每个基准记录都是中间记录）
9.4 假设序列由n个关键字不同的记录构成，要求不经排序而从中选出关键字从大到小顺序的前k(k<<n)个记录。试问如何进行才能使所作的关键字间比较次数达到最小？
（简单选择、冒泡排序、堆排序均有可能）
插入排序中找插入位置的操作可以通过二分查找的方法来实现。试据此写一个改进后的插入排序算法。
编写一个双向起泡的排序算法，即相邻两遍向相反方向起泡。
[提示]：（1）参快速排序（2）“水底”、“水面”相遇时结束。
9.7 编写算法，对n个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求：
采取顺序存储结构，至多使用一个记录的辅助存储空间；
算法的时间复杂度O(n)；
讨论算法中记录的最大移动次数。
[提示]：r[0]=r[1]，以0为分界值，参快速排序划分过程，但不要求对元素排序。
9.8试以单链表为存储结构实现简单选择排序的算法
9.9假设含n个记录的序列中，其所有关键字为值介于v和w 之间的整数，且其中很多关键字的值是相同的。则可按如下方法排序：另设数组number[v...w]且令number[i]为统计关键字取整数I 的记录数，之后按number 重排序列以达到有序，编写算法实现上述排序方法，并讨论此方法的优缺点。
9.10 已知两个有序序列(a1,a2,...,am)和(am+1,am+2,...,an),并且其中一个序列的记录个数少于s,且s= floor ( sqrt (n) ),试写一个算法,用O(n)时间和O(1)附加空间完成这两个有序序列的归并。
9.11 偶交换排序如下所述：第一趟对所有奇数i,将a[i]和a[i+1]进行比较；第二趟对所有偶数i,将a[i]和a[i+1]进行比较，若a[i]>a[i+1],则将两者交换；第一趟对所有奇数i,第二趟对所有偶数i，…,依次类推直至整个序列有序为止。
这种排序方法的结束条件是什么？
分析当初始序列为正序或逆序两种情况下，奇偶交换排序过程中所需进行的关键字比较的次数。
写出奇偶交换排序的算法。
9.12 设计一个用链表表示的直接选择排序算法。（与9.8重）
9.13 插入排序中找插入位置的操作可以通过二分查找的方法来实现。试据此写一个改进后的插入排序算法。
（与9.5重复）
9.14 一个线性表中的元素为正整数或负整数。设计一个算法，将正整数和负整数分开，使线性表的前一半为负整数，后一半为正整数。不要求对元素排序，但要尽量减少交换次数。
（与9.7类似）
9.15 为什么通常使用一维数组作为堆的存放形式？
9.16 已知（k1,k2,…，kn）是堆，写一个算法将（k1,k2,…，kn，kn+1）调整为堆。按此思想写一个从空堆开始一个一个添入元素的建堆算法。
9.17 试比较直接插入排序、简单选择排序、快速排序、堆排序、归并排序、希尔排序和基数排序的时空性能、稳定性和适用情况。
9.18 在供选择的答案中填入正确答案：
1）、排序（分类）的方法有许多种：__A_③_法从未排序序列中依次取出元素，与排序序列（初始为空）中的元素作比较，将其放入已排序列的正确位置上；__B①__法从未排序序列中挑选元素，并将其依次放入已排序序（初始时为空）的一端；交换排序法是对序列中元素进行一系列的比较，当被比较的两元素逆序时进行交换。__C_④__和__D②__是基于这类方法的两种排序方法，而__D__是比__C__效率更高的方法，利用某种算法，根据元素的关键值计算出排序位置的方法是__E_⑦_。
供选择答案选择排序 ② 快速排序 ③ 插入排序 ④ 冒泡排序
归并排序 ⑥ 二分排序 ⑦ 哈希排序 ⑧ 基数排序
2）、一组记录的关键字为（46，79，56，38，40，84），利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 C 。
A、38，40，46，56，79，84
B、40，38，46，79，56，84
C、40，38，46，56，79，84
D、40，38，46，84，56，79
3）、下列排序算法中,C 算法可能会出现下面情况：初始数据有序时，花费时间反而最多。
A、堆排序 B、冒泡排序 C、快速排序 D、SHELL 排序
9.19 判断正误：
（ ）在一个大堆中，最小元素不一定在最后。
（ X ）对n个记录采用快速排序方法进行排序，最坏情况下所需时间是o（nlog2n）。
（ X ）在执行某排序算法过程中，出现了排序码朝着与最终排序序列相反方向移动的现象，则称该算法是不稳定的。
http://jpkc.nwu.edu.cn/sjjg/pick_title/exercises/hints.htm
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+12)/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+n2)/2
f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2
=[ (1+n)×n/2 + n(n+1)(2n+1)/6 ] / 2
=n(n+1)(n+2)/6
=n3/6+n2/2+n/3
区分语句频度和算法复杂度：
O(f(n)) = O(n3)
四、试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能使用求幂函数。注意：本题中的输入ai(i=0,1,…,n),x和n，输出为Pn(x0).通常算法的输入和输出可采用下列两种方式之一：
通过参数表中的参数显式传递；
通过全局变量隐式传递。
试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。
[提示]：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;
第二章描述以下三个概念的区别：头指针，头结点，首元素结点。
填空：
在顺序表中插入或删除一个元素，需要平均移动＿＿一半＿＿元素，具体移动的元素个数与＿＿插入或删除的位置＿＿有关。
在顺序表中，逻辑上相邻的元素，其物理位置＿＿＿＿＿＿相邻。在单链表中，逻辑上相邻的元素，其物理位置＿＿＿＿＿＿相邻。
在带头结点的非空单链表中，头结点的存储位置由＿＿＿＿＿＿指示，首元素结点的存储位置由＿＿＿＿＿＿指示，除首元素结点外，其它任一元素结点的存储位置由＿＿其直接前趋的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域）。
找到第一个应删结点的前驱pre
pre=L; p=L－>next;
while (p!=NULL && p－>data <= mink)
{ pre=p; p=p－>next; }
找到最后一个应删结点的后继s，边找边释放应删结点
s=p;
while (s!=NULL && s－>data < mink)
{ t =s; s=s－>next; free(t); }
pre－>next = s;
2.7试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1,a2...,an）逆置为（an,an-1,...,a1）。
以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。
以单链表作存储结构。
[方法1]:在原头结点后重新头插一遍
[方法2]:可设三个同步移动的指针p,q,r，将q的后继r改为p
假设两个按元素值递增有序排列的线性表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;
假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前趋结点。
[提示]：设指针p指向s结点的前趋的前趋，则p与s有何关系？
2.10 已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。
2.11 设线性表A=(a1,a2,…,am)，B=(b1,b2,…,bn)，试写一个按下列规则合并A、B为线性表C的算法，使得：
C= (a1,b1,…,am,bm,bm+1,…,bn) 当m≤n时；
或者 C= (a1,b1,…,an,bn,an+1,…,am) 当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) {……}
第三章按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：
⑴ 如进站的车厢序列为123，则可能得到的出站车厢序列是什么？ 123、213、132、231、321（312）
⑵如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。
SXSS XSSX XXSX 或 S1X1S2S3X3S4S5X5X4X2S6X6
设队列中有A、B、C、D、E这5个元素，其中队首元素为A。如果对这个队列重复执行下列4步操作：
输出队首元素；
把队首元素值插入到队尾；
删除队首元素；
再次删除队首元素。
直到队列成为空队列为止，则是否可能得到输出序列：
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）
给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？
按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：
A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ
试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1 & 序列2’模式的字符序列。其中序列1和序列2 中都不含字符’&’，且序列2 是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。
[提示]：
边读边入栈，直到&
边读边出栈边比较，直到……
假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式（中缀）且书写正确的表达式转换为逆波兰式（后缀）。
[提示],
例：
中缀表达式：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/-
后缀表达式的计算过程：（简便）
顺序扫描表达式，
如果是操作数，直接入栈；
如果是操作符op，则连续退栈两次，得操作数X,Y，计算X op Y，并将结果入栈。
如何将中缀表达式转换为后缀表达式？
顺序扫描中缀表达式，
（1）如果是操作数，直接输出；
（2）如果是操作符op2，则与栈顶操作符op1比较：
如果op2 > op1，则op2入栈；
如果op2 = op1，则脱括号；
如果op2 < op1，则输出op1；
假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。
[提示],参P.56 P.70 先画图.
typedef LinkList CLQueue;
int InitQueue(CLQueue * Q)
int EnterQueue(CLQueue Q,QueueElementType x)
int DeleteQueue(CLQueue Q,QueueElementType *x)
要求循环队列不损失一个空间全部都能得到利用,设置一个标志域tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。
[提示],
初始状态：front==0,rear==0,tag==0
队空条件：front==rear,tag==0
队满条件：front==rear,tag==1
其它状态：front !=rear,tag==0（或1、2）
入队操作：
…
…（入队）
if (front==rear) tag=1；（或直接tag=1）
出队操作：
…
…（出队）
tag=0；
[问题]：如何明确区分队空、队满、非空非满三种情况？
简述以下算法的功能（其中栈和队列的元素类型均为int）：
（1）void proc_1(Stack S)
{ int i,n,A[255];
n=0;
while(!EmptyStack(S))
{n++; Pop(&S,&A[n]);}
for(i=1; i<=n; i++)
Push(&S,A[i]);
}
将栈S逆序。
（2）void proc_2(Stack S,int e)
{ Stack T; int d;
InitStack(&T);
while(!EmptyStack(S))
{ Pop(&S,&d);
if (d!=e) Push( &T,d);
}
while(!EmptyStack(T))
{ Pop(&T,&d);
Push( &S,d);
}
}
删除栈S中所有等于e的元素。
（3）void proc_3(Queue *Q)
{ Stack S; int d;
InitStack(&S);
while(!EmptyQueue(*Q))
{
DeleteQueue(Q,&d);
Push( &S,d);
}
while(!EmptyStack(S))
{ Pop(&S,&d);
EnterQueue(Q，d)
}
}
将队列Q逆序。
第四章
1,设s=’I AM A STUDENT’,t=’GOOD’,q=’WORKER’。给出下列操作的结果：
StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1);
StrIndex(s,’A’,4); StrReplace(s,’STUDENT’,q);
StrCat(StrCat(sub1,t),StrCat(sub2,q));
[参考答案]
StrLength(s)=14; sub1= ’I AM A_’; sub2= ’_’; StrIndex(s,’A’,4)=6;
StrReplace(s,’STUDENT’,q)= ’I AM A WORKER’;
StrCat(StrCat(sub1,t),StrCat(sub2,q))= ’I AM A GOOD WORKER’;
2,编写算法，实现串的基本操作StrReplace(S,T,V)。
3,假设以块链结构表示串，块的大小为1，且附设头结点。
试编写算法，实现串的下列基本操作：
StrAsign(S,chars)； StrCopy(S,T)； StrCompare(S,T)； StrLength(S)； StrCat(S,T)； SubString(Sub,S,pos,len)。
[说明]：用单链表实现。
叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。
已知：S=”(xyz)*”,T=”(x+z)*y”。试利用联接、求子串和置换等操作，将S转换为T.
S和T是用结点大小为1的单链表存储的两个串，设计一个算法将串S中首次与T匹配的子串逆置。
S是用结点大小为4的单链表存储的串,分别编写算法在第k个字符后插入串T，及从第k个字符删除len个字符。
以下算法用定长顺序串：
写下列算法：
将顺序串r中所有值为ch1的字符换成ch2的字符。
将顺序串r中所有字符按照相反的次序仍存放在r中。
从顺序串r中删除其值等于ch的所有字符。
从顺序串r1中第index 个字符起求出首次与串r2相同的子串的起始位置。
从顺序串r中删除所有与串r1相同的子串。
写一个函数将顺序串s1中的第i个字符到第j个字符之间的字符用s2串替换。
[提示]：（1）用静态顺序串 （2）先移位，后复制写算法，实现顺序串的基本操作StrCompare(s,t)。
写算法，实现顺序串的基本操作StrReplace(&s,t,v)。
[提示]：
被替换子串定位（相当于第9题中i）
被替换子串后面的字符左移或右移（为替换子串准备房间）
替换子串入住（复制）
重复上述，直到……
第五章假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址。已知A的基地址为1000，计算：
数组A共占用多少字节； （288）
数组A的最后一个元素的地址； （1282）
按行存储时，元素A36的地址； （1126）
按列存储时，元素A36的地址； （1192）
[注意]：本章自定义数组的下标从1开始。
2,设有三对角矩阵（aij）n×n,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得B[k]= aij,求：
用i,j表示k的下标变换公式；
用k表示i,j的下标变换公式。
i = k/3 + 1,j = k%3 + i - 1 = k%3 + k/3
或：
i = k/3 + 1,j = k - 2×( k/3 )
假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放结果矩阵。
[提示]：参考P.28例、P.47例。
4．在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个辅助向量空间。
5．写一个在十字链表中删除非零元素aij的算法。
[提示]：“删除”两次，释放一次。
6．画出下面广义表的两种存储结构图示：
((((a),b)),((( ),d),(e,f)))
7．求下列广义表运算的结果：
HEAD[((a,b),(c,d))];
TAIL[((a,b),(c,d))];
TAIL[HEAD[((a,b),(c,d))]];
HEAD[TAIL[HEAD[((a,b),(c,d))]]]; b
TAIL[HEAD[TAIL[((a,b),(c,d))]]]; (d)
第六章
1．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
2．对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。
3．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，nk个度为k的结点，则该树中有多少个叶子结点？
[提示]：参考 P.116 性质3
∵ n=n0 + n1 + …… + nk
B=n1 + 2n2 + 3n3 + …… + knk
n= B + 1
∴ n0 + n1 + …… + nk = n1 + 2n2 + 3n3 + …… + knk + 1
∴ n0 = n2 + 2n3 + …… + (k-1)nk + 1
4.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。
[提示]：参考 P.148
已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？
[提示]：一个叶子结点，总结点数至多有多少个？可压缩一度结点。
给出满足下列条件的所有二叉树：
前序和中序相同中序和后序相同前序和后序相同
[提示]：去异存同。
D L R 与L D R 的相同点：D R，如果无 L，则完全相同,如果无 LR，…。
L D R 与L R D 的相同点：L D，如果无 R，则完全相同。
D L R 与L R D 的相同点：D，如果无 L R，则完全相同。
（如果去D，则为空树）
7,n个结点的K叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的Child域有多少个？
[提示]：参考 P.119
8．画出与下列已知序列对应的树Ｔ：
树的先根次序访问序列为GFKDAIEBCHJ；
树的后根次序访问序列为DIAEKFCJHBG。
[提示]：
（1）先画出对应的二叉树
（2）树的后根序列与对应二叉树的中序序列相同
9．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为：
0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10
（1）请为这8个字母设计哈夫曼编码，
（2）求平均编码长度。
10．已知二叉树采用二叉链表存放,要求返回二叉树T的后序序列中的第一个结点的指针,是否可不用递归且不用栈来完成?请简述原因.
[提示]：无右子的“左下端”
11,画出和下列树对应的二叉树：
12．已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。
13．编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。
[提示]：
[方法1]：（1）按先序查找；（2）超前查看子结点（3）按后序释放；
void DelSubTree(BiTree *bt,DataType x)
{
if ( *bt != NULL && (*bt) ->data==x )
{ FreeTree(*bt);
*bt =NULL;
}
else DelTree( *bt,x)
void DelTree(BiTree bt,DataType x)
{ if ( bt )
{ if (bt->LChild && bt->LChild->data==x)
{ FreeTree(bt->LChild);
bt->LChild=NULL;
}
if (bt->RChild && bt->RChild->data==x)
{ FreeTree(bt->RChild);
bt->RChild=NULL;
}
DelTree(bt->LChild,x);
DelTree(bt->RChild,x);
}
}
[方法2]：（1）先序查找；（2）直接查看当前根结点（3）用指针参数；
[方法3]：（1）先序查找；（2）直接查看当前根结点
（3）通过函数值，返回删除后结果；
（参示例程序）
14．分别写函数完成：在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。
[提示]：
（1）先查看线索，无线索时用下面规律：
（2）结点*p在先序序列中的后继为其左子或右子；
（3）结点*p在后序序列中的前驱也是其左子或右子。
15．分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。（参例题）
16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。
[提示]：
（1）可将孩子-兄弟链表划分为根、首子树、兄弟树，递归处理。
（2）可利用返回值，或全局变量。
17．对以孩子-兄弟链表表示的树编写计算树的深度的算法。
18．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出后序遍历非递归的算法。 （参课本）
19．设二叉树按二叉链表存放，写算法判别一棵二叉树是否是一棵正则二叉树。正则二叉树是指：在二叉树中不存在子树个数为1的结点。
[提示]：可利用任何递归、非递归遍历算法。
20．计算二叉树最大宽度的算法。二叉树的最大宽度是指：二叉树所有层中结点个数的最大值。
[提示]：
[方法一]：
（1）利用队列，初值为根
（2）出队访问，并将左、右子入队，直到队空
（3）记录每一层中最后一个结点在队中的位置
（4）第i层最后一个结点的右子，必是第i+1层的最后一个结点
（5）第1层最后一个结点在队中的位置为0
[方法二]：利用层号和全局数组，任意遍历、统计
21．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。
22,证明：给定一棵二叉树的前序序列与中序序列，可唯一确定这棵二叉树；
给定一棵二叉树的后序序列与中序序列，可唯一确定这棵二叉树；
23,二叉树按照二叉链表方式存储，编写算法将二叉树左右子树进行交换。
第七章已知如图所示的有向图，请给出该图的：
每个顶点的入度、出度；
邻接矩阵；
邻接表；
逆邻接表；
十字链表；
强连通分量。
已知如图所示的无向图，请给出该图的：
邻接多重表；（要求每个边结点中第一个顶点号小于第二个顶点号，且每个顶点的各邻接边的链接顺序，为它所邻接到的顶点序号由小到大的顺序。）
从顶点1开始，深度优先遍历该图所得顶点序列和边的序列；（给出深度优先搜索树）
从顶点1开始，广度优先遍历该图所得顶点序列和边的序列。（给出广度优先搜索树）
已知如图7.31所示的AOE-网，试求：
每个事件的最早发生时间和最晚发生时间；
每个活动的最早开始时间和最晚开始时间；
给出关键路径。
已知如图7.30所示的有向网，试利用Dijkstra算法求顶点1到其余顶点的最短路径，并给出算法执行过程中各步的状态。
编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。
[参例题]
试在邻接矩阵存储结构上实现图的基本操作：InsertVertex(G,v); InsertArc(G,v,w); DeleteVertex(G,v)和DeleteArc(G,v,w)。
试对邻接表存储结构重做题6。
试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中，是否存在由顶点vi到顶点vj的路径（i≠j）。注意：算法中涉及的图的基本操作必须在此存储结构上实现。
同上题要求。试基于图的广度优先搜索策略写一算法。
试利用栈的基本操作，编写按深度优先策略遍历一个强连通图的、非递归形式的算法。算法中不规定具体的存储结构，而将图Graph看成是一种抽象数据类型。
采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径（指顶点序列中不含有重现的顶点）的算法。
[提示]：利用深度搜索，增设一个深度参数，深度超过k 则停止对该结点的搜索。
下图是带权的有向图G的邻接表表示法。从结点V1出发，深度遍历图G所得结点序列为（ A ），广度遍历图G所得结点序列为（ B ）；G的一个拓扑序列是（ C ）；从结点V1到结点V8的最短路径为（ D ）；从结点V1到结点V8的关键路径为（ E ）。
其中A、B、C的选择有：
V1,V2,V3,V4,V5,V6,V7,V8
V1,V2,V4,V6,V5,V3,V7,V8
V1,V2,V4,V6,V3,V5,V7,V8
V1,V2,V4,V6,V7,V3,V5,V8
V1,V2,V3,V8,V4,V5,V6,V7
V1,V2,V3,V8,V4,V5,V7,V6
V1,V2,V3,V8,V5,V7,V4,V6
D、E的选择有：
V1,V2,V4,V5,V3,V8
V1,V6,V5,V3,V8
V1,V6,V7,V8
V1,V2,V5,V7,V8
第八章
8.1 若对大小均为n的有序的顺序表和无序的顺序表分别进行查找，试在下列三种情况下分别讨论两者在等概率时的平均查找长度是否相同？
查找不成功，即表中没有关键字等于给定值K的记录。
查找成功，且表中只有一个关键字等于给定值K的记录。
查找成功，且表中有若干个关键字等于给定值K的记录，一次查找要求找出所有记录。
[提示]：均用顺序查找法。
画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。
[提示]：根据P.191 ASL定义计算平均查找长度。
试推导含12个结点的平衡二叉树的最大深度并画出一棵这样的树。
[提示]：沿最左分支生长，前提是：其任一祖先的右分支与左分支等深，如不等深，则先生长右分支，而生长右分支的前提是：其任一祖先的左分支与右分支等深，如不等深，则先生长左分支，如此交互考虑，逐步生长，直到12个结点。
试从空树开始，画出按以下次序向2-3树，即3阶B-树中插入关键码的建树过程：20，30，50，52，60，68，70。如果此后删除50和68，画出每一步执行后2-3树的状态。
选取哈希函数H(k)=(3k)%11，用线性探测再散列法处理冲突。试在0～10的散列地址空间中，对关键字序列（22，41，53，46，30，13，01，67）构造哈希表，并求等概率情况下查找成功与不成功时的平均查找长度。
[提示]：平均查找长度参考P.225。
0
1
2
3
4
5
6
7
8
9
10
22
41
30
01
53
46
13
67
1
1
2
2
1
1
2
6
ASLsucc = (1×4 + 2×3 + 6) / 8 = 2
ASLunsucc = ( 2 + 1 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 1 ) / 11 = 40 / 11
试为下列关键字建立一个装载因子不小于0.75的哈希表，并计算你所构造的哈希表的平均查找长度。
（ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG，CHANG，CHAO，YANG，JIN）
[提示]：（1）由装填因子求出表长，（2）可利用字母序号设计哈希函数，
（3）确定解决冲突的方法。
试编写利用折半查找确定记录所在块的分块查找算法。
试写一个判别给定二叉树是否为二叉排序树的算法。设此二叉树以二叉链表作存储结构，且树中结点的关键字均不同。
[提示]：检验中序遍历序列是否递增有序？
[方法1]：用非递归中序遍历算法，设双指针pre,p
一旦pre->data > p->data 则返回假
[方法2]：用递归中序遍历算法，设全局指针pre，（参中序线索化算法）
一旦pre->data > p->data 则返回假
[方法3]：用递归（中序或后序）算法
（1）空树是（2）单根树是（3）左递归真（4）右递归真
（5）左子树的右端小于根（6）右子树的左端大于根
编写算法，求出指定结点在给定的二叉排序树中所在的层数。
8.10 编写算法，在给定的二叉排序树上找出任意两个不同结点的最近公共祖先（若在两结点A、B中，A是B的祖先，则认为A是A、B的最近公共祖先）。
[提示]：
假设A<=B，
从根开始，左走或右走，直到A在左（或根），B在右（或根）。
8.11 编写一个函数，利用二分查找算法在一个有序表中插入一个元素x，并保持表的有序性。
[提示]：（1）表中已经有x，（2）表中没有x
参P,231
8.12 已知长度为12的表：
（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）。
试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树并求其等概率的情况下查找成功的平均查找长度。
若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。
按表中元素的顺序依次构造一棵平衡二叉排序树，并求其等概率的情况下查找成功的平均查找长度。
[提示]：画出判定树或排序树，根据P.191 ASL定义计算平均查找长度。
8.13 含有9个叶子结点的3阶B-树中至少有多少个非叶子结点？含有10个叶子结点的3阶B-树中至少有多少个非叶子结点？
[提示]：叶子结点对应空指针。
8.14 写一时间复杂度为O(log2n + m)的算法，删除二叉排序树中所有关键字不小于x的结点，并释放结点空间。其中n为树中的结点个数，m为被删除的结点个数。
[提示]：
p=root
如果p->key大于、等于x，则删除p->rchild和p，
左走一步，转（2）
如果p->key小于x，则反复右走，
转（2）
直到p==NULL
8.15 在平衡二叉排序树的每个结点中增加一个lsize域，其值为它的左子树中的结点数加1。编写一时间复杂度为O(log n)的算法，确定树中第k个结点的位置。
[提示]：先画图手工求。
（1）sum=0,
（2）从当前根开始沿左链找sum + lsize<=k的最大结点a，
（3）沿a的右链求sum=sum + lsize，直到结点b，sum + lsize(b)>=k
重复（2）、（3），直到sum=k
第九章以关键码序列（503，087，512，061，908，170，897，275，653，426）为例，手工执行以下排序算法，写出（前三趟）每一趟排序结束时的关键码状态：
（1）直接插入排序； （2）希尔排序（增量d[1]=5）；
（3）快速排序； （4）堆排序；
（5）归并排序； （6）基数排序。
9.2 一组关键字码，40，27，28，12，15，50，7，采用快速排序或堆排序，写出每趟排序结果。
不难看出，对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n个元素的初始排列。
n=7时在最好情况下需进行多少次比较？请说明理由。
对n=7给出一个最好情况的初始排列实例。
（保证每个基准记录都是中间记录）
9.4 假设序列由n个关键字不同的记录构成，要求不经排序而从中选出关键字从大到小顺序的前k(k<<n)个记录。试问如何进行才能使所作的关键字间比较次数达到最小？
（简单选择、冒泡排序、堆排序均有可能）
插入排序中找插入位置的操作可以通过二分查找的方法来实现。试据此写一个改进后的插入排序算法。
编写一个双向起泡的排序算法，即相邻两遍向相反方向起泡。
[提示]：（1）参快速排序（2）“水底”、“水面”相遇时结束。
9.7 编写算法，对n个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求：
采取顺序存储结构，至多使用一个记录的辅助存储空间；
算法的时间复杂度O(n)；
讨论算法中记录的最大移动次数。
[提示]：r[0]=r[1]，以0为分界值，参快速排序划分过程，但不要求对元素排序。
9.8试以单链表为存储结构实现简单选择排序的算法
9.9假设含n个记录的序列中，其所有关键字为值介于v和w 之间的整数，且其中很多关键字的值是相同的。则可按如下方法排序：另设数组number[v...w]且令number[i]为统计关键字取整数I 的记录数，之后按number 重排序列以达到有序，编写算法实现上述排序方法，并讨论此方法的优缺点。
9.10 已知两个有序序列(a1,a2,...,am)和(am+1,am+2,...,an),并且其中一个序列的记录个数少于s,且s= floor ( sqrt (n) ),试写一个算法,用O(n)时间和O(1)附加空间完成这两个有序序列的归并。
9.11 偶交换排序如下所述：第一趟对所有奇数i,将a[i]和a[i+1]进行比较；第二趟对所有偶数i,将a[i]和a[i+1]进行比较，若a[i]>a[i+1],则将两者交换；第一趟对所有奇数i,第二趟对所有偶数i，…,依次类推直至整个序列有序为止。
这种排序方法的结束条件是什么？
分析当初始序列为正序或逆序两种情况下，奇偶交换排序过程中所需进行的关键字比较的次数。
写出奇偶交换排序的算法。
9.12 设计一个用链表表示的直接选择排序算法。（与9.8重）
9.13 插入排序中找插入位置的操作可以通过二分查找的方法来实现。试据此写一个改进后的插入排序算法。
（与9.5重复）
9.14 一个线性表中的元素为正整数或负整数。设计一个算法，将正整数和负整数分开，使线性表的前一半为负整数，后一半为正整数。不要求对元素排序，但要尽量减少交换次数。
（与9.7类似）
9.15 为什么通常使用一维数组作为堆的存放形式？
9.16 已知（k1,k2,…，kn）是堆，写一个算法将（k1,k2,…，kn，kn+1）调整为堆。按此思想写一个从空堆开始一个一个添入元素的建堆算法。
9.17 试比较直接插入排序、简单选择排序、快速排序、堆排序、归并排序、希尔排序和基数排序的时空性能、稳定性和适用情况。
9.18 在供选择的答案中填入正确答案：
1）、排序（分类）的方法有许多种：__A_③_法从未排序序列中依次取出元素，与排序序列（初始为空）中的元素作比较，将其放入已排序列的正确位置上；__B①__法从未排序序列中挑选元素，并将其依次放入已排序序（初始时为空）的一端；交换排序法是对序列中元素进行一系列的比较，当被比较的两元素逆序时进行交换。__C_④__和__D②__是基于这类方法的两种排序方法，而__D__是比__C__效率更高的方法，利用某种算法，根据元素的关键值计算出排序位置的方法是__E_⑦_。
供选择答案选择排序 ② 快速排序 ③ 插入排序 ④ 冒泡排序
归并排序 ⑥ 二分排序 ⑦ 哈希排序 ⑧ 基数排序
2）、一组记录的关键字为（46，79，56，38，40，84），利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 C 。
A、38，40，46，56，79，84
B、40，38，46，79，56，84
C、40，38，46，56，79，84
D、40，38，46，84，56，79
3）、下列排序算法中,C 算法可能会出现下面情况：初始数据有序时，花费时间反而最多。
A、堆排序 B、冒泡排序 C、快速排序 D、SHELL 排序
9.19 判断正误：
（ ）在一个大堆中，最小元素不一定在最后。
（ X ）对n个记录采用快速排序方法进行排序，最坏情况下所需时间是o（nlog2n）。
（ X ）在执行某排序算法过程中，出现了排序码朝着与最终排序序列相反方向移动的现象，则称该算法是不稳定的。
http://jpkc.nwu.edu.cn/sjjg/pick_title/exercises/hints.htm
