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

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

)。

A.p=p->next;

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

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

D.p->next=p;

26、在一個單鏈表HL中,若要在指針q所指結(jié)點得后面插入一個由指針P所指向得結(jié)點,則執(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)造一個空得線性表L用(

A

)A、InitList(&L)B、DestroyList(&L)

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