广西广播电视中等专业学校
01级五年制计算机应用,网络专业《数据结构》期末考试复习提要
2004年1月
绪论
理解数据结构的基本概念及算法的基本概念.
重点掌握数据的三种基本结构:线性结构,树结构,图形结构.
重点掌握数组的结构以及数组的顺序存储结构中元素数目的计算,存储地址的计算.
基本题型:
二维数组A[10][20]每个元素占4个存储单元,并且A[0][0]的存储地址是100,则A[6][12]的存储地址是多少
解: LOC (A[6][12])=100+(6*12+12)*4=628
已知三维数组M[-1…7][0…8][1…12]每个元素占用3个存储单元,并且第一个元素的存储地址为1000,试求:
数组M需要的内存空间.
元素M[5][5][7]的存储地址.
解:(1) p*m*n=9*9*12=972
LOC(A[5][5][7])=1000+{ ( I +1)*9*12+(j – 0)*12+(k — 1) }* L
=1000+{6*9*12+5*12+6}*3=3142
一种数据结构B=(K,R),其中K={a,b,c,d,e,f,g,h} ,R={r1,r2,r3},且r1={,,,,,,}
r2={,,,,,,}
r3={(a,b),(b,c),(b,d),(c,d),(c,e),(c,f),(d,e),(e,f),(f,g),(f,h)}
请画出它们分别对应的逻辑图形表示,并指出它们分别属于哪一种类型

解:r1是线性结构:○a ○b ○c ○d ○e ○f ○g ○h
r2 是树结构:○d r3是图型结构: ○a
○b ○a ○b
○g ○c ○c ○d
○e ○h ○f ○e
○f ○g ○h
线性表
1.重点掌握线性表的概念和操作.
2.要能区分栈与队列的异同:栈的特性是LIFO而队列的特性是LILO,它们都有两种存储结构,一种是顺序存储,另一种是链式存储.重点操作:元素的出栈与入栈,元素的出队与入队.
3.理解串的定义及基本操作.
4.要能够用后缀形式表达一个算术式.
基本题型:
算术式a*(a+b)—b*(b+a)的后缀表达式为:aab+*bba+*—
算术式16—9*(4+3)的波兰表达式为:16 9 4 3 + * —
3. 已知一个栈的入栈序列是1,2,3,…..,n,其输出序列为p1,p2,p3,……pn,若p1=1,则pi为( A ).
A.n - i +1 B. n – i C. n D.1
4. 判定一个栈ST(最多元素为m0)为空的条件是( B ).
A.ST-- >top m0 B.ST-- >top=0 C.ST-- >top m0 D.ST-->top= m0
5.判定一个队列QU(最多元素为m0)为满队列的条件是( A ).
A.QU-- >rear—QU-- >front = =m0 B.QU-- >rear—QU-- >front – 1 = = m0

下一页