《数据结构综合练习》由会员分享，可在线阅读，更多相关《数据结构综合练习（7页珍藏版）》请在金锄头文库上搜索。
1、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、衡旋转的类型 及平衡旋转的结果。(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. 下
3、图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市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，画出哈夫曼树，并写出各个字符的哈夫曼编码。（左子树根节点值不大于
4、右子树根节点值）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中的队列，进出队列的操作改为入出栈的操作
5、。即当一个顶 点的一个邻接点被搜索后，下一个搜索的出发点应该是最近 入栈(栈顶)的顶点。用 深度优先搜索方法搜索下图,设初始出 发点为 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到其他各个顶点的最短路径和最短路径长度。
