DS习题讲解.doc

1、11、利用原来的存储空间实现单链表的就地逆置。void resverse(LinkList /L 为单链表的头结点L-next=null; while (p) q=p; p=p-next; q-next=L-next;L-next=q; 2、编写计算数组元素累加和的递归函数templateT Rsum(T a , int n) / /计算 a0: n-1的和if (n 0)return Rsum(a, n-1) + an-1;return 0;3、编程实现在带头结点的 head 单链表的结点 a 之后插入新元素 x。class node public: elemtype data;node *

2、next;void lkinsert(node *head, elemtype x)node *s, *p;s= new node;s-data=x;p=head-next;while ( p!=NULL)if ( p=NULL )coutnext=p-next ;2p-next=s;4、在栈顶指针为 HS 的链栈中编写计算该链栈中结点个数的函数。int count(node *HS)node *p; int n=0; p=HS; while (p!=NULL) n+; p=p-next; return(n);5、给定二叉树的两种遍历序列，分别是：前序遍历序列：ABECDFGHIJ ； 中序遍

3、历序列：EBCDAFHIGJ，试画出二叉树。当前序序列为 ABECDFGHIJ，中序序列为 EBCDAFHIGJ 时，逐步形成二叉树的过程如下图所示： 6、编写递归算法，计算二叉树中叶子结点的数目。int NumOfLeaves(Node *t) const if (t = NULL) return 0; else if(t-left=Null7、写出求二叉树深度的算法。 int Depth(Node *t) const if (t = NULL) return 0; else int lt = Depth (t-left), rt = Depth (t-right);return 1 + (

4、 (lt rt) ? lt : rt);EBCD FHIGJA ABEFCD HIGJABEFCDGJHIABEFCDGJHI38、编写递归算法，求二叉树中以元素值为x的结点为根的子树的深度。int Get_Sub_Depth(BinaryTree T,int x)/求二叉树中以值为 x 的结点为根的子树深度 if(T-data=x) coutlchild) Get_Sub_Depth(T-lchild,x); if(T-rchild) Get_Sub_Depth(T-rchild,x); /在左右子树中继续寻找 /Get_Sub_Depth int Get_Depth(BinaryTree

5、T)/求子树深度的递归算法 if(!T) return 0; else m=Get_Depth(T-lchild); n=Get_Depth(T-rchild); return (mn?m:n)+1; /Get_Depth9、画出一次一个地将 10、12、1、14、6、5、8、15、3、9、7、4、11、13 和 2 插入一个初始为空的最小堆的结果。10、改写 Binary heap 的 insert 函数，在 0 号数组元素中存放插入项的副本。void insert( const Comparable / Percolate upint hole = +currentSize;for( ;

6、hole 1 j-)R j+1 = Rj; /元素后移Rleft =temp;12、对于给定的一组键值：83，40，63，13，84，35，96，57，39，79，61，15，分别画出应用直接插入排序、直接选择排序、快速排序、堆排序、归并排序对上述序列进行排序中各趟的结果。1直接插入排序序号 1 2 3 4 5 6 7 8 9 10 11 12关键字 83 40 63 13 84 35 96 57 39 79 61 15i = 2 40 83 63 13 84 35 96 57 39 79 61 15 i = 3 40 63 83 13 84 35 96 57 39 79 61 15i = 4

7、 13 40 63 83 84 35 96 57 39 79 61 15i = 5 13 40 63 83 84 35 96 57 39 79 61 15i = 6 13 35 40 63 83 84 96 57 39 79 61 155i = 7 13 35 40 63 83 84 96 57 39 79 61 15i = 8 13 35 40 57 63 83 84 96 39 79 61 15i = 9 13 35 39 40 57 63 83 84 96 79 61 15i = 10 13 35 39 40 57 63 79 83 84 96 61 15i = 11 13 35 39

8、40 57 61 63 79 83 84 96 15i = 12 13 15 35 39 40 57 61 63 79 83 84 96直接选择排序序号 1 2 3 4 5 6 7 8 9 10 11 12关键字 83 40 63 13 84 35 96 57 39 79 61 15i = 1 13 40 63 83 84 35 96 57 39 79 61 15i = 2 13 15 63 83 84 35 96 57 39 79 61 40i = 3 13 15 35 83 84 63 96 57 39 79 61 40i = 4 13 15 35 39 84 63 96 57 83 79

9、 61 40i = 5 13 15 35 39 40 63 96 57 83 79 61 84i = 6 13 15 35 39 40 57 96 63 83 79 61 84i = 7 13 15 35 39 40 57 61 63 83 79 96 84i = 8 13 15 35 39 40 57 61 63 83 79 96 84i = 9 13 15 35 39 40 57 61 63 79 83 96 84i = 10 13 15 35 39 40 57 61 63 79 83 96 84i = 11 13 15 35 39 40 57 61 63 79 83 84 96快速排序关

10、键字 83 40 63 13 84 35 96 57 39 79 61 15第一趟排序后 15 40 63 13 61 35 79 57 39 83 96 84第二趟排序后 13 15 63 40 61 35 79 57 39 83 84 96第三趟排序后 13 15 39 40 61 35 57 63 79 83 84 96趟排序后 13 15 35 39 61 40 57 63 79 83 84 96第五趟排序后 13 15 35 39 57 40 61 63 79 83 84 96第六趟排序后 13 15 35 39 40 57 61 63 79 83 84 96第七趟排序后 13 15

11、 35 39 40 57 61 63 79 83 84 96堆排序关键字： 83 40 63 13 84 35 96 57 39 79 61 15第一趟（建堆）：15 84 83 57 79 35 63 13 39 40 61 96过程如下：初始排列8363409635841357 39 79 61 15968384633579576初始堆交换 0# 与 11# 对象，输出 96第二趟：15 79 83 57 61 35 63 13 39 40 84 96重新形成堆交换 0# 与 10# 对象，输出 84第三趟：40 79 63 57 61 35 15 13 39 83 84 96重新形成堆交

12、换 0# 与 9# 对象，输出 84第四趟：39 61 63 57 40 35 15 13 79 83 84 96重新形成堆交换 0# 与 8# 对象，输出 79第五趟：13 61 39 57 40 35 15 63 79 83 84 96重新形成堆13 39 40 61 151583846335795713 39 40 618483796335615713 39 40 158363791535615713 39 407963611535405713 3963396115354057137交换 0# 与 7# 对象，输出 63第六趟：15 57 39 13 40 35 61 63 79 83

13、84 96重新形成堆交换 0# 与 6# 对象，输出 61第七趟：35 40 39 13 15 57 61 63 79 83 84 96重新形成堆交换 0# 与 5# 对象，输出 57第八趟：15 35 39 13 40 57 61 63 79 83 84 96重新形成堆交换 0# 与 4# 对象，输出 40第九趟：13 35 15 39 40 57 61 63 79 83 84 96重新形成堆交换 0# 与 3# 对象，输出 39第十趟：15 13 35 39 40 57 61 63 79 83 84 96重新形成堆交换 0# 与 2# 对象，输出 35第十一趟：13 15 35 39 40

14、 57 61 63 79 83 84 96重新形成堆613957153540135739403515134039351513391535133515138交换 0# 与 1# 对象，输出 15，堆排序完成。在数组中存放的为正序，而输出结果为倒序。归并排序关键字 83 40 63 13 84 35 96 57 39 79 61 15第一趟排序后 40 83 13 63 35 84 57 96 39 79 15 61第二趟排序后 13 40 63 83 35 57 84 96 15 39 61 79第三趟排序后 13 35 40 57 63 83 84 96 15 39 61 79第四趟排序后 1

15、3 15 35 39 40 57 61 63 79 83 84 9613、如果每个结点占用 2 个磁盘块因而需要 2 次磁盘访问才能实现读写，那么在一棵有 n个关键码的 2m 阶 B 树中，每次搜索需要的最大磁盘访问次数是多少？14、已知如图所示的有向图，请给出该图的:（1） 每个顶点的入/出度；（2） 邻接矩阵；（3） 邻接表；（4） 逆邻接表。15、设有一组关键字19，01 ，23，14，55，20，84，27 ，68，11，10，77 ，采用哈希函数：H(key)=key % 13 采用开放地址法的线性探测再散列方法解决冲突，试在 018 的散列地址空间中对该关键字序列构造哈希表并计算其

16、填充因子 。依题意，m=19 ，线性探测再散列的下一地址计算公式为：d1=H(key)，dj+1=(dj+1) % m ； j=1，2，；其计算函数如下：顶点 1 2 3 4 5 6入度出度15139H(19)=19 % 13=6 H(01)=01 % 13=1 H(23)=23 % 13=10H(14)=14 % 13=1(冲突)H(14)=(1+1) % 19 =2H(55)=55 % 13=3 H(20)=20 % 13=7H(84)=84 % 13=6 (冲突)H(84)=(6+1) % 19=7 (仍冲突)H(84)=(7+1) % 19=8H(27)=27 % 13=1 (冲突)H

17、(27)=(1+1) % 19=2 (冲突)H(27)=(2+1) % 19=3 (仍冲突)H(27)=(3+1) % 19=4H(68)=68 % 13=3 (冲突) H(68)=(3+1) % 19=4 (仍冲突)H(68)=(4+1)% 19=5H(11)= 11 % 13=11 H(10 )=10 % 13=10 (冲突)H(10)=(10+ 1) % 19=11 (仍冲突 )H(10 )=(11+1) % 19=12 H(77)=77 % 13=12 (冲突)H(77)=(12+1) % 19=13因此：各关键字的记录对应的地址分配如下：addr(01)=1 addr(14)=2 addr(55)=3 addr(27)=4 addr(68)=5 addr(19)=6 addr(20)=7 addr(84)=8 addr(23)=10 addr(11)=11 addr(10)=12 addr(77)=13其他地址为空。装填因子 12/190.63。