《數(shù)據(jù)結(jié)構(gòu)與算法》復(fù)習(xí)題A（專升本）

PAGE2《數(shù)據(jù)結(jié)構(gòu)與算法》復(fù)習(xí)題A（專升本）一、填空題1、數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R），其中D是的有限集合，R是D上的有限集合。數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的、數(shù)據(jù)的和數(shù)據(jù)的這三個方面的內(nèi)容。寫出帶頭結(jié)點的雙向循環(huán)鏈表L為空表的條件。在具有n個元素的循環(huán)隊列中，隊滿時具有個元素。求子串在主串中首次出現(xiàn)的位置的運算稱為。由3個結(jié)點所構(gòu)成的二叉樹有種形態(tài)。數(shù)據(jù)的邏輯結(jié)構(gòu)是指。選擇題1、若某線性表中最常用的操作是取第i個元素和找第i個元素的前驅(qū)，則采用（）存儲方法最節(jié)省時間。A.順序表B.單鏈表 C.雙鏈表 D.單循環(huán)鏈表2、二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹。A.空或只有一個結(jié)點B.高度等于其結(jié)點數(shù)C.任一結(jié)點無左孩子D.任一結(jié)點無右孩子3、計算機算法指的是：（）A.計算方法B.排序方法 C.解決問題的有限運算序列 D.調(diào)度方法4、棧和隊列的主要區(qū)別在于（）。A.它們的邏輯結(jié)構(gòu)不一樣B.它們的存儲結(jié)構(gòu)不一樣C.所包含的運算不一樣D.插入刪除運算的限定不一樣5、為5個使用頻率不等的字符設(shè)計哈弗曼編碼，不可能的方案是（）。A.000,001,010,011,1B.0000,0001,001,01,1C.000,001,01,10,11D.00,100,101,110,1116、用深度優(yōu)先遍歷方法遍歷一個有向無環(huán)圖，并在深度優(yōu)先遍歷算法中按退棧次序打印出相應(yīng)的頂點，則輸出的頂點序列是（）。A.逆拓?fù)溆行駼.拓?fù)溆行駽.無序D.頂點編號次序7、對如圖所示的無向連通網(wǎng)圖從頂點d開始用Prim算法構(gòu)造最小生成樹，在構(gòu)造過程中加入最小生成樹的前4條邊依次是（）。A.（d,f）4,(f,e)2,(f,b)3(b,a)5B.（f,e）2,(f,b)3,(a,c)3(f,d)4C.（d,f）4,(f,e)2,(a,c)3(b,a)5D.（d,f）4,(d,b)5,(f,e)2(b,a)58、在采用線性探測法處理沖突所構(gòu)成的閉散列表上進行查找，可能要探測多個位置，在查找成功的情況下，所探測的這些位置的鍵值（）。A.一定都是同義詞B.一定都不是同義詞C.不一定都是同義詞D.都相同9、二叉排序樹中，最小值結(jié)點的（）。A．左指針一定為空B．右指針一定為空C．左右指針均為空D．左右指針均不為空10、數(shù)據(jù)序列{8，9，10，4，5，6，20，1，2}只能是（）的兩趟排序后的結(jié)果。A.選擇排序B.冒泡排序C.插入排序D.堆排序三、判斷題1、線性表的邏輯順序總是與其物理順序一致。（

）2、當(dāng)待排序序列初始有序時，簡單選擇排序的時間復(fù)雜性為O(n)。（

）3、對稀疏矩陣進行壓縮存儲是為了節(jié)省存儲空間。（）4、邊數(shù)很少的稀疏圖，適宜用鄰接矩陣表示。（

）5、二叉樹是一棵無序樹。(

)

6、對于一棵具有n個結(jié)點，其高度為h的二叉樹，進行任一種次序遍歷的時間復(fù)雜度為O(n)。(

)

7、當(dāng)待排序序列初始有序時，快速排序的時間復(fù)雜性為O(n)。（

）8、順序表的空間利用率高于鏈表。（

）9、哈希查找法中解決沖突問題的常用方法是除留余數(shù)法。（

）10、順序查找法適用于存儲結(jié)構(gòu)為順序或鏈接存儲的線性表。（

）

四、名詞解釋1、數(shù)據(jù)：2、存儲結(jié)構(gòu)分為：3、算法的五個重要特性：棧：完全二叉樹：五、簡答題1、由二叉樹的中序序列及前序序列能唯一的建立二叉樹，試問前序序列及后序序列是否也能唯一的建立二叉樹，不能則舉例說明理由。2、關(guān)鍵碼集合{47,7,29,11,16,92,22,8,3}，散列函數(shù)為H(key)=keymod11，用拉鏈法處理沖突，構(gòu)造開散列表，并求查找成功時的平均查找長度。3.已知數(shù)據(jù)序列為（12，5，9，20，6，31，24），對該數(shù)據(jù)序列進行排序，寫出簡單選擇排序以及快速排序每趟的結(jié)果。4、程序分析填空題（1）函數(shù)GetElem實現(xiàn)返回單鏈表的第i個元素，請在空格處將算法補充完整。intGetElem(LinkListL,inti,Elemtype*e){LinkListp;intj;p=L->next;j=1;while(p&&j<i){(1);++j;}if(!p||j>i)returnERROR;*e=(2);returnOK;}（2）、函數(shù)實現(xiàn)單鏈表的插入算法，請在空格處將算法補充完整。intListInsert(LinkListL,inti,ElemTypee){LNode*p,*s;intj;p=L;j=0;while((p!=NULL)&&(j<i-1)){p=p->next;j++;}if(p==NULL||j>i-1)returnERROR;s=(LNode*)malloc(sizeof(LNode));s->data=e;(1);(2);returnOK;}/*ListInsert*/《數(shù)據(jù)結(jié)構(gòu)與算法》復(fù)習(xí)題B（專升本）一、填空題1、數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是和。2、線性結(jié)構(gòu)中元素之間存在關(guān)系，樹形結(jié)構(gòu)中元素之間存在關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系。3、帶頭結(jié)點的單鏈表head為空的條件是。4、兩個串相等的充分必要條件是兩個串的長度相等且。5、二維數(shù)組，可以按照和兩種不同的存儲方式。6、一棵具有257個結(jié)點的完全二叉樹，它的深度為。7、內(nèi)部排序方法按排序采用的策略可劃分為五類：、、、和基數(shù)排序。二、選擇題1、計算機算法必須具備輸入、輸出和（）等5個特性。A.可行性、可移植性和可擴充性 B.可行性、確定性和有窮性C.確定性、有窮性和穩(wěn)定性 D.易讀性、穩(wěn)定性和安全性2、串與普通的線性表相比較，它的特殊性體現(xiàn)在（）。A.順序的存儲結(jié)構(gòu) B.鏈?zhǔn)酱鎯Y(jié)構(gòu)C.數(shù)據(jù)元素是一個字符 D.數(shù)據(jù)元素任意3、以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是（

）。A．循環(huán)隊列

B.

鏈表

C.

哈希表

D.

棧4、以下屬于邏輯結(jié)構(gòu)的是（

）。A．順序表

B.

哈希表

C.有序表

D.單鏈表5、將一棵有100個結(jié)點的完全二叉樹從根這一層開始，每一層上從左到右依次對結(jié)點進行編號，根結(jié)點的編號為1，則編號為49的結(jié)點的左孩子編號為（）。A.98 B.99C.50D.486、已知關(guān)鍵碼序列{78，19，63，30，89，84，55，69，28，83}采用基數(shù)排序，第一趟排序后的關(guān)鍵碼序列為（）A.{19，28，30，55，63，69，78，83，84，89}B.{28，78，19，69，89，63，83，30，84，55}C.{30，63，83，84，55，78，28，19，89，69}D.{30，63，83，84，55，28，78，19，69，89}7、在一個長度為n的順序表中，在第i個元素之前插入一個新元素時，需向后移動（）個元素。A.n-iB.n-i+1 C.n-i-1 D.i8、空串和空格串（）。A.相同B.不相同 C.可能相同D.無法確定9、常對數(shù)組進行兩種基本操作是（）。A.建立和刪除B.索引和修改C.查找和修改D.查找與索引10、二叉樹的深度為k，則二叉樹最多有（）個結(jié)點。A.2kB.2k-1C.2k-1D.2k-1三、判斷題1、

線性表的順序存儲優(yōu)于鏈?zhǔn)酱鎯?。?/p>

）

2、用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中的頂點個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。

(

)3、當(dāng)向一個最小堆插入一個具有最小值的元素時，該元素需要逐層向上調(diào)整，直到被調(diào)整到堆頂位置為止。（）4、采用不同的遍歷方法，所得到的無向圖的生成樹是不同的。（

）

5、有回路的有向圖不能完成拓?fù)渑判颉?

)

6、若讓元素1,2,3依次進棧，則出棧次序1,3,2是不可能出現(xiàn)的情況。（

）7、在線性鏈表中刪除中間的結(jié)點時，只需將被刪結(jié)點釋放。（

）8、線性表若采用鏈?zhǔn)酱鎯Ρ硎?

在刪除時不需要移動元素。（

）9、采用不同的遍歷方法，所得到的無向圖的生成樹總是相同的。（

）10、遞歸的算法簡單、易懂、容易編寫，而且執(zhí)行效率也高。（

）四、名詞解釋1、算法：2、隊列：3、滿二叉樹：連通圖：5、數(shù)據(jù)項：五、簡答題1、已知一棵度為m的樹中有：n1個度為1的結(jié)點，n2個度為2的結(jié)點，……nm個度為m的結(jié)點，問該樹中共有多少個葉子結(jié)點？2、已知一個AOV網(wǎng)如圖所示，寫出所有的拓?fù)湫蛄小?、已知數(shù)據(jù)序列為(12,5,9,20,6,31,24)，對該數(shù)據(jù)序列進行排序，寫出直接插入排序、堆排序每趟的結(jié)果。4、程序分析填空題（1）、函數(shù)ListDelete_sq實現(xiàn)順序表刪除算法，請在空格處將算法補充完整。intListDelete_sq(Sqlist*L,inti){intk;if(i<1||i>L->length)returnERROR;for(k=i-1;k<L->length-1;k++)L->slist[k]=（1）;（2）;returnOK;}（2）函數(shù)實現(xiàn)單鏈表的刪除算法，請在空格處將算法