数据结构练习题-数组和广义表(共2页).doc

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

1、精选优质文档-倾情为你奉上已知二维数组A35，其每个元素占3个存储单元，并且A00的存储地址为1200。求元素A13的存储地址（分别对以行序和列序为主序存储进行讨论），该数组共占用多少个存储单元？ 【解答】按照以行序为主序存储公式：LOC(i，j)=LOC(c1，c2)+(i-c1)*(d2-c2+1)+(j-c2)*L在C语言中有：LOC(i，j)=LOC(0，0)+(i*(d2+1)+j)*L 则：LOC(A13)=1200+(1*5+3)*3=1224 (按行序存储)LOC(A13)=1200+(3*3+1)*3=1230 (按列序存储)有一个10阶的对称矩阵A，采用压缩存储方式以行序为

2、主序存储，A11为第一元素，其存储地址为1，每个元素占一个地址空间，求A75和A56的地址。【解答】按照公式：LOC(A75)=7(7-1)/25=26 LOC(A56)=LOC(A65)=6(6-1)/2+5=20 设有一个二维数组Amn，设A00存放位置在644，A22存放位置在676，每个元素占一个空间，问A33存放在什么位置？ 因为A00存放位置在644，A22存放位置在676，每个元素占一个空间，说明一行有15个元素（算法：（6762644）/2）。A33存放位置是692。二维数组A910的元素都是6个字符组成的串，请回答下列问题：（1）存放A至少需要()个字节； （2）A的第7列和

3、第4行共占()个字节； （3）若 A按行存放，元素A74的起始地址与A按列存放时哪一个元素的起始地址一致。【解答】按照题5.1给出的公式：（1）存放A需要9*10*6=540个字节（2）A的第7列和第行共占(9+10-1)*6=108个字节（3）LOC(A74)=LOC(A00)+7*10+4*L (按行序存储)LOC(Aij)=LOC(A00)+j*9+i*L（按列序存储，0=i=8,0=j=9)所以,i=2,j=8。 即元素A74的起始地址与A按列存放时A28的起始地址一致。什么是广义表？请简述广义表和线性表的主要区别。【解答】广义表是零至多个元素的有限序列，广义表中的元素可以是原子，也可

4、以是子表。从“元素的有限序列”角度看，广义表满足线性结构的特性：在非空线性结构中，只有一个称为“第一个”的元素，只有一个称为“最后一个”的元素，第一元素有后继而没有前驱，最后一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。从这个意义上说，广义表属于线性结构。当广义表中的元素都是原子时，广义表就蜕变为线性表。求广义表D=(a，(b，()，c)，(d)，e)的长度和深度。【解答】3和3 设广义表L=()，()，试问GetHead(L)，GetTail(L)的值，求L的长度和深度各为多少? 【解答】GetHead(L)和GetTail(L)的值是()和()。L的长度和深度都是2。求下列广

5、义表运算的结果：(1)GetHead(p，h，w)(2)GetTail(b，k，p，h) (3)GetHead(GetTail(a，b)，(c，d)(4)GetTail(GetHead(a，b)，(c，d)【解答】(1)GetHead(p,h,w)=p(2)GetTail(b,k,p,h)=(k,p,h) (3)GetHead(GetTail(a，b)，(c，d)=GetHead(c,d)=(c,d)(4)GetTail(GetHead(a，b)，(c，d)=GetTail(a,b)=(b) 选择题：对矩阵压缩存储是为了A.方便运算B.方便存储C.提高运算速度D.减少存储空间【解答】D 选择题

6、：下面说法不正确的是A.广义表的表头总是一个广义表B.广义表的表尾总是一个广义表C.广义表难以用顺序存储结构D.广义表可以是一个多层次的结构【解答】A 利用广义表的GetHead和GetTail操作写出函数表达式，把以下各题中的单元素banana从广义表中分离出来：(1)(apple，pear，banana，orange)(2)(apple，pear)，(banana，orange)(3)(apple)，(pear)，(banana)，orange)(4)(apple，(pear，(banana)，orange)【解答】 (1)GetHead(GetTail(GetTail(apple,pear,banana,orange)(2)GetHead(GetHead(GetTail(apple,pear),(banana,orange)(3)GetHead(GetHead(GetTail(GetTail(apple),(pear),(banana),orange)(4)GetHead(GetHead(GetTail(GetHead(GetTail(apple,(pear,(banana),orange)专心-专注-专业