计算机数据结构复习题

1、 习 题一、简答题1有数据WG=7，19，2，6，32，3，21，10，则所建Huffman树的树高是_(1)_，带权路径长度WPL为_(2)_。1解：哈夫曼树的高度是6。 带权路径长度为2612.分别给出直接插入排序、冒泡排序、直接选择排序、归并排序、快速排序和堆排序在下列条件下的执行情况。对一个已排好序的数组进行排序；对一个逆序的数组进行排序。 2 解答：直接插入冒泡排序直接选择归并排序快速排序堆排序正序最好最好不敏感不敏感最坏不敏感逆序最坏最坏不敏感不敏感最坏不敏感判断题： 1.一个没有回路的连通图是树。 （错） 2.中序遍历一棵二叉查找树的结点可以得到一个排好序的结点序列。（对）3 （

2、1）如果G1是一个具有n个顶点的连通无向图，那么G1最多有多少条边？G1最少有多少条边？（2）如果G2是一个具有n个顶点的强连通有向图，那么G2最多有多少条边？G2最少有多少条边？（3）如果G3是一个具有n个顶点的弱连通有向图，那么G3最多有多少条边？G3最少有多少条边？ 3答：（1）G1最多n(n-1)/2条边，最少n-1条边 (2) G2最多n(n-1)条边，最少n条边 (3) G3最多n(n-1)条边，最少n-1条边 (注：弱连通有向图指把有向图看作无向图时，仍是连通的) 4试用下列三种表示法画出网G 的存储结构，并评述这三种表示法的优、缺点：（1）邻接矩阵表示法; （2）邻接表表示法;

3、 4答：邻接矩阵表示法，有n个顶点的图占用n2个元素的存储单元，与边的个数无关，当边数较少时，存储效率较低。这种结构下，对查找结点的度、第一邻接点和下一邻接点、两结点间是否有边的操作有利，对插入和删除顶点的操作不利。邻接表表示法是顶点的向量结构与顶点的邻接点的链式存储结构相结合的结构，顶点的向量结构含有n（n0）个顶点和指向各顶点第一邻接点的指针，其顶点的邻接点的链式存储结构是根据顶点的邻接点的实际设计的。这种结构适合查找顶点及邻接点的信息，查顶点的度，增加或删除顶点和边（弧）也很方便，但因指针多占用了存储空间，另外，某两顶点间是否有边（弧）也不如邻接矩阵那么清楚。对有向图的邻接表，查顶点出度

4、容易，而查顶点入度却困难，要遍历整个邻接表。要想查入度象查出度那样容易，就要建立逆邻接表。无向图邻接表中边结点是边数的二倍也增加了存储量。5在执行某种排序算法的过程中出现了排序码朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗？为什么？ 5答： 这种说法不对。因为排序的不稳定性是指两个关键字值相同的元素的相对次序在排序前、后发生了变化，而题中叙述和排序中稳定性的定义无关，所以此说法不对。对4，3，2，1起泡排序就可否定本题结论。 6请回答下列关于堆(Heap)的一些问题： (1) 堆的存储表示是顺序的，还是链接的? (2) 设有一个小根堆，即堆中任意结点的关键码均大于

5、它的左子女和右子女的关键码。其具有最大值的元素可能在什么地方?6. 答：（1）堆的存储是顺序的（2）最大值元素一定是叶子结点，在最下两层上。7二叉树由_(1)_，_(2)_，_(3)_三个基本单元组成。7.(1)根结点(2)左子树(3)右子树 8. 有以下算法，其时间复杂度为（C ）。void fun(int n) while(i*i*ilchild),f(b-lchild),c) 其他情况其中，f()为递归函数，g为非递归函数，c为常量。（2）求二叉树深（高）度解析：递归模型如下：f(b)=0 若b=NULLf(b)= MAXf(b-lchild),f(b-rchild)+1 其他情况相应算

6、法如下：int BiTreeDepth(BiTree bt) int hl, hr; if (bt=NULL) return(0); elsehl=BiTreeDepth(bt-LChild);/*求左子树的深度 */ hr=BiTreeDepth(bt-RChild);/*求右子树的深度 */ return(hlhr)?(hl+1):(hr+1);) （3）统计一棵给定二叉树中的所有叶子结点数解析：递归模型如下：f(b)=0 若b=NULLf(b)=1 若b-lchild=NULL 且b-rchild=NULLf(b)= f(b-lchild)+ f(b-rchild) 其他情况相应算法如下

7、：int LeafNodes (BiTree bt) int num1,mun2; if (bt=NULL) return 0; else if (bt-lchild=NULL & bt-rchild=NULL)return 1; else num1=LeafNodes(bt-lchild); num2=LeafNodes(bt-rchild); return (num1+num2);1、已知二叉树采用二叉链表方式存放，要求返回二叉树T的后序序列中的第一个结点的指针，是否可不用递归且不用栈来完成？请简述原因。答：可以。原因：后序遍历的顺序是“左子树右子树根结点”。因此，二叉树最左下的叶子结点是

8、遍历的第一个结点。下面的语句段说明了这一过程（设p是二叉树根结点的指针）。if (p!=null)while (p-lchild!=null | p-rchild!=null)while(p-lchild!=null) p=p-lchild;if(p-rchild!=null) p=p-rchild; return(p); /返回后序序列第一个结点的指针（5）已知二叉树的前序序列、中序序列构造二叉树的算法。BiTree CreateBT1(char *pre，char *in, int n)/* pre存放前序序列，in存放中序序列，n为in中字符个数，本算法执行后返回构造的二叉树的根结点指针

9、*/ BiTree bt; char *p;int k; if (ndata=*pre;for(p=in;plchild= CreateBT1(pre+1,in,k); bt-rchild= CreateBT1(pre+k+1,p+1,n-k-1); return bt; BiTree CreateBT1(char *pre，char *in, int n)for(p=in;plchild= CreateBT1(pre+1,in,k); bt-rchild= CreateBT1(pre+k+1,p+1,n-k-1); return bt; 先序序列：ABDGCEF中序序列：DGBAECF (k

10、=3)BiTree CreateBT1(char *pre，char *in, int n)for(p=in;plchild= CreateBT1(pre+1,in,k); bt-rchild= CreateBT1(pre+k+1,p+1,n-k-1); return bt; 先序序列：ABDGCEF中序序列：DGBAECF (k=2) 2在有向图G中，如果r到G中的每个结点都有路径可达，则称结点r为G的根结点。编写一个算法完成下列功能：（1）建立有向图G的邻接表存储结构；（2）判断有向图G是否有根，若有，则打印出所有根结点的值。2. 题目分析本题应使用深度优先遍历，从主调函数进入dfs(v)

11、时 ，开始记数，若退出dfs()前，已访问完有向图的全部顶点（设为n个），则有向图有根，v为根结点。将n个顶点从1到n编号，各调用一次dfs()过程，就可以求出全部的根结点。题中有向图的邻接表存储结构、记顶点个数的变量、以及访问标记数组等均设计为全局变量。 void JudgeRoot()/判断有向图是否有根，有根则输出之。 static int i ;for (i=1;iadjvex=0) dfs (p-adjvex);p=p-next; /while visitedv=0; num-; /恢复顶点v/dfsint num=0， visited=0 /num记访问顶点个数,访问数组visit

12、ed初始化。 const n=用户定义的顶点数; AdjList g ; /用邻接表作存储结构的有向图g。 void dfs(v) visited v=1; num+; /访问的顶点数1 if (num=n) printf(“%d是有向图的根。n”,v); num=0;/if p=gv.firstarc; while (p) if (visiedp-adjvex=0) dfs (p-adjvex);p=p-next; /while visitedv=0; num-; /恢复顶点v/dfs 3 编写算法求二叉树中从根节点到各叶子节点路径中最长的路径，并输出此路径上各个结点的值。3、 解题思路 本

13、题采用非递归后根遍历二叉树的方法。引入一个辅助数据结构栈stack。当后根遍历访问到由p所指的叶结点时，stack中的所有结点均为p所指结点的祖先，由这些祖先便构成了一条从根结点到此叶结点的路径。另外，设一LongestPath数组来保存二叉树中最长的路径，m为最长的路径长度。算法的C+实现： void LongPath (BintreeNode *root , int maxsize;) BintreeNode *stackmaxsize,*s; char LongestPathmaxsize; /保存最长路径的数组int i, m, top; /top为栈顶指针，m为最长路径长度int t

14、agmaxsize; /tag为标志数组，若结点i的左右孩子均被访问过，则tagi=1 m=0; top=0; s=root; do while (s! =NULL) /祖先结点入栈 top+; stacktop = s; tagtop = 0; /右孩子还未访问过s = sleft; if (top0) /保存最长路径 if (tagtop = 1) /左右孩子均已访问过，则访问该结点 if (stacktop left = NULL) & (stacktop right = NULL) & (topm) for (i =1; idata; m = top; top; else s = stacktop; if (top0) s=sright; tagtop =1; while (s! =NULL) | (top! =0); for (i=1; i=m; i+) coutlongest