第五章数组和广义表习题_数据结构.doc

《第五章数组和广义表习题_数据结构.doc》由会员分享，可在线阅读，更多相关《第五章数组和广义表习题_数据结构.doc（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、习题五 数组和广义表一、单项选择题1常对数组进行的两种基本操作是（ ）A.建立与删除 B. 索引与修改 C. 查找与修改 D. 查找与索引2对于C语言的二维数组DataType Amn,每个数据元素占K个存储单元，二维数组中任意元素ai,j 的存储位置可由( )式确定.A.Loci,j=Am,n+(n+1)*i+j*kB.Loci,j=loc0,0+(m+n)*i+j*kC.Loci,j=loc0,0+(n+1)*i+j*kD.Loci,j=(n+1)*i+j*k3稀疏矩阵的压缩存储方法是只存储 ( )A.非零元素 B. 三元祖（i,j, aij） C. aij D. i,j4. 数组A0.5

2、,0.6的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A5，5的地址是( )。A. 1175 B. 1180 C. 1205 D. 12105. AN，N是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组TN（N+1）/2中，则对任一上三角元素aij对应Tk的下标k是（ ）。A. i（i-1）/2+j B. j（j-1）/2+i C. i（j-i）/2+1 D. j（i-1）/2+17. 对稀疏矩阵进行压缩存储目的是（ ）。A便于进行矩阵运算 B便于输入和输出 C节省存储空间 D降低运算的时间复杂度8. 已知广义表LS(a,b,c),(d,e,f),运

3、用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和311. 下面说法不正确的是( )。 A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表C. 广义表难以用顺序存

4、储结构 D. 广义表可以是一个多层次的结构二、填空题1通常采用_存储结构来存放数组 。对二维数组可有两种存储方法：一种是以_为主序的存储方式，另一种是以_为主序的存储方式。3设n行n列的下三角矩阵A已压缩到一维数组B1.n*（n+1）/2中，若按行为主序存储，则Ai,j对应的B中存储位置为_。4. 所谓稀疏矩阵指的是_ 。5. 广义表简称表，是由零个或多个原子或子表组成的有限序列，原子与表的差别仅在于_ 。为了区分原子和表，一般用 _表示表，用 _表示原子。一个表的长度是指 _，而表的深度是指_ _6设广义表L=(),(), 则head(L)是 ；tail(L)是 ；L的长度是 ；深度是 _。

5、三、应用题1. 数组A1.8，-2.6，0.6以行为主序存储，设第一个元素的首地址是78，每个元素的长度为4，试求元素A4,2,3的存储首地址。2. 特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能？为什么？3. 数组，广义表与线性表之间有什么样的关系？ 4. 设有三对角矩阵(aij)n*n，将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得Bk=aij，求：（1）用i,j表示k的下标变换公式；（2）用k表示i,j的下标变化公式。5画出下面广义表的头尾链表存储结构图示： (a), b), ( ), d), (e, f)6求下列广义表运算的结果：（1） HEAD(a,b),(c,

6、d); （2） TAIL(a,b),(c,d); （3） TAILHEAD(a,b),(c,d); （4） HEADTAILHEAD(a,b),(c,d); （5） TAILHEADTAIL(a,b),(c,d); 7. 利用广义表的Head和ail运算，把原子d分别从下列广义表中分离出来，L1(a),b),d),e)；L2（a,(b,(d),e)）。 第5章 数组和广义表一、单项选择题1 C2 C3 A4 A5 B6 A7 C8 C9 C10 C11 A二、填空题1顺序、列序、行序2. 第1行 第3列3i(i-1)/2+j (1=i,j=n)4. 非零元很少(tm*n)且分布没有规律5 （1

7、） 原子（单元素）是结构上不可再分的，可以是一个数或一个结构；而表带结构，本质就是广义表，因作为广义表的元素故称为子表。 （2）大写字母 （3）小写字母 （4）表中元素的个数（5）表展开后所含括号的层数6（1）（） （2）（） （3）2 （4）27 coltag=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 /头结点指向广义表三、应用题1. 958 三维数组以行为主序存储，其元素地址公式为：LOC(Aijk)=LOC(Ac1

8、c2c3)+(i-c1)V2V3+(j-c2)V3+(k-c3)*L+1其中ci,di是各维的下界和上界，Vi=di-ci+1是各维元素个数，L是一个元素所占的存储单元数。2. 特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律，因此可以对非零元素分配单元（对值相同元素只分配一个单元），将非零元素存储在向量中，元素的下标i和j和该元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小（tm*n），且分布没有规律。用十字链表作存储结构自然失去了随机存取的功能。即使用三元组表的顺序存储结构，存取下标为i和j的元素时，要扫描三元组表，下标不

9、同的元素，存取时间也不同，最好情况下存取时间为O(1)，最差情况下是O(n)，因此也失去了随机存取的功能。3. 数组是具有相同性质的数据元素的集合，同时每个元素又有唯一下标限定，可以说数组是值和下标偶对的有限集合。n维数组中的每个元素，处于n个关系之中，每个关系都是线性的，且n维数组可以看作其元素是n-1维数组的一个线性表。广义表中的元素，可以是原子，也可以是子表，即广义表是原子或子表的有限序列，满足线性结构的特性：在非空线性结构中，只有一个称为“第一个”的元素，只有一个成为“最后一个”的元素，第一元素有后继而没有前驱，最后一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。从这个意义

10、上说，广义表属于线性结构。 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；（1k3n-2） / k/3取小于k/3的最大整数。下同j=k-2(i-1)=k-2(k/3)=k%3+k/35第一种存储结构6（1） HEAD(a,b),(c,d); (a,b)（2） TAIL(a,b),(c,d); (c,d) （3） TAILHEAD(a,b),(c,d); (b)（4） HEADTAILHEAD(a,b),(c,d); b（5） TAILHEADTAIL(a,b),(c,d); (d)7. Head（Tail（Head（Head（L1） Head（Head（Head（Tail（Head（Tail（L2）