數(shù)據(jù)結(jié)構(gòu)(C語言版)第一二章習(xí)題答案

1、第1章 緒論習(xí)題1簡(jiǎn)述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、抽象數(shù)據(jù)類型。2試舉一個(gè)數(shù)據(jù)結(jié)構(gòu)的例子，敘述其邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)兩方面的含義和相互關(guān)系。3簡(jiǎn)述邏輯結(jié)構(gòu)的四種基本關(guān)系并畫出它們的關(guān)系圖。4存儲(chǔ)結(jié)構(gòu)由哪兩種基本的存儲(chǔ)方法實(shí)現(xiàn)？5選擇題（1）在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（ ）。A動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C線性結(jié)構(gòu)和非線性結(jié)構(gòu) D內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)（2）與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、個(gè)數(shù)無關(guān)的是數(shù)據(jù)的（ ）。A存儲(chǔ)結(jié)構(gòu) B存儲(chǔ)實(shí)現(xiàn)C邏輯結(jié)構(gòu) D運(yùn)算實(shí)現(xiàn)（3）通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著

2、（ ）。 A數(shù)據(jù)具有同一特點(diǎn)B不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對(duì)應(yīng)數(shù)據(jù)項(xiàng)的類型要一致C每個(gè)數(shù)據(jù)元素都一樣D數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等（4）以下說法正確的是（ ）。A數(shù)據(jù)元素是數(shù)據(jù)的最小單位B數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位C數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項(xiàng)的集合D一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)（5）以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)的術(shù)語是（ ）。A順序隊(duì)列 B. 鏈表 C. 有序表 D. 鏈棧（6）以下數(shù)據(jù)結(jié)構(gòu)中，（ ）是非線性數(shù)據(jù)結(jié)構(gòu)A樹 B字符串 C隊(duì) D棧6試分析下面各程序段的時(shí)間復(fù)雜度。（1）x=90; y=100; while(y>0)if(x>10

3、0) x=x-10;y-;else x+;（2）for (i=0; i<n; i+)for (j=0; j<m; j+)aij=0;（3）s=0; for i=0; i<n; i+)for(j=0; j<n; j+) s+=Bij;sum=s;（4）i=1; while(i<=n) i=i*3;（5）x=0;for(i=1; i<n; i+) for (j=1; j<=n-i; j+)x+;（6）x=n; /n>1y=0;while(x(y+1)* (y+1) y+;（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）因?yàn)?/p>

4、x+共執(zhí)行了n-1+n-2+1= n(n-1)/2，所以執(zhí)行時(shí)間為O（n2）（6）O()第2章 線性表1選擇題（1）一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的地址是（ ）。A110 B108 C100 D120（2）在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O(1)的操作是（ ）。A訪問第i個(gè)結(jié)點(diǎn)（1in）和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（2in） B在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1in）C刪除第i個(gè)結(jié)點(diǎn)（1in）D將n個(gè)結(jié)點(diǎn)從小到大排序（3） 向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變，平均要移動(dòng) 的元素個(gè)數(shù)為（ ）。A8 B63.5 C63 D7（4

5、）鏈接存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間（ ）。A分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針B只有一部分，存放結(jié)點(diǎn)值C只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針D分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)（5）線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（ ）。A必須是連續(xù)的 B部分地址必須是連續(xù)的C一定是不連續(xù)的 D連續(xù)或不連續(xù)都可以（6）線性表在（ ）情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。A需經(jīng)常修改中的結(jié)點(diǎn)值 需不斷對(duì)進(jìn)行刪除插入 C中含有大量的結(jié)點(diǎn) 中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜（7）單鏈表的存儲(chǔ)密度（ ）。A大于1 B等于1 C小于1 D不能確定（8）將兩個(gè)各有n個(gè)元素的有序表歸

6、并成一個(gè)有序表，其最少的比較次數(shù)是（ ）。An B2n-1 C2n Dn-1（9）在一個(gè)長(zhǎng)度為n的順序表中，在第i個(gè)元素（1in+1）之前插入一個(gè)新元素時(shí)須向后移動(dòng)（ ）個(gè)元素。An-i Bn-i+1 Cn-i-1 Di(10) 線性表L=(a1，a2,an)，下列說法正確的是（ ）。A每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼B線性表中至少有一個(gè)元素C表中諸元素的排列必須是由小到大或由大到小D除第一個(gè)和最后一個(gè)元素外，其余每個(gè)元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和直接后繼。(11) 若指定有n個(gè)元素的向量，則建立一個(gè)有序單鏈表的時(shí)間復(fù)雜性的量級(jí)是（ ）。AO(1) BO(n) CO(n2) DO(nl

7、og2n)(12) 以下說法錯(cuò)誤的是（ ）。A求表長(zhǎng)、定位這兩種運(yùn)算在采用順序存儲(chǔ)結(jié)構(gòu)時(shí)實(shí)現(xiàn)的效率不比采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)實(shí)現(xiàn)的效率低B順序存儲(chǔ)的線性表可以隨機(jī)存取C由于順序存儲(chǔ)要求連續(xù)的存儲(chǔ)區(qū)域，所以在存儲(chǔ)管理上不夠靈活D線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)(13) 在單鏈表中，要將s所指結(jié)點(diǎn)插入到p所指結(jié)點(diǎn)之后，其語句應(yīng)為（ ）。As->next=p+1; p->next=s;B(*p).next=s; (*s).next=(*p).next;Cs->next=p->next; p->next=s->next;Ds->next=p->next;

8、 p->next=s; (14) 在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針（ ）。Ap->next->prior=p->prior; p->prior->next=p->next;Bp->next=p->next->next; p->next->prior=p;Cp->prior->next=p; p->prior=p->prior->prior;Dp->prior=p->next->next; p->next=p->prior->prior;(1

9、5) 在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點(diǎn)后插入q所指向的新結(jié)點(diǎn)，其修改指針的操作是（ ）。Ap->next=q; q->prior=p; p->next->prior=q; q->next=q;Bp->next=q; p->next->prior=q; q->prior=p; q->next=p->next;Cq->prior=p; q->next=p->next; p->next->prior=q; p->next=q;Dq->prior=p; q->next=p->ne

10、xt; p->next=q; p->next->prior=q;2算法設(shè)計(jì)題（1）將兩個(gè)遞增的有序鏈表合并為一個(gè)遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個(gè)鏈表的存儲(chǔ)空間, 不另外占用其它的存儲(chǔ)空間。表中不允許有重復(fù)的數(shù)據(jù)。void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc) pa=La->next; pb=Lb->next; Lc=pc=La; /用La的頭結(jié)點(diǎn)作為L(zhǎng)c的頭結(jié)點(diǎn) while(pa && pb) if(pa->data<pb->dat

11、a) pc->next=pa;pc=pa;pa=pa->next; else if(pa->data>pb->data) pc->next=pb; pc=pb; pb=pb->next; else / 相等時(shí)取La的元素，刪除Lb的元素 pc->next=pa;pc=pa;pa=pa->next; q=pb->next;delete pb ;pb =q; pc->next=pa?pa:pb; /插入剩余段 delete Lb; /釋放Lb的頭結(jié)點(diǎn) （2）將兩個(gè)非遞減的有序鏈表合并為一個(gè)非遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個(gè)

12、鏈表的存儲(chǔ)空間, 不另外占用其它的存儲(chǔ)空間。表中允許有重復(fù)的數(shù)據(jù)。void union(LinkList& La, LinkList& Lb, LinkList& Lc, ) pa = La->next; pb = Lb->next; / 初始化 Lc=pc=La; /用La的頭結(jié)點(diǎn)作為L(zhǎng)c的頭結(jié)點(diǎn) Lc->next = NULL; while ( pa | pb ) if ( !pa ) q = pb; pb = pb->next; else if ( !pb ) q = pa; pa = pa->next; else if (pa-&g

13、t;data <= pb->data ) q = pa; pa = pa->next; else q = pb; pb = pb->next; q->next = Lc->next; Lc->next = q; / 插入 delete Lb; /釋放Lb的頭結(jié)點(diǎn) （3）已知兩個(gè)鏈表A和B分別表示兩個(gè)集合，其元素遞增排列。請(qǐng)?jiān)O(shè)計(jì)算法求出A與B的交集，并存放于A鏈表中。void Mix(LinkList& La, LinkList& Lb, LinkList& Lc, ) pa=la->next;pb=lb->next;

14、設(shè)工作指針pa和pb；Lc=pc=La; /用La的頭結(jié)點(diǎn)作為L(zhǎng)c的頭結(jié)點(diǎn)while(pa&&pb) if(pa->data=pb->data)交集并入結(jié)果表中。 pc->next=pa;pc=pa;pa=pa->next; u=pb;pb=pb->next; delete u; else if(pa->data<pb->data) u=pa;pa=pa->next; delete u;else u=pb; pb=pb->next; delete u;while(pa) u=pa; pa=pa->next; de

15、lete u; 釋放結(jié)點(diǎn)空間while(pb) u=pb; pb=pb->next; delete u;釋放結(jié)點(diǎn)空間pc->next=null;置鏈表尾標(biāo)記。delete Lb; 注： 本算法中也可對(duì)B表不作釋放空間的處理（4）已知兩個(gè)鏈表A和B分別表示兩個(gè)集合，其元素遞增排列。請(qǐng)?jiān)O(shè)計(jì)算法求出兩個(gè)集合A和B 的差集（即僅由在A中出現(xiàn)而不在B中出現(xiàn)的元素所構(gòu)成的集合），并以同樣的形式存儲(chǔ)，同時(shí)返回該集合的元素個(gè)數(shù)。void Difference（LinkedList A，B，*n）A和B均是帶頭結(jié)點(diǎn)的遞增有序的單鏈表，分別存儲(chǔ)了一個(gè)集合，本算法求兩集合的差集，存儲(chǔ)于單鏈表A中，*n是

16、結(jié)果集合中元素個(gè)數(shù)，調(diào)用時(shí)為0p=A->next； p和q分別是鏈表A和B的工作指針。 q=B->next； pre=A； pre為A中p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針。 while（p!=null && q!=null）if（p->data<q->data）pre=p；p=p->next；*n+； A鏈表中當(dāng)前結(jié)點(diǎn)指針后移。else if（p->data>q->data）q=q->next； B鏈表中當(dāng)前結(jié)點(diǎn)指針后移。else pre->next=p->next； 處理A，B中元素值相同的結(jié)點(diǎn)，應(yīng)刪除。 u=p

17、； p=p->next； delete u； 刪除結(jié)點(diǎn)（5）設(shè)計(jì)算法將一個(gè)帶頭結(jié)點(diǎn)的單鏈表A分解為兩個(gè)具有相同結(jié)構(gòu)的鏈表B、C，其中B表的結(jié)點(diǎn)為A表中值小于零的結(jié)點(diǎn)，而C表的結(jié)點(diǎn)為A表中值大于零的結(jié)點(diǎn)（鏈表A的元素類型為整型，要求B、C表利用A表的結(jié)點(diǎn)）。（6）設(shè)計(jì)一個(gè)算法，通過一趟遍歷在單鏈表中確定值最大的結(jié)點(diǎn)。ElemType Max (LinkList L )if(L->next=NULL) return NULL;pmax=L->next; /假定第一個(gè)結(jié)點(diǎn)中數(shù)據(jù)具有最大值p=L->next->next;while(p != NULL )/如果下一個(gè)結(jié)點(diǎn)存

18、在if(p->data > pmax->data) pmax=p;p=p->next;return pmax->data;（7）設(shè)計(jì)一個(gè)算法，通過遍歷一趟，將鏈表中所有結(jié)點(diǎn)的鏈接方向逆轉(zhuǎn)，仍利用原表的存儲(chǔ)空間。void inverse(LinkList &L) / 逆置帶頭結(jié)點(diǎn)的單鏈表 L p=L->next; L->next=NULL; while ( p) q=p->next; / q指向*p的后繼 p->next=L->next; L->next=p; / *p插入在頭結(jié)點(diǎn)之后 p = q; （8）設(shè)計(jì)一個(gè)算法，刪

19、除遞增有序鏈表中值大于mink且小于maxk的所有元素（mink和maxk是給定的兩個(gè)參數(shù)，其值可以和表中的元素相同，也可以不同 ）。void delete(LinkList &L, int mink, int maxk) p=L->next; /首元結(jié)點(diǎn) while (p && p->data<=mink) pre=p; p=p->next; /查找第一個(gè)值>mink的結(jié)點(diǎn) if (p) while (p && p->data<maxk) p=p->next; / 查找第一個(gè)值 maxk 的結(jié)點(diǎn) q=pr

20、e->next; pre->next=p; / 修改指針 while (q!=p) s=q->next; delete q; q=s; / 釋放結(jié)點(diǎn)空間 /if（9）已知p指向雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，其結(jié)點(diǎn)結(jié)構(gòu)為data、prior、next三個(gè)域，寫出算法change(p),交換p所指向的結(jié)點(diǎn)和它的前綴結(jié)點(diǎn)的順序。知道雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，與前驅(qū)交換涉及到四個(gè)結(jié)點(diǎn)（p結(jié)點(diǎn)，前驅(qū)結(jié)點(diǎn)，前驅(qū)的前驅(qū)結(jié)點(diǎn)，后繼結(jié)點(diǎn)）六條鏈。void Exchange（LinkedList p）p是雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，本算法將p所指結(jié)點(diǎn)與其前驅(qū)結(jié)點(diǎn)交換。q=p->llink； q->llink->rlink=p； p的前驅(qū)的前驅(qū)之后繼為p p->llink=q->llink； p的前驅(qū)指向其前驅(qū)的前驅(qū)。