DS习题讲解.doc

1、利用原来的存储空间实现单链表的就地逆置。void resverse(LinkList &L) p=L-next; /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 *next;void lkinsert(node *head, elemtype x)node *s, *p;s= new node;s-data=x;p=head-next;while ( p!=NULL)&(p-data!=a ) p=p-next;if ( p=NULL )coutnext=p-next ; p-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； 中序遍历序列：EBCDAFHIGJ，试画出二叉树。当前序序列为ABECDFGHIJ，中序序列为EBCDAFHIGJ时，逐步形成二叉树的过程如下图所示： AAAAFBBFFBGECGECHIGJCDEFHIGJHDJHIJDIEBCD6、编写递归算法，计算二叉树中叶子结点的数目。int NumOfLeaves(Node *t) const if (t = NULL) return 0; else if(t-left=Null& t-right=Null) return 1；else return NumOfLeaves(t-left) + NumOfLeaves ( t-right);7、写出求二叉树深度的算法。 int Depth(Node *t) const if (t = NULL) return 0; else int lt = Depth (t-left), rt = Depth (t-right); return 1 + ( (lt rt) ? lt : rt); 8、编写递归算法，求二叉树中以元素值为x的结点为根的子树的深度。int Get_Sub_Depth(BinaryTree T,int x)/求二叉树中以值为x的结点为根的子树深度 if(T-data=x) coutGet_Depth(T)lchild) Get_Sub_Depth(T-lchild,x); if(T-rchild) Get_Sub_Depth(T-rchild,x); /在左右子树中继续寻找 /Get_Sub_Depth int Get_Depth(BinaryTree 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 & x )if( currentSize = array.size( ) - 1 )array.resize( array.size( ) * 2 );/ Percolate upint hole = +currentSize;for( ; hole 1 & x array hole / 2 ; hole /= 2 )array hole = array hole / 2 ;array0 = array hole = x;11、编程实现折半插入排序void insertsort( int R , int n)/ 按照递增顺序对R0Rn进行折半插入排序 int i , j, left, right,mid;for ( i=2 ; in; i+) R0=Ri;/设定R0为监视哨left=1; right=n;while ( left = right ) mid=(left+right)/2;if( R0=left ; j-)R j+1 = Rj; /元素后移Rleft =temp;12、对于给定的一组键值：83，40，63，13，84，35，96，57，39，79，61，15，分别画出应用直接插入排序、直接选择排序、快速排序、堆排序、归并排序对上述序列进行排序中各趟的结果。1直接插入排序序号123456789101112 关键字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 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 15i = 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 40 57 61 63 79 83 84 96 15i = 12 13 15 35 39 40 57 61 63 79 83 84 96直接选择排序序号123456789101112 关键字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 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快速排序 关键字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 35 39 40 57 61 63 79 83 84 96堆排序关键字：834063138435965739796115第一趟（建堆）：15 84 83 57 79 35 63 13 39 40 61 96过程如下：834063138496351561577939初始排列968483577963351561134039初始堆交换0# 与11# 对象，输出96第二趟：15 79 83 57 61 35 63 13 39 40 84 961584835779633561134039重新形成堆8479835761633515134039交换0# 与10# 对象，输出84第三趟：40 79 63 57 61 35 15 13 39 83 84 96重新形成堆83796357611535134039交换0# 与9# 对象，输出84第四趟：39 61 63 57 40 35 15 13 79 83 84 96重新形成堆796163574015351339交换0# 与8# 对象，输出79第五趟：13 61 39 57 40 35 15 63 79 83 84 96重新形成堆6361395740153513交换0# 与7# 对象，输出63第六趟：15 57 39 13 40 35 61 63 79 83 84 96重新形成堆61573913401535交换0# 与6# 对象，输出61第七趟：35 40 39 13 15 57 61 63 79 83 84 96重新形成堆574039131535交换0# 与5# 对象，输出57第八趟：15 35 39 13 40 57 61 63 79 83 84 96重新形成堆4035391315交换0# 与4# 对象，输出40第九趟：13 35 15 39 40 57 61 63 79 83 84 96重新形成堆39351513交换0# 与3# 对象，输出39第十趟：15 13 35 39 40 57 61 63 79 83 84 96重新形成堆351315交换0# 与2# 对象，输出35第十一趟：13 15 35 39 40 57 61 63 79 83 84 96重新形成堆1513交换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第四趟排序后 13 15 35 39 40 57 61 63 79 83 84 9613、如果每个结点占用2个磁盘块因而需要2次磁盘访问才能实现读写，那么在一棵有n个关键码的2m阶B树中，每次搜索需要的最大磁盘访问次数是多少？14、已知如图所示的有向图，请给出该图的:顶点123456入度出度（1） 每个顶点的入/出度；（2） 邻接矩阵；（3） 邻接表；（4） 逆邻接表。15、设有一组关键字19，01，23，14，55，20，84，27，68，11，10，77，采用哈希函数：H(key)=key % 13 采用开放地址法的线性探测再散列方法解决冲突，试在 018 的散列地址空间中对该关键字序列构造哈希表并计算其填充因子。依题意，m=19，线性探测再散列的下一地址计算公式为：d1=H(key)，dj+1=(dj+1) % m； j=1，2，；其计算函数如下：H(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(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