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

floatxap
pri
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
floatpsi
tipx
1
fsa0fori1i
i
ssaip
ppxretur
p算法的时间复杂度：T
O

执行次数
次
第2章线性表
习题
1填空：
1在顺序表中插入或删除一个元素，需要平均移动一半元素，具体移动的元素个数与插入或删除的位置有关。2线性表有顺序和链式两种存储结构。在顺序表中，线性表的长度在数组定义时就已经确定，是静态保存，在链式表中，整个链表由“头指针”来表示，单链表的长度是动态保存。3在顺序表中，逻辑上相邻的元素，其物理位置＿一定＿＿＿＿＿相邻。在单链表中，逻辑上相邻的元素，其物理位置不一定相邻。4在带头结点的非空单链表中，头结点的存储位置由头指针指示，首元素结点的存储位置由头结点指示，除首元素结点外，其它任一元素结点的存储位置由其直接前趋的
ext域指示。
2选择题
1A2已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。a在P结点后插入S结点的语句序列是：E、r