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、编写计算数组元素累加和的递归函数
template
T Rsum(T a[ ], int n)
{ / /计算a[0: n-1]的和
if (n > 0)
return Rsum(a, n-1) + a[n-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 )
cout<<”不存在结点 a ! ”;
else {
s->next=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时，逐步形成二叉树的过程如下图所示：
A
A
A
A

F
B
B
F
F
B

G
E
C
G
E
C
HIGJ
CD
E
FHIGJ

H
D
J
HI
J
D

I
EBCD

6、编写递归算法，计算二叉树中叶子结点的数目。
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)
{
cout<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 (m>n?m:n)+1;
}
}//Get_Depth
9、画出一次一个地将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 up
int hole = ++currentSize;
for( ; hole > 1 && x < array[ hole / 2 ]; hole /= 2 )
array[ hole ] = array[ hole / 2 ];
array[0] = array[ hole ] = x;
}
11、编程实现折半插入排序
void insertsort( int R[ ] , int n)
// 按照递增顺序对R[0]~R[n]进行折半插入排序
{ int i , j, left, right,mid;
for ( i=2 ; i=left ; j--)
R[ j+1 ]= R[j]; //元素后移
R[left] =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 15
i = 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 15]
i = 4 13 40 63 83 [84 35 96 57 39 79 61 15]
i = 5 13 40 63 83 84 [35 96 57 39 79 61 15]
i = 6 13 35 40 63 83 84 [96 57 39 79 61 15]
i = 7 13 35 40 63 83 84 96 [57 39 79 61 15]
i = 8 13 35 40 57 63 83 84 96 [39 79 61 15]
i = 9 13 35 39 40 57 63 83 84 96 [79 61 15]
i = 10 13 35 39 40 57 63 79 83 84 96 [61 15]
i = 11 13 35 39 40 57 61 63 79 83 84 96 [15]
i = 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 15
i = 1 13 [40 63 83 84 35 96 57 39 79 61 15]
i = 2 13 15 [63 83 84 35 96 57 39 79 61 40]
i = 3 13 15 35 [83 84 63 96 57 39 79 61 40]
i = 4 13 15 35 39 [84 63 96 57 83 79 61 40]
i = 5 13 15 35 39 40 [63 96 57 83 79 61 84]
i = 6 13 15 35 39 40 57 [96 63 83 79 61 84]
i = 7 13 15 35 39 40 57 61 [63 83 79 96 84]
i = 8 13 15 35 39 40 57 61 63 [83 79 96 84]
i = 9 13 15 35 39 40 57 61 63 79 [83 96 84]
i = 10 13 15 35 39 40 57 61 63 79 83 [96 84]
i = 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
④堆排序
关键字：　83　40　63　13　84　35　96　57　39　79　61　15
第一趟（建堆）：15 84 83 57 79 35 63 13 39 40 61 96
过程如下：
83

40
63

13
84
96
35

15
61
57
79
39

初始排列
96

84
83

57
79
63
35

15
61
13
40
39

初始堆
交换0# 与11# 对象，输出96
第二趟：15 79 83 57 61 35 63 13 39 40 84 96

15

84
83

57
79
63
35

61
13
40
39

重新形成堆

84

79
83

57
61
63
35

15
13
40
39

交换0# 与10# 对象，输出84
第三趟：40 79 63 57 61 35 15 13 39 83 84 96
重新形成堆

83

79
63

57
61
15
35

13
40
39

交换0# 与9# 对象，输出84
第四趟：39 61 63 57 40 35 15 13 79 83 84 96
重新形成堆

79

61
63

57
40
15
35

13
39

交换0# 与8# 对象，输出79
第五趟：13 61 39 57 40 35 15 63 79 83 84 96
重新形成堆

63

61
39

57
40
15
35

13

交换0# 与7# 对象，输出63
第六趟：15 57 39 13 40 35 61 63 79 83 84 96
重新形成堆

61

57
39

13
40
15
35

交换0# 与6# 对象，输出61

第七趟：35 40 39 13 15 57 61 63 79 83 84 96
重新形成堆

57

40
39

13
15
35

交换0# 与5# 对象，输出57
第八趟：15 35 39 13 40 57 61 63 79 83 84 96
重新形成堆

40

35
39

13
15

交换0# 与4# 对象，输出40
第九趟：13 35 15 39 40 57 61 63 79 83 84 96
重新形成堆

39

35
15

13

交换0# 与3# 对象，输出39
第十趟：15 13 35 39 40 57 61 63 79 83 84 96
重新形成堆

35

13
15

交换0# 与2# 对象，输出35
第十一趟：13 15 35 39 40 57 61 63 79 83 84 96

重新形成堆

15

13

交换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 96

13、如果每个结点占用2个磁盘块因而需要2次磁盘访问才能实现读写，那么在一棵有n个关键码的2m阶B树中，每次搜索需要的最大磁盘访问次数是多少？

14、已知如图所示的有向图，请给出该图的:
顶点
1
2
3
4
5
6
入度

出度

（1） 每个顶点的入/出度；
（2） 邻接矩阵；
（3） 邻接表；
（4） 逆邻接表。

15、设有一组关键字{19，01，23，14，55，20，84，27，68，11，10，77}，采用哈希函数：H(key)=key % 13 采用开放地址法的线性探测再散列方法解决冲突，试在 0～18 的散列地址空间中对该关键字序列构造哈希表并计算其填充因子α。
依题意，m19，线性探测再散列的下一地址计算公式为：
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=10
H(14)=14 % 13=1(冲突)
H(14)=(1+1) % 19 =2
H(55)=55 % 13=3
H(20)=20 % 13=7
H(84)=84 % 13=6 (冲突)
H(84)=(6+1) % 19=7 (仍冲突)
H(84)=(7+1) % 19=8
H(27)=27 % 13=1 (冲突)
H(27)=(1+1) % 19=2 (冲突)
H(27)=(2+1) % 19=3 (仍冲突)
H(27)=(3+1) % 19=4
H(68)=68 % 13=3 (冲突)
H(68)=(3+1) % 19=4 (仍冲突)
H(68)=(4+1)% 19=5
H(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/19≈0.63。
9