严飞 - 《软件技术基础》沈被娜习题解答

第二章

2.1 什么是数据结构？它对算法有什么影响？

数据结构是指同一数据对象中各数据元素间存在的关系。

数据结构对算法的影响：算法的实现必须借助程序设计语言中提供的数据

类型及其运算。一个算法的效率往往与数据的表达形式有关，因此数据结构的选择对数据处理的效率起着至关重要的作用。它是算法和程序设计的基本部分，它对程序的质量影响很大。 2.2 何谓算法？它与程序有何区别？

广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。计算机算法是通过计算机能执行的算法语言来表达的。 和程序的区别：一个程序包括两个方面的内容： （1）对数据的描述，即数据结构。 （2）对操作的描述，即算法。 所以算法是程序的一个要素。

2.3 何谓频度，时间复杂度，空间复杂度？说明其含义。

频度：在某个算法中某个语句被重复执行的次数就是此语句的频度。 时间复杂度：是用来估算一个算法的执行时间的量，以算法中频度最大的语句来度量。

空间复杂度：指在算法中所需的辅助空间的单元，而不包括问题的原始数据占用的空间。

2.4试编写一个求多项式Pn =anxn +an-1 xn-1+a1x+a0的值Pn(x 0)的算法，要求用乘法次数最少，并说明算法中主要语句的执行次数及整个算法的时间复杂度。

A=(a0, a1 ……an) mul ＝ 1 // sum=a0

for i=1 to n

mul ＝ mul * x // x

sum = A[i]*mul + sum //求和 end(i)

进行了n次

时间复杂度为：2n

2.5计算下列各片段程序中X←X+1执行次数 (1)

for i=1 to n for j=1 to i for k=1 to j x←x+1 end(k) end(j) end(i)

执行次数：n*n*n

(2) i←1

while i

for i=1 to n j←1

for k=j+1 to n

x← x+1 end(k) end(i)

执行次数：n*（n-1）

2.6 数据的存储结构主要有哪两种?它们之间的本质区别是什么？ 数据的存储结构：向量和链表。 本质区别：

向量是连续存放的，其存储空间是静态分配的，以存放顺序来表达元素的前后件的关系。

链式存储结果不需要一组连续的存储单元，其数据元素可以分散存放在存储空间中，其元素关系由指针来指向。

2.8已知线性表L(a1, a2, … , an ) 元素按递增有序排列。用向量作为存储结构，试编写算法：删除表中值在c与d之间(c<=d)的元素 大于等于c 序号4 大于d

序号11

a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13a14 a15 0

找到第1个大于等于c的元素，序号为s 找到第一个大于d的元素，序号为t L[s] ← L[t]

L[s+1] ← L[t+1]…

L[s+m] ← L[t+m] // s+m = t -1 m = t – s - 1 L[s + i ] ← L[t + i ] // i = 0 to t-s-1

i=1; // i 从1 循环到n

s = -1; // 第1个大于等于c的元素序号 t = -1; // 第1个大于d的元素序号 for i = 1 to n step -1

if s ==-1 and L[i]>=c // 找到第1个大于等于c的元素 s = i

if t == -1 and L[i] >d // 找到第1个大于d的元素 t = i ; end (i)

if s != -1 and t !=-1 i = s

while i < t and i + t – s <=n L[i] = L [i + t – s ] i++ end(while) else

return(错误 没有找到 元素在c和d之间) end(if)

for j=c to n-d+c

L[j]<--L[j+d-c]//把j+d-c项给j

End(j)

N<--n-d+c//所有项数减少 Return

2.9 线性表A，B中的元素为字符串类型，用向量结构存储，试编写算法，判断B是否为A的子序列（例如A=ENGLISH ，B=LIS ，则B为A的子序列）

A[m] B[n]

A： a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13a14 a15 B： b1 b2 b3 b4 b5 b6

i=1 检查A中第1个元素开始的字符串是否与B匹配 i=2 检查A中第2个元素开始的字符串是否与B匹配 … …

i= m – n + 1 检查 A中 第(m-n+1)个元素开始的字符串是否与B匹配

A[m] B[n]

if ( m

if j>n then return( A字符串中第i个字符开始的子串与B匹配 ) end(i)

renturn (找不到匹配的子串)

设A，B两个线性表的元素个数为m，n If (m<=n)then{return} For i=0 to n-1

a=A[i]

for j=0 to m-1

if(a=B[j])then{b++} end(j) end(i)

if(b=m)then{B 为A的子集} return

本文来源：https://www.bwwdw.com/article/6ist.html