浙江工商大学数据结构期末复习题2(4)

(1) if (i<＝0) or (HL＝nil) error('not h&&le'); (2) if (i＝1 )

{ HL＝HL->next; return ; }

(3) j＝1; p＝HL; //p指针所指向的结点，是单链表中第j个结点 while (jnext; }

// 寻找第i个结点的前驱结点 (4) if (p->next!= =nil)

p->next＝p->next->next; else error('out of range'); }

(3)删除单链表中由指针p所指向的结点。 (3) 解答:status delete(HL,P,X){

// 删除单链表HL中由指针p所指向的结点 if (p->next＝nil ) error ('not delete'); X＝p->data; q＝p->next; p->data＝p->next->data; p->next＝p->next->next; free(q); }

或者：

status delete(HL,P,X) { if ( HL＝p ) {

X＝HL->data ; HL＝HL->next; free(p);

} else{

(1) q＝HL;

(2) while (q->next!=nil) && (q->next!=p) q＝q->next; (3) if (q->next＝p){ X＝p->data;

q->next＝p->next;

free(p) }

else error('*p结点不存在');

}

}

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

16

(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 {

k=(i+j)/2;

if A(k)<=x i=k+1

18

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 ┃ ┗━━━┻━┻━┻━┻━━━━┻━━━━━━━┛ …… 此处隐藏：1496字，全部文档内容请下载后查看。喜欢就下载吧 ……