江西理工大学数据结构考试大题,保过.docx

1. 掌握链表（包括单向、双向链表的插入和删除算法）2.给定二叉树的两种遍历序列，分别是：前序遍历序列：D，A，C，E，B，H，F，G，I； 中序遍历序列：D，C，B，E，H，A，G，I，F， D A C FE GB H I3.试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。（以及算法的实现）答：DLR：A B D F J G K C E H I L MLDR: B F J D G K A C H E L I MLRD：J F K G D B H L M I E C A4把如图所示的树转化成二叉树。答：注意全部兄弟之间都要连线（包括度为2的兄弟）,并注意原有连线结点一律归入左子树，新添连线结点一律归入右子树。 A B E C K F H D L G I M J5.画出和下列二叉树相应的森林。答：注意根右边的子树肯定是森林，而孩子结点的右子树均为兄弟。6.编写递归算法，计算二叉树中叶子结点的数目。int LeafCount_BiTree(Bitree T)/求二叉树中叶子结点的数目 if(!T) return 0; /空树没有叶子 else if(!T-lchild&!T-rchild) return 1; /叶子结点 else return Leaf_Count(T-lchild)+Leaf_Count(T-rchild);/左子树的叶子数加 上右子树的叶子数 /LeafCount_BiTree 7.编写算法判别给定二叉树是否为完全二叉树。答：int IsFull_Bitree(Bitree T)/判断二叉树是否完全二叉树,是则返回1,否则返回0 InitQueue(Q); flag=0; EnQueue(Q,T); /建立工作队列 while(!QueueEmpty(Q) DeQueue(Q,p); if(!p) flag=1; else if(flag) return 0; else EnQueue(Q,p-lchild); EnQueue(Q,p-rchild); /不管孩子是否为空,都入队列 /while return 1; /IsFull_Bitree 8 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.17，0.09，0.02，0.06，0.32，0.13，0.11，0.10。试为这8个字母设计哈夫曼编码。使用07的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。解：方案1；哈夫曼编码9.已知如图所示的有向图，请给出该图的:顶点123456入度出度（1） 每个顶点的入/出度；（2） 邻接矩阵；（3） 邻接表；（4） 逆邻接表。 答案：10.请对下图的无向带权图：（两种生成算法）（1） 写出它的邻接矩阵，并按普里姆算法求其最小生成树；（2） 写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。 解：设起点为a。可以直接由原始图画出最小生成树，而且最小生成树只有一种（类）!邻接矩阵为： 最小生成树 PRIM算法（横向变化）： VbcdefghUV-UVexlowcosta4a3aaaaaab,c,d,e,f,g,hVexlowcosta40c5aaac5a,cb, d,e,f,g,hVexlowcost00c5b9aac5a,c,bd,e,f,g,hVexlowcost000d7d6d5d4a,c,b,d e,f,g,hVexlowcost000d7d6d50a,c,b,d ,h e,f,g Vexlowcost000d7g200a,c,b,d ,h ,g f,e Vexlowcost000f3000a,c,b,d ,h ,g, f e Vexlowcost0000000a,c,b,d ,h ,g, f, e 邻接表为：ab4c3ba4c5d5e9ca3b5d5h5db5c5e7f6g5h4eb9d7f3fd6e3g2gd5f2h6hc5d4g6克鲁斯卡尔算法步骤(按边归并,堆排序)：先罗列：f-2-g a3-c f3e a4-b d4h (a,b,c) (e,f,g) (d,h) 取b5d, g5-d 就把三个连通分量连接起来了。11.已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。（包括深度优先遍历和广度优先遍历算法）12.试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。解：最短路径为：（a,c,f,e,d,g,b）13、给定下列网G: (1) 试着找出网G的最小生成树，画出其逻辑结构图；(2) 用两种不同的表示法画出网G的存储结构图；A BC EF GD解：1. 最小生成树可直接画出，如右图所示。2. 可用邻接矩阵和邻接表来描述：邻接表为：ab12e4ba12c20e8f9cb20d15g12dc15g10ea4b8f6fb9e6gc12d1014.试在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v,w) ，即删除一条边的操作。（如果要删除所有从第i个顶点出发的边呢？ 提示： 将邻接矩阵的第i行全部置0 ）解：/本题中的图G均为有向无权图。 Status Delete_Arc(MGraph &G,char v,char w)/在邻接矩阵表示的图G上删除边(v,w) if(i=LocateVex(G,v)0) return ERROR; if(j=LocateVex(G,w)high) return 0; /查找不到时返回0 mid=(low+high)/2; if(ST.elemmid.key= =key) return mid; else if(ST.elemmid.keykey) return Search_Bin_Recursive(ST, key, low, mid-1); else return Search_Bin_Recursive(ST, key, mid+1, high); /Search_Bin_Recursive 21 已知某哈希表的装载因子小于1，哈希函数H(key)为关键字（标识符）的第一个字母在字母表中的序号，处理冲突的方法为线性探测开放定址法。试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。解：注意此题给出的条件：装载因子a1, 则哈希表未填满。由此可写出下列形式简明的算法：void PrintWord(Hash Table ht)for(i=1; i=26; i+)j=i;While(ht.elemj.key)if(Hash(ht.elemj.key=i)printf(ht.elemj.key);j=(j+1)%m;/PrintWord22 各种排序算法的时间复杂度、过程和算法名称数据对象稳定性时间复杂度空间复杂度描述平均最坏冒泡排序数组（无序区，有序区）。从无序区通过交换找出最大元素放到有序区前端。选择排序数组（有序区，无序区）。在无序区里找一个最小的元素跟在有序区的后面。对数组：比较得多，换得少。链表插入排序数组、链表（有序区，无序区）。把无