第一章答案13计算下列程序中xx1的语句频度
fori1i
iforj1jijfork1kjkxx1
【解答】xx1的语句频度为：T
112（123）……（12……
）
1
26
14试编写算法，求p
xa0a1xa2x2……a
x
的值p
x0并确定算法中每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求
幂函数。注意：本题中的输入为aii01…
、x和
输出为P
x0。算法的输入和输出采用下列方法（1）通过参数表中的参数显式传递（2）通过全局变量隐式传递。讨论
两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。
【解答】
（1）通过参数表中的参数显式传递
优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通
用性强，移置性强。
缺点：形参须与实参对应，且返回值数量有限。
（2）通过全局变量隐式传递
优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗
缺点：函数通用性降低，移植性差
算法如下：通过全局变量隐式传递参数
PolyValue
i
ti

floatxappri
tf“
”
sca
f“f”

pri
tf“
x”
sca
f“f”x
fori0i
isca
f“f”ai
执行次数：
次
pa0
fori1i
ippaix
执行次数：
次
xxx
pri
tf“f”p
算法的时间复杂度：T
O

通过参数表中的参数显式传递
floatPolyValuefloatafloatxi
t


floatps
i
ti
pxsa0
fori1i
issaip
执行次数
次
ppx
retur
p
算法的时间复杂度：T
O

f第二章答案
27试分别以不同的存储结构实现单线表的就地逆置算法，即在原表的存储空间将线性表
（a1a2…a
）逆置为a
a
1…a1。
【解答】（1）用一维数组作为存储结构
voidi
vertSeqListLi
t
um

i
tj
ElemTypetmp
forj0j
um12j
tmpLj
LjL
umj1
L
umj1tmp

（2）用单链表作为存储结构
voidi
vertLi
kListL

Nodepqr
ifL
extNULLretur

链表为空
pL
ext
qp
ext
p
extNULL
摘下第一个结点，生成初始逆置表
whileqNULL
从第二个结点起依次头插入当前逆置表

rq
ext
q
extL
ext
L
extq
qr


211将线性表Aa1a2……amBb1b2……b
合并成线性表C
Ca1b1……ambmbm1……b

当
m

时
，
或
Ca1b1……a
b
a
1……am当m
时线性表A、B、C以单链表作为存储结构，
且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和
均未显式存储。
【解答】算法如下：
Li
kListr