數(shù)據(jù)結(jié)構(gòu)第二章習(xí)題

1、數(shù)據(jù)結(jié)構(gòu)第二章習(xí)題2.1.1 向量1 定義向量指的是所有元素都是同一類型結(jié)點(diǎn)的線性表。向量的定義如下：typeof ElemType vectorn0 這里的ElemType 可以是任何相應(yīng)的數(shù)據(jù)類型如 int, float 或char 等，在算法中，我們規(guī)定 ElemType 缺省是int 類型。向量中的元素個(gè)數(shù)n 小于或等于某一整數(shù) n0。說明 在C語言中，數(shù)組的下標(biāo)是從0開始的，但為了描述算法簡潔，本書中的向量規(guī)定從下標(biāo)1開始，這樣，讀者可不必考慮下標(biāo)0的數(shù)組值。2 向量的建立輸入n個(gè)整數(shù)，產(chǎn)生一個(gè)存儲這些整數(shù)的向量A的函數(shù)如下： void create ( A, n) vector A

2、; int n; int i;for (i=0;i<=n;i+) scanf (“%d,Ai)；3 向量的存儲方法向量通常的存儲方法是順序存儲，每個(gè)元素在存儲中占用的空間大小相同，若第一個(gè)元素存放的位置是LOC(k1), 每個(gè)元素占用的元素大小為s，則元素ki的存放位置為： LOC(ki)= LOC(k1)+s * (i-1)任給一個(gè)i，便可以很快計(jì)算出LOC(ki)，因此，對順序存儲的向量要查找任何一個(gè)元素都很方便。 單項(xiàng)選擇題1 一個(gè)向量第一個(gè)元素的存儲地址是100，每個(gè)元素的長度為2，則第5個(gè)元素的地址是。A) 110 B) 108 C) 100 D)1204 向量的插入在一個(gè)有n

3、個(gè)元素的向量A中的第 i個(gè)元素之前插入一個(gè)元素x的函數(shù)如下：void insert (A,n,x)vector A;int n,x; int j; if (I<1 | i>n) printf (“值錯(cuò)誤！n”); else for (j=n;j>=i;j-) Aj+1=Aj; /*將第i個(gè)元素及其后的元素后移*/ Aj=x; n+; /向量長度增1*/ 5向量的刪除在一個(gè)有n個(gè)元素的向量A中刪除第i個(gè)的函數(shù)如下： void delete (A,n) vector A; int n; int j;if (I<1 | i>n)printf (“i值錯(cuò)誤！n”);els

4、e for (j=1;j<=n;j+) Aj=aj+1; /*第i個(gè)元素之后的元素前移*/ n-; 6. 向量的查找在一個(gè)有n個(gè)元素的向量A中查找元素值為x的元素的函數(shù)如下： void find(A, n,x)vector A;int n, x;int j；i=1;while(I<=n&& Ai<>x)I+;if(I<=n) printf(“找到了！ n”);else printf(“未找到n”);2.2.1 向量習(xí)題解析1、 已知一個(gè)向量A，其中的元素按值非遞減有序排列，編寫一個(gè)函數(shù)插入一個(gè)元素x后保持該向量仍按遞減有序排列。解：本題的算法思想是

5、：先找到適當(dāng)?shù)奈恢?，然后后移元素空出一個(gè)位置，再將x插入。實(shí)現(xiàn)本題功能的函數(shù)如下： void insert(vector A, int n, x)int I,j;if(x>=An)An+1=x /*若x大于最后的元素，則將其插入到最后*/else I=1; while(x>=AI)I+; /*查找插入位置*/ for(j=n;j>=I;j-)Aj+1=Aj; /*移出插入x的位置*/ AI=x; n+; /*將x插入，向量長度增1*/ 2、 已知一個(gè)向量中的元素按元素值非遞減有序排列，編寫一個(gè)函數(shù)刪除向量中多余的值相同的元素；解：本題的算法思想是：由于向量中的元素按元素值非遞

6、減有序排列，值相同的元素必為相鄰的元素，因此依次比較相鄰兩個(gè)元素，若值相等，則刪除其中一個(gè)，否則繼續(xù)向后查找，實(shí)現(xiàn)本題功能的函數(shù)如下： void del(vect or A, int n) /*向量A的長度為n*/ int I=1, j; while(I<=n-1) if(AI!=AI+1)I+; /*元素值不相等，繼續(xù)向下找*/else for(j=(I+2)；j<=n;j+)Aj-1=Aj; /*刪除第I+1個(gè)元素*/ n-; /*向量長度減1*/3、 編寫一個(gè)函數(shù)將一個(gè)向量A（有n個(gè)元素，且任何元素均不為0）分拆成兩個(gè)向量，使A大于0的元素存在B中，小于0的元素存放在C中。解

7、：本題的算法思想是：依次遍歷A的元素，比較當(dāng)前的元素值，大于0的賦給B(假設(shè)有p個(gè)元素)，小于0的賦給C（假設(shè)有q個(gè)元素）。實(shí)現(xiàn)本題功能的函數(shù)如下： void ret(vector A, int n,vector B, int p, vector C,int q) int I;p=0; q=0;for(I=1;I<=n;I+) if (AI>0) p+; Bp=AI; if (AI<0) q+; Cq=AI; 8.有兩個(gè)向量A（有m個(gè)元素）和B（有n個(gè)元素），其元素均以從小到大的升序排列，編寫一個(gè)函數(shù)將它們合并成一個(gè)向量C，要求C的元素也是從小到大的升序排列。解：本題的算法思

8、想是：依次掃描通過A和B的元素，比較當(dāng)前的元素的值，將較小值的元素賦給C，如此直到一個(gè)向量掃描完畢，然后將未完的一個(gè)向量的余下所有元素賦給C即可。實(shí)現(xiàn)本題功能的函數(shù)如下：viod link(A，B：vector；m，n：integer；VAR C：vector)vector A，B，C；int m,n; int i=1，j=1，k=1，l； while （i<=m&&j<=n）/*掃描通過A和B，將當(dāng)前掃描的較小元素賦給C*/ if (Ai<Bj) Ck=Ai;i+;k+; else Ck=Bj;j+;k+; if(j= =n) /*當(dāng)A未完成時(shí)，當(dāng)A的余下元

9、素賦給C*/ for ( l=(i+1);l<=m;l+) Ck=Al;k+; if(i = =m) /*當(dāng)B未完成時(shí)，當(dāng)B的余下元素賦給C*/ for ( l=j+1;l<=n;l+) Ck=Bl;k+; 2.2.2 鏈表習(xí)題解析6. 已知兩個(gè)整數(shù)集合A和B， 它們的元素分別依元素值遞增有序存放在兩個(gè)單鏈表HA和HB中，編寫一個(gè)函數(shù)求出這兩個(gè)集合的并集C，并要求表示集合C的鏈表的結(jié)點(diǎn)仍依元素值遞增有序存放。 解：假設(shè)HA和HB的頭指針分別為ha和hb， 先設(shè)置一個(gè)空的循環(huán)單鏈表HC，頭指針為hc，之后依次比較HA和HB的當(dāng)前結(jié)點(diǎn)的元素值，將較小元素值的結(jié)點(diǎn)復(fù)制一個(gè)并鏈接到HC的末

10、尾，若相等，則將其中之一復(fù)制一個(gè)并鏈接到HC的末尾。當(dāng)HA或HB為空后，把另一個(gè)鏈表的余下結(jié)點(diǎn)都復(fù)制并鏈接到HC的末尾。實(shí)現(xiàn)本題功能的函數(shù)如下： void union(ha,hb,hc) node *ha,*hb,*hc; node *p,*q,*r,*s;hc=node *malloc(sizeof(node);/*建立一個(gè)頭結(jié)點(diǎn)， r總是指向HC鏈表的最后一個(gè)結(jié)點(diǎn)*/r=hc;p=ha;q=hb;while(p!=NULL&&q!=NULL)if (p->data<q->data) s=(node*)malloc(sizeof(node);s->da

11、ta=p->data;r->next=s;r=s;p=p->next;else if (p->data>q->data) s=(node*)malloc(sizeof(node);s->data=q->data;r->next=s;r=s;q=q->next;else /*p->data=q->data的情況/ s=node*malloc(sizeof(node);q=q->next;if(p=NULL)/* 把q及之后的結(jié)點(diǎn)復(fù)制到HC中*/ while (q!=NULL) s=(node*)malloc(sizeo

12、f(node);s->data=p->data; r->next=s; r=s; p=p->next;r->next=NULL;s=hc;hc=hc->next;free(s); /*刪除頭結(jié)點(diǎn)*/15. 假設(shè)在長度大于1的循環(huán)單鏈表中， 既無頭結(jié)點(diǎn)也無頭指針，p為指向該鏈表中某個(gè)結(jié)點(diǎn)的指針， 編寫一個(gè)函數(shù)刪除該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。 解：本題利用循環(huán)單鏈表的特點(diǎn)，通過p指針可循環(huán)找到其前驅(qū)結(jié)點(diǎn)q及q的前驅(qū)結(jié)點(diǎn) r,然后將其刪除。實(shí)現(xiàn)本題功能的函數(shù)如下： node *del(p) node *p; node *q,*r; q=p; /*查找p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，用q指

13、針指向* / while(q->next!=p) q=q->next;r=q;/*查找q結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，用r指針指向*/while(r->next!=q) r=r->next;r->next=p;/*刪除q所指的結(jié)點(diǎn)*/free(q);return(p);基礎(chǔ)知識題2.1 描述以下概念的區(qū)別： 頭指針, 頭結(jié)點(diǎn)， 首元結(jié)點(diǎn)（第一個(gè)元素的結(jié)點(diǎn)）。2.2 填空題。（1） 在順序表中插入或刪除一個(gè)元素，需要平均移動 元素， 具體移動的元素個(gè)數(shù)與 有關(guān)。（2）順序表中邏輯上相鄰的元素的物理位置 緊鄰。（3）在單鏈表中， 除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲位置由 指示。（4）在

14、單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是 。 （5）對于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知p所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是 ；在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是 。2.3 在什么條件下用順序表比鏈表好？2.6 已知L是無表頭結(jié)點(diǎn)的單鏈表， 且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)， 也不是尾元結(jié)點(diǎn)， 試從下列提供的答案中選擇合適的語句序列。 a. 在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語句序列是 。 b. 在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語句序列是 。 c. 在表首插入S結(jié)點(diǎn)的語句序列是 。 d. 在表尾插入S結(jié)點(diǎn)的語句序列是 。 （1） P->next=S;（2） P->next=P->next->nex

15、t;（3） P->next=S->next;（4） S->next= P->next;（5） S->next=L;（6） S->next=NULL;（7） Q=P;（8） While (P->next!=Q) P=P->next;（9） While (P->next!=NULL ) P=P->next;（10） P=Q;（11） P=L;（12） L=S;（13） L=P;2.7已知L是帶表頭結(jié)點(diǎn)的非空單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)， 試從下列提供的答案中選擇合適的語句序列。a. 刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列是b

16、. 刪除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語句序列是c. 刪除P結(jié)點(diǎn)的語句序列是d. 刪除首元結(jié)點(diǎn)的語句序列是e. 刪除尾元結(jié)點(diǎn)的語句序列是（1） P= P->next;（2） P->next= P;（3） P->next=P->next->next;（4） P=P->next->next;（5） W hile (P!=NULL ) P=P->next;（6） While (Q->next!=NULL) P=Q; Q=Q->next;（7） While (P->next!=Q) P=P->next;（8） While (P->n

17、ext->next!=Q) P=P->next;（9） While (P->next->next!=NULL) P=P->next;（10） Q=P;（11） Q= P->next;（12） P=L;（13） L= L ->next;（14） Free(Q)鏈表基本習(xí)題一、單項(xiàng)選擇題1.不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是a. head=NULL b. head - >next=NULLc. head- >next=headd. head!=NULL2.帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是a. head=NULL b. head

18、- >next=NULLc. head- >next=headd. head!=NULL3.非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿足a. p ànext=NULLb. p=NULLc. p ànext=headd. p=head4.在循環(huán)單鏈表p所指結(jié)點(diǎn)之后插入s所指結(jié)點(diǎn)的操作是a. p àright=s; sàleft=p;pàrightàleft=s;sàright=pàright;b. p àright=s;pàrightàleft=s; sàle

19、ft=p; sàright=pàright;c. sàleft=p; sàright=pàright; p àright=s; pàrightàleft=s;d. sàleft=p; sàright=pàright; pàrightàleft=s; p àright=s;5.在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則執(zhí)行a. sànext =pànext;pànext=s;b. p

20、24;next =sànext;sànext=p;c. qànext=s;sànext=p;d. pànext=s;sànext=q;6.在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行a. sànext =p;pànext=s;b. sànext =pànext;pànext=s;c. sànext =pànext;p =s;d. pànext =s;sànext=p;7.在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)

21、行a. pànext =pànext ànext;b. p=pànext ; pànext =pànext ànext;c. pànext =pànext ;d. p =pànext ànext;8.假設(shè)雙鏈表結(jié)點(diǎn)的類型如下： typedef struct linknode int data; /*數(shù)據(jù)域*/ struct linknode *llink ; /*link是指向前驅(qū)結(jié)點(diǎn)的指針域*/ struct linknode *rlink ; /*rlink是指向后續(xù)結(jié)點(diǎn)的指針域*/bnode 下面給出的算法段是要把一個(gè)q所指新結(jié)點(diǎn)作為非空雙向鏈表中的p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)插入到該雙鏈表中，能正確完成要求的算法段是： a . qàrlink=p; qàllink=pàllink; pàllink=q; pàllink àrlink=q; b. pàllink=q; qàrlink=p; pàllink àrlink=q;qàllink =pàrlink;c