数据结构期末复习文档

《数据结构期末复习文档》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一、问答题1.循环队列的优点是什么？如何判断它的空和满？答：循环队列可解决队列的假溢出。方法之一是附设一个存储队屮元素个数的变量如num,当num==O时队空，当num==MAXSIZE时为队满＜：另一种方法是少用一个元素空间，所示的情况就视为队满，此时的状态是队尾指针加1就会从后面赶上队头指针，这种情况下队满的条件是：(rear+1)%MAXSIZE==front,也能和空队区别开。队空：from==rear2.栈和队列数据结构的特点，什么情况下用到栈，什么情况下用到队列？答：栈是在表的一端进行插入和删除的线性表。后进先出的线性表前而所讲的栈是一种后进先出的数据结构；队列--种

2、''先进先出”(FIFO…FirstInFirstOut)的数据结构：即插入在表一端进行，而删除在表的另一端进行，我们将这种数据结构称为队或队列，3.什么是递归？递归程序有什么有优点？答:函数在运行过程小直接或间接的调用了自己，称为递归。优点：程序简单、结构清晰、符合结构化程序设计、可读性好。4•假设按行优先存储整数数组A[9][3]⑸[8]时，第一个元素的字节地址时100,每个整数占4个字节。问下列元素的存储地址是什么。(第四章3)Aijkl=100+(i*3*5*8+j*5*8+k*8+l)*4=100+(i*120+j*40+k*8+l)*4(l)aoooo100(2)^1

3、11100+169*4=776⑶巧必100+421M=1784⑷遜247100+1079*4二44165•现有如下稀疏矩阵A要求划出以下各种表示方法000220・150133000000-60000000091000000028000142216-15221323334-651916328(1)三元组表示法(2)十字链表法Arliuk1•一棵度为2的树与一棵二叉树有何区别？树与二叉树之间有何区别？答:度为2的树至少有一个节点的读为2,二叉树的度不一定为2；该树不空，二叉树空以空；树分为有序树和无序树，二叉树是有序的；二叉树有左右孩子，而树没有；二叉树度为0〜2,而树的度是大于等于

4、0区别：度为2的树有二个分支，没有左右Z分；二叉树也有两个分支，但有左右Z分，且左右不能交换。7.证明：在哈夫曼树中有n个叶结点，则树一共有2n・l结点。证明：在二叉树中n0=n2+l,B

5、Jn2=nO-1而nl=0,这里nO二n则总结点=nO+n2=n+n-l=2n-l10・在具有n（n>l）个结点的二叉树中，深度最小的那棵树的度是多少？它共有多少叶子和非叶子结点?深度最大的那棵树的度是多少？它共有多少叶子和非叶子结点？答：（1）深度最小的二叉棵树的度是k=[log2nj+l,k・l层以上共有结点：2k-1-l=2flog2nl-l第K层结点为：m2卩咗川+1都是叶子结点。第k

6、・l层非叶子结点为:（n・2血叫1+1）/2第k・l层叶子结点为2l，og2n-1-（n-2I，og2n]+l+l）/2;总叶子结点为：n-2Uo82nl+l+2[,Qg2n-1-（n-2l，og2nJ+l+l）/2（2）深度最大的那棵树的度是n,1个叶子和n・l个非叶子结点。11・设度为h的二叉树上只有度为0和度为2的结点，问该二叉树的结点数可能达到的最大值和最小值。结点数最大值：2h-l最小值:2h-l1•对于如图所示的有向图，试给出（1）每个顶点的入度和出度；（2）邻接矩阵；（3）邻接表；（4）逆邻接表；（5）强连通分量。结点入度出度1212223134305236122.

7、3450101000110000100014.3.(5)强连通分量。三个强连通分量二.算法设计题2.已知一顺序表A,其元素值非递减有序排列，编写一个函数删除顺序表中多余的值相同的元素。(第二章)I、直接使用数组的写法：tfdefineMAXSIZE30#include"stdio.h"intdele(inta[],intelenum){inti,j;i=j=0;while(j

8、nO;for(i=0;i