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

1、第2頁第1頁西安建筑科技大學(xué)2018年攻讀碩士學(xué)位研究生招生考試試題(答案書寫在本試題紙上無效?？荚嚱Y(jié)束后本試題紙須附在答題紙內(nèi)交回答案書寫在本試題紙上無效?？荚嚱Y(jié)束后本試題紙須附在答題紙內(nèi)交回)共4頁二、填空題（共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è)考試科目:適用專業(yè):（835）數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)科學(xué)與技術(shù)、計(jì)算機(jī)技術(shù)、控制工程有一批數(shù)據(jù)元素，

2、為了最快地存取某元素，宜用結(jié)構(gòu)存儲(chǔ)；為了方便地插入一個(gè)元素，宜用結(jié)構(gòu)存儲(chǔ)。3、在長度為n的順序表的第i個(gè)位置上插入一個(gè)元素，i的合法范圍是，元素的移動(dòng)次數(shù)為；刪除表中第i個(gè)元素，i的合法范圍是，需要向前移動(dòng)個(gè)元素。4、棧和隊(duì)列都是結(jié)構(gòu)；對于棧，只能在插入和刪除元素；對于隊(duì)列，只能在插入元素，在刪除元素。5、假設(shè)以S和X分別表示進(jìn)棧和退棧操作，則對輸入序列a，b，c，d，e進(jìn)行一系列棧操作SSXSXSSXXX之后，得到的輸出序列為。6、對

3、于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為，所有鄰接表中的結(jié)點(diǎn)總數(shù)是。7、二分查找的存儲(chǔ)結(jié)構(gòu)僅限于，且是。8、對于二叉排序樹上的查找，若結(jié)點(diǎn)元素的關(guān)鍵字值大于被查找元素的關(guān)鍵字值，則應(yīng)該在該二叉樹的繼續(xù)查找。e三解答題（共7題，共59分）。bf1、（14分）已知二叉樹如右圖所示。請按要求回答問題：（1）列出該二叉樹的所有葉子結(jié)點(diǎn)。ac（2）請寫出該二叉樹的先序遍歷序列、中序遍歷序列、后序遍歷序列。（3）請寫

4、出該二叉樹的按層次遍歷序列。d（4）將該二叉樹調(diào)整成AVL樹。（5）若該圖為“左孩子－右兄弟”的二叉存儲(chǔ)結(jié)構(gòu)，請畫出該圖所對應(yīng)的樹（森林）。2、（15分）已知圖G的鄰接表如右圖所示。（1）請畫出該存儲(chǔ)結(jié)構(gòu)對應(yīng)的圖。（2）請寫出該圖的鄰接矩陣。（3）請寫出該圖的逆鄰接表。（4）請寫出該圖從頂點(diǎn)1出發(fā)的深度優(yōu)先搜索序列。（5）請寫出該圖從頂點(diǎn)1出發(fā)的廣度優(yōu)先搜索序列。1324∧2∧345∧4∧524∧一、單項(xiàng)選擇題（共10題，每小題2分，共

5、20分）。1、算法分析的目的是（）。A找出數(shù)據(jù)結(jié)構(gòu)的合理性B研究算法中的輸入和輸出關(guān)系C分析算法的效率以求改進(jìn)D分析算法的可讀性和簡明性2、若一個(gè)順序表中第一個(gè)元素的存儲(chǔ)地址為1000，每個(gè)元素占4個(gè)地址單元，那么，第6個(gè)元素的存儲(chǔ)地址應(yīng)是（）。A1020B1010C1016D10243、帶頭結(jié)點(diǎn)的單鏈表（以head為頭指針）為空的判斷條件是（）。Ahead!=NULLBheadnext==headCheadnext==NULLDhea

6、d==NULL4、在一個(gè)單鏈表中，已知q指向p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在p、q所指結(jié)點(diǎn)之間插入一個(gè)s所指向的新結(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=qnex

7、tfree(q)Cq=pnextnextp=pnextnextfree(q)Dp=pnextnextq=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)的完全二叉樹從根開始，每一層從左到右依次對結(jié)點(diǎn)進(jìn)行編號，根結(jié)點(diǎn)的

8、編號為0，則編號為49的結(jié)點(diǎn)的左孩子編號為（）。A99B98C50D489、以二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)，在具有n個(gè)結(jié)點(diǎn)的二叉鏈表中（n0），空鏈域的個(gè)數(shù)為（）。A2n1Bn1Cn1D2n110、無向圖的鄰接矩陣是一個(gè)（）。A對角矩陣B對稱矩陣C上三角矩陣D零矩陣第4頁第3頁西安建筑科技大學(xué)2018年攻讀碩士學(xué)位研究生招生考試試題(答案書寫在本試題紙上無效。考試結(jié)束后本試題紙須附在答題紙內(nèi)交回答案書寫在本試題紙上無效。考試結(jié)束后本試題

9、紙須附在答題紙內(nèi)交回)共4頁四、算法設(shè)計(jì)題（共5題，共51分）。1、（15分）求兩個(gè)正整數(shù)的最大公約數(shù)可以使用歐幾里德算法。該算法的基本思想如下：兩個(gè)正整數(shù)的最大公約數(shù)等于其中較小的那個(gè)數(shù)和兩數(shù)相除余數(shù)的最大公約數(shù)。（1）請?jiān)O(shè)計(jì)遞歸版本的歐幾里德算法?？荚嚳颇?（835）數(shù)據(jù)結(jié)構(gòu)intintEuclideanRecursiveEuclideanRecursive(int(intaaintintb)b)適用專業(yè):計(jì)算機(jī)科學(xué)與技術(shù)、計(jì)算機(jī)技

10、術(shù)、控制工程（2）請?jiān)O(shè)計(jì)非遞歸版本的歐幾里德算法。intintEuclideanIterativeEuclideanIterative(int(intaaintintb)b)2、（10分）設(shè)二叉樹的根指針為bt，設(shè)計(jì)算法求二叉樹的高度。intintHeightTree(BTreeNodeHeightTree(BTreeNodebt)bt)3、（8分）已知數(shù)組R中存儲(chǔ)的m項(xiàng)數(shù)據(jù)是亂序的（即沒有按照從小到大的順序排列好），請?jiān)O(shè)計(jì)算法判斷待查

11、元素x是否在數(shù)組中出現(xiàn)。intintSearch(intSearch(intR[]R[]intintmmintintx)x)4、（8分）設(shè)二叉排序樹的根指針為bt，設(shè)計(jì)算法求二叉排序樹中最大的關(guān)鍵字值。intintMaximum(BSTreeNodeMaximum(BSTreeNodebt)bt)5、（10分）基于合理的有向圖存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)算法判定給定連通有向圖G是否存在回路。boolboolExistCyclePath(GraphEx

12、istCyclePath(GraphG)G)3、（3分）有一組記錄的關(guān)鍵字序列為46，79，56，38，40，84，利用快速排序的方法，寫出以第一個(gè)記錄為基準(zhǔn)得到的一趟排序結(jié)果。4、（6分）對于給定的一組關(guān)鍵字41，62，13，84，35，96，57，39，79，61，15，83，寫出執(zhí)行希爾排序算法的第一趟排序結(jié)果，增量為5。5、（4分）對于給定的一組關(guān)鍵字26，18，60，14，7，45，13，32，寫出執(zhí)行堆排序算法的第一趟排序結(jié)