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

第一章1.在數(shù)據(jù)結(jié)構(gòu)中,從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為(C)A.動態(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ù)結(jié)構(gòu)中,與所使用得計(jì)算機(jī)無關(guān)得就是(A)A、邏輯結(jié)構(gòu)B、存儲結(jié)構(gòu)C、邏輯與存儲結(jié)構(gòu)D、物理結(jié)構(gòu)3、下面程序得時(shí)間復(fù)雜度為____O(mn)_______。for(inti=1;i<=m;i++)for(intj=1;j<=n;j++)S+=i第二章線性表鏈表不具備得特點(diǎn)就是(A)A可以隨機(jī)訪問任一結(jié)點(diǎn)(順序)B插入刪除不需要移動元素C不必事先估計(jì)空間D所需空間與其長度成正比2、不帶頭結(jié)點(diǎn)得單鏈表head為空得判定條件為(A),帶頭結(jié)點(diǎn)得單鏈表head為空得判定條件為(B)Ahead==nullBhead->next==nullChead->next==headDhead!=null3、在線性表得下列存儲結(jié)構(gòu)中,讀取元素花費(fèi)時(shí)間最少得就是(D)A單鏈表B雙鏈表C循環(huán)鏈表D順序表4、對于只在表得首、尾兩端進(jìn)行手稿操作得線性表,宜采用得存儲結(jié)構(gòu)為(C)A順序表B用頭指針表示得單循環(huán)鏈表C用尾指針表示得單循環(huán)鏈表D單鏈表5、在一個(gè)具有n個(gè)結(jié)點(diǎn)得有序單鏈表中插入一個(gè)新得結(jié)點(diǎn),并保持鏈表元素仍然有序,則操作得時(shí)間復(fù)雜度為(D)AO(1)BO(log2n)CO(n2)DO(n)6、在一個(gè)長度為n(n>1)得單鏈表上,設(shè)有頭與尾兩個(gè)指針,執(zhí)行(B)操作與鏈表得長度有關(guān)A刪除單鏈表中第一個(gè)元素B刪除單鏈表中最后一個(gè)元素C在第一個(gè)元素之前插入一個(gè)新元素D在最后一個(gè)元素之后插入一個(gè)新元素7、與單鏈表相比,雙向鏈表得優(yōu)點(diǎn)之一就是(D)A插入刪除操作更簡單B可以進(jìn)行隨機(jī)訪問C可以省略表頭指針或表尾指針D順序訪問相鄰結(jié)點(diǎn)更容易8、若list就是某帶頭結(jié)點(diǎn)得循環(huán)鏈表得頭結(jié)點(diǎn)指針,則該鏈表最后那個(gè)鏈結(jié)點(diǎn)得指針域(頭結(jié)點(diǎn)得地址)中存放得就是(B)Alist得地址Blist得內(nèi)容Clist指得鏈結(jié)點(diǎn)得值D鏈表第一個(gè)鏈結(jié)點(diǎn)得地址9、若list1與list2分別為一個(gè)單鏈表與一個(gè)雙向鏈表得第一個(gè)結(jié)點(diǎn)得指針,則(B)Alist2比list1占用更多得存儲單元Blist1與list2占用相同得存儲單元Clist1與list2應(yīng)該就是相同類型得指針變量D雙向鏈表比單鏈表占用更多得存儲單元10、鏈表中得每個(gè)鏈結(jié)點(diǎn)占用得存儲空間不必連續(xù),這句話正確嗎？(不正確)11、某線性表采用順序存儲結(jié)構(gòu),元素長度為4,首地址為100,則下標(biāo)為12得(第13個(gè))元素得存儲地址為148。V100+4*12=14811、在順序表得(最后一個(gè)結(jié)點(diǎn)之后)插入一個(gè)新得數(shù)據(jù)元素不必移動任何元素。12、若對線性表進(jìn)行得操作主要不就是插入刪除,則該線性表宜采用(順序)存儲結(jié)構(gòu),若頻繁地對線性表進(jìn)行插入與刪除操作,則該線性表宜采用(鏈)存儲結(jié)構(gòu)。13、一個(gè)順序表所占用存儲空間得大小與(B)無關(guān)。A.表得長度B、元素得存放順序C、元素得類型D、元素中各得類型14、設(shè)存儲分配就是從低地址到高地址進(jìn)行得。若每個(gè)元素占用4個(gè)存儲單元,則某元素得地址就是指它所占用得單元得(A)。A、第1個(gè)單元得地址B、第2個(gè)單元得地址C、第3個(gè)單元得地址D、第4個(gè)單元得地址15、若線性表采用順序存儲結(jié)構(gòu),每個(gè)元素占用4個(gè)存儲單元,第1個(gè)元素得存儲地址為100,則第12個(gè)元素得存儲地址就是(B)。A、112B、144C16、若長度為n得線性表采用順序存儲結(jié)構(gòu),在表得第i個(gè)位置插入一個(gè)數(shù)據(jù)元素,i得合法值應(yīng)該就是(D)。A、i>0B、i<=nC、1<=i<=nD、1<=i<=n+117、若長度為n得非空線性表采用順序存儲結(jié)構(gòu),刪除表得第i個(gè)數(shù)據(jù)元素,i得合法值應(yīng)該就是(C)。A、i>0B、y<=nC、1<=i<=nD、d<=i<=i+118、若長度為n得非空線性表采用順序存儲結(jié)構(gòu),刪除表得第i個(gè)數(shù)據(jù)元素,首先需要移動表中(B)個(gè)數(shù)據(jù)元素。A、n-iB、n+iC、n-i+1D、n-i-119、若長度為n得非空線性表采用順序存儲結(jié)構(gòu),在表得第i個(gè)位置插入一個(gè)數(shù)據(jù)元素,首先需要移動表中(C)個(gè)數(shù)據(jù)元素。A、iB、n+iC、n-i+1D、n-i-120、若頻繁地對線性表進(jìn)行插入與刪除操作,該線性表應(yīng)該采用(C)存儲結(jié)構(gòu)。A、散列B、順序C、鏈?zhǔn)紻、索引21、鏈表中得每一個(gè)鏈結(jié)點(diǎn)所占用得存儲單元(B)。A、不必連續(xù)B、一定連續(xù)C、部分連續(xù)D、連續(xù)與否無所謂22、在一個(gè)具有n個(gè)鏈結(jié)點(diǎn)得線性鏈表中查找某一個(gè)鏈結(jié)點(diǎn),若查找成功,需要平均比較(C)個(gè)鏈結(jié)點(diǎn)。A、nB、n/2C、(n+1)/2D、(n-1)/223、給定具有n個(gè)元素得順序表,建立一個(gè)有序線性鏈表得時(shí)間復(fù)雜度為(C)。A、O(1)B、O(n)C、O(n2)D、O(log2n)24、在非空線性鏈表中由p所指得鏈結(jié)點(diǎn)后面插入一個(gè)由q所指得鏈結(jié)點(diǎn)得過程就是依次執(zhí)行(B)。A、q->next=p;p->next=q;B、q->next=p->next;p->next=q;C、q->next=p->next;p=q;D、p->next=q;q->next=p;25、若刪除非空線性鏈表中由p所指得鏈結(jié)點(diǎn)得直接后繼鏈結(jié)點(diǎn)得過程過程就是依次執(zhí)行(B)。A、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);26、在非空雙向循環(huán)鏈表中由q所指得鏈結(jié)點(diǎn)后面插入一個(gè)由p所指得鏈結(jié)點(diǎn)得操作依次為p->prior=q;p->next=q->next;q->next=p;(C)。A、q->prior=pB、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->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ù)為(D)。A、nB、n/2C、n+1D、(n+1)/229、在長度為n得順序表得第i(1≤i≤n+1)個(gè)位置上插入一個(gè)元素,元素得移動次數(shù)就是(A)。A、n-i+1B、n-iC、iD、i-130、在線性表得下列存儲結(jié)構(gòu)中,讀取元素花費(fèi)時(shí)間最少得就是(D)。A、單鏈表B、雙鏈表C、循環(huán)鏈表D、順序表31、在以單鏈表為存儲結(jié)構(gòu)得線性表中,數(shù)據(jù)元素之間得邏輯關(guān)系用(C)。A、數(shù)據(jù)元素得相鄰地址表示B、數(shù)據(jù)元素在表中得序號表示C、指向后繼元素得指針表示D、數(shù)據(jù)元素得值表示25、假設(shè)指針p指向單鏈表中得某一結(jié)點(diǎn),若把p指針后面得結(jié)點(diǎn)刪除,只需修改下列哪個(gè)指針值即可(

)。

A.p=p->next;

B.p->next=p->next->next

C.p=p->next->next;

D.p->next=p;

26、在一個(gè)單鏈表HL中,若要在指針q所指結(jié)點(diǎn)得后面插入一個(gè)由指針P所指向得結(jié)點(diǎn),則執(zhí)行(

D

)。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)第三章1、棧與隊(duì)列得共同點(diǎn)就是(C)A、都就是先進(jìn)后出B、都就是先進(jìn)先出在C、只允許在端點(diǎn)處插入與刪除元素D、沒有共同點(diǎn)2、一個(gè)棧得進(jìn)棧順序就是a,b,c,d,e,則棧得出棧順序不可能就是(C)A、edcbaB、decbaC、dceabD、adcbe3、設(shè)n個(gè)元素得進(jìn)棧序列為1,2,3,……,n,出棧序列為p1,p2,p3,……,pn,若p1=n,則pi(1<=i<=n)得值為(C)。A、iB、n-iC、n-i+1D、有多種可能4、判斷下面得說法就是否正確(1)插入與刪除操作比較簡單,就是鏈?zhǔn)綏Ｅc鏈?zhǔn)疥?duì)列得優(yōu)點(diǎn)之一。X(2)堆棧允許刪除得一端稱為棧頂,而棧底元素就是不能刪除得。X5、設(shè)有一個(gè)順序棧S,元素s1,s2,s3,s4,s5,s6依次進(jìn)棧,如果6個(gè)元素得出棧順序?yàn)閟2,s3,s4,s6,s5,s1,則順序棧得容量至少應(yīng)為多少？6、若數(shù)組s[0、、n-1]為兩個(gè)棧,s1與s2得共用存儲空間,且僅當(dāng)s[0、、n-1]全滿時(shí),各棧才不能進(jìn)行進(jìn)棧操作,則為這兩個(gè)棧分配空間得最佳方案就是:s1與s2得棧頂指針得初值分別為(C)。A、1與n+1B、1與n/2C、-1與nD、-1與n+17、判定一個(gè)順序棧st(最多元素為Maxsize)為空得條件為(B),判斷棧滿得條件為(D)、A、st、top!=-1B、st、top==0C、st、top!=MaxsizeD、st、top==Maxsize8、循環(huán)順序隊(duì)列中就是否可以插入下一個(gè)元素,(A)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,當(dāng)從隊(duì)列中刪除1個(gè)元素,然后再插入2個(gè)新元素后,rear與front得值分別為(B)。A、1與5B、2與4C、4與2D、5與110、用單鏈表表示隊(duì)列時(shí),隊(duì)頭應(yīng)該在單鏈表得(A)位置。A、鏈頭B、鏈尾C、鏈中D、任意11、堆棧與隊(duì)列得共同之處在于它們具有相同得(A)。A、邏輯特性B、物理特性C、運(yùn)算方法D、元素類型12、堆棧與隊(duì)列都就是特殊得線性表,其特殊性在于(C)。A、它們具有一般線性表所沒有得邏輯特性B、它們得存儲結(jié)構(gòu)特殊C、對它們得使用方法做了限制D、它們比一般線性表更簡單13、若5個(gè)元素得出棧序列為1,2,3,4,5,則進(jìn)棧序列可能就是(D)。A、24315B、23154C、31425D、14、若堆棧采用順序存儲結(jié)構(gòu),正常情況下,向堆棧中插入一個(gè)元素,棧頂指針top得變化就是(D)A、不變B、top=0C、top--D、top++15、若堆棧采用順序存儲結(jié)構(gòu),正常情況下,刪除堆棧中一個(gè)元素,棧頂指針top得變化就是(C)A、不變B、top=0C、top--D、top++16、若隊(duì)列采用順序存儲結(jié)構(gòu),元素得排列順序(B)。A、與元素得值得大小有關(guān)B、由元素進(jìn)入隊(duì)列得先后順序決定C、與隊(duì)頭指針與隊(duì)尾指針得取值有關(guān)D、與作為順序存儲結(jié)構(gòu)得數(shù)組得大小有關(guān)17、“鏈接隊(duì)列”這一概念不涉及(B)。A、數(shù)據(jù)得存儲結(jié)構(gòu)B、數(shù)據(jù)得邏輯結(jié)構(gòu)C、對數(shù)據(jù)進(jìn)行得操作D、鏈表得種類18、若堆棧采用鏈?zhǔn)酱鎯Y(jié)構(gòu),棧頂指針為top,向堆棧插入一個(gè)由p所指得新結(jié)點(diǎn)得過程就是依次執(zhí)行(C),top=pA、p=topB、top=pC、p->next=topD、top->next=p19、若非空堆棧采用鏈?zhǔn)酱鎯Y(jié)構(gòu),棧頂指針為top,刪除堆棧一個(gè)元素得過程就是依次執(zhí)行p=top;(B);free(p)A、top=pB、top=p->nextC、p=top->nextD、p=p-next20、若隊(duì)列采用鏈?zhǔn)酱鎯Y(jié)構(gòu),隊(duì)頭元素指針與隊(duì)尾元素指針分別為front與rear,向隊(duì)列中插入一個(gè)由p所指得新結(jié)點(diǎn)得過程就是依次執(zhí)行:(C);rear=p;A、rear=pB、front=pC、rear->next=pD、front->next=p21、若非空隊(duì)列采用鏈?zhǔn)酱鎯Y(jié)構(gòu),,隊(duì)頭元素指針與隊(duì)尾元素指針分別為front與rear,刪除隊(duì)列得一個(gè)元素得過程就是依次執(zhí)行:p=front;(D);free(p)A、rear=pB、rear=p->nextC、p->next=rearD、fro