2018年西安建筑科技大學(xué)考研專業(yè)課真題835數(shù)據(jù)結(jié)構(gòu)

1、西安建筑科技大學(xué)2018年攻讀碩士學(xué)位研究生招生考試試題年攻讀碩士學(xué)位研究生招生考試試題(答案書寫在本試題紙上無效?？荚嚱Y(jié)束后本試題紙須附在答題紙內(nèi)交回答案書寫在本試題紙上無效?？荚嚱Y(jié)束后本試題紙須附在答題紙內(nèi)交回))共4頁考試科目:適用專業(yè):（835）數(shù)據(jù)結(jié)構(gòu)一、單項(xiàng)選擇題（共10題，每小題2分，共20分）。計(jì)算機(jī)科學(xué)與技術(shù)、計(jì)算機(jī)技術(shù)、控制工程1、算法分析的目的是（）。A找出數(shù)據(jù)結(jié)構(gòu)的合理性B研究算法中的輸入和輸出關(guān)系C分析算法的效

2、率以求改進(jìn)D分析算法的可讀性和簡(jiǎn)明性2、若一個(gè)順序表中第一個(gè)元素的存儲(chǔ)地址為1000，每個(gè)元素占4個(gè)地址單元，那么，第6個(gè)元素的存儲(chǔ)地址應(yīng)是（）。A1020B1010C1016D10243、帶頭結(jié)點(diǎn)的單鏈表（以head為頭指針）為空的判斷條件是（）。Ahead!=NULLBheadnext==headCheadnext==NULLDhead==NULL4、在一個(gè)單鏈表中，已知q指向p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在p、q所指結(jié)點(diǎn)之間插入一個(gè)s所

3、指向的新結(jié)點(diǎn)，則執(zhí)行的操作是（）。Aqnext=ssnext=pBpnext=ssnext=qCsnext=pnextpnext=sDpnext=snextsnext=p5、在一個(gè)單鏈表中，若刪除p指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行的操作為（）。Aq=pnextpnext=pnextnextfree(q)Bp=pnextq=pnextp=qnextfree(q)Cq=pnextnextp=pnextnextfree(q)Dp=pnextnext

4、q=pnextnextfree(q)6、棧的操作原則是（）。A順序進(jìn)出B后進(jìn)后出C后進(jìn)先出D先進(jìn)先出7、一個(gè)隊(duì)列的入隊(duì)序列是1，3，5，7，9，則出隊(duì)的輸出序列只能是（）。A9，7，5，3，1B1，3，5，7，9C1，5，9，3，7D9，5，1，7，38、將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從根開始，每一層從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為0，則編號(hào)為49的結(jié)點(diǎn)的左孩子編號(hào)為（）。A99B98C50D489、以二叉鏈表作為二叉樹的存

5、儲(chǔ)結(jié)構(gòu)，在具有n個(gè)結(jié)點(diǎn)的二叉鏈表中（n0），空鏈域的個(gè)數(shù)為（）。A2n1Bn1Cn1D2n110、無向圖的鄰接矩陣是一個(gè)（）。A對(duì)角矩陣B對(duì)稱矩陣C上三角矩陣D零矩陣第1頁第2頁二、填空題（共20空，每空1分，共20分）。1、數(shù)據(jù)結(jié)構(gòu)一般包括、和數(shù)據(jù)運(yùn)算三個(gè)方面的內(nèi)容。2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）可以用、存儲(chǔ)方法表示。設(shè)有一批數(shù)據(jù)元素，為了最快地存取某元素，宜用結(jié)構(gòu)存儲(chǔ)；為了方便地插入一個(gè)元素，宜用結(jié)構(gòu)存儲(chǔ)。3、在長度為n的順序表的第

6、i個(gè)位置上插入一個(gè)元素，i的合法范圍是，元素的移動(dòng)次數(shù)為；刪除表中第i個(gè)元素，i的合法范圍是，需要向前移動(dòng)個(gè)元素。4、棧和隊(duì)列都是結(jié)構(gòu)；對(duì)于棧，只能在插入和刪除元素；對(duì)于隊(duì)列，只能在插入元素，在刪除元素。5、假設(shè)以S和X分別表示進(jìn)棧和退棧操作，則對(duì)輸入序列a，b，c，d，e進(jìn)行一系列棧操作SSXSXSSXXX之后，得到的輸出序列為。6、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為，所有鄰接表中的結(jié)點(diǎn)總數(shù)是。

7、7、二分查找的存儲(chǔ)結(jié)構(gòu)僅限于，且是。8、對(duì)于二叉排序樹上的查找，若結(jié)點(diǎn)元素的關(guān)鍵字值大于被查找元素的關(guān)鍵字值，則應(yīng)該在該二叉樹的繼續(xù)查找。三解答題（共7題，共59分）。1、（14分）已知二叉樹如右圖所示。請(qǐng)按要求回答問題：（1）列出該二叉樹的所有葉子結(jié)點(diǎn)。（2）請(qǐng)寫出該二叉樹的先序遍歷序列、中序遍歷序列、后序遍歷序列。（3）請(qǐng)寫出該二叉樹的按層次遍歷序列。（4）將該二叉樹調(diào)整成AVL樹。（5）若該圖為“左孩子－右兄弟”的二叉存儲(chǔ)結(jié)構(gòu)，請(qǐng)

8、畫出該圖所對(duì)應(yīng)的樹（森林）。2、（15分）已知圖G的鄰接表如右圖所示。（1）請(qǐng)畫出該存儲(chǔ)結(jié)構(gòu)對(duì)應(yīng)的圖。（2）請(qǐng)寫出該圖的鄰接矩陣。（3）請(qǐng)寫出該圖的逆鄰接表。（4）請(qǐng)寫出該圖從頂點(diǎn)1出發(fā)的深度優(yōu)先搜索序列。（5）請(qǐng)寫出該圖從頂點(diǎn)1出發(fā)的廣度優(yōu)先搜索序列。123452∧34∧∧∧34∧∧4∧5∧52∧4∧4ebacdf西安建筑科技大學(xué)2018年攻讀碩士學(xué)位年攻讀碩士學(xué)位研究生招生考試試題研究生招生考試試題(答案書寫在本試題紙上無效?？荚嚱Y(jié)

9、束后本試題紙須附在答題紙內(nèi)交回答案書寫在本試題紙上無效?？荚嚱Y(jié)束后本試題紙須附在答題紙內(nèi)交回))共4頁考試科目:適用專業(yè):（835）數(shù)據(jù)結(jié)構(gòu)3、（3分）有一組記錄的關(guān)鍵字序列為46，79，56，38，40，84，利用快速排序的方法，寫出以第一個(gè)記錄為基準(zhǔn)得到的一趟排序結(jié)果。4、（6分）對(duì)于給定的一組關(guān)鍵字41，62，13，84，35，96，57，39，79，61，15，83，寫出執(zhí)行希爾排序算法的第一趟排序結(jié)果，增量為5。5、（4分）對(duì)

10、于給定的一組關(guān)鍵字26，18，60，14，7，45，13，32，寫出執(zhí)行堆排序算法的第一趟排序結(jié)果。6、（8分）已知帶權(quán)圖如下圖所示。（1）請(qǐng)用普里姆（Prim）算法求出該圖的最小生成樹。（2）請(qǐng)用克魯斯卡爾（Kruskal）算法求出該圖的最小生成樹。計(jì)算機(jī)科學(xué)與技術(shù)、計(jì)算機(jī)技術(shù)、控制工程7、（9分）試分析以下3個(gè)程序片段的時(shí)間復(fù)雜度。第3頁第4頁四、算法設(shè)計(jì)題（共5題，共51分）。1、（15分）求兩個(gè)正整數(shù)的最大公約數(shù)可以使用歐幾里德

11、算法。該算法的基本思想如下：兩個(gè)正整數(shù)的最大公約數(shù)等于其中較小的那個(gè)數(shù)和兩數(shù)相除余數(shù)的最大公約數(shù)。（1）請(qǐng)?jiān)O(shè)計(jì)遞歸版本的歐幾里德算法。intintEuclideanEuclideanRecursiveRecursive(intaintb)(intaintb)（2）請(qǐng)?jiān)O(shè)計(jì)非遞歸版本的歐幾里德算法。intintEuclideanEuclideanIterativeIterative(intaintb)(intaintb)2、（10分）設(shè)二叉

12、樹的根指針為bt，設(shè)計(jì)算法求二叉樹的高度。intintHeightTree(BTreeHeightTree(BTreeNodeNodebt)bt)3、（8分）已知數(shù)組R中存儲(chǔ)的m項(xiàng)數(shù)據(jù)是亂序的（即沒有按照從小到大的順序排列好），請(qǐng)?jiān)O(shè)計(jì)算法判斷待查元素x是否在數(shù)組中出現(xiàn)。intintSearchSearch(intintR[]intmintxR[]intmintx))4、（8分）設(shè)二叉排序樹的根指針為bt，設(shè)計(jì)算法求二叉排序樹中最大的關(guān)鍵