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

第二章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=a0for i=1 to nmul mul * x / xsum = Ai*mul + sum /求和end(i)进行了 n 次时间复杂度为：2n2.5 计算下列各片段程序中 XX+1 执行次数(1)for i=1 to nfor j=1 to ifor k=1 to jxx+1end(k)end(j)end(i)执行次数：n*n*n(2)i1while i=c / 找到第 1 个大于等于 c 的元素s = i if t = -1 and Li d / 找到第 1 个大于 d 的元素t = i ; end (i)if s != -1 and t !=-1i = s while i n then return( A 字符串中第 i 个字符开始的子串与 B 匹配 ) end(i)renturn (找不到匹配的子串)设 A，B 两个线性表的元素个数为 m，nIf (m=n)thenreturnFor i=0 to n-1a=Aifor j=0 to m-1if(a=Bj)thenb+end(j)end(i)if(b=m)thenB 为 A 的子集 returna1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a130a14 a15b1 b2 b3 b4 b5 b62.11 写一个将向量 L（a 1 ，a 2， an）倒置的算法。对 L(a1，a 2, . ., an )如果是奇数个元素，则1, 15 交换 1, n 交换2，14 交换 2, n-1 交换3，13 交换 3，n-2 交换 4，12 交换 4，n-3 交换5，11 交换 5，n-4 交换6，10 交换 6，n-5 交换7，9 交换 7，n-6 交换8，8 交换 8，n-7 交换9，7 交换 9，n-8 交换？ 停止！如果是偶数个元素，则1，14 交换 1, n 交换2，13 交换 2, n-1 交换3，12 交换 3，n-2 交换4，11 交换 4，n-3 交换5，10 交换 5，n-4 交换6，9 交换 6，n-5 交换7，8 交换 7，n-6 交换8，7 交换？ 8，n-7 交换？ 停止！小结：n 个元素倒置的算法是，i = 1while ( in-i+1)ai 与 an-i+1 交换i+end(while) a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a130a14 a15a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a130a14 a152.12 试编写算法求已知单链表长度，并考虑表空的情况。p = headi = 0While(p!=nil) /表不为空P- next(p)/移动到下一个元素i+End(while)Return i /返回数据的个数head2.13 试编写算法删除单链表中第 k 个结点。GETNODE(q)GETNODE(p)q-headFor i=1 to k-1q-next(q)End(i)P-next(q);next(q)-next(p)Ret(p)Return标签2.14 已知一循环链表中数值已按递增有序排列现要插入一个新结点，并使插入一个新节点，并使插入后链表仍为有序序列GETNODE(p)Data(p)=aWhile(data(p)data(n)n-next(n)End(while)q -nnext(p) -next(q)-preturn2.18 设在长度大于 1 的循环链表中，即无头结点，也无头指正，p 为指向链表中每个节点的指针，试编写算法删除该节点的前趋结点。q-Next(p)/找到该节点的前趋结点p-next(q);next(q)-next(p)RET(p)Return2.20 试用单链表表示两个多项式：A=4X 12 +5X8+6X3+4 ,B=3X12+6X7+2X4+5(1)设计此两个多项式的数据结构-1 A 0 4 3 6 8 5 12 4-1 B 0 5 4 2 7 6 12 3(2)写出两个多项式相加的算法II 答案参见 33 页即可2.22 CQ0:10为一循环队列，初态 front=rear=1，画出下列操作后队的头，尾指示器状态：(1)d,e,b,g,h 入队；rear=6 front=1(2)d，e 出队 rear=6 front=3(3)I,j,k,l,m 入队 rear=0 front=3(4)b 出队 rear=0 front=4(5)n,o,p,q,r 入队 rear=5 front=42.25 有一个二维数组 A1:m ;1:n,假设 A3,2地址为 1110，A2，3地址为1115，若每个单元占一个空间，问 A1,4的地址是多少答案：11202.26 用三维数组和带行辅助向量形式表示下列稀疏矩阵：答案：(1)1 1 151 4 221 6 -152 2 112 3 33 4 -65 1 916 3 28I 1 2 3 5 6Pos 1 2 4 1 3Num 3 2 1 1 1(2)参考上面的，和 47，48 页的内容2.28 将题图 2.3 的一般树