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

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

）。A．p=p->next;

B．p->next=p->next->nextC．p=p->next->next;

D．p->next=p;26、在一種單鏈表HL中，若要在指針q所指結(jié)點(diǎn)的背面插入一種由指針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)造一種空的線性表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.沒(méi)有共同點(diǎn)2、一種棧的進(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.有多個(gè)可能4、判斷下面的說(shuō)法與否對(duì)的（1）插入和刪除操作比較簡(jiǎn)樸，是鏈?zhǔn)綏：玩準(zhǔn)疥?duì)列的優(yōu)點(diǎn)之一。X（2）堆棧允許刪除的一端稱為棧頂，而棧底元素是不能刪除的。X5、設(shè)有一種次序棧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的共用存儲(chǔ)空間，且僅當(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、鑒定一種次序棧st（最多元素為Maxsize）為空的條件為（B），判斷棧滿的條件為(D).A.st.top!=-1B.st.top==0C.st.top!=MaxsizeD.st.top==Maxsize8、循環(huán)次序隊(duì)列中與否能夠插入下一種元素，（A）A.與隊(duì)頭指針和隊(duì)尾指針的值有關(guān)B.只與隊(duì)尾指針的值有關(guān)，與隊(duì)頭指針的值無(wú)關(guān)C.只與數(shù)組的大小有關(guān)，與隊(duì)首頭指針和隊(duì)尾指針的值無(wú)關(guān)D.與曾經(jīng)進(jìn)行過(guò)多少次插入操作有關(guān)9、若用一種大小為6的一維數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且現(xiàn)在rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除1個(gè)元素，然后再插入2個(gè)新元素后，rear和front的值分別為（B）。A.1和5B.2和4C.4和2D.5和110、用單鏈表表達(dá)隊(duì)列時(shí)，隊(duì)頭應(yīng)當(dāng)在單鏈表的（A）位置。A.鏈頭B.鏈尾C.鏈中D.任意11、堆棧和隊(duì)列的共同之處在于它們含有相似的（A）。A.邏輯特性B.物理特性C.運(yùn)算辦法D.元素類型12、堆棧和隊(duì)列都是特殊的線性表，其特殊性在于（C）。A.它們含有普通線性表所沒(méi)有的邏輯特性B.它們的存儲(chǔ)構(gòu)造特殊C.對(duì)它們的使用辦法做了限制D.它們比普通線性表更簡(jiǎn)樸13、若5個(gè)元素的出棧序列為1，2，3，4，5，則進(jìn)棧序列可能是（D）。A.24315B.23154C.31425D.14、若堆棧采用次序存儲(chǔ)構(gòu)造，正常狀況下，向堆棧中插入一種元素，棧頂指針top的變化是（D）A.不變B.top=0C.top--D.top++15、若堆棧采用次序存儲(chǔ)構(gòu)造，正常狀況下，刪除堆棧中一種元素，棧頂指針top的變化是（C）A.不變B.top=0C.top--D.top++16、若隊(duì)列采用次序存儲(chǔ)構(gòu)造，元素的排列次序（B）。A.與元素的值的大小有關(guān)B.由元素進(jìn)入隊(duì)列的先后次序決定C.與隊(duì)頭指針和隊(duì)尾指針的取值有關(guān)D.與作為次序存儲(chǔ)構(gòu)造的數(shù)組的大小有關(guān)17、“鏈接隊(duì)列”這一概念不涉及（B）。A.數(shù)據(jù)的存儲(chǔ)構(gòu)造B.數(shù)據(jù)的邏輯構(gòu)造C.對(duì)數(shù)據(jù)進(jìn)行的操作D.鏈表的種類18、若堆棧采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造，棧頂指針為top，向堆棧插入一種由p所指的新結(jié)點(diǎn)的過(guò)程是依次執(zhí)行（C）,top=pA.p=topB.top=pC.p->next=topD.top->next=p19、若非空堆棧采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造，棧頂指針為top，刪除堆棧一種元素的過(guò)程是依次執(zhí)行p=top；（B）;free(p)A.top=pB.top=p->nextC.p=top->nextD.p=p-next20、若隊(duì)列采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造，隊(duì)頭元素指針與隊(duì)尾元素指針?lè)謩e為front和rear，向隊(duì)列中插入一種由p所指的新結(jié)點(diǎn)的過(guò)程是依次執(zhí)行：（C）;rear=p;A.rear=pB.front=pC.rear->next=pD.front->next=p21、若非空隊(duì)列采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造，，隊(duì)頭元素指針與隊(duì)尾元素指針?lè)謩e為front和rear，刪除隊(duì)列的一種元素的過(guò)程是依次執(zhí)行：p=front;(D);free(p)A.rear=pB.rear=p->nextC.p->next=rearD.f