C語言數(shù)據(jù)結構-綜合測試題及答案

1、第10章 綜合測試能力要求（1） 計算機基礎知識：掌握圖的概念以及圖的基本操作。（2） 分析問題：針對具體的問題，要能夠運用圖去進行分析，逐步找到解決問題的方法。（3） 具有概念化和抽象化能力：針對具體的應用和實際的問題，能夠運用圖對問題進行抽象，提取它的邏輯結構和存儲結構。（4） 發(fā)現(xiàn)問題和表述問題：在具體的工程中，能夠發(fā)現(xiàn)工程中涉及到圖的問題，并能夠明確表述。（5） 建模：在具體的工程中，能夠使用圖進行建模，設計合理的數(shù)據(jù)結構和相應的算法。（6） 解決方法和建議：在具體工程應用中，發(fā)現(xiàn)了關于圖的問題，要能夠解決問題，并提出合理的建議。（7） 定義功能，概念和結構：使用圖這種邏輯結構處理一些

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

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

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

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

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

7、D head!=NULL10 在循環(huán)雙鏈表的p所指結點之后插入s所指結點的操作是（ ）。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 若在線性表中采用折半查找法查找元素，該線性表應該：（ ）A 元素按值有序B 采用順序存儲結

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

9、4，.，pn，若p1=n，則pi為（ ）。A iB n=iC n-i+1D 不確定15（ ）排序的比較次數(shù)與記錄的初始排列狀態(tài)無關。 A 插入 B 冒泡 C 選擇 D 快速16 用鏈表仿真隊列時，隊空的條件是（ ）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的結點前插入一個指針q的結點操作是 （ ）A p

10、-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 用鏈表仿真棧時，棧滿的條件是（ ）A top=0 B top！=0 C 沒有 D topNULL12 數(shù)組用來表示一個循環(huán)隊列，為當前隊列頭元素的前一位置，為隊尾元素的位置，假定隊列中元素的個

11、數(shù)小于，計算隊列中元素的公式為（ ）rf （nfr）% n nrf （nrf）% n13 下列關鍵字序列中，（ ）是堆。 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）的時間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是（）A 快速排序 B 堆排序 C 歸并排序 D 直接插入排序15 關鍵路徑是事件結點網(wǎng)絡中（ ）。A 從源點到匯點的最長路徑 B 從源點到匯點的最短路徑C 最長回路 D 最短回路16 設無向圖的頂點個數(shù)

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

13、（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）其結果為。 （ ）A ABC#G0123 B ABCD#2345 C ABC#G2345 D ABC#2345 E ABC#G1234 F ABCD#1234 G ABC#01234四、簡答題說明：共5小題，每小

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