數(shù)據(jù)結(jié)構(gòu)習題集 線性表第1次更新20123

1、第2章 線性表一、 選擇題1. 表長為N 的順序表，當在任何位置上插入或刪除一個元素的概率相等時，插入一個元素所需移動元素的平均次數(shù)為（ e ），刪除一個元素需要移動的元素個數(shù)為（ a ）。【，】A. (N-1)/2 B. N C. N+1 D. N-1 E. N/2 F. (N+1)/2 G. (N-2)/22. 線性表是具有N 個（ ）的有限序列?！尽緼、表元素 B、字符 C、數(shù)據(jù)元素 D、數(shù)據(jù)項 E、信息3. “線性表的邏輯順序和物理順序總是一致的。”這個結(jié)論是（ ）。【】A、正確的 B、錯誤的 C、不一定，與具體結(jié)構(gòu)有關(guān)。4. 線性表采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址（

2、）?！?，】A、必須是連續(xù)的 B、部分地址必須是連續(xù)的 C、一定是不連續(xù)的 D、連續(xù)或不連續(xù)都可以。5. 帶頭結(jié)點的單鏈表為空的判定條件是（ ）。【】A、head=NULL B、head->next=NULL C、head->next=head D、head!=NULL6. 不帶頭結(jié)點的單鏈表head 為空的判定條件是（ ）?！尽緼、head=NULL B、head->next=NULLC、head->next=head D、head!=NULL7. 非空的循環(huán)單鏈表head 的尾結(jié)點P 滿足（ ）?！尽緼、P->NEXT=NULL B、p=NULL C、p->

3、;next=head D、p=head8. 在一個具有n 個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序的時間復雜度是（ ）。【，】A、O(1) B、O(n) C、O(n2) D、O(nlog2n)9. 在一個單鏈表中，若刪除P 所指結(jié)點的后繼結(jié)點，則執(zhí)行（ ）?！?，】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;10. 在一個單鏈表中，若在所指結(jié)點之后插入所指結(jié)點，則執(zhí)行（ ）。【，】A

4、、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;11. 在一個單鏈表中，已知q 是p 的前趨結(jié)點，若q 和p 之間插入結(jié)點s，則執(zhí)行（ ）?！尽緼、s->next=p->next;p->next=s; B、p->next=s->next;s->next=p; C、q->next=s;s->next=p; D、p->next=s;s->nex

5、t=q;12. 假設(shè)雙鏈表結(jié)點的類型如下：【，】typedef struct linknodeint data; /數(shù)據(jù)域struct linknode *llink; /指向前趨結(jié)點的指針域struct linknode *rlink; /指向后繼結(jié)點的指針域bnode;現(xiàn)將一個q 所指新結(jié)點作為非空雙向鏈表中的p 所指結(jié)點的前趨結(jié)點插入到該雙鏈表中，能正確完成此要求的語句段是（ ）。A、q->rlink=p;q->llink=p->llink;p->llink=q;p->llink->rlink=q;B、p->llink=q;q->rlink

6、=p;p->llink->rlink=q;q->llink=p->llinkC、q->llink=p->rlink;q->rlink=p;p->llink->rlink=q;p->llink=q;D、以上都不對13. 如上題結(jié)點結(jié)構(gòu)，如在此非空循環(huán)雙向鏈表的結(jié)點 p 之后插入結(jié)點s 的操作序列是（ ）。（多項選擇）【】A、p->rlink=s;s->llink=p;p->rlink->llink=s;s->rlink=p->rlink;B、p->rlink=s;p->rlink->

7、llink=s;s->llink=p;s->rlink=p->rlink;C、s->llink=p;s->rlink=p->rlink;p->rlink=s;p->rlink->llink=s;D、s->llink=p;s->rlink=p->rlink;p->rlink->llink=s;p->rlink=s;14. 在一個長度為n 的單鏈表上，設(shè)有頭和尾兩個指針，執(zhí)行（ ）操作與鏈表的長度有關(guān)。【，】A、刪除單鏈表中的第一個元素 B、刪除單鏈表中最后一個元素 C、在單鏈表第一個元素前插入一個新元素 D

8、、在單鏈表最后一個元素后插入一個新元素15. 線性結(jié)構(gòu)中的一個結(jié)點代表一個（ ）【】A、數(shù)據(jù)元素 B、數(shù)據(jù)項 C、數(shù)據(jù) D、數(shù)據(jù)結(jié)構(gòu)16. 非空線性表L=(a1,a2,ai,an)，下列說法正確的是（ ）【】A、每個元素都有一個直接前驅(qū)和直接后繼B、線性表中至少要有一個元素C、表中諸元素的排列順序必須是由小到大或由大到小的D、除第一個元素和最后一個元素外其余每個元素都有一個且僅有一個直接前驅(qū)和直接后繼17. 順序表是線性表的（ ）【，】A、鏈式存儲結(jié)構(gòu) B、順序存儲結(jié)構(gòu) C、索引存儲結(jié)構(gòu) D、散列存儲結(jié)構(gòu)18. 對于順序表，以下說法錯誤的是（ ）【，】A、順序表是用一維數(shù)組實現(xiàn)的線性表，數(shù)組的

9、下標可以看成是元素的絕對地址B、順序表的所有存儲結(jié)點按相應數(shù)據(jù)元素間的邏輯關(guān)系決定的次序依次排列C、順序表的特點是:邏輯結(jié)構(gòu)中相鄰的結(jié)點在存儲結(jié)構(gòu)中仍相鄰D、順序表的特點是:邏輯上相鄰的元素，存儲在物理位置也相鄰的單元中19. 對順序表上的插入、刪除算法的時間復雜性分析來說，通常以（ ）為標準操作?！尽緼、插入操作 B、結(jié)點移動 C、算術(shù)表達式 D、刪除操作20. 對于順序表的優(yōu)缺點，以下說法錯誤的是（ ）【】A、無需為表示結(jié)點間的邏輯關(guān)系而增加額外的存儲空間B、可以方便地隨機存取表中的任一結(jié)點C、插入和刪除運算較方便D、由于順序表要求占用連續(xù)的空間，存儲分配只能預先進行(靜態(tài)分配)21. 若

10、某線性表中最常用的操作是取第i 個元素和找第i 個元素的前趨元素，則采用（ ）存儲方式最節(jié)省時間。【】A、順序表 B、單鏈表 C、雙鏈表 D、單循環(huán)鏈表22. 循環(huán)鏈表主要優(yōu)點是（ ）【】A、不再需要頭指針了B、已知某個結(jié)點的位置后，能夠容易找到它的直接前趨C、在進行插入、刪除運算時，能更好地保證鏈表不斷開D、從表中任一結(jié)點出發(fā)都能掃描到整個鏈表23. 在線性表的下列存儲結(jié)構(gòu)中，讀取元素花費時間最少的是（ ）【，】A、單鏈表 B、雙鏈表 C、循環(huán)鏈表 D、順序表二、 填空題1. 在線性結(jié)構(gòu)中，第一個結(jié)點（ 沒有 ）前趨結(jié)點，其余每個結(jié)點有且只有（ 一個 ）個前趨結(jié)點?！尽?. 在順序表中插入或

11、刪除一個元素，需要平均移動（ 表中一半的 ）元素，具體移動的元素個數(shù)與（ 表長 ）有關(guān)?！尽?. 已知是無表頭結(jié)點的單鏈表，試從下列提供的答案中選擇合適的語句序列，分別實現(xiàn)：【，】（）表首插入結(jié)點的語句序列是（C）。（）表尾插入結(jié)點的語句序列是（ ）。、->next=S; 、P=L; 、L=S; 、P->next=S->next; 、S->next=P->next; 、S->next=L; 、S->next=NULL; 、while(P->next!=Q)p=p->next; 、while(P->next!=NULL)P=P->

12、next;4. 已知L 是帶表頭結(jié)點的非空單鏈表，試從下列提供的答案中選擇合適的語句序列。【，】（1）刪除首元結(jié)點的語句序列是（ H,G,B,I ） ,（2）刪除尾元結(jié)點的語句序列是（ H,F,D,B,J）A、P=P->next;B、P->next=P->next->next;C、while(P!=NULL) P=P->next;D、while(Q->next!=NULL)P=Q;Q=Q->next;E、while(P->next!=Q) P=P->next;F、Q=P; G、Q=P->next; H、P=L; I、L=L->n

13、ext;J、free(Q);5. 已知L 是帶表頭結(jié)點的非空單鏈表，且P 結(jié)點既不是首元結(jié)點，也不是尾元結(jié)點，試從下列提供的答案中選擇合適的語句序列?！尽浚?）刪除P 結(jié)點的直接后繼結(jié)點的語句序列是（ F,A,I ）, （2）刪除P 結(jié)點的直接前趨結(jié)點的語句序列是（ E,G,D,F,A,I ）A、P->next=P->next->next; B、P=P->Pnext->next;C、while(P->next!=Q)P=P->next;D、while(P->next->next!=Q)P=P->next; E、Q=P;F、Q=P-&g

14、t;next; G、P=L;H、L=L->next; I、free(Q);6. 已知結(jié)點編號，在各結(jié)點查找概率相等的情況下，從n 個結(jié)點的單鏈表中查找一個結(jié)點，平均要訪問（ N/2 ）個結(jié)點，從n 個結(jié)點的雙鏈表中查找一個結(jié)點，平均要訪問（ N/4 ）個結(jié)點?！?，?】7. 對于一個具有n 個結(jié)點的單鏈表，在已知p 所指結(jié)點后插入一個新結(jié)點的時間復雜度是（ O(1) ）；在值域為給定值的結(jié)點后插入一個新結(jié)點的時間復雜度是（ O(n) ）?！荆?. 單鏈表是（ 線性表 ）的鏈接存儲表示。【】9. 單鏈表中設(shè)置頭結(jié)點的作用是（插入和刪除元素時不必進行特殊處理 ）。【】10. 在單鏈表中，除首

15、元結(jié)點外，任一結(jié)點的存儲位置由（ 其前驅(qū)結(jié)點的鏈域 ）指示?！尽?1. 在非空雙向循環(huán)鏈表中，在結(jié)點q 的前面插入結(jié)點p 的過程如下：【】p->prior=q->prior; q->prior->next=p;p->next=q;(q->prior=p; );12. 在雙向鏈表中，每個結(jié)點有兩個指針域，一個指向（前驅(qū)結(jié)點 ），另一個指向（ 后繼結(jié)點 ）?！尽?3. 順序表中邏輯上相鄰的元素的物理位置（ 必定 ）相鄰。單鏈表中邏輯上相鄰的元素的物理位置（ 不一定 ）相鄰。【】14. 為了便于討論，有時將含n(n0)個結(jié)點的線性結(jié)構(gòu)表示成(a1，a2,an)，其

16、中每個ai 代表一個_結(jié)點_。a1 稱為_第一個_結(jié)點，an 稱為_最后_結(jié)點，i 稱為ai 在線性表中的_位置_。對任意一對相鄰結(jié)點ai、ai1(1i<n),ai稱為ai1 的直接_前驅(qū)結(jié)點_，ai1 稱為ai 的直接_后繼結(jié)點_。【】15. 線性結(jié)構(gòu)的基本特征是：若至少含有一個結(jié)點，則除起始結(jié)點沒有直接_前驅(qū)_外，其他結(jié)點有且僅有一個直接_前驅(qū)_；除終端結(jié)點沒有直接_后繼_外，其它結(jié)點有且僅有一個直接_后繼_.【】16. 所有結(jié)點按1對1的鄰接關(guān)系構(gòu)成的整體就是_線性_結(jié)構(gòu)。【】17. 線性表的邏輯結(jié)構(gòu)是_線性_結(jié)構(gòu)。其所含結(jié)點的個數(shù)稱為線性表的_長度_?！尽?8. 在單鏈表中，指針

17、p 所指結(jié)點為最后一個結(jié)點的條件是_p->next=NULL;_?！尽咳?判斷題1. 順序存儲的線性表可以隨機存取。【】對2. 順序存儲的線性表的插入和刪除操作不需要付出很大的代價，因為平均每次操作只有近一半的元素需要移動。【】錯3. 線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性，因此是屬于同一數(shù)據(jù)對象?！尽繉?. 在線性表的順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上不一定相鄰?！尽垮e5. 在線性表的鏈式存儲結(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰?！尽繉?. 在單鏈表中，可以從頭結(jié)點進行查找任何一個元素?！尽繉?. 線性表的鏈式存儲結(jié)構(gòu)優(yōu)于順序存

18、儲結(jié)構(gòu)?！尽垮e8. 在線性表的順序存儲結(jié)構(gòu)中，插入和刪除元素時，移動元素的個數(shù)與該元素的位置有關(guān)?！尽繉?. 在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此，單鏈表是隨機存取的存儲結(jié)構(gòu)。【】錯10. 順序存儲方式只能用于存儲線性結(jié)構(gòu)?！? 】錯四、 簡答題1. 若較頻繁地對一個線性表進行插入和刪除操作，該線性表宜采用哪種存儲結(jié)構(gòu)？為什么？【】采用鏈式存儲結(jié)構(gòu)，因為其復雜度為O（1）；2. 描述概念：頭指針、頭結(jié)點、首元結(jié)點的區(qū)別？【，】3. 設(shè) A 是一個線性表（a1a2an），采用順序存儲結(jié)構(gòu)，則在等概率的前提下，平均每插入一個元素需要移動的元素個數(shù)為多少？若元素插在ai 與ai

19、+1 之間（0<=I<=n-1）的概率為2(n-i)/(n(n+1)，則平均每插入一個元素所要移動的元素個數(shù)又是多少？【，】4. 為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好？【，】5. 雙鏈表和單循環(huán)鏈表中，若僅知道指針p 指向某個結(jié)點，不知道頭指針，能否將結(jié)點*p 從相應的鏈表中刪除？若可以，其時間復雜度各為多少？【】6. 下列算法的功能是什么？【，】LinkedList test1(LinkedList L)/L 是無頭結(jié)點的單鏈表ListNode *q,*p;if(L&&L->next)q=L ;L=L->next; p=L;while(p-&

20、gt;next) p=p->next;p->next=q;q->next=NULL;return L;7. 如果有n 個線性表同時共存，并且在處理過程中各表的長度會發(fā)生動態(tài)變化，線性表的總長度也會自動地改變。在此情況下，應選擇哪一種存儲結(jié)構(gòu)。為什么？【】8. 若線性表的總數(shù)基本穩(wěn)定，且很少進行插入刪除操作，但要求以最快的方式存取線性表的元素，應該用哪種存儲結(jié)構(gòu)。為什么？【】9. 設(shè)有多項式a(x)=9+8x+9x4+5x10 b(x)=-2x+22x7-5x10（1） 用單鏈表給出a(x)、b(x)的存儲表示；（2） 設(shè)c (x)=a(x)+b(x)，求得c(x)并用單鏈表給出其存儲表示。【，】五、 設(shè)計題1. 編寫一個函數(shù)將一個順序表A（有多個元素且任何元素不為0）分拆成兩個順序表，使A 中大于0的元素存放在B 中，小于0 的元素存放在C 中。【】2. 設(shè)順序表L 中的數(shù)據(jù)元素遞增有序。試寫一算法，將e插入到順序表的適當位置，插入后保持該表的有序性。【】3. A、B 為元素遞增有序排列的單鏈表（同一表中可能有相同元素），編寫算法另建一單鏈表C