int value;
if ( ! m ) value = 3;
else value = unknown ( m-1 ) + 5; return value; }
执行语句为 cout << unknown (3)。 答案： 18
4、 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（10），A[2][2]存放位置在676（10），每个元素占一个空间，问A[3][3]（10）存放在什么位置？脚注（10）表示用10进制表示。
答案：设数组元素A[i][j]存放在起始地址为Loc(i,j)的存储单元中。 因为：Loc(2,2)= Loc(0,0)+2*n+2=644+2*n+2=676 所以：n=(676-2-644)/2=15
所以：Loc(3,3)= Loc(0,0)+3*15+3=644+45+3=692 5、设单链表结构为 struct ListNode {
int data ;
};
ListNode * link ;
下面的程序是以单链表为存储结构, 实现二路归并排序的算法, 要求链表不另外占用存储空间, 排序过程中不移动结点中的元素, 只改各链结点中的指针, 排序后r仍指示结果链表的第一个结点。在初始状态下, 所有待排序记录链接在一个以r为头指针的单链表中。例如,
在算法实现时，利用了一个队列做为辅助存储, 存储各有序链表构成的归并
段的链头指针。初始时, 各初始归并段为只有一个结点的有序链表。队列的数据类型为Queue, 其可直接使用的相关操作有
? 置空队列操作：makeEmpty ( );
? 将指针x加入到队列的队尾操作：EnQueue ( ListNode * x ); ? 退出队头元素, 其值由函数返回的操作：ListNode *DlQueue ( ); ? 判队列空否的函数, 空则返回1, 不空则返回0：int IsEmpty( )。 解决方法提示：
? 程序首先对待排序的单链表进行一次扫描, 将它划分为若干有序的子链表, 其表头 指针存放在一个指针队列中。
? 当队列不空时, 从队列中退出两个有序子链表, 对它们进行二路归并, 结果链表的表头指针存放到队列中。
? 如果队列中退出一个有序子链表后变成空队列, 则算法结束。这个有序子链表即为所求。
在算法实现时有 6 处语句缺失，请阅读程序后补上。 (1) 两路归并算法
void merge ( ListNode * ha, ListNode * hb,, ListNode *& hc ) { ListNode *pa, *pb, *pc ;
if ( ha→data <= hb→data ) { hc = ha; pa = ha→link; pb = hb; }
else { hc = hb; pb = hb→link; pa = ha ; } pc = hc;
while ( pa && pb )
if pa→data <= pb→data (
{
)
pc→link = pa; pc = pa;
;
pa = pa→link
}
else
{ pc→link = pb; pc = pb;
pb = pb→link ;
}
if ( pa ) pc→link = pa;
else pc→link = pb; };
(2) 归并排序主程序 void mergesort ( ListNode * r ) { ListNode * s, t; Queue Q ;
if ( ! r ) return;
s = r; Q.EnQueue( r ) ;
while ( s ) { t = s→link;
while ( t != 0 && s→data <= t→data ) { s = t;link; }
if ( t ) {
s→link = 0; s = Q.EnQueue( s ) ;
t;
} }
while ( !Q.IsEmpty( ) ) { r = Q.DlQueue( );
if ( Q.IsEmpty( ) ) break;
= t→
t
s = Q.DlQueue( );
merge( r, s, Q.EnQueue( t ) t );
}
}
;
6、请读下列程序，该程序是在单链表中删除一个结点的算法，为空出的地方填上正确的语句。（7分）
void demo2(LinkList head,ListNode *p) {//head 是带头结点的单链表，删除P指向的结点 ListNode *q=head;
while(q&&q->next!=p ) q=q->next; if (q) Error(“*p not in head”); q->next=p->next; free(p);
}
7、 已知一完全二叉树从根结点开始，自顶向下，同一层自左向右连续编号，根
结点的编号为0，阅读以下程序请回答该程序所实现的功能： template
void linkedtosequent(Bintreenode
linkedtosequent(t->getleftchild(),a,2*i+1); linkedtosequent(t->getrightchild(),a,2*i+2); }}
主程序调用方式：linkedtosequent(t.root,a,0);
答案：该程序的功能是：将用二叉链表表示的完全二叉树转换为二叉树的顺序（数组）表示。
8、设散列表为HT[13], 散列函数为 H (key) = key 。用闭散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。
(1) 采用线性探查法寻找下一个空位, 画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度和搜索不成功的平均搜索长度。
(2) 采用双散列法寻找下一个空位, 再散列函数为 RH (key) = (7*key) % 10 + 1, 寻找下一个空位的公式为 Hi = (Hi-1 + RH (key)) % 13, H1 = H (key)。画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度。 答案：使用散列函数H(key)=key mod 13 有：
H（12）=12， H（23）=10，H（45）=6，H（57）=5，H（20）=7，H（03）=3，H（78）=0，H（31）=5，H（15）=2，H（36）=10 利用线性探查法造表： 0 78 1 1 2 15 1 3 03 1 4 5 57 1 6 45 1 7 20 1 8 31 4 9 10 23 1 11 36 2 12 12 1 搜索成功的平均搜索长度为：
ASLsucc =1/10（1+1+1+1+1+1+4+1+2+1）=14/10 搜索不成功的平均搜索长度为：
ASLunsucc =1/13（2+1+3+2+1+5+4+3+2+1+5+4+3）=36/13 利用双散列法造表：
Hi =（Hi-1 +RH(key)）, Hi =H(key) 0 78 1 1 2 15 1 3 03 1 4 5 57 1 6 45 1 7 20 1 8 31 3 9 36 5 10 23 1 11 12 12 1 9、阅读下面程序，指出其算法的功能并求出其时间复杂度。
（1） int Prime(int n){
int i=2,x=(int)sqrt(n);