《数据结构》由会员分享，可在线阅读，更多相关《数据结构（16页珍藏版）》请在金锄头文库上搜索。
1、1. 将森林转换为二叉树。用左子女-右兄弟表示实现的树定义：typedef struct node TreeData data; struct node * firstChild, * nextSibling; TreeNode;2. 图的邻接矩阵、邻接表的存储表示。图的邻接矩阵存储：两点之间有边矩阵对应的位置处填1，两点之间无边对应位置处填0EdgeData EdgeNumVerticesNumVertices; 图的邻接表存储： 2. 计算AOE网络的关键路径。完成整个工程所需的时间取决于从源点到汇点的最长路径长度, 即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路
2、径关键活动：最早开始时间和最晚开始时间相等4. 画出下图的结构，并分别给出以A顶点开始的深度优先遍历和广度优先遍历。ABDCFE深度优先搜索：ABDCEF广度优先搜索：ABCDEF5. (1) 哈希函数常用的构造方法有哪些?处理冲突的方法有哪些？(2) 用除留余数法构建哈希表，并以线性探测再散列处理冲突。1、常用的构造方法：直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法处理冲突的方法：开放定址法、再哈希法、链地址法2、除留余数法：H(key) = key % p -m为表长，p为不大于m的素数P为素数？如key（关键字）：12 39 18 24 33 21 若p = 9 则哈
3、希函数值为：3 3 0 6 6 3可见，当p的因子中含有素数3，则所有含因子3的关键字都对应到“3的倍数”的地址上，从而增加了冲突的可能!/*表长为6，关键字个数6，p=m且p为素数，故p取5,但是这样最后一个数21将永远不会放到下标为5的地方！那么这个p的取法不是有错吗？还是说表长必须比给的关键字个数大？*/如key（关键字）：12 39 18 24 33 21 若p = 7 则哈希函数值为: 5 4 4 3 5 0先行探测在散列处理冲突：Key = 18：18 % 7 = 4(冲突)(4+1)%7=5(冲突)(5+1)%7=6key = 33: 33%7=5（冲突）(5+1)%7=6（冲突
4、）(6+1)%7=0Key = 21:21%7 = 0(冲突)(0+1)%7 = 1所以最后得：5 4 6 3 0 101234563321243912186. 证明二叉树性质：n0=n2+1 ( n0度为0的结点；n2:度为2的结点 )n1为度为1的节点，e表示二叉树的边数；这里用到的一个等式是二叉树边的两种表达:e=n0+n1+n2-1 /每一个节点对应一条边，根节点除外所以减一e=2*n2+n1 /2倍的度为2的节点数目加上度为1的节点数目，就是边的数目得：n0 = n2 + n17. 求最小生成树 1、Prim（普里姆）算法从连通图中的某一顶点 u0 出发, 选择与它关联的具有最小权值
5、的边，将其顶点加入到生成树顶点集合中2、Kruskal（克鲁斯卡尔）算法对每一条边按照权值从小到大排序，每一次选择最小的权值的边，注意避免选择出现环的边！8.以权重集合 4, 5, 6, 7, 8 构建哈夫曼树（霍夫曼树）。带权路径长度达到最小的二叉树即为哈夫曼树。 9. 给出用下列关键字构建大顶堆的全过程，关键字集合为 70 40 55 81 74 18 46 70 01234567704055817418467010. 给出上述集合数据的快速排序的过程选定初始关键字temp，首先从右向左遍历，当遇到比temp小的时候，就让ai = aj, i+;然后重左向右遍历，当遇到比temp大的时候，
6、就让aj = ai, j-;然后循环做上述两个过程，直到i=j时，就让ai = temp;这时枢轴就是ai;然后递归调用从（l, i-1）和(i+1,r);11. 请按照给出的数字顺序构造二叉排序树。如：50 30 80 20 40 90 10 25 35 85 23 8812. 计算从顶点b到其它顶点的最短路径。答题不能这样写，这样写最多2分，要写出步骤！这只是草稿，方便看！Dijkstra 逐步求解的过程:13. 二叉树计数。1、由二叉树的前序序列和中序序列可唯一地确定一棵二叉树前序序列 ABHFDECKG /确定根节点中序序列 HBDFAEKCG /在前序序列确定根节点的基础上，确定左右
7、孩子节点 2、计算具有 n 个结点的不同二叉树的棵数14. 给出求顺序表A和B并集和交集的程序实现，要求并集存储在表A当中。运行结果：La :0 1 2 3 4 5 6 7 8 9Lb :0 2 4 6 8 10 12 14 16 18BingJi :0 1 2 3 4 5 6 7 8 9 10 12 14 16 18JiaoJi :0 2 4 6 8请按任意键继续. . .代码：#include #define NewSeqList (SeqList*)malloc(sizeof(SeqList)#define NewListData (int*)malloc(40 * sizeof(int
8、)using namespace std;typedef struct int *data, length;SeqList;void SetL(SeqList *&L) cout L-length;for (int i = 0; i length; +i) cin L-datai;void Show(SeqList *&L) for (int i = 0; i length; +i) cout datai ; cout endl;bool InL(SeqList *&L, int &key) for (int i = 0; i length; +i) if (key = L-datai) re
9、turn true;return false;void Insert(SeqList *&L, int key) L-dataL-length+ = key; void Delete(SeqList *&L, int &pos) /pos代表要删除的元素的下标for (int i = pos; i length - 1; +i) L-datai = L-datai + 1;-L-length;void Union(SeqList *&La, SeqList *&Lb) for (int i = 0; i length; +i) if (!InL(La, Lb-datai) Insert(La,
10、 Lb-datai);/如果Lb中元素不在La中就把该元素插入到La中void Intersect(SeqList *&La, SeqList *&Lb) for (int i = 0; i length; +i) if (!InL(Lb, La-datai) Delete(La, i); -i; /如果La中元素不在Lb中就把La中该元素删除int main()SeqList *La = NewSeqList, *Lb = NewSeqList;/NewSeqList 用宏定义创建结构体La-data = NewListData;/NewListData 用宏定义创建数组Lb-data =
11、NewListData;La-length = Lb-length = 0;SetL(La);/向顺序表La输入数据SetL(Lb);/向顺序表Lb输入数据cout 输出集合La：; Show(La);cout 输出集合Lb：; Show(Lb);Union(La, Lb);/并集cout 并集结果：; Show(La);Intersect(La, Lb);/交集cout head的代码即可）运行结果：please input VertexNum and EdgeNum :4 5please input VertexNode :A B C Dplease input Edge as A B 1
12、0 :A C 2A B 1A D 3B C 1B D 5A Chu Du is : 3B Chu Du is : 3C Chu Du is : 2D Chu Du is : 2A Ru Du is : 3B Ru Du is : 3C Ru Du is : 2D Ru Du is : 2请按任意键继续. . .代码：#include #include using namespace std;const int VertexNum = 10;typedef struct nodeint dex, cost;struct node *link;EdgeNode;typedef char VertexData;typedef struct VertexData data;EdgeNode *first_link;VertexNode;typedef struct VertexNode VexListVertex
