数据结构作业：第4—5章作业答案.docx

第4〜5章串和数组一、填空题不包含任何字符（KJ顼为（））的串 称为空串:由一个或多个空格（fgi广日幻、力组成的串 称为空白串。
（对应严题集4.1®,简答题：简述空串和空格串的区别）假设有二维数组A6X8,每个元素用相邻的6个字节存储，存储器按字节编址。己知A的起始存储位置 （基地址）为1000,则数组A的体积（存储量）为 288 B ；末尾元素As?的第一个字节地址为—1282；若按行存储时，元素Au的第一个字节地址为（8+4）X6+1000=1072:若按列存储时，元素A47的第_个字节地址为（6X7+4）X6+1（）0（）） =1276。
（注：数组是从0行0列还是从1行1列计算起呢？由末单元为A57可知，是从0行。列开始！）00年计算机系考研题』设数组a[l・・・60, 1・・・70]的基地址为2048,每个元素占2个存储单元，若以列 序为主序顺序存储，则元素a[32,58]的存储地址8950答：不考虑 0 行 0 列，利用列优先公式：LOC（aij）=LOC（ac|, c2）+【0-C2）*（d|-C| + l）+i-C|）]*L得：LOC（a32.58）=2048+[（58-1 ）*（60-1 +1 ）+32-1 ]]*2=8950
1. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素 的行下标 、列下标 和元素值 。
2. 一个字符串中任意个连续的字符组成的子序列称为该串的子串。
3. 串是一种特殊的线性表，其特殊性表现在其数据元素都是字符；串的两种最基本的存储方式是_亟 序存储、链式存储；两个串相等的充分必要条件是串的长度相等且两串中对应位置的字符也相等
。【中国矿业大学2000 一、3 （4分）】二、单选题
（B ） I. K李』串是一种特殊的线性表，其特殊性体现在：
A.可以顺序存储B.数据元素是一个字符C.可以链式存储D.数据元素可以是多个字符2.串的长度是指（B ）【北京工商大学2001 一、6 （3分）】A.串中所含不同字母的个数B.串中所含字符的个数
C.串中所含不同字符的个数D.串中所含非空格字符的个数【91初程P78]从供选择的答案中，选出应填入下面叙述_ ?内的最确切的解答，把相应编号写在答卷的对应栏内。
有一个二维数组A,行下标的范围是0到8,列下标的范围是1到5,每个数组元素用相邻的4个字 节存储。存储器按字节编址。假设存储数组元素A[0,l]的第一个字节的地址是0。
存储数组A的最后一个元素的第一个字节的地址是4。若按行存储，则A[3,5]和A[5,3]的第一个字节的 地址分别是_和C。
A〜E：①28②44③76④92⑤108
⑥116⑦132⑧176⑨184⑩188答案：ABC=8, 3, 5,[94程PI2】有一个二维数组A,行下标的范围是1到6,列下标的范围是（）到7,每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是_A_个字节。假设存储数组元素A[l,0] 的第一个字节的地址是0,则存储数组A的最后一个元素的第一个字节的地址是B o若按行存储，
则A[2,4]的第一个字节的地址是_£_。若按列存储，则A[5,7]的第一个字节的地址是供选择的答案A〜D：①12②66③72④96⑤114⑥120
⑦ 156 ⑧ 234⑨ 276 ⑩ 282(11) 283(12) 288答案：ABCD=12, 10,3, 9三、简答题(每小题5分，共15分)1.【其他教材】己知二维数组Am,m采用按行优先顺序存放，每个元素占K个存储单元，并且第一个元
素的存储地址为Loc(all),请写出求Loc(aij)的计算公式。如果采用列优先顺序存放呢？
解：公式教材已给出，此处虽是方阵，但行列公式仍不相同；按行存储的元素地址公式是：Loc(aij)= Loc(all)+[ (i-l)*m+(j-l) ] * K按列存储的元素地址公式是：Loc(aij)= Loc(al 1) +[ (j-1 )*m+(i-l) ] * K2. (P60 4-18)用三元组表表示下列稀疏矩阵:
0000000000000000
00000000

00000000
00000-2
03000800
03000800

03000800
00000000
00060000
00009
00000
00500
00000000
00000000

00000000
00000()()5
00000 0
00003 0

20000000
解：参见填空题4.三元素组表中的每个结点对应于稀疏矩阵的•个非零元素，它包含有三个数据项，分列下标 和 元素值
(2)可列表为：

列下标 和 元素值
(2)可列表为：
8
8
5
3
2
3
3
6
8
5
4
6
7
8
5
8
1
2

别表示该元素的行下标 所以(1)可列表为：
6
6
4
1
6
-2
2
5
9
4
3
5
6
5
3

3.下列各三元组表分别表示一个稀疏矩阵，试写出它们的稀疏矩阵。
6 4 6
1 2 2
2 1 12(1) 3 1 3
44 4
5 3 6
6 1 16解：(I)为6X4矩阵，非零元素有6个。
0
2
0
0
12
0
0
0
3
0
0
0
0
0
0
4
0
0
6
0
16
0
0
0