oi塔的函数定义如下:Hanoi ( int n,char x,char y ,char z )Р { if ( n= =1) move ( x ,1,z)Р Else{ hanoi( n-1, x,z,y);Р Move(x,n,z);Р Hanoi(n-1,y,x,z);Р }Р }Р 写出执行hanoi(3,a,b,c)时递归函数的实在参变量变化,以及move的搬运过程。Р 3.已知关键字序列为:(75,33,52,41,12,88,66,27),哈希表长为10,哈希函数为:H(k)=kMOD7,解决冲突用线性探测再散列法,要求构造哈希表,求出等概率下查找成功查找长度。Р 4.已知一棵二叉树,中序序列DBCAFGE,后序序列DCBGFEA,构造该二叉树。Р 5.给定权值{8,12,4,5,26,16,9},构造一个哈夫曼树,并计算其带权路径长度。Р 四、编写程序(15分)Р 建立线形表,(a1,a2,a3…。,an)的单链表存储,并实现其就地逆置为(an, ,an-1…a2.,a1)。Р 五、编写程序(10分)Р 在中序线索树中,要找出X结点的前驱结点,请写出相关函数定义。Р Ltag Lc Data Rtag RcР 六、编写算法(20分)Р 已知有N个结点的无向图,采用邻接表结构存储,要求对每个连通子图中一个生成树中的各条边逐层输出,边的输出格式为(ki,kj)。Р 七、编写算法(25分)Р 1.写出建立二叉树,二叉链表存储结构的算法。(10分)Р 2.已知二叉树采用二叉链表方式存放,要求对二叉树从1开始进行连续编号,要求每个结点的编号大于其左右孩子的编号,同一结点的左右孩子中,左孩子编号小于右孩子编号。给出在二叉树中结点的数据域部分填写,实现如上要求编号的非递归算法。(10分)Р 3.已知二叉树采用二叉链表方式存放,给出判定它是否为一棵二叉排序树的算法。(5分)
全文预览
