數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)總結(jié)計劃思考題

《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)思慮題一、基礎(chǔ)題題目答案數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容是：非數(shù)值計算程序設(shè)計中數(shù)據(jù)的（①）和（②）以及它們之間（③）方法。①C①A.操作對象B.計算方法C.邏輯結(jié)構(gòu)D.數(shù)據(jù)映像②D②A.計算方法B.數(shù)據(jù)映像C.分類方法D.儲存結(jié)構(gòu)③B③A.鏈接與關(guān)系B.關(guān)系與算法C.數(shù)據(jù)映像D.計算方法一棵含18個結(jié)點的二叉樹的高度起碼為()CA.3B.4C.5D.6算法剖析的主要目的是對（①）和（②）兩個方面進(jìn)行評論。①C①A.數(shù)據(jù)儲存的合理性B.算法選擇的簡單性②AC.算法的空間復(fù)雜度D.算法過程的邏輯性②A.算法的時間復(fù)雜度B.算法選擇的簡單性C.算法的空間復(fù)雜度D.算法的正確性與簡單性擁有屢次插入刪除操作的線性表，應(yīng)采納（）儲存結(jié)構(gòu)效率較高。BA.矩陣B.鏈表C.數(shù)組D.結(jié)構(gòu)無向圖中一個極點的度是指圖中()BA.經(jīng)過該極點的簡單路徑數(shù)B.與該極點相毗鄰的極點數(shù)C.經(jīng)過該極點的回路數(shù)D.與該極點連通的極點數(shù)以下程序段的時間復(fù)雜度數(shù)目級為__________。O(log3nk=1;)while(k<=n){k=k*3;}從算法設(shè)計的簡單性、時間復(fù)雜性和空間復(fù)雜性等多種角度考慮，你以為實現(xiàn)圖深度優(yōu)先遍歷過程的控制，采納（）作為算法協(xié)助儲存結(jié)構(gòu)最合B適。A.行列B.貨倉C.單向環(huán)形鏈表D.雙向循環(huán)鏈表一個棧的數(shù)據(jù)入棧次序為：ABCDE，指出不行能的出棧序列為（）。CA.EDCBAB.DECBAC.DCEABD.ABCDEhead為無頭結(jié)點單向向后鏈表，判斷head為空表的判斷條件是（）AA．head==NULLB．head=0C．head-→data==0D．head→next==NULL循環(huán)行列定義為：intA[m];使用A[0]至A[m-1]A作為數(shù)據(jù)儲存區(qū)，已知頭尾指針分別為front和rear，表示行列中有效數(shù)據(jù)元素總數(shù)（一個正整數(shù)）的表達(dá)式是（）。A.（rear-front+m）%mB.rear–front+1C.rear–front-1D.(rear–front)%m帶頭結(jié)點的單鏈表head為空表的判斷條件是（）。CA.head->next!=NULLB.head!=NULLC.head->next==NULLD.head==NULL一貨倉數(shù)據(jù)進(jìn)棧的序次為：1，2，3，4，5確立下述結(jié)果中錯誤的選項是（）。DA.5,4,3,2,1B.1,2,3,4,5C.2,3,1,5,4D.3,1,2,4,5依據(jù)數(shù)據(jù)元素的重點字能夠直接確立記錄素儲存地點的方法稱為（）。A．鏈接儲存方法B．次序儲存方法C．散列儲存方法D．索引儲存方法算法剖析的目的是（）。A．鑒識數(shù)據(jù)結(jié)構(gòu)的合理性B．評論算法的效率C．研究算法中輸入與輸出的關(guān)系D．鑒識算法的可讀性在線性表的以下運算中，不改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運算是（）。A．插入B．刪除C．排序D．定位在按層次遍歷二叉樹的算法中，借助（）協(xié)助數(shù)據(jù)結(jié)構(gòu)比較適合。A．行列B．棧

CBDAC．線性表D．有序表在以下排序方法中，均勻時間性能為O(nlogn)且空間性能最好的是( )BA.迅速排序B.堆排序C.合并排序D.基數(shù)排序若用數(shù)組s[0..n-1]作為兩個棧s1和s2的共用儲存空間，且僅當(dāng)s[0..n-1]全滿時，各棧才不可以進(jìn)前進(jìn)棧操作。為這兩個棧選擇空間利用的最正確方案，問s1和s2棧頂指針的初值分別為（）能更好地利用供給的儲存空間？A．1和n+1B．1和n/2C．－1和nD．－1和n+1假如求一個連通圖中以某個極點為根的高度最小的生成樹，應(yīng)采納（）。A．深度優(yōu)先搜尋算法B．廣度優(yōu)先搜尋算法C．求最小生成樹的prim算法D．拓?fù)渑判蛩惴：托辛卸际牵ǎ?。A．限制存取地點的線性結(jié)構(gòu)B．次序儲存的線性結(jié)構(gòu)C．鏈?zhǔn)絻Υ娴木€性結(jié)構(gòu)D．限制存取地點的非線性結(jié)構(gòu)若用毗鄰矩陣表示一個有向圖，則此中每一列包含的″1″的個數(shù)為（）。A．圖中每個極點的入度B．圖中每個極點的出度C．圖中弧的條數(shù)D．圖中連通重量的數(shù)目在一個帶權(quán)連通圖G中，權(quán)值最小的邊必定包含在G的（）中。A．最小生成樹B．深度優(yōu)先遍歷樹C．廣度優(yōu)先遍歷樹D．深度優(yōu)先生成叢林假如在排序過程中，每次均將一個待排序的記錄按重點字大小加入到前面已經(jīng)有序的子表中的適合地點，則該排序方法稱為（）。A．插入排序B．合并排序C．冒泡排序D．堆排序二、操作題題目答案對給定字符集和相應(yīng)權(quán)重，結(jié)構(gòu)Huffman樹并確立每個字符的Huffman編碼，給出huffman答案:樹的帶權(quán)路徑長度。樹的邏輯結(jié)構(gòu)：節(jié)點ETADU權(quán)重1012794

CBABAA編碼：U:000（3位）D:001（3位）e:01（2位）a:11（2位）t:10（2位）樹的帶權(quán)路徑長度：97給定數(shù)據(jù)序列：6,3,9,5,7,8,2,1,4,12，按要求達(dá)成以下題目。答案：（1）結(jié)構(gòu)排序二叉樹，畫出排序二叉樹的邏輯結(jié)構(gòu)；（1）二叉樹的邏輯結(jié)構(gòu)（2）給出該二叉樹先序、中序和后序遍歷的節(jié)點序列。（2）遍歷結(jié)果先序：6-3-2-1-5-4-9-7-8-12中序：1-2-3-4-5-6-7-8-9-12后序：1-2-4-5-3-8-7-12-9-6（3）選作題參照答案使用左子樹右下角節(jié)點替代使用右子樹左下角節(jié)點替代對指定的二叉樹，寫出二叉樹次序儲存方式的節(jié)點次序（包含空位）、先根遍歷的節(jié)點次序、中根答案:遍歷的節(jié)點次序、后根遍歷的節(jié)點次序。0123456789ABCDEFG10111213141516171819HIJ先序：ABDEGHCFIJ中序：DBGEHACIFJ后序：DGHEBIJFCA節(jié)點次序儲存的節(jié)點次序012345678910111213141516171819先序：中序：后序：對給定的圖，按要求達(dá)成以下題目。答案：（1）寫出圖的毗鄰矩陣，毗鄰表；（1）毗鄰矩陣：（2）寫出從節(jié)點V6出發(fā)深度優(yōu)先與廣度優(yōu)先遍歷的節(jié)點序列。結(jié)點12345611025223348456475毗鄰表：出邊結(jié)點1236233^4365^6145入邊結(jié)點162131244656614（2）遍歷結(jié)果：深度優(yōu)先：v6—v1—v2—v3—v4—v5廣度優(yōu)先：v6—v1—v4—v5—v2—v3對以下無向連通圖給出圖最小生成樹的邏輯結(jié)構(gòu)；給出求解的操作過程，說明所依照的算法最小生成樹：（結(jié)果的形式不獨一）（克魯斯卡爾，普利姆？）判斷以下數(shù)據(jù)是不是堆？說明判斷方法？數(shù)據(jù)以下：答案：5，23，16，68，94，72，71，73，是小根堆，按二叉樹次序儲存結(jié)構(gòu)確立堆的邏輯結(jié)果，并判斷：對以下無向連通圖給出圖最小生成樹的邏輯結(jié)構(gòu)，并寫出從V1到其余各點最短路徑的組成與路徑答案：長度。（1）最小生成樹：對給定的數(shù)據(jù)序列{19,01,23,14,55,20,84,27,68,11,10,77}，使用指定Hash函數(shù)和矛盾解決方法，寫出數(shù)據(jù)序列的最后儲存結(jié)果。Hash(key)=key%13使用線性探測再散列方法解決矛盾，在0-13地點空間內(nèi)散列儲存數(shù)據(jù)序列中數(shù)據(jù)012345678910111213對指定的圖，寫出全部可能的拓?fù)湫蛄小?/p>

（2）最短路徑v1-v2：3v1-v3：5v1-v4：4v1-v5：51-4-5v1-v6：4答案：01234567891111012311526128211745789043107答案：2—1—3—4—6—5已知帶權(quán)圖的毗鄰表以下所示，按要求達(dá)成以下題目。答案：1）給出該圖的邏輯結(jié)構(gòu)；2）給出該圖從V0出發(fā)深度優(yōu)先遍歷和廣度優(yōu)先遍歷結(jié)果；3）寫出從極點V0到其余各極點的最短路徑。0123450∞1210∞301001∞∞∞∞∞∞2∞∞∞50∞∞3∞∞∞∞∞104∞∞∞20∞605∞∞∞∞∞∞深度優(yōu)先遍歷：V0—V1—V2—V3—V5—V4廣度優(yōu)先遍歷：V0—V1—V2—V4—V5—V3單源最短路徑：V0V1V0—V1：12V2V0—V2：10V3V0—V4—V3：50V4V0—V4：30V5V0—V4—V3—V5：60已知待散列的線性表為（36，15，40，63，22），散列用的一維地點空間為[0..6]，假設(shè)采納的散答案：列函數(shù)是H（K）=Kmod7，若發(fā)生矛盾采納線性探查法辦理，按要求達(dá)成以下題目。（1）散列結(jié)果：（1）計算出每一個元素的散列地點并在以下圖中填寫出散列表；012340123456566336152240（2）求出在查找每一個元素概率相等狀況下的均勻查找長度。（提示依據(jù)各個重點字的散列操作計算過程：次數(shù)計算均勻定位查找次數(shù)）。設(shè)一組記錄重點字序列為（80，70，33，65，24，56，48），將數(shù)據(jù)序列調(diào)整為小根堆，寫出獲得數(shù)據(jù)序列，并給出小根堆二叉樹的邏輯圖。

H(36)=36mod7=1;H(15)=15mod7=1;矛盾H１(15)=(1+1)mod7=2;H(40)=40mod7=5;H(63)=63mod7=0;5)H(22)=22mod7=1;矛盾H１(22)=(1+1)mod7=2;矛盾H2(22)=(2+1)mod7=3;（2）ASL=121131.65答案：(24，65，33，80，70，56，48)原始二叉樹：調(diào)整后的二叉樹：已知二叉樹的先序序列和中序序列分別為（1）畫出該二叉樹；

HDABCGFE

和ADCBHFEG

，按要求達(dá)成以下題目。

答案：（1）二叉樹邏輯結(jié)構(gòu)：2）給出二叉樹后序遍歷的結(jié)果；3）給出該二叉樹次序儲存的邏輯結(jié)構(gòu)圖。（2）后序遍歷結(jié)果ACBDEFGH（3）次序儲存結(jié)構(gòu)圖0123456789HDGABFC10111213141516E給出下述圖所能組成的全部拓?fù)湫蛄小４鸢福篤0—V1—V2—V3—V4—V5V0—V2—V1—V3—V4—V5三、程序設(shè)計題目

答案達(dá)成知足下述要求的排序函數(shù)（填空或獨立達(dá)成一個擁有同樣方法功能的函數(shù)）

：

答案：intPartition（intr[],intlow,inthigh）{intkey;key=r[low];while(____(1)____)//從表的兩頭，向中間掃描{while(low<high&&r[high]>=key)high--;_____(2)______;//將小于key數(shù)據(jù)挪動到地區(qū)低段while(_________(3)_______)low++;_____(4)______;//將大于key數(shù)據(jù)挪動到地區(qū)高段}r[low]=key;returnlow;//返回定位key數(shù)據(jù)地點

IntPartition（intr[],intlow,inthigh）{intkey;key=r[low];while(low<high)//從表的兩頭，向中間掃描{while(low<high&&r[high]>=key)high