z=y—x；break；
casex=y：
z=abs（x*y）;break;
default:
z=（x—y）/abs（x）＊abs（y）;
}
1.6在程序设计中，常用下列三种不同的出错处理方式:
（1）用exit语句终止执行并报告错误；
（2）以函数的返回值区别正确返回或错误返回；
（3）设置一个整型变量的函数参数以区别正确返回或某种错误返回。
试讨论这三种方法各自的优缺点。
1。
7在程序设计中，可采用下列三种方法实现输出和输入：
（1）通过scanf和printf语句；
（2）通过函数的参数显式传递；
（3）通过全局变量隐式传递。
试讨论这三种方法的优缺点。
1.8设n为正整数。
试确定下列各程序段中前置以记号@的语句的频度:
（1）i=1；k=0；
while（i〈=n-1）{
＠k+=10＊i;
i++;
}
（2）i=1；k=0；
do{
＠k+=10＊i；
i++；
｝while（i〈=n-1）；
（3）i=1;k=0;
while（i〈=n—1）{
i++;
＠k+=10＊i;
｝
（4）k=0;
for（i=1；i〈=n；i++）｛
for（j=i；j〈=n；j++）
＠k++；
｝
（5）for（i=1;i〈=n；i++）{
for（j=1；j<=i；j++）｛
for（k=1；k<=j;k++）
＠x+=delta；
}
（6）i=1；j=0;
while（i+j〈=n）{
＠if（i〉j）j++；
elsei++;
｝
（7）x=n;y=0;//n是不小于1的常数
while（x〉=（y+1）*（y+1））｛
＠y++;
｝
（8）x=91；y=100;
while（y〉0）{
＠if（x>100）{x-=10；y——；｝
elsex++;
}
1。
9假设n为2的乘幂，并且n〉2，试求下列算法的时间复杂度及变量count的值（以n的函数形式表示）。
intTime（intn）｛
count=0；x=2;
while（x〈n/2）｛
x＊=2;count++;
｝
returncount；
｝
1.11已知有实现同一功能的两个算法，其时间复杂度分别为
和
假设现实计算机可连续运算的时间为
秒（100多天），又每秒可执行基本操作（根据这些操作来估算算法时间复杂度）
次。
试问在此条件下，这两个算法可解问题的规模（即n值的范围）各为多少？
哪个算法更适宜？
请说明理由。
1。
12设有以下三个函数：
，
请判断以下断言正确与否：
（1）f（n）是O（g（n））
（2）h（n）是O（f（n））
（3）g（n）是O（h（n））
（4）h（n）是O（n3。
5）
（5）h（n）是O（nlogn）
1.13试设定若干n值，比较两函数
和
的增长趋势，并确定n在什么范围内，函数
的值大于
的值。
1。
14判断下列各对函数
和
，当
时，哪个函数增长更快？
（1）
，
（2）
，
（3）
，
（4）
，
1。
15试用数学归纳法证明：
（1）
（2）
（3）
（4）
1。
16试写一算法，自大至小依次输出顺序读入的三个整数X,Y和Z的值
1。
17已知k阶斐波那契序列的定义为
，
，…,
，
；
，
试编写求k阶斐波那契序列的第m项值的函数算法,k和m均以值调用的形式在函数参数表中出现.
1。
18假设有A，B，C，D,E五个高等院校进行田径对抗赛，各院校的单项成绩均已存入计算机，并构成一张表,表中每一行的形式为
项目名称
性别
校名
成绩
得分
编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。
1.19试编写算法，计算
的值并存入数组a[0。
。
arrsize-1]的第i—1个分量中（i=1，2,…,n）。
假设计算机中允许的整数最大值为maxint,则当n〉arrsize或对某个
，使
时，应按出错处理。
注意选择你认为较好的出错处理方法.
1。
20试编写算法求一元多项式的值
的值
，并确定算法中每一语句的执行次数和整个算法的时间复杂度。
注意选择你认为较好的输入和输出方法.本题的输入为
，
和
输出为
。
第2章线性表
2。
1描述以下三个概念的区别：
头指针，头结点，首元结点（第一个元素结点）.
2.2填空题。
（1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。
（2）顺序表中逻辑上相邻的元素的物理位置紧邻。
单链表中逻辑上相邻的元素的物理位置紧邻.
（3）在单链表中，除了首元结点外，任一结点的存储位置由指示。
（4）在单链表中设置头结点的作用是。
2。
3在什么情况下用顺序表比链表好?
2。
4对以下单链表分别执行下列各程序段，并画出结果示意图。
2.5画出执行下列各行语句后各指针及链表的示意图。
L=（LinkList）malloc（sizeof（LNode））;P=L;
for（i=1；i<=4；i++）｛
P—>next=（LinkList）malloc（sizeof（LNode））；
P=P—>next;P-〉data=i*2—1；
}
P-〉next=NULL;
for（i=4;i〉=1；i——）Ins_LinkList（L,i+1,i*2）;
for（i=1；i〈=3；i++）Del_LinkList（L，i）;
2。
6已知L是无表头结点的单链表，且P结点既不是首元结点,也不是尾元结点，试从下列提供的答案中选择合适的语句序列。
a.在P结点后插入S结点的语句序列是__________________。
b.在P结点前插入S结点的语句序列是__________________。
c.在表首插入S结点的语句序列是__________________。
d。
在表尾插入S结点的语句序列是__________________。
（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。
7已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点,试从下列提供的答案中选择合适的语句序列。
a.删除P结点的直接后继结点的语句序列是____________________.
b。
删除P结点的直接前驱结点的语句序列是____________________。
c。
删除P结点的语句序列是____________________。
d。
删除首元结点的语句序列是____________________。
e.删除尾元结点的语句序列是____________________.
（1）P=P-〉next；
（2）P-〉next=P;
（3）P-〉next=P->next->next;
（4）P=P-〉next—〉next；
（5）while（P!
=NULL）P=P—〉next；
（6）while（Q->next！
=NULL）｛P=Q；Q=Q—>next;}
（7）while（P—>next!
=Q）P=P—>next；
（8）while（P—〉next->next!
=Q）P=P—>next;
（9）while（P-〉next->next!
=NULL）P=P->next;
（10）Q=P;
（11）Q=P-〉next;
（12）P=L；
（13）L=L->next；
（14）free（Q）；
2.8已知P结点是某双向链表的中间结点,试从下列提供的答案中选择合适的语句序列.
a。
在P结点后插入S结点的语句序列是_______________________。
b。
在P结点前插入S结点的语句序列是_______________________。
c.删除P结点的直接后继结点的语句序列是_______________________。
d.删除P结点的直接前驱结点的语句序列是_______________________。
e.删除P结点的语句序列是_______________________。
（1）P->next=P-〉next—〉next;
（2）P—>priou=P—〉priou-〉priou;
（3）P->next=S；
（4）P—〉priou=S;
（5）S—>next=P;
（6）S->priou=P;
（7）S—>next=P->next;
（8）S-〉priou=P—>priou；
（9）P—>priou->next=P—>next;
（10）P—〉priou->next=P；
（11）P—>next->priou=P；
（12）P-〉next—>priou=S;
（13）P-〉priou-〉next=S；
（14）P—>next->priou=P->priou；
（15）Q=P-〉next;
（16）Q=P—>priou;
（17）free（P）；
（18）free（Q）;
2.9简述以下算法的功能。
（1）StatusA（LinkedListL）{//L是无表头结点的单链表
if（L&&L->next）｛
Q=L；L=L—>next;P=L；
while（P—>next）P=P-〉next；
P—〉next=Q;Q->next=NULL；
｝
returnOK;
}
（2）voidBB（LNode*s,LNode*q）｛
p=s;
while（p—〉next！
=q）p=p—〉next；
p—〉next=s；
｝
voidAA（LNode*pa,LNode＊pb）{
//pa和pb分别指向单循环链表中的两个结点
BB（pa，pb）;
BB（pb,pa）；
}
2.10指出以下算法中的错误和低效之处,并将它改写为一个既正确又高效的算法.
StatusDeleteK（SqList&a，inti，intk）
{
//本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素
if（i〈1|｜k<0||i+k〉a.length）returnINFEASIBLE；//参数不合法
else｛
for（count=1;count〈k；count++）{
//删除第一个元素
for（j=a。
length;j〉=i+1；j——）a.elem[j—i]=a.elem［j]；
a.length—-;
｝
returnOK;
｝
2。
11设顺序表va中的数据元素递增有序。
试写一算法，将x插入到顺序表的适当位置上,以保持该表的有序性。
解：
StatusInsertOrderList（SqList&va，ElemTypex）
{
//在非递减的顺序表va中插入元素x并使其仍成为顺序表的算法
inti;
if（va。
length==va。
listsize）return（OVERFLOW）；
for（i=va。
length;i〉0,xelem［i-1］；i-—）
va。
elem［i］=va.elem[i-1]；
va.elem[i］=x；
va。
length++;
returnOK；
}
2。
12设
和
均为顺序表，
和
分别为
和
中除去最大共同前缀后的子表。
若
空表，则
;若
=空表，而
空表，或者两者均不为空表，且
的首元小于
的首元,则
；否则
.试写一个比较
大小的算法。
2.13试写一算法在带头结点的单链表结构上实现线性表操作Locate（L,x）;
2。
14试写一算法在带头结点的单链表结构上实现线性表操作Length（L）。
2。
15已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n.试写一算法将这两个链表连接在一起，假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。
请分析你的算法的时间复杂度.
2.16已知指针la和lb分别指向两个无头结点单链表中的首元结点。
下列算法是从表la中删除自第i个元素起共len个元素后,将它们插入到表lb中第i个元素之前。
试问此算法是否正确?
若有错，请改正之。
StatusDeleteAndInsertSub（LinkedListla，LinkedListlb，inti，intj，intlen）
｛
if（i〈0|｜j〈0||len〈0）returnINFEASIBLE；
p=la；k=1;
while（knext；k++；｝
q=p；
while（k〈=len）{q=q—>next;k++；}
s=lb;k=1；
while（ks-〉next=p;q-〉next=s-〉next；
returnOK；
}
2。
17试写一算法，在无头结点的动态单链表上实现线性表操作Insert（L,i,b），并和在带头结点的动态单链表上实现相同操作的算法进行比较。
2。
18试写一算法，实现线性表操作Delete（L，i），并和在带头结点的动态单链表上实现相同操作的算法进行比较.
2。
19已知线性表中的元素以值递增有序排列,并以单链表作存储结构。
试写一高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删结点空间,并分析你的算法的时间复杂度（注意，mink和maxk是给定的两个参变量,它们的值可以和表中的元素相同,也可以不同）.
2.20同2。
19题条件，试写一高效的算法，删除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同），同时释放被删结点空间，并分析你的算法的时间复杂度。
2。
21试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表
逆置为
。
2。
22试写一算法,对单链表实现就地逆置。
2。
23设线性表
，
，试写一个按下列规则合并A，B为线性表C的算法，即使得
当
时；
当
时。
线性表A，B和C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成。
注意：
单链表的长度值m和n均未显式存储。
2。
24假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构,请编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序,允许表中含有值相同的元素）排列的线性表C，并要求利用原表（即A表和B表）的结点空间构造C表.
2.25假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合（即同一表中的元素值各不相同）,现要求另辟空间构成一个线性表C，其元素为A和B中元素的交集,且表C中的元素有依值递增有序排列.试对顺序表编写求C的算法.
2.26要求同2。
25题。
试对单链表编写求C的算法.
2。
27对2。
25题的条件作以下两点修改，对顺序表重新编写求得表C的算法。
（1）假设在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同;
（2）利用A表空间存放表C。
2.28对2。
25题的条件作以下两点修改,对单链表重新编写求得表C的算法。
（1）假设在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同；
（2）利用原表（A表或B表）中的结点构成表C,并释放A表中的无用结点空间。
2。
29已知A,B和C为三个递增有序的线性表，现要求对A表作如下操作：
删去那些既在B表中出现又在C表中出现的元素.试对顺序表编写实现上述操作的算法，并分析你的算法的时间复杂度（注意：
题中没有特别指明同一表中的元素值各不相同）。
2.30要求同2。
29题。
试对单链表编写算法，请释放A表中的无用结点空间.
2。
31假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针.已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点.
2.32已知有一个单向循环链表，其每个结点中含三个域:
pre，data和next，其中data为数据域，next为指向后继结点的指针域，pre也为指针域，但它的值为空，试编写算法将此单向循环链表改为双向循环链表，即使pre成为指向前驱结点的指针域。
2.33已知由一个线性链表表示的线性表中含有三类字符的数据元素（如：
字母字符、数字字符和其他字符），试编写算法将该线性表分割为三个循环链表，其中每个循环链表表示的线性表中均只含一类字符。
2。
34假设在算法描述语言中引入指针的二元运算“异或”，若a和b为指针，则a⊕b的运算结果仍为原指针类型，且
a⊕（a⊕b）=（a⊕a）⊕b=b
（a⊕b）⊕b=a⊕（b⊕b）=a
则可利用一个指针域来实现双向链表L.链表L中的每个结点只含两个域:
data域和LRPtr域，其中LRPtr域存放该结点的左邻与右邻结点指针（不存在时为NULL）的异或。
若设指针L.Left指向链表中的最左结点，L。
Right指向链表中的最右结点，则可实现从左向右或从右向左遍历此双向链表的操作。
试写一算法按任一方向依次输出链表中各元素的值.
2。
35采用2。
34题所述的存储结构，写出在第i个结点之前插入一个结点的算法.
2.36采用2。
34题所述的存储结构，写出删除第i个结点的算法。
2。
37设以带头结点的双向循环链表表示的线性表
。
试写一时间复杂度O（n）的算法，将L改造为
。
2.38设有一个双向循环链表，每个结点中除有pre,data和next三个域外，还增设了一个访问频度域freq。
在链表被起用之前，频度域freq的值均初始化为零，而每当对链表进行一次Locate（L,x）的操作后，被访问的结点（即元素值等于x的结点）中的频度域freq的值便增1，同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。
试编写符合上述要求的Locate操作的算法.
2。
39已知稀疏多项式
，其中
，
。
试采用存储量同多项式项数m成正比的顺序存储结构，编写求
的算法（
为给定值）,并分析你的算法的时间复杂度。
2.40采用2.39题给定的条件和存储结构，编写求
的算法，将结果多项式存放在新辟的空间中，并分析你的算法的时间复杂度。
2。
41试以循环链表作稀疏多项式的存储结构，编写求其导函数的方法，要求利用原多项式中的结点空间存放其导函数多项式，同时释放所有无用结点.
2.42试编写算法，将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间构成这两个链表.
第3章栈和队列
3。
1若按教科书3.1.1节中图3.1（b）所示铁道进行车厢调度（注意：
两侧铁道均为单向行驶道），则请回答:
（1）如果进站的车厢序列为123，则可能得到的出站车厢序列是什么？
（2）如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到（即写出以‘S'表示进栈和以‘X’表示出栈的栈操作序列）。
3.2简述栈和线性表的差别。
3.3写出下列程序段的输出结果（栈的元素类型SElemType为char）。
voidmain（）
{
StackS;
charx，y；
InitStack（S）;
x=‘c’;y=‘k'；
Push（S,x）;Push（S,‘a'）;Push（S，y）;
Pop（S，x）;Push（S,‘t’）;Push（S，x）；
Pop（S,x）;Push（S,‘s’）;
while（！
StackEmpty（S））{Pop（S,y）；printf（y）;｝
printf（x）;
}
3.4简述以下算法的功能（栈的元素类型SElemType为int）。
（1）statusalgo1（StackS）
｛
inti,n,A[255］；
n=0;
while（!
StackEmpty（S））｛n++；Pop（S，A[n]）;}
for（i=1;i〈=n；i++）Push（S，A[i］）;
}
（2）statusalgo2（StackS，inte）
{
StackT;intd；
InitStack（T）;
while（!
StackEmpty（S））{
Pop（S，d）；
if（d！
=e）Push（T,d）；
}
while（！
StackEmpty（T））{
Pop（T，d）；
Push（S,d）;
｝
}
3.5假设以S和X分别表示入栈和出栈的操作，则初态和终态均为空栈的入栈和出栈的操作序列可以表示为仅由S和X组成的序列。
称可以操作的序列为合法序列（例如，SXSX为合法序列，SXXS为非法序列）。
试给出区分给定序列为合法序列或非法序列的一般准则，并证明：
两个不同的合法（栈操作）序列（对同一输入序列）不可能得到相同的输出元素（注意:
在此指的是元素实体，而不是值）序列。
3.6试证明:
若借助栈由输入序列12…n得到的输出序列为
（它是输入序列的一个排列
升级会员 