暨南大學(xué)2020年《830數(shù)據(jù)結(jié)構(gòu)》研究生入學(xué)考試真題

1、考試科目：數(shù)據(jù)結(jié)構(gòu) 9/92020年全國碩士研究生統(tǒng)一入學(xué)考試自命題試題B卷*學(xué)科、專業(yè)名稱：網(wǎng)絡(luò)空間安全研究方向：網(wǎng)絡(luò)空間安全083900考試科目名稱及代碼：數(shù)據(jù)結(jié)構(gòu)830考生注意：所有答案必須寫在答題紙（卷）上，寫在本試題上一律不給分。 一、 單項(xiàng)選擇題(每題2分，共30分) 1. 下述關(guān)于順序存儲(chǔ)結(jié)構(gòu)優(yōu)點(diǎn)的說法，哪個(gè)是正確的（ ）A. 插入運(yùn)算方便 B. 可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示C. 存儲(chǔ)密度大 D. 刪除運(yùn)算方便2. 假設(shè)根結(jié)點(diǎn)為第1層，深度為h層的二叉樹至少有( ) 個(gè)結(jié)點(diǎn)(h1)； A. 2h B. 2h-1 C. 2h+1 D. 2h-13. 用單向鏈表來實(shí)現(xiàn)容量為n的

2、堆棧時(shí)，鏈表頭指針指向堆棧頂部元素，鏈表尾指針指向堆棧底部元素，則以下說法錯(cuò)誤的是( )A. 入棧操作的復(fù)雜度為O(1) B. 出棧操作的復(fù)雜度為O(1) C. 刪除底部元素的復(fù)雜度為O(1) D. 插入一個(gè)新的堆棧底部元素復(fù)雜度為O(1)4. 以下關(guān)于遞歸算法的論述，不正確的是( )A. 遞歸算法的代碼可讀性好 B. 遞歸算法可以提高程序運(yùn)行效率C. 遞歸調(diào)用層次太深有可能造成堆棧溢出 D. 遞歸調(diào)用層次太深會(huì)占用大量內(nèi)存5. 設(shè)有字符集合4,6,3,W,S，將字符序列6W43S中的字符按順序進(jìn)入堆棧，出?？砂l(fā)生在任何時(shí)刻。則以下的出棧序列錯(cuò)誤的是（ ）。 A. 64WS3 B. 4W36S

3、 C. 6W34S D. WS4366. 在管理城市道路交通網(wǎng)絡(luò)據(jù)時(shí)，最適合采用（ ）數(shù)據(jù)結(jié)構(gòu)來對(duì)其進(jìn)行存儲(chǔ)。A有向圖 B無向圖 C樹 D矩陣7. 具有k個(gè)頂點(diǎn)的完全有向圖的邊數(shù)為( )。 A. k(k-1) B. k(k-1)/2 C. k2-1 D. k2+1 8. 若線性表最常用的操作是增加或者刪除某個(gè)元素, 則采用( )存儲(chǔ)方式節(jié)省時(shí)間.A. 單鏈表 B. 雙鏈表 C. 單循環(huán)鏈表 D. 順序表9. 由權(quán)為6,3,2,8的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一個(gè)哈夫曼樹，該樹的帶權(quán)路徑長度為（ ）。A. 36 B. 35 C. 34 D. 3310. 為了提高哈希表的查找效率，以下方法說法不正確的是( )

4、。A. 設(shè)計(jì)好的哈希函數(shù) B. 增加哈希函數(shù)的個(gè)數(shù) C. 增大存儲(chǔ)空間 D. 采用更好的地址沖突解決方法11. 以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？( ) A. 隊(duì)列 B. 棧 C. 線性表 D. 二叉樹12. 對(duì)于一個(gè)整數(shù)集合11，37，29，55，80，46，73，17進(jìn)行散列存儲(chǔ)時(shí)，若選用函數(shù)H（K）= K %9作為散列(哈希)函數(shù)，則散列地址為1的元素有（ ）個(gè)。 A3 B4 C5 D613. 有一個(gè)100*90的整數(shù)稀疏矩陣，其中非0元素個(gè)數(shù)為10；設(shè)每個(gè)整數(shù)占用3個(gè)字節(jié)，則用三元組表示該矩陣時(shí)，總共需要的存儲(chǔ)空間為( )字節(jié)。A30 B33 C90 D9914. 在一個(gè)雙向鏈表中，當(dāng)

5、刪除結(jié)點(diǎn)p時(shí)，錯(cuò)誤的操作序列為 ( )。 A. p=p-prev; p-next-prev=p; p-next=p-next-next; B. p=p-next; p-prev=p-prev-prev; p-prev-next=p; C. p-prev-next=p-next; p-next-prev=p-prev; D. p=p-prev; p-next=p-next-next; p-next-prev=p;15. 在一個(gè)具有V個(gè)頂點(diǎn)的有向連通圖中，若所有頂點(diǎn)的入度數(shù)之和為N，所有頂點(diǎn)的出度之和為M，則以下說法正確的是（ ）。AV=(M+N)/2 BMV CM=N DNV二、填空題(每空2分

6、，共20分)1. 對(duì)n個(gè)不同的排序碼進(jìn)行冒泡排序，在元素?zé)o序的情況下比較的次數(shù)為 。2. 在單鏈表中，要將m所指結(jié)點(diǎn)插入到n所指結(jié)點(diǎn)之后，其語句表示為 。3. 設(shè)有數(shù)組Aij，數(shù)組的每個(gè)元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)用以列為主存放時(shí)，元素A58的存儲(chǔ)首地址為 。4. 設(shè)哈夫曼樹中有199個(gè)結(jié)點(diǎn)，則該哈夫曼樹中有 個(gè)葉子結(jié)點(diǎn)。5. 對(duì)22個(gè)記錄的有序表作折半查找，當(dāng)查找失敗時(shí)候，至多需要比較 次關(guān)鍵字，至少需要比較 次關(guān)鍵字。6. 由3個(gè)結(jié)點(diǎn)可以構(gòu)造出 種不同的二叉樹。7. 最大容量為s的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭是front，則

7、隊(duì)滿的條件是 。8. G是一個(gè)非連通無向圖，共有28條邊，則該圖至少有 個(gè)頂點(diǎn)。9. 數(shù)據(jù)表中有10000個(gè)元素，如果僅要求求出其中最大的10個(gè)元素，則采用 排序算法最節(jié)省時(shí)間。三判斷題（每題1分，共10分，正確的選T，錯(cuò)誤的選F）1. 對(duì)n個(gè)記錄進(jìn)行插入排序，最多只需要O(nlog(n)次兩兩比較。( )2. 用鏈表(Linked list)來實(shí)現(xiàn)的堆棧，單次入棧/出棧操作的時(shí)間復(fù)雜度可達(dá)到O(1)。( )3. 當(dāng)圖G中存在權(quán)重為負(fù)數(shù)的邊時(shí)，Dijkstra算法不能用于計(jì)算G中兩結(jié)點(diǎn)間最短路徑。( )4. 貪婪算法有時(shí)候能夠求出全局最優(yōu)解，有時(shí)候無法求出全局最優(yōu)解。( )5. 對(duì)含有n個(gè)記錄

8、的集合進(jìn)行快速排序，在最壞情況下的時(shí)間復(fù)雜度是O(nlog(n)。 ( )6. 哈希表查找效率高，當(dāng)查找主鍵在范圍a,b內(nèi)所有的記錄時(shí)，也應(yīng)該優(yōu)先選擇哈希表。( )7. 無向圖的鄰接矩陣是對(duì)稱的，因此可只存儲(chǔ)矩陣的下三角陣以節(jié)省存儲(chǔ)空間。 ( )8. 用Prime算法和Kruskal 算法求得的圖的最小生成樹一定相同。( )9. 在一個(gè)有向圖的鄰接表或逆鄰接表中，若某頂點(diǎn)的鏈表為空，則該頂點(diǎn)的度為零。( )10. 在有n個(gè)頂點(diǎn)的無向圖中，若邊數(shù)n-1，則該圖必是連通圖。( ) 四、簡答題（40分）1. 簡述邏輯結(jié)構(gòu)的四種基本關(guān)系并畫出它們的關(guān)系圖。（10分）2. 設(shè)二維數(shù)組 num1.m, 1

9、n含有m*n個(gè)整數(shù)，請(qǐng)分析判斷數(shù)組中元素是否互不相同的算法的時(shí)間復(fù)雜度。（8分）3. 設(shè)待排序的關(guān)鍵字序列為12，2，16，30，28，10，16*，20，6，18 ，請(qǐng)寫出二路歸并排序的方法下，每趟排序結(jié)束后關(guān)鍵字序列的狀態(tài)。（6分）圖1. 有向圖4. 已知圖1所示的有向圖，請(qǐng)給出（1）每個(gè)頂點(diǎn)的入度與出度；（2）鄰接矩陣。（10分）5. 在一棵空的二叉排列樹中依次插入關(guān)鍵字序列為12，7，17，11，16，2，13，9，21，4，請(qǐng)畫出所得到的二叉排列樹。（6分）五、算法填空（共2小題，每空2分，共20分）1. 在漢諾塔(hanoi tower)游戲中，總共有3根柱子和n個(gè)大小不一樣的盤子

10、。初始狀態(tài)時(shí)n個(gè)盤子從小到大堆疊在1號(hào)柱子，下面的遞歸算法偽代碼能夠?qū)⑦@n個(gè)盤子從1號(hào)柱子移動(dòng)到3號(hào)柱子。其中，該遞歸算法滿足以下條件：(1)每次只移動(dòng)1個(gè)盤子，(2)任何一個(gè)盤子只有當(dāng)它上面沒有堆放盤子時(shí)才能移動(dòng)，(3)任何時(shí)刻在任何一個(gè)柱子上永遠(yuǎn)不能出現(xiàn)大盤子堆在小盤子之上的情況。請(qǐng)?jiān)赺處填上適當(dāng)內(nèi)容，使其成為一個(gè)完整的算法。hanoi(from, tmp, to, n) if(n=1) move( (1) , (2) );return;hanoi( (3) );printf ( (%d,%d), from, to );hanoi( (4) );return;2. 假設(shè)一維數(shù)組A保存有N個(gè)

11、整數(shù)，以下快速排序算法代碼能夠?qū)?shù)組A進(jìn)行排序。請(qǐng)?jiān)赺處填上適當(dāng)內(nèi)容，使其成為一個(gè)完整的算法。int partition(int* A, int N, int p, int r) int x = Ar; int i = (5) ; for (int j = p; j=r-1; j+) if ( (6) ) i = i + 1; int temp = Ai;Ai = Aj;Aj = temp; int temp = Ai+1; Ai+1 = Ar; Ar = temp; return (7) ;void QuickSort(int* A, int N, int p, int r) int q; if ( (8) )q = partition(A, N, p, r);QuickSort( (9) );QuickSort( (10) ); return;void main() QuickSort(A, N, 0,N-1); return 0;六編寫算法（30分）1. 寫一個(gè)算法統(tǒng)計(jì)在輸入字符串中各個(gè)不同字符