习题五 数组和广义表
一、单项选择题
1.常对数组进行的两种基本操作是( )
A.建立与删除 B. 索引与修改 C. 查找与修改 D. 查找与索引
2.对于C语言的二维数组DataType A[m][n],每个数据元素占K个存储单元,二维数组中任意元素a[i,j] 的存储位置可由( )式确定.
[i,j]=A[m,n]+[(n+1)*i+j]*k [i,j]=loc[0,0]+[(m+n)*i+j]*k [i,j]=loc[0,0]+[(n+1)*i+j]*k [i,j]=[(n+1)*i+j]*k 3.稀疏矩阵的压缩存储方法是只存储 ( )
A.非零元素 B. 三元祖(i,j, aij) C. aij D. i,j
4. 数组A[0..5,0..6]的每个元素占五个字节,将其按列优先次序存储在起始地址为1000的内存单元中,则元素A[5,5]的地址是( )。
A. 1175 B. 1180 C. 1205 D. 1210 5. A[N,N]是对称矩阵,将下面三角(包括对角线)以行序存储到一维数组T[N(N+1)/2]中,则对任一上三角元素a[i][j]对应T[k]的下标k是( )。
A. i(i-1)/2+j B. j(j-1)/2+i C. i(j-i)/2+1 D. j(i-1)/2+1
6. 用数组r存储静态链表,结点的next域指向后继,工作指针j指向链中结点,使j 沿链移动的操作为( )。
A. j=r[j].next B. j=j+1 C. j=j->next D. j=r[j]-> next 7. 对稀疏矩阵进行压缩存储目的是( )。
A.便于进行矩阵运算 B.便于输入和输出 C.节省存储空间 D.降低运算的时间复杂度
8. 已知广义表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)))) 9. 广义表((a,b,c,d))的表头是( ),表尾是( )。
A. a B.() C.(a,b,c,d) D.(b,c,d) 10. 设广义表L=((a,b,c)),则L的长度和深度分别为( )。
A. 1和1 B. 1和3 C. 1和2 D. 2和3 11. 下面说法不正确的是( )。
A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表 C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构
二、填空题
1.通常采用___________存储结构来存放数组 。对二维数组可有两种存储方法:一种是以___________为主序的存储方式,另一种是以___________为主序的存储方式。
2. 用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j] (1≤i≤n,i-2≤j≤i+2),B中的第8个元素是A 中的第_ _行,第_ _列的元素。
3.设n行n列的下三角矩阵A已压缩到一维数组B[1..n*(n+1)/2]中,若按行为主序存储,则A[i,j]对应的B中存储位置为_______。
4. 所谓稀疏矩阵指的是_ 。
5. 广义表简称表,是由零个或多个原子或子表组成的有限序列,原子与表的差别仅在于____ 。为了区分原子和表,一般用 ____表示表,用 _____表示原子。一个表的长度是指 __,而表的深度是指__ __
6.设广义表L=((),()), 则head(L)是 ;tail(L)是 ;L的长度是 ;深度是 __。
7.基于三元组的稀疏矩阵转置的处理方法有两种,以下运算按照矩阵A的列序来进行转置,请在___________处用适当的句子用以填充。
Trans_Sparmat(SpMatrixTp a,SpMatrixTp *b) { (*b).mu=;(*b).nu=;(*b).tu=; if
{ q=1;
for(col=1; ___________;col++) for(p=1;p<=;p++)
if(___________==col) {(*b).data[q].i=[p].j; (*b).data[q].j=[p].i; (*b).data[q].v=[p].v; ___________; }
}
8. 完善下列程序。下面是一个将广义表逆置的过程。例如原来广义表为((a,b),c,(d,e)),经逆置后为:((e,d),c,(b,a))。
typedef struct glistnode {int tag;
struct glistnode *next; union{char data;
struct{struct glistnode *hp,*tp;}ptr; }val; }*glist,gnode; glist reverse(p) glist p;
{glist q,h,t,s;
if(p==NULL) q=NULL; else
{if(1) { q=(glist)malloc(sizeof(gnode)); q->tag=0; q->=p->; }
else {(2)
if (3)
{t=reverse(p-> s=t;
while(s-> s=s-> s-> s-> (4) __ }
else {q=(glist)malloc(sizeof(gnode));q->tag=1;
q-> (5) ; }
}
} return(q); }
三、应用题
1. 数组A[1..8,-2..6,0..6]以行为主序存储,设第一个元素的首地址是78,每个元素的长度为4,试求元素A[4,2,3]的存储首地址。
2. 特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能为什么
3. 数组,广义表与线性表之间有什么样的关系
4. 设有三对角矩阵(aij)n*n,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中,使得
B[k]=aij,求:
(1)用i,j表示k的下标变换公式; (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和Tail运算,把原子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. 试编写建立广义表存储结构的算法,要求在输入广义表的同时实现判断、建立。设广义表按如下形式输入(a1,a2,a3,…,an)时为只含空格字符的空表。
n>=0,其中ai或为单字母表示的原子或为广义表,n=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 其中ci,di是各维的下界和上界,Vi=di-ci+1是各维元素个数,L是一个元素所占的存储单元数。 2. 特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律,因此可以对非零元素分配单元(对值相同元素只分配一个单元),将非零元素存储在向量中,元素的下标i和j和该元素在向量中的下标有一定规律,可以用简单公式表示,仍具有随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小(t< 3. 数组是具有相同性质的数据元素的集合,同时每个元素又有唯一下标限定,可以说数组 是值和下标偶对的有限集合。n维数组中的每个元素,处于n个关系之中,每个关系都是线性的,且n维数组可以看作其元素是n-1维数组的一个线性表。广义表中的元素,可以是原子,也可以是子表,即广义表是原子或子表的有限序列,满足线性结构的特性:在非空线性结构中,只有一个称为“第一个”的元素,只有一个成为“最后一个”的元素,第一元素有后继而没有前驱,最后一个元素有前驱而没有后继,其余每个元素有唯