第五章数组与广义表
一．选择题
1．下面的说法不正确的是____________。
A．数组是一种线性结构B．数组是一种定长的线性表结构
C．除了插入与删除操作外，数组的基本操作还有存取、修改、检索和
排序等
D．数组的基本操作有存取、修改、检索和排序等，没有插入和删除操
作
分析：数组的主要操作是存取、修改、检索和排序。数组没有插入和修改
错误。答案应选择C。
2．一维数组A 采用顺序存储结构，每个元素占用6 个字节，第6 个元素的起始地址为100，则该数组的首地址是
。
A．64 B．28 C．70 D．90
分析：设数组元素的首地址为x，则存在关系x+5*6=100，因此x 为70，答案应选择C。
3．稀疏矩阵采用压缩存储的目的主要是______________ 。
A．表达变得简单B．对矩阵元素的存取变得简单
C．去掉矩阵中的多余元素D．减少不必要的存储空间的开销
分析：答案应选择D。
4．若对n 阶对称矩阵A 以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B 中确
定aij(i A. i*(i+1)/2+j B. j*(j+1)/2+i C. i*(i+1)/2+j+1 D. j*(j+1)/2+i+1 分析：设以行为主序放对称矩阵的下三角元素，其存储结 构如5.4 所示，a00 存储在B[1],a10 存储在B[2], …… an-1n-1 存储在B[n (n+1)/2]，则对称矩阵k 与(i，j)的对应关系为：故答案 应选择B。 B[ ] 1 2 3 4 5 6 … k … (n(n+1))/2-1 (n(n+1))/2 A a00 a10 a11 a20 a21 a22 … aij … a(n-1) (n-2) a(n-1) (n-1) 图5.4 对称矩阵的存储示意图 5．已知广义表LS=((a,b,c), (d,e,f))，运用GetHead 和GetTail 运算取 出LS 中的元素e 的运算是 。 A．GetHead(GetTail(LS)) B．GetHead(GetTail(GetTail (GetHead (LS)))) C ． GetTail (GetHead (LS)) D．GetHead(GetTail(GetHead(GetTail(LS)))) 分析：本题的解答过程要应用排除法，分别对A、B、C、D 选项进行计算并判断。根据选项D 可知：GetHead(GetTail(GetHead(GetTail(LS))))＝ GetHead(GetTail(GetHead ((d,e,f))))= GetHead(GetTail(d,e,f))= GetHead((e,f))=e。答案应选 择D。 6. 设广义表L=((a,b,c))，则L 的长度和深度分别为 。 A. 1 和1 B. 1 和3 C. 1 和2 D. 2 和3 i(i+1)/2+j+1ij k= j(j+1)/2+i+1i 分析：该题目主要考查广义表的长度和深度的基本概念，广义表的长度是广义表中层次为1 的元素个数，而广义表的深度是指广义表展开后所含括 号的层数。因此本题中的L 的长度为1，L 的深度为2。答案应选择C。7. 一个100*90 的稀疏矩阵，非0 元素有10 个整型数，设每个整型数占2 字节，则用三元组表示该矩阵时，所需的字节数是_____________。 A. 60 B. 66 C. 18000 D. 33 分析：三元组表结构为(行，列，元素值)，用三元组表表示稀疏矩阵时， 还需记录稀疏矩阵的行数、列数以及非零元素个数，本题中所需的字节数 应为10*(1+1+1)*2+3*2＝66。答案应选择D。 二判断题 1．稀疏矩阵压缩后，必会失去随机存取功能。 正确 分析：具有存取任一个元素的时间相等这一特点的存储结构称为随机存取结构。对稀疏矩阵压缩存储所用的存储结构是三元组表或十字链表。十字链 表因其链表结构而不能随机存取；而使用三元组表存储矩阵时，若要访问 元素aij，则必须扫描三元组表，显然查找三元组表中前后元素所消耗的时 间不同。 2．线性表可以看成是广义表的特例，如果广义表中的每个元素都是原子， 则广义表便成为线性表。 正确 3．广义表中的元素可以是一个不可分割的原子，或者是一个非空的广义表。错误。 分析：该题目主要考查广义表的定义，广义表中元素可以是原子，也可以 是表(包括空表和非空表)。 4．广义表中原子个数即为广义表的长度。 错误 分析：该题目主要考查广义表长度的定义，广义表的长度是广义表中层次 为1 的元素个数。因此本题说法是片面的。 5．数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插 入，删除等操作。 错误 分析：数组可以看成一种特殊的线性表，数组在维数和上下界确定后，其 元素个数已经确定，不能进行插入和删除运算。但线性表可以插入删除。二．填空题 1．需要压缩存储的矩阵可分为 矩阵和 矩阵两种。 答案：特殊矩阵稀疏矩阵 分析：关于矩阵的压缩存储方法，根据矩阵的特点分为特殊矩阵和稀疏矩 阵。特殊矩阵要求进行压缩存储时保持其随机存取特性不变，而稀疏矩阵 则会失去随机存取功能。 2．设数组A[0..8,1..10],数组中任一元素A[i,j]均占内存48 个二进制位， 从首地址2000 开始连续存放在主内存里，主内存字长为16 位，那么 (1) 存放该数组至少需要的单元数是(1) ； (2) 存放数组的第8 列的所有元素至少需要的单元数是(2) ； (3) 数组按列优先存储时，元素A[5,8]的起始地址是(3) 。 答案：(1) 270 (2) 27 (3) 2204 分析：(1)数组A[0..8,1..10]的数组元素个数为9*10＝90，因此存放该数 组的单元个数为90*48/16＝270，其中每个单元占据48/16=3 个字长。(2) 存放数组的第8 列的所有元素应为9*48/16＝27。(3)若数组按列优先存储，元素A[5,8]的起始地址为2000+(7*9+5)*3＝2204。 3．设数组A[1..50,1..80]的基地址为2000，每个元素占2 个存储单元， 若以行序为主序顺序存储，则元素A[45,68]的存储地址为(1) ; 若以列序为主序顺序存储，则元素A[45,68]的存储地址为(2) 。 答案：(1)9174 (2)8878 分析：本题主要考查计算某元素的存储地址，注意区分按行为主序和以列 为主序的存储方式。 (1)A[45,68]的存储地址=2000+((45-1)*80+67)*2＝9174； (2)A[45,68]的存储地址=2000+((68-1)*50+44)*2＝8788。 4．设广义表L=(()，()) ，则GetHead(L)是 ；GetTail(L) 是 ；L 的长度是 ；L 的深度 是 。 答案：() (()) 2 2 分析：对于广义表LS=(a1,a2,a3,…,an)，各个运算如下： 表头：GetHead(LS)=a1 表尾：GetTail(LS)= (a2,a3,…,an) 长度：Length(LS)=n 深度： 故答案为：GetHead(L)=()；GetTail(L)=(())；L 的长度为2；L 的深度为 2。 5．广义表中的元素，可以是(1) ，所以其描述宜采用程序1LS ()0LS 1+MAX{Depth(ai)|i=1,2,...,n}LS 当为空 表 当为原 子 当为子 表 DepthLS 设计语言的(2) 来表示。 答案：(1)原子元素或广义表(2)联合或共同体 分析：根据广义表定义，广义表中的元素，即可以是原子元素，也可以是 广义表。因此其描述应采用程序设计语言的联合或共同体来表示。 6．设某广义表H=(A,(a,b,c)) ，运用GetHead 函数和GetTail 函数求出广 义表H 中某元素 b 的运算式______________ 。 答案：GetHead(GetTail(GetHead(GetTail(H)))) 分析：本题的解题思路可参见5.2.1 节第5 题，获得元素b 操作的运算式为 GetHead(GetTail(GetHead(GetTail(H))))。具体过程如下： （1）GetTail(H)=((a,b,c)) （2）GetHead(((a,b,c)))＝(a,b,c) （3）GetTail((a,b,c))＝(b,c) （4）GetHead((b,c))=b （5）b＝GetHead(GetTail(GetHead(GetTail(H)))) 四．应用题 1．设有三对角矩阵An×n，将其三条对角线上的元素按行优先顺序存储到向量B[0..3n-3]中，使得B[k]=aij，求： (1)用i,j 表示k 的下标变换公式； (2)用k 表示i,j 的下标变换公式； 分析与解答：三对角矩阵为 A 为 0001 101112 2,32,22,1 1,21,1 nnnnnn nnnn aa aaa aaa aa 将其按行存储到向量B 中，得到的存储形式如下： LOC(B*0+) …… LOC(B*3n-3]) a00 a01 a10 a11 a12 …… an-2,n-3 an-2,n-2 an-2,n-1 an-1,n-2 an-1,n-1 第0 行第1 行第n-2 行第n-1 行 (1)元素的二维下标(i,j)与一维向量中的位置k 的对应关系为：k=3*i-1+j-i+1=2*i+j (2) 一维向量中的位置k 与元素的二维下标(i,j)的对应关系为：i=int((k+2)/3), j=k-2*i 2．假设一个准对角矩阵： a11 a12 a21 a22 a33 a34 a43 a44 …. aij a2m-1,2m-1 a2m-1,2m a2m,2m-1 a2m,2m 按以下方式存储于一维数组B[4m]中: 0 1 2 3 4 5 6 … k … 4m-1 4m a11 a12 a21 a22 a33 a34 a43 … aij … a2m-1,2m a2m,2m-1 a2m,2m 写出由一对下标(i,j)求k 的转换公式。 分析与解答：将准对角矩阵看成是对角线元素为矩阵的对角矩阵。 11 0 mm A A 首先计算出aij 所处在对角矩阵Amm 中的位置，计算公式为int((i-1)/2)，int()为取整操作。则int((i-1)/2)*4 为对角矩阵所处在一维数组B 中的 位置。 其次计算aij 的所处在的对角矩阵Amm 中的相对位置。 具体转换公式如下： k=int((i-1)/2)*4+(i-1)%2*2+1 当i k=int((i-1)/2)*4+(i-1)%2*2 当i>j 或当i=j 且i 为奇数 3．设稀疏矩阵 0-31000 00100-1 000000 002000 000040 000000 A (1)画出其三元组表形成的压缩存储表。 (2)画出其十字链表形成的压缩存储表。 分析与解答： (1)稀疏矩阵的三元组表为： s=((1,2,-3),(1,3,1),(2,3,1),(2,6,-1),(4,3,2),(5,5,4)，其中三元组 分别表示非零元素行号、列号以及元素值。其顺序存储结构如图5.5 所示。 1 2 3 0 1 2 -3 1 1 3 1 2 2 3 1 3 2 6 -1 4 4 3 2 5 5 5 4 6 稀疏矩阵行数 6 稀疏矩阵列数 6 稀疏矩阵非零 元素个数 图5.5 稀疏矩阵A 的三元组表 (2)十字链表法实际上是采用链式存储结构表示三元组表。在链表中，每个 非零元可用一个含有五个域的结点表示。其存储结构定义如图5.2 所示。稀疏矩阵A 所对应的十字链表存储结构如图5.6 所示。 图5.6 稀疏矩阵A 的十字链表 4．画出下列广义表的图形表示。 (1)A(a,B(b,d),C(e,B(b,d),L(f,g,h))) (2)A(a,B(b,A)) 分析与解答： （1）A(a,B(b,d),C(e,B(b,d),L(f,g,h)))的图形表示如图5.7(a)所示。 （2）A(a,B(b,A)) 的图形表示如图5.7(b)所示。 (a) (b) 图5.7 1 2 - 3 1 3 1 2 3 1 2 6 - 1 4 3 2 5 5 4 6 6 H2 H4 H5 H6 H3 H1 H4 H3 H5 H6 Head H1 H2 5．画出下列广义表的存储结构图，并利用Head 和Tail 操作分离出原子e。 (1) L=(((a)),(b),c,(a),(((d,e)))) (2) L=((x,a),(x,a,(b,e)),y) (3) L=(a,((),b),(((e)))) 分析与解答：由于广义表中的数据元素既可能是列表也可能是单元素，相 应结点的结构形式有两种：一种是表结点，用以表示列表；另一种是元素 结点，用以表示单元素。在表结点中应该包括一个指向表头的指针和指向 表尾的指针；而在元素结点中应该包括所表示单元素的元素值。为了区分 这两类结点，在结点中还要设置一个标志域，如果标志为1，则表示该结点 为表结点；如果标志为0，则表示该结点为元素结点。 (1) L=(((a)),(b),c,(a),(((d,e))))的存储结构如图5.8(a)所示。 获取原子e 的操作为： GetHead(GetTail(GetHead(GetHead(GetHead(GetTail(GetTail (GetTail(GetTail(L)))))))))。 (2) L=((x,a),(x,a,(b,e)),y) 的存储结构如图5.8(b)所示。 获取原子e 的操作为： GetHead(GetTail(GetTail(GetHead(GetTail(L)))))。 (3) L=(a,((),b),(((e)))) 的存储结构如图5.8(c)所示 获取原子e 的操作为： GetHead(GetHead(GetHead(GetHead(GetTail(GetTail(L))))))。 (a)表结点(b)元素结点 tag=1 hp tp tag=0 data 图5.8 广义表的存储结构图 五．算法设计题 1. 已知两个稀疏矩阵A 和B，其行数和列数均对应相等，编写一个函数， 计算A 和B 之和，假设稀疏矩阵采用三元组表示。 分析：按照行优先的顺序同时扫描稀疏矩阵A 和B，若当前A 与B 中的数的行值和列值均相同，则将两数相加，若相加结果不为0，则将其结构存入三 元组表C 中；若当前 A 中数的行值小，或者行值与当前B 中数的行值相等，而列值小于当前B 中的数的列值，则将当前A 中数存放到三元组表C 中，否则将当前B 中数存放到C 中。当稀疏矩阵A 和B 有一个先扫描结束，则1 1 ∧ 1 1 ∧ 1 ∧ 1 ∧ 1 ∧ 1 ∧ e a L b (c) 1 1 1 1 1 ∧1 ∧1 1 ∧1 0 y 1 ∧0 e 0 a 0 b 0 a 0 x L 0 x (b) 1 1 1 1 1 ∧1 ∧1 ∧1 1 ∧ 1 ∧ 1 ∧ 1 d 1 ∧ e a c b a L (a) 将另一个的剩余数据以此放入C 中。 typedef struct tripletable SPMatrix; /*三元组表 SPMatrix*/ 算法描述如下： SPMatrix *Matrix_add (SPMatrix *A, SPMatrix *B) /*稀疏矩阵A+B，结果存放到C*/ { SPMatrix *C; C->m=A->m; /*置稀疏矩阵C 的行数*/ C->n=A->n; /*置稀疏矩阵C 的列数*/ pa=0 ; pb=0 ; pc=0; while (pa {if((A->data[pa].i==B->data[pb].i) && (A->data[pa].j==B->data[pb].j) && ((A->data[pa].v + B->data[pb].v)!=0)) /*A 和B 的行号、列号相同，且它们的之和不为零*/ { C->data[pc].i=A->data[pa].i; C->data[pc].j=A->data[pa].j; C->data[pc].v=A->data[pa].v + B->data[pb].v; pc++ ; pa++ ; pb++ ; } if((A->data[pa].i < B->data[pb].i)|| (A->data[pa].i==B->data[pb].i && A->data[pa].j< B->data[pb].j)) , /*A 的行号小于B 的行号或者A 和B 的行号相同，且A 的列号小于B 的列号*/ C->data[pc].i=A->data[pa].i; C->data[pc].j=A->data[pa].j; C->data[pc].v=A->data[pa].v; pc++ ;pa++; } else /*A 的行号大于B 的行号*/ { C->data[pc].i=B->data[pb].i; C->data[pc].j=B->data[pb].j; C->data[pc].v=B->data[pb].v; pc++; pb++; } } while ( pa { C->data[pc].i=A->data[pa].i; C->data[pc].j=A->data[pa].j; C->data[pc].v=A->data[pa].v; pc++; pa++; } while(pb<=B->t ) /*B 中有剩余元素*/ { C->data[pc].i=B->data[pb].i; C->data[pc].j=B->data[pb].j; C->data[pc].v=B->data[pb].v; pc++; pb++; } C->t=pc; return C; /*返回C*/ } 2．编写一个以三元组形式输出用十字链表存储表示的稀疏矩阵中非零元素以及下标的算法。 分析：本题主要考查十字链表的基本遍历操作。遍历十字链表的方法，通常是逐行依次遍历每一行链表，将所访问的结点插入到三元组中。其操作类似于单链表的遍历操作。 tripletable Convert(crosslist *head) /*将十字链表表示的稀疏矩阵转换成以三元组形式存储*/ { int k=0; /*用于统计稀疏矩阵中非零元素个数*/ crosslist *p; tripletable table; /*定义三元组table*/ p=head->next; table.m=head->row; /*将十字链表所表示的稀疏矩阵的行数赋值给三 元组表*/ table.n=head->col; /*将十字链表所表示的稀疏矩阵的列数赋值给三 元组表*/ for(;p!=head; p=p->next) /*依次访问十字链表的行所在的表头结点 */ { for(q=p;q->right!=p;q=q->right) /*依次遍历十字链表的行*/ { table.data[k].i=q->row; /*将十字链表中的元素插入 到三元组中*/ table.data[k].j=q->col; table.data[k].v=q->value; k++; } } table.t=k; /*记录三元组中非零元素个数*/ return table; } 3．编写一个算法计算广义表的长度。 分析：(1)若广义表采用教材中5.1.3 节所描述的链式存储结构，则这种存储结构的最高层的表结点个数就是广义表的长度。可以通过扫描广义表的第一层的每个结点，直到遇到表尾指针为空的元素，利用计数器可得到广义表的长度。 广义表的数据结构定义参见本章的5.1.6 节。 算法描述如下： int length(Glist L) { Glist p=L; int count=0; /*设置计数器*/ while(p!=NULL) { p=p->ptr.tp; /*沿表尾指针扫描第一层*/ count++; } return count; /*广义表的长度*/ - (2)本题也可以利用递归函数实现，本题的问题递归定义如下： 1 当广义表为空 时 广义表长度广义表表尾的长度广义表非空 时 算法描述如下。 int length(GList L) { if(L==NULL) return 0 ; /*广义表为空时*/ else return(1+length(l->ptr.tp)); /*长度＝表尾的长度+1*/ } 4. 编写一个函数计算一个广义表的原子结点个数，例如一个广义表为(a,(b,c),((e)))，其原子结点数目为4。 分析：广义表的定义是一个递归定义，即一个广义表中又可含有广义表。其链式存储结构具有一定递归特性，一个广义表可以用表头和表尾来表示，所以本题可以考虑用递归的方法实现。其递归定义如下： 0p=NULL Count(p)=1p->tag=0 Count(p->hp)+Count(p->tp)p->tag=1 其中p 表示指向广义表链表中的结点，Count(p)表示从指针p 可以得到的原子结点个数。 算法描述如下： int Count(GList p) { if(p==NULL) return 0; else { if(p->tag==0) return 1; else return(Count(p->ptr.hp)+Count(p->ptr.tp)); } } 5．广义表具有可共享性，因此在遍历一个广义表时必需为每一个结点增 加一个标志域mark，以记录该结点是否访问过。一旦某一个共享的子表结点被作了访问标志，以后就不再访问它。 (1) 试定义该广义表的数据结构； (2) 采用递归的算法对一个非空的广义表进行遍历。 (3) 试使用一个栈，实现一个非递归算法，对一个非空广义表进行遍历。 分析: 该题目就是对非空广义表进行遍历，对访问过的结点设置已访问标 志即可。 (1)其数据结构定义如下： typedef enum {ATOM, LIST} Elemtag; /*ATOM=0：单元素；LIST=1： 子表*/ typedef struct GLNode { Elemtag tag; /*标志域，用于区分元素结点 和表结点*/ int mark; /* mark 为0，表示未访问，mark 为1，表示已访问*/ union { /*元素结点和表结点的联合 部分*/ DataType data; /*data 是元素结点的值域*/ struct { struct GLNode *hp, *tp; }ptr; /*ptr 是表结点的指针域，ptr.hp 和ptr.tp 分别指向 表头和表尾*/ }; }*GList; (2) 非空广义表的递归遍历算法如下描述： void Traverse(GList L) { if(L!=NULL && !L->mark) { L->mark=1; if(L->tag==0) visit(L->data); /*访问原子结点*/ else { Traverse(L->ptr.hp); Traverse(L->ptr.tp); } } } (3) 非空广义表的非递归遍历算法如下描述： void traverse(GList L) { Glist p=L; PSeqStack S; /*定义一个栈S,其中DataType 类型为struct GLNode*/ S=Init_SeqsStack(); /*初始化栈*/ while ((p)||!Empty_SeqStack(S)) /*当前p 不空或者栈不为空*/ { if (p) { if ((!p->mark) && (p->tag==0)) , p->mark=1; /*标志结点p 已被访问*/ visit(p->data); /*访问广义表结点p*/ p=NULL; /*返回到上一层进行处理*/ } else if ((p->mark) && (p->tag==0)) p=NULL; else if ((!p->mark) && (p->tag==1)) { p->mark=1; /*标志结点p 已被访问*/ Push_SeqStack(S, p->ptr.tp); p=p->ptr.hp; } else p=NULL; /*返回到上一层进行处理*/ } else Pop_SeqStack (S,&p); } } 6. 假设广义表按如下形式的字符串表示。(a1,a2,…,an)n≥0 其中ai 或为单字母表示的原子，或为广义表；n=0 时，用只含空格字符的空表( )。按照教材中所示的链表结点结构编写，按照读入的一个广义表字符串建立其存储结构的递归算法。 分析：若广义表为空表，则其输入形式为′( )′，其特点是在左括弧之 后输入的是空格字符′′；若广义表非空，则在左括弧之后输入的必为表头，它或是表示原子的单字母，或是子表的首字符′(′,其它均为非法字符。对非空的广义表，在表头之后输入的合法字符或为′)′,或为′,′， 前者表明表尾为空表，后者表明为非空表。 数据结构定义见5.1.6 节。 算法描述： #define ERROR 0 #define OK 1 int Create_GList(GList *L) /*根据输入创建广义表L,并返回指针*/ { scanf("%c",&ch); if(ch==' ') { *L=NULL; scanf("%c",&ch); if(ch!=')') return ERROR; return OK; } *L=(GList)malloc(sizeof(GLNode)); /*生成广义表表头*/ *L->tag=1; if(isalphabet(ch)) /*输入是字母*/ { p=(GList)malloc(sizeof(GLNode)); /*建原子型的表头*/ p->tag=0;p->data=ch; *L->ptr.hp=p; } else if(ch=='(') Create_GList(&(L->ptr.hp)); /*建子表型的表头*/ else return ERROR; scanf ("%c",&ch); if(ch==')') *L->ptr.tp=NULL; else if(ch==',') Create_Glist(&(L->ptr.tp)); /*建子表型的表尾*/ else return ERROR; return OK; /*结束并返回1*/ } 第五章数组和广义表 一．选择题 1．在二维数组A 中引用A[i,j]的时间_________。 A．与i、j的大小有关 B．与i、j的大小无关 C．与i的大小有关，与j的大小无关 D．与i的大小无关，与j的大小有关 2．在稀疏矩阵的带行指针向量的链接存储中，每一行单链表中的结点都具有相同的________。 A．行号 B．列号 C．元素值 D.地址 3．二维数组A 按行顺序存储，其中每个元素占1个存储单元。若 A[1][1]的存储地址为420， A[3][3]的存储地址为446，则A[5][5]的存储地址为_______。A．470 B．471 C．472 D. 473 4．在稀疏矩阵的十字链接存储中，每个列单链表中的结点都具有相同的_____。A．行号 B．列号 C．元素值 D.地址 5．下面的说法中，不正确的是________。 A．对称矩阵中只须存放包括主对角线元素在内的下(或上)三角部分的元素即可B．对角矩阵中只须存放的非零元素即可 C．稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储 D．稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储6．对一些特殊矩阵采用压缩存储的目的主要是为了________。 A．表达变得简单 B．对矩阵元素的存取变得简单 C．去掉矩阵中的多余元素 D．减少不必要的存储空间的开销 7．若将n 阶对称矩阵 A 按照行序为主序方式将包括主对角线元素在内的下三角形的所有元素依次存放在一个一维数组 B 中，则该对称矩阵在 B 中占用了________个数组元素。 A．n2 B．n*(n-1) C．n*(n+1)／2 D．n*(n-1) 8. 稀疏矩阵的三元组顺序表表示的一个三元组中不包括________。 A. 行号 B.列号 C.元素值 D.元素总数 9．稀疏矩阵一般的压缩存储方法有两种，即________。 A．二维数组和三维数组 B．三元组和散列 C. 三元组和十字链表 D．散列和十字链表 10．有一个 10 阶对称矩阵 A，采用压缩存储方式(以行序为主存储，且A[0 Ⅱ0]=1)，则A[8][5]的地址是________。 A．52 B．48 C．54 D．53 11.数组通常具有的两种基本操作是________。 A．建立与删除 B．索引和修改 C．查找和修改 D．查找与索引12．二维数组M 的成员是 6 个字符(每个字符占一个存储单元)组成的串，行下标 i 的范围从0 到 8，列下标j 的范围从1到10，则存放M 至少需要________个字节。 A．90 B．180 C．240 D．540 13．二维数组M 的元素是4 个字符(每个字符占一个存储单元)组成的串，行下标 i 的范围从0 到 4 ，列下标j 的范围从0 到 5,M 按行存储时元素M[3 Ⅱ5]的起始地址与M 按列存储时元素________的起始地址相同。 第五章数组和广义表：习题 习题 一、选择题 1．假设以行序为主序存储二维数组A[1．．100,1．．100]，设每个数据元素占两个存储单元，基地址为10，则LOC(A[5，5])=( )。 A. 808 B. 818 C. 1010 D. 1020 2．同一数组中的元素( )。 A. 长度可以不同B．不限C．类型相同 D. 长度不限 3．二维数组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 (2) A. 108 B. 114 C. 54 D. 60 (3)[8][5] B. A[3][10] [5][8] [O][9] 4.数组与一般线性表的区别主要是( )。 A.存储方面 B.元素类型方面 C.逻辑结构方面 D.不能进行插入和删除运算 5．设二维数组A[1．．m，1．．n]按行存储在数组B[1．．m×n]中，则二维数组元素A[i，j]在一维数组B中的下标为( )。 A. (i-l)×n+j B. (i-l)×n+j-l C．i×(j-l) D. j×m+i-l 6．所谓稀疏矩阵指的是( )。 A.零元素个数较多的矩阵 B.零元素个数占矩阵元素中总个数一半的矩阵 C.零元素个数远远多于非零元素个数且分布没有规律的矩阵 D.包含有零元素的矩阵 7．对稀疏矩阵进行压缩存储的目的是( )。 A.便于进行矩阵运算 B.便于输入和输出 C.节省存储空间 D. 降低运算的时间复杂度 8．稀疏矩阵一般的压缩存储方法有两种，即( )。 A.二维数组和三维数组 B.三元组和散列 C.三元组和十字链表 D.散列和十字链表 9．有一个100×90的稀疏矩阵，非0元素有10个，设每个整型数占两字节，则用三元组表示该矩阵时，所需的字节数是( )。 A. 60 B. 66 C．18000 D．33 10. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N(N+I)/2] 中，则对任一上三角元素a[i][j]对应T[k]的下标k是( )。 A. i(i-l)/2+j B. j(j-l)/2+i C. i(j-i)/2+1 D. j(i-l)/2+1 11．已知广义表L=((x，y,z)，a，(u，t，w))，从L表中取出原子项t的运算是( ) A. head(tail(tail(L))) B. tail(head(head(taiI(L)))) C. head(tail(head(taiI(L)))) D. head(tail(head(tail(tail(L))))) 习题五数组和广义表 一、单项选择题 1．常对数组进行的两种基本操作是（） A.建立与删除 B. 索引与修改 C. 查找与修改 D. 查找与索引2．对于C语言的二维数组DataType A[m][n],每个数据元素占K个存储单元，二维数组中任意元素a[i,j] 的存储位置可由( )式确定. A.Loc[i,j]=A[m,n]+[(n+1)*i+j]*k B.Loc[i,j]=loc[0,0]+[(m+n)*i+j]*k C.Loc[i,j]=loc[0,0]+[(n+1)*i+j]*k D.Loc[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 中的第_ _行，第_ _列的元素。 第5章 数组和广义表 自测题含答案 一、单选题 1. 假设有二维数组A 6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A 的起始存储位置（基地址）为1000，则数组A 的体积（存储量）为 288 B ；末尾元素A 57的第一个字节地址为 1282 ；若按行存储时，元素A 14的第一个字节地址为 (8+4)×6+1000=1072 ；若按列存储时，元素A 47的第一个字节地址为 (6×7＋4)×6＋1000）＝1276 。 2. 〖00年计算机系考研题〗设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为 8950 。 答：不考虑0行0列，利用列优先公式： LOC(a ij )=LOC(a c 1， c 2)+[(j-c 2)*( d 1-c 1+1)+i-c 1)]*L 得：LOC(a 32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2＝8950 3. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 行下标 、 列下标 和 元素值 。 4. 求下列广义表操作的结果： （1） GetHead 【((a,b),(c,d))】=== (a, b) ; //头元素不必加括号 （2） GetHead 【GetTail 【((a,b),(c,d))】】=== (c,d) ; （3） GetHead 【GetTail 【GetHead 【((a,b),(c,d))】】】=== b ; （4） GetTail 【GetHead 【GetTail 【((a,b),(c,d))】】】=== （d ） ; 二、单选题（ A ）1. 〖01年计算机系考研题〗假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为 。（无第0行第0列元素） Ａ．16902 Ｂ．16904 Ｃ．14454 Ｄ．答案A, B, C 均不对 答：此题与填空题第8小题相似。（57列×60行＋31行）×2字节＋10000=16902 ( B )2. 设矩阵A 是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素a i,j (i ≤j), 在一维数组B 中下标k 的值是： Ａ．i(i-1)/2+j-1 Ｂ．i(i-1)/2+j Ｃ．i(i+1)/2+j-1 Ｄ．i(i+1)/2+j ??????????????=n n n n a a a a a a A ,2 ,1,2 ,21,21 ,1 第5章数组和广义表习题 一、选择题 1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（B）。 i×（i-1）/2+j-1~~~~（i>=j） 8×7÷2+5=33因为a11从1开始所以要加1 A. 13 B. 33 C. 18 D. 40 2. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( A)。 所求=a+(j*n+j)*l A. 1175 B. 1180 C. 1205 D. 1210 3. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（i 第5章 数组和广义表 5.1数组 一、填空题 1. 假设有二维数组A 6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A 的起始存储位置 （基地址）为1000，则数组A 的体积（存储量）为 ；末尾元素A 57的第一个字节地址为 。 2. 三元组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素 的 、 和 。 3. 设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则 元素a[32,58]的存储地址为 。 4. 设n 行n 列的下三角矩阵A 已压缩到一维数组B[1..n*（n+1）/2]中，若按行为主序存储，则A[i,j] 对应的B 中存储位置为 。 5. 设有一个10阶对称矩阵A 采用压缩存储方式（以行为主序存储：a 11=1），则a 85 的地址为 。 6. 设下三角矩阵A 如果按行序为主序将下三角元素A i j (i ≤j)存储在一个一维数组B[1..n(n+1)/2]中， 对任一个三角矩阵元素A ij ,它在数组B 中的下标为 。 二、选择题 1. （ ）假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为10000， 每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为 。 A ．16902 B ．16904 C ．14454 D ．答案A, B, C 均不对 2. （ ）对特殊矩阵采用压缩存储的目的主要是为了 。 A ．表达变得简单 B ．对矩阵元素的存取变得简单 C ．去掉矩阵中多余元素 D ．减少不必要的存储空间 3. （ ）对于n 阶对称矩阵，如果以行序或列序放入内存中，则需要 个存储单元。 A ．n(n+1)/2 B ．n(n-1)/2 C ． n 2 D ．n 2 /2 4. 有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时， 所需的字节数是 。 A. 60 B. 66 C. 18000 D. 33 5. 对稀疏矩阵进行压缩存储目的是（ ）。 A ．便于进行矩阵运算 B ．便于输入和输出 C ．节省存储空间 D ．降低运算的时间复杂度 6. （ ）设矩阵A 是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一 维数组B[1, n(n-1)/2 ]中，对下三角部分中任一元素a i,j (i ≤j), 在一维数组B 中下标k 的值是 。 A ．i(i-1)/2+j-1 B ．i(i-1)/2+j C ．i(i+1)/2+j-1 D ．i(i+1)/2+j 三、判断题： 1．（ ）一个稀疏矩阵Am*n 采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把 ?????? ? ???????=n n n n a a a a a a A ,2,1 ,2,21,21,1Λ Λ 第五章答案 5.2设有三对角矩阵A n×n,将其三条对角线上的元素逐行的存于数组B[1..3n-2]中，使得 B[k]=a ij，求：（1）用i,j表示k的下标变换公式；（2）用k表示i、j的下标变换公式。【解答】（1）k=2(i-1)+j (2) i=[k/3]+1, j=[k/3]+k%3 （[ ]取整，%取余） 5.4在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个辅助向量空间。 【解答】算法（一） FastTransposeTSMatrix(TSMartrix A, TSMatrix *B) {/*把矩阵A转置到B所指向的矩阵中去，矩阵用三元组表表示*/ int col,t,p,q; int position[MAXSIZE]; B->len=A.len; B->n=A.m; B->m=A.n; if(B->len>0) { position[1]=1; for(t=1;t<=A.len;t++) position[A.data[t].col+1]++; /*position[col]存放第col-1列非零元素的个数, 即利用pos[col]来记录第col-1列中非零元素的个数*/ /*求col列中第一个非零元素在B.data[ ]的位置，存放在position[col]中*/ for(col=2;col<=A.n;col++) position[col]=position[col]+position[col-1]; for(p=1;p 第五章数组与广义表 一．选择题 1．下面的说法不正确的是____________。 A．数组是一种线性结构B．数组是一种定长的线性表结构 C．除了插入与删除操作外，数组的基本操作还有存取、修改、检索和 排序等 D．数组的基本操作有存取、修改、检索和排序等，没有插入和删除操 作 分析：数组的主要操作是存取、修改、检索和排序。数组没有插入和修改 错误。答案应选择C。 2．一维数组A 采用顺序存储结构，每个元素占用6 个字节，第6 个元素的起始地址为100，则该数组的首地址是 。 A．64 B．28 C．70 D．90 分析：设数组元素的首地址为x，则存在关系x+5*6=100，因此x 为70，答案应选择C。 3．稀疏矩阵采用压缩存储的目的主要是______________ 。 A．表达变得简单B．对矩阵元素的存取变得简单 C．去掉矩阵中的多余元素D．减少不必要的存储空间的开销 分析：答案应选择D。 4．若对n 阶对称矩阵A 以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B 中确 定aij(i 第五章数组和广义表 一、单项选择题 1．一维数组A采用顺序存储结构，每个元素占用6个字节，第6个元素的存储地址为100，则该数组的首地址是（）。 A．64 B．28 C．70 D．90 2．稀疏矩阵采用压缩存储的目的主要是（）。 A．表达变得简单B．对矩阵元素的存取变得简单 C．去掉矩阵中的多余元素D．减少不必要的存储空间的开销 3．一个非空广义表的表头（）。 A．不可能是原子B．只能是子表 C．只能是原子D．可以是子表或原子 4．常对数组进行的两种基本操作是（）。 A．建立与删除B．索引与修改 C．查找和修改D．查找与索引 5. 设二维数组A[5][6]按行优先顺序存储在内存中，已知A[0][0] 起始地址为1000，每个数组元素占用5个存储单元，则元素A[4][4]的地址为（）。 A．1140 B．1145 C．1120 D．1125 6．设有一个20阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a9,2在一维数组B中的下标是（）。 A．41 B．32 C．18 D．38 7．稀疏矩阵的压缩存储方式通常有两种，即（）。 A．二元组和三元组B．三元组和散列 C．三元组和十字链表D．散列和十字链表 8．广义表（a，（a，b），d，e，（（I，j），k））的长度和深度分别是（）。 A．5，3 B．5，5 C．6，4 D．6，6 9．广义表（（a），a）的表头是（）。 A．a B．（a）C．（）D．（（a）） 10．二维数组A[20][10]采用行序为主序方式存储，每个数据元素占4个存储单元，且A[10][5]的存储地址是1000，则A[18][9]的存储地址是（）。 A．1208 B．1212 C．1368 D．1336 11．二维数组A中，每个数据元素占4个字节，行下标从0到4，列下标从0到5，按行优先存储时元素A[3][5]的地址域同按列优先存储时元素（）的地址相同。 A．A[2][4] B．A[3][4] C．A[3][5] D．A[4][4] 二、问答题 1、简述广义表和线性表的区别与联系。 2、设广义表L=((),())，试问head(L)、tail(L)、L的长度、深度各为多少？ 第四章数组与广义表（作业） 一、判断题 1.数组是同类型值的集合。 2.数组是一组相继的内存单元。 3.数组是一种复杂的数据结构，数组元素之间的关系，既不是线 性的，也不是树型的。 4.插入和删除操作是数据结构中最基本的两种操作，所以这两种 操作在数组中也经常使用。 5.数组的存储方式分为顺序和链式两种。 6.使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间。 7.广义表是由零或多个单元素或子表所组成的有序列，所以广义 表可能为空表。 8.线性表可以看成是广义表的特例，如果广义表中的每个元素都 是单元素，则广义表便成为线性表。 二、选择题 1.一个n*n的对称矩阵，如果以行或列为主序存入内存，则其容 量为（）。 A.n*n B.n*n/2 C.n(n+1)/2 D.(n+1)*(n+1)/2 E.(n-1)*n/2 F.n(n-1) 2.在二维数组A[7][9]中，假定每个数据元素占4个存储单元，A00 的存储位置（基地址）为100，则A56的存储位置为（）。 A.232 B.151 C.204 D.304 3.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主 存储，a11为第一个元素，其存储地址为1，每个元素占1个地址空间，则a85的地址为（）。 A.13 B.33 C.18 D.40 4.二维数组a的每个元素是由6个字符组成的串，行下标i的范 围从0-8，列下标j的范围是从1-10。 （1）存放a至少需要( ）个字节。 A.90 B.180 C.240 D.270 E.540 （2）A的第8列和第5行共占（）字节。 A.108 B.114 C.54 D.60 E.150 （3）若a按行存放，元素a[8,5]的起始地址与当a按列存放的元素( ）的起始地址一致。 A.a[8,5] B. a[3,10] C.a[5,8] D. a[0,9] 5.已知广义表LS=（a,(b,c,c),e）,运用HEAD和TAIL函数取出LS中 的单元素b的运算是（）。 A.HEAD(HEAD(LS)) B.TAIL(HEAD(LS)) C.HEAD(HEAD(TAIL(LS))) D.HEAD(TAIL(LS)) 6.已知广义表A=((a,b,c),(d,e,f)),从A中取出单元素e的运算是 （）。 A.TAIL(HEAD(A)) B.HEAD(TAIL(A)) C.HEAD(TAIL(TAIL(HEAD(A)))) D.HEAD(TAIL(HEAD(TAIL(A)))) E.HEAD(TAIL(TAIL(A))) 1．广义表(((a)))的表头是(((a)))，表尾是( ) 。 2．假设一个10阶的下三角矩阵A按列优先顺序压缩存储在一维数组B中，则B数组的大小应为55。(1+10)*10／2 3．假设三维数组A[10][9][8]按行优先顺序存储，若每个元素占3个存储单元，且首地址为100，则元素A[9][8][7]的存储地址是2257 。 4．对矩阵采用压缩存储是为了节省空间。 5．广义表（a,(a,b),d,e,((i,j),k)）的长度为5。 ？？？1．二维数组A[12][18]采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A[9][7]的地址为（ A ） A．429 B．432 C．435 D．438 ？？？2．二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为（A）A．1207 B．1209 C．1211 D．1213 3．对广义表L=（（a,b）,(c,d), (e,f)）执行操作tail(tail(L))的结果是（B）A．(e,f) B．((e,f)) C．(f) D．() 1．已知稀疏矩阵采用带行表的三元组表表示，其形式说明如下： #define MaxRow 100 //稀疏矩阵的最大行数 typedef struct { int i,j,v; //行号、列号、元素值 }TriTupleNode; typedef struct{ TriTupleNode data[MaxSize]; int RowTab[MaxRow+1]; //行表 int m,n,t; //矩阵的行数、列数和非零元个数 }RTriTupleTable; 下列算法f的功能是，以行优先的顺序输入稀疏矩阵的非零元（行号、列号、元素值），建立稀疏矩阵的带行表的三元组表存储结构。请在空缺处填入合适内容，使其成为一个完整的算法。（注：矩阵的行、列下标均从1起计） void f (RTriTupleTable *R) 第五章数组和广义表 讲课提要 【主要内容】 1．多维数组的顺序存储结构 2．特殊矩阵的压缩存储 3．广义表的定义及其与线性表的关系 4．广义表的存储结构 5．广义表运算实现中递归的应用 【教学目标】 1．掌握多维数组的顺序存储结构 2．掌握特殊矩阵的压缩存储方法 3．掌握广义表的定义及其与线性表的关系 4．掌握广义表的存储结构 5．了解广义表运算实现中递归的应用 学习指导 1．多维数组的顺序存储结构 对于多维数组，有两种存储方式： 一是以行为主序（或先行后列）的顺序存放，如BASIC、PASCAL、C等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。 另一种是以列为主序（先列后行）的顺序存放，如FORTRAN语言中，用的是以列为主序的分配顺序，即一列一列地分配。 以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，…，从右向左，最后是左下标。以列为主序分配的规律是：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，…，从左向右，最后是右下标。 不论按何种方式存储，只要确定了数组的首地址以及每个数组元素所占用的单元数，就可以将数组元素的存储地址表示为其下标的线性函数。设有m×n二维数组A mn，以“以行为主序”的分配为例，按照元素的下标确定其地址的计算方法如下。 设数组的基址为LOC(a11)，每个数组元素占据L个地址单元，计算a ij 的物理地址的函数为： LOC(a ij) = LOC(a11) + ( (i-1)*n + j-1 ) * L 同理，对于三维数组A mnp，即m×n×p数组，对于数组元素a ijk其物理地址为：LOC(a ijk)=LOC(a111)+( ( i-1) *n*p+ (j-1)*p +k-1) )*L 注意：在C语言中，数组中每一维的下界定义为0，则： LOC(a ij) = LOC(a00) + ( i*n + j ) * L 【例4-1】二维数组A的每一个元素是由6个字符组成的串，其行下标i=0，1，…，8，列下标j=1，2，…，10。若A以行为主序存储元素，A[8][5]的物理地址与当A按列为主序存 习题五数组和广义表一、单项选择题）1．常对数组进行的两种基本操作是（ D.查找与索引C.B.索引与修改建立与删除A. 查找与修改 K 个存储单元，二维数组中DataType A[m][n],2．对于 C 语言的二维数组每个数据元素占.( )a[i,j]的存储位置可由任意元素式确定 A.Loc[i,j]=A[m,n]+[(n+1)*i+j]*k B.Loc[i,j]=loc[0,0]+[(m+n)*i+j]*k C.Loc[i,j]=loc[0,0]+[(n+1)*i+j]*k D.Loc[i,j]=[(n+1)*i+j]*k 3．稀疏矩阵的压缩存储方法是只存储( ) A. 非零元素三元祖（i,j, aij）D. i,jC. aij B. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为10004. ( )的地址是A[5 ，5]的内存单元中，则元素。 A. 1175 B. 1180 C. 1205 D. 1210 A[N，N] 是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N （N+1）/2]5. 对应T[k] 的下标k是（中，则对任一上三角元素）。a[i][j] （i-1）/2+j（j-i）/2+1（（j-1）/2+i i-1 ）/2+1D. jB. jA. iC. i j 沿用数组r 存储静态链表，结点的next 域指向后继，工 作指针j 指向链中结点，使6. ( )链移动的操作为。 A. j=r[j].next B. j=j+1D. j=r[j]-> next C. j=j->next 对稀疏矩阵进行压缩存储目的是（）。7. A．便于进行矩阵运算．便于输入和输出B ．节省存储空间C．降低运算的时间复杂度D LS＝((a,b,c),(d,e,f)),函数取出LS 中原子运用head 和tail e 的运算是已知广义表8. 。)( A. head(tail(LS)) B. tail(head(LS)) C. head(tail(head(tail(LS))) D. head(tail(tail(head(LS)))) 广义表（（a,b,c,d），表尾是（））的表头是（）。9. （a,b,c,d（b,c,d）（））D.C.A. aB. L=（（a,b,c）），则L 的长度和深度分别为（设广义表）。10.和 3 1和和和3 2B. 1C. 1A. 1D. 211.下面说法不正确的是( )。 A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表 C. 广义表难以用顺序存储结构 D.广义表可以是一个多层次的结构二、填空题 存储结构来存放数组___________1．通常采用。对二维数组可有两种存储方法：一种是以 第五章数组与广义表 一、假设有二维数组A6*8，每个元素用相邻的6个字节存储，存储器按字节 编址。已知A的起始存储位置（基地址）为1000。计算： 1、数组A的体积（即存储量）； 2、数组A的最后一个元素a57的第一个字节的地址； 3、按行存储时，元素a14的第一个字节的地址； 4、按列存储时，元素a47的第一个字节的地址； 答案： 1、（6*8）*6=288 2、loc(a57)=1000+(5*8+7)*6=1282或=1000+（288-6）=1282 3、loc(a14)=1000+(1*8+4)*6=1072 4、loc(a47)=1000+(7*6+4)*6=1276 二、假设按低下标(行优先)优先存储整数数组A9*3*5*8时第一个元素的字节地址是100，每个整数占四个字节。问下列元素的存储地址是什么？ （1）a0000(2)a1111(3)a3125 (4)a8247 答案：（1）100 （2）loc(a1111)=100+(1*3*5*8+1*5*8+1*8+1)*4=776 (3) loc(a3125)=100+(3*3*5*8+1*5*8+2*8+5)*4=1784 (4) loc(a8247)=100+(8*3*5*8+2*5*8+4*8+7)*4=4416 五、设有一个上三角矩阵（aij）n*n,将其上三角元素逐行存于数组B[m]中，（m 充分大），使得B[k]=aij且k=f1(i)+f2(j)+c。试推导出函数f1,f2和常数C（要求f1和f2中不含常数项）。 答： K=n+(n-1)+(n-2)+…..+(n-(i-1)+1)+j-i =(i-1)(n+(n-i+2))/2+j-i 所以f1(i)=(n+1/2)i-1/2i2 f2(j)=j c=-(n+1) 九、已知A为稀疏矩阵，试从空间和时间角度比较采用两种不同的存储结构（二 第5章数组和广义表 习题 一. 选择题 1、数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。 A. 1175 B. 1180 C. 1205 D. 1210 2、若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定a ij（i 第5章数组与广义表 一、选择题 1.在以下讲述中，正确的是（B ）。 A、线性表的线性存储结构优于链表存储结构 B、二维数组是其数据元素为线性表的线性表 C、栈的操作方式是先进先出 D、队列的操作方式是先进后出 2.若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转 置运算，这种观点（B ）。 A、正确 B、错误 3.二维数组SA 中，每个元素的长度为3 个字节，行下标I 从0 到7，列下标J 从0 到9，从首地址SA 开始 连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为（ B ）。 A、SA+141 B、SA+180 C、SA+222 D、SA+225 4.数组SA 中，每个元素的长度为3 个字节，行下标I 从0 到7，列下标J 从0 到9，从首地址SA 开始连续 存放在存储器内，存放该数组至少需要的字节数是（ C ）。 A、80 B、100 C、240 D、270 5.常对数组进行的两种基本操作是（C ）。 A、建立与删除 B、索引和修改 C、查找和修改 D、查找和索引 6.将一个A[15][15]的下三角矩阵（第一个元素为A[0][0]），按行优先存入一维数组B[120]中，A 中元素A[6][5] 在B 数组中的位置K 为（B ）。 A、19 B、26 C、21 D、15 7.若广义表A 满足Head(A)=Tail(A)，则A 为（B ）。 A、（） B、（（）） C、（（），（）） D、（（），（），（）） 8.广义表（（a）,a）的表头是（C ），表尾是（C ）。 A、a B、b C、(a) D、((a)) 9.广义表（（a,b）,c,d）的表头是（C ），表尾是（D ）。 A、a B、b C、(a,b) D、(c,d) 10.广义表（（a））的表头是（B ），表尾是（C ）。 A、a B、(a) C、() D、((a)) 11.广义表（a,b,c,d）的表头是（A ），表尾是（D ）。 A、a B、(a) C、(a,b) D、(b,c,d) 12.广义表（（a,b,c,d））的表头是（C ），表尾是（B ）。 A、a B、() C、(a,b,c,d) D、((a,b,c,d)) 13.下面结论正确的是（BC ）。 A、一个广义表的表头肯定不是一个广义表 B、一个广义表的表尾肯定是一个广义表 C、广义表L=（（），（A，B））的表头为空表 D、广义表中原子个数即为广义表的长度 14.广义表A=（A,B,(C,D),(E,(F,G))），则head(tail(head(tail(tail(A)))))=( D ) A、(G) B、(D) C、C D、D第五章 数组和广义表
数据结构 第五章数组和广义表
(完整word版)数据结构第五章数组和广义表习题及答案
第5章 数组和广义表 自测题含答案
第五章 数组和广义表
数据库系统l试题库及答案 第5章数组和广义表
第5章 数组和广义表答案
第五章数组和广义表
第五章数组和广义表
第五章数组与广义表(作业)
第5章 数组和广义表
第5章 数组和广义表
第五章数组和广义表习题_数据结构
数据结构课后习题答案第五章数组与广义表
第5章 数组和广义表(习题)
《数据结构》习题集：第5章 数组与广义表
相关主题
文本预览