C語言數(shù)據(jù)結(jié)構(gòu)-綜合測(cè)試題及答案

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第10章 綜合測(cè)試能力要求（1） 計(jì)算機(jī)基礎(chǔ)知識(shí)：掌握?qǐng)D的概念以及圖的基本操作。（2） 分析問題：針對(duì)具體的問題，要能夠運(yùn)用圖去進(jìn)行分析，逐步找到解決問題的方法。（3） 具有概念化和抽象化能力：針對(duì)具體的應(yīng)用和實(shí)際的問題，能夠運(yùn)用圖對(duì)問題進(jìn)行抽象，提取它的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。（4） 發(fā)現(xiàn)問題和表述問題：在具體的工程中，能夠發(fā)現(xiàn)工程中涉及到圖的問題，并能夠明確表述。（5） 建模：在具體的工程中，能夠使用圖進(jìn)行建模，設(shè)計(jì)合理的數(shù)據(jù)結(jié)構(gòu)和相應(yīng)的算法。（6） 解決方法和建議：在具體工程應(yīng)用中，發(fā)現(xiàn)了關(guān)于圖的問題，要能夠解決問題，并提出合理的建議。（7） 定義功能，概念和結(jié)構(gòu)：

2、使用圖這種邏輯結(jié)構(gòu)處理一些具體問題，實(shí)現(xiàn)系統(tǒng)的功能。（8） 設(shè)計(jì)過程的分段與方法：采取不同的階段去設(shè)計(jì)（概念設(shè)計(jì)、詳細(xì)設(shè)計(jì)）一個(gè)具體的圖的應(yīng)用項(xiàng)目。（9）軟件實(shí)現(xiàn)過程：了解系統(tǒng)中各個(gè)模塊中的關(guān)于圖的設(shè)計(jì)；討論算法（數(shù)據(jù)結(jié)構(gòu)、控制流程、數(shù)據(jù)流程）；使用編程語言實(shí)施底層設(shè)計(jì)（編程）。 10.1綜合測(cè)試題1 一、判斷題說明：共10題，每題1分，滿分10分（ ）1 有一批數(shù)據(jù)，經(jīng)常用來進(jìn)行插入和刪除處理，這樣的數(shù)據(jù)用順序表存儲(chǔ)最合適。（ ）2 棧用于實(shí)現(xiàn)子程序調(diào)用。 （ ）3 隊(duì)列可用于表達(dá)式的求值。（ ）4 隊(duì)列在隊(duì)頭插入，隊(duì)尾刪除。（ ）5 若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個(gè)結(jié)點(diǎn)的二叉樹鏈表中

3、只有n1個(gè)非空指針域。（ ）6 完全二叉樹的某結(jié)點(diǎn)若無左孩子，則它必是葉結(jié)點(diǎn)。（ ）7 將一棵樹轉(zhuǎn)換成二叉樹后，根結(jié)點(diǎn)沒有左子樹。（ ） 8 任一二叉排序樹的平均查找時(shí)間都小于用順序查找法查找同樣結(jié)點(diǎn)的線性表的平均查找時(shí)間。（ ）9 中序遍歷一棵二叉排序樹的結(jié)點(diǎn)就可得到排好序的結(jié)點(diǎn)序列。（ ）10 如果待排序的數(shù)據(jù)是有一定順序的，那么冒泡和簡(jiǎn)單選擇排序法中，簡(jiǎn)單選擇最好。二、填空題說明：共10空，每空1分，滿分10分。1 棧的特點(diǎn)是 ，隊(duì)列的特點(diǎn)是 。2 深度為k的完全二叉樹的至少有 個(gè)節(jié)點(diǎn)， 至多有 節(jié)點(diǎn)。3 一棵二叉樹的前序遍歷結(jié)點(diǎn)的訪問順序?yàn)椋篴bdgcefh， 中序遍歷為：dgbaec

4、hf， 則其后序遍歷結(jié)果為 。4 一組記錄元素的關(guān)鍵碼為75，84，26，33，92，15，則利用快速排序的方法，以第一個(gè)記錄為樞紐值得到的一次劃分結(jié)果是： 5 n 個(gè)頂點(diǎn)的無向連通圖中最多邊數(shù)為 ，最少邊數(shù)為 。6 利用冒泡排序處理n個(gè)數(shù)據(jù)，最快比較 次完成排序，最慢比較 次完成排序。三、選擇題 說明：共20小題，每小題1分，滿分20分；請(qǐng)將答案填入題后括號(hào)中。在本選擇題中出現(xiàn)的front代表隊(duì)列的隊(duì)頭指針，rear代表隊(duì)列的隊(duì)尾指針，top代表?xiàng)ｍ斨羔?。其中，涉及到單鏈表的?jié)點(diǎn)定義如下： struct list int data; struct list *next;1 循環(huán)隊(duì)列用數(shù)組Am

5、axsize 表示，下面哪個(gè)選項(xiàng)表示該循環(huán)隊(duì)列隊(duì)滿 （）A rear=maxsize-1 Bfront=（rear+1）%maxsizeCrear-t=maxsize Drear-ft=maxsize-12 元素的入棧序列是a，b，c，d，則棧的不可能的輸出序列是 （ ）Adcba BabcdCdcab Dcbad3 高度為3的完全二叉樹最多有 個(gè)節(jié)點(diǎn)，最少有 個(gè)節(jié)點(diǎn) （ ）A7，8B 4，7C7，4D8，74 堆的形狀是一顆（ ）A 二叉排序樹 B 滿二叉樹 C 完全二叉樹 D 平衡二叉樹5 從n個(gè)未排序的數(shù)中，找出處在中間位置的元素的計(jì)算時(shí)間復(fù)雜度為（ ）A O（1）B O（n）C O（）

6、D O（）6 線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（ ）。A 必須是連續(xù)的B 部分地址必須是連續(xù)的C 一定是不連續(xù)的D 連續(xù)不連續(xù)都可以7 線性表是具有n個(gè)（ ）的有限序列（n0）A 表元素 B.字符 C 數(shù)據(jù)元素D 數(shù)據(jù)項(xiàng)8 設(shè)有一個(gè)二維數(shù)Amn，假設(shè)A00存放位置在644（10），A22存放位置在676（10），每個(gè)元素占一個(gè)空間，則A45在（ ）位置，（10）表明用10進(jìn)數(shù)表示。 A 692（10） B 626（10） C 709（10） D 724（10）9 不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（ ）A head=NULLB head-next=NULLC h

7、ead-next=headD head!=NULL10 在循環(huán)雙鏈表的p所指結(jié)點(diǎn)之后插入s所指結(jié)點(diǎn)的操作是（ ）。A p-right=s;s-left=p;p-right-left=s;s-right=p-right;B p-right=s;p-right-left=s;s-left=p;s-right=p-right;C s-left=p;s-right=p-right;p-right=s;p-right-left=s;D s-left=p;s-right=p-right;p-right-left=s;p-right=s;11 若在線性表中采用折半查找法查找元素，該線性表應(yīng)該：（ ）A 元素

8、按值有序B 采用順序存儲(chǔ)結(jié)構(gòu)C 元素按值有序，且采用順序存儲(chǔ)結(jié)構(gòu) D 元素按值有序，且采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)12 下列哪一個(gè)程序片斷是刪除鏈表中間點(diǎn)。（假設(shè)欲刪除結(jié)點(diǎn)為Pointer結(jié)點(diǎn)，Back為前一個(gè)結(jié)點(diǎn)）（ ）A free（Pointer）;B free（Back）;C Back=Pointer-next;D Back-next=Pointer-next; free（Pointer）; free（Pointer）;13 用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷（DFS）算法類似于二叉樹的（ ）A 先序遍歷 B 中序遍歷C 后序遍歷 D 按層次遍歷14 若已知一個(gè)棧的入棧序列是1，2，3，4.，n，其輸出

9、序列為p1，p2，p3，p4，.，pn，若p1=n，則pi為（ ）。A iB n=iC n-i+1D 不確定15（ ）排序的比較次數(shù)與記錄的初始排列狀態(tài)無關(guān)。 A 插入 B 冒泡 C 選擇 D 快速16 用鏈表仿真隊(duì)列時(shí)，隊(duì)空的條件是（ ）A front= =rear B rear0C 沒有 D front= =NULL17 有一子函數(shù)如下： int X（int n） if（nnext=p; p-next=s. B s-next =p-next ; p-next=s.C s-next =p-next; p=s D p-next=s; s-next=p10 在雙向鏈表指針p的結(jié)點(diǎn)前插入一個(gè)指針q

10、的結(jié)點(diǎn)操作是 （ ）A p-Llink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q；B p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink;C q-Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=q;p-Llink=q;D q-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q;11 用鏈表仿真棧時(shí)，棧滿的條件是（ ）A top=0 B top！=0 C 沒有 D topNULL12 數(shù)組用來表示一個(gè)循環(huán)隊(duì)列，為當(dāng)前隊(duì)列頭元素的前一位置，為隊(duì)尾元素

11、的位置，假定隊(duì)列中元素的個(gè)數(shù)小于，計(jì)算隊(duì)列中元素的公式為（ ）rf （nfr）% n nrf （nrf）% n13 下列關(guān)鍵字序列中，（ ）是堆。 16， 72， 31， 23， 94， 53 94， 23， 31， 72， 16， 53 16， 53， 23， 94，31， 72 16， 23， 53， 31， 94， 7214 若需在O（nlog2n）的時(shí)間內(nèi)完成對(duì)數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是（）A 快速排序 B 堆排序 C 歸并排序 D 直接插入排序15 關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（ ）。A 從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑 B 從源點(diǎn)到匯點(diǎn)的最短路徑C 最長(zhǎng)回路 D 最短回

12、路16 設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（ ）條邊。A n-1 B n（n-1）/2 C n（n+1）/2 D 0 E n217 將下圖的二叉樹按中序線索化，結(jié)點(diǎn)X的右指針和Y的左指針分別指向（ ）AA，D BB，C C D，A DC，A 圖10.5 17題圖 圖10.6 18題圖18 已知一個(gè)圖如圖所示，若從頂點(diǎn)a出發(fā)按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為 （ ） A a，b，e，c，d，f B a，c，f，e，b，dC a，e，b，c，f，d D a，e，d，f，c，b19 已知廣義表LS（a，b，c），（d，e，f），運(yùn)用head和tail函數(shù)取出LS中原子e的運(yùn)算是（

13、 ）A head（tail（LS） B tail（head（LS）C head（tail（head（tail（LS） D head（tail（tail（head（LS）20 若串S1=ABCDEFG， S2=9898 ，S3=#，S4=，執(zhí)行concat（replace（S1，substr（S1，length（S2），length（S3），S3），substr（S4，index（S2，8），length（S2）其結(jié)果為。 （ ）A ABC#G0123 B ABCD#2345 C ABC#G2345 D ABC#2345 E ABC#G1234 F ABCD#1234 G ABC#01234四、

14、簡(jiǎn)答題說明：共5小題，每小題8分，滿分40分1 試求以下稀疏數(shù)組壓縮后的數(shù)組內(nèi)容。 0 0 1 0 8 0 0 0 0 0 0 0 0 4 0 3 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 5 0 0 0 00 0 0 0 0 0圖10.7 1題圖2 線性表有兩種存儲(chǔ)結(jié)構(gòu)：一是順序表，二是鏈表。試問：（1）如果有 n個(gè)線性表同時(shí)并存，并且在處理過程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)變化，線性表的總數(shù)也會(huì)自動(dòng)地改變。在此情況下，應(yīng)選用哪種存儲(chǔ)結(jié)構(gòu)？ 為什么？（2）若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應(yīng)采用哪種存儲(chǔ)結(jié)構(gòu)？為什么？3 將右面的樹轉(zhuǎn)換成對(duì)應(yīng)的二叉樹，并寫出其中序遍歷的順序。圖10.8 3題圖4 下圖是帶權(quán)的有向圖G，求：（1）用鄰接表表示法表示此有向圖；（2）從結(jié)點(diǎn)A到結(jié)點(diǎn)I的最短路徑；圖10.9 4題圖5 選取哈希函數(shù)H（key）key Mod 11，用線性探測(cè)再散列開放定址法解決沖突。試在010的散列地址空間內(nèi)對(duì)關(guān)鍵字序列19、11、31、23、17、27、41、13、91、61構(gòu)造哈希表，并計(jì)算在等概率下成功查找的平均查找長(zhǎng)度。 五、算法題說明：共2小題，每小題10分，滿分20分。以下題目的算法可以用C語言函數(shù)表達(dá)，也可以用偽代碼描述。1 試寫出一個(gè)函數(shù)，實(shí)現(xiàn)“計(jì)算二叉樹所有葉子節(jié)點(diǎn)