数据结构第1-3章作业参考答案 (2)

(7)

【2.5】 【解】

L L

L

L 2 10 P 14 Q 6 R 16 S … 12 4 ∧ ∧ 1 1 3 2 5 3 7 4 ∧ 5 6 7 8 ∧

L 8 ∧ 2 4 6 7

【2.6】 【解】 a. (4)(1)

b. (7)(11)(8)(4)(1) c. (5)(12)

d. (9)(4)(1)或(9)(1)(6)

【2.7】 【解】

a. (11)(3)(14)

b. (10)(12)(8)(11)(3)(14) c. (10)(12)(7)(3)(14) d. (12)(11)(3)(14) e. (9)(11)(3)(14)

【2.8】 【解】

a. (7)(6)(12)(3)或(6)(12)(7)(3)或(6)(7)(12)(3)或(7)(12)(6)(3)或(7)(12)(3)(6)等 b. (8)(5)(13)(4)或(8)(13)(5)(4)或(13)(8)(5)(4)或(5)(8)(13)(4)等 c. (15)(1)(11)(18) d. (16)(2)(10)(18) e. (9)(14)(17)

【2.10】 【解】

Status DeleteK(SqList &a, int i, int k){

//本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素 if (i<1||i>a.length||k<0||k>a.length-i) return INFEASIBLE; for (j=0; j

a.elem[j+i-1]=a.elem[j+k+i-1];

a.length-=k; return OK; }//DeleteK

或一：for循环改变如下，算法其余部分不变。 ……

for (j=i+k; j<=a.length; j++) a.elem[j-k-1]=a.elem[j-1];

……

或二：for循环改变如下，算法其余部分不变。 ……

for (j=i-1; j

……

【2.13】

【解法一】查找算法必须找到待查找结点在内存中的地址，不能仅仅找到位序。 LinkList Locate(Linklist L, ElemType X){

//在单链表L中查找第1个值为X的元素，若找到，则返回它的地址，否则返回空指针。 for (p=L->next; p&&p->data!=X; p=p->next); //循环体为空 return p; }//Locate 【解法二】

Status Locate(Linklist L, ElemType X, LinkList &p){

//在单链表L中查找第1个值为X的元素，则用形参p返回它的地址。 //若找到，返回OK，否则返回ERROR。 p=L->next;

while(p&&p->data!=X)

p=p->next; if (p) return OK; return ERROR; }//Locate

【2.14】 【解法一】

int Length(LinkList L ) { k=0;

for(p=L; p->next; p=p->next) k++; return k; }//Length

【解法二】

int Length(LinkList L ) { k=0;

P=L->next; while(p){ k++;

p=p->next; }

return k; }//Length

【3.1】 【解】

（1）123 231 321 213 132

（2）可以得到135426的出站序列，但不能得到435612的出站序列。因为4356出站说明12已经在栈中，1不可能先于2出栈。135426的出站序列为：SXSSXSSXXXSX。

【3.3】

【解】输出结果：stack

【3.4】 【解】

（1） 栈中的数据元素逆置。

（2） 用栈T作辅助，将栈S中值为e的所有元素删除。

【3.12】

【解】输出结果：char

【3.13】

【解】用栈作辅助，将队列中的数据元素逆置。