第頁(yè)數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)測(cè)試卷附答案1.設(shè)有5個(gè)元素的進(jìn)棧序列為a，b，e,d，e，其榆出序列是c，e，d，b，a，則該棧的容量至少是()A、1B、2C、3D、4【正確答案】：D2.在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入S結(jié)點(diǎn)，則執(zhí)行()。A、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->next=q;【正確答案】：C3.設(shè)棧的初始狀態(tài)為空，當(dāng)字符序列“n9_”作為棧的輸入時(shí)，輸出長(zhǎng)度為3且可用作C語(yǔ)言標(biāo)識(shí)符的序列有()A、4B、6C、3D、5【正確答案】：C4.如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則退棧操作時(shí)(A、必須判斷鏈棧是否滿B、判斷鏈棧元素的類型.C、必須判斷鏈棧是否空D、對(duì)鏈棧不做任何判斷【正確答案】：C5.數(shù)據(jù)的基本單位是()A、數(shù)據(jù)元素B、數(shù)據(jù)項(xiàng)C、數(shù)據(jù)類型D、數(shù)據(jù)變量【正確答案】：A6.關(guān)于線性表的正確說(shuō)法是()A、每個(gè)元素都有一個(gè)前驅(qū)元素和一個(gè)后繼元素B、線性表中至少有一個(gè)元素C、表中元素的排序順序必須是由小到大或由大到小D、除第一個(gè)元素和最后一個(gè)元素外，其余每個(gè)元素有且僅有一個(gè)直接前驅(qū)元素和一個(gè)直接后繼元素【正確答案】：D7.輸入序列為ABC，輸出序列為CBA時(shí)，經(jīng)過(guò)的棧操作為(A、push,pop,push,pop,push,popB、push,push,push,pop,pop,popC、push,push.pop,pop,push,popD、push,pop,push.push,pop.pop【正確答案】：B8.非空循環(huán)單鏈表的頭指針為head，則其尾指針p滿足()A、p->next==NULLB、p==NULLC、p->next==headD、p==head【正確答案】：C9.以下屬于順序表的優(yōu)點(diǎn)的是()。A、插入元素方便B、刪除元素方便C、存儲(chǔ)密度大D、以上都不對(duì)【正確答案】：C10.鏈棧與順序棧相比有一個(gè)明顯的優(yōu)點(diǎn)，即()A、插入操作更方便B、通常不會(huì)出現(xiàn)棧滿的情況C、總是不會(huì)出現(xiàn)棧空的情況D、刪除操作重方便【正確答案】：B11.在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度是A、0(1)。B、O(n)C、O(n2)D、0(nlogzn)【正確答案】：B12.算法在發(fā)生非法操作時(shí)可以做出處理的特性稱為算法的()A、正確性B、易讀性C、健壯性D、高效性【正確答案】：C13.非線性結(jié)構(gòu)中的每個(gè)結(jié)點(diǎn)(A、無(wú)直接前驅(qū)結(jié)點(diǎn)B、無(wú)直接后繼結(jié)點(diǎn)C、只有一個(gè)直接前驅(qū)結(jié)點(diǎn)和一個(gè)直接后繼結(jié)點(diǎn)D、可能有多個(gè)直接前驅(qū)結(jié)點(diǎn)和多個(gè)直接后繼結(jié)點(diǎn)【正確答案】：D14.數(shù)據(jù)結(jié)構(gòu)通言研究數(shù)據(jù)的()及它們之間的相互聯(lián)系。A、存儲(chǔ)結(jié)構(gòu)和邏輯結(jié)構(gòu)B、存儲(chǔ)和抽象C、聯(lián)系和抽象D、聯(lián)系與邏輯【正確答案】：A15.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為()兩大類A、動(dòng)態(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)【正確答案】：C16.在一個(gè)雙鏈表中,在?p結(jié)點(diǎn)之后插入結(jié)點(diǎn)?q的操作是()A、q->prior=p;p->next=q;p->next->prior=q;q-next=p->next;B、q->next=p->next;p->next->prior=q;p->next=q;q->prior=p;C、p->next=q;q->prior=p;q->next=p->next;p->next->prior=q;D、p->next->prior=q;q->next=p->next;q->prior=p;p->next=q;【正確答案】：B17..若A是7×4的二維數(shù)組，按行優(yōu)先方式順序存儲(chǔ)，元素AFOTO]的存儲(chǔ)地址為1000，若每個(gè)元素占2個(gè)字節(jié)，則元素A[3[3]的存儲(chǔ)地址為()。A、1015B、1016C、1028D、1030【正確答案】：D18.將序列(2,12,16,88,5,10,34排序。若前2趟排序的結(jié)果如下：第1趟排序后：2,12,16,10,5,34,88第2趟排序后：2,5,10,12,16,34,88則可能的排序算法是：()。A、冒泡排序B、歸并排序C、插入排序D、快速排序【正確答案】：D19.不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是(）A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL【正確答案】：A20.設(shè)abcdef以所給的次序進(jìn)棧，若在進(jìn)棧操作時(shí)，允許連續(xù)進(jìn)棧操作，則下面得不到的序列為(A、fedcbaB、bcafedC、dcefbaD、cabdef【正確答案】：D21.一顆二又樹(shù)的先序遍歷為A.B.C.D,EF,中序遍歷為C,B,A,E,D.F則后序遍歷為()。A、C,B,E,F,D,AB、F,E,D,C,B,AC,B,E,D,F,AD、不確定【正確答案】：A22.向一個(gè)不帶頭結(jié)點(diǎn)的棧頂指針為lst的鏈棧中插入一個(gè)?s結(jié)點(diǎn)時(shí)，則執(zhí)行（）A、lst->next=s;B、s->next=lst->next;lst->next=s;C、s->next=lst;lst=sD、s->next=lst;lst=lst->next;【正確答案】：C23.若想存儲(chǔ)固定數(shù)量的數(shù)據(jù)元素，關(guān)于采用不同存儲(chǔ)方式的比較，下列說(shuō)法中正確的是()。A、順序存儲(chǔ)比鍵式存儲(chǔ)少占空間B、順序存儲(chǔ)比鏈?zhǔn)酱鎯?chǔ)多占空間C、順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)都要求占用整塊存儲(chǔ)空間D、鏈?zhǔn)交軆?chǔ)比順序存儲(chǔ)難于擴(kuò)充空間【正確答案】：A24.在長(zhǎng)度為n的()上，刪除第一個(gè)元素，其算法的時(shí)間復(fù)雜度為0(n)。A、只有表頭指針的不帶表頭結(jié)點(diǎn)的循環(huán)單鏈表B、只有表尾指針的不帶表頭結(jié)點(diǎn)的循環(huán)單鍵表C、只有表尾指針的帶表頭結(jié)點(diǎn)的循環(huán)單鏈表D、只有表頭指針的帶表頭結(jié)點(diǎn)的循環(huán)單鏈表【正確答案】：A25.將兩個(gè)各有n個(gè)元素的遞增有序順序表歸并成一個(gè)有序順序表，其最少的比較次數(shù)是()A、nB、2n-1C、2nD、n-1【正確答案】：A26.數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址和邏輯地址相同并且是連續(xù)的，稱為(A、存儲(chǔ)結(jié)構(gòu)B、邏輯結(jié)構(gòu)C、順序存儲(chǔ)結(jié)構(gòu)D、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)【正確答案】：C27.下面關(guān)于線性表的權(quán)述中，錯(cuò)誤的是()A、線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元B、線性表采用順序存儲(chǔ)，使于進(jìn)行插入和刪除操作C、線性表采用鍵式存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元D、線性表采用鍵式存儲(chǔ)，便于進(jìn)行插入和刪除操作【正確答案】：B28.以下各鏈表均不帶頭結(jié)點(diǎn),其中最不適合用作鏈棧的鏈表是()A、只有表頭指針沒(méi)有表尾指針的循環(huán)雙鏈表B、只有表尾指針沒(méi)有表頭指針的循環(huán)雙鏈表C、只有表尾指針沒(méi)有表頭指針的循環(huán)單鏈表D、只有表頭指針沒(méi)有表尾指針的循環(huán)單鏈表【正確答案】：D29.在一個(gè)長(zhǎng)度為n的單鏈表上，設(shè)有頭指針h和尾指針t，執(zhí)行()的時(shí)間復(fù)雜度與鏈表的長(zhǎng)度有關(guān)。A、刪除單鍵表中的第一個(gè)元素B、刪除單鏈表中的最后一個(gè)元素C、在單鍵表第一個(gè)元素前插入一個(gè)新元素D、在單鍵表最后一個(gè)元素后插入一個(gè)新元素【正確答案】：B30.在單鏈表中，增加一個(gè)頭結(jié)點(diǎn)的目的是().A、使單鏈表至少有一個(gè)結(jié)點(diǎn)B、標(biāo)識(shí)鏈表中重要結(jié)點(diǎn)的位置C、方便運(yùn)算的實(shí)現(xiàn)D、說(shuō)明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)【正確答案】：C31.下列關(guān)于棧的敘述中正確的是A、在棧中只能插入數(shù)據(jù)B、在棧中只能刪除數(shù)據(jù)C、棧是先進(jìn)先出的線性表D、棧是先進(jìn)后出的線性表【正確答案】：D32.以下關(guān)于單鏈表的敘述中，不正確的是()A、結(jié)點(diǎn)除自身信息外還包括指針城，因此存儲(chǔ)密度小于順序存儲(chǔ)結(jié)構(gòu)B、邏輯上相鄰的元素物理上不必相鄰C、可以通過(guò)頭結(jié)點(diǎn)直接計(jì)算第i個(gè)結(jié)點(diǎn)的存儲(chǔ)地址D、插入、刪除運(yùn)算操作方便，不必移動(dòng)結(jié)點(diǎn)【正確答案】：C33.一個(gè)棧的輸入序列為1，2,3，….，n，若輸出序列的第1個(gè)元素是n，則第i(1≤i≤n)個(gè)輸出的元素是（）A、不確定B、n-i+1C、iD、n-i【正確答案】：B34.設(shè)有兩個(gè)長(zhǎng)度為n的單鏈表，結(jié)點(diǎn)類型相同，若以hl為頭結(jié)點(diǎn)指針的單鏈表是非循環(huán)的，以h2為頭結(jié)點(diǎn)指針的單鏈表是循環(huán)的，則()。A、對(duì)于兩個(gè)鏈表來(lái)說(shuō)，刪除第一個(gè)結(jié)點(diǎn)的操作，其時(shí)間復(fù)雜度都是O(1)B、對(duì)于兩個(gè)鏈表來(lái)說(shuō)，刪除尾結(jié)點(diǎn)的操作，其時(shí)間復(fù)雜度都是0(n)C、循環(huán)鏈表要比非循環(huán)鏈表占用更多的內(nèi)存空間D、hl和h2是不同類型的變量【正確答案】：B35.棧適合在()中應(yīng)用。A、遞歸調(diào)用B、括號(hào)匹配的檢查C、表達(dá)式求值D、以上都對(duì)【正確答案】：D36.已知last指向單鏈表的尾結(jié)點(diǎn)，將s所指結(jié)點(diǎn)插入在表尾，正確的操作是()。A、s->next=s,last=s,last->next=NULL;B、last->next=s,s->next=NULL,last=s;C、s->next=NULL,last->next=s,s=last;D、s->next=last,last->next=NULL,last=s;【正確答案】：B37.一顆二又樹(shù)葉子結(jié)點(diǎn)有12個(gè)，度為1的結(jié)點(diǎn)有4個(gè)，則該二又樹(shù)共有()個(gè)結(jié)點(diǎn)。A、27B、28C、29D、30【正確答案】：A38.向一個(gè)棧頂指針為hs的帶頭結(jié)點(diǎn)的鏈棧中插入一個(gè)?s結(jié)點(diǎn)時(shí)，執(zhí)行（）A、hs->next=s;B、s->next=hs->next;hs->next=s;C、s->next=hs;hs=sD、s->next=hs;hs=hs->next;【正確答案】：B39.通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著()A、數(shù)據(jù)具有同一特點(diǎn)B、不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對(duì)應(yīng)數(shù)據(jù)項(xiàng)的類型要一致C、每個(gè)數(shù)據(jù)元素都一樣D、數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等【正確答案】：B40.算法的時(shí)間復(fù)雜度取決于()A、問(wèn)題的規(guī)模B、待處理數(shù)據(jù)的初態(tài)C、計(jì)算機(jī)的配置D、A和B【正確答案】：D41.一個(gè)棧的輸入序列為12345，則下列序列中不可能是棧的輸出序列的是(A、15432B、54132C、23145D、23415【正確答案】：B42..一棵完全二又樹(shù)上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是()。A、250B、500C、254D、501【正確答案】：D43.以下說(shuō)法正確的是()A、數(shù)據(jù)元素是數(shù)據(jù)的最小單位B、數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位C、數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項(xiàng)的集合D、一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)【正確答案】：D44.循環(huán)隊(duì)列的隊(duì)滿條件為()。A、(sq.rear+1)%maxsize==(sq.front+1)%maxsizeB、(sq.front+1)%-maxsize==sq.rearC、(sq.rear+1)%maxsize==sq.frontD、sq.rear==sq.Front【正確答案】：C1.當(dāng)棧中元素為n個(gè)時(shí)，進(jìn)棧操作發(fā)生數(shù)據(jù)上溢，則說(shuō)明棧的最大容量為_(kāi)______A、正確B、錯(cuò)誤【正確答案】：B2.刪除單鏈表L中某結(jié)點(diǎn)?p之前的一個(gè)結(jié)點(diǎn)，其時(shí)間復(fù)雜度為0(1)A、正確B、錯(cuò)誤【正確答案】：B3.棧是運(yùn)算受限制的線性表。A、正確B、錯(cuò)誤【正確答案】：A4.在單鏈表中，要?jiǎng)h除某一指定的結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)。A、正確B、錯(cuò)誤【正確答案】：A5.將十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)是棧的典型應(yīng)用之一。A、正確B、錯(cuò)誤【正確答案】：A6.健壯的算法不會(huì)因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。A、正確B、錯(cuò)誤【正確答案】：A7.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。A、正確B、錯(cuò)誤【正確答案】：B8.棧一定是順序存儲(chǔ)的線性結(jié)構(gòu)。鏈?zhǔn)酱鎯?chǔ)A、正確B、錯(cuò)誤【正確答案】：B9.若一個(gè)棧的輸入序列為:A，B，C，D，可以得到輸出序列:C，A，B，DA、正確B、錯(cuò)誤【正確答案】：B10.在棧空的情況下，不能做出棧操作，否則產(chǎn)生下溢。A、正確B、錯(cuò)誤【正確答案】：A11.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。A、正確B、錯(cuò)誤【正確答案】：B12.數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小單位A、正確B、錯(cuò)誤【正確答案】：A13.當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時(shí)，應(yīng)采用順序存儲(chǔ)結(jié)構(gòu)。A、正確B、錯(cuò)誤【正確答案】：A14.算法的優(yōu)劣與算法描述語(yǔ)言無(wú)關(guān)。A、正確B、錯(cuò)誤【正確答案】：A15.鏈棧與順序棧相比，其特點(diǎn)之一是通常不會(huì)出現(xiàn)棧滿的情況。A、正確B、錯(cuò)誤【正確答案】：A16.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各項(xiàng)露類之間的邏輯關(guān)系。A、正確B、錯(cuò)誤【正確答案】：B17.棧的特點(diǎn)是“后進(jìn)先出”。A、正確B、錯(cuò)誤【正確答案】：A填空題1.______是數(shù)據(jù)的最小單位是數(shù)據(jù)的基本單位。【正確答案】：數(shù)據(jù)項(xiàng)；數(shù)據(jù)元素2.在單鏈表中，在p所指結(jié)點(diǎn)之后插入s所指向結(jié)點(diǎn)，應(yīng)執(zhí)行s->next=_______和p->next=_____的操作。【正確答案】：p->next;S3.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L為空表的條件是____【正確答案】：L->next==L，L→prior==L4.對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知p所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是_____;在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜是______【正確答案】：O(1);O(n)5.下列的代碼是實(shí)現(xiàn)有序表二分（折半）查找的算法，請(qǐng)?jiān)诳瞻滋幪顚戇m當(dāng)內(nèi)容，使該程序功能完整。intbin_search(SqListL,ElemTypee){

intmid,low=0,high=L.length-1；

while(low<=high)

{

mid=__________________

if(e—L.elemfmid])

retunmid+1；

elseif(e<=L.elem[mid)

high=__________

else

low=___________

}

return-1；}

【正確答案】：low+(high–low)/2；mid-1；mid+1；6.在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)結(jié)構(gòu)的線性表中，當(dāng)向第i個(gè)元素(1≤i≤n+1)之前插入一個(gè)新元素時(shí)，需要從后向前一次后移_______個(gè)元素。【正確答案】：n-i+17.在順序棧中，當(dāng)棧頂指針top=0時(shí)，表示_____【正確答案】：空棧8.表達(dá)式ax(b+c)-d的后綴表達(dá)式是_____【正確答案】：abc+xd-三、9.對(duì)于雙鏈表，在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)時(shí)，需要修改_____個(gè)指針域;刪除其中某個(gè)結(jié)點(diǎn)時(shí)，需要修改____個(gè)指針域。【正確答案】：4；210.在長(zhǎng)度為n的順序表中插入一個(gè)元素的時(shí)間復(fù)雜度為_(kāi)____刪除一個(gè)元素的時(shí)間復(fù)雜度為_(kāi)______,查找特定值的元素的時(shí)間復(fù)雜度為_(kāi)_____【正確答案】：O(n);O(n);O(n)11.若在長(zhǎng)度為n的順序表第i個(gè)元素之前插入一個(gè)元素，則需要向后移動(dòng)的元素個(gè)數(shù)是______。【正確答案】：n-i+112.列代碼的功能是返回帶頭結(jié)點(diǎn)的單鏈表L的逆轉(zhuǎn)鏈表，請(qǐng)?jiān)诳瞻滋幪顚戇m當(dāng)內(nèi)容，使該程序功能完整。ListReverse(ListL){

PositionOld_head,New_head,Temp;

New_head=NULL;

Old_head=L->Next;

while(Old_head)

{

Temp