2.3.练习1.内存中一片连续空间(不妨假设地址从1到m),提供给两个 栈 S1 和 S2 使用，怎样分配这部分存储空间，使得对任一个 栈，仅当这部分空间全满时才发生上溢。叙述前序和中序遍历二叉树的步骤；一棵前序序列为 1,2,3,4的二叉树,其中序序列可能是 4,1,2,3 吗?设一棵二叉树的前序 序列为 1,2,3,4,5,6,7,8,9,其中序序列为 2,3,1,5,4,7,8,6,9,试画出该二叉树。设有一个关键码的输入序列 55, 31, 11, 37, 46, 73, 63 ,(1) 从空树开始构造平衡二叉搜索树 , 画出每加入一个新结点时二叉树的形态。若发生不平衡, 指明需做的平衡旋转的类型 及平衡旋转的结果。(2) 计算该平衡二叉搜索树在等概率下的查找成功的平均查 找长度。4.设散列表为HTO 12,即表的大小为m=13。现采用双散列法解决冲突。散列函数和再散列函数分别为：H0(key)=key%13;注：是求余数运算(=mod)H=(H. +REV(key+1)%11+1)%13;i=1,2,3,m-1i i-1其中，函数REV (x)表示颠倒10进制数x的各位，如REV(37)=73,REV(7)=7 等。若插 入的关键码序列为2,8,31,20,19,18,53,27。(1)试画出插入这 8个关键码后的散列表 (2)计算搜索成功的平均搜索长度 ASL。5. 下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市6. 给出一组关键字： 29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：（1）归并排序 每归并一次书写一个次序。（2）快速排序 每划分一次书写一个次序。3）堆排序 先建成一个最大堆，然后每从堆顶取下一个元素 后，将堆调整一次。7.假设用于通讯的电文由5个字母组成，A B C D E F，字母在电文中的出现频率分别为 0.09， 0.12， 0.07， 0.22， 0.23，0.27，画出哈夫曼树，并写出各个字符的哈夫曼编码。（左子树根节点值不大于右子树根节点值）8. 已知序列（50， 72， 43， 85， 75， 20， 35， 45， 65， 30），请 以顺序插入方式构造二叉排序树，并画出删除结点 72之后的 二叉排序树。9.已知带权无向图G的邻接矩阵是A。V1 V2 V3 V4 V5 V6(1) 画出图 G；(2) 分别画出一颗从 V1 出发的深度优先生成树和广度优先生 成树；(3) 画出一棵最小生成树。10.假定一组记录的排序码为(46，79，56，38，40，84，50，42)利用堆排序方法画出初始大顶堆(以树状表示)。11. 图的深度优先搜索类似于BFS不同之处在于使用栈代替BFS中的队列，进出队列的操作改为入出栈的操作。即当一个顶 点的一个邻接点被搜索后，下一个搜索的出发点应该是最近 入栈(栈顶)的顶点。用 深度优先搜索方法搜索下图,设初始出 发点为 1。(1) 画出搜索过程中栈的变化。(2) 写出顶点的访问次序(当从某顶点出发搜索他的邻接点时，im12. 按 照 次 序 输 入 关 键 字 的 值 建 立 2-3 树 (3 阶 B-树):(68,54,82,35,75,90，103，22)。(1)请画出所建的 2-3 树。(2)如果此后依次删除 22,75，画出每一步执行后的 2-3 树的状态。13已知如下树林，画出对应的二叉树。14. 已知二叉树，画出中序的线索。15.以下图为例，按Dijkstra算法计算得到的从顶点A到其他各个顶点的最短路径和最短路径长度。