第1-3章復(fù)習(xí)題及參考答案

第1_3章復(fù)習(xí)題及參考答案第1_3章復(fù)習(xí)題及參考答案第1_3章復(fù)習(xí)題及參考答案V:1.0精細(xì)整理，僅供參考第1_3章復(fù)習(xí)題及參考答案日期：20xx年X月第1-3章復(fù)習(xí)題《數(shù)據(jù)結(jié)構(gòu)與算法》復(fù)習(xí)題一、選擇題。1．在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為C。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)2．?dāng)?shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指A。A．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)B．?dāng)?shù)據(jù)結(jié)構(gòu)C．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)D．?dāng)?shù)據(jù)元素之間的關(guān)系3．在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的A結(jié)構(gòu)。A．邏輯B．存儲(chǔ)C．邏輯和存儲(chǔ)D．物理4．在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ)C。A．?dāng)?shù)據(jù)的處理方法B．?dāng)?shù)據(jù)元素的類型C．?dāng)?shù)據(jù)元素之間的關(guān)系D．?dāng)?shù)據(jù)的存儲(chǔ)方法5．在決定選取何種存儲(chǔ)結(jié)構(gòu)時(shí)，一般不考慮A。A．各結(jié)點(diǎn)的值如何B．結(jié)點(diǎn)個(gè)數(shù)的多少C．對(duì)數(shù)據(jù)有哪些運(yùn)算D．所用的編程語(yǔ)言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便。6．以下說(shuō)法正確的是D。A．?dāng)?shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位B．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位C．?dāng)?shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)項(xiàng)的集合D．一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)7．算法分析的目的是C，算法分析的兩個(gè)主要方面是A。（1）A．找出數(shù)據(jù)結(jié)構(gòu)的合理性B．研究算法中的輸入和輸出的關(guān)系C．分析算法的效率以求改進(jìn)C．分析算法的易讀性和文檔性（2）A．空間復(fù)雜度和時(shí)間復(fù)雜度B．正確性和簡(jiǎn)明性C．可讀性和文檔性D．?dāng)?shù)據(jù)復(fù)雜性和程序復(fù)雜性8．下面程序段的時(shí)間復(fù)雜度是O(n2)。 s=0;for(I=0;i<n;i++) for(j=0;j<n;j++) s+=B[i][j];sum=s;9．下面程序段的時(shí)間復(fù)雜度是O(n*m)。for(i=0;i<n;i++) for(j=0;j<m;j++) A[i][j]＝0;10．下面程序段的時(shí)間復(fù)雜度是O(log3n)。i＝0；while（i<=n） i=i*3；11．在以下的敘述中，正確的是B。A．線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu)B．二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C．棧的操作方式是先進(jìn)先出D．隊(duì)列的操作方式是先進(jìn)后出12．通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著B(niǎo)。A．?dāng)?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．?dāng)?shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等13．鏈表不具備的特點(diǎn)是A。A．可隨機(jī)訪問(wèn)任一結(jié)點(diǎn)B．插入刪除不需要移動(dòng)元素C．不必事先估計(jì)存儲(chǔ)空間D．所需空間與其長(zhǎng)度成正比14．不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是A。A．head==NULLBhead->next==NULLC．head->next==headDhead!=NULL15．帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是B。A．head==NULLBhead->next==NULLC．head->next==headDhead!=NULL16．若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)，則采用D存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A．單鏈表B．給出表頭指針的單循環(huán)鏈表C．雙鏈表D．帶頭結(jié)點(diǎn)的雙循環(huán)鏈表17．需要分配較大空間，插入和刪除不需要移動(dòng)元素的線性表，其存儲(chǔ)結(jié)構(gòu)是B。A．單鏈表B．靜態(tài)鏈表C．線性鏈表D．順序存儲(chǔ)結(jié)構(gòu)18．非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿足C。A．p->next==NULLB．p==NULLC．p->next==headD．p==head19．在循環(huán)雙鏈表的p所指的結(jié)點(diǎn)之前插入s所指結(jié)點(diǎn)的操作是D。A．p->prior=s；s->next=p；p->prior->next=s；s->prior=p->priorB．p->prior=s；p->prior->next=s；s->next=p；s->prior=p->priorC．s->next=p；s->prior=p->prior；p->prior=s；p->prior->next=sD．s->next=p；s->prior=p->prior；p->prior->next=s；p->prior=s20．如果最常用的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用D存儲(chǔ)方式最節(jié)省時(shí)間。A．單鏈表B．雙鏈表C．單循環(huán)鏈表D．順序表21．在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然保持有序的時(shí)間復(fù)雜度是B。A．O（1）B．O（n）C．O（n2）D．O（nlog2n）22．在一個(gè)長(zhǎng)度為n（n>1）的單鏈表上，設(shè)有頭和尾兩個(gè)指針，執(zhí)行B操作與鏈表的長(zhǎng)度有關(guān)。A．刪除單鏈表中的第一個(gè)元素B．刪除單鏈表中的最后一個(gè)元素C．在單鏈表第一個(gè)元素前插入一個(gè)新元素D．在單鏈表最后一個(gè)元素后插入一個(gè)新元素23．與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是D。A．插入、刪除操作更簡(jiǎn)單B．可以進(jìn)行隨機(jī)訪問(wèn)C．可以省略表頭指針或表尾指針D．順序訪問(wèn)相鄰結(jié)點(diǎn)更靈活24．如果對(duì)線性表的操作只有兩種，即刪除第一個(gè)元素，在最后一個(gè)元素的后面插入新元素，則最好使用B。A．只有表頭指針沒(méi)有表尾指針的循環(huán)單鏈表B．只有表尾指針沒(méi)有表頭指針的循環(huán)單鏈表C．非循環(huán)雙鏈表D．循環(huán)雙鏈表25．在長(zhǎng)度為n的順序表的第i個(gè)位置上插入一個(gè)元素（1≤i≤n+1），元素的移動(dòng)次數(shù)為：A。A．n–i+1B．n–iC．iD．i–126．對(duì)于只在表的首、尾兩端進(jìn)行插入操作的線性表，宜采用的存儲(chǔ)結(jié)構(gòu)為C。A．順序表B．用頭指針表示的循環(huán)單鏈表C．用尾指針表示的循環(huán)單鏈表D．單鏈表27．下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)C。A插入運(yùn)算方便B可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示C存儲(chǔ)密度大D刪除運(yùn)算方便28．下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)B。A線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元B線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。C線性表采用鏈?zhǔn)酱鎯?chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元D線性表采用鏈?zhǔn)酱鎯?chǔ)，便于進(jìn)行插入和刪除操作。29．線性表是具有n個(gè)B的有限序列。A．字符B．?dāng)?shù)據(jù)元素C．?dāng)?shù)據(jù)項(xiàng)D．表元素30．在n個(gè)結(jié)點(diǎn)的線性表的數(shù)組實(shí)現(xiàn)中，算法的時(shí)間復(fù)雜度是O（1）的操作是A。A．訪問(wèn)第i（1<=i<=n）個(gè)結(jié)點(diǎn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（1<i<=n）B．在第i（1<=i<=n）個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)C．刪除第i（1<=i<=n）個(gè)結(jié)點(diǎn)D．以上都不對(duì)31．若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為C。A．O(0)B．O(1)C．O(n)D．O(n2)32．對(duì)于順序存儲(chǔ)的線性表，訪問(wèn)結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為C。A．O(n)O(n)B．O(n)O(1)C．O(1)O(n)D．O(1)O(1)33．線性表（a1,a2,…,an）以鏈?zhǔn)椒绞酱鎯?chǔ)，訪問(wèn)第i位置元素的時(shí)間復(fù)雜度為C。A．O(0)B．O(1)C．O(n)D．O(n2)34．單鏈表中，增加一個(gè)頭結(jié)點(diǎn)的目的是為了C。A．使單鏈表至少有一個(gè)結(jié)點(diǎn) B．標(biāo)識(shí)表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置C．方面運(yùn)算的實(shí)現(xiàn)D．說(shuō)明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)35．在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是B。A．p->next=s；s->next=p->nextB．s->next=p->next；p->next=s;C．p->next=s；p->next=s->nextD．p->next=s->next；p->next=s36．線性表的順序存儲(chǔ)結(jié)構(gòu)是一種A。A．隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)B．順序存取的存儲(chǔ)結(jié)構(gòu)C．索引存取的存儲(chǔ)結(jié)構(gòu)D．Hash存取的存儲(chǔ)結(jié)構(gòu)37．棧的特點(diǎn)是B，隊(duì)列的特點(diǎn)是A。A．先進(jìn)先出B．先進(jìn)后出38．棧和隊(duì)列的共同點(diǎn)是C。A．都是先進(jìn)后出B．都是先進(jìn)先出C．只允許在端點(diǎn)處插入和刪除元素D．沒(méi)有共同點(diǎn)39．一個(gè)棧的進(jìn)棧序列是a，b，c，d，e，則棧的不可能的輸出序列是C。A．edcbaB．decbaC．dceabD．a(chǎn)bcde40．設(shè)有一個(gè)棧，元素依次進(jìn)棧的順序?yàn)锳、B、C、D、E。下列C是不可能的出棧序列。A．A,B,C,D,EB．B,C,D,E,AC．E,A,B,C,DD．E,D,C,B,A41．以下B不是隊(duì)列的基本運(yùn)算A．從隊(duì)尾插入一個(gè)新元素B．從隊(duì)列中刪除第i個(gè)元素C．判斷一個(gè)隊(duì)列是否為空D．讀取隊(duì)頭元素的值42．若已知一個(gè)棧的進(jìn)棧序列是1，2，3，，n，其輸出序列為p1，p2，p3，…，pn，若p1＝n，則pi為C。A．iB．n－iC．n－i＋1D．不確定43．判定一個(gè)順序棧st（最多元素為MaxSize）為空的條件是B。A．st->top!=-1B．st->top==-1C．st->top!=MaxSizeD．st->top==MaxSize44．判定一個(gè)順序棧st（最多元素為MaxSize）為滿的條件是D。A．st->top!=-1B．st->top==-1C．st->top!=MaxSizeD．st->top==MaxSize45．一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4，則隊(duì)列的輸出序列是B。A．4，3，2，1B．1，2，3，4C．1，4，3，2D．3，2，4，146．判定一個(gè)循環(huán)隊(duì)列qu（最多元素為MaxSize）為空的條件是C。A．qu->rear–qu->front==MaxSizeB．qu->rear–qu->front-1==MaxSizeC．qu->rear==qu->frontD．qu->rear=qu->front-147．在循環(huán)隊(duì)列中，若front與rear分別表示對(duì)頭元素和隊(duì)尾元素的位置，則判斷循環(huán)隊(duì)列空的條件是C。A．front==rear+1B．rear==front+1C．front==rearD．front==048．向一個(gè)棧頂指針為h的帶頭結(jié)點(diǎn)的鏈棧中插入指針s所指的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行D操作。A．h->next=s;B．s->next=h;C．s->next=h;h=s;D．s->next=h->next;h->next=s;49．輸入序列為ABC，可以變?yōu)镃BA時(shí)，經(jīng)過(guò)的棧操作為B。A．push，pop，push，pop，push，popB．push，push，push，pop，pop，popC．push，push，pop，pop，push，popD．push，pop，push，push，pop，pop50．若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間V[1m]，top[1]、top[2]分別代表第1和第2個(gè)棧的棧頂，棧1的底在V[1]，棧2的底在V[m]，則棧滿的條件是B。A．|top[2]-top[1]|=0B．top[1]+1=top[2]C．top[1]+top[2]=mD．top[1]=top[2]51．設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對(duì)出現(xiàn)的算法，采用D數(shù)據(jù)結(jié)構(gòu)最佳。A．線性表的順序存儲(chǔ)結(jié)構(gòu)B．隊(duì)列C．線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D．棧5