郑州手机网站制作公司哪家好,德国域名申请网站,太原网站建设方案开发,建立什么填词语欢迎评论#xff08;指正或是询问都可#xff09;#xff0c;谢谢大家 一、判断题 思路很正常的题目。 1-4反例#xff1a;4个顶点只用3条边就可以做到全连通。所以边数可能等于顶点个数减一。错误。 二、选择题 2-8需要细心的做一下双旋操作#xff0c; 2-12 C 设数字 {… 欢迎评论指正或是询问都可谢谢大家 一、判断题 思路很正常的题目。 1-4反例4个顶点只用3条边就可以做到全连通。所以边数可能等于顶点个数减一。错误。 二、选择题 2-8需要细心的做一下双旋操作 2-12 C 设数字 {4371, 1323, 6173, 4199, 4344, 9679, 1989} 在大小为10的散列表中根据散列函数 h(X)X%10得到的下标对应为 {1, 3, 4, 9, 5, 0, 2}。那么继续用散列函数 “h(X)X%表长”实施再散列并用线性探测法解决冲突后它们的下标变为(4分) 11, 3, 13, 19, 4, 0, 91, 3, 4, 9, 5, 0, 21, 12, 9, 13, 20, 19, 111, 12, 17, 0, 13, 8, 14 再散列即是double扩大原表长使得loading factorα下降一半的过程。因为装载因子和期望查找长度有反相关的关系参考数据结构第三版 散列性能分析章节的一张曲线图所以降低α这样可以增加散列查找的效率。 本题中再散列后的表长应该是20但是要取大于20的第一个素数所以表长取23较适宜。所以选C而不是A。 2-14 此题有争议 C、D 当初是看错选对的看书上的意思应该选C 求大佬指正。 2-20 三角不等式在图论中同样也适用两边之和必定大于第三边。 2-21 图退化成线性表后堆栈和队列的拓扑排序就相同。 三、程序填空题 counter //TopNum starts counting from 1 --Indegree[W] 这个堆的应用很聪明就是找出K个尽可能小的数字再在其中选一个最大的数即为第K小的数。 建立了K个元素的大顶堆利用不等式的传递性质。如果一个数大于堆顶那其必定大于堆顶以下的元素那这个数至少是第K1小的数因为比K1个数还大所以在循环中直接跳过该数如果一个数小于堆顶则完成替换堆顶调整最大堆的操作使得最大堆里永远是较小的一堆数字。 四、编程题 7-1 根据后序和中序遍历输出先序遍历 (8 point(s)) 本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果输出该树的先序遍历结果。 输入格式: 第一行给出正整数N(≤30)是树中结点的个数。随后两行每行给出N个整数分别对应后序遍历和中序遍历结果数字间以空格分隔。题目保证输入正确对应一棵二叉树。 输出格式: 在一行中输出Preorder:以及该树的先序遍历结果。数字间有1个空格行末不得有多余空格。 输入样例: 7 2 3 1 5 7 6 4 1 2 3 4 5 6 7 输出样例: Preorder: 4 1 3 2 6 5 7 陈越老师一道讲过的课后习题 思路 申请三个全局数组。PostOrder、InOrder、PreOrder。 依据PostOrder找到根节点后记录查找InOrder中的根节点把InOrder原序列划分成左右两个子序列递归解决问题。 参考代码 1 #include cstdio2 #define MAXN 503 4 int pre[MAXN], in[MAXN], post[MAXN];5 6 7 8 void InputPostAndIn(int N);9 void solve(int preL, int inL, int postL, int n);
10 void OutputPost(int N);
11
12 int main()
13 {
14 int N; scanf(%d, N);
15 InputPostAndIn(N);
16 solve(0, 0, 0, N);
17 OutputPost(N);
18 }
19
20 void InputPostAndIn(int N)
21 {
22
23 for (int i0; iN; i) {
24 scanf(%d, post[i]);
25 }
26 for (int i0; iN; i) {
27 scanf(%d, in[i]);
28 }
29
30 }
31
32 void solve(int preL, int inL, int postL, int Num)
33 {
34 if (Num 0) {
35 return;
36 }
37
38 int root, i, LTreeNodeNum, RTreeNodeNum;
39 root post[postL Num - 1];
40 pre[preL] root;
41
42 for (iinL; in[i]!root; i) {}
43
44 LTreeNodeNum i - inL; RTreeNodeNum Num - LTreeNodeNum - 1;
45
46 solve(preL1, inL, postL, LTreeNodeNum);
47 solve(preL1LTreeNodeNum, inL1LTreeNodeNum, postL LTreeNodeNum, RTreeNodeNum);
48 }
49
50 void OutputPost(int N)
51 {
52 printf(Preorder: );
53 printf(%d, pre[0]);
54 for (int i1; iN; i) {
55 printf( %d, pre[i] );
56 }
57 printf(\n);
58 } View Code 转载于:https://www.cnblogs.com/acoccus/p/10957065.html
