数据结构第4章习题

《数据结构第4章习题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第4章习题解答一、填空1.字符串是一种特殊的线性表，特殊在于它的数据元素只能是一字符,特殊在于串可以作为一个参与所需要的处理。2.空格串是由组成的串，空串是的串，因此空格串和空串不是一个概念。3.字符串中任意多个字符所组成的子序列，被称作是这个串的“子串”，这个字符串木身则称为“主串”。4.我们说两个字符串相等，在计算机内部实际上是通过对相应位置上字符码的比较而得到的结论。5.设有串s=1)个具有」业L类型的

2、数据的有序集合。8.矩阵与通常所说的[维数组冇关。9.所谓“特殊矩阵”,是指那些元素在矩阵小的分布具有一定规律性的矩阵；而矩阵小的零元素个数远远多于非零元素的个数，但非零元素的分布却没有规律，这样的矩阵被称为“稀疏矩阵”。10.在一个阶方阵A中，若所有元素都有性质：=n),就称其为对称矩阵。二、选择1•设有两个串si和s20求s2在si中首次出现的位置的操作称为oA.连接B.模式匹配C.求了串D.求串长2・有串：“①"，那么它的长度是oA.0B.1C.2D.33.设有串sl=“ABCDEFG'和s2=“PQRSF'。已知:算法con(x,y)返回串x和y的连接串；subs(s,i,j)返

3、回串s的第i个字符开始往后j个字符组成的子串；len(s)返回串s的长度。那么，con(subs(sl,2,len(s2)),subs(sl,len(s2),2))的操作结果是串。A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF4.设有一个8阶的对称矩阵A,采用以行优先的方式压缩存储。an为第1个元索，其存储地址为1,每个元素占一个地址空间。试问元素a*5的地址是oA.33B.30C.13D.235.一个加检的对称矩阵，如果以行优先的方式压缩存入内存。那么所需存储区的容量应该是oA.加*(加・1)/2B.m冰ird2C.加*(加+1)/2D.伽+1)*伽+1)/26.二

4、维数组M的每个元索含4个字符(每个字符占用一•个存储单元)，行下标i从1变到5,列下标j从1变到60那么按行顺序存储时元素M[4][6]的起始地址与M按列顺序存储时元素的起始地址相同。A.M⑶⑸B.M[4][5]C.M[4][6]D.M⑸⑸7.二维数组M中的每个元素占用3个存储单元，行下标i从1变到8,列下标j从1变到10o现从首地址为SA的存储区开始存放A。那么该数组以行优先存放时，元素A[8][5]的起始地址应该是OA.SA+141B.SA+180C.SA+222D.SA+2253.设有一个5阶上三角矩阵A,将其元素按列优先顺序存放在一维数组B中。已知每个元素占用2个存储单元，B［l

5、］的地址是100。那么A⑶［4］的地址是oA.116B.118C.120D.122(分析：把一个上三角矩阵按列优先顺序存放在一个一维数组B中，元素的顺序是：anai2a223i3A［3,4］的地址=100+a34前面的元素个数*2=100+(前3列的个数+木列a34前面的个数)*2=100+((1+2+3)+2)*2=116三、问答1.为什么可以把二维数组视为是一种线性结构？答：实际上，二维数组是一种较为复杂的数据结构，数据元素之间的关系并不是线性的。不过，如果我们把它看作是其每个元索为一维数纽的一个-•维数组，那么就可以把二维数组视为是线性表的一种推广(因为一维数组即是线性表)，因此可

6、以说它的数据元素间的逻辑关系呈现出的是一种线性结构。A=0002.图4・34(a)所示为一个特殊矩阵Ase这种形式的短阵被称作是“带状矩阵”，因为它的非零元素都分布在以主对角线为中心的一个带状区域里，其他位置上的元素全部为0o可以以行优先的方式，将具压缩存储到一个一维数组里，如图4-34(b)所示。试找出元素下标i、丿与存储序号k间的对应关系。128003166250\567147\上面的791928I上面的、■次对角线076、61卜」主对角线(a)序号412345678910111213值：1283166255671477919287661元素名:anana：ia22a

7、ia^2a%a到3344»45a$4a$5图4・34带状矩阵答：压缩存储元素卜•标i、j与存储序号k间的对应关系是：k=2*i+j—23.一个稀疏矩阵如图4・35所示。试问，它对应的三元组表是什么？03005000A=00-1800000900■图4・35稀疏矩阵示例稀蔬惩阵遇的三元纽表545-特殊的三元纽135d非零元素的三元纽21333-1348529四、应用1.请将算法4-1改为用while循环来实现。答：改写的算法4・1可以