數(shù)據(jù)結(jié)構(gòu)習(xí)題及答案

1、第一章 1 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ C ）B. 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)A 動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu).線性結(jié)構(gòu)和非線性結(jié)構(gòu)D. C2.在數(shù)據(jù)結(jié)構(gòu)中（A ）, 與所使用的計(jì)算機(jī)無關(guān)的是邏輯和存儲結(jié)構(gòu)B. A.邏輯結(jié)構(gòu)存儲結(jié)構(gòu)D. 物理結(jié)構(gòu) C.3.下面程序的時(shí)間復(fù)雜度為 O （mn） 。 for （int i=1;i<=m; i+）for （int j=1; j<=n; j+ ）S+=i第二章線性表） A 鏈表不具備的特點(diǎn)是（插入刪除不需要移動元素 B（順序） A 可以隨機(jī)訪問任一結(jié)點(diǎn)所需空間與其長度成正比 C不必事先估計(jì)空間 Dhead 不帶頭結(jié)點(diǎn)的單鏈

2、表為空的判定條件為 （ A ） ， 帶頭結(jié)點(diǎn)的單鏈表 head 為空的判定2.） B 條件為（ A head=null B head ->next=null Chead ->next=head D head!=null） D3. 在線性表的下列存儲結(jié)構(gòu)中，讀取元素花費(fèi)時(shí)間最少的是（順序表D循環(huán)鏈表 A 單鏈表B 雙鏈表C 4. 對于只在表的首、尾兩端進(jìn)行手稿操作的線性表，宜采用的存儲結(jié)構(gòu)為(C)用頭指針表示的單循環(huán)鏈表用尾指針表示的單循環(huán)鏈表單鏈表C 順序表ABD5.在一個(gè)具有n 個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新的結(jié)點(diǎn)， 并保持鏈表元素仍然有序，則操作的時(shí)間復(fù)雜度為 ( D )2n)

3、 C O(n) D O(n)A O(1) B O(log 2(B)操作與鏈表的長 n (n>1)6.在一個(gè)長度為的單鏈表上， 設(shè)有頭和尾兩個(gè)指針， 執(zhí)行度有關(guān)刪除單鏈表中最后一個(gè)元素 BA 刪除單鏈表中第一個(gè)元素 C 在第一個(gè)元素之前插入一個(gè)新元素 D 在最后一個(gè)元素之后插入一個(gè)新元素 (D)7. 與單鏈表相比， 雙向鏈表的優(yōu)點(diǎn)之一是可以進(jìn)行隨機(jī)訪問 A 插入刪除操作更簡單 BC 可以省略表頭指針或表尾指針 D 順序訪問相鄰結(jié)點(diǎn)更容易是某帶頭結(jié)點(diǎn)的循環(huán)鏈表的頭結(jié)點(diǎn)指針， 則該鏈表最后那個(gè)鏈結(jié)點(diǎn)的指針域list8. 若 (頭結(jié)點(diǎn)的地址) 中存放的是( B )的地址B list 指的鏈結(jié)點(diǎn)的

4、值的內(nèi)容A list C listD鏈表第一個(gè)鏈結(jié)點(diǎn)的地址分別為一個(gè)單鏈表與一個(gè)雙向鏈表的第一個(gè)結(jié)點(diǎn)的指針，則若9.list1list2( B )和B list1A list2 與 list2 占用相同的存儲單元占用更多的存儲單元比list1 應(yīng)該是相同類型的指針變量list2 D 雙向鏈表比單鏈表占用更多的存儲單元 C list1 和 10.（不正確 ）鏈表中的每個(gè)鏈結(jié)點(diǎn)占用的存儲空間不必連續(xù)， 這句話正確嗎？11. 某線性表采用順序存儲結(jié)構(gòu)， 元素長度為 4， 首地址為 100 ，則下標(biāo)為 12 的（第 13 個(gè)） 100+4*12=148148 。元素的存儲地址為 V） 插入一個(gè)新的數(shù)據(jù)

5、元素不必移動任何元素。 11. 在順序表的 （最后一個(gè)結(jié)點(diǎn)之后 12. ）存儲結(jié)構(gòu)，若順序若對線性表進(jìn)行的操作主要不是插入刪除， 則該線性表宜采用 （頻繁地對線性表進(jìn)行插入和刪除操作，則該線性表宜采用存儲結(jié)構(gòu)。 ）鏈 （13、一個(gè)順序表所占用存儲空間的大小與（ B）無關(guān)。元素的類型 C.D.元素中各的類型A.表的長度B.元素的存放順序4個(gè)存儲單元，則某元素若每個(gè)元素占用 14 、設(shè)存儲分配是從低地址到高地址進(jìn)行的。的地址是指它所占用的單元的（ A ） 。 A. 第1 個(gè)單元的地址B. 第 2 個(gè)單元的地址第 4 第 3 個(gè)單元的地址D.個(gè)單元的地址C.15 、若線性表采用順序存儲結(jié)構(gòu)，每個(gè)元素

6、占用 4 個(gè)存儲單元，第 1 個(gè)元素的存儲地址為。 ， 則第 12 個(gè)元素的存儲地址是（ B ）100A. 112 B. 144C.148 D. 41216 、若長度為 n 的線性表采用順序存儲結(jié)構(gòu)，在表的第 i 個(gè)位置插入一個(gè)數(shù)據(jù)元素， i。 （ D ）的合法值應(yīng)該是A. i>0 B.i<=nC.1<=i<=n D. 1<=i<=n+1刪除表的第 i 個(gè)數(shù)據(jù)元素， i 的合法值應(yīng) 17 、若長度為 n 的非空線性表采用順序存儲結(jié)構(gòu)， 。 ）該是（ CA. i>0 B.y<=n C.1<=i<=n D. d<=i<=i+1

7、刪除表的第 i 個(gè)數(shù)據(jù)元素， 、若長度為 n 的非空線性表采用順序存儲結(jié)構(gòu)，首先需要18 ）個(gè)數(shù)據(jù)元素。移動表中（ BA. n-i B.n+i C. n-i+1 D. n-i-1在表的第i19、若長度為n的非空線性表采用順序存儲結(jié)構(gòu)，個(gè)位置插入一個(gè)數(shù)據(jù)元素， 首） 個(gè)數(shù)據(jù)元素。 先需要移動表中 （ CA. i B. n+i C.n-i+1D.n-i-1C 、若頻繁地對線性表進(jìn)行插入和刪除操作，該線性表應(yīng)該采用（）存儲結(jié)構(gòu)。 20 索引散列 B.鏈?zhǔn)紻.順序C.A. 、鏈表中的每一個(gè)鏈結(jié)點(diǎn)所占用的存儲單元（ 21 B ） 。連續(xù)與否無所謂部分連續(xù) D.B.A.不必連續(xù)一定連續(xù)C.若查找成功，需要

8、平均比22、在一個(gè)具有n 個(gè)鏈結(jié)點(diǎn)的線性鏈表中查找某一個(gè)鏈結(jié)點(diǎn)， 較（ C ）個(gè)鏈結(jié)點(diǎn)。 A. n B. n/2C.（n+1）/2 D. （n-1）/223 、 給定具有 n 個(gè)元素的順序表， 建立一個(gè)有序線性鏈表的時(shí)間復(fù)雜度為（ C ） 。 2） D. O（logn）A. O(1) B.O(n) C.O(n 2q 所指的鏈結(jié)點(diǎn)的過程是依次執(zhí)行p 所指的鏈結(jié)點(diǎn)后面插入一個(gè)由、 24 在非空線性鏈表中由。 )( BA. q ->next=p; p ->next=q; B. q ->next=p ->next;p->next=q;C. q ->next=p -&

9、gt;next; p =q; D. p->next=q; q ->next=p;p 所指的鏈結(jié)點(diǎn)的直接后繼鏈結(jié)點(diǎn)的過程過程是依次執(zhí)行25 、 若刪除非空線性鏈表中由。 ) ( BA. r=p->next; p->next=r;free(r);B. r=p ->next;p->next=r ->next;free(r);C. r=p->next;p->next=r ->next;free(p);D. p->next=p ->next ->next; free(p);pq 在非空雙向循環(huán)鏈表中由、所指的鏈結(jié)點(diǎn)后面插入一個(gè)

10、由所指的鏈結(jié)點(diǎn)的操作依次為 26p->prior=q;p->next=q ->next;q ->next=p; () C 。 A. q->prior=p B.q->next->prior=pC. p ->next ->prior=p; D. p->prior->next=p;27 、 在非空雙向循環(huán)鏈表中由 q 所指的鏈結(jié)點(diǎn)前面插入一個(gè)由 p所指的鏈結(jié)點(diǎn)的操作依次為 p->next=q;p->prior=q ->prior;q ->prior=p; 。 ( D ) A.q->next=p;B. q-

11、>prior->next=p;C. p ->next ->prior=p; D. p ->prior ->next=p;28、順序存儲的線性表(a1,a2,an), 在任一結(jié)點(diǎn)前插入一個(gè)新結(jié)點(diǎn)時(shí)所需移動結(jié)點(diǎn)的平。 ）均次數(shù)為（ DA. n B. n/2 C. n+1 D. （n+1）/2（1<i<n+1i） 29、在長度為n的順序表的第個(gè)位置上插入一個(gè)元素，元素的移動次數(shù)是（ A ）。 A. n-i+1 B. n-i C. iD. i-130 、在線性表的下列存儲結(jié)構(gòu)中，讀取元素花費(fèi)時(shí)間最少的是（ D ） 。順序表D.單鏈表B.雙鏈表C.循環(huán)鏈表

12、 A.、 在以單鏈表為存儲結(jié)構(gòu)的線性表中， 數(shù)據(jù)元素之間的邏輯關(guān)系用 （ 31 C ） 。 數(shù)據(jù)元素在表中的序號表示B. 數(shù)據(jù)元素的相鄰地址表示A.數(shù)據(jù)元素的值表示D.C. 指向后繼元素的指針表示25 、 假設(shè)指針 p 指向單鏈表中的某一結(jié)點(diǎn)， 若把 p 指針后面的結(jié)點(diǎn)刪除，只需修改下列哪個(gè)。 指針值即可（） B p->next=p ->next->next A p=p ->next;D p->next=p;C p=p ->next ->next;q 所指結(jié)點(diǎn)的后面插入一個(gè)由指針 P 中，若要在指針26 、在一個(gè)單鏈表HL所指向的結(jié)。點(diǎn)，則執(zhí)行（D ）

13、A. q->next = p->next ； p->next = qB. p->next =q->next ； q = p； C. q->next =p->next; p->next =q； D. p->next =q->next ; q->next = p； 27、構(gòu)造個(gè)空的線 性表 L 用( A) A.InitList(&L)B.DestroyList (&L)C.ListEmpty(L)D.ClearList(&L)第三章) 、棧和隊(duì)列的共同點(diǎn)是( C 1 都是先進(jìn)先出在A.都是先進(jìn)后出只允許在端點(diǎn)

14、處插入和刪除元素 B. C.沒有共同點(diǎn) D.) ，則棧的出棧順序不可能是( a,b,c,d,e2 、一個(gè)棧的進(jìn)棧順序是CD. adcbe A. edcba B.decbaC. dceab3、設(shè) n 個(gè)元素的進(jìn)棧序列為，則，若, ，出棧序列為1,2,3,np1,p2,p3,pnp1=n 的值為 ( C ) 。 pi(1<=i<=n)A. i B.n-i C.n-i+1 D. 有多種可能、 判斷下面的說法是否正確 4 X ( 1 )插入和刪除操作比較簡單，是鏈?zhǔn)綏：玩準(zhǔn)疥?duì)列的優(yōu)點(diǎn)之一。 ) 堆棧允許刪除的一端稱為棧頂， 而棧底元素是不能刪除的。2 ( X 5、設(shè)有一個(gè)順序棧 S,元素s

15、1,s2,s3,s4,s5,s6依次進(jìn)棧，如果6 個(gè)元素的出棧順序?yàn)?s2,s3,s4,s6,s5,s1 ，則順序棧的容量至少應(yīng)為多少？ 6、 若數(shù)組 s0.n -1為兩個(gè)棧，s1s0.n -1全滿時(shí)， 各棧才不和 s2 的共用存儲空間，且僅當(dāng)能進(jìn)行進(jìn)棧操作，則為這兩個(gè)棧分配空間的最佳方案是： s1 和 s2 的棧頂指針的初值分別為。 C ） （ n+1和和 A. 1 和 n+1 B. 1 和 n/2 C. -1n D. -1 ，判斷棧滿的條件為） （D ）.7、判定一個(gè)順序棧 Maxsize （最多元素為st）為空的條件為（BA. st.top!= -1 B. st.top=0 C.st.t

16、op!=MaxsizeD.st.top=Maxsize8 （ A ） 、循環(huán)順序隊(duì)列中是否可以插入下一個(gè)元素， A. 與隊(duì)頭指針和隊(duì)尾指針的值有關(guān)B. 只與隊(duì)尾指針的值有關(guān)，與隊(duì)頭指針的值無關(guān)C. 只與數(shù)組的大小有關(guān)，與隊(duì)首頭指針和隊(duì)尾指針的值無關(guān) D. 與曾經(jīng)進(jìn)行過多少次插入操作有關(guān) 9 、若用一個(gè)大小為 6 的一維數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列， 且當(dāng)前 rear 和 front 的值分別為 0 和 3 ， 1 個(gè)元素，然后再插入2 個(gè)新元素后， rear 和 front的值分別為（ B 當(dāng)從隊(duì)列中刪除） 。 12 D. 55 B. 2和和和 4 C. 4 和 A. 110A ）位置。 、用單鏈表表示

17、隊(duì)列時(shí)，隊(duì)頭應(yīng)該在單鏈表的（鏈尾C.鏈頭 B.任意鏈中 D.A.11） A。、堆棧和隊(duì)列的共同之處在于它們具有相同的（ A.邏輯特性 B.物理特性C.運(yùn)算方法D.元素類型、堆棧和隊(duì)列都是特殊的線性表，其特殊性在于（。） 12C它們具有一般線性表所沒有的邏輯特性 A.它們的存儲結(jié)構(gòu)特殊 B.對它們的使用方法做了限制C.它們比一般線性表更簡單 D.1 ， 2， 3， 4， 513、若 5 個(gè)元素的出棧序列為，則進(jìn)棧序列可能是（ D ）。 A.24315B.23154 C. 31425 D. 3125414 、 若堆棧采用順序存儲結(jié)構(gòu)， 正常情況下， 向堆棧中插入一個(gè)元素， 棧頂指針 top 的變化

18、是 （D ）A. 不變 B. top=0 C.top -D. top+15 、 若堆棧采用順序存儲結(jié)構(gòu)， 正常情況下， 刪除堆棧中一個(gè)元素， 棧頂指針 top 的變化是） C （ B. top=0 C.top - D.top+A. 不變。 B ） 16 、若隊(duì)列采用順序存儲結(jié)構(gòu)，元素的排列順序 （由元素進(jìn)入隊(duì)列的先后順序決定與元素的值的大小有關(guān)B.A.與作為順序存儲結(jié)構(gòu)的數(shù)組的大小有關(guān) D. 與隊(duì)頭指針和隊(duì)尾指針的取值有關(guān)C.“鏈接隊(duì)列” 這一概念不涉及（ B ） 。 、 17 數(shù)據(jù)的邏輯結(jié)構(gòu)C.對數(shù)據(jù)進(jìn)行的操作D.鏈表的種類B.A.數(shù)據(jù)的存儲結(jié)構(gòu)18,向堆棧插入一個(gè)由 topp 、若堆棧采用

19、鏈?zhǔn)酱鎯Y(jié)構(gòu)，棧頂指針為所指的新結(jié)點(diǎn)的過程C )是依次執(zhí)行( ,top=pA. p=top B. top=p C. p->next=top D.top->next=p19 、 若非空堆棧采用鏈?zhǔn)酱鎯Y(jié)構(gòu)， 棧頂指針為， 刪除堆棧一個(gè)元素的過程是依次執(zhí)行topfree(p)B ； p= top () ;A.top=p B. top=p ->next C. p=top ->next D. p=p -next20 、 若隊(duì)列采用鏈?zhǔn)酱鎯Y(jié)構(gòu)， 隊(duì)頭元素指針與隊(duì)尾元素指針分別為 front 和 rear ，向隊(duì)列 ;rear=p;C ) 中插入一個(gè)由 p 所指的新結(jié)點(diǎn)的過程是依次執(zhí)行： ( A. rear=pB. front=p C. rear ->next=p D. front ->next=p21 、若非空隊(duì)列采用鏈?zhǔn)酱鎯Y(jié)構(gòu)， ，隊(duì)頭元素指針與隊(duì)尾元素指針分別為front 和 rear ，刪 free(p) ( D ); 除隊(duì)列的一個(gè)元素的過程是依次執(zhí)行： p=