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

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

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

)

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

)

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

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

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

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

）

四、名詞解釋1、數(shù)據(jù)：2、存儲(chǔ)結(jié)構(gòu)分為：3、算法的五個(gè)重要特性：棧：完全二叉樹：五、簡(jiǎn)答題1、由二叉樹的中序序列及前序序列能唯一的建立二叉樹，試問前序序列及后序序列是否也能唯一的建立二叉樹，不能則舉例說(shuō)明理由。2、關(guān)鍵碼集合{47,7,29,11,16,92,22,8,3}，散列函數(shù)為H(key)=keymod11，用拉鏈法處理沖突，構(gòu)造開散列表，并求查找成功時(shí)的平均查找長(zhǎng)度。3.已知數(shù)據(jù)序列為（12，5，9，20，6，31，24），對(duì)該數(shù)據(jù)序列進(jìn)行排序，寫出簡(jiǎn)單選擇排序以及快速排序每趟的結(jié)果。4、程序分析填空題（1）函數(shù)GetElem實(shí)現(xiàn)返回單鏈表的第i個(gè)元素，請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整。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ù)實(shí)現(xiàn)單鏈表的插入算法，請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整。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)中元素之間存在多對(duì)多關(guān)系。3、帶頭結(jié)點(diǎn)的單鏈表head為空的條件是。4、兩個(gè)串相等的充分必要條件是兩個(gè)串的長(zhǎng)度相等且。5、二維數(shù)組，可以按照和兩種不同的存儲(chǔ)方式。6、一棵具有257個(gè)結(jié)點(diǎn)的完全二叉樹，它的深度為。7、內(nèi)部排序方法按排序采用的策略可劃分為五類：、、、和基數(shù)排序。二、選擇題1、計(jì)算機(jī)算法必須具備輸入、輸出和（）等5個(gè)特性。A.可行性、可移植性和可擴(kuò)充性 B.可行性、確定性和有窮性C.確定性、有窮性和穩(wěn)定性 D.易讀性、穩(wěn)定性和安全性2、串與普通的線性表相比較，它的特殊性體現(xiàn)在（）。A.順序的存儲(chǔ)結(jié)構(gòu) B.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C.數(shù)據(jù)元素是一個(gè)字符 D.數(shù)據(jù)元素任意3、以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)的術(shù)語(yǔ)是（

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

B.

鏈表

C.

哈希表

D.

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

）。A．順序表

B.

哈希表

C.有序表

D.單鏈表5、將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層上從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為49的結(jié)點(diǎn)的左孩子編號(hào)為（）。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、在一個(gè)長(zhǎng)度為n的順序表中，在第i個(gè)元素之前插入一個(gè)新元素時(shí)，需向后移動(dòng)（）個(gè)元素。A.n-iB.n-i+1 C.n-i-1 D.i8、空串和空格串（）。A.相同B.不相同 C.可能相同D.無(wú)法確定9、常對(duì)數(shù)組進(jìn)行兩種基本操作是（）。A.建立和刪除B.索引和修改C.查找和修改D.查找與索引10、二叉樹的深度為k，則二叉樹最多有（）個(gè)結(jié)點(diǎn)。A.2kB.2k-1C.2k-1D.2k-1三、判斷題1、

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

）

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

(

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

）

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

)

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

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

）8、線性表若采用鏈?zhǔn)酱鎯?chǔ)表示,

在刪除時(shí)不需要移動(dòng)元素。（

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

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

）四、名詞解釋1、算法：2、隊(duì)列：3、滿二叉樹：連通圖：5、數(shù)據(jù)項(xiàng)：五、簡(jiǎn)答題1、已知一棵度為m的樹中有：n1個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，……nm個(gè)度為m的結(jié)點(diǎn)，問該樹中共有多少個(gè)葉子結(jié)點(diǎn)？2、已知一個(gè)AOV網(wǎng)如圖所示，寫出所有的拓?fù)湫蛄小?、已知數(shù)據(jù)序列為(12,5,9,20,6,31,24)，對(duì)該數(shù)據(jù)序列進(jìn)行排序，寫出直接插入排序、堆排序每趟的結(jié)果。4、程序分析填空題（1）、函數(shù)ListDelete_sq實(shí)現(xiàn)順序表刪除算法，請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整。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ù)實(shí)現(xiàn)單鏈表的刪除算法，請(qǐng)?jiān)诳崭裉帉⑺惴?/p>