数 据 结 构 习 题 集

(4)从带有附加表头结点的循环单链表中删除其值等于x的第一个结点。 (4) 解答:status delete(HL,x) { (1) q＝HL; p＝HL->next;

(2) while (p!=HL) && (p->data!=x) { q＝p;

p＝p->next;

}

(3) if (p= =HL) error('not found'); else {q->next＝p->next; free(p); }

}

(5)在单链表中指针p所指结点之前插入一个值为x的新结点。 (5) 解答:status insert(HL,p,x){

malloc(q);

q->data＝p->data; q->next＝p->next; p->next＝q; p->data＝x; }

(6)从循环单链表中查找出最小值。 (6) 解答: elemtype min(HL){ //从循环单链表HL中查找出最小值 if (HL= =nil ) {

printf('HL＝nil'); return; }

min＝HL->data; p＝HL->next;

while (p!=HL) {

(1) if (p->datadata; (2) p＝p->next; }

}

(7)根据一维数组A(1:n)中顺序存储的具有n个元素的线性表建立一个带有附加表头结 点的单链表。

(7) 解答:status create(HL,A,n) {

(1) malloc(HL); q＝HL; // 产生附加表头结点 (2) for (i＝1 ;I<=n ;++i) { // 完成n个元素的依次链接 malloc(p);

p->data＝A(i); q->next＝p; q＝p;

}

(3) q->next＝nil ; // 把最后一个结点的指针域置空

17

}

23.请指出下面的过程执行p(5)和p(6)时分别输出的结果。 void P(int n); { if n>0 {

p(n-2);

printf(“%d”,n);

} }

23. 解答:这是一个递归过程，n执行一次就减2，当n≤0时该过程执行结束。因此，当n＝5 时，其输出结果为1、3、5；当n＝6时，其输出结果为2、4、6。 24.假定用一个循环单链表表示队列（称此为循环链队），该队列只设一个队尾指针， 不设队首指针，试编写下列算法：

(1)向循环链队插入一个元素为x的结点；

(1) 解答:status insert(Rear,x){

// 假定Rear为循环链队的队尾指针，x为待插入的元素 (1) malloc(p);

p->data＝x; // 建立值为x的新结点p＾ (2) if( Rear＝nil){

Rear＝p; Rear->next＝p; }

else {p->next＝Rear->next;

Rear->next＝p; Rear＝p;

}

// 若条件成立则建立循环链队的第一个结点，否则在队尾插入p＾结点 }

(2)从循环链队中删除一个结点（假定不需要保留被删除结点的值和不需要回收结点）。 (2) 解答:status delete(Rear){

if( Rear＝nil ) error('underflow'); if (Rear->next= =Rear) Rear＝nil;

else Rear->next＝Rear->next->next;

} //Rear＾.next 所指向的结点为循环链队的队首结点

25.设A(k)有如下10个元素：2，4，6，8，10，12，14，16，18，20。若对A(k)分别查找x＝1，3，13，21，试跟踪下面过程的执行，并分析该程序段关于n的计算时间。 【程序段】 i=1;j=n; do

18

{

k=(i+j)/2;

if A(k)<=x i=k+1 else j=k-1 }while !(i>j);

25.解答

(1)查找x＝1,n＝10

┏━━━┳━┳━┳━┳━━━━┳━━━━━━━┓ ┃ ┃i ┃j ┃k ┃A(k)? X ┃ ┃ ┣━━━╋━╋━╋━╋━━━━╋━━━━━━━┫ ┃第1次┃1 ┃10┃5 ┃ 10 > 1 ┃ 新j＝k－1＝4 ┃ ┃第2次┃1 ┃4 ┃2 ┃ 4 > 1 ┃ 新j＝k－1＝1 ┃ ┃第3次┃1 ┃1 ┃1 ┃ 2 > 1 ┃ 新j＝k－1＝0 ┃ ┗━━━┻━┻━┻━┻━━━━┻━━━━━━━┛ 当(i＝1)>(j＝0)时，过程终止。未找到。

(2)查找x＝3,n＝10

┏━━━┳━┳━┳━┳━━━━┳━━━━━━━┓ ┃ ┃i ┃j ┃k ┃A(k)? x ┃ ┃ ┣━━━╋━╋━╋━╋━━━━╋━━━━━━━┫ ┃第1次┃1 ┃10┃5 ┃ 10 > 3 ┃ 新j＝k－1＝4 ┃ ┃第2次┃1 ┃4 ┃2 ┃ 4 > 3 ┃ 新j＝k－1＝1 ┃ ┃第3次┃1 ┃1 ┃1 ┃ 2 < 3 ┃ 新i＝k＋1＝2 ┃ ┗━━━┻━┻━┻━┻━━━━┻━━━━━━━┛ 当(i＝2)>(j＝1)时，过程终止。未找到。

(3)查找x＝13,n＝10

┏━━━┳━┳━┳━┳━━━━┳━━━━━━━┓ ┃ ┃i ┃j ┃k ┃A(k)? x ┃ ┃ ┣━━━╋━╋━╋━╋━━━━╋━━━━━━━┫ ┃第1次┃1 ┃10┃5 ┃ 10 <13 ┃ 新i＝k＋1＝6 ┃ ┃第2次┃6 ┃10┃8 ┃ 16 >13 ┃ 新j＝k－1＝7 ┃ ┃第3次┃6 ┃7 ┃6 ┃ 12 <13 ┃ 新i＝k＋1＝7 ┃ ┃第4次┃7 ┃7 ┃7 ┃ 14 >13 ┃ 新j＝k－1＝6 ┃ ┗━━━┻━┻━┻━┻━━━━┻━━━━━━━┛ 当(i＝7)>(j＝6)时，过程终止。未找到。 (4)查找x＝21,n＝10

┏━━━┳━┳━┳━┳━━━━┳━━━━━━━┓ ┃ ┃i ┃j ┃k ┃ A(k)? x ┃ ┃ ┣━━━╋━╋━╋━╋━━━━╋━━━━━━━┫ ┃第1次┃1 ┃10┃5 ┃ 10 <21 ┃ 新i＝k＋1＝6 ┃ ┃第2次┃6 ┃10┃8 ┃ 16 <21 ┃ 新i＝k＋1＝9 ┃ ┃第3次┃9 ┃10┃9 ┃ 18 <21 ┃ 新i＝k＋1＝10┃ ┃第4次┃10┃10┃10┃ 20 <21 ┃ 新i＝k＋1＝11┃ ┗━━━┻━┻━┻━┻━━━━┻━━━━━━━┛

19

当(i＝11)>(j＝10)时，过程终止，未找到。该程序段的时间复杂型为O(log2 n)。

**26.分别写出对二叉树进行中根遍历和先根遍历的非递归算法(不允许使用转向语句)。 26. 解答:中根遍历的非递归算法： status inorder(bt){ top＝0; p＝bt; do{

(1) while (p!=nil ){ top＝top＋1; s[top]＝p;

p:＝p->left; //p指向左子树 }

(2) if (top>0 ){

p＝s[top]; top＝top－1;

printf(p->data);

p＝p->right; // p指向右子树 }

}while !((top＝0) && (p＝nil)); }

解答: 先根遍历的非递归算法： status preorder(bt) { top＝0; p＝bt do{

(1) while( p!=nil ){

printf (p->data); if (p->right!=nil){ top＝top＋1;

s[top]＝p->right;

}

//若右子树非空，则把链接指针保存起来， 待访问过左子树后再访问它 p＝p->left; //使p指向左子树 }

(2) if (top>0) { // 出栈，使p指向右子树 p＝s[top] top＝top－1; }

}while !((top＝0) && (p＝nil));

20