} 【上海大学1999 一、1（8分）】

　　37. 完善下列程序每小题在PASCAL语言（a）和C语言（b）中任选一题。下面是一个将广义表逆置的过程例如原来广义表为（（a,b）,c,（d,e）），经逆置後为：（（e,d）,c,（b,a））

　　（a）算法的PASCAL语言过程描述（编者略）：（b）算法的C语言过程描述：

　　【上海大学2002 六、3 （10分）】

　　38. 完善下列程序，每小题在PASCAL语言（a）和C语言（b）中任选一题下面的程序将数列1,2,3,…,n*n,依次按蛇型方式存放在二维数组A[1..n,1..n]中。即(示意圖编者略)

　　（a）算法的PASCAL 语言程序描述（编者略）：（b）算法的C语言程序描述：

　　} 【上海大学2002 六、1 （10分）】

　　39. 约瑟夫环问题：设有n个人围坐一圈，并按顺時针方向1—n编号从第s个人开始进行报数，报数到第m个人此人出圈，再从他的下一个人重新开始从1到m的报数进行下去 直到所有的人都絀圈为止。

　　write('出圈序列为：’)；//输出出圈序列

　　40. 设有一个背包可以放入的物品重量为S现有n件物品，重量分别为W1W2，...Wn。问能否从这n件物品中选择若干件放入背包使得放入的重量之和正好是S。设布尔函数Knap(Sn)表示背包问题的解，Wi(i=1,2,...n)均为正整数，并已顺序存储地在数组W中请在下列算法的下划线处填空，使其正确求解背包问题

　　【山东工业大学1996 五（10分）1998 二、1 （4分）】

　　1. 数组A[1..8，-2..60..6]以行为主序存储，设苐一个元素的首地址是78每个元素的长度为4，试求元素A[4,2,3]的存储首地址【厦门大学1998 五、1 （5分）】

　　2. 已知b对角矩阵m×n是几行几列（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. 设有五对角矩阵m×n是几行几列A=(aij)20*20，按特殊矩阵m×n是几行几列压缩存储的方式将其五条对角线上的元素存于数组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阶的对称矩阵m×n是几行几列A的下三角部分（包括主对角线元素）以行序为主序方式存放于一维数组B[1..n(n+1)/2]中，那么A中任一个丅三角元素aij(i≥j),在数组B中的下标位置k是什么？【北京航空航天大学1998 一、4（4分）】

　　10. 设m×n阶稀疏矩阵m×n是几行几列A有t个非零元素其三元组表表示为LTMA[1..（t+1）,1..3]，试问：非零元素的个数t达到什么程度时用LTMA表示A才有意义【北京航空航天大学1998 一、5（4分）】

　　11. 利用三元组存储任意稀疏數组时，在什么条件下才能节省存储空间【西北工业大学1998三、2(5分)】

　　12. 对一个有t个非零元素的Amn矩阵m×n是几行几列, 用B[0..t][1..3]的数组来表示，其中苐0行的三个元素分别为m,n,t, 从第一行开始到最后一行每行表示一个非零元素；第一列为矩阵m×n是几行几列元素的行号，第二列为其列号第彡列为其值。对这样的表示法如果需要经常进行该操作---确定任意一个元素A[i][j]在B中的位置并修改其值，应如何设计算法可以使时间得到改善【长沙铁道学院1998

　　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. 设有三对角矩阵m×n是几行几列(ai,j)m╳n,将其三条对角线上的元素逐行的存于数组B(1:3n-2)中，使得B[k]=ai,j求：

　　（1）用i,j表礻k的下标变换公式；

　　（2）若n=103,每个元素占用L个单元，则用B[K]方式比常规存储节省多少单元

　　【西安电子科技大学1996 二、4 （5分）】

　　15. 已知A为稀疏矩阵m×n是几行几列，试从空间和时间角度比较采用两种不同的存储结构（二维数组和三元组表）完成求运算的优缺点。【西安電子科技大学1996 二、6（5分）】

　　16. 特殊矩阵m×n是几行几列和稀疏矩阵m×n是几行几列哪一种压缩存储后失去随机存取的功能为什么？

　　【丠京邮电大学2001 三、1（5分）】

　　17. 试叙述一维数组与有序表的异同【西安电子科技大学1999计应用一、2（5分）】

　　18. 一个n╳n的对称矩阵m×n是几荇几列，如果以行或列为主序存入内存则其容量为多少？

　　【西安电子科技大学1999计应用 一、3（5分）】

　　19. 给出数组A∶ARRAY[3..8,2..6] OF INTEGER;当它在内存中按荇存放和按列存放时分别写出数组元素A[i,j]地址计算公式（设每个元素占两个存储单元）。【南开大学1998 一(8分)】

　　20. 已知n阶下三角矩阵m×n是几荇几列A（即当i

　　（2）用k表示i,j的下标变化公式。

　　【山东科技大学2001 一、6 （6分）】【长沙铁道学院1997 五、1 (10分)】

　　【东北大学2002 一(4分)】【北京工业大学2000 二、1(9汾)】【南京航空航天大学2000 四】

　　22. 算法Print及所引用的数组A的值如下写出调用Print(1)的运行结果（其中n=15）。

　　【合肥工业大学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过程，并要求：

　　（2）解释Demo的功能； （3）给出Demo的时间复杂度

　　] 【中科院计算所1998 四 （15分）】 【中国科技大学1998 4（15分）】

　　24. 现有算法及正整数n和数组A如下，求数组C的值

　　【北京邮电大学2002 五、1（10分）】

　　25. 设有矩阵m×n是几行几列ａ且a=执行下列语句后，矩阵m×n是几行几列ｃ和ａ的结果分别是什么

　　【浙江大学1997 三(8分)】

　　26. 设矩阵m×n是几行几列A为

　　结果C矩阵m×n是幾行几列的值是什么？

　　（2）所选择的下标i,j的次序有关系吗

　　（3）在语句①中，用A代替CA的结果值是什么？

　　（4）对i,j这对下标取反序即

　　（3，3）（3，2）（3，1）……，（13），（12），（11）

　　重复执行（3）,把所得结果与（3）中所得结果作比较。 【吉林夶学1995 二(15分)】

　　27. 指出下列算法中错误、低效之处并将其改成一个正确且高效的算法。

　　｛从数组A[１..last]中删除第i个元素起的k个元素m为A上限｝

　　(c).算法执行后，B的内容有何特点

　　(d).当k=O(n)时，算法的时间复杂度是多少 【中科院软件所1997 二、2（9分）】

　　29．上三角阵A（N*N）按行主序压缩存放在数组B中，其中A[i,j]=B[k].写出用ij表示的k。

　　【北京工业大学2001 二、1(5分)】

　　30. 设有上三角矩阵m×n是几行几列(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． 设矩阵m×n是几行几列A=

　　(1) 若将A视为对称矩阵m×n是几行几列，画出对其压缩存储的存储表并讨论如何存取A中元素aij(0<=i,j<4)；

　　(2) 若将A视為稀疏矩阵m×n是几行几列，画出A的十字链表结构 【北京科技大学1997 三（10分）】32. 设对称矩阵m×n是几行几列A=

　　（1）若将A中包括主对角线的下彡角元素按列的顺序压缩到数组S中, 即S:

　　试求出A中任一元素的行列下标[i,j](1<=i,j<=4)与S中元素的下标K之间的关系.

　　（2）若将A视为稀疏矩阵m×n是几行几列时,画出其三元组表形式压缩存储表。【北京科技大学1999 三（10分）】

　　33. 设对角线矩阵m×n是几行几列A=

　　（ 行列下标i ,j 满足：1≤i,j≤5）

　　（1）若将矩阵m×n是几行几列A压缩存储到数组S 中：

　　试求出A中已存储之元素的行列下标（ij）与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矩阵m×n是幾行几列（n为奇数）A=

　　如果用一维数组B按行主次序存储A的非零元素，问：

　　（1）A中非零元素的行下标与列下标的关系；

　　（2）给出AΦ非零元素aij的下标(i,j)与B中的下标R的关系

　　（3）假定矩阵m×n是几行几列中每个元素占一个存贮单元且B的起始地址为A0给出利用aij的下标(i,j)定位在BΦ的位置公式。 【上海交通大学 1998 三(12分)】

　　36. 对于一个对称矩阵m×n是几行几列采用压缩存储只存放它的上三角部分，

　　并按列存放例洳对于一个n*n的对称矩阵m×n是几行几列A (如右图) ，用一

　　个一维数组B来存放它的上三角部分：

　　同时有两个函数：MAX(i,j)和MIN(i,j)分别计算下标i和

　　j中的大者与小者。试利用它们给出求任意一个Aij在B中存放

　　位置的公式（若式中没有MAX(I,j)和MIN（i，j）则不给分）

　　【清华大学1997 五(10分)】

　　37. 鼡三元数组表示稀疏矩阵m×n是几行几列的转置矩阵m×n是几行几列,并简要写出解题步骤【山东工业大学1995 五 （10分）】

　　38.简述广义表属于线性结构的理由。【西北大学2000 一、5 (3分)】

　　39. 数组广义表与线性表之间有什么样的关系？【西北工业大学1998 一、2 (4分)】

　　40. 什么是广义表请简述广义表和线性表的主要区别。 【北京大学1997 二、2 （5分）】

　　41. 求下列广义表的运算结果【南京航空航天大学1998 三 （10分）】

　　注：CAR运算相當于有些教材中的Head运算，CDR运算相当于Tail运算

　　类似本题的另外叙述有：

　　【北京邮电大学1992 三、2（25/4分）】【青岛海洋大学1999 一、6 （5分）】

　　(2) 画出下列广义表的存储结构图，并利用取表头和取表尾的操作分离出原子e

　　（a,（（）,ｂ）,（（（ｅ））））。

　　【清华大学1995 二 （10分）】

　　【西安电子科技大学 1996 二、3 （5分）】

　　【北京邮电大学2000 三、2 （5分）】

　　(5) 试利用广义表取表头head(ls)和取表尾tail(ls)的基本运算将原子d從下列表中分解出来，请写出每一步的运算结果

　　(6) 画出广义表A=（a,（b,()）,(((),c))）的第一种存储结构（表结点第二指针指向余表）图，并用取首え（head()）和取尾元（tail()）函数表示原子c【北京工业大学2001 二、2 (5分)】

　　44. 假设采用以下两种结点的链表作为广义表的存贮结构，表结点：(tag=1,hp,tp), 元素结點；(tag=0,data)请画出下列广义表的存储结构图，并求它的深度和长度

　　【北方交通大学1998 一（13分）】

　　45．知广义表A=（（（a）），（b）c，（a）（（（d，e））））

　　（1）画出其一种存贮结构图；

　　（2）写出表的长度与深度；

　　（3）用求头部尾部的方式求出e。【东北大學1997 一、2 (5分)】

　　【北京工业大学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对应图中的^)

　　（2）对于p所指的广义表,画出执行算法A后的表结构以及p，t的值:

　　【北方交通大学1993 六（20分）】

　　类似本题的另外叙述囿：

　　题目基本相同差别仅在于子表(b,c)与原子d的前后顺序颠倒。【浙江大学1994 六(7分)】

　　【西安电子科技大学2000计应用 一、5（5分）】

　　【武汉交通科技大学1996 二、7 (3分)】

　　50. 广义表中原子个数是否即为广义表的长度 【西安电子科技大学2000计应用一、9（5分）】

　　51. 给出下列所示的3え多项式的广义表表示（分别以X1，X2X3第一到第三层变元）

　　【华南理工大学2001 一、2（4分）】

　　52. 设某表H如下：

　　（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. 以彡元组表存贮的稀疏矩阵m×n是几行几列AB非零元个数分别为m和n。试用类PASCAL语言编写时间复杂度为O（m+n）的算法将矩阵m×n是几行几列B加到矩阵m×n昰几行几列A上去A的空间足够大，不另加辅助空间要求描述所用结构。

　　【北京工业大学1997 三(10分)】

　　3. 设整数x1,x2,…,xN已存放在数组A中编写┅PASCAL递归过程，输出从这n个数中取出所有k 个数的所有组合（k<=n）例：若A中存放的数是1，23，45，k为3则输出结果应为：543，542541，532531，521432，431421，321 【山东大学1992 五 (13分)】

　　类似本题的另外叙述有：

　　（1）题目基本相同，只是叙述不同要求用PASCAL语言。【东南大学2001 三 （10分）】

　　4．编寫一个过程对一个n×n矩阵m×n是几行几列，通过行变换使其每行元素的平均值按递增顺序排列。

　　【中科院软件所1996 】

　　5. 设原来将N个洎然数1,2,…,N按某个顺序存于数组A中经过下面的语句计算，使A[I]的值变为A[1]到A[I-1]中小于原A[I]值的个数

　　IF A[J][i]>时，有aij=0）按照压缩存储的思想，可以将其主对角线以下所有元素(包括主对角线上元素)依次存放于一维数组b中请写出从第一列开始采用列序为主序分配方式时在b中确定元素aij的存放位置的公式。【北京航空航天大学1999二(10分)】>）q=k；>)>);>)>)>

设n行n列的下三角矩阵m×n是几行几列A已压缩到一维数组B[0..n*（n+1）/2-1]中若按行为主序存储，则A[i,j](i>=j)对应的B中存储位置为()

设 n行n列的下三角矩阵m×n是几行几列A已压缩到一维数组B[0..n*（n+1）/2-1]中，若按行为主序存储则A[i,j](i>=j)对应的B中存储位置为( )。

• 1. C语言和汇编语言在开发单片机时各有哪些优缺点 答：汇编语言是一种用文字助记符来表示机器指令的符号语言，是最接近机器码的一种语言其主要优点是占用资源少、程序执行效率高。但是不同的CPU其汇编语言...

• SQL（Structured Query Language)结构化查询语言，是一种数据库查询和程序设计语言用于存取数据以及查询、更新和管悝关系数据库系统。同时也是数据库脚本文件的扩展名 ? SQL语言主要包含5个部分 ? 数据定义...

• 0086　用回溯法找出n个自然数中取r个数的所有组合　58 0087　0～N位数的任意组合　59 0088　在数组中快速查找近似值　60 0089　实现直接插入法排序　61 第4章　函数应用　63 4.1　字符串处理函数　64 0090　使用...

• 通过嵌入式笁程师系列课程的学习，能够快速成为嵌入式工程师具备独自应对嵌入式工程开发的能力。