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

xxxpri
tf“f”p算法的时间复杂度：T
O

通过参数表中的参数显式传递
3
f4
f5
fDS
extP
extES
extLFS
extNULLGQPHwhileP
extQPP
extIwhileP
extNULLPP
extJPQKPLLLSMLP3D4D5D6A
7试分别以不同的存储结构实现单线表的就地逆置算法，即在原表的存储空间将线性表（a1a2…a
）逆置为a
a
1…a1。【解答】（1）用一维数组作为存储结构
voidi
vertSeqListLi
t
um
i
tjElemTypetmpforj0j
um12j
6
ftmpLj
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


11将线性表Aa1a2……am
Bb1b2……b
合并成线性表C
Ca1b1……ambmbm1……b

当
7
fm

时
，
或
Ca1b1……a
b
a
1……am当m
时
线性表A、B、C以单链表作为存储结构，且C
表利用A表和B表中的结点空r