9512.net
甜梦文库
当前位置:首页 >> >>

第5章 数组和广义表(习题)



第 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 中确定 aij(i<j)的位置 k 的关 系为( )。 A. i*(i-1)/2+j B. j*(j-1)/2+i C. i*(i+1)/2+j D. j*(j+1)/2+i 3、 设二维数组 A[1.. m,1.. n](即 m 行 n 列)按行存储在数组 B[1.. m*n]中,则二 维数组元素 A[i,j]在一维数组 B 中的下标为( )。 A.(i-1)*n+j B.(i-1)*n+j-1 C. i*(j-1) D. j*m+i-1 4、对矩阵压缩存储是为了 。 A.方便压缩 B.节省空间 C. 方便存储 D. 提高运算速度 5、设广义表 L=( (a,b,c),则 L 的长度和深度分别为( ) ) 。 A. 1 和 1 B. 1 和 3 C. 1 和 2 D. 2 和 3 6、有一个 100*90 的稀疏矩阵,非 0 元素有 10 个,设每个整型数占 2 字节,则用三元 组表示该矩阵时,所需的字节数是( ) 。 A. 60 B. 66 C. 18000 D. 33 7、已知广义表 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)))) 8、已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果: tail(head(tail(C))) =( )。 A.(a) B. A C. a D. (b) E. b F. (A) 二. 判断题 1、数组是一种复杂的数据结构,数组元素之间的关系既不是线性的,也不是树形的。 2、二维以上的数组其实是一种特殊的广义表。 3、稀疏矩阵压缩存储后,必会失去随机存取功能。 4、一个稀疏矩阵 Am*n 采用三元组形式表示,若把三元组中有关行下标与列下标的值互 换,并把 m 和 n 的值互换,则就完成了 Am*n 的转置运算。 5、线性表可以看成是广义表的特例,如果广义表中的每个元素都是原子,则广义表便 成为线性表。 6、一个广义表可以为其它广义表所共享。 7、广义表中原子个数即为广义表的长度。 8、所谓取广义表的表尾就是返回广义表中最后一个元素。 9、广义表是由零或多个原子或子表所组成的有限序列,所以广义表可能为空表。



10、任何一个非空广义表,其表头可能是单个元素或广义表,其表尾必定是广义表。 三. 填空题 1、二维数组 A[6][8]采用行序为主方式存储,每个元素占 4 个存储单元,已知 A 的起始 。 存储地址(基地址)是 1000,则 A[2][3]的地址是 2、设数组 A[9][10],数组中任一元素 A[i][j]均占内存 48 个二进制位,从首地址 2000 开 始连续存放在主内存里,主内存字长为 16 位,那么 (l)存放该数组至少需要的单元数是_______; (2)存放数组的第 8 列的所有元素至少需要的单元数是_______; (3) 数组按列存储时,元素 A[5][8]的起始地址是_______。 3、所谓稀疏矩阵指的是_______。 4、当广义表中的每个元素都是原子时,广义表便成了_______。 5、求下列广义表的运算结果; GetTail(GetHead(((a,b),(c,d))))= ; 6、广义表 A=((a,b)(c,d,e)) ( , ),取出 A 中的原子 e 的操作是: _______。 7、广义表的深度是_______。 8、广义表(a,(a,b),d,e,((i,j),k))的长度是 ,深度是 。 四. 应用题 1、设二维数组 A[8][10]是一个按行优先顺序存储在内存中,已知 A[0][0]的起始存储位 置为 1000,每个数组元素占用 4 个存储单元,求: (1) A[4][5]的起始存储位置; (2) 起始存储位置为 1184 的数组元素的下标。 2、设有一个对称矩阵 A[n][n],为节省存储,将其下三角部分按行优先顺序存放在一维 数组 B[1,n(n-1)/2]中,求元素 aij 在一维数组 B 中的下标位置。 3、已知 A 为稀疏矩阵,试从时间和空间角度比较采用两种不同的存储结构(二维数组 和三元组表)实现求∑a(i,j)运算的有缺点。 4、利用三元组存储任意稀疏数组时,在什么条件下才能节省存储空间。 5、求下面各广义表的操作结果。 (1) GetHead((a,(b,c),d)) (2) GetTail((a,(b,c),d)) (3) GetHead(GetTail ((a,(b,c),d))) (4) GetTail (GetHead ((a,(b,c),d))) 6、写出对广义表 A=(x,((a,b),c,d))作运算 head(head(tail(A)))后的结果。 7、画出下列广义表的两种存储结构图((),A,(B,(C,D)),(E,F))。 8、数组、广义表与线性表之间有什么样的关系? 五. 算法设计题 1、试设计一个算法,将数组 A[n]中的元素 A[0]至 A[n-1]循环右移 k 位,并要求时间 复杂度为 O(n) ,只用一个元素大小的附加存储。 2、 已知数组 A[1..n]的元素类型为整型, 设计算法调整 A, 使其左边的所有元素小于零, 右边的所有元素大于等于零。 (要求算法的时间复杂度和空间复杂度均为 0(n)。 ) 3、已知具有 m 行 n 列的稀疏矩阵 A,请写一算法,将稀疏矩阵转换为三元组表示。 4、已知两个稀疏矩阵 A 和 B,其行数和列数均对应相等,编写一个函数,计算 A 和 B 之和,假设稀疏矩阵采用三元组表示。

5、已知两个稀疏矩阵 A 和 B,其行数和列数均对应相等,编写一个函数,计算 A 和 B 之和,假设稀疏矩阵采用十字链表表示。 6、编写一个广义表的复制算法。 7、编写一个判别两个广义表是否相等的函数,若相等,则返回 1;否则,返回 0。相等 的含义是指两个广义表具有相同的存储结构,对应的原子结点的数据域值也相同。 8、编写一个计算广义表长度的算法,例如:一个广义表为(a,(b,c),((e))),其长度 为 3。



更多相关文章:
第五章数组和广义表习题_数据结构
第五章数组和广义表习题_数据结构_理学_高等教育_教育专区。习题五 数组和广义表 一、单项选择题 1.常对数组进行的两种基本操作是( ) A.建立与删除 B. 索引与...
第5章 数组和广义表 自测题含答案
第5章 数组和广义表 自测题含答案_理学_高等教育_教育专区。第5章 数组和广义表 自测题含答案 一、单选题 1. 假设有二维数组 A6×8,每个元素用相邻的 6 个...
数据结构习题第五章 数组和广义表答案
数据结构习题第五章 数组和广义表答案_理学_高等教育_教育专区。第 5 章数组和广义表 一、单项选择题 1. C 2. C 3. B 4.A 5.C 6. A 7.A 8. C ...
数据结构 数组和广义表习题
第五章 数组和广义表习题一、选择题 1.已知广义表 LS=((a,b,c),(d,e,f)), 运用 head 和 tail 函数取出 LS 中原子 e 运算是 。 A.head(tail(LS))...
第5章 数组和广义表 自测题含答案
第5章 数组和广义表 自测题含答案_计算机软件及应用_IT/计算机_专业资料。第5章 数组和广义表 自测题含答案 一、单选题 1. 假设有二维数组 A6×8,每个元素用...
第五章数组和广义表习题_数据结构
广义表可以是一个多层次的结构 二、填空题 1.通常采用___存储结构来存放数组 。对二维数组可有两种存储方法:一种是以 ___为主序的存储方式,另一种是以___...
《数据结构》习题集:第5章_数组和广义表(第1次更新2012...
《数据结构》习题集:第5章_数组和广义表(第1次更新2012-3)_理学_高等教育_教育专区。做过的作业题数据结构课后练习题 数组和广义表 第 5 章 数组和广义表 第...
(习题)数据结构第五章 数组与广义表
(习题)数据结构第五章 数组与广义表_电脑基础知识_IT/计算机_专业资料。第五章 数组与广义表 5.1 假设有二维数组 A6×8,每个元素用相邻的 6 个字节存储, ...
第5章 数组和广义表
第5章 数组和广义表 一、基础知识题 5.1 已知二维数组 A[3][5],其每个元素占 3 个存储单元,并且 A[0][0]的存储 地址为 1200。 求元素 A[1][3]的...
第五章数组和广义表
第五章数组与广义表一.选择题 1.下面的说法不正确的是___。 A.数组是一种线性结构 B.数组是一种定长的线性表结构 C.除了插入与删除操作外,数组的基本操作...
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图