在一个由小到大排列的n个数的数列中，在其中插入一个数，输出前后两个数组，并将挤出的最大数返回给主函数输出
[问题点数：20分，结帖人Kimimarolong]
在一个由小到大排列的n个数的数列中，在其中插入一个数，输出前后两个数组，并将挤出的最大数返回给主函数输出
[问题点数：20分，结帖人Kimimarolong]
不显示删除回复
显示所有回复
显示星级回复
显示得分回复
只显示楼主
匿名用户不能发表回复！|c题库题目_c题库题目doc下载_爱问共享资料
c题库题目.doc
c题库题目.doc
c题库题目.doc
简介：本文档为《c题库题目doc》，可适用于考试题库领域，主题内容包含程序填空从键盘上输入两个复数的实部与虚部求出并输出它们的和、积、商。以下程序的功能如(图)。|x|x&f=xxsinxx&输入三个整数x,y,z请把符等。
侵权或盗版
*若权利人发现爱问平台上用户上传内容侵犯了其作品的信息网络传播权等合法权益时，请按照平台要求书面通知爱问！
赌博犯罪类
在此可输入您对该资料的评论~
添加成功至
资料评价：第 5章 数组和广义表一、选择题 1.设有一个 10 阶的对称矩阵 A，采用压缩存储方式，以行序为主存储，a11 为第一元素，其 存储地址为 1，每个元素占一个地址空间，则 a85 的地址为（ ）【燕山大学 2001 一、2 。 （2 分） 】 A. 13 B. 33 C. 18 D. 40 2. 有一个二维数组 A[1:6， 0:7] 每个数组元素用相邻的 6 个字节存储， 存储器按字节编址， 那么这个数组的体积是（①）个字节。假设存储数组元素 A[1，0]的第一个字节的地址是 0， 则存储数组 A 的最后一个元素的第一个字节的地址是（②） 。若按行存储，则 A[2，4]的第 一个字节的地址是（③） 。若按列存储，则 A[5，7]的第一个字节的地址是（④） 。就一般情 况而言，当（⑤）时，按行存储的 A[I，J]地址与按列存储的 A[J，I]地址相等。供选择的 答案： 【上海海运学院 1998 二、2 （5 分） 】 ①-④： A．12 B. 66 C. 72 D. 96 E. 114 F. 120 G. 156 H. 234 I. 276 J. 282 K. 283 L. 288 ⑤： A．行与列的上界相同 B. 行与列的下界相同 C. 行与列的上、下界都相同 D. 行的元素个数与列的元素个数相同 3. 设有数组 A[i,j]，数组的每个元素长度为 3 字节，i 的值为 1 到 8 ，j 的值为 1 到 10， 数组从内存首地址 BA 开始顺序存放，当用以列为主存放时，元素 A[5，8]的存储首地址为 ( )。 A. BA+141 B. BA+180 C. BA+222 D. BA+225 【南京理工大学 1997 一、8 （2 分） 】 4. 假设以行序为主序存储二维数组 A=array[1..100，1..100]，设每个数据元素占 2 个存 储单元，基地址为 10，则 LOC[5，5]=（ ）【福州大学 1998 一、10 (2 分)】 。 A. 808 B. 818 C. 1010 D. 1020 5. 数组 A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为 1000 的内存单元中，则元素 A[5，5]的地址是( )。 【南京理工大学 2001 一、13 （1.5 分） 】 A. 1175 B. 1180 C. 1205 D. 1210 6. 有一个二维数组 A[0:8,1:5],每个数组元素用相邻的 4 个字节存储，存储器按字节编址， 假设存储数组元素 A[0,1]的第一个字节的地址是 0， 存储数组 A 的最后一个元素的第一个字 节的地址是（ ① ） 。若按行存储，则 A[3,5]和 A[5,3]的第一个字节的地址是（ ② ） 和（ ③ ） 。若按列存储，则 A[7,1]和 A[2,4]的第一个字节的地址是（ ④ ）和（ ⑤ ） 。 【上海海运学院 1996 二、1 （5 分） 】 ①-⑤:A.28 B.44 C.76 D.92 E.108 F.116 G.132 H.176 I.184 J.188 7. 将一个 A[1..100，1..100]的三对角矩阵，按行优先存入一维数组 B[1‥298]中，A 中元 素 A6665（即该元素下标 i=66，j=65） ，在 B 数组中的位置 K 为（ ） 。供选择的答案： A. 198 B. 195 C. 197 【北京邮电大学 1998 二、5 （2 分） 】 8. 二维数组 A 的元素都是 6 个字符组成的串，行下标 i 的范围从 0 到 8，列下标 j 的范圈 从 1 到 10。从供选择的答案中选出应填入下列关于数组存储叙述中（ ）内的正确答案。 （1）存放 A 至少需要（ ）个字节； （2）A 的第 8 列和第 5 行共占（ ）个字节； （3）若 A 按行存放，元素 A[8，5]的起始地址与 A 按列存放时的元素（ ）的起始地址一致。 供选择的答案： （1）A. 90 B. 180 C. 240 D. 270 E. 540 （2）A. 108 B. 114 C. 54 D. 60 E. 150 （3）A. A[8,5] B. A[3,10] C. A[5,8] D. A[0,9] 【山东工业大学 2000 三、1 （4 分） 【山东大学 1998 三、1 (4 分)】 】 9. 二维数 组 A 的每 个元素是 由 6 个 字符组成的串，其 行下 标 i=0,1,? ,8,列下 标 j=1,2,?,10。 A 按行先存储， 若 元素 A[8,5]的起始地址与当 A 按列先存储时的元素 （ ） 的起始地址相同。设每个字符占一个字节。 【西安电子科技大学 1998 一、2 （2 分） 】 A. A[8,5] B. A[3,10] C. A[5,8] D. A[0,9] 10. 若对 n 阶对称矩阵 A 以行序为主序方式将其下三角形的元素(包括主对角线上所有元素) 依次存放于一维数组 B 1..(n(n+1))/2］ 则在 B 中确定 aij ［ 中， （i&j） 的位置 k 的关系为( )。 A. i*(i-1)/2+j B. j*(j-1)/2+i C. i*(i+1)/2+j D. j*(j+1)/2+i 【北京航空航天大学 2000 一、2 （2 分） 】 11. 设 A 是 n*n 的对称矩阵， A 的对角线及对角线上方的元素以列为主的次序存放在一维 将 数组 B[1..n(n+1)/2]中， 对上述任一元素 aij(1≤i， j≤n， i≤j)在 B 中的位置为( 且 )。 A. i(i-l)/2+j B. j(j-l)/2+i C. j(j-l)/2+i-1 D. i(i-l)/2+j-1 【南京理工大学 1999 一、9（2 分） 】 12. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组 T[N（N+1）/2] 中，则对任一上三角元素 a[i][j]对应 T[k]的下标 k 是（ ）【青岛大学 2002 二、6 （2 。 分） 】 A. i（i-1）/2+j B. j（j-1）/2+i C. i（j-i）/2+1 D. j（i-1）/2+1 13. 设二维数组 A[1.. m，1.. n]（即 m 行 n 列）按行存储在数组 B[1.. m*n]中，则二维数 组元素 A[i，j]在一维数组 B 中的下标为( )。 【南京理工大学 1998 一、2 （2 分） 】 A.（i-1）*n+j B.（i-1）*n+j-1 C. i*（j-1） D. j*m+i-1 14. 有一个 100*90 的稀疏矩阵，非 0 元素有 10 个，设每个整型数占 2 字节，则用三元组表 示该矩阵时，所需的字节数是（ ）【南京理工大学 1999 二、8 （2 分） 。 】 A. 60 B. 66 C. 18000 D. 33 15. 数组 A[0..4,-1..-3,5..7]中含有元素的个数（ ）【中山大学 1998 二、5（2 分） 。 】 A. 55 B. 45 C. 36 D. 16 16. 用数组 r 存储静态链表，结点的 next 域指向后继，工作指针 j 指向链中结点，使 j 沿 链移动的操作为( )。 【南京理工大学 2001 一、16（1.5 分） 】 A. j=r[j].next B. j=j+1 C. j=j-&next D. j=r[j]-& next 17. 对稀疏矩阵进行压缩存储目的是（ ）【北京工商大学 2001 一、1 (3 分)】 。 A．便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间 复杂度 18. 已知广义表 L=（ （x,y,z） （u，t，w），从 L 表中取出原子项 t 的运算是（ ，a， ） ） 。 A. head（tail（tail（L）） ） B. tail（head（head（tail（L）） ）） C. head（tail（head（tail（L）） ）） D. head（tail(head（tail（tail（L））)） ） 【北京邮电大学 1998 二、4（2 分） 】 19. 已知广义表 LS＝((a,b,c),(d,e,f)),运用 head 和 tail 函数取出 LS 中原子 e 的运算是 ( )。 A. head(tail(LS)) B. tail(head(LS)) C. head(tail(head(tail(LS))) D. head(tail(tail(head(LS))))【西安电子科技大学 2001 应用一、3（2 分） 】 20. 广义表 A=(a,b,(c,d),(e,(f,g))),则下面式子的值为 （ ） 。 【北京邮电大学 1999 一、 2（2 分） 】 Head(Tail(Head(Tail(Tail(A))))) A. (g) B. (d) C. c D. d 21. 已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果: tail(head(tail(C))) =( )。 【长沙铁道学院 1998 三、4 (2 分)】 A.（a） B. A C. a D. (b) E. b F. (A) 22. 广义表运算式 Tail(((a,b),(c,d)))的操作结果是（ ）【西安电子科技大学 1998 。 一、4（2 分） 】 A. (c,d) B. c,d C. ((c,d)) D. d 23. 广义表 L=（a， （b，c），进行 Tail（L）操作后的结果为（ ）【中山大学 1999 一、 ） 。 10】 A. c B. b，c C.（b，c） D.（ （b，c） ） 24. 广义表（ （a,b,c,d） ）的表头是（ ） ，表尾是（ ）【青岛大学 2002 二、7 （2 。 分） 】 A. a B.（） C.（a,b,c,d） D.（b,c,d） 25. 广义表（a,(b,c),d,e）的表头为（ ）【中山大学 1998 二、6（2 分） 。 】 A. a B. a,(b,c) C. (a,(b,c)) D. (a) 26. 设广义表 L=（ （a,b,c），则 L 的长度和深度分别为（ ） ）【武汉大学 2000 二、9】 。 A. 1 和 1 B. 1 和 3 C. 1 和 2 D. 2 和 3 27. 下面说法不正确的是( )。 【南京理工大学 2001 一、3 （1.5 分） 】 A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表 C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构 二、判断题 1. 数组不适合作为任何二叉树的存储结构。（ ）【南京航空航天大学 1995 五、2 （1 分） 】 2. 从逻辑结构上看，n 维数组的每个元素均属于 n 个向量。（ ） 【东南大学 2001 一、2 （1 分）【中山大学 1994 】 一、2 （2 分） 】 3. 稀疏矩阵压缩存储后， 必会失去随机存取功能。 （ ） 【中科院软件所 1997 一、 （1 1 分） 】 4. 数组是同类型值的集合。 （ ） 【上海海运学院 1996 一、3（1 分）1999 一、4（1 分） 】 5. 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。 （ ） 【上海交通大学 1998 一、5】 6. 一个稀疏矩阵 Am*n 采用三元组形式表示， 若把三元组中有关行下标与列下标的值互换， 并把 m 和 n 的值互换，则就完成了 Am*n 的转置运算。（ ） 【西安交通大学 1996 二、8 (3 分)】 7. 二维以上的数组其实是一种特殊的广义表。（ ） 【北京邮电大学 2002 一、5 （1 分） 】 8. 广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（ ） 【南京航空航天大学 1996 六、2 （1 分） 】 9. 若一个广义表的表头为空表，则此广义表亦为空表。（ ）【中科院软件所 1997 一、8（1 分） 【长沙铁道学院 1998 一、8 (1 分)】 】 10. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。 （ ） 【合肥工业大学 2000 二、3 （1 分） 】 11. 所谓取广义表的表尾就是返回广义表中最后一个元素。 （ ） 【合肥工业大学 2001 二、 3 （1 分） 】 12. 广义表的同级元素（直属于同一个表中的各元素）具有线性关系。 （ ） 【华南理工大学 2002 一、9（1 分） 】 13. 对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。 （ ） 【华南理工大学 2002 一、10（1 分） 】 14. 一个广义表可以为其它广义表所共享。 （ ） 【山东大学 2001 一、2（1 分） 】 三、 填空题 1. 数组的存储结构采用_______存储方式。 【中山大学 1998 一、6（1 分） 】 2. 设二维数组 A[-20..30,-30..20], 每个元素占有 4 个存储单元, 存储起始地址为 200. 如按行优先顺序存储,则元素 A[25,18]的存储地址为__（1）_；如按列优先顺序存储,则元 素 A[-18,-25]的存储地址为__（2）_。 【北方交通大学 1999 二、3（4 分） 】 3. 设数组 a[1..50,1..80]的基地址为 2000， 每个元素占 2 个存储单元， 若以行序为主序顺 序存储， 则元素 a[45,68]的存储地址为_ （1） _;若以列序为主序顺序存储， 则元素 a[45,68] 的存储地址为_（2）_。 【华中理工大学 2000 一、5（2 分） 】 4. 将整型数组 A[1..8，1..8]按行优先次序存储在起始地址为 1000 的连续的内存单元中， 则元素 A[7，3]的地址是：_______。 【合肥工业大学 1999 三、4（2 分） 】 5. 二维数组 a[4][5][6]（下标从 0 开始计，a 有 4*5*6 个元素） ，每个元素的长度是 2，则 a[2][3][4]的地址是____。(设 a[0][0][0]的地址是 1000,数据以行为主方式存储) 【南京理工大学 2000 二、11（1.5 分） 】 6. 设有二维数组 A[0..9,0..19],其每个元素占两个字节，第一个元素的存储地址为 100， 若按列优先顺序存储， 则元素 A[6,6]存储地址为_______。【北京工商大学 2001 二、 （4 5 分） 】 7. 已知数组 A[0..9,0..9]的每个元素占 5 个存储单元， 将其按行优先次序存储在起始地址 为 1000 的连续的内存单元中，则元素 A[6，8]的地址为_______。 【合肥工业大学 2001 三、 4（2 分） 】 8. 已知二维数组 A[1..10，0..9]中每个元素占 4 个单元，在按行优先方式将其存储到起始 地址为 1000 的连续存储区域时，A[5，9]的地址是：_______。 【厦门大学 2002 六、5 （4 分）】 9. 用一维数组 B 与列优先存放带状矩阵 A 中的非零元素 A[i,j] (1≤i≤n,i-2≤j≤i+2),B 中的第 8 个元素是 A 中的第_（1）_行，第_（2）_列的元素。 【北京邮电大学 2001 二、3 （4 分） 】 10. 设数组 A[0..8,1..10],数组中任一元素 A[i,j]均占内存 48 个二进制位， 从首地址 2000 开始连续存放在主内存里，主内存字长为 16 位，那么 （l） 存放该数组至少需要的单元数是_______; （2） 存放数组的第 8 列的所有元素至少需要的单元数是_______; （3） 数组按列存储时，元素 A[5,8]的起始地址是_______。 【中国矿业大学 2000 一、 4（4 分） 】 11．设 n 行 n 列的下三角矩阵 A 已压缩到一维数组 B[1..n*（n+1）/2]中，若按行为主序存储，则 A[i,j]对应的 B 中存储位置为_______。 【武汉大学 2000 一、1】 12. n 阶对称矩阵 a 满足 a[i][j]=a[j][i],i,j=1..n,，用一维数组 t 存储时，t 的长度为 __(1)______，当 i=j，a[i][j]=t[(2)],i&j,a[i][j]=t[(3)],i&j,a[i][j]=t[(4)]。 【青岛 大学 2001 六、1（3 分） 】 13．己知三对角矩阵 A【1..9,1..9】的每个元素占 2 个单元，现将其三条对角线上的元素 逐行存储在起始地址为 1000 的连续的内存单元中，则元素 A[7,8]的地址为______。 【合肥 工业大学 2000 三、4（2 分） 】 14. 设有一个 10 阶对称矩阵 A 采用压缩存储方式（以行为主序存储：a11=1），则 a85 的地 址为_______。 【西安电子科技大学 1999 软件 一、3 （2 分） 】 15. 所谓稀疏矩阵指的是_______。【厦门大学 2001 一、2 （14%/5 分） 】 16. 对矩阵压缩是为了_______。 【北京理工大学 2000 二、3（2 分） 】 17. 上三角矩阵压缩的下标对应关系为：_______。 【福州大学 1998 二、6 (2 分)】 【南京 大学 1999】 18. 假设一个 15 阶的上三角矩阵 A 按行优先顺序压缩存储在一维数组 B 中， 则非零元素 A9,9 在 B 中的存储位置 k=_______。 （注： 矩阵元素下标从 1 开始） 【北京工商大学 2001 二、 （4 1 分） 】19．设下三角矩阵 A= 如果按行序为主序将下三角元素 Ai j (i,j)存储在一个一维数组 B[ 1..n(n+1)/2]中，对 任一个三角矩阵元素 Aij ,它在数组 B 中的下标为_______。 【北方交通大学 2001 二、3】 20. 当广义表中的每个元素都是原子时，广义表便成了_______。 【长沙铁道学院 1998 二、 8 (2 分)】 21. 广义表的表尾是指除第一个元素之外，_______。 【中山大学 1998 一、7 （1 分） 】 22. 广义表简称表，是由零个或多个原子或子表组成的有限序列，原子与表的差别仅在于 (1)____。为了区分原子和表，一般用 (2)____表示表，用 (3)_____表示原子。一个表 的长度是指 (4)__，而表的深度是指__(5)__【山东工业大学 2000 一、3（3 分） 【山 】 东大学 1998 一、2 (3 分)】 23. 广义表的_______ 定义为广义表中括弧的重数。 【重庆大学 2000 一、5】 24．设广义表 L=((),()), 则 head(L)是(1)___；tail(L)是(2)____；L 的长度是(3)___； 深度是 (4)__。 【中科院计算所 1998 一、2（4 分）【中国科技大学 1998 一、2（4 分） 】 】 25. 已知广义表 A=(9,7,( 8,10,(99)),12)，试用求表头和表尾的操作 Head( )和 Tail( ) 将原子元素 99 从 A 中取出来。 【西安交通大学 1996 四、5 (5 分)】 26. 广义表的深度是_______。 【北京轻工业学院 2000 一、1（2 分） 】 27. 广义表(a,(a,b),d,e,((i,j),k))的长度是（1）_，深度是（2）_。 【山东大学 2001 三、 9 (2 分)】 【西安电子科技大学 2001 软件 一、5 （2 分） 【哈尔滨工业大学 2001 一、2 （2 】 分） 】 28. 已知广义表 LS=(a，(b，c，d)，e),运用 head 和 tail 函数取出 LS 中原子 b 的运算是_______。 【燕山大学 2001 二、2 （3 分） 】 29. 广义表 A=（（a，b）（c，d，e）） （ ， ），取出 A 中的原子 e 的操作是: _______。 【合肥工业大学 1999 三、5（2 分） 】 30. 设某广义表 H=（A， （a,b,c） ，运用 head 函数和 tail 函数求出广义表 H 中某元素 b ） 的运算式_______。 【北京科技大学 1997 一、5】 31. 广义表 A((( ),(a,(b),c)))，head(tail(head(tail(head(A))))等于 。 【合肥工业大学 2000 三、5（2 分） 】 32. 广义表运算式 HEAD(TAIL(((a,b,c),(x,y,z))))的结果是_______。 【西安电子科技大学 1999 软件 一、9（2 分） 】 33. 已知广义表 A=（（a，b）（c）（d，e）） （ ， ， ），head（tail（tail（head（A）） ））的结果 是_______。 【合肥工业大学 2001 三、5 （2 分） 】 34. 利用广义表的 GetHead 和 GetTail 操作， 从广义表 L=（apple， （ pear） banana， （ ， orange） ） 中分离出原子 banana 的函数表达式是_______。 【山东大学 2001 三、6 (2 分)】 35. 已知 a 数组元素共 5 个， 依次为 12， 10， 3， b 数组元素共 4 个， 5， 1； 依次为 4,6,8,15， 则执行如下所示的过程语句 sort 后得到 c 数组各元素依次为 15,12,10,8,6,5,4,3,1； 数组 a,b,c 的长度分别为 l=5,m=4,n=9 请在程序中方框内填入正确的成分，完成上述要求。 PROCEDURE VAR i, j, k, x: d: ARRAY[1..m] OF BEGIN FOR i:=1 TO m DO d[i]:=(1) ; i:=1; j:=1; k:=1; WHILE (i&=l) AND (j&=m) DO BEGIN IF a[i]&d[j] THEN BEGIN(2) ; (3) _END ELSE BEGIN (4)__; (5) __END; c[k]:=x; (6) END; WHILE(7) _DO BEGIN c[k]:=a[i]; k:=k+1; i:=i+1；END; WHILE(8) _DO BEGIN c[k]:=d[j]; k:=k+1; j:=j+1；END; END. {sort} 【上海交通大学 1998 七 (12 分)】 36. 下列程序段 search(a,n,k)在数组 a 的前 n(n&=1)个元素中找出第 k(1&=k&=n)小的值。 这里假设数组 a 中各元素的值都不相同。 #define MAXN 100 int a[MAXN],n,k; int search_c(int a[], int n, int k) {int low, high, i, j, m, k--,;low=0 ;high=n-1; do {i= j= t=a[low]; do{while (i&j && t&a[j]) j--;if (i&j) a[i++]=a[j]; while (i&j && t&=a[i]) i++ if (i&j) a[j--]=a[i]; } while (i&j); a[i]=t; if (1) ; if (i&k) low= (2) ; else high= (3) ; }while(4) _; return(a[k]); } 【上海大学 1999 一、1（8 分） 】 37. 完善下列程序，每小题在 PASCAL 语言（a）和 C 语言（b）中任选一题。下面是一个将 广义表逆置的过程。 例如原来广义表为 （a,b） （d,e）， （ ,c, ） 经逆置后为： （ （e,d） （b,a）。 ,c, ） （a）算法的 PASCAL 语言过程描述（编者略）（b）算法的 C 语言过程描述： ： typedef struct glistnode { struct glistnode * union{ struct{struct glistnode *hp,*} } }*glist, glist reverse(p) {glist q,h,t,s; if(p==NULL) q=NULL; else {if(1) { q=(glist)malloc(sizeof(gnode)); q-&tag=0; q-&val.data=p-&val. } else {(2) if (3) {t=reverse(p-&val.ptr.tp); s=t; while(s-&val.ptr.tp!=NULL) s=s-&val.ptr. s-&val.ptr.tp=(glist)malloc(sizeof(gnode)); s=s-&val.ptr.s-&tag=1;s-&val.ptr.tp=NULL; s-&val.ptr.hp=h; (4) __ } else {q=(glist)malloc(sizeof(gnode));q-&tag=1; q-&val.ptr.tp=NULL; (5) ; } } } return(q); } 【上海大学 2002 六、3 （10 分） 】 38. 完善下列程序，每小题在 PASCAL 语言（a）和 C 语言（b）中任选一题。下面的程序将 数列 1,2,3,?,n*n,依次按蛇型方式存放在二维数组 A[1..n,1..n]中。 (示意圖编者略)。 即 （a）算法的 PASCAL 语言程序描述（编者略）（b）算法的 C 语言程序描述： ：#define NMAX 10 #include “stdio.h” main() { int i,j,n,k,p,q,m; int a [NMAX][NMAX]; scanf(“%d”,&n); m=1; for(k=1；(1) ；k++) {if（k&n） q=k； else(2) __; for(p=1;p&=q;p++) {if(3) {i=q-p+1；j=p；} else{i=p；j=q-p+1；} if(4) {i=i+n-q；j=j+n-q；} a[i][j]=m；(5) _; } for（i=1；i&=n;i++） { for（j=1；j&=n；j++） printf（ “%4d”,a[i][j]）;printf(“\n”); } } } 【上海大学 2002 六、1 （10 分） 】 39. 约瑟夫环问题：设有 n 个人围坐一圈，并按顺时针方向 1—n 编号。从第 s 个人开始进 行报数， 报数到第 m 个人， 此人出圈， 再从他的下一个人重新开始从 1 到 m 的报数进行下去 ， 直到所有的人都出圈为止。 PROCEDURE Josef (A:ARRAY [1..n] OF s,m:integer); BEGIN FOR i:= 1 TO n DO A[i]:=i; sl:=s; FOR i:=n DOWNTO 2 DO BEGIN sl:= (1) __；//计算出圈人 s1 IF sl=0 THEN (2) _； w:=A[sl]; //A[s1]出圈 FOR j:= (3) __ DO A[j]:=A[j+1]; A[i]:=w; END; write('出圈序列为：’)；//输出出圈序列 FOR i :=n DOWNTO 1 DO write(A[i]); writeln ； END; 【华南师范大学 2000 五、2 (9 分)】 40. 设有一个背包可以放入的物品重量为 S，现有 n 件物品，重量分别为 W1，W2，...，Wn。 问能否从这 n 件物品中选择若干件放入背包，使得放入的重量之和正好是 S。设布尔函数 Knap(S，n)表示背包问题的解，Wi(i=1,2,...，n)均为正整数，并已顺序存储地在数组 W 中。 请在下列算法的下划线处填空，使其正确求解背包问题。 Knap(S，n) 若 S=0则 Knap←true 否则若（S&0）或(S&0 且 n&1) 则 Knap←false 否则若 Knap(1) , _=true 则 print(W[n])；Knap ←true 否则 Knap←Knap(2) _ , _ 【山东工业大学 1996 五（10 分）1998 二、1 （4 分） 】 四 应用题 1. 数组 A[1..8，-2..6，0..6]以行为主序存储，设第一个元素的首地址是 78，每个元素的 长度为 4，试求元素 A[4,2,3]的存储首地址。【厦门大学 1998 五、1 （5 分）】 2. 已知 b 对角矩阵（aij）n*n，以行主序将 b 条对角线上的非零元存储在一维数组中，每个 数据元素占Ｌ个存储单元，存储基地址为Ｓ，请用 i，j 表示出 aij 的存储位置。 【北方交通 大学 1996 三（10 分） 】 3. 数组 A 中， 每个元素 A[i,j]的长度均为 32 个二进位,行下标从-1 到 9， 列下标从 1 到 11， 从首地址 S 开始连续存放主存储器中，主存储器字长为 16 位。求： （1）存放该数组所需多少单元？ （2）存放数组第 4 列所有元素至少需多少单元？ （3）数组按行存放时，元素 A[7,4]的起始地址是多少？ （4）数组按列存放时，元素 A[4,7]的起始地址是多少？ 【大连海事大学 1996 四、1 (6 分)】 4．假设按低下标优先存储整型数组 A（-3:8,3:5,-4:0,0:7）时，第一个元素的字节存储地 址是 100，每个整数占 4 个字节，问 A（0，4，-2，5）的存储地址是什么？【清华大学 1996 三】 5．设有三维数组 A[-2:4,0:3,-5:1]按列序存放，数组的起始地址为 1210，试求 A(1,3,-2） 所在的地址。 【长沙铁道学院 1997 三、1 (3 分)】 6. 三维数组 A[1..10,-2..6,2..8]的每个元素的长度为 4 个字节，试问该数组要占多少个 字节的存储空间？如果数组元素以行优先的顺序存贮，设第一个元素的首地址是 100，试求 元素 A[5,0,7] 的存贮首地址。 【上海海运学院 1995 三（6 分） 1997 三（8 分） 】 7. 设有五对角矩阵 A=(aij)20*20，按特殊矩阵压缩存储的方式将其五条对角线上的元素存于 数组 A[-10：m]中，计算元素 A[15,16]的存储位置。 【东北大学 1999 一、2（4 分） 】 8． 数组 A[0..8, 1..10] 的元素是 6 个字符组成的串， 则存放 A 至少需要多少个字节？ A 的 第 8 列和第 5 行共占多少个字节？若 A 按行优先方式存储，元素 A[8,5]的起始地址与当 A 按列优先方式存储时的哪个元素的起始地址一致？ 【厦门大学 2000 五、3（14%/3 分）】 9. 若按照压缩存储的思想将 n×n 阶的对称矩阵 A 的下三角部分 （包括主对角线元素） 以行 序为主序方式存放于一维数组 B[1..n(n+1)/2]中，那么，A 中任一个下三角元素 aij(i≥j), 在数组 B 中的下标位置 k 是什么？【北京航空航天大学 1998 一、4（4 分） 】 10. 设 m×n 阶稀疏矩阵 A 有 t 个非零元素，其三元组表表示为 LTMA[1..（t+1）,1..3]， 试问： 非零元素的个数 t 达到什么程度时用 LTMA 表示 A 才有意义？ 【北京航空航天大学 1998 一、5（4 分） 】 11. 利用三元组存储任意稀疏数组时，在什么条件下才能节省存储空间。 【西北工业大学 1998 三、2(5 分)】 12. 对一个有 t 个非零元素的 Amn 矩阵, 用 B[0..t][1..3]的数组来表示，其中第 0 行的三个元素分别为 m,n,t, 从第一行开始到最后一行，每行表示一个非零元素；第一列为矩阵元 素的行号， 第二列为其列号， 第三列为其值。 对这样的表示法， 如果需要经常进行该操作--确定任意一个元素 A[i][j]在 B 中的位置并修改其值，应如何设计算法可以使时间得到改 善？【长沙铁道学院 1998 四、4 (6 分)】 13. 有一个二维数组 A[0:8,1:5],每个数组元素用相邻的 4 个字节存储,存储器按字节编址, 假设存储数组元素 A[0,1]的第一个字节的地址是 0,那么存储数组的最后一个元素的第一个 字节的地址是多少?若按行存储,则 A[3,5]和 A[5,3]的第一个字节的地址是多少?若按列存 储,则 A[7,1]和 A[2,4]的第一个字节的地址是多少?【上海海运学院 1999 三（10 分） 】 14. 设有三对角矩阵(ai,j)m╳n,将其三条对角线上的元素逐行的存于数组 B(1:3n-2)中，使得 B[k]=ai,j，求： （1）用 i,j 表示 k 的下标变换公式； 3 （2）若 n=10 ,每个元素占用 L 个单元，则用 B[K]方式比常规存储节省多少单元。 【西安电子科技大学 1996 二、4 （5 分） 】 15. 已知 A 为稀疏矩阵，试从空间和时间角度，比较采用两种不同的存储结构（二维数组和三元组表）完成求运算的优缺点。 【西安电子科技大学 1996 二、6（5 分） 】16. 特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能？为什么？ 【北京邮电大学 2001 三、1（5 分） 】 17. 试叙述一维数组与有序表的异同。 【西安电子科技大学 1999 计应用一、2（5 分） 】 18. 一个 n╳n 的对称矩阵，如果以行或列为主序存入内存，则其容量为多少？ 【西安电子科技大学 1999 计应用 一、3（5 分） 】 19. 给出数组 A∶ARRAY[3..8,2..6] OF INTEGER;当它在内存中按行存放和按列存放时，分 别写出数组元素 A[i,j]地址计算公式（设每个元素占两个存储单元）【南开大学 1998 一 。 (8 分)】 20. 已知 n 阶下三角矩阵 A（即当 i&j 时，有 aij=0） ，按照压缩存储的思想，可以将其主对 角线以下所有元素(包括主对角线上元素 )依次存放于一维数组 B 中，请写出从第一列开始 采用列序为主序分配方式时在 B 中确定元素 aij 的存放位置的公式。北京航空航天大学 1999 【 二(10 分)】 【中山大学 1999 三 2】 21. 设有三对角矩阵(aij)n*n，将其三条对角线上的元素逐行地存于数组 B(1:3n-2)中，使 得 B[k]=aij，求： （1）用 i,j 表示 k 的下标变换公式； （2）用 k 表示 i,j 的下标变化公式。 【山东科技大学 2001 一、6 （6 分）【长沙铁道学院 1997 五、1 (10 分)】 】 【东北大学 2002 一 (4 分)】 【北京工业大学 2000 二、1 (9 分)】 【南京航空航天大学 2000 四】 22. 算法 Print 及所引用的数组 A 的值如下，写出调用 Print(1)的运行结果（其中 n=15） 。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B C D E F G O O H 0 I J K L PROCEDURE print（i：integer） ； BEGIN IF（i&=n〉 AND （A[i] &&‘0’ THEN ） BEGIN Print（2*i） ；write（A[i]） ；Print（2*i+1） END； ； END； 【合肥工业大学 1999 四、1（5 分） 】23. 设数组 A 的长度为 2N，前 N 个元素 A[1..N]递减有序，后 N 个元素 A[N+1.. 2N]递增有 序， 2N 是 2 的整数次幂， k=log22N 为整数。 且 即 例如 A[1..8]=[90,85,50,10,30,65,80,100] 满足上述要求， 这里 N=4,k=3,A 的前 4 个元素和后 4 个元素分别递减和递增有序。 用此例调 用如下的 Demo 过程，并要求： （1）给出 for 循环中每次执行 PerfectShuffle（A,N）和 CompareExchange（A,N）的结果； （2）解释 Demo 的功能； （3）给出 Demo 的时间复杂度。 PROCEDURE PerfectShuffle(VAR A: N:integer) [ i:=1; j:=1; WHILE i&=N DO [ B[j]:=A[i]; B[j+1]:=A[i+N]; i:=i+1; j:=j+2; ] A[1..2N]:=B[1..2N]; //B copy to A ] PROCEDURE CompareExchange(VAR A: N:integer) [ j:=1; WHILE j&2N DO [ IF A[j]&A[j+1] THEN A[j]←→A[j+1]; //交换 A[j]和 A[j+1] j:=j+2; ] ] PROCEDURE Demo (VAR A:N:integer) //A 的长度为 2N,k=log22N 为整数 [ FOR i:=1 TO log22N DO [ PerfectShuffle(A,N); CompareExchange(A,N); ] ] 【中科院计算所 1998 四 （15 分） 【中国科技大学
分） 】 】 24. 现有算法及正整数 n 和数组 A 如下，求数组 C 的值。 VAR A,B,C:Array[1..100] FUNC AAA(s,t:integer): IF s=t THEN IF B[s]=0 THEN AAA:=S ELSE AAA:=-s ELSE BEGIN l:=AAA(s,(s+t) DIV 2); r:=AAA((s+t) DIV 2+1,t); IF l&0 THEN AAA:=l ELSE AAA:=r; IF (r&0) AND (A[l]&A[r]) THEN AAA:=r END ENDF; PROC BBB; FOR i:=1 TO n DO B[i]:=0; FOR i:=1 TO n DO B[AAA(1,n)]:=i; FOR i:=1 TO n DO C[B[i]]:=A[i]; ENDP; 初始值：n=10,A={121,22,323,212,636,939,828,424,55,262}; 【北京邮电大学 2002 五、1（10 分） 】25. 设有矩阵ａ且 a=执行下列语句后，矩阵ｃ和ａ的结果分别是什么？（1） FOR i:=1 TO 3 DO FOR j:=1 TO 3 DO c[i,j]:=a[a[i,j],a[j,i]] （2） FOR i:=1 TO 3 DO FOR j:=1 TO 3 DO a[i,j]:=a[a[i,j],a[j,i]] 【浙江大学 1997 三 (8 分)】26. 设矩阵 A 为 i:=1 TO 3 DO j:=1 TO 3 DO ① C[i,j]:=A[A[i,j],A[j,i]] 结果 C 矩阵的值是什么？ （2）所选择的下标 i,j 的次序有关系吗？ （3）在语句①中，用 A 代替 C，A 的结果值是什么？ （4）对 i,j 这对下标取反序，即 （3，3）（3，2）（3，1） ， ， ，??， （1，3）（1，2）（1，1） ， ， 重复执行 （3）,把所得结果与（3）中所得结果作比较。 【吉林大学 1995 二 (15 分)】 27. 指出下列算法中错误、低效之处，并将其改成一个正确且高效的算法。 PROCEDURE delk(A, m , last,i, k) ; ｛从数组 A[１..last]中删除第 i 个元素起的 k 个元素，m 为 A 上限｝ BEGIN IF(i&1) OR (i&last) OR(k&0) OR(last&m) THEN write ('error') ELSE FOR count: = 1 TO k TO [FOR j:=last DOWNTO i+1 DO A[j-1]:=A[j]; last:=last-1] ENDP;{delk} 【北方交通大学 1997 一 （10 分） 】 28. 设输入为整数数组 A[1..n]， 其中 1&=A[i]&=k(1&=i&=n)； 输出数组为 b[1..n]； c[1..k] 是临时工作空间；阅读下述算法后，回答下列问题： PROC Demo(A,B,k){ (1)FOR i:=1 TO k DO C[i]:=0; (2)FOR j:=1 TO n DO C[A[j]]:= C[A[j]]+1; (3)FOR i:=2 TO k DO C[i]:= C[i]+ C[i-1] (4)FOR j:=n DOWNTO 1 DO { (5) B[C[A[j]]]:=A[j]; (6)C[A[j]]:=C[A[j]]-1 } } (a).当标号（2）行的循环执行完后，C[i](1&=i&=n)的值有何意义？ （1）执行语句 FOR FOR(b).当标号（3）行的循环执行完后，C[i](1&=i&=n)的值有何意义？ (c).算法执行后，B 的内容有何特点？ (d).当 k=O(n)时，算法的时间复杂度是多少？ 【中科院软件所 1997 二、2（9 分） 】 29．上三角阵 A（N*N）按行主序压缩存放在数组 B 中，其中 A[i,j]=B[k].写出用 i，j 表示 的 k。 【北京工业大学 2001 二、1 (5 分)】 30. 设有上三角矩阵(aij)n*n，将其上三角中的元素按先行后列的顺序存于数组 B（1:m）中， 使得 B[k]= aij 且 k=f1(i)+f2(j)+c，请推导出函数 f1,f2 和常数 c，要求 f1 和 f2 中不含 常数项。 【中科院自动化所 1999】 【山东科技大学 2002 一、5 （6 分） 】31． 设矩阵 A= (1) 若将 A 视为对称矩阵，画出对其压缩存储的存储表，并讨论如何存取 A 中元素 aij (0&=i,j&4)； (2) 若将 A 视为稀疏矩阵，画出 A 的十字链表结构。 【北京科技大学 1997 三 （10 分） 】32. 设对称矩阵 A= （1）若将 A 中包括主对角线的下三角元素按列的顺序压缩到数组 S 中, 即 S: 1下标：10023000502 3 4 5 6 7 8 9 10 试求出 A 中任一元素的行列下标[i,j](1&=i,j&=4)与 S 中元素的下标 K 之间的关系. （2）若将 A 视为稀疏矩阵时,画出其三元组表形式压缩存储表。 【北京科技大学 1999 三 （10 分） 】33. 设对角线矩阵 A= （ 行列下标 i ,j 满足：1≤i,j≤5） （1）若将矩阵 A 压缩存储到数组 S 中： 1 2 1 0 1 2 1 0 0 0 1 3 5 下标： 1 2 3 4 5 6 7 8 9 10 11 12 13 试求出 A 中已存储之元素的行列下标（i， j）与 S 中元素的下标 K 之间的关系 （2） 若将 A 视为稀疏距阵时， 请画出其行逻辑链接顺序表。 【北京科技大学 2000 三(10 分)】 34．设有一个三维数组 a[c1:d1,c2:d2,c3:d3]，其中 ci:di 是第 i 维的界偶，如该数组在 内存中按行排列，且 a[c1,c2,c3]的地址为 a0，那么请导出下标变量 a[i1,i2,i3]的地址， 假设每个元素占 L 个单元。【山东师范大学 1999 四、1 （5 分） 】 35 ． 假 定 有 下 列 n ⅹn矩阵（n为奇数）A= 如果用一维数组 B 按行主次序存储 A 的非零元素，问： （1）A 中非零元素的行下标与列下标的关系； （2）给出 A 中非零元素 aij 的下标(i,j)与 B 中的下标 R 的关系; （3） 假定矩阵中每个元素占一个存贮单元且 B 的起始地址为 A0， 给出利用 aij 的下标(i,j) 定位在 B 中的位置公式。 【上海交通大学 1998 三(12 分)】 36. 对于一个对称矩阵采用压缩存储，只存放它的上三角部分， 并按列存放。例如对于一个 n*n 的对称矩阵 A (如右图) ，用一 个一维数组 B 来存放它的上三角部分： B=[A11，A12，A22，A13，A23，A33，A14，?，A1n，A2n，?，Ann] 同时有两个函数：MAX(i,j)和 MIN(i,j)，分别计算下标 i 和 j 中的大者与小者。试利用它们给出求任意一个 Aij 在 B 中存放 位置的公式。 （若式中没有 MAX(I,j)和 MIN（i，j）则不给分） 【清华大学 1997 五 (10 分)】 37. 用三元数组表示稀疏矩阵的转置矩阵,并简要写出解题步骤。 【山东工业大学 1995 五 （10 分） 】 38. 简述广义表属于线性结构的理由。【西北大学 2000 一、5 (3 分)】 39. 数组，广义表与线性表之间有什么样的关系？【西北工业大学 1998 一、2 (4 分)】 40. 什么是广义表？请简述广义表和线性表的主要区别。 【北京大学 1997 二、2 （5 分） 】 41. 求下列广义表的运算结果。 【南京航空航天大学 1998 三 （10 分） 】 （1）CAR(CDR(((a,b),(c,d),(e,f)))) （2）CDR(CAR(((a,b),(c,d),(e,f)))) （3）CAR(CDR(CAR(((a,b),(e,f))))) （4）CDR(CAR(CDR(((a,b),(e,f))))) （5）CDR(CDR(CAR(((a,b),(e,f))))) 注：CAR 运算相当于有些教材中的 Head 运算，CDR 运算相当于 Tail 运算。 42. 利用广义表的 Head 和Ｔail 运算，把原子 d 分别从下列广义表中分离出来，L1＝ (((((a),b),d),e))；L2＝（a,(b,((d)),e）。 【北方交通大学 1996 一、2（5 分） ） 】类似本题的另外叙述有：(1) 已知广义表 L=((((a))),((b)),(c),d)，试利用 head 和 tail 运算把原子项 c 从 L 中分离出来。 【北京邮电大学 1992 三、2（25/4 分）【青岛海洋大学 1999 一、6 （5 分） 】 】 (2) 画出下列广义表的存储结构图，并利用取表头和取表尾的操作分离出原子 e。 （ a,（ （）,ｂ）,（（ｅ））。 （ ））【清华大学 1995 二 （10 分） 】 (3) 已知广义表 A=((a,b,c),(d,e,f)) 试写出从表 A 中取出原子元素 e 的运算。 【西安电子科技大学 1996 二、3 （5 分） 】 (4)请将香蕉 banana 用工具 H( )—Head( )，T( )—Tail( )从 L 中取出。 L=(apple,(orange,(strawberry,(banana)),peach),pear) 【北京邮电大学 2000 三、2 （5 分） 】 (5) 试利用广义表取表头 head(ls)和取表尾 tail(ls)的基本运算， 将原子 d 从下列表中 分解出来，请写出每一步的运算结果。 L=((a,(b)),((c,d)),(e,f)) 【北京工商大学 2001 三 （10 分） 】 (6) 画出广义表 A=（a,（b,()）,(((),c))）的第一种存储结构（表结点第二指针指向 余表）图，并用取首元（head()）和取尾元（tail()）函数表示原子 c。 【北京工业大学 2001 二、2 (5 分)】 43. 画出下列广义表的两种存储结构图((),A,(B,(C,D)),(E,F))。 南京航空航天大学 1999 【 三（10 分） 】 44. 假设采用以下两种结点的链表作为广义表的存贮结构， 表结点： (tag=1,hp,tp), 元素 结点；(tag=0,data)。请画出下列广义表的存储结构图，并求它的深度和长度。 ( ( ) , ( ( ( ) ) , ( ( ( ) ) ) ) ) 【北方交通大学 1998 一（13 分） 】 45．知广义表 A=（（a）， ，c， ，（ （ ）（b） （a）（（d，e）） ）） （1）画出其一种存贮结构图； （2）写出表的长度与深度； （3）用求头部，尾部的方式求出 e。 【东北大学 1997 一、2 (5 分)】 46．画出具有共享结构广义表（（b,c）,d）,(a),((a),((b,c),d)),e,()）的存贮表示。 （ 【北京工业大学 1996 一、3 (6 分)】 47. 广义表的结点结构如下:(TAG,DATA,LINK)。其中 LINK 为指向表中下一元素的指针;TAG 为标志域；DATA 为数据域，具体含义如下: TAG=0 表示该结点为原子结点，DATA 为其数据； TAG=1 表示该结点为一个子表，DATA 为指向该子表的指针。 （1） 说明下列算法 A 的功能(注:算法中 p,t,m,n,r,q 为指针;算法中的 NIL 对应图中的^) PROCEDURE A(p,t) BEGIN q:=NIL; WHILE p&&NIL DO BEGIN IF p^.TAG&&0 THEN BEGIN m:=p^.DATA; A(m,n); p^.DATA:=n; END; r:=p^.LINK; p^.LINK:=q; q:=p; p:=r END;t:=q; END. （2）对于 p 所指的广义表,画出执行算法 A 后的表结构以及 p，t 的值:【北方交通大学 1993 六（20 分） 】类似本题的另外叙述有：题目基本相同， 差别仅在于子表(b,c)与原子 d 的前后顺序颠倒。浙江大学 1994 六 (7 【 分)】 48. 写出对广义表 A=(x,((a,b),c,d))作运算 head(head(tail(A)))后的结果。 【西安电子科技大学 2000 计应用 一、5（5 分） 】 49．写出广义表的运算结果: TAIL[HEAD[TAIL[((a,b),(c,d))]]]=? 【武汉交通科技大学 1996 二、7 (3 分)】 50. 广义表中原子个数是否即为广义表的长度？ 【西安电子科技大学 2000 计应用一、 （5 9 分） 】 51. 给出下列所示的 3 元多项式的广义表表示（分别以 X1，X2，X3 第一到第三层变元） 5 3 5 2 4 5 3 3 4 2 P（X1X2X3）=X1 X2 X3+2X1 X2 X3 +5X1 X2 X3 +3X1X2 X3 +X2X3+6 【华南理工大学 2001 一、2（4 分） 】 52. 设某表 H 如下： A a1 a2 B b1 c1 C c2 X其中 A,B,C 为子表名，a1,a2,b1,c1,c2,x 为其元素。 （1）试用广义表形式表示 H,并写出运算 HEAD(H)和 TAIL(H) 函数从 H 中取出单元素 a2 的 运算； （2）画出表 H 的链式存储结构； 【北京科技大学 1998 三（10 分） 】 五 算法设计题 1. 设有大小不等的 n 个数据组（n 个数据组中数据的总数为 m） ，顺序存放在空间区 D 内, 每个数据占一个存储单元，数据组的首地址由数组 S 给出， （如下图所示） ，试编写将新数据 x 插入到第 i 个数据组的末尾且属于第 i 个数据组的算法， 插入后， 空间区 D 和数组 S 的相 互关系仍保持正确。 【东北大学 2000 六 (15 分)】2. 以三元组表存贮的稀疏矩阵 A，B 非零元个数分别为 m 和 n。试用类 PASCAL 语言编写时 间复杂度为 O（m+n）的算法将矩阵 B 加到矩阵 A 上去。A 的空间足够大，不另加辅助空间。 要求描述所用结构。 【北京工业大学 1997 三 (10 分)】 3. 设整数 x1,x2,?,xN 已存放在数组 A 中，编写一 PASCAL 递归过程，输出从这 n 个数中取 出所有 k 个数的所有组合（k&=n） 。例：若 A 中存放的数是 1，2，3，4，5，k 为 3，则输出 结果应为：543，542，541，532，531，521，432，431，421，321。 【山东大学 1992 五 (13 分)】类似本题的另外叙述有：（1）题目基本相同，只是叙述不同，要求用 PASCAL 语言。 【东南大学 2001 三 （10 分） 】 4． 编写一个过程， 对一个 n×n 矩阵， 通过行变换， 使其每行元素的平均值按递增顺序排列。 【中科院软件所 1996 】 5. 设原来将 N 个自然数 1,2,?,N 按某个顺序存于数组 A 中， 经过下面的语句计算， A[I] 使 的值变为 A[1]到 A[I-1]中小于原 A[I]值的个数。 FOR I:=N DOWNTO 1 DO BEGIN C：=0； FOR J：=1 TO I-1 DO IF A[J]&A[I] THEN C：=C+1； A[I]：=C END； 编程将经过上述处理后的 A 还原成原来的 A。 【上海大学 1996 二 （16 分） 】 6．请编写完整的程序。如果矩阵 A 中存在这样的一个元素 A[i,j]满足条件:A[i,j]是第 i 行中值最小的元素,且又是第 j 列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程 计算出 m*n 的矩阵 A 的所有马鞍点。 【上海大学 2000 三 （20 分） 中科院自动化所 1997】 】 【 7． 给定一个整数数组 b[0..N-1]， 中连续的相等元素构成的子序列称为平台。 b 试设计算法， 求出 b 中最长平台的长度。 【中科院计算所 1999 五、2 （20 分） 】 8. 给定 nxm 矩阵 A[a..b,c..d],并设 A[i,j]≤A[i,j+1](a≤i≤b,c≤j≤d-1)和 A[i,j]≤ A[i+1,j](a≤i≤b-1,c≤j≤d).设计一算法判定 X 的值是否在 A 中,要求时间复杂度为 O(m+n)。 【东南大学 2001 六(13 分)】类似本题的另外叙述有：（1）给定整型数组 B[0..m,0..n] 。已知 B 中数据在每一维方向上都按从小到大的次序 排列，且整型变量 x 在 B 中存在。试设计一个程序段找出一对满足 B[i,j]=x 的(i,j)值，要 求比较次数不超过 m+n.。 【清华大学 1998 六（10 分） 】 (2) 给定 n×m 矩阵 A[a..b,c..d]，并设 A[i,j]&=A[i,j+1]（a&=i&=b,c&=j&=d-1）知 A[i,j]&=A[i+1,j],(a&=i&=b-1, c&=j&=d)。设计一算法以比 O(n*m)小的最坏时间复杂性判 定值 x 是否在 A 中。 【东南大学 1994 三(17 分)】 9. 编写算法，将自然数 1～n 按“蛇形”填入 n×n 矩阵中。例（1～4 ）如图所示： （用 程序实现）【南京航空航天大学 1997 八 （12 分） 【中科院计算所 1996】 】 10. 设二维数组 a[1..m, 1..n] 含有 m*n 个整数。 (1) 写出算法(pascal 过程或 c 函数)： 判断 a 中所有元素是否互不相同?输出相关信息 (yes/no)； (2) 试分析算法的时间复杂度。 【华中理工大学 1999 五 （10 分） 】 n 11. 二项式(a+b) 展开式的系数为 C（n，0）=1，C（n，n）=1，对于 n&=0 C（n，k）=C（n-1，k）+C（n-1，k-1） ，对于 0&k&n 形成著名的杨辉三角形，如图所 示。 (1)试写一个递归算法，根据以上公式生成 C（n,k）（6 分） 。 (2)试画出计算 C（6，4）的递归树。 分） （4 (3)试写一个非递归算法，既不用数组也不用栈，对于任意的 0&=k&=n 计算 C(n,k)（6 分）【清华大学 1999 五 （16 分） 】 12． 设任意 n 个整数存放于数组 A(1:n)中， 试编写程序， 将所有正数排在所有负数前面 （要 求算法复杂性为 0( n)） 【山东大学 1993 三 (12 分)】. 。类似本题的另外叙述有：（1）已知数组 A[1..n]的元素类型为整型，设计算法调整 A，使其左边的所有元素小于 零，右边的所有元素大于等于零。 （要求算法的时间复杂度和空间复杂度均为 0（n） ） 【北京理工大学 2000 四、1 （4 分） 】 （2）设计一个算法，把整数数组中所有的偶数放到所有的奇数之前。要求时间、空间效 率尽可能高。 【华南师范大学 1999 六、1 (10 分)】 （3）设一系列正整数存放在一个数组中，试设计算法，将所有奇数存放在数组的前半部 分，将所有的偶数存放在数组的后半部分。要求尽可能少用临时存储单元并使时间最少。请 试着分析你实现的算法的时间复杂度和空间复杂度。 【南开大学 2000 三、2】 （4）设计算法将数组 A[1..n]调整为左右两部分，使的左边所有的元素小于右边的所有 元素， 并给出这一划分的分界位置。 要求算法的时间复度为 O(n)。 【合肥工业大学 2001 五、 3 （8 分） 】 13.若 S 是 n 个元素的集合，则 S 的幂集 P(S)定义为 S 所有子集的集合。例如， S=(a,b,c),P(S)={() ,(a),(b),(c),(a,b),(a,c),(b,c),(a,b,c)}给定 S，写一递归算法求P(S)。 【东南大学 1993 五 （15 分）【东南大学 1997 五 （15 分） 】 】 14．编写算法打印出由指针 Hm 指向总表头的以十字链表形式存储的稀疏矩阵中每一行的非 零元的个数。注意：行、列及总表头结点的形式为： row down col val right它们已用 val 域链接成循环链表。 非零元的结点形式也同上， 每一行 （列） 的非零元由 right （down）域把它们链接成循环链表，该行（列）的表头结点即为该行（列）循环链表的表头。 【上海大学 1998 五 （16 分） 】 15. 试编写建立广义表存储结构的算法，要求在输入广义表的同时实现判断、建立。设广义 表按如下形式输入（a1,a2,a3,?,an） n&=0，其中 ai 或为单字母表示的原子或为广义表，n=0 时为只含空格字符的空表。(注:算法可用类 pascal 或类 c 书写) 【北京工业大学 1998 十 (15 分)】 16. 广义表是 n(n&=0)个数据元素 a1,a2,a3,?,an 的有限序列。其中 ai (1&=i&=n)或者是单 个数据元素（原子），或仍然是一个广义表。广义表的结点具有不同的结构，即原子结点和 子表元素结点，为了将两者统一，用了一个标志 tag，当其为 0 时表示是原子结点，其 data 域存储结点值，link 域指向下一个结点，当其 tag 为 1 时表示是子表结点，其 sublist 为 指向子表的指针。因此，广义表可采用如下结构存储： TYPE glist=^ gnode=RECORD link: CASE tag:0..1 OF 0:(data:char); 1:(sublist:glist) END; （1）画出广义表((a,b),c)的存储结构； （2）写出计算一个广义表的原子结点个数的递归算法表示式； （3）编写实现上述算法的过程或函数程序。【厦门大学 2002 三 （12 分）】 17. 广义表 GL=(a1,a2 ,?,an),其中 ak(k=1,2,...,n)或是单个数据元素（原子），或仍然 是个广义表。给定如下有关广义表的类型定义： TYPE tagtype=0..1; glist=^ gnode=RECORD link: {link 域指向下一个结点} CASE tag:tagtype OF ｛tag=0 表示原子结点｝ 0: (data :integer); 1:(sublist: glist) END; 编写一个过程或函数计算一个广义表的所有原子结点数据域之和，例如对广义表 (3,(2,4,5),(6,3）) 数据域之和为 23。【厦门大学 2000 四、2 （9 分）】 18. 数组 H[ 1：1000] 中存放着 1000 个大小不同的正整数; （1） 选择一分类算法使能最快地得到其中 10 个最大的数，简要说明理由；（2） 编写一程序 seek() ，执行该程序时，在命令行中提供二个参数； seek a n&enter& 表示需打印 H[ ]中 n 个最大数。 seek I n&enter& 表示需打印 H[ ]中 n 个最小数。 【浙江大学 1994 八 (18 分)】 19．已知两个定长数组，它们分别存放两个非降序有序序列，请编写程序把第二个数组序列 中的数逐个插入到前一个数组序列中，完成后两个数组中的数分别有序（非降序）并且第一 数组中所有的数都不大于第二个数组中的任意一个数。注意，不能另开辟数组，也不能对任 意一个数组进行排序操作。例如， 第一个数组为：4,12,28 第二个数组为：1,7,9,29,45 输出结果为：1,4,7--------------第一个数组 9,12,28,29,45---------第二个数组 【上海大学 1998 四 （20 分） 】 20. 设数组 A[1..n]中，A[n-2k+1..n-k]和[n-k+1..n]中元素各自从小到大排好序，试设计 一个算法使 A[n-2k+1..n]按从小到大次序排好序。并分析算法所需的计算时间。 【福州大学 1998 四、3 (10 分)】 21. 设 A[1..100]是一个记录构成的数组，B[1..100]是一个整数数组，其值介于 1 至 100 之间，现要求按 B[1..100]的内容调整 A 中记录的次序，比如当 B[1]=ll 时，则要求将 A[1] 的内容调整到 A[11]中去。 规定可使用的附加空间为 O(1)。 中科院计算所 2000 七 【 （15 分） 】 22. 给定有 m 个整数的递增有序数组 a[1..m]和有 n 个整数的递减有序数组 b[1..n]，试写 出算法:将数组 a 和 b 归并为递增有序数组 c[l..m+n]。 (要求： 算法的时间复杂度为 O(m+n)) 【华中理工大学 2000 八、1（10 分） 】 23．在数组 A[1..n]中有 n 个数据，试建立一个带有头结点的循环链表，头指针为 h，要求 链中数据从小到大排列，重复的数据在链中只保存一个。 【南京理工大学 1998 七、2 （7 分） 】第五章 数组和广义表一、选择题 1.B 6.4A 15.B 27.A 二、判断题 1. × 13.√ 2.√ 14.√ 3.√ 4.× 5.× 6. × 7.√ 8.× 9.× 10.× 11.× 12.√ 2.1L 6.5F 16.A 2.2J 7.B 17.C 2.3C 8.1E 18.D 2.4I 8.2A 19.C 2.5C 8.3B 20.D 3.B 9.B 21.F 4.B 10.B 22.C 5.A 11.B 23.D 6.1H 12.B 24.C 6.2C 13.A 25.A 6.3E 14.B 26.C部分答案解释如下。 1. 错误。对于完全二叉树，用一维数组作存储结构是效率高的（存储密度大） 。 4. 错误。数组是具有相同性质的数据元素的集合，数据元素不仅有值，还有下标。因此， 可以说数祖是元素值和下标构成的偶对的有穷集合。 5. 错误。数组在维数和界偶确定后，其元素个数已经确定，不能进行插入和删除运算。 6. 错误。稀疏矩阵转置后，除行列下标及行列数互换外，还必须确定该元素转置后在新三 元组中的位置。 8. 错误。广义表的取表尾运算，是非空广义表除去表头元素，剩余元素组成的表，不可能 是原子。9. 错误。广义表的表头就是广义表的第一个元素。只有非空广义表才能取表头。 10. 错误。广义表中元素可以是原子，也可以是表（包括空表和非空表） 。 11. 错误。广义表的表尾，指去掉表头元素后，剩余元素所组成的表。 三、填空题 1. 顺序存储结构 2.（1）28 3.（1）88 4. 64 公式：LOC(aijk)=LOC(a000)+[v2*v3*(i-c1)+v3*(j-c2)+(k-c3)]*l (l 为每个元素所 占单元数) 6. 232 7. 96 9. 第 1 行第 3 列 10. (1)270 (2)27 (3)2204 11. i(i-1)/2+j (1&=i,j&=n) 12. (1)n(n+1)/2 (2)i(i+1)/2 (或 j(j+1)/2) (3)i(i-1)/2+j (4)j(j-1)/2+i (1&=i,j&=n) 13. 1038 三对角矩阵按行存储：k=2(i-1)+j (1&=i,j&=n) 14. 33 (k=i(i-1)/2+j) (1&=i,j&=n) 15. 非零元很少(t&&m*n)且分布没有规律 16. 节省存储空间。 17. 上三角矩阵中，主对角线上第 r(1?r?n) 行有 n-r+1 个元素，aij 所在行的元素数是 j-i+1 。 所 以 ， 元 素 在 一 维 数 组 的 下 标 k 和 二 维 数 组 下 标 关 系:k=((i-1)*(2n-i+2))/2+(j-i+1)=(i-1)(2n-i)/2+j (i?j) 18. 93 19. i(i-1)/2+j 20. 线性表 21. 其余元素 组成的表 22. （1） 原子（单元素）是结构上不可再分的，可以是一个数或一个结构；而表带结构， 本质就是广义表，因作为广义表的元素故称为子表。 （2）大写字母 （3）小写字母 （4）表中元素的个数（5）表展开后所含括号的层数 23. 深度 24.（1） （） （2）（） （3）2 （4）2 （ ） 25. head（head（tail（tail（head（tail（tail（A）））） ））） 26. 表展开后所含括号的层数 27.（1）5 （2）3 28. head(head(tail(LS))) 29. head(tail(tail(head(tail(head(A)))))) 30. head(tail(head(tail(H)))) 31. (b) 32. (x,y,z) 33. (d,e) 34. GetHead(GetHead(GetTail(L))) 35. 本算法中， 首先数组 b 中元素以逆置顺序放入 d 数组中， 然后数组 a 和数组 d 的元素比 较， 将大者拷贝到数组 c。 第一个 WHILE 循环到数组 a 或数组 d 结尾， 第二个和第三个 WHILE 语句只能执行其中的一个。 （1）b[m-i+1]（2）x:=a[i]（3）i:=i+1（4）x:=d[j]（5）j:=j+1 （6）k:=k+1（7）i&=l （8）j&=m 36.（1）(i==k) return（2）i+1（3）i-1（4）i!=k 本算法利用快速排序思想，找到第 k 个元素的位置（下标 k-1 因而开初有 k--） 。内层 do 循环以 t(t=a[low])为“枢轴”找到其应在 i 位置。这时若 i 等于 k，则算法结束。 （即第一 个空格处 if(i==k) return)。否则，若 i&k，就在 i+1 至 high 中间去查；若 i&k，则在 low 到 i-1 间去找，直到找到 i=k 为止。 37.逆置广义表的递归模型如下f(LS)= 上面 appEND(a,b)功能是将广义表 a 和 b 作为元素的广义表连接起来。 （1）(p-&tag==0) //处理原子 （2）h=reverse(p-&val.ptr.hp) //处理表头 （3）(p-&val.ptr.tp) //产生表尾的逆置广义表 （4）s-&val.ptr.tp=t; //连接 （5）q-&val.ptr.hp=h //头结点指向广义表 38. 本题要求将 1，2，...,n*n 个自然数，按蛇型方式存放在二位数组 A[n][n]中。 “蛇型” 2 方式，即是按“副对角线”平行的各对角线，从左下到右上，再从右上到左下，存放 n 个 整数。对角线共 2n-1 条，在副对角线上方的对角线，题目中用 k 表示第 k 条对角线（最左 上角 k=1） ，数组元素 x 和 y 方向坐标之和为 k+1（即题目中的 i+j=k+1） 。副对角线下方第 k 条对角线与第 2n-k 条对角线对称，其元素的下标等于其对称元素的相应坐标各加(k-n)。 （1）k&=2*n-1 //共填 2*n-1 条对角线 （2）q=2*n-k //副对角线以下的各条对角线上的元素数 （3） k%2！ =0 //k 为偶数时从右上到左下， 否则从左下向右上填数。 （本处计算下标 i 和 j） （4）k&=n //修改副对角线下方的下标 i 和 j。 （5）m++；或 m=m+1 //为填下个数作准备，m 变化范围 1..n*n。 本题解法的另一种思路见本章算法设计题第 9 题。 39.本题难点有二： 一是如何求下一出圈人的位置， 二是某人出圈后对该人的位置如何处理。 按题中要求，从第 s 个人开始报数，报到第 m 个人，此人出圈。n 个人围成一圈，可看 作环状，则下个出圈人，其位置是(s+m-1)%n。n 是人数，是个变量，出圈一人减 1，算法中 用 i 表示。对第二个问题，算法中用出圈人后面人的位置依次前移，并把出圈人的位置（下 标）存放到当时最后一个人的位置（下标） 。算法最后打印出圈人的顺序。 （1）(s+m-1) MOD i //计算出圈人 s1 （2）s1:=i //若 s1=0,说明是第 i 个人出圈（i%i=0） （3）s1 TO i-1 //从 s1 到 i 依次前移，使人数减 1，并将出圈人放到当前最后一个 位置 A[i]=w。 40. 若第 n 件物品能放入背包， 则问题变为能否再从 n-1 件物品中选出若干件放入背包 （这 时背包可放入物品的重量变为 s-w[n]） 。若第 n 件物品不能放入背包，则考虑从 n-1 件物品 选若干件放入背包（这时背包可放入物品仍为 s） 。若最终 s=0,则有一解；否则，若 s&0 或 虽然 s&0 但物品数 n&1,则无解。 （1）s-w[n],n-1 //Knap(s-w[n],n-1)=true （2）s,n-1 // Knap←Knap(s,n-1) 四、应用题 1、958 三维数组以行为主序存储，其元素地址公式为： LOC(Aijk)=LOC(Ac1c2c3)+[(i-c1)V2V3+(j-c2)V3+(k-c3)]*L+1 其中 ci,di 是各维的下界和上界，Vi=di-ci+1 是各维元素个数，L 是一个元素所占的存储 单元数。2. b 对角矩阵的 b 条对角线，在主对角线上方和下方各有 ?b/2? 条对角线(为叙述方便，下 面设 a=?b/2?)。 从第 1 行至第 a 行， 每行上的元素数依次是 a+1,a+2,...,b-2,b-1,最后的 a 行上的元素个数是 b-1，b-2,...,a+1。中间的(n-2a )行，每行元素个数都是 b。故 b 条对 角线上元素个数为 (n-2a)b+a*(a+b)。存放在一维数组 V[1..nb-a(b-a)]中，其下标 k 与元 素在二维数组中下标 i 和 j 的关系为：k= 3．每个元素 32 个二进制位，主存字长 16 位，故每个元素占 2 个字长，行下标可平移至 1 到 11。 （1）242 （2）22 （3）s+182 （4）s+142 4．1784 (公式：Loc(Aijkl)=100(基地址)+[(i-c1)v2v3v4+(j-c2)v3v4+(k-c3)v4+(l-c4)]*4 5. L (LOC(A[1,3,-2])=1210+[(k-c3)v2v1+(j-c2)v1+(i-c1)]*L（设每个元素占 L 个 存储单元） 6. 数组占的存储字节数=10*9*7*4=2520； A[5,0,7]的存储地址=100+[4*9*7+2*7+5]*4=1184 7. 五对角矩阵按行存储，元素在一维数组中下标（从 1 开始）k 与 i,j 的关系如下:k= A[15,16]是第 71 个元素，在向量[-10:m]中的存储位置是 60 。 8． （1）540 （2）108 （3）i=3,j=10，即 A[3,10] 9． k=i(i-1)/2+j 10. 稀疏矩阵 A 有 t 个非零元素，加上行数 mu、列数 nu 和非零元素个数 tu(也算一个三元 组)，共占用三元组表 LTMA 的 3(t+1)个存储单元，用二维数组存储时占用 m*n 个单元，只 有当 3(t+1)&m*n 时，用 LTMA 表示 A 才有意义。解不等式得 t&m*n/3-1。 11．参见 10。 12. 题中矩阵非零元素用三元组表存储， 查找某非零元素时， 按常规要从第一个元素开始查 找，属于顺序查找，时间复杂度为 O(n)。若使查找时间得到改善，可以建立索引，将各行 行号及各行第一个非零元素在数组 B 中的位置（下标）偶对放入一向量 C 中。若查找非零元 素， 可先在数组 C 中用折半查找到该非零元素的行号， 并取出该行第一个非零元素在 B 中的 位置，再到 B 中顺序（或折半）查找该元素，这时时间复杂度为 O(logn)。 13． （1）176 （2）76 和 108 （3）28 和 116。 14． （1）k = 3(i-1) (主对角线左下角，即 i=j+1) k = 3(i-1)+1 (主对角线上，即 i=j) k = 3(i-1)+2 (主对角线上，即 i=j-1) 由以上三式，得 k=2(i-1)+j (1?i,j?n; 1?k?3n-2) 3 3 3 （2）10 *10 -(3*10 -2) 15. 稀疏矩阵 A 采用二维数组存储时，需要 n*n 个存储单元，完成求Σ aii(1&=i&=n)时，由 于 a[i][i]随机存取，速度快。但采用三元组表时，若非零元素个数为 t，需 3(t+1)个存储 单元（第一个分量中存稀疏矩阵 A 的行数，列数和非零元素个数，以后 t 个分量存各非零元 素的行值、列值、元素值） ，比二维数组节省存储单元；但在求Σ aii(1&=i&=n)时，要扫描整个三元组表，以便找到行列值相等的非零元素求和，其时间性能比采用二维数组时差。 16. 特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律， 因此可以对非零元素分 配单元（对值相同元素只分配一个单元） ，将非零元素存储在向量中，元素的下标 i 和 j 和 该元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。而稀疏矩 阵是指非零元素和矩阵容量相比很小（t&&m*n） ，且分布没有规律。用十字链表作存储结构 自然失去了随机存取的功能。 即使用三元组表的顺序存储结构， 存取下标为 i 和 j 的元素时， 要扫描三元组表，下标不同的元素，存取时间也不同，最好情况下存取时间为 O(1)，最差 情况下是 O(n)，因此也失去了随机存取的功能。 17．一维数组属于特殊的顺序表，和有序表的差别主要在于有序表中元素按值排序（非递增 或非递减） ，而一维数组中元素没有按元素值排列顺序的要求。 2 18．n(n+1)/2（压缩存储） 或 n （不采用压缩存储） 19．LOC（A[i,j]）=LOC（A[3，2]）+[（i-3）*5+（j-2）]×2 （按行存放） LOC（A[i,j]）=LOC（A[3，2]）+[（j-2）*6+（i-3）]×2 （按列存放） 20．n 阶下三角矩阵元素 A[i][j]（1&=i,j&=n,i&=j） 。第 1 列有 n 个元素，第 j 列有 n-j+1 个元素，第 1 列到第 j-1 列是等腰梯形，元素数为(n+(n-j+2)(j-1)/2，而 aij 在第 j 列上的 位置是为 i-j+1。所以 n 阶下三角矩阵 A 按列存储，其元素 aij 在一维数组 B 中的存储位置 k 与 i 和 j 的关系为： k=(n+(n-(j-1)+1)(j-1)/2+(i-j+1)=(2n-j)(j-1)/2+i 21．三对角矩阵第一行和最后一行各有两个非零元素，其余每行均有三个非零元素，所以共 有 3n-2 个元素。 （1） 主对角线左下对角线上的元素下标间有 i=j+1 关系， 与 i 和 j 的关系为 k=3(i-1); k 主对角线上元素下标间有关系 i=j，k 与 i 和 j 的关系为 k=3(i-1)+1; 主对角线右上那条对 角线上元素下标间有关系 i=j-1，k 与 i 和 j 的关系为 k=3(i-1)+2。综合以上三等式，有 k=2(i-1)+j (1&=i,j&=n, |i-j|&=1) （2）i=k/3+1； （1≤k≤3n-2） // k/3 取小于 k/3 的最大整数。下同 j=k-2(i-1)=k-2(k/3)=k%3+k/3 22．这是一个递归调用问题，运行结果为：DBHEAIFJCKGL 23.（1）FOR 循环中，每次执行 PerfectShuffle(A,N)和 CompareExchange(A,N)的结果： 第 1 次：A[1..8]=[90,30,85,65,50,80,10,100] A[1..8]=[30,90,65,85,50,80,10,100] 第 2 次：A[1..8]=[30,50,90,80,65,10,85,100] A[1..8]=[30,50,80,90,10,65,85,100] 第 3 次：A[1..8]=[30,10,50,65,80,85,90,100] A[1..8]=[10,30,50,65,80,85,90,100] （2）Demo 的功能是将数组 A 中元素按递增顺序排序。 （3）PerfectShuffle 中 WHILE 循环内是赋值语句，共 2N 次，WHILE 外成组赋值语句， 相当 2N 个简单赋值语句；CompareExchange 中 WHILE 循环内是交换语句，最好情况下不发 生交换， 最差情况下发生 N 次交换， 相当于 3N 个赋值语句； Demo 中 FOR 循环循环次数 log22N， 故按赋值语句次数计算 Demo 的时间复杂度为：最好情况：O(4N*log22N)≈O(Nlog(2*N))； 最差情况：O((4N+3N)*log22N)≈O(Nlog(2*N))。 24. 这是一个排序程序。运行后 B 数组存放 A 数组各数在排序后的位置。结果是： A={121,22,323,212,636,939,828,424,55,262} B={3,1,6,4,8,10,9,7,2,5} C={22,55,121,212,262,323,424,639,828,939}25.（1）c=（2）a=26.（1）同上面 26 题（1） （2）对 c 数组的赋值同所选择的下标 i 和 j 的次序（指外层循环用 j 内层用 i）没有关 系 （3）同上题 26（2） （4）对 i,j 下标取反序后，重复执行第（3）步，A 数组所有元素均变为 2。 （在机器上 验证，反复循环 3 次后，所有元素均变为 2） 27．错误有以下几处： （1）过程参数没有类型说明； （2）出错条件判断：缺少 OR（i+k&last+1） ； （3）删除元素时 FOR 循环应正向，不应用反向 DOWNTO； （4）count 没定义； 低效体现在两处： （1）删除 k 个元素时，不必一个一个元素前移，而应一次前移 k 个位置； （2）last 指针不应一次减 1，而应最后一次减 k。 正确的高效算法如下： const m=64； TYPE ARR=ARRAY[1..m] OF integer； PROCEDURE delk（VAR A:ARR；VAR last:i,k：integer） ； {从数组 A[1..last]中删除第 i 个元素起的 k 个元素，m 为 A 的上限} VAR count：integer； BEGIN IF（i&0）OR（i&last）OR（k&0）OR（last&m）OR（i+k&last+1） THEN write（’error’ ） ELSE[FOR count：= i+k TO last DO A[count-k]：=A[count]； last：=last-k；] END； 28. 这是计数排序程序。 （a）c[i](1&=i&=n)中存放 A 数组中值为 i 的元素个数。 （b）c[i](1&=i&=n)中存放 A 数组中小于等于 i 的个数。 （c）B 中存放排序结果，B[1..n]已经有序。 （d）算法中有 4 个并列 for 循环语句，算法的时间复杂度为 O(n)。 29．上三角矩阵第一行有 n 个元素，第 i-1 行有 n-（i-1）+1 个元素，第一行到第 i-1 行是 等腰梯形，而第 i 行上第 j 个元素（即 aij）是第 i 行上第 j-i+1 个元素，故元素 Aij 在一维 数组中的存储位置（下标 k）为： k=(n+(n-(i-1)+1))(i-1)/2+(j-i+1)=(2n-i+2)(i-1)/2+j-i+1 30．将上面 29 题的等式进一步整理为： 2 k=（n+1/2）i-i /2+j-n， 2 则得 f1（i）=（n+1/2）i-i /2，f2（j）=j，c=-n。 31.（1）将对称矩阵对角线及以下元素按行序存入一维数组中，结果如下：（2）因行列表头的“行列域”值用了 0 和 0，下面十字链表中行和列下标均从 1 开始。注：上侧列表头 Hi 和左侧行表头 Hi 是一个（即 H1、H2、H3 和 H4） ，为了清楚，画成了 两个。 32.（1）k=(2n-j+2)(j-1)/2+i-j+1 （当 i≥j 时，本题 n=4） k=(2n-i+2)(i-1)/2+j-i+1 （当 i&j 时，本题 n=4） （ 2 ） 稀 疏 矩 阵 的 三 元 组 表 为 ： s=((4,4,6),(1,1,1),(1,4,2),(2,2,3),(3,4,5),(4,1,2),(4,3,5)。 其中第一个三元组是稀 疏矩阵行数、列数和非零元素个数。其它三元组均为非零元素行值、列值和元素值。 33.（1）k=2（i-1）+j （1≤i，j≤n，|i-j|≤1） i=floor（k/3）+1 // floor（a）是取小于等于 a 的最大整数 j=k-2（i-1） 推导过程见上面第 25 题。 （2）行逻辑链接顺序表是稀梳矩阵压缩存储的一种形式。为了随机存取任意一行的非零 元，需要知道每一行第一个非零元在三元组表中的位置。为此，除非零元的三元组表外，还 需要一个向量，其元素值是每行第一个非零元在三元组表中的位置。其类型定义如下： typedef struct { int mu,nu, //稀梳矩阵的行数、列数和非零元素个数 int rpos[maxrow+1]; //行向量， 其元素值是每行第一个非零元在三元组表中的 位置。 Triple data[maxsize]; }SparsM 因篇幅所限，不再画出行逻辑链接顺序表。 34．各维的元素数为 di-ci+1，则 a[i1，i2，i3]的地址为： a0+[（i1-c1） 3- c3+1） 2- c2+1）+（i2-c2） 2- c2+1）+（i3-c3）]*L （d （d （d 35．主对角线上元素的坐标是 i=j，副对角线上元素的坐标 i 和 j 有 i+j=n+1 的关系 （1）i=j 或 i=n+1-j （1≤i，j≤n） （2）非零元素分布在两条主、副对角线上，除对角线相交处一个元素（下称“中心元素” ）外，其余每行都有两个元素。主对角线上的元素，在向量 B 中存储的下标是 k=2i-1(i=j, 1 ≤i，j≤n，1&=k&=2n-1)。 副对角线上的元素，在中心元素前，在向量 B 中存储的下标是 k=2i(i&&j, 1≤i，j≤ n/2)；在中心元素后，其下标是 k=2(i-1)(i&&j，n/2+1≤i，j≤n, 1&=k&=2n-1)。（3）aij 在 B 中的位置 K= 36. 由于对称矩阵采用压缩存储，上三角矩阵第一列一个元素，第二列两个元素，第 j 列 j 个元素。 上三角矩阵共有 n (n+1)/2 个元素。 我们将这些元素存储到一个向量 B[n(n+1)/2+1] 中。可以看到 B[k]和矩阵中的元素 aij 之间存在着一一对应关系：则 其 对 应 关 系 可 表 示 为 ： k=( 1&=i,j&=n,1&=k&=n(n+1)/2) int MAX(int x,int y) { return(x&y?x:y); } int MIN(int x,int y) { return(x&y?x:y); } 37. 设用 mu,nu 和 tu 表示稀疏矩阵行数，列数和非零元素个数，则转置矩阵的行数，列数 和非零元素的个数分别是 nu,mu 和 tu。转置可按转置矩阵的三元组表中的元素顺序进行， 即按稀疏矩阵的列序，从第 1 列到第 nu 列，每列中按行值递增顺序，找出非零元素，逐个 放入转置矩阵的三元组表中，转时行列值互换，元素值复制。按这种方法，第 1 列到第 1 个非零元素一定是转置后矩阵的三元组表中的第 1 个元素， 1 列非零元素在第 2 列非零元 第 素的前面。这种方法时间复杂度是 O(n*P)，其中 p 是非零元素个数，当 p 和 m*n 同量级时， 时间复杂度为 O(n3)。 另一种转置方法称作快速转置，使时间复杂度降为 O(m*n)。它是按稀疏矩阵三元组表 中元素的顺序进行。按顺序取出一个元素，放到转置矩阵三元组表的相应位置。这就要求出 每列非零元素个数和每列第一个非零元素在转置矩阵三元组表中的位置， 设置了两个附加向 量。 38. 广义表中的元素，可以是原子，也可以是子表，即广义表是原子或子表的有限序列，满 足线性结构的特性： 在非空线性结构中， 只有一个称为 “第一个” 的元素， 只有一个成为 “最 后一个”的元素，第一元素有后继而没有前驱，最后一个元素有前驱而没有后继，其余每个 元素有唯一前驱和唯一后继。从这个意义上说，广义表属于线性结构。 39. 数组是具有相同性质的数据元素的集合， 同时每个元素又有唯一下标限定， 可以说数组 是值和下标偶对的有限集合。n 维数组中的每个元素，处于 n 个关系之中，每个关系都是线 性的，且 n 维数组可以看作其元素是 n-1 维数组的一个线性表。而广义表与线性表的关系， 见上面 38 题的解释。40．线性表中的元素可以是各种各样的，但必须具有相同性质，属于同一数据对象。广义表 中的元素可以是原子，也可以是子表。其它请参见 38 41.（1） （c,d） （2） （b） （3）b （4） （f） （5） （） 42. Head（Tail（Head（Head（L1）） ）） Head（Head（Head（Tail（Head（Tail（L2））） ））） 类似本题的另外叙述的几个题解答如下： （1）head（head（tail（tail（L）），设 L=（a， ，b）（（e）） ）） （c） ，（ ）） （2）head（head（head（head（tail（tail（L））） ）））（3）head（tail（head（tail（A）） ）） （4）H（H（T（H（T（H（T（L）））） ））） （5）tail（L）=（（c,d）， （ ）（e,f） ） head（tail（L） （c,d） ）=（ ） head（head（tail（L））=（c,d） ） tail（head（head（tail（L）） ））=（d） head（tail（head（head（tail（L）））=d ）） （6）head（tail（head（head（tail（tail（A））） ））） 43. 广义表的第一种存储结构的理论基础是，非空广义表可唯一分解成表头和表尾两部分， 而由表头和表尾可唯一构成一个广义表。这种存储结构中，原子和表采用不同的结点结构 （ “异构” ，即结点域个数不同） 。原子结点两个域：标志域 tag=0 表示原子结点，域 DATA 表示原子的值；子表结点三个域： tag=1 表示子表，hp 和 tp 分别是指向表头和表尾的指针。在画存储结构时，对非空广义表 不断进行表头和表尾的分解， 表头可以是原子， 也可以是子表， 而表尾一定是表 （包括空表） 。 上面是本题的第一种存储结构图。 广义表的第二种存储结构的理论基础是，非空广义表最高层元素间具有逻辑关系：第 一个元素无前驱有后继，最后一个元素无后继有前驱，其余元素有唯一前驱和唯一后继。有人将这种结构看作扩充线性结构。 这种存储结构中， 原子和表均采用三个域的结点结构 “同 （ 构”。结点中都有一个指针域指向后继结点。原子结点中还包括标志域 tag=0 和原子值域 ） DATA；子表结点还包括标志域 tag=1 和指向子表的指针 hp。在画存储结构时，从左往右一 个元素一个元素的画，直至最后一个元素。下面是本题的第二种存储结构图。由于存储结构图占篇幅较大，下面这类题均不再解答。 44.深度为 5，长度为 2 45.（1）略 （2）表的长度为 5，深度为 4 （3）head（tail（head（head（head（tail（tail（tail（tail（A））））） ）））） 46.共享结构广义表 A=（（b,c） ， ，（a）（ （ ，d）（a）（ ，（b,c） ） （） ，d），e， ）的存储表示：47.（1）算法 A 的功能是逆置广义表 p（即广义表由 p 指针所指） 。逆置后的广义表由 t 指 向。 （2）逆置后的广义表由 t 指向，这时 p=nil。48.（a,b） 49.（d） 50.否。广义表的长度不是广义表中原子个数，而是指广义表中所含元素的个数，广义表中 的元素可以是原子，也可以是子表。广义表元素多于 1 个时，元素间用逗号分开。 5 2 4 5 3 3 4 2 5 3 51. p（x1 x2 x3）=2 x1 x2 x3 +5 x1 x2 x3 +3 x1 x2 x3 +（x1 x2 + x2）x3+652.（1）H(A(a1,a2）,B(b1）,C(c1，c2）,x） HEAD(TAIL(HEAD(H））=a2 ） （2）略 五.算法设计题 1.[题目分析]本题是在向量 D 内插入元素问题。首先要查找插入位置，数据 x 插入到第 i 个数据组的末尾，即是第 i+1 个数据组的开始，而第 i（1≤i≤n）个数据组的首地址由数 组 s（即数组元素 s[i]）给出。其次，数据 x 插入后，还要维护数组 s，以保持空间区 D 和 数组 s 的正确的相互关系。 void Insert（int s[]，datatype D[]，x，int i,m） //在 m 个元素的 D 数据区的第 i 个数据组末尾，插入新数据 x，第 i 个数据组的首址由 数组 s 给出。 ｛if（i&１|| i&n） ｛printf（ “参数错误”；exit（０）｝ ） ； if（i==n） D[m]=x； // 在第 n 个数据组末尾插入元素。 else｛for（j=m-1;j&=s[i+1];j--）D[j+1]=D[j]; // 第 i＋１个数据组及以后元素 后移 D[s[i+1]]=x; // 将新数据 x 插入 for(j=i+1;j&=n;j++) s[j]++; // 维护空间区 D 和数组 s 的的关系。 } //结束元素插入 m++; //空间区 D 的数据元素个数增 1。 }// 算法 Insert 结束 [算法讨论] 数据在空间区从下标 0 开始，最后一个元素的下标是 m-1。设空间区容量足 够大，未考虑空间溢出问题。数组 s 随机存数，而向量 D 数据插入，引起数组元素移动，时 间复杂度是 O（n） 。 2. [题目分析]设稀疏矩阵的非零元素的三元组以行序为主存储在三元组表中。矩阵的相加 是对应元素的相加。 对两非零元素相加， 若行号不等， 则行号大者是结果矩阵中的非零元素。 若行号相同，则列号大者是结果中一非零元素；若行号列号相同，若对应元素值之和为零， 不予存储，否则，作为新三元组存到三元组表中。题目中要求时间复杂度为 O（m+n） 。因此 需从两个三元组表的最后一个元素开始相加。第一个非零元素放在 A 矩阵三元组表的第 m+n 位置上。结果的三元组至多是 m+n 个非零元素。最后若发生对应元素相加和为零的情况，对 三元组表中元素要进行整理，以便使第一个三元组存放在下标 1 的位置上。 CONST maxnum=大于非零元素数的某个常量 TYPE tuple=RECORD i,j：integer； v：elemtp； END； sparmattp=RECORD mu，nu，tu：integer； data: ARRAY[1..maxnum] OF tuple； END； PROC AddMatrix（VAR A：sparmattp；B：sparmattp） ； // 稀疏矩阵 A 和 B 各有 m 和 n 个非零元素，以三元组表存储。A 的空间足够大，本算 法实现两个稀疏矩阵相加，结果放到 A 中。 L:=m；p:=n；k:=m+n；// L,p 为 A，B 三元组表指针，k 为结果三元组表指针（下标） 。A.tu:=m+n；// 暂存结果矩阵非零元素个数 WHILE（L≥1）AND（p≥1）DO [CASE // 行号不等时，行号大者的三元组为结果三元组表中一项。 A.data[L].i&B.data[p].i：A.data[k]:=A.data[L]；L:=L-1；// A 中当前项为结 果项 A.data[L].i&B.data[p].i：A.data[k]:=B.data[p]；p:=p-1；//B 中当前项为结 果当前项 A.data[L].i=B.data[p].i： CASE //行号相等时，比较列号 A.data[L].j&B.data[p].j：A.data[k]:=A.data[L]；L:=L-1； A.data[L].j&B.data[p].j：A.data[k]:=B.data[p]；p:=p-1； A.data[L].j=B.data[p].j ： IF A.data[L].v+B.data[p].v ≠ 0 THEN [A.data[L].v=A.data[L].v+ B.data[p].v； A.data[k]:= A.data[L]；] L:=L-1；p:=p-1； ENDC； //结束行号相等时的处理 ENDC； //结束行号比较处理。 k:=k-1； //结果三元组表的指针前移（减 1） ]//结束 WHILE 循环。 WHILE p&0 DO[A.data[k]:=B.data[p]；k:=k-1；p:=p-1；] //处理 B 的剩余部分。 WHILE L&1 DO[A.data[k]:=A.data[L]；k:=k-1；L:=L-1；] //处理 A 的剩余部分。 IF k&1 THEN //稀疏矩阵相应元素相加时，有和为零的元素，因而元素总数&m+n。 [FOR p:=k TO m+n DO A[p-k+1]:=A[p]；// 三元组前移，使第一个三元组的下标为 1。 A.tu=m+n-k+1；] // 修改结果三元组表中非零元素个数。 ENDP； // 结束 addmatrix [算法讨论]算法中三元组的赋值是“成组赋值” ，可用行值、列值和元素值的三个赋值 句代替。A 和 B 的三元组表的当前元素的指针 L 和 p，在每种情况处理后均有修改，而结果 三元组表的指针 k 在 CASE 语句后统一处理（k:=k-1） 。算法在 B 的第一个元素“大于”A 的 最后一个元素时，时间复杂度最佳为 O（n） ，最差情况是每个元素都移动（赋值）了一次， 且出现了和为零的元素，致使最后（m+n-k+1）个元素向前平移一次，时间复杂度最差为 O （m+n） 。 3.[题目分析]从 n 个数中，取出所有 k 个数的所有组合。设数已存于数组 A[1..n]中。为使 结果唯一，可以分别求出包括 A[n]和不包括 A[n]的所有组合。即包括 A[n]时，求出从 A[1..n-1]中取出 k-1 个元素的所有组合，不包括 A[n]时，求出从 A[1..n-1]中取出 k 个元 素的所有组合。 CONST n=10；k=3； TYPE ARR=ARRAY[1..n] OF integer； VAR A，B：ARR；// A 中存放 n 个自然数，B 中存放输出结果。 PROC outresult；//输出结果 FOR j：=1 TO k DO write（B[j]） ；writeln； ENDP； PROC nkcombination（i,j,k：integer） ；//从 i 个数中连续取出 k 个数的所有组合，i 个数已存入数组 A 中，j 为结果数组 B 中 的下标。 IF k=0 THEN outresult ELSE IF（i-k≥0）THEN [ B[j]:=A[i]；j:=j+1； nkcombination（i-1，k-1，j） ； nkcombination（i-1，k，j-1） ；] ENDP； [算法讨论]本算法调用时，i 是数的个数（题目中的 n） ，k≤i，j 是结果数组的下标。 按题中例子，用 nkcombination（5，1，3）调用。若想按正序输出，如 123，124，?，可 将条件表达式 i-k≥0 改为 i+k-1≤n，其中 n 是数的个数，i 初始调用时为 1，两个调用语 句中的 i-1 均改为 i+1。 4. [题目分析]题目中要求矩阵两行元素的平均值按递增顺序排序，由于每行元素个数相等， 按平均值排列与按每行元素之和排列是一个意思。 所以应先求出各行元素之和， 放入一维数 组中，然后选择一种排序方法，对该数组进行排序，注意在排序时若有元素移动，则与之相 应的行中各元素也必须做相应变动。 void Translation（float *matrix，int n） //本算法对 n×n 的矩阵 matrix，通过行变换，使其各行元素的平均值按递增排列。 {int i,j,k,l； float sum，min； //sum 暂存各行元素之和 float *p, *pi, * for(i=0; i&n; i++) {sum=0.0; pk=matrix+i*n; //pk 指向矩阵各行第 1 个元素. for (j=0; j&n; j++){sum+=*(pk); pk++;} //求一行元素之和. *(p+i)= //将一行元素之和存入一维数组. }//for i for(i=0; i&n-1; i++) //用选择法对数组 p 进行排序 {min=*(p+i); k=i; //初始设第 i 行元素之和最小. for(j=i+1;j&n;j++) if(p[j]&min) {k=j; min=p[j];} //记新的最小值及行号. if(i!=k) //若最小行不是当前行,要进行交换(行元素及行元素之 和) {pk=matrix+n*k; //pk 指向第 k 行第 1 个元素. pi=matrix+n*i; //pi 指向第 i 行第 1 个元素. for(j=0;j&n;j++) //交换两行中对应元素. {sum=*(pk+j); *(pk+j)=*(pi+j); *(pi+j)=} sum=p[i]; p[i]=p[k]; p[k]= //交换一维数组中元素之和. }//if }//for i free(p); //释放 p 数组. }// Translation [算法分析] 算法中使用选择法排序,比较次数较多,但数据交换(移动)较少.若用其它 2 排序方法,虽可减少比较次数,但数据移动会增多.算法时间复杂度为 O(n ). 5. [题目分析] 因为数组中存放的是从 1 到 N 的自然数，原程序运行后,数组元素 A[i](1&=i&=N)中存放的是 A[1]到 A[i-1]中比原 A[i]小的数据元素的个数。 易见 A[N]+1 就 是原 A[N]的值(假定是 j,1&=j&=N)。设一元素值为 1 的辅助数组 flag，采用累加，确定一个值后，flag 中相应元素置零。下面程序段将 A 还原成原来的 A: VAR flag:ARRAY[1..N] OF FOR i:=1 TO N DO flag[i]:=1; //赋初值 FOR i:=N DOWNTO 1 DO BEGIN sum:=0; j:=1; found:= WHILE j&=N AND NOT found DO BEGIN sum:=sum+flag[j]; IF sum=A[i]+1 THEN BEGIN flag[j]:=0; found:= END; END; A[i]:=j; END; 6.[题目分析] 寻找马鞍点最直接的方法,是在一行中找出一个最小值元素,然后检查该元 素是否是元素所在列的最大元素,如是,则输出一个马鞍点,时间复杂度是 O(m*(m+n)).本算 法使用两个辅助数组 max 和 min,存放每列中最大值元素的行号和每行中最小值元素的列号, 时间复杂度为 O（m*n+m） ，但比较次数比前种算法会增加，也多使用向量空间。 int m=10, n=10; void Saddle(int A[m][n]) //A 是 m*n 的矩阵,本算法求矩阵 A 中的马鞍点. {int max[n]={0}, //max 数组存放各列最大值元素的行号,初始化为行号 0; min[m]={0}, //min 数组存放各行最小值元素的列号,初始化为列号 0; i, for(i=0;i&m;i++) //选各行最小值元素和各列最大值元素. for(j=0;j&n;j++) {if(A[max[j]][j]&A[i][j]) max[j]=i; //修改第 j 列最大元素的行号 if(A[i][min[i]]&A[i][j]) min[i]=j; //修改第 i 行最小元素的列号. } for (i=0;i&m;i++) {j=min[i]; //第 i 行最小元素的列号 if(i==max[j])printf(“A[%d][%d]是马鞍点，元素值是%d”,i,j,A[i][j]); // 是马鞍点 } }// Saddle [算法讨论] 以上算法假定每行（列）最多只有一个可能的马鞍点，若有多个马鞍点, 因为一行(或一列)中可能的马鞍点数值是相同的，则可用二维数组 min2，第一维是行向量， 是各行行号，第二维是列向量，存放一行中最大值的列号。对最大值也同样处理，使用另一 二维数组 max2，第一维是列向量，是各列列号，第二维存该列最大值元素的行号。最后用 类似上面方法，找出每行(i)最小值元素的每个列号（j） ，再到 max2 数组中找该列是否有最 大值元素的行号（i） ，若有，则是马鞍点。 7． [题目分析]我们用 l 代表最长平台的长度， k 指示最长平台在数组 b 中的起始位置 用 （下 标） 。用 j 记住局部平台的起始位置，用 i 指示扫描 b 数组的下标，i 从 0 开始，依次和后 续元素比较，若局部平台长度（i-j）大于 l 时，则修改最长平台的长度 k（l=i-j）和其在 b 中的起始位置（k=j） ，直到 b 数组结束，l 即为所求。 void Platform (int b[ ], int N) //求具有 N 个元素的整型数组 b 中最长平台的长度。{l=1;k=0;j=0;i=0; while(i&n-1) {while(i&n-1 && b[i]==b[i+1]) i++; if(i-j+1&l) {l=i-j+1;k=j;} //局部最长平台 i++; j=i; } //新平台起点 printf(“最长平台长度%d，在 b 数组中起始下标为%d” ，l，k)； }// Platform 8．[题目分析]矩阵中元素按行和按列都已排序，要求查找时间复杂度为 O（m+n） ，因此不 能采用常规的二层循环的查找。可以先从右上角（i=a,j=d）元素与 x 比较，只有三种情况： 一是 A[i,j]&x， 这情况下向 j 小的方向继续查找；二是 A[i,j]&x，下步应向 i 大的方向 查找；三是 A[i,j]=x，查找成功。否则，若下标已超出范围，则查找失败。 void search(datatype A[ ][ ], int a,b,c,d, datatype x) //n*m 矩阵 A,行下标从 a 到 b,列下标从 c 到 d,本算法查找 x 是否在矩阵 A 中. {i=a; j=d; flag=0; //flag 是成功查到 x 的标志 while(i&=b && j&=c) if(A[i][j]==x) {flag=1;} else if (A[i][j]&x) j--; else i++; if(flag) printf(“A[%d][%d]=%d”,i,j,x); //假定 x 为整型. else printf(“矩阵 A 中无%d 元素” ，x)； }算法 search 结束。 [算法讨论]算法中查找 x 的路线从右上角开始， 向下 （当 x&A[i,j]） 或向左 （当 x&A[i,j]） 。 向下最多是 m， 向左最多是 n。 最佳情况是在右上角比较一次成功， 最差是在左下角 （A[b,c]） ， 比较 m+n 次，故算法最差时间复杂度是 O(m+n） 。 9．[题目分析]本题的一种算法前面已讨论（请参见本章三、填空题 38） 。这里给出另一中 解法。分析数的填法，是按“从右上到左下”的”蛇形” ，沿平行于副对角线的各条对角线 上，将自然数从小到大填写。当从右上到左下时，坐标 i 增加，坐标 j 减小，当 j 减到小于 0 时结束，然后 j 从 0 开始增加，而 i 从当前值开始减少，到 i&0 时结束。然后继续如此循 环。当过副对角线后，在 i&n-1 时，j=j+2，开始从左}