數(shù)據(jù)結(jié)構(gòu)線性表試題

1、第 2 章 線性表 2.1選擇題1對于線性表最常用的操作是查找指定序號的元素和在末尾插入元素，則選擇 ( )最節(jié)省時間A) 順序表B)帶頭結(jié)點的雙循環(huán)鏈表C)單鏈表D)帶尾結(jié)點的單循環(huán)鏈表【答案】 A2若長度為 n 的線性表采用順序存儲結(jié)構(gòu)， 在其第 i 個位置插入一個新元素的算法時間復雜 度為()(1 w i w n+1)。A) O(0)B) O(1) C ) O(n) D ) O(n2)【答案】 C3雙向鏈表中有兩個指針域， prior 和 next ，分別指向前驅(qū)及后繼， 設(shè) p 指向鏈表中的一個 結(jié)點，q指向一待插入結(jié)點，現(xiàn)要求在p前插入q，則正確的插入為()A) p->prio

2、r=q; q->next=p; p->prior->next=q; q->prior=p->prior;B) q->prior=p->prior; p->prior->next=q; q->next=p; p->prior=q->next;C) q->next=p; p->next=q; p->prior->next=q; q->next=p;D) p->prior->next=q; q->next=p; q->prior=p->prior; p->prio

3、r=q;【答案】 D4在一個具有 n 個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然保持有序的時間復雜度是) O(n ) D ) O(n2 )p 指針指向鏈尾結(jié)點的條件是() p->next=h)p->data=-1A) O(nlog2n ) B ) O(1 ) C【答案】 C5 在一個以 h 為頭指針的單循環(huán)鏈中，A) p->next=NULLBC) p->next->next=hD【答案】 B6對于一個具有 n 個結(jié)點的線性表，建立其單鏈表的時間復雜度是(A )O(n) B ) O(1)【答案】 A 8在雙向鏈表存儲結(jié)構(gòu)中，刪除 A) p->prior->

4、;next=p->nextC ) O(nlog2n) Dp 所指的結(jié)點時須修改指針(p->next->prior=p->prior;) O(n2)B) p->prior=p->prior->prior p->prior->next=p;C) p->next->prior=pp->next=p->next->nextD) p->next=p->prior->priorp->prior=p->next->next;答案】 A9線性表采用鏈式存儲時，其元素地址()A)必須是連續(xù)的B

5、)一定是不連續(xù)的C)部分地址是連續(xù)的D)連續(xù)與否均可【答案】 D2.2 填空題1 線性表L= (al, a2，an)用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是 ?！敬鸢浮? n-1 ) /22 在單鏈表中設(shè)置頭結(jié)點的作用是 。答案】主要是使插入和刪除等操作統(tǒng)一，在第一個元素之前插入元素和刪除第一個結(jié)點不 必另作判斷。另外，不論鏈表是否為空，鏈表頭指針不變。3線性表的順序存儲是通過 來反應元素之間的邏輯關(guān)系，而鏈式存儲結(jié)構(gòu)是通過 來反應元素之間的邏輯關(guān)系?！敬鸢浮浚?）數(shù)據(jù)元素的前后順序（ 2）元素中的指針4當對一個線性表經(jīng)常進行的是存取操作，而很少進行插

6、入和刪除操作時，則采用存儲結(jié)構(gòu)最節(jié)省時間 ，相反當經(jīng)常 進行插入和刪除操作時，則采用 存儲結(jié)構(gòu)最節(jié)省時間?！敬鸢浮浚?）順序 （ 2）鏈式5對于一個具有 n 個結(jié)點的單鏈表，在已知的結(jié)點 *p 后插入一個新結(jié)點的時間復雜度為 ，在給定值為 x 的結(jié)點后插入一個新結(jié)點的時間復雜度為 。【答案】（1） 0（1）（2） 0（n）7. 對于雙向鏈表，在兩個結(jié)點之間插入一個新結(jié)點需修改的指針共 個，單鏈表為 個。【答案】（ 1 ） 4（ 2） 28. 循環(huán)單鏈表的最大優(yōu)點是 。【答案】從任一結(jié)點出發(fā)都可訪問到鏈表中每一個元素。9若要在一個不帶頭結(jié)點的單鏈表的首結(jié)點*p 結(jié)點之前插入一個 *s 結(jié)點時，可

7、執(zhí)行下列操作：s->next=;p->next=s;t=p->data;p->data= ;s->data=;【答案】( 1 ) p->next( 2) s->data( 3 ) t10 某線性表采用順序存儲結(jié)構(gòu)，每個元素占據(jù)4 個存儲單元，首地址為 100 ，則下標為 11的（第 12 個）元素的存儲地址為 答案】 14411帶頭結(jié)點的雙循環(huán)鏈表 L 中只有一個元素結(jié)點的條件是 【答案】 L->next->next=L2.3 判斷題1 取線性表的第 i 個元素的時間同 i 的大小有關(guān)（【答案】X2線性表的特點是每個元素都有一個前驅(qū)和一個后

8、繼（【答案】X3 順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高（ 【答案】X4線性表采用鏈表存儲時，結(jié)點的存儲空間可以是不連續(xù)的（ 【答案】“在鏈表中比在順序存儲結(jié)構(gòu)5鏈表是采用鏈式存儲結(jié)構(gòu)的線性表，進行插入、 刪除操作時，中效率高（ ）【答案】“6順序存儲方式只能用于存儲線性結(jié)構(gòu)（【答案】X【解析】線性結(jié)構(gòu)、樹型結(jié)構(gòu)和圖狀結(jié)構(gòu)均可用順序存儲表示。9順序存儲結(jié)構(gòu)的主要缺點是不利于插入或刪除操作(【答案】“10順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好()【答案】X2.4 程序設(shè)計題1設(shè)順序表 va 中的數(shù)據(jù)元素遞增有序。 試設(shè)計一個算法， 將 x 插入到順序表的適當位

9、置上， 以保持該表的有序性?！舅惴ㄔ创a】void Insert_SqList(SqList va,int x)/* 把 x 插入遞增有序表 va 中 */ int i;if(va.length> MAXSIZE) return;for(i=va.length-1;va.elem>x&&i>=0;i-) va.elemi+1=va.elem;va.elemi+1=x;va.length+;/*Insert_SqList*/2 .設(shè)A= (al, a2,，am)和B= (bl, b2,，bn)均為順序表，試設(shè)計一個比較A, B大小的算法(請注意：在算法中，不要破

10、壞原表A和B)?！舅惴ǚ治觥勘容^順序表A和B，并用返回值表示結(jié)果，值為1,表示A>B;值為-1，表示A<B值為 0，表示 A=B。1) 當兩個順序表可以互相比較時,若對應元素不等,則返回值為1 或-1;2) 當兩個順序表可以互相比較的部分完全相同時,若表長也相同,則返回值為0;否則,哪 個較長,哪個就較大【算法源代碼】int ListComp(SqList A,SqList B) for(i=1;i<=A.length&&i<=B.length;i+) if(A.elem!=B.elem) return A.elem>B.elem?1:-1; if

11、(A.length=B.length) return 0; return A.length>B.length?1:-1; /*當兩個順序表可以互相比較的部分完全相同時,哪個較長,哪個就較大 */*ListComp */3 .已知指針ha和hb分別指向兩個單鏈表的頭結(jié)點，并且已知兩個鏈表的長度分別為m和n。試設(shè)計一個算法將這兩個鏈表連接在一起(即令其中一個表的首元結(jié)點連在另一個表的最后一個結(jié)點之后) ,假設(shè)指針 hc 指向連接后的鏈表的頭結(jié)點,并要求算法以盡可能短的時間 完成連接運算?！舅惴ǚ治觥? )單鏈表 ha 的頭結(jié)點作為連接后的鏈表的頭結(jié)點,即 hc=ha;2)查找單鏈表 ha 的

12、最后一個結(jié)點,由指針 p 指向,即 p->next=NULL;3 )將單鏈表hb的首元結(jié)點(非頭結(jié)點)連接在p之后，即p->next=hb->next ;4)回收單鏈表hb的頭結(jié)點空間【算法源代碼】void ListConcat(LinkList ha,LinkList hb,LinkList *hc)/* 把鏈表 hb 接在 ha 后面形成鏈 表 hc*/ *hc=ha; p=ha;/* 由指針 p 指向 ha 的尾元結(jié)點 */ p=p->next;p->next=hb->next;free(hb);/*ListConcat */4 .試設(shè)計一個算法，在無

13、頭結(jié)點的動態(tài)單鏈表上實現(xiàn)線性表操作INSERT ( L, i , b),并和在帶頭結(jié)點的動態(tài)單鏈表上實現(xiàn)相同操作的算法進行比較?！舅惴ǚ治觥?) 生成新結(jié)點存放元素 b，由指針new指向；2) 將 new 插入在單鏈表的第 i 個元素的位置上：若 i=1 ， new 插在鏈表首部；否則查找第i-1個結(jié)點，由指針p指向，然后將new插在p之后。【算法源代碼】void Insert(LinkList *L,int i,int b) LinkList new;new=(LinkList*)malloc(sizeof(LNode);new->data=b;if(i=1) /* 插入在鏈表頭部 *

14、/ New->next=*L; *L=new; else /* 插入在第 i 個元素的位置 */ p=*L; while(-i>1) p=p->next; new->next=p->next; p->next=new; /*Insert */5. 已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。 試設(shè)計一個高效的算法， 刪除表中所有值大于 mink 且小于 maxk 的元素(若表中存在這樣的元素) ，同時釋放被刪結(jié) 點空間(注意： mink 和 maxk 是給定的兩個參變量。它們的值可以和表中的元素相同，也可 以不同)。【算法分析】1) 查找最后一

15、個不大于 mink的元素結(jié)點，由指針 p指向；2) 如果還有比mink更大的元素，查找第一個不小于maxk的元素，由指針q指向；3) p->next=q ，即刪除表中所有值大于 mink 且小于 maxk 的元素?！舅惴ㄔ创a】void Delete_Between(LinkList *L,int mink,int maxk) p=*L;while(p->next->data<=mink) p=p->next; /*p是最后一個不大于 mink 的元素 */if(p->next) /* 如果還有比 mink 更大的元素 */ q=p->next;whi

16、le(q->data<maxk) q=q->next; /*q是第一個不小于 maxk 的元素 */p->next=q;/*Delete_Between */6. 已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。 試設(shè)計一個高效的算法， 刪除表中所有值相同的多余元素 (使得操作后的線性表中所有元素的值均不相同) ，同時釋放 被刪結(jié)點空間。【算法分析】1) 初始化指針p和q，分別指向鏈表中相鄰的兩個元素；2) 當 p->next 不為空時，做如下處理： 若相鄰兩元素不相等時， p 和 q 都向后推一步； 否則，當相鄰元素相等時，刪除多余元素?！舅惴ㄔ创a】

17、void Delete_Equal(LinkList *L) p=(*L)->next;q=p->next; /*p while(p->next) if(p->data!=q->data) /* p=p->next; else和 q 指向相鄰的兩個元素 */若相鄰兩元素不相等時，q=p->next; p和q都向后推一步*/ while(q->data=p->data) /*當相鄰元素相等時刪除多余元素 */ r=q; q=q->next; free(r);p->next=q;p=q;q=p->next;/*else*/*w

18、hile*/*Delete_Equal */ 7試設(shè)計一個算法，對帶頭結(jié)點的單鏈表實現(xiàn)就地逆置。算法分析】1）空表或長度為 1 的表，不做任何處理；2）表長大于 2 時，做如下處理： 首先將整個鏈表一分為二，即從鏈表的第一元素結(jié)點處斷開; 逐個地把剩余鏈表的當前元素 q插入到鏈表的頭部。 【算法源代碼】void LinkList_reverse(LinkList L) if(!L->next|!L->next->next) return;從鏈表的第一元素結(jié)點處斷p=L->next; q=p->next; s=q->next; p->next=NULL;

19、 /* 開*/while（s->next）q->next=p;p=q;q=s;s=s->next; /* 把 L 的元素逐個插入新表表頭 */q->next=p; s->next=q;L->next=s;/*LinkList_reverse*/8.設(shè)線性表 A= （al, a2,，am）和B= （ bl, b2,，bn）,試設(shè)計一個按下列規(guī)則合并 A, B為線性表C的算法，即使得C=（ al,bl,，am,bm,bm+1，bn ）當mW n 時；或者C=（ al,bl,，an,bn,an+1，am ）當m> n 時。線性表A, B和C均以單鏈表作存儲結(jié)

20、構(gòu)，且C表利用A表和B表中的結(jié)點空間構(gòu)成。注意:單鏈表的長度值 m和n均未顯式存儲?！舅惴ǚ治觥?）初始化指針p指向鏈表A的當前元素，指針 q指向鏈表B的當前元素；2)當鏈表 A 和 B 均為結(jié)束時，做如下處理： 將B的元素插入 若 A 非空，將 A 的元素插入 指針 p 和 q 同時后移【算法源代碼】void merge1(LinkList A,LinkList B,LinkList *C) p=A->next; q=B->next; *C=A;while(p&&q) s=p->next; p->next=q; /* 將 B 的元素插入 */if (s

21、) t=q->next;q->next=s;I* 若 A非空，將 A 的元素插入 */ p=s;q=t; I* 指針p和q同時后移*II*while*II*merge1 *I9 假設(shè)有兩個按元素值遞增有序排列的線性表A和B,均以單鏈表作存儲結(jié)構(gòu)，請設(shè)計一個算法將A表和B表歸并成一個按元素值遞減有序(即非遞增有序，允許表中含有值相同的元素)排列的線性表 C,并要求利用原表(即 A表和B表)的結(jié)點空間構(gòu)造C表?！舅惴ǚ治觥?按從小到大的順序依次把A和B的元素插入新表的頭部pc處，最后處理A或B的剩余元素?！舅惴ㄔ创a】void reverse_merge(LinkList A,Link

22、List B,LinkList *C) LinkList pa,pb,pre;pa=A->next;pb=B->next; I*pa和pb分別指向 A和B的當前元素*Ipre=NULL;while(pa|pb) if(pa->data<pb->data|!pb)/*將 A 的元素插入新表 *I pc=pa;q=pa->next;pa->next=pre;pa=q; else I* 將B的元素插入新表*I pc=pb;q=pb->next;pb->next=pre;pb=q; pre=pc;*C=A; A->next=pc; I* 構(gòu)造

23、新表頭 *II*reverse_merge*I10 .已知A，B和C為三個遞增有序的線性表，現(xiàn)要求對A表作如下操作：刪去那些既在B表中出現(xiàn)又在 C表中出現(xiàn)的元素。試對順序表編寫實現(xiàn)上述操作的算法，并分析你的算法的 時間復雜度(注意：題中沒有特別指明同一表中的元素值各不相同)?！舅惴ǚ治觥肯葟?B和C中找出共有元素，記為same,再在A中從當前位置開始， 凡小于same的元素均保留(存到新的位置)，等于same的就跳過，到大于same時就再找下一個 sama【算法源代碼】void SqList_Intersect_Delete(SqList *A,SqList B,SqList C) i=0;

24、j=0; k=0; m=0; I*i指示A中元素原來的位置，m為移動后的位置*Iwhile(i<(*A).length&&j<B.length&& k<C.length) if (B.elemj<C.elemk) j+;else if(B.elemj>C.elemk) k+;elsesame=B.elemj; /* 找到了相同元素 same*/ while(B.elemj=same) j+;while(C.elemk=same) k+; /*j 和 k 后移到新的元素 */ while(i<(*A).length&&a

25、mp;(*A).elem<same) (*A).elemm+=(*A).elemi+;/* 需保留的元素移動到新位置 */while(i<(*A).length&&(*A).elem=same) i+; /* 跳過相同的元素 */*while*/while(i<(*A).length) (*A).elemm+=(*A).elemi+; /*A 的剩余元素重新 存儲 */(*A).length=m;/* SqList_Intersect_Delete*/ 11設(shè) L 為單鏈表的頭結(jié)點地址，其數(shù)據(jù)結(jié)點的數(shù)據(jù)都是正整數(shù)且無相同的，試設(shè)計利用直 接插入的原則把該鏈表整

26、理成數(shù)據(jù)遞增的有序單鏈表的算法。【算法分析】本題明確指出單鏈表帶頭結(jié)點，其結(jié)點數(shù)據(jù)是正整數(shù)且不相同，要求利用直接 插入原則把鏈表整理成遞增有序鏈表。這就要求從第二結(jié)點開始，將各結(jié)點依次插入到有序 鏈表中?！舅惴ㄔ创a】void InsertSort (LinkList la) if(la->next!=NULL) /* 鏈表不為空表 */ p=la->next->next; /*p 指向第一結(jié)點的后繼 */ la->next->next=NULL;/* 直接插入原則認為第一元素有序，然后從第二元素起依次插入 */while (p!=NULL) r=p->ne

27、xt;/* 暫存 p 的后繼 */q=la;while (q->next!=NULL&&q->next->data<p->data) q=q->next;/* 查找插入位置 */ p->next=q->next;/* 將 p 結(jié)點鏈入鏈表 */q->next=p; p=r;12設(shè)有一個雙向循環(huán)鏈表，每個結(jié)點中除有prior ， data 和 next 三個域外，還增設(shè)了一個訪問頻度域 freq 。在鏈表被起用之前，頻度域 freq 的值均初始化為零，而每當對鏈表進 行一次LOCATE( L, X)的操作后，被訪問的結(jié)點(元素

28、值等于 X的結(jié)點)中的頻度域 freq 的值便增 1，同時調(diào)整鏈表中結(jié)點之間的次序，使其按訪問頻度非遞增的次序順序排列，以 便始終保持被頻繁訪問的結(jié)點總是靠近表頭結(jié)點。試編寫符合上述要求的LOCATE操作的算法。【算法分析】1) 在雙向鏈表中查找數(shù)據(jù)值為x的結(jié)點，由指針p指向，若找不到，直接返回，否則執(zhí)行第2 步；2) 修改 x 結(jié)點的訪問頻度 freq ，并將結(jié)點從鏈表上摘下；3) 順結(jié)點的前驅(qū)鏈查找該結(jié)點的位置，即找到一個結(jié)點的訪問頻度大于x結(jié)點的訪問頻度， 由指針 q 指向；若 q 和 p 不是相鄰結(jié)點，調(diào)整位置，把 p 插在 q 之后?！舅惴ㄔ创a】 DuLNode * Locate_

29、DuList(DuLinkList *L,int x) p=(*L)->next;沒找到 x 結(jié)點 */ 將 x 結(jié)點從鏈表上摘查找插入位置 */ 將 x 結(jié)點插入 */調(diào)整位置 */while(p.data!=x&&p!= (*L) p=p->next;if(p=(*L) return NULL; /*p->freq+; p->pre->next=p->next;p->next->pre=p->pre; /* 下*/q=p->pre;while(q->freq<=p->freq&&p

30、!= (*L) q=q->pre;/*if(q!=p->pre) /* q->next->pre=p;p->next=q->next;q->next=p;p->preq; /*return p;/*Locate_DuList */13.已知三個帶頭結(jié)點的線性鏈表A、B和C中的結(jié)點均依元素值自小至大非遞減排列(可能存在兩個以上值相同的結(jié)點)，編寫算法對A表進行如下操作：使操作后的鏈表A中僅留下三 個表中均包含的數(shù)據(jù)元素的結(jié)點，且沒有值相同的結(jié)點，并釋放所有無用結(jié)點。限定算法的 時間復雜度為 0(m+n+p),其中m n和p分別為三個表的長度?！舅惴?/p>

31、分析】留下三個鏈表中公共數(shù)據(jù)，首先查找兩表A和B中公共數(shù)據(jù)，再去 C中找有無該數(shù)據(jù)。要消除重復元素，應記住前驅(qū)，要求時間復雜度0 (m+n+p，在查找每個鏈表時，指針不能回溯?！舅惴ㄔ创a】LinkList Common(LinkList A, LinkList B, LinkList C) pa=A->next;pb=B->next; pc=C->next; /*pa， pb 和 pc 是工作指針 */pre=A;while(pa && pb && pc) /*當三表均不空時，查找共同元素 */ while(pa && pb)

32、if(pa->data<pb->data) /*處理 pa 結(jié)點，后移指針 */u=pa;pa=pa->next;free(u);else if(pa->data> pb->data)pb=pb->next;else if (pa && pb) /*處理A和B表元素值相等的結(jié)點*/ while(pc && pc->data<pa->data) pc=pc->next;if(pc)if(pc->data>pa->data) /*處理 pa 結(jié)點，后移指針 */u=pa;pa=

33、pa->next;free(u);elseif(pre=A) /*結(jié)果表中第一個結(jié)點 */ pre->next=pa;pre=pa;pa=pa->nextelse if(pre->data=pa->data) /*重復結(jié)點不鏈入 A 表 */u=pa;pa=pa->next;free(u);elsepre->next=pa;pre=pa;pa=pa->next;/*將新結(jié)點鏈入 A 表 */pb=pb->next;pc=pc->next; /*鏈表的工作指針后移 */elseif(pa=NULL)pre->next=NULL; /* 若 A 表已結(jié)束，置 A 表表尾 *