数据结构题型分析复习资料

《数据结构题型分析复习资料》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构重点题型整理古月编辑【题型1】时间复杂性分析[例1]分析下列程序段的时间复杂性。m＝91；n＝100；while(n>0)if(m>0){m=m-10;n=n-1;}elsem=m+1;[解]本程序段是著名的McCarthy函数：⎧m−10m>100f(m)=⎨⎩f(f(m+1))m≤100对任何的m≤100，f(m)=91，所以此程序段实质上是一个二重循环；对每个n（n>0）值，if语句执行11次，其中10次是执行m++语句，但它们与n无关；while循环的执行次数取决于n的值大小，所以T(n

2、)=O(n)。[例2]阅读下列算法：voidsuan_fa(intn){inti,j,k,s,x;for(s=0,i=0;i

3、句的执行次数为：1+2+…+n=。2⎢n⎥（2）“x+=2;”语句的执行次数为：⎢⎥。⎣2⎦-1-数据结构重点题型整理古月编辑n(n+1)⎢n⎥（3）在for循环语句中时间复杂度为，在while循环语句中时间复杂度为⎢⎥，2⎣2⎦所以，算法时间复杂度为O(n2)。（4）s=15，x=4【题型2】数组存储地址分析[例1]数组B[1..10，-2..6，2..8]以行为主序顺序存储；设基地址（第一个元素的地址）为100，每个元素的存储长度为3；试求元素B[5，0，7]的存储地址。[解]loc(B[i,j,k

4、])=loc(B[a,b,c])+[(i-a)*(-2..6)*(2..8)+(j-b)*(2..8)+(k-c)]*3loc(B[5,0,7])=loc(B[1,-2,2])+[(5-1)*9*7+2*7+5]*3=100+(36*7+19)*3=913[例2]设有上三角矩阵(a)，将其上三角元素逐行存于数组B[1..m]中（m充分大），使ijn×n得B[k]=a，且k=f(i)+f(j)+C。试推导出函数f和f以及常数C（要求f和f不ij121212含有常数项）。[解]由于要求将上三角矩阵A上的元素

5、逐行存于数组B中。因此对于a来说，若它在Bij中的存储位置是k，则在它之前存放着A中第一行的n个元素，第二行的n−1个元素，……第i−1行的n−i+2个元素，以及第i行的j−1个元素，由此可以得到k与i,j,n的关系如下：k=n+(n−1)+⋯+（n−i+2）+j=i/2*(2n+3−i)+j−(n+1),所以，f(i)=i/2∗(2n+3+i);f(i)=j;C=−(n+1)12[例3]三对角矩阵(a)是除主对角线以及与主对角线相邻的两条对角线以外的元素全为ijn×n0，将其3条对角线上的元素逐行地存

6、于数组B[1..3n-2]中使得B[k]=a，求：ij（1）用i,j表示k的下标变换公式。（2）用k表示i,j的下标变换公式。[解]（1）k=3∗(i−1)−1+j−i+2=2i+j−2（2）i=[k/3]+1;j=[k/3]+k%3【题型3】表达式的表示[例1]已知表达式的中缀表示为（A+B）*D+E/(F+A*D)+C，试利用栈把它改写成后缀表示，并写出转换过程中栈的变化。[解]AB+D*EFAD*+/+C+[例2]对于下面的中缀表达式，画出其二叉树表示（即标识符树），并写出其前缀形式和后缀形式。（

7、1）-A+B-C+D（2）(A+B/C-D)*(E*(F+G))[解]中缀表达式所对应的二叉树如下所示：-2-数据结构重点题型整理古月编辑（1）根据中缀表达式画出的二叉树（1），其前缀形式为：+−+−ABCD，后缀形式为A−B+C−D+。（2）根据中缀表达式画出的二叉树（2），其前缀形式为：∗−+A/BCD*E+FG，后缀形式为ABC/+D−EFG+∗∗。【题型4】栈的出栈序列[例1]设有一个栈，元素的进栈次序为A、B、C、D、E，试问能否得到下面的出栈序列？若能请写出操作序列，若不能请说明原因。（1）

8、C、E、A、B、D（2）C、B、A、D、E（3）D、C、A、B、E（4）A、C、B、E、D（5）A、B、C、D、E（6）E、A、B、C、D[解]可以得到的出栈序列为（2）（4）（5）。原因如下：（2）A、B、C依次进栈后依次出栈，即得出栈顺序为C、B、A，然后D进栈后出栈，E进栈后出栈，最后的出栈序列为：C、B、A、D、E。（4）A进栈后出栈，接着B、C依次进栈再依次出栈，最后D、E依次进栈后依次出栈，最后出栈序列为：A、C、B、E、D。（