数据结构练习题数组和广义表.doc

《数据结构练习题数组和广义表.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、已知二维数组A[3][5]，其每个元素占3个存储单元，并且A[0][0]的存储地址为1200。求元素A[1][3]的存储地址（分别对以行序和列序为主序存储进行讨论），该数组共占用多少个存储单元？ 【解答】按照以行序为主序存储公式：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(A[1][3])=1200+(1*5+3)*3=1224 (按行序存储)  LOC(A[1

2、][3])=1200+(3*3+1)*3=1230 (按列序存储) 有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，A[1][1]为第一元素，其存储地址为1，每个元素占一个地址空间，求A[7][5]和A[5][6]的地址。 【解答】按照公式：LOC(A[7][5])=7(7-1)/2＋5 = 26  LOC(A[5][6])=LOC(A[6][5])=6(6-1)/2+5=20 设有一个二维数组A[m][n]，设A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，

3、问A[3][3]存放在什么位置？ 因为A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，说明一行有15个元素（算法：（676－2－644）/2）。A[3][3]存放位置是692。二维数组A[9][10]的元素都是6个字符组成的串，请回答下列问题：（1）存放A至少需要( )个字节； （2）A的第7列和第4行共占( )个字节； （3）若A按行存放，元素A[7][4]的起始地址与A按列存放时哪一个元素的起始地址一致。 【解答】按照题5.1给出的公式： （1）存放A需要9*10*6

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

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

6、【解答】GetHead(L)和GetTail(L)的值是()和(())。L的长度和深度都是2。   求下列广义表运算的结果： (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,

7、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 选择题：下面说法不正确的是A. 广义表的表头总是一个广义表B. 广义表的表尾总是一个广义表 C.广义表难以用顺序存储结构D.广义表可以是一个多层次的结构【解答

8、】A 利用广义表的GetHead和GetTail操作写出函数表达式，把以下各题中的单元素banana从广义表中分离出来：(1) (apple，pear，banana， orange)  (2) ((apple，pear)，(banana，orange))  (3) ((((apple)))，((pear))，(banana)，orange) (4) (apple，(pear，(banana)，orange))