2021年全國(guó)碩士研究生統(tǒng)一入學(xué)考試自命題試題A卷

1、4/42021年全國(guó)碩士研究生統(tǒng)一入學(xué)考試自命題試題A卷*學(xué)科、專(zhuān)業(yè)名稱(chēng)：網(wǎng)絡(luò)空間安全研究方向：網(wǎng)絡(luò)空間安全083900考試科目名稱(chēng)及代碼：數(shù)據(jù)結(jié)構(gòu)830考生注意：所有答案必須寫(xiě)在答題紙（卷）上，寫(xiě)在本試題上一律不給分。一、 單項(xiàng)選擇題 (每題2分，共20分)1. 以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線(xiàn)性結(jié)構(gòu)？ () A. 二叉樹(shù) B. 棧 C. 線(xiàn)性表 D. 隊(duì)列2. 當(dāng)要對(duì)線(xiàn)性表進(jìn)行折半查找時(shí)，線(xiàn)性表必須滿(mǎn)足以下條件（ ）。A. 以順序方式存儲(chǔ) B. 以鏈表方式存儲(chǔ)C. 以順序方式存儲(chǔ)且按關(guān)鍵字有序排列 D. 以鏈表方式存儲(chǔ)且按關(guān)鍵字有序排列3. 為了提高哈希表的查找效率，以下方法說(shuō)法不正確的是( )

2、。A. 設(shè)計(jì)好的哈希函數(shù) B. 增加哈希函數(shù)的個(gè)數(shù)C. 增大存儲(chǔ)空間 D. 采用更好的地址沖突解決方法4. 用單向鏈表來(lái)實(shí)現(xiàn)容量為n的堆棧時(shí)，鏈表頭指針指向堆棧頂部元素，鏈表尾指針指向堆棧底部元素，則以下說(shuō)法錯(cuò)誤的是（ ）A. 入棧操作的復(fù)雜度為O(1) B.出棧操作的復(fù)雜度為O(1) C. 插入一個(gè)新的堆棧底部元素復(fù)雜度為O(1) D. 刪除底部元素的復(fù)雜度為O(1)5. 設(shè)一個(gè)順序有序的一維數(shù)組A1:14中有14個(gè)元素，采用二分查找算法查找到A4中的元素過(guò)程中需要比較的元素的順序是（）A. A1, A2, A3, A4 B. A7, A3, A5, A4 C. A1, A14, A7, A

3、4 D. A7, A5, A3, A46. 稀疏矩陣一般采用的壓縮存儲(chǔ)方法有兩種，即（） A. 二維數(shù)組和三維數(shù)組 B.三元組和散列 C. 三元組和十字鏈表 D. 十字鏈表和散列7. 設(shè)a, b為一棵二叉樹(shù)上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)先訪(fǎng)問(wèn)a后訪(fǎng)問(wèn)b的條件是（） A. a在B的左邊 B. a在b的右邊 C. a是b的祖先 D. a是b的子孫8. 某二叉樹(shù)的中序序列為ABCDEFG，后序序列為BDCAFGE，則其左子樹(shù)結(jié)點(diǎn)數(shù)為（ ） A. 5B. 4 C. 3 D. 29. 判斷一個(gè)有向圖中是否存在環(huán)（回路），可采用以下方法（） A. 廣度優(yōu)先遍歷 B. 求關(guān)鍵路徑 C. 求最短路徑 D. 拓?fù)渑?/p>

4、序10. 用哈希表存儲(chǔ)7個(gè)整數(shù)18,25,63,50,42,32,9, 如果哈希函數(shù)為H(x)=x mod 9，則與18發(fā)生地址沖突的整數(shù)有（）個(gè) A. 1 B. 2 C. 3 D. 4二、填空題 (每空2分，共20分)1. 數(shù)據(jù)結(jié)構(gòu)的三要素是指（ ）（ ）（ ）。2. 在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)（ ），具體移動(dòng)的元素個(gè)數(shù)與（ ）有關(guān)。3. 設(shè)棧S與隊(duì)列Q的初始狀態(tài)皆為空，元素a1,a2,a3,a4,a5和a6依次通過(guò)一個(gè)棧，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素出隊(duì)列的順序是a3,a5,a4,a6,a2,a1,則棧S至少應(yīng)該容納（ ）個(gè)元素。4. 有一個(gè)10階對(duì)稱(chēng)矩陣A，采用

5、壓縮存儲(chǔ)方式（以行序?yàn)橹?，且A00=1）,則A85的地址是（ ）5. 含有100個(gè)結(jié)點(diǎn)的樹(shù)有（ ）條邊。 6. 已知二叉樹(shù)的前序序列為ABDEGCFHIJ，中序序列為DBGEAHFIJC，請(qǐng)寫(xiě)出后序列（ ）。7. 在一個(gè)無(wú)向圖的鄰接表中，若表結(jié)點(diǎn)數(shù)目為m，則圖中邊的條數(shù)為（ ）。三判斷題（每題2分，共20分，正確的選T，錯(cuò)誤的選F）通過(guò)使用線(xiàn)性鏈表來(lái)實(shí)現(xiàn)堆棧，可以使得每次入棧/出棧操作的時(shí)間復(fù)雜度為O(1)。（ ）深度優(yōu)先搜索的核心數(shù)據(jù)結(jié)構(gòu)是隊(duì)列。（）將包含n個(gè)元素的升序線(xiàn)性鏈表改成降序線(xiàn)性鏈表所需要的時(shí)間復(fù)雜度為O(n)。（）選擇排序算法是穩(wěn)定的。（）一棵高度為h的完全二叉樹(shù)的結(jié)點(diǎn)數(shù)量比同樣

6、高度的一棵滿(mǎn)二叉樹(shù)的結(jié)點(diǎn)要多。（ ）平衡二叉樹(shù)（AVL）的優(yōu)點(diǎn)是能夠保證在最壞情況下的查找時(shí)間復(fù)雜度為O(logN)。（ ）無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)的，因此只需要存儲(chǔ)矩陣的下三角陣以節(jié)省存儲(chǔ)空間。 ( )一棵高度為h的完全二叉樹(shù)可能的最大結(jié)點(diǎn)個(gè)數(shù)為2h個(gè)。（）在快速排序、冒泡排序、希爾排序、堆排序中，空間復(fù)雜度最高的是快速排序。（）將一棵樹(shù)轉(zhuǎn)化成一棵二叉樹(shù)，則該二叉樹(shù)的右子樹(shù)不一定為空。（）四、簡(jiǎn)答題（共40分）1.描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元結(jié)點(diǎn)（第一個(gè)元素結(jié)點(diǎn)）。（6分）2.簡(jiǎn)述線(xiàn)性表、隊(duì)列和堆棧這三種數(shù)據(jù)類(lèi)型的相同點(diǎn)和差異處。 （6分）3. 在程序設(shè)計(jì)中，可采用下列三種方法

7、實(shí)現(xiàn)輸出和輸入: （1）通過(guò) scanf 和 printf 語(yǔ)句;(2) 通過(guò)函數(shù)的參數(shù)顯式傳遞; (3) 通過(guò)全局變量隱式傳遞。試討論這三種方法的優(yōu)缺點(diǎn)。（6分）4.試著描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類(lèi)型的概念與程序設(shè)計(jì)語(yǔ)言中數(shù)據(jù)類(lèi)型概念的區(qū)別。（6分）5.試寫(xiě)出一種算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線(xiàn)性表操作Length(L)。（8分）6.請(qǐng)用順序存儲(chǔ)的方式，用C語(yǔ)言寫(xiě)出實(shí)現(xiàn)把串S1復(fù)制到串S2的串復(fù)制函數(shù)strcpy（S1，S2）。（8分）五、算法填空（共2小題，每空2分，共20分）1. 假設(shè)有一棵二叉查找樹(shù)，其每個(gè)結(jié)點(diǎn)包含鍵值key、左孩子指針left和右孩子指針right，指針p指向該二叉樹(shù)的

8、根結(jié)點(diǎn)?，F(xiàn)要查找鍵值為x的結(jié)點(diǎn)，如果該二叉樹(shù)中存在鍵值為x的結(jié)點(diǎn)，則返回指向該結(jié)點(diǎn)的指針；如果不存在，則返回空指針NULL。請(qǐng)?zhí)顚?xiě)下面C代碼中空白的部分，使其成為完整的算法以完成對(duì)二叉樹(shù)的查找。SearchBinaryTree(p, x) if (p = NULL | （1） ) return p; if (2) return (3)_; else return (4) ;請(qǐng)將以上空白處的答案填寫(xiě)在下面對(duì)應(yīng)位置： 2給定一個(gè)單向鏈表L，鏈表中的結(jié)點(diǎn)按照鍵值大小升序排列。以下的代碼可以將L中所有鍵值相同的結(jié)點(diǎn)從L中刪除，請(qǐng)將代碼中空白處填寫(xiě)完整。Struct node int key; node

9、 *next;int DeleteDuplicate(node *L) node *p, *q; if (L = NULL | L-next =NULL) return -1;p = L;q = p-next;while (p-next != NULL) if (p-key != q-key)（1） ;（2） ; else while (（3） ) node *tmp = q-next; delete q;（4） ; if (q = NULL) break; if (q != NULL)（5） ; p = p-next; q = p-next; else（6） ; 請(qǐng)將以上代碼的空白處答案填寫(xiě)在下方相應(yīng)位置： (1) (2) (3) (4) (5) (6) 六編寫(xiě)算法（30分）1.假設(shè)稱(chēng)正讀和反讀都相同的字符序列為 “回文”，例如， abba和abcba是回文， abcde和ababab 則不是回文。試寫(xiě)一個(gè)算法判別讀入的一個(gè)以 為結(jié)束符的字符序列是否是 “回文”。（10分）2. 已知由一個(gè)線(xiàn)性