v1.0 可编辑可修改 （2）用k表示i,j的下标变化公式。
5．画出下面广义表的两种存储结构图示： ((((a), b)), ((( ), d), (e, f)))
6．求下列广义表运算的结果：
（1）HEAD[((a,b),(c,d))]; （2）TAIL[((a,b),(c,d))]; （3）TAIL[HEAD[((a,b),(c,d))]]; （4）HEAD[TAIL[HEAD[((a,b),(c,d))]]]; （5）TAIL[HEAD[TAIL[((a,b),(c,d))]]];
7. 利用广义表的Head和Ｔail运算，把原子d分别从下列广义表中分离出来，L1＝(((((a),b),d),e))；L2＝（a,(b,((d)),e)）。
四、算法设计题
1. 给定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)。
2. 设二维数组a[1..m, 1..n] 含有m*n 个整数。
(1) 写出算法：判断a中所有元素是否互不相同输出相关信息(yes/no)； (2) 试分析算法的时间复杂度。
3. 设A[1..100]是一个记录构成的数组，B[1..100]是一个整数数组，其值介于1至100之间，现要求按B[1..100]的内容调整A中记录的次序，比如当B[1]=ll时，则要求将A[1]的内容调整到A[11]中去。规定可使用的附加空间为O(1)。
4．稀疏矩阵用三元组的表示形式，试写一算法实现两个稀疏矩阵相加，结果仍用三元组表示。 5
v1.0 可编辑可修改 5. 试编写建立广义表存储结构的算法，要求在输入广义表的同时实现判断、建立。设广义表按如下形式输入（a1,a2,a3,…,an） n>=0，其中ai或为单字母表示的原子或为广义表，n=0时为只含空格字符的空表。
6
v1.0 可编辑可修改 第5章 数组和广义表
一、单项选择题 1． C 2． C 3． A 4． A 5． B 6． A 7． C 8． C 9． C 10． C 11． A
二、填空题
1．顺序、列序、行序 2. 第1行 第3列 3．i(i-1)/2+j (1<=i,j<=n)
4. 非零元很少(t< 5． （1） 原子（单元素）是结构上不可再分的，可以是一个数或一个结构；而表带结构，本质就是广义表，因作为广义表的元素故称为子表。 （2）大写字母 （3）小写字母 （4）表中元素的个数（5）表展开后所含括号的层数 6．（1）（） （2）（（）） （3）2 （4）2 7． col<=, [p].j, q++ 8. （1）(p->tag==0) 958 三维数组以行为主序存储，其元素地址公式为： LOC(Aijk)=LOC(Ac1c2c3)+[(i-c1)V2V3+(j-c2)V3+(k-c3)]*L+1 7 v1.0 可编辑可修改 其中ci,di是各维的下界和上界，Vi=di-ci+1是各维元素个数，L是一个元素所占的存储单元数。 2. 特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律，因此可以对非零元素分配单元（对值相同元素只分配一个单元），将非零元素存储在向量中，元素的下标i和j和该元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小（t< 3. 数组是具有相同性质的数据元素的集合，同时每个元素又有唯一下标限定，可以说数组 是值和下标偶对的有限集合。n维数组中的每个元素，处于n个关系之中，每个关系都是线性的，且n维数组可以看作其元素是n-1维数组的一个线性表。广义表中的元素，可以是原子，也可以是子表，即广义表是原子或子表的有限序列，满足线性结构的特性：在非空线性结构中，只有一个称为“第一个”的元素，只有一个成为“最后一个”的元素，第一元素有后继而没有前驱，最后一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。从这个意义上说，广义表属于线性结构。 4. 三对角矩阵第一行和最后一行各有两个非零元素，其余每行均有三个非零元素，所以共有3n-2个元素。 （1）主对角线左下对角线上的元素下标间有i=j+1关系，k与i和j的关系为k=3(i-1);主对角线上元素下标间有关系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 ） 8
相关推荐：
loading