ds200911数据结构复习

北京化工大学信息科学与技术学院计算机系史晟辉数据结构复习——复习《数据结构》课程复习参考书籍考试题型考试范围内容概述试题分析内容简介内容简介试题分析严蔚敏，吴伟民数据结构（C语言版）清华大学出版社考试题型程序题证明题计算题考试范围线性表★栈和队列★串★数组树和二叉树★图★查找★内部排序★内容概述《数据结构》课程复习数据结构逻辑结构存储结构操作●数据结构三个层次内容概述内容概述是对数据元素之间的逻辑关系、数据的存储方式以及对数据的操作的抽象描述。●数据结构定义《数据结构》课程复习●数据的逻辑结构非线性结构（树、图）线性结构（线性表）逻辑结构存储结构（物理结构）顺序存储方法散列存储方法链接存储方法索引存储方法稠密索引（DenseIndex)稀疏索引（SparseIndex）●数据的存储结构《数据结构》课程复习插入：遍历：删除：查找：排序：更新：在数据结构的各个元素中移动，查看所有数据元素向数据结构中添加新元素修改或替代数据结构中的数据元素在数据结构中去除指定的元素在数据结构中查找满足条件的元素把数据结构中的元素按要求重新排序●数据的操作《数据结构》课程复习试题1.1——线性表试题分析例1.1(10’)已知顺序结构线性表的结构定义如下：structSList{intbuffer[MAXLENGTH];inttablelen;};请编写高效算法，删除表中的所有零元，且不改变非零元的排列顺序。如，若原表为(10,2,0,0,5,7,0,4,0,0)，经过算法处理后，表为(10,2,5,7,4)。参考算法代码形式如下：intPackZero(SList&L){...}●线性表《数据结构》课程复习试题分析(10’)参考代码如下：intPackZero(SList&L){inti,j;for(i=0;iL.tablelen&&L.buffer[i]!=0;i++);for(j=i+1;jL.tablelen;j++){if(L.buffer[j]!=0){L.buffer[i]=L.buffer[j];i++;}}L.tablelen=i;return1;}《数据结构》课程复习试题1.2——线性表试题分析例1.2(10’)已知单链表的结构定义如下：structListNode{intdata;structListNode*next;};typedefListNode*LinkList;请编写算法（写出算法代码），将指定的带头结点的单链表转为逆序。参考算法代码形式如下：intReverseLinkList(LinkListA){...}●线性表《数据结构》课程复习试题分析(10’)参考代码如下：intReverseLinkList(LinkListA){if(A==NULL)return0;ListNode*p=A-next;A-next=NULL;while(p!=NULL){ListNode*q=p;p=p-next;q-next=A-next;A-next=q;}return1;}缺少异常检测扣2分。《数据结构》课程复习试题2.1——栈试题分析例2.1设入栈序列为：12345678，将入栈动作用P表示，出栈动作用Q表示。①请写出操作序列PPQPPQQPQPPQPQQQ得到的出栈序列；②请写出得到出栈序列21347685的操作序列，如果不能得到该序列，请说明原因；③请写出得到出栈序列43127865的操作序列，如果不能得到该序列，请说明原因；●栈《数据结构》课程复习试题分析参考答案：①24357861②PPQQPQPQPPPQQPQQ③要先弹出43，必须先将1234入栈，则43出栈后，栈中1已压在2下，不可能先于2出栈，得不到该序列。《数据结构》课程复习试题2.2——栈(树)试题分析《数据结构》课程考研辅导2005.12例2.2请写出二叉树前序遍历的递归算法代码(6’)和非递归算法代码(9’)。●栈（树）《数据结构》课程复习试题分析参考递归算法代码(6’)intPreTraverse(BiTreeT){if(T!=NULL){Visit(T);PreTraverse(T-lchild);PreTraverse(T-rchild);}return0;}《数据结构》课程复习试题分析参考非递归算法代码(9’)intPreTraverse(BiTreeT){StackS;InitStack(S);if(T==NULL)return0;Push(S,T);while(!EmptyStack(S)){Pop(S,T);Visit(T);if(T-rchild!=NULL)Push(S,T-rchild);if(T-lchild!=NULL)Push(S,T-lchild);}return1;}《数据结构》课程复习试题2.3——栈(树)试题分析《数据结构》课程考研辅导2005.12例2.3请写出二叉树中序遍历的递归和非递归算法代码。●栈（树）《数据结构》课程复习试题分析参考递归算法代码:intInOrderTraverse(BiTreeT){if(T==NULL)return1;InOrderTraverse(T-lchild);Visit(T);InOrderTraverse(T-rchild);return1;}《数据结构》课程复习试题分析参考非递归算法代码:intInOrderTraverse(BiTreeT){StackS;InitStack(S);while(!EmptyStack(S)||T!=NULL){while(T!=NULL){Push(S,T);T=T-lchild;}《数据结构》课程复习试题2.4——栈试题分析《数据结构》课程考研辅导2005.12例2.4已知递推式如下，写出递归算法和非递归算法。●栈mn=1f(m,n)nm=1f(m-1,n)+f(m,n-1)m1,n1《数据结构》课程复习试题分析(1)参考递归算法代码intfun(intm,intn){intf,temp;if(m==1)f=n;elseif(n==1)f=m;else{temp=fun(m-1,n);f=fun(m,n-1);f=f+temp;}returnf;}例：f(3,2)=f(2,2)+f(3,1)=f(1,2)+f(2,1)+f(3,1)=2+2+3=7mn=1f(m,n)nm=1f(m-1,n)+f(m,n-1)m1,n1《数据结构》课程复习试题分析(2)参考非递归算法代码:intfun1(intm,intn){//S[Max]为栈，top栈顶inttop=0;intsum=0;S[top].m=m;S[top].n=n;do{while(S[top].n1){while(S[top].m1){top++;S[top].m=S[top-1].m-1;S[top].n=S[top-1].n;}mn=1f(m,n)nm=1f(m-1,n)+f(m,n-1)m1,n1例：f(3,2)=f(2,2)+f(3,1)=f(1,2)+f(2,1)+f(3,1)=2+2+3=7《数据结构》课程复习试题分析(2)参考非递归算法代码：(接上)sum=sum+S[top].n;S[top].m=S[top-1].m;S[top].n=S[top-1].n-1;}sum=sum+S[top].m;while((top0)&&(S[top].m==S[top-1].m)&&(S[top].n==S[top-1].n-1)){top--;}S[top].m=S[top-1].m;S[top].n=S[top-1].n-1;}while(top!=0);returnsum;}mn=1f(m,n)nm=1f(m-1,n)+f(m,n-1)m1,n1例：f(3,2)=f(2,2)+f(3,1)=f(1,2)+f(2,1)+f(3,1)=2+2+3=7《数据结构》课程复习试题3.1——串试题分析例3.1(10’)请用改进KMP算法计算下面两个模式串的nextval值（写出结果nextval值即可）：kkmmppkkmmnextvanext●串abcabababc《数据结构》课程复习试题分析(每小题5’)答案如下：每错一位扣1分，错5位以上不给分。i0123456789TkkmmppkkmmK-1010000123-1-11000-1-110i0123456789TnextvanextK-1000000123-100000-1000nextnexti0123456789Tabcabababcnext-1000121212nextval-100-1020200《数据结构》课程复习例4.1已知多维数组A的维数和各维长度，请计算指定元素在按行优先排列的一维向量中的下标。（下标均从0开始）(1)维数为3，各维长度分别为：15、3、9。计算A(2,2,5)对应的一维下标。(2)维数为4，各维长度分别为：4、14、3、5。计算A(2,1,0,3)对应的一维下标。试题4.1——数组试题分析●数组参考答案如下：(1)Index(2,2,5)=2*3*9+2*9+5=77(2)Index(2,1,0,3)=2*14*3*5+1*3*5+0*5+3=438《数据结构》课程复习例4.2(5’)已知三元组表如下，请画出所对应的矩阵。试题4.2——数组试题分析●数组RowColValuemu:5nu:6tu:70021010372105314114333543964511《数据结构》课程复习试题分析(5’)答案如下：001070050001100000000003000009011《数据结构》课程复习例4.3已知一个稀疏矩阵如下，请画出其对应的三元组表结构，并写出对此矩阵进行快速转置的计算过程。试题4.3——数组试题分析●数组400100002003000000007025000900《数据结构》课程复习试题分析参考答案如下：(1)三元组表示如下：参考答案如下：irowcolvaluemu:6nu:5tu:800041031213232134407542264357529《数据结构》课程复习试题分析(2)快速转置过程如下：步骤1：计算转置后各行非零元个数，得到向量rsum如下：步骤2：计算转后三元组表中各行排列起点，得到向量rpos如下：步骤3：在rpos引导下对源三元组表做一趟扫描，填写到目标三元组表中，得结果三元组表如下：参考答案如下：i01234rsum21230i01234rpos02358irowcolvaluemu:5nu:6tu:800041047212332424259530163127345《数据结构》课程复习试题5.1——树试题分析例5.1(5’)已知二叉树中度为2的结点个数为n2，度为1的结点个数为n1，度为0的结点个数为n0。请证明：n2=n0-1。●树参考证明如下：设结点数为n，则，除根结点外，每个结点有唯一的父结点，因此总分支数为n-1，因此可得：n=n2+n1+n0n2*2+n1*1+n0*0=n-1综合上述两式，可得n2=n0-1《数据结构》课程复习试题5.2——树试题分析例5.2(5’)已知一棵二叉树的中序遍历序和后序遍历序，请画出这棵二叉树。中序遍历序：bgfajcdhkei后序遍历序：fgbjdcaeikh●树《数据结构》课程复习试题分析(5’)参考答案如下：ejfgdbciakh《数据结构》课程复习试题5.3——树试题分析例5.3(10’)已知一组字符及其权值如下：a:35,b:9,c:19,d:27,e:81,f:14,g:21,h:12,i:25,j:5,k:11,l:8请构造相应的哈夫曼树，画出结果哈夫曼树即可。●树《数据结构》课程复习试题分析(10’)参考答案如下：a:35,b:9,c:19,d:27,e:81,f:14,g:21,h:12,i:25,j:5,k:11,l:8a/35b/9c/19d/27f/14g/21h/12i/25j/5k/11l/8e/