第 4  章  数组和广义表

一、选择题

1.
将一个A[1..100,1..100]的三对角矩阵,按行优先存入一维数组B[1‥298]中,A中元素A6665(即该元素下标i=66,j=65),在B数组中的位置K为(
B   )。供选择的答案:

A. 198            B. 195               C. 197  

2. 二维数组A的元素都是6个字符组成的串,行下标i的范围从0到8,列下标j的范圈从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中(   
)内的正确答案。

(1)存放A至少需要(  E )个字节;

(2)A的第8列和第5行共占(  A  )个字节;

(3)若A按行存放,元素A[8,5]的起始地址与A按列存放时的元素( B   )的起始地址一致。

供选择的答案:

(1)A. 90       B. 180        C. 240       D. 270       E. 540    

(2)A. 108      B. 114        C. 54        D. 60        E. 150    

(3)A. A[8,5]   B. A[3,10]    C. A[5,8]   D. A[0,9]     

3.
设A是n*n的对称矩阵,将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中,对上述任一元素aij(1≤i,j≤n,且i≤j)在B中的位置为(
B )。

A. i(i-l)/2+j     B. j(j-l)/2+i       C. j(j-l)/2+i-1    D. i(i-l)/2+j-1

4.
A[N,N]是对称矩阵,将下面三角(包括对角线)以行序存储到一维数组T[N(N+1)/2]中,则对任一上三角元素a[i][j]对应T[k]的下标k是(B )。

A. i(i-1)/2+j    B. j(j-1)/2+i     C. i(j-i)/2+1    D. j(i-1)/2+1

5. 设二维数组A[1.. m,1..n](即m行n列)按行存储在数组B[1.. m*n]中,则二维数组元素A[i,j]在一维数组B中的下标为( A  )。

A.(i-1)*n+j     B.(i-1)*n+j-1      C. i*(j-1)        D. j*m+i-1

6. 有一个100*90的稀疏矩阵,非0元素有10个,设每个整型数占2字节,则用三元组表示该矩阵时,所需的字节数是(B   )。

A. 60             B. 66                C. 18000             D. 33   

7. 数组A[0..4,-1..-3,5..7]中含有元素的个数( B   )。

A. 55            B. 45               C. 36            D. 16                

8.  广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为( D  )。

Head(Tail(Head(Tail(Tail(A)))))

A. (g)            B. (d)               C. c              D. d

9. 已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B),求下列运算的结果:

 tail(head(tail(C))) =(  F  )。

A.(a)      B. A       C. a        D. (b)         E. b           F. (A)

10. 广义表运算式Tail(((a,b),(c,d)))的操作结果是(   C )。

A. (c,d)          B. c,d                C. ((c,d))        D. d

11. 广义表L=(a,(b,c)),进行Tail(L)操作后的结果为(D  )。

A. c         B. b,c           C.(b,c)                D.((b,c))

12. 广义表((a,b,c,d))的表头是( A   ),表尾是(D    )。

A. a             B.()             C.(a,b,c,d)    D.(b,c,d)

二、判断题

1. 数组不适合作为任何二叉树的存储结构。( ×   )

2. 从逻辑结构上看,n维数组的每个元素均属于n个向量。( √   )

3. 稀疏矩阵压缩存储后,必会失去随机存取功能。( √   )

4. 数组是同类型值的集合。( ×   )

5. 数组可看成线性结构的一种推广,因此与线性表一样,可以对它进行插入,删除等操作。(  ×    )

6. 一个稀疏矩阵Am*n采用三元组形式表示,  若把三元组中有关行下标与列下标的值互换,并把m和n的值互换,则就完成了Am*n的转置运算。( ×     )

7. 二维以上的数组其实是一种特殊的广义表。(  √   )

8. 广义表的取表尾运算,其结果通常是个表,但有时也可是个单元素值。( ×   )

9. 若一个广义表的表头为空表,则此广义表亦为空表。( ×   )

10. 广义表中的元素或者是一个不可分割的原子,或者是一个非空的广义表。(×    )

11. 所谓取广义表的表尾就是返回广义表中最后一个元素。( ×  )

12. 广义表的同级元素(直属于同一个表中的各元素)具有线性关系。(  √   )

13. 对长度为无穷大的广义表,由于存储空间的限制,不能在计算机中实现。(  √   )

14. 一个广义表可以为其它广义表所共享。( √    )

 

三、 填空题

1.设广义表L=((),()), 则head(L)是(1) () ___;tail(L)是(2) (()_)__;L的长度是(3)2_ _;深度是  
(4)_2_。

2. 已知广义表A=(9,7,( 8,10,(99)),12),试用求表头和表尾的操作Head( )和Tail( )将原子元素99从A中取出来。

head(head(tail(tail(head(tail(tail(A)))))))

3. 广义表的深度是__表展开后所含括号的层数 ____。

4. 广义表(a,(a,b),d,e,((i,j),k))的长度是(1)   5,深度是(2)  3 _。

5. 已知广义表LS=(a,(b,c,d),e),运用head和tail函数取出LS中原子b的运算是_head(head(tail(LS)))_____。

6. 广义表A=(((a,b),(c,d,e))),取出A中的原子e的操作是: _
_head(tail(tail(head(tail(head(A))))))__。

四  应用题

1.数组A中,每个元素A[i,j]的长度均为32个二进位,行下标从-1到9,列下标从1到11,从首地址S开始连续存放主存储器中,主存储器字长为16位。求:

(1)存放该数组所需多少单元?

(2)存放数组第4列所有元素至少需多少单元?

(3)数组按行存放时,元素A[7,4]的起始地址是多少?

(4)数组按列存放时,元素A[4,7]的起始地址是多少?

(1)242 (2)22 (3)s+182 (4)s+142

 

2.
三维数组A[1..10,-2..6,2..8]的每个元素的长度为4个字节,试问该数组要占多少个字节的存储空间?如果数组元素以行优先的顺序存贮,设第一个元素的首地址是100,试求元素A[5,0,7]
的存贮首地址。

数组占的存储字节数=10*9*7*4=2520;A[5,0,7]的存储地址=100+[4*9*7+2*7+5]*4=1184

 

3. 数组,广义表与线性表之间有什么样的关系?

数组是具有相同性质的数据元素的集合,同时每个元素又有唯一下标限定,可以说数组是值和下标偶对的有限集合。n维数组中的每个元素,处于n个关系之中,每个关系都是线性的,且n维数组可以看作其元素是n-1维数组的一个线性表。

 

4. 什么是广义表?请简述广义表和线性表的主要区别。

线性表中的元素可以是各种各样的,但必须具有相同性质,属于同一数据对象。广义表中的元素可以是原子,也可以是子表。

广义表中的元素,可以是原子,也可以是子表,即广义表是原子或子表的有限序列,满足线性结构的特性:在非空线性结构中,只有一个称为“第一个”的元素,只有一个成为“最后一个”的元素,第一元素有后继而没有前驱,最后一个元素有前驱而没有后继,其余每个元素有唯一前驱和唯一后继。从这个意义上说,广义表属于线性结构

技术
©2019-2020 Toolsou All rights reserved,
(精华2020年6月2日更新) TypeScript函数详解【Python-数据读取】读取txt文件每一行数据生成列表Dijkstra算法的Python实现-最短路径问题el-ui:select获取值latex中自定义的命令———\newcommand[work] python读取txt文件最后一行一个猜数字的小游戏,用JavaScript实现python 动态规划求解单源最短路径fio使用详解Mybatis映射文件Mapper.xml中#和$的区别