2021年數(shù)據(jù)結(jié)構(gòu)C語言版期末題庫

“數(shù)據(jù)構(gòu)造”期末考試試題一、單選題(每小題2分，共12分)1．在一種單鏈表HL中，若要向表頭插入一種由指針p指向結(jié)點(diǎn)，則執(zhí)行()。A．HL＝psp一>next＝HLB．p一>next＝HL；HL＝p3C．p一>next＝Hl；p＝HL；D．p一>next＝HL一>next;HL一>next＝p；2．n個(gè)頂點(diǎn)強(qiáng)連通圖中至少具有()。A.n—l條有向邊B.n條有向邊C.n(n—1)／2條有向邊D.n(n一1)條有向邊3.從一棵二叉搜索樹中查找一種元素時(shí)，其時(shí)間復(fù)雜度大體為()。A.O(1)B.O(n)C.O(1Ogzn)D.O(n2)4．由權(quán)值分別為3，8，6，2，5葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它帶權(quán)途徑長(zhǎng)度為()。A．24B．48C．72D．535．當(dāng)一種作為實(shí)際傳遞對(duì)象占用存儲(chǔ)空間較大并也許需要修改時(shí)，應(yīng)最佳把它闡明為()參數(shù)，以節(jié)約參數(shù)值傳播時(shí)間和存儲(chǔ)參數(shù)空間。A.整形B.引用型C.指針型D.常值引用型·6．向一種長(zhǎng)度為n順序表中插人一種新元素平均時(shí)間復(fù)雜度為()。A．O(n)B．O(1)C．O(n2)D．O(10g2n)二、填空題(每空1分，共28分)1．?dāng)?shù)據(jù)存儲(chǔ)構(gòu)造被分為——、——、——和——四種。2．在廣義表存儲(chǔ)構(gòu)造中，單元素結(jié)點(diǎn)與表元素結(jié)點(diǎn)有一種域相應(yīng)不同，各自分別為——域和——域。3．——中綴表達(dá)式3十x*(2.4／5—6)所相應(yīng)后綴表達(dá)式為————。4．在一棵高度為h3叉樹中，最多具有——結(jié)點(diǎn)。5．假定一棵二叉樹結(jié)點(diǎn)數(shù)為18，則它最小深度為——，最大深度為——·6．在一棵二叉搜索樹中，每個(gè)分支結(jié)點(diǎn)左子樹上所有結(jié)點(diǎn)值一定——該結(jié)點(diǎn)值，右子樹上所有結(jié)點(diǎn)值一定——該結(jié)點(diǎn)值。7．當(dāng)向一種小根堆插入一種具備最小值元素時(shí)，該元素需要逐級(jí)——調(diào)節(jié)，直到被調(diào)節(jié)到——位置為止。8．表達(dá)圖三種存儲(chǔ)構(gòu)造為——、——和———。9．對(duì)用鄰接矩陣表達(dá)具備n個(gè)頂點(diǎn)和e條邊圖進(jìn)行任一種遍歷時(shí)，其時(shí)間復(fù)雜度為——，對(duì)用鄰接表表達(dá)圖進(jìn)行任一種遍歷時(shí)，其時(shí)間復(fù)雜度為——。10．從有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素時(shí)，其查找長(zhǎng)度分別為——和——·11．假定對(duì)長(zhǎng)度n＝144線性表進(jìn)行索引順序查找，并假定每個(gè)子表長(zhǎng)度均為，則進(jìn)行索引順序查找平均查找長(zhǎng)度為——，時(shí)間復(fù)雜度為——·12．一棵B—樹中所有葉子結(jié)點(diǎn)均處在——上。13．每次從無序表中順序取出一種元素，把這插入到有序表中恰當(dāng)位置，此種排序辦法叫做——排序；每次從無序表中挑選出一種最小或最大元素，把它互換到有序表一端，此種排序辦法叫做——排序。14．迅速排序在乎均狀況下時(shí)間復(fù)雜度為——，最壞狀況下時(shí)間復(fù)雜度為——。三、運(yùn)算題(每小題6分，共24分)1．假定一棵二叉樹廣義表表達(dá)為a(b(c，d)，c(((，8)))，分別寫出對(duì)它進(jìn)行先序、中序、后序和后序遍歷成果。先序：中序；后序：2．已知一種帶權(quán)圖頂點(diǎn)集V和邊集G分別為：V＝{0，1，2，3，4，5}；E={(0，1)8，(0，2)5，(0，3)2，(1，5)6，(2，3)25，(2，4)13，(3，5)9，(4，5)10}，則求出該圖最小生成樹權(quán)。最小生成樹權(quán)；3．假定一組記錄排序碼為(46，79，56，38，40，84，50，42)，則運(yùn)用堆排序辦法建立初始堆為——。4．有7個(gè)帶權(quán)結(jié)點(diǎn)，其權(quán)值分別為3，7，8，2，6，10，14，試以它們?yōu)槿~子結(jié)點(diǎn)生成一棵哈夫曼樹，求出該樹帶權(quán)途徑長(zhǎng)度、高度、雙分支結(jié)點(diǎn)數(shù)。帶權(quán)途徑長(zhǎng)度：——高度：——雙分支結(jié)點(diǎn)數(shù)：——。四、閱讀算法，回答問題(每小題8分，共16分)1．VOldAC(List&L){InitList(L)；InsertRear(L;25)；InsertFront(L，50)；IntaL4]＝{5，8，12，15，36};for(inti＝0；i<5；i++)if(a[i]％2＝＝0)InsertFront(L，a[i])；elselnsertRear(L，a[i])；}該算法被調(diào)用執(zhí)行后，得到線性表L為：2．voidAG(Queue&Q){InitQueue(Q)；inta[5]＝{6，12，5，15，8}；for(inti＝0;i<5；i++)QInsert(Q，a[i])；QInsert(Q，QDelete(Q))；QInsert(Q，20)；QInsert(Q，QDelete(Q)十16)；while(!QueueEmpty(Q))cout<<QDelete(Q)<<”；}該算法被調(diào)用后得到輸出成果為：五、算法填空，在畫有橫線地方填寫適當(dāng)內(nèi)容(每小題6分，共12分)1．從一維數(shù)組A[n)中二分查找核心字為K元素遞歸算法，若查找成功則返回相應(yīng)元素下標(biāo)，否則返回一1。IntBinsch(ElemTypeA[]，Intlow，inthigh，KeyTypeK){if(low<＝high){intmid＝(low+high)／2；if(K＝＝A[mid].key)——；elseif(K<A[mid].key)——；else；}elsereturn—l；}2．已知二叉樹中結(jié)點(diǎn)類型BinTreeNode定義為：structBinTreeNode{ElemTypedata；BinTreeNode*left，*right}；其中data為結(jié)點(diǎn)值域，left和right分別為指向左、右子女結(jié)點(diǎn)指針域。下面函數(shù)功能是返回二叉樹BT中值為x結(jié)點(diǎn)所在層號(hào)，請(qǐng)?jiān)趧澯袡M線地方填寫適當(dāng)內(nèi)容。IntNodeLevel(BinTreeNode*BT，ElemTypeX){if(BT：＝NULL)return0；／／空樹層號(hào)為0elseif(BT一>data＝＝X)return1；／／根結(jié)點(diǎn)層號(hào)為1／／向子樹中查找x結(jié)點(diǎn)else{intcl＝NodeLevel(BT一>left，X)；if(cl>＝1)returncl+1;intc2＝；if——；／／若樹中不存在X結(jié)點(diǎn)則返回oelsereturn0；}}六、編寫算法(8分)按所給函數(shù)聲明編寫一種算法，從表頭指針為HL單鏈表中查找出具備最大值結(jié)點(diǎn)，該最大值由函數(shù)返回，若單鏈表為空則中斷運(yùn)營(yíng)。EIemTypeMaxValue(LNOde*HL);“數(shù)據(jù)構(gòu)造”期末考試試題答案一、單選題(每小題2分，共12分)評(píng)分原則；選對(duì)者得2分，否則不得分。1．B2．B3．C4．D5．B6．A二、填空題(每空1分，共28分)1．順序構(gòu)造鏈接構(gòu)造索引構(gòu)造散列構(gòu)造(順序無先后)2．值(或data)子表指針(或sublist)3．3x2．45／6一*十4．(3h一1)／25．5186．不大于不不大于(或不不大于等于)7．向上堆頂8．鄰接矩陣鄰接表邊集數(shù)組(順序無先后)9．O(n2)O(e)10．1311．13O()12．同一層13．插人選取14．O(nlog2n)O(n2)三、運(yùn)算題(每小題6分，共24分)1．先序：a，b，c，d，e，f，e／／2分中序：c，b，d，a，f，8，e／／2分后序：c，d，b，e，f，e，a／／2分2．最小生成樹權(quán)：31／／6分3．(84，79，56，42，40，46，50，38)／／6分4．帶權(quán)途徑長(zhǎng)度：131／／3分高度：5／／2分雙分支結(jié)點(diǎn)數(shù)：6／／1分四、閱讀算法，回答問題(每小題8分，共16分)評(píng)分原則：每小題對(duì)的得8分，浮現(xiàn)一處錯(cuò)誤扣4分，兩處及以上錯(cuò)誤不得分。1．(36，12，8，50，25，5，15)2．515862028五、算法填空，在畫有橫線地方填寫適當(dāng)內(nèi)容(每小題6分，共12分)1．feturnmid／／2分returnBinsch(A，low，mid一1，K)／／2分returnBmsch(A，mid+1，high，K)／／2分2．NodeLevel(BT一>right，X)／／3分(c2>=1)returnc2十1／／3分六、編寫算法(8分)評(píng)分原則：請(qǐng)參照語句后注釋，或依照狀況酌情給分。ElemTypeMaxValue(LNodeO*HL。){if(HL＝=NUlL){／／2分cerr<<"Linkedllstisempty!”<<endl；exit(1)；}ElemTypemax：HL一>data；／／3分LNOde*p=HI一>next；／／4分while(P!：NULL){／／7分if(max<p一>data)max＝p一>data；p＝p一>next；}returnmax；／／8分}數(shù)據(jù)構(gòu)造復(fù)習(xí)資料一、填空題1.數(shù)據(jù)構(gòu)造是一門研究非數(shù)值計(jì)算程序設(shè)計(jì)問題中計(jì)算機(jī)操作對(duì)象以及它們之間關(guān)系和運(yùn)算等學(xué)科。2.數(shù)據(jù)構(gòu)造被形式地定義為（D，R），其中D是數(shù)據(jù)元素有限集合，R是D上關(guān)系有限集合。3.數(shù)據(jù)構(gòu)造涉及數(shù)據(jù)邏輯構(gòu)造、數(shù)據(jù)存儲(chǔ)構(gòu)造和數(shù)據(jù)運(yùn)算這三個(gè)方面內(nèi)容。4.數(shù)據(jù)構(gòu)造按邏輯構(gòu)造可分為兩大類，它們分別是線性構(gòu)造和非線性構(gòu)造。5.線性構(gòu)造中元素之間存在一對(duì)一關(guān)系，樹形構(gòu)造中元素之間存在一對(duì)多關(guān)系，圖形構(gòu)造中元素之間存在多對(duì)多關(guān)系。6．在線性構(gòu)造中，第一種結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，別的每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)；最后一種結(jié)點(diǎn)沒有后續(xù)結(jié)點(diǎn)，別的每個(gè)結(jié)點(diǎn)有且只有1個(gè)后續(xù)結(jié)點(diǎn)。7.在樹形構(gòu)造中，樹根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，別的每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有后續(xù)結(jié)點(diǎn)，別的每個(gè)結(jié)點(diǎn)后續(xù)結(jié)點(diǎn)數(shù)可以任意各種。8.在圖形構(gòu)造中，每個(gè)結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以任意各種。9．?dāng)?shù)據(jù)存儲(chǔ)構(gòu)造可用四種基本存儲(chǔ)辦法表達(dá)，它們分別是順序、鏈?zhǔn)健⑺饕蜕⒘小?0.數(shù)據(jù)運(yùn)算最慣用有5種，它們分別是插入、刪除、修改、查找、排序。11.一種算法效率可分為時(shí)間效率和空間效率。12.在順序表中插入或刪除一種元素，需要平均移動(dòng)表中一半元素，詳細(xì)移動(dòng)元素個(gè)數(shù)與表長(zhǎng)和該元素在表中位置關(guān)于。13.線性表中結(jié)點(diǎn)集合是有限，結(jié)點(diǎn)間關(guān)系是一對(duì)一。14.向一種長(zhǎng)度為n向量第i個(gè)元素(1≤i≤n+1)之前插入一種元素時(shí)，需向后移動(dòng)n-i+1個(gè)元素。15.向一種長(zhǎng)度為n向量中刪除第i個(gè)元素(1≤i≤n)時(shí)，需向前移動(dòng)n-i個(gè)元素。16.在順序表中訪問任意一結(jié)點(diǎn)時(shí)間復(fù)雜度均為O(1)，因而，順序表也稱為隨機(jī)存取數(shù)據(jù)構(gòu)造。17.順序表中邏輯上相鄰元素物理位置必然相鄰。單鏈表中邏輯上相鄰元素物理位置不一定相鄰。18．在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)存儲(chǔ)位置由其直接前驅(qū)結(jié)點(diǎn)鏈域值批示。19．在n個(gè)結(jié)點(diǎn)單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，需找到它前驅(qū)結(jié)點(diǎn)地址，其時(shí)間復(fù)雜度為O（n）。20.向量、棧和隊(duì)列都是線性構(gòu)造，可以在向量任何位置插入和刪除元素；對(duì)于棧只能在棧頂插入和刪除元素；對(duì)于隊(duì)列只能在隊(duì)尾插入和隊(duì)首刪除元素。21.棧是一種特殊線性表，容許插入和刪除運(yùn)算一端稱為棧頂。不容許插入和刪除運(yùn)算一端稱為棧底。22.隊(duì)列是被限定為只能在表一端進(jìn)行插入運(yùn)算，在表另一端進(jìn)行刪除運(yùn)算線性表。23.不包括任何字符（長(zhǎng)度為0）串稱為空串；由一種或各種空格（僅由空格符）構(gòu)成串稱為空白串。24.子串定位運(yùn)算稱為串模式匹配；被匹配主串稱為目的串，子串稱為模式。25.假設(shè)有二維數(shù)組A6×8，每個(gè)元素用相鄰6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A起始存儲(chǔ)位置（基地址）為1000，則數(shù)組A體積（存儲(chǔ)量）為288B；末尾元素A57第一種字節(jié)地址為1282；若按行存儲(chǔ)時(shí)，元素A14第一種字節(jié)地址為(8+4)×6+1000=1072；若按列存儲(chǔ)時(shí)，元素A47第一種字節(jié)地址為(6×7＋4)×6＋1000）＝1276。26．由３個(gè)結(jié)點(diǎn)所構(gòu)成二叉樹有5種形態(tài)。27.一棵深度為6滿二叉樹有n1+n2=0+n2=n0-1=31個(gè)分支結(jié)點(diǎn)和26-1=32個(gè)葉子。注：滿二叉樹沒有度為1結(jié)點(diǎn)，因此分支結(jié)點(diǎn)數(shù)就是二度結(jié)點(diǎn)數(shù)。28．一棵具備２５７個(gè)結(jié)點(diǎn)完全二叉樹，它深度為9。（注：用log2(n)+1=8.xx+1=929．設(shè)一棵完全二叉樹有700個(gè)結(jié)點(diǎn)，則共有350個(gè)葉子結(jié)點(diǎn)。答：最快辦法：用葉子數(shù)＝[n/2]＝35030．設(shè)一棵完全二叉樹具備1000個(gè)結(jié)點(diǎn)，則此完全二叉樹有500個(gè)葉子結(jié)點(diǎn)，有499個(gè)度為2結(jié)點(diǎn)，有1個(gè)結(jié)點(diǎn)只有非空左子樹，有0個(gè)結(jié)點(diǎn)只有非空右子樹。答：最快辦法：用葉子數(shù)＝[n/2]＝500，n2=n0-1=499。此外，最后一結(jié)點(diǎn)為2i屬于左葉子，右葉子是空，因此有1個(gè)非空左子樹。完全二叉樹特點(diǎn)決定不也許有左空右不空狀況，因此非空右子樹數(shù)＝0.31．在數(shù)據(jù)存儲(chǔ)無規(guī)律而言線性表中進(jìn)行檢索最佳辦法是順序查找（線性查找）。32.線性有序表（a1，a2，a3，?，a256)是從小到大排列，對(duì)一種給定值k，用二分法檢索表中與k相等元素，在查找不成功狀況下，最多需要檢索8次。設(shè)有100個(gè)結(jié)點(diǎn)，用二分法查找時(shí)，最大比較次數(shù)是7。33.假設(shè)在有序線性表a[20]上進(jìn)行折半查找，則比較一次查找成功結(jié)點(diǎn)數(shù)為1；比較兩次查找成功結(jié)點(diǎn)數(shù)為2；比較四次查找成功結(jié)點(diǎn)數(shù)為8；平均查找長(zhǎng)度為3.7。解：顯然，平均查找長(zhǎng)度＝O（log2n）<5次（25）。但詳細(xì)是多少次，則不應(yīng)當(dāng)按照公式ASLn1log2(n1)來計(jì)算（即（21×log221）/20＝4.6n次并不對(duì)的?。Ｓ捎谶@是在假設(shè)n＝2m-1狀況下推導(dǎo)出來公式。應(yīng)當(dāng)用窮舉法羅列：所有元素查找次數(shù)為＝（1＋2×2＋4×3＋8×4＋5×5）＝74；ASL＝74/20=3.7?。?！34．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它將依次與表中元素28，6，12，20比較大小。35.在各種查找辦法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無關(guān)查找辦法是散列查找。36.散列法存儲(chǔ)基本思想是由核心字值決定數(shù)據(jù)存儲(chǔ)地址。二、判斷正誤（在對(duì)的說法背面打勾，反之打叉）（×）1.鏈表每個(gè)結(jié)點(diǎn)中都正好包括一種指針。答：錯(cuò)誤。鏈表中結(jié)點(diǎn)可含各種指針域，分別存儲(chǔ)各種指針。例如，雙向鏈表中結(jié)點(diǎn)可以具有兩個(gè)指針域，分別存儲(chǔ)指向其直接前趨和直接后繼結(jié)點(diǎn)指針。（×）2.鏈表物理存儲(chǔ)構(gòu)造具備同鏈表同樣順序。錯(cuò)，鏈表存儲(chǔ)構(gòu)造特點(diǎn)是無序，而鏈表達(dá)意圖有序。（×）3.鏈表刪除算法很簡(jiǎn)樸，由于當(dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算機(jī)會(huì)自動(dòng)地將后續(xù)各個(gè)單元向前移動(dòng)。錯(cuò)，鏈表結(jié)點(diǎn)不會(huì)移動(dòng)，只是指針內(nèi)容變化。（×）4.線性表每個(gè)結(jié)點(diǎn)只能是一種簡(jiǎn)樸類型，而鏈表每個(gè)結(jié)點(diǎn)可以是一種復(fù)雜類型。錯(cuò)，混淆了邏輯構(gòu)造與物理構(gòu)造，鏈表也是線性表！且雖然是順序表，也能存儲(chǔ)記錄型數(shù)據(jù)。（×）5.順序表構(gòu)造適當(dāng)于進(jìn)行順序存取，而鏈表適當(dāng)于進(jìn)行隨機(jī)存取。錯(cuò)，正好說反了。順序表才適合隨機(jī)存取，鏈表恰恰適于“順藤摸瓜”（×）6.順序存儲(chǔ)方式長(zhǎng)處是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。錯(cuò)，前一半對(duì)的，但后一半說法錯(cuò)誤，那是鏈?zhǔn)酱鎯?chǔ)長(zhǎng)處。順序存儲(chǔ)方式插入、刪除運(yùn)算效率較低，在表長(zhǎng)為n順序表中，插入和刪除一種數(shù)據(jù)元素，平均需移動(dòng)表長(zhǎng)一半個(gè)數(shù)數(shù)據(jù)元素。（×）7.線性表在物理存儲(chǔ)空間中也一定是持續(xù)。錯(cuò)，線性表有兩種存儲(chǔ)方式，順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。后者不規(guī)定持續(xù)存儲(chǔ)。（×）8.線性表在順序存儲(chǔ)時(shí)，邏輯上相鄰元素未必在存儲(chǔ)物理位置順序上相鄰。錯(cuò)誤。線性表有兩種存儲(chǔ)方式，在順序存儲(chǔ)時(shí)，邏輯上相鄰元素在存儲(chǔ)物理位置順序上也相鄰。（×）9.順序存儲(chǔ)方式只能用于存儲(chǔ)線性構(gòu)造。錯(cuò)誤。順序存儲(chǔ)方式不但能用于存儲(chǔ)線性構(gòu)造，還可以用來存儲(chǔ)非線性構(gòu)造，例如完全二叉樹是屬于非線性構(gòu)造，但其最佳存儲(chǔ)方式是順序存儲(chǔ)方式。（后一節(jié)簡(jiǎn)介）（×）10.線性表邏輯順序與存儲(chǔ)順序總是一致。錯(cuò)，理由同7。鏈?zhǔn)酱鎯?chǔ)就無需一致。（×）11.線性表每個(gè)結(jié)點(diǎn)只能是一種簡(jiǎn)樸類型，而鏈表每個(gè)結(jié)點(diǎn)可以是一種復(fù)雜類型。錯(cuò)，線性表是邏輯構(gòu)造概念，可以順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)，與元素?cái)?shù)據(jù)類型無關(guān)。（×）12.在表構(gòu)造中最慣用是線性表，棧和隊(duì)列不太慣用。錯(cuò)，不一定吧？調(diào)用子程序或函數(shù)慣用，CPU中也用隊(duì)列。（√）13.棧是一種對(duì)所有插入、刪除操作限于在表一端進(jìn)行線性表，是一種后進(jìn)先出型構(gòu)造。（√）14.對(duì)于不同使用者，一種表構(gòu)造既可以是棧，也可以是隊(duì)列，也可以是線性表。對(duì)的，都是線性邏輯構(gòu)造，棧和隊(duì)列其實(shí)是特殊線性表，對(duì)運(yùn)算定義略有不同而已。（×）15.棧和鏈表是兩種不同數(shù)據(jù)構(gòu)造。錯(cuò)，棧是邏輯構(gòu)造概念，是特殊殊線性表，而鏈表是存儲(chǔ)構(gòu)造概念，兩者不是同類項(xiàng)。（×）16.棧和隊(duì)列是一種非線性數(shù)據(jù)構(gòu)造。錯(cuò)，她們都是線性邏輯構(gòu)造，棧和隊(duì)列其實(shí)是特殊線性表，對(duì)運(yùn)算定義略有不同而已。（√）17.棧和隊(duì)列存儲(chǔ)方式既可是順序方式，也可是鏈接方式。（√）18.兩個(gè)棧共享一片持續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存運(yùn)用率，減少溢出機(jī)會(huì)，應(yīng)把兩個(gè)棧棧底分別設(shè)在這片內(nèi)存空間兩端。（×）19.隊(duì)是一種插入與刪除操作分別在表兩端進(jìn)行線性表，是一種先進(jìn)后出型構(gòu)造。錯(cuò)，后半句不對(duì)。（×）20.一種棧輸入序列是12345，則棧輸出序列不也許是12345。錯(cuò)，有也許。（√）21.若二叉樹用二叉鏈表作存貯構(gòu)造，則在n個(gè)結(jié)點(diǎn)二叉樹鏈表中只有n—1個(gè)非空指針域。（×）22.二叉樹中每個(gè)結(jié)點(diǎn)兩棵子樹高度差等于1。（√）23.二叉樹中每個(gè)結(jié)點(diǎn)兩棵子樹是有序。（×）24.二叉樹中每個(gè)結(jié)點(diǎn)有兩棵非空子樹或有兩棵空子樹。（×）25.二叉樹中每個(gè)結(jié)點(diǎn)核心字值不不大于其左非空子樹（若存在話）所有結(jié)點(diǎn)核心字值，且不大于其右非空子樹（若存在話）所有結(jié)點(diǎn)核心字值。（應(yīng)當(dāng)是二叉排序樹特點(diǎn)）（×）26.二叉樹中所有結(jié)點(diǎn)個(gè)數(shù)是2k-1-1，其中k是樹深度。（應(yīng)2i-1）（×）27.二叉樹中所有結(jié)點(diǎn)，如果不存在非空左子樹，則不存在非空右子樹。（×）28.對(duì)于一棵非空二叉樹，它根結(jié)點(diǎn)作為第一層，則它第i層上最多能有2i—1個(gè)結(jié)點(diǎn)。（應(yīng)2i-1）（√）29.用二叉鏈表法（link-rlink）存儲(chǔ)包括n個(gè)結(jié)點(diǎn)二叉樹，結(jié)點(diǎn)2n個(gè)指針區(qū)域中有n+1個(gè)為空指針。（√）30.具備12個(gè)結(jié)點(diǎn)完全二叉樹有5個(gè)度為2結(jié)點(diǎn)。三、單項(xiàng)選取題（B）1.非線性構(gòu)造是數(shù)據(jù)元素之間存在一種：A）一對(duì)多關(guān)系B）多對(duì)多關(guān)系C）多對(duì)一關(guān)系D）一對(duì)一關(guān)系（C）2.數(shù)據(jù)構(gòu)造中，與所使用計(jì)算機(jī)無關(guān)是數(shù)據(jù)構(gòu)造；A)存儲(chǔ)B)物理C)邏輯D)物理和存儲(chǔ)（C）3.算法分析目是：A)找出數(shù)據(jù)構(gòu)造合理性B)研究算法中輸入和輸出關(guān)系C)分析算法效率以求改進(jìn)D)分析算法易懂性和文檔性（A）4.算法分析兩個(gè)重要方面是：A)空間復(fù)雜性和時(shí)間復(fù)雜性B)對(duì)的性和簡(jiǎn)要性C)可讀性和文檔性D)數(shù)據(jù)復(fù)雜性和程序復(fù)雜性（C）5.計(jì)算機(jī)算法指是：A)計(jì)算辦法B)排序辦法C)解決問題有限運(yùn)算序列D)調(diào)度辦法（B）6.計(jì)算機(jī)算法必要具備輸入、輸出和等5個(gè)特性。A)可行性、可移植性和可擴(kuò)充性B)可行性、擬定性和有窮性C)擬定性、有窮性和穩(wěn)定性D)易讀性、穩(wěn)定性和安全性（C）7．?dāng)?shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表達(dá)時(shí)，物理地址與邏輯地址相似并且是持續(xù)，稱之為：（A）存儲(chǔ)構(gòu)造（B）邏輯構(gòu)造（C）順序存儲(chǔ)構(gòu)造（D）鏈?zhǔn)酱鎯?chǔ)構(gòu)造（B）8.一種向量第一種元素存儲(chǔ)地址是100，每個(gè)元素長(zhǎng)度為2，則第5個(gè)元素地址是（A）110（B）108（C）100（D）120（A）9.在n個(gè)結(jié)點(diǎn)順序表中，算法時(shí)間復(fù)雜度是O（1）操作是：（A）訪問第i個(gè)結(jié)點(diǎn)（1≤i≤n）和求第i個(gè)結(jié)點(diǎn)直接前驅(qū)（2≤i≤n）（B）在第i個(gè)結(jié)點(diǎn)后插入一種新結(jié)點(diǎn)（1≤i≤n）（C）刪除第i個(gè)結(jié)點(diǎn)（1≤i≤n）（D）將n個(gè)結(jié)點(diǎn)從小到大排序（B）10.向一種有127個(gè)元素順序表中插入一種新元素并保持本來順序不變，平均要移動(dòng)個(gè)元素（A）8（B）63.5（C）63（D）7（A）11.鏈接存儲(chǔ)存儲(chǔ)構(gòu)造所占存儲(chǔ)空間：（A）分兩某些，一某些存儲(chǔ)結(jié)點(diǎn)值，另一某些存儲(chǔ)表達(dá)結(jié)點(diǎn)間關(guān)系指針（B）只有一某些，存儲(chǔ)結(jié)點(diǎn)值(C）只有一某些，存儲(chǔ)表達(dá)結(jié)點(diǎn)間關(guān)系指針（D）分兩某些，一某些存儲(chǔ)結(jié)點(diǎn)值，另一某些存儲(chǔ)結(jié)點(diǎn)所占單元數(shù)（B）12.鏈表是一種采用存儲(chǔ)構(gòu)造存儲(chǔ)線性表；（A）順序（B）鏈?zhǔn)剑–）星式（D）網(wǎng)狀（D）13.線性表若采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造時(shí)，規(guī)定內(nèi)存中可用存儲(chǔ)單元地址:（A）必要是持續(xù)（B）某些地址必要是持續(xù)（C）一定是不持續(xù)（D）持續(xù)或不持續(xù)都可以（B）14．線性表Ｌ在狀況下合用于使用鏈?zhǔn)綐?gòu)造實(shí)現(xiàn)。（Ａ）需經(jīng)常修改Ｌ中結(jié)點(diǎn)值（Ｂ）需不斷對(duì)Ｌ進(jìn)行刪除插入（Ｃ）Ｌ中具有大量結(jié)點(diǎn)（Ｄ）Ｌ中結(jié)點(diǎn)構(gòu)造復(fù)雜（B）15.棧中元素進(jìn)出原則是Ａ．先進(jìn)先出Ｂ．后進(jìn)先出Ｃ．?？談t進(jìn)Ｄ．棧滿則出（C）16.若已知一種棧入棧序列是1，2，3，?，n，其輸出序列為p1，p2，p3，?，pn，若p1=n，則pi為Ａ．iＢ．n=iＣ．n-i+1Ｄ．不擬定（B）17.鑒定一種棧ST（最多元素為m0）為空條件是Ａ．ST->top<>0Ｂ．ST->top=0Ｃ．ST->top<>m0Ｄ．ST->top=m0（C）18.在一種圖中，所有頂點(diǎn)度數(shù)之和等于圖邊數(shù)倍。A．1/2B.1C.2D.4（B）19.在一種有向圖中，所有頂點(diǎn)入度之和等于所有頂點(diǎn)出度之和倍。A．1/2B.1C.2D.4（B）20.有8個(gè)結(jié)點(diǎn)無向圖最多有條邊。A．14B.28C.56D.112（C）21.有8個(gè)結(jié)點(diǎn)有向完全圖有條邊。A．14B.28C.56D.112（B）22．在表長(zhǎng)為ｎ鏈表中進(jìn)行線性查找，它平均查找長(zhǎng)度為Ａ.ＡＳＬ＝ｎ；Ｂ.ＡＳＬ＝（ｎ＋１）／２;Ｃ.ＡＳＬ＝＋１；Ｄ.ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１（A）23．折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中比較大小，查找成果是失敗。A．20，70，30，50B．30，88，70，50C．20，50D．30，88，50（C）24．對(duì)22個(gè)記錄有序表作折半查找，當(dāng)查找失敗時(shí)，至少需要比較次核心字。A．3B．4C．5D．6（A）25.鏈表合用于查找A．順序B．二分法C．順序，也能二分法D．隨機(jī)《數(shù)據(jù)構(gòu)造與算法》復(fù)習(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．?dāng)?shù)據(jù)構(gòu)造在計(jì)算機(jī)內(nèi)存中表達(dá)是指A。A．?dāng)?shù)據(jù)存儲(chǔ)構(gòu)造B．?dāng)?shù)據(jù)構(gòu)造C．?dāng)?shù)據(jù)邏輯構(gòu)造D．?dāng)?shù)據(jù)元素之間關(guān)系3．在數(shù)據(jù)構(gòu)造中，與所使用計(jì)算機(jī)無關(guān)是數(shù)據(jù)A構(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ǔ)構(gòu)造時(shí)，普通不考慮A。A．各結(jié)點(diǎn)值如何B．結(jié)點(diǎn)個(gè)數(shù)多少C．對(duì)數(shù)據(jù)有哪些運(yùn)算D．所用編程語言實(shí)現(xiàn)這種構(gòu)造與否以便。6．如下說法對(duì)的是D。A．?dāng)?shù)據(jù)項(xiàng)是數(shù)據(jù)基本單位B．?dāng)?shù)據(jù)元素是數(shù)據(jù)最小單位C．?dāng)?shù)據(jù)構(gòu)造是帶構(gòu)造數(shù)據(jù)項(xiàng)集合D．某些表面上很不相似數(shù)據(jù)可以有相似邏輯構(gòu)造7．算法分析目是C，算法分析兩個(gè)重要方面是A。（1）A．找出數(shù)據(jù)構(gòu)造合理性B．研究算法中輸入和輸出關(guān)系C．分析算法效率以求改進(jìn)C．分析算法易讀性和文檔性（2）A．空間復(fù)雜度和時(shí)間復(fù)雜度B．對(duì)的性和簡(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．在如下論述中，對(duì)的是B。A．線性表順序存儲(chǔ)構(gòu)造優(yōu)于鏈表存儲(chǔ)構(gòu)造B．二維數(shù)組是其數(shù)據(jù)元素為線性表線性表C．棧操作方式是先進(jìn)先出D．隊(duì)列操作方式是先進(jìn)后出12．普通規(guī)定同一邏輯構(gòu)造中所有數(shù)據(jù)元素具備相似特性，這意味著B。A．?dāng)?shù)據(jù)元素具備同一特點(diǎn)B．不但數(shù)據(jù)元素所包括數(shù)據(jù)項(xiàng)個(gè)數(shù)要相似，并且相應(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ī)訪問任一結(jié)點(diǎn)B．插入刪除不需要移動(dòng)元素C．不必事先預(yù)計(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．若某表最慣用操作是在最后一種結(jié)點(diǎn)之后插入一種結(jié)點(diǎn)或刪除最后一種結(jié)點(diǎn)，則采用D存儲(chǔ)方式最節(jié)約運(yùn)算時(shí)間。A．單鏈表B．給出表頭指針單循環(huán)鏈表C．雙鏈表D．帶頭結(jié)點(diǎn)雙循環(huán)鏈表17．需要分派較大空間，插入和刪除不需要移動(dòng)元素線性表，其存儲(chǔ)構(gòu)造是B。A．單鏈表B．靜態(tài)鏈表C．線性鏈表D．順序存儲(chǔ)構(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．在一種具備n個(gè)結(jié)點(diǎn)有序單鏈表中插入一種新結(jié)點(diǎn)并依然保持有序時(shí)間復(fù)雜度是B。A．O（1）B．O（n）C．O（n2）D．O（nlog2n）22．在一種長(zhǎng)度為n（n>1）單鏈表上，設(shè)有頭和尾兩個(gè)指針，執(zhí)行B操作與鏈表長(zhǎng)度關(guān)于。A．刪除單鏈表中第一種元素B．刪除單鏈表中最后一種元素C．在單鏈表第一種元素前插入一種新元素D．在單鏈表最后一種元素后插入一種新元素23．與單鏈表相比，雙鏈表長(zhǎng)處之一是D。A．插入、刪除操作更簡(jiǎn)樸B．可以進(jìn)行隨機(jī)訪問C．可以省略表頭指針或表尾指針D．順序訪問相鄰結(jié)點(diǎn)更靈活24．如果對(duì)線性表操作只有兩種，即刪除第一種元素，在最后一種元素背面插入新元素，則最佳使用B。A．只有表頭指針沒有表尾指針循環(huán)單鏈表B．只有表尾指針沒有表頭指針循環(huán)單鏈表C．非循環(huán)雙鏈表D．循環(huán)雙鏈表25．在長(zhǎng)度為n順序表第i個(gè)位置上插入一種元素（1≤i≤n+1），元素移動(dòng)次數(shù)為：A。A．n–i+1B．n–iC．iD．i–126．對(duì)于只在表首、尾兩端進(jìn)行插入操作線性表，宜采用存儲(chǔ)構(gòu)造為C。A．順序表B．用頭指針表達(dá)循環(huán)單鏈表C．用尾指針表達(dá)循環(huán)單鏈表D．單鏈表27．下述哪一條是順序存儲(chǔ)構(gòu)造長(zhǎng)處？C。A插入運(yùn)算以便B可以便地用于各種邏輯構(gòu)造存儲(chǔ)表達(dá)C存儲(chǔ)密度大D刪除運(yùn)算以便28．下面關(guān)于線性表論述中，錯(cuò)誤是哪一種？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．訪問第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)后插入一種新結(jié)點(diǎn)C．刪除第i（1<=i<=n）個(gè)結(jié)點(diǎn)D．以上都不對(duì)31．若長(zhǎng)度為n線性表采用順序存儲(chǔ)構(gòu)造，在其第i個(gè)位置插入一種新元素算法時(shí)間復(fù)雜度為C。A．O(0)B．O(1)C．O(n)D．O(n2)32．對(duì)于順序存儲(chǔ)線性表，訪問結(jié)點(diǎn)和增長(zhǎng)、刪除結(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ǔ)，訪問第i位置元素時(shí)間復(fù)雜度為C。A．O(0)B．O(1)C．O(n)D．O(n2)34．單鏈表中，增長(zhǎng)一種頭結(jié)點(diǎn)目是為了C。A．使單鏈表至少有一種結(jié)點(diǎn)B．標(biāo)記表結(jié)點(diǎn)中首結(jié)點(diǎn)位置C．方面運(yùn)算實(shí)現(xiàn)D．闡明單鏈表是線性表鏈?zhǔn)酱鎯?chǔ)35．在單鏈表指針為p結(jié)點(diǎn)之后插入指針為s結(jié)點(diǎn)，對(duì)的操作是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ǔ)構(gòu)造是一種A。A．隨機(jī)存取存儲(chǔ)構(gòu)造B．順序存取存儲(chǔ)構(gòu)造C．索引存取存儲(chǔ)構(gòu)造D．Hash存取存儲(chǔ)構(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．沒有共同點(diǎn)39．一種棧進(jìn)棧序列是a，b，c，d，e，則棧不也許輸出序列是C。A．edcbaB．decbaC．dceabD．a(chǎn)bcde40．設(shè)有一種棧，元素依次進(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ì)尾插入一種新元素B．從隊(duì)列中刪除第i個(gè)元素C．判斷一種隊(duì)列與否為空D．讀取隊(duì)頭元素值42．若已知一種棧進(jìn)棧序列是1，2，3，，n，其輸出序列為p1，p2，p3，?，pn，若p1＝n，則pi為C。A．iB．n－iC．n－i＋1D．不擬定43．鑒定一種順序棧st（最多元素為MaxSize）為空條件是B。A．st->top!=-1B．st->top==-1C．st->top!=MaxSizeD．st->top==MaxSize44．鑒定一種順序棧st（最多元素為MaxSize）為滿條件是D。A．st->top!=-1B．st->top==-1C．st->top!=MaxSizeD．st->top==MaxSize45．一種隊(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．鑒定一種循環(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分別表達(dá)對(duì)頭元素和隊(duì)尾元素位置，則判斷循環(huán)隊(duì)列空條件是C。A．front==rear+1B．rear==front+1C．front==rearD．front==048．向一種棧頂指針為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í)，通過棧操作為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ì)一種鑒別表達(dá)式中左、右括號(hào)與否配對(duì)浮現(xiàn)算法，采用D數(shù)據(jù)構(gòu)造最佳。A．線性表順序存儲(chǔ)構(gòu)造B．隊(duì)列C．線性表鏈?zhǔn)酱鎯?chǔ)構(gòu)造D．棧52．容許對(duì)隊(duì)列進(jìn)行操作有D。A．對(duì)隊(duì)列中元素排序B．取出近來進(jìn)隊(duì)元素C．在隊(duì)頭元素之前插入元素D．刪除隊(duì)頭元素53．對(duì)于循環(huán)隊(duì)列D。A．無法判斷隊(duì)列與否為空B．無法判斷隊(duì)列與否為滿C．隊(duì)列不也許滿D．以上說法都不對(duì)54．若用一種大小為6數(shù)值來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front值分別為0和3，當(dāng)從隊(duì)列中刪除一種元素，再加入兩個(gè)元素后，rear和front值分別為B。A．1和5B．2和4C．4和2D．5和155．隊(duì)列“先進(jìn)先出”特性是指D。A．最早插入隊(duì)列中元素總是最后被刪除B．當(dāng)同步進(jìn)行插入、刪除操作時(shí)，總是插入操作優(yōu)先C．每當(dāng)有刪除操作時(shí)，總是要先做一次插入操作D．每次從隊(duì)列中刪除總是最早插入元素56．和順序棧相比，鏈棧有一種比較明顯優(yōu)勢(shì)是A。A．普通不會(huì)浮現(xiàn)棧滿狀況B．普通不會(huì)浮現(xiàn)?？諣顩rC．插入操作更容易實(shí)現(xiàn)D．刪除操作更容易實(shí)現(xiàn)57．用不帶頭結(jié)點(diǎn)單鏈表存儲(chǔ)隊(duì)列，其頭指針指向隊(duì)頭結(jié)點(diǎn)，尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行出隊(duì)操作時(shí)C。A．僅修改隊(duì)頭指針B．僅修改隊(duì)尾指針C．隊(duì)頭、隊(duì)尾指針都也許要修改D．隊(duì)頭、隊(duì)尾指針都要修改58．若串S=‘software’，其子串?dāng)?shù)目是B。A．8B．37C．36D．959．串長(zhǎng)度是指B。A．串中所含不同字母?jìng)€(gè)數(shù)B．串中所含字符個(gè)數(shù)C．串中所含不同字符個(gè)數(shù)D．串中所含非空格字符個(gè)數(shù)60．串是一種特殊線性表，其特殊性體當(dāng)前B。A．可以順序存儲(chǔ)B．?dāng)?shù)據(jù)元素是一種字符C．可以鏈?zhǔn)酱鎯?chǔ)D．?dāng)?shù)據(jù)元素可以是各種字符61．設(shè)有兩個(gè)串p和q，求q在p中初次浮現(xiàn)位置運(yùn)算稱為B。A．連接B．模式匹配C．求子串D．求串長(zhǎng)62．?dāng)?shù)組A中，每個(gè)元素長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始持續(xù)存儲(chǔ)存儲(chǔ)器內(nèi)，該數(shù)組按行存儲(chǔ)，元素A[8][5]起始地址為C。A．SA＋141B．SA＋144C．SA＋222D．SA＋22563．?dāng)?shù)組A中，每個(gè)元素長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始持續(xù)存儲(chǔ)存儲(chǔ)器內(nèi)，該數(shù)組按行存儲(chǔ)，元素A[5][8]起始地址為C。A．SA＋141B．SA＋180C．SA＋222D．SA＋22564．若聲明一種浮點(diǎn)數(shù)數(shù)組如下：froataverage[]=newfloat[30];假設(shè)該數(shù)組內(nèi)存起始位置為200，average[15]內(nèi)存地址是C。A．214B．215C．260D．25665．設(shè)二維數(shù)組A[1?m,1?n]按行存儲(chǔ)在數(shù)組B中，則二維數(shù)組元素A[i,j]在一維數(shù)組B中下標(biāo)為A。A．n*(i-1)+jB．n*(i-1)+j-1C．i*(j-1)D．j*m+i-166．有一種100×90稀疏矩陣，非0元素有10，設(shè)每個(gè)整型數(shù)占2個(gè)字節(jié)，則用三元組表達(dá)該矩陣時(shí)，所需字節(jié)數(shù)是B。A．20B．66C．18000D．3367．?dāng)?shù)組A[0?4，-1?-3，5?7]中具有元素個(gè)數(shù)是A。A．55B．45C．36D．1668．對(duì)矩陣進(jìn)行壓縮存儲(chǔ)是為了D。A．以便運(yùn)算B．以便存儲(chǔ)C．提高運(yùn)算速度D．減少存儲(chǔ)空間69．設(shè)有一種10階對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a1，1為第一種元素，其存儲(chǔ)地址為1，每個(gè)元素占1個(gè)地址空間，則a8，5地址為B。A．13B．33C．18D．4070．稀疏矩陣普通壓縮存儲(chǔ)方式有兩種，即C。A．二維數(shù)組和三維數(shù)組B．三元組和散列C．三元組和十字鏈表D．散列和十字鏈表71．樹最適合用來表達(dá)C。A．有序數(shù)據(jù)元素B．無序數(shù)據(jù)元素C．元素之間具備分支層次關(guān)系數(shù)據(jù)D．元素之間無聯(lián)系數(shù)據(jù)72．深度為5二叉樹至多有C個(gè)結(jié)點(diǎn)。A．16B．32C．31C．1073．對(duì)一種滿二叉樹，m個(gè)葉子，n個(gè)結(jié)點(diǎn)，深度為h，則D。hA．n=h+mBh+m=2nCm=h-1Dn=2-174．任何一棵二叉樹葉子結(jié)點(diǎn)在前序、中序和后序遍歷序列中相對(duì)順序A。A．不發(fā)生變化B．發(fā)生變化C．不能擬定D．以上都不對(duì)75．在線索化樹中，每個(gè)結(jié)點(diǎn)必要設(shè)立一種標(biāo)志來闡明它左、右鏈指向是樹構(gòu)造信息，還是線索化信息，若0標(biāo)記樹構(gòu)造信息，1標(biāo)記線索，相應(yīng)葉結(jié)點(diǎn)左右鏈域，應(yīng)標(biāo)記為__D__。A．00B．01C．10D．1176．在下述闡述中，對(duì)的是D。①只有一種結(jié)點(diǎn)二叉樹度為0；②二叉樹度為2；③二叉樹左右子樹可任意互換；④深度為K順序二叉樹結(jié)點(diǎn)個(gè)數(shù)不大于或等于深度相似滿二叉樹。A．①②③B．②③④C．②④D．①④77．設(shè)森林F相應(yīng)二叉樹為B，它有m個(gè)結(jié)點(diǎn)，B根為p，p右子樹結(jié)點(diǎn)個(gè)數(shù)為n，森林F中第一棵樹結(jié)點(diǎn)個(gè)數(shù)是A。A．m-nB．m-n-1C．n+1D．不能擬定78．若一棵二叉樹具備10個(gè)度為2結(jié)點(diǎn)，5個(gè)度為1結(jié)點(diǎn)，則度為0結(jié)點(diǎn)個(gè)數(shù)是B。A．9B．11C．15D．不能擬定79．具備10個(gè)葉子結(jié)點(diǎn)二叉樹中有B個(gè)度為2結(jié)點(diǎn)。A．8B．9C．10D．1180．在一種無向圖中，所有頂點(diǎn)度數(shù)之和等于所有邊數(shù)C倍。A．1/2B1C2D481．在一種有向圖中，所有頂點(diǎn)入度之和等于所有頂點(diǎn)出度之和B倍。A．1/2B1C2D482．某二叉樹結(jié)點(diǎn)中序序列為ABCDEFG，后序序列為BDCAFGE，則其左子樹中結(jié)點(diǎn)數(shù)目為：CA．3B．2C．4D．583．已知一算術(shù)表達(dá)式中綴形式為A＋B*C–D/E，后綴形式為ABC*+DE/–，其前綴形式為D。A．–A+B*C/DEB．–A+B*CD/EC–+*ABC/DED．–+A*BC/DE84．已知一種圖，如圖所示，若從頂點(diǎn)a出發(fā)按深度搜索法進(jìn)行遍歷，則也許得到一種頂點(diǎn)序列為____D___；按廣度搜索法進(jìn)行遍歷，則也許得到一種頂點(diǎn)序列為___A___；①A．a(chǎn)，b，e，c，d，fB．a(chǎn)，c，f，e，b，dC．a(chǎn)，e，b，c，f，d，D．a(chǎn)，e，d，f，c，b②A．a(chǎn)，b，c，e，d，fB．a(chǎn)，b，c，e，f，dC．a(chǎn)，e，b，c，f，d，D．a(chǎn)，c，f，d，e，b85．采用鄰接表存儲(chǔ)圖深度優(yōu)先遍歷算法類似于二叉樹___A____。A．先序遍歷B．中序遍歷C．后序遍歷D．按層遍歷86．采用鄰接表存儲(chǔ)圖廣度優(yōu)先遍歷算法類似于二叉樹___D____。A．先序遍歷B．中序遍歷C．后序遍歷D．按層遍歷87．具備n個(gè)結(jié)點(diǎn)連通圖至少有A條邊。A．n-1B．nC．n(n-1)/2D．2n88．廣義表（（a），a）表頭是C，表尾是C。A．a(chǎn)B（）C（a）D（（a））89．廣義表（（a））表頭是C，表尾是B。A．a(chǎn)B（）C（a）D（（a））90．順序查找法適合于存儲(chǔ)構(gòu)造為B線性表。A散列存儲(chǔ)B順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)C壓縮存儲(chǔ)D索引存儲(chǔ)91．對(duì)線性表進(jìn)行折半查找時(shí)，規(guī)定線性表必要B。A以順序方式存儲(chǔ)B以順序方式存儲(chǔ)，且結(jié)點(diǎn)按核心字有序排列C以鏈?zhǔn)椒绞酱鎯?chǔ)D以鏈?zhǔn)椒绞酱鎯?chǔ)，且結(jié)點(diǎn)按核心字有序排列92．采用折半查找法查找長(zhǎng)度為n線性表時(shí)，每個(gè)元素平均查找長(zhǎng)度為D。AO(n2)BO(nlog2n)CO(n)DO(log2n)93．有一種有序表為｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，當(dāng)折半查找值為82結(jié)點(diǎn)時(shí)，C次比較后查找成功。A．11B5C4D894．二叉樹為二叉排序樹充分必要條件是其任一結(jié)點(diǎn)值均不不大于其左孩子值、不大于其右孩子值。這種說法B。A對(duì)的B錯(cuò)誤95．下面關(guān)于B樹和B+樹論述中，不對(duì)的結(jié)論是A。AB樹和B+樹都能有效支持順序查找BB樹和B+樹都能有效支持隨機(jī)查找CB樹和B+樹都是平衡多叉樹DB樹和B+樹都可用于文獻(xiàn)索引構(gòu)造96．如下說法錯(cuò)誤是B。A．散列法存儲(chǔ)思想是由核心字值決定數(shù)據(jù)存儲(chǔ)地址B．散列表結(jié)點(diǎn)中只包括數(shù)據(jù)元素自身信息，不包括指針。C．負(fù)載因子是散列表一種重要參數(shù)，它反映了散列表飽滿限度。D．散列表查找效率重要取決于散列表構(gòu)造時(shí)選用散列函數(shù)和解決沖突辦法。97．查找效率最高二叉排序樹是C。A．所有結(jié)點(diǎn)左子樹都為空二叉排序樹。B．所有結(jié)點(diǎn)右子樹都為空二叉排序樹。C．平衡二叉樹。D．沒有左子樹二叉排序樹。98．排序辦法中，從未排序序列中依次取出元素與已排序序列中元素進(jìn)行比較，將其放入已排序序列對(duì)的位置上辦法，稱為C。A．希爾排序B。冒泡排序C插入排序D。選取排序99．在所有排序辦法中，核心字比較次數(shù)與記錄初始排列順序無關(guān)是D。A．希爾排序B．冒泡排序C．直接插入排序D．直接選取排序100．堆是一種有用數(shù)據(jù)構(gòu)造。下列核心碼序列D是一種堆。A．94,31,53,23,16,72B．94,53,31,72,16,23C．16,53,23,94,31,72D．16,31,23,94,53,72101．堆排序是一種B排序。A．插入B．選取C．互換D．歸并102．D在鏈表中進(jìn)行操作比在順序表中進(jìn)行操作效率高。A．順序查找B．折半查找C．分塊查找D．插入103．直接選取排序時(shí)間復(fù)雜度為D。（n為元素個(gè)數(shù)）A．O（n)B．O(log2n)C．O(nlog2n)D．O(n2)二、填空題。1．?dāng)?shù)據(jù)邏輯構(gòu)造涉及線性構(gòu)造、樹形構(gòu)造和圖狀構(gòu)造三種類型，樹形構(gòu)造和圖狀構(gòu)造合稱非線性構(gòu)造。2．?dāng)?shù)據(jù)邏輯構(gòu)造分為集合、線性構(gòu)造、樹形構(gòu)造和圖狀構(gòu)造4種。3．在線性構(gòu)造中，第一種結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，別的每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)；最后一種結(jié)點(diǎn)沒有后續(xù)結(jié)點(diǎn)，別的每個(gè)結(jié)點(diǎn)有且只有1個(gè)后續(xù)結(jié)點(diǎn)。4．線性構(gòu)造中元素之間存在一對(duì)一關(guān)系，樹形構(gòu)造中元素之間存在一對(duì)多關(guān)系，圖形構(gòu)造中元素之間存在多對(duì)多關(guān)系。5．在樹形構(gòu)造中，樹根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，別的每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有后續(xù)結(jié)點(diǎn)，別的每個(gè)結(jié)點(diǎn)后續(xù)結(jié)點(diǎn)可以任意各種。6．?dāng)?shù)據(jù)構(gòu)造基本存儲(chǔ)辦法是順序、鏈?zhǔn)?、索引和散列存?chǔ)。7．衡量一種算法優(yōu)劣重要考慮對(duì)的性、可讀性、健壯性和時(shí)間復(fù)雜度與空間復(fù)雜度。8．評(píng)估一種算法優(yōu)劣，普通從時(shí)間復(fù)雜度和空間復(fù)雜度兩個(gè)方面考察。9．算法5個(gè)重要特性是有窮性、擬定性、可行性、輸入和輸出。10．在一種長(zhǎng)度為n順序表中刪除第i個(gè)元素時(shí)，需向前移動(dòng)n-i-1個(gè)元素。11．在單鏈表中，要?jiǎng)h除某一指定結(jié)點(diǎn)，必要找到該結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)。12．在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一種指向前驅(qū)結(jié)點(diǎn)，另一種指向后繼結(jié)點(diǎn)。13．在順序表中插入或刪除一種數(shù)據(jù)元素，需要平均移動(dòng)n個(gè)數(shù)據(jù)元素，移動(dòng)數(shù)據(jù)元素個(gè)數(shù)與位置關(guān)于。14．當(dāng)線性表元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但規(guī)定以最迅速度存取線性表元素是，應(yīng)采用順序存儲(chǔ)構(gòu)造。15．依照線性表鏈?zhǔn)酱鎯?chǔ)構(gòu)造中每一種結(jié)點(diǎn)包括指針個(gè)數(shù)，將線性鏈表提成單鏈表和雙鏈表。16．順序存儲(chǔ)構(gòu)造是通過下標(biāo)表達(dá)元素之間關(guān)系；鏈?zhǔn)酱鎯?chǔ)構(gòu)造是通過指針表達(dá)元素之間關(guān)系。17．帶頭結(jié)點(diǎn)循環(huán)鏈表L中只有一種元素結(jié)點(diǎn)條件是L->next->next=L。18．棧是限定僅在表尾進(jìn)行插入或刪除操作線性表，其運(yùn)算遵循后進(jìn)先出原則。19．空串是零個(gè)字符串，其長(zhǎng)度等于零?？瞻状怯梢环N或各種空格字符構(gòu)成串，其長(zhǎng)度等于其包括空格個(gè)數(shù)。20．構(gòu)成串?dāng)?shù)據(jù)元素只能是單個(gè)字符。21．一種字符串中任意個(gè)持續(xù)字符構(gòu)成某些稱為該串子串。22．子串”str”在主串”datastructure”中位置是5。23．二維數(shù)組M每個(gè)元素是6個(gè)字符構(gòu)成串，行下標(biāo)i范疇從0到8，列下標(biāo)j范疇從1到10，則存儲(chǔ)M至少需要540個(gè)字節(jié)；M第8列和第5行共占108個(gè)字節(jié)。24．稀疏矩陣普通壓縮存儲(chǔ)辦法有兩種，即三元組表和十字鏈表。25．廣義表（