西安交通大學(xué)計(jì)算機(jī)軟件基礎(chǔ)歷年考研真題匯編

西安交通大學(xué)計(jì)算機(jī)軟件基礎(chǔ)歷年考研真題匯編820只考C語言與數(shù)據(jù)結(jié)構(gòu)，難度不大，非?；A(chǔ)，具體題目記不清楚由于09年以后的試題基本沒有，就大體回憶一下，也算是感謝半年來大家資源的相互分享，題型：選擇2X10;判斷2X10;簡答共三道20分；編程4X10;問答題5X10其他的記不清了，總之，非?；A(chǔ)，重點(diǎn)在理解概念，熟悉算法操作，代碼量很少第六章：樹，重點(diǎn)章，考題很多，但均為概念和算法思想與過程，基本無代碼，大題：樹的中序、后序遍歷，二叉樹轉(zhuǎn)化為森林，森林的先序遍歷，二叉排序樹的概念，性質(zhì)，創(chuàng)建，哈夫曼樹的概念，創(chuàng)建，哈夫曼編碼的過程；題目較多，選擇，判斷，簡答，問答都有，分值應(yīng)該超過30了吧第七章：圖，重點(diǎn)章，考題很多，但均為概念和算法思想與過程，基本無代碼，大題：拓?fù)溥x擇，判斷，簡答，問答都有，分值應(yīng)該也超過30了吧，選擇，判斷重在概念學(xué)第九章：排序次重點(diǎn)章，大題涉及：選擇排序的流程圖，直接插入排序的過程，基數(shù)排序的過程，無代碼，這更不科學(xué)第一道：編寫函數(shù)實(shí)現(xiàn)二維數(shù)組對角元素的和第二道：編寫函數(shù)分別計(jì)算字符串中數(shù)字、字母和其他字符的個(gè)數(shù)第四道：編寫函數(shù)計(jì)算單鏈表中值為X的結(jié)點(diǎn)個(gè)數(shù)可以看到，整張?jiān)嚲黼y度不大，代碼量甚少，重基礎(chǔ)，重概念，重算法過程，數(shù)據(jù)結(jié)構(gòu)部分，只要認(rèn)真看教材，做到熟悉，記憶準(zhǔn)確就可以及格了，語言部分甚至可以不用復(fù)習(xí)，我就是說明：以上僅為15年考題情況，由于記憶有限，各章分值分布也只是大概，重點(diǎn)與否自行判斷，大題知識點(diǎn)基本就這些，遺漏不了多少!交大的講義啊，期末題啊，復(fù)習(xí)大綱之類的，可以不用，不是說沒有，只是用了和認(rèn)真看教材沒區(qū)別，只要認(rèn)真看書了，就應(yīng)該不會(huì)差對關(guān)鍵字序列(32,13,49,55,22,38,21),試問：(1)按線性探測法解決沖突，產(chǎn)生的散列表是：地址012346(在地址0~6對應(yīng)的表格內(nèi)填入相關(guān)的關(guān)鍵字)(2)在(1)中產(chǎn)生的散列表中，用散列法查找各關(guān)鍵字需要進(jìn)行比較的次數(shù)是關(guān)鍵字比較次數(shù)三.算法設(shè)計(jì)(每題15分，共30分)0一三古奇異常出口(無空閑單元)第1頁(共2頁)(2)流程圖如圖三所示，用來實(shí)現(xiàn)中序遍歷二叉樹的算法，二叉樹存放在數(shù)組tree中在數(shù)組中的下標(biāo)，若指針值為0,表示它指向空樹。圖中指針root指向二叉樹的根結(jié)點(diǎn)。問題一：請?jiān)诹鞒虉D中①~③處填入適當(dāng)?shù)牟僮?。中序遍歷變?yōu)榍靶虮闅v，請畫出流程圖，root->p二三top:0≠②≠③=①四.編寫程序(每題10分，共20分)(可選用任意一種程序設(shè)計(jì)語言編寫程序)①編寫函數(shù)，函數(shù)首部為voidstrcat(char*sl,char*s2),實(shí)現(xiàn)將兩個(gè)字符串合并后存到s②設(shè)有一個(gè)已排好序的數(shù)組，編寫程序，要求：輸入一個(gè)數(shù)，按原來排序的規(guī)律將它插入數(shù)組合適的位置中，并且輸出數(shù)組內(nèi)容五、設(shè)計(jì)算法并編寫程序題(30分)1)從鍵盤輸入100個(gè)整型數(shù)據(jù)；n),有如下功能：(15分)(注：所有答案必須寫在專用答題紙上，寫在本試題紙上和其它草藕紙上一律無效一、判斷下列敘述是否正確，正確填√,不正確填×(每小題2分)()1、評價(jià)一個(gè)算法時(shí)間復(fù)雜性能的主要標(biāo)準(zhǔn)市算法的時(shí)間復(fù)雜度。)2、在單鏈表中，頭結(jié)點(diǎn)是必不可少的。()3、順序存儲的線性表可以隨機(jī)存取，()4、對稀疏矩陣進(jìn)行壓縮存儲是為了便于矩陣的運(yùn)算。()5、如果一個(gè)二叉樹中沒有度為1的結(jié)點(diǎn)，則必為完全二叉樹。()6、在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等子所有頂點(diǎn)的出度之和，()7、含有。個(gè)結(jié)點(diǎn)的二叉排序樹的平均查找長度和樹的形態(tài)無關(guān)，()8、在采用線性探測法處理沖突的散列表中，所有同義詞存儲在表中相鄰的位置。()9、快速排序在最壞情況下的時(shí)間復(fù)雜度為0(n2)。()10、堆排序、快速排序和希爾排序等時(shí)間性能較好的排序方法都是不穩(wěn)定的。1、假設(shè)以數(shù)組A[48]存放循環(huán)隊(duì)列的元素，其頭指針是fronr=36,當(dāng)前隊(duì)列有35個(gè)元素，則隊(duì)列的尾指針值為()。2、己知二叉樹如圖所示，此二叉樹的順序存儲的結(jié)點(diǎn)序列是()。C、□BDA□CE;D、ABCODDE:DE3、若采用起泡排序?qū)﹃P(guān)鍵字序列(24,21,17,13,8,10),從小到大進(jìn)行排序，則需要交換的總次數(shù)為()。4.對于一個(gè)頭指針為head的帶表頭結(jié)點(diǎn)的單鏈表，判斷該表為空的條件是()。A、head->nextNULLheadNULL2、如果根的層次為1,具有61個(gè)結(jié)點(diǎn)的完全二叉樹高度為()。6、在各種查找方法中，平均查找長度與查找表中的元素個(gè)數(shù)無關(guān)的查找方法是()。A.順序查找B.散列查找C.折半查找Q.動(dòng)態(tài)查找7、無向圖中一個(gè)頂點(diǎn)的度是指圖中()。A.通過該頂點(diǎn)的簡單路徑數(shù)B.通過該頂點(diǎn)的回路數(shù)C.與該頂點(diǎn)相鄰接的頂點(diǎn)數(shù)D.與該頂點(diǎn)連通的頂點(diǎn)數(shù)8、利用逐點(diǎn)插入法建立關(guān)鍵字序列<50,72,43,85,75,20,35,45,65,30>對應(yīng)的二叉排序樹以后，查找元素30要進(jìn)行元素間的比較次數(shù)為()。9、如果具有n個(gè)頂點(diǎn)的有向圖中最多有多少條弧?()A、n(n-1)B、n(n-1)/2C、nD、n-110、有一組記錄的關(guān)鍵字為(45,77,52,36,41,88),利用快速排序方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為()。三、填空題(20分)1、假設(shè)一個(gè)12階的下三角矩陣A按行優(yōu)先順序壓縮存儲在一維數(shù)組B中，則非零元素a,6在B中的存儲位置k=。(注：矩陣元素下標(biāo)從1算起，數(shù)組B的下標(biāo)從0算起)2、在長度為n的顧序存儲的線性表中插入一個(gè)元素，平均需要移動(dòng)個(gè)元素。3、在一個(gè)循環(huán)單鏈表中p所指結(jié)點(diǎn)之后插入s所指的結(jié) 的操作。4、給出下列程序段中語句x=x+1的執(zhí)行次數(shù),}5、已知中序遍歷的序列為：DBGEAFHC,前序遍歷序列為：ABDEGCFH,則其后序遍歷序列為。6、深度為5的二叉樹至少有結(jié)點(diǎn)，最多有結(jié)點(diǎn)7、線性表最常用的運(yùn)算是插入和刑除，當(dāng)插入和刪除操作在線性表的一端進(jìn)行，這個(gè)線性表被稱為,他的特點(diǎn)是。四、簡答題(40分)1、(4分)請回答樹與二叉樹的區(qū)別，并舉例說明之。2、<8分)已知一棵二叉樹，如圖1所示，試完成：AAG(2)給出該二叉樹先序遍歷序列；(3)給出該二叉樹后序遍歷序列：(4)給出該二義樹所對應(yīng)的森林。3、(6分)設(shè)有向圖，如圖2所示，給出該圖的拓?fù)渑判蛐蛄?，井用圖示的方法給出產(chǎn)生該拓?fù)渑判蛐蛄械倪^程。4、(8分)己知一個(gè)無向圖G=(V,E),箕中V=(V1,V2,V3,V4,V5),其鄰接矩陣如下所示34(1)還原圖G,并寫出圖G的鄰接表存儲結(jié)構(gòu)；(2)寫出從V1開始的深度優(yōu)先遍歷和廣度優(yōu)先遍歷序列及其相應(yīng)的生成樹。5、(8分)設(shè)散列表的存儲空間為[0..6],設(shè)hash函數(shù)為H(k)=kmod7,采用建立公共溢出區(qū)解決沖突，現(xiàn)給定關(guān)鍵字序列為：11,6,17,14,9,3,24,18,23,16.(1)請畫出相應(yīng)的散列表；(2)求出查找各關(guān)鍵字的比較次數(shù)；(3)計(jì)算出等概率情況下，查找成功的平均查找長度。6、(6分)設(shè)某系統(tǒng)的通信聯(lián)絡(luò)中僅有5種字符：a,b,c,d,e,組成，其頻率分別為：(1)給出相應(yīng)的哈夫曼樹；(2)設(shè)計(jì)出這5種字符的哈夫曼編碼；(3)計(jì)算出該哈夫曼樹的帶權(quán)路徑長WPL。五、算法設(shè)計(jì)(20分)1、己知下列算法中，Ls時(shí)不帶表頭結(jié)點(diǎn)的單鏈表。typedefstructLnode/*鏈表結(jié)點(diǎn)類型定義*/StatusFun(LinkListLs)(/*針對鏈表的操作函數(shù)*/請回答下列問題：(1)簡述上面算法功能；(2)語句(a)的功能是什么?(3)語句(b)執(zhí)行之后，p指向鏈表中的那個(gè)結(jié)點(diǎn)?2、已知二叉樹采用二叉鏈表存儲，其結(jié)點(diǎn)結(jié)構(gòu)定義為：typedefstructNode/*二文樹結(jié)點(diǎn)類型定義*/請采用遞歸方式編寫算法SumNode(BiTreeT),返回二叉樹T中的結(jié)點(diǎn)總數(shù)。六、采用任意一種編程語言編寫程序(30分)1、編寫函數(shù)，用置泡排序法或選擇排序法對輸入的100個(gè)整數(shù)按從小到大的順序排列。2、采用遞歸法，編寫實(shí)現(xiàn)n!的函數(shù)，3、編寫統(tǒng)計(jì)候選人得票的程序。設(shè)有十個(gè)候選人，有100個(gè)人參加投票，每次輸入一個(gè)得票的候選人的名字，要求最后統(tǒng)計(jì)輸出每個(gè)候選人的得票結(jié)果，(注：所有答來必須寫在專用答題紙上，寫在本試題紙上和其它草稿紙上一律無效一.判斷下列敘述是否正確，正確填V,不正確填X(15分)1、數(shù)據(jù)對象是一組數(shù)據(jù)元素的集合()2、判定一個(gè)圖是否存在回路，只能使用拓?fù)渑判蛩惴?)3、在何一棵前序線索二叉樹，都可以不用棧實(shí)現(xiàn)前序遮歷()4、用快速排序算法中，不可以用隊(duì)列代替棧()5、在任何情況下，折半查找的時(shí)間復(fù)雜度和二叉排序樹查找的時(shí)間復(fù)雜度相同二.填空題(15分)①算法的時(shí)間復(fù)雜度是指。②若某二叉樹的中序遍歷序列與后序遍歷序列剛好相同，則該二叉樹一定是·③數(shù)組G[9][5]的每一個(gè)元素占4個(gè)字節(jié)，下標(biāo)從0開始，已知G的存儲起始地址為2072,按行優(yōu)先方式存儲的G[6][3]的素的起始地址為2140,則這個(gè)元素的下標(biāo)是。④具有n各頂點(diǎn)的無向連通圖至少有條邊、⑤深度為k的二又樹至多有個(gè)節(jié)點(diǎn)。三.解答題(60分)①(10分)循環(huán)隊(duì)列squeue[45]的頭尾指針為f、r,請問該隊(duì)列滿的條件是什么?當(dāng)f=38,r=14時(shí)，該隊(duì)列當(dāng)前存儲有多少元素?②(10分)求出next函數(shù)值。③(10分)已知遍歷一棵二叉樹后，其中序遍歷序列為：CIBHDAFGE,后序避歷序列為：ICHDBGFEA,試完成：(1)構(gòu)造這棵二叉樹(2)給出其先序遍歷序列；(3)給出該二叉樹所對應(yīng)的森林，④(10分)已知一無向圖G的鄰接矩陣為⑤(10分)已知有關(guān)鍵字序列{34,45,14,32,84,21,8,5}對關(guān)鍵字序列(32,13,49,55,22,38,21),試問：(在地址0~6對應(yīng)的表格內(nèi)填入相關(guān)的關(guān)鍵字)比較次數(shù)四.程序填空題(15分)數(shù)。如果要找出2至10中的素?cái)?shù)，開始時(shí)篩中有2到10的數(shù)，然后取走篩中第1頁#2頁工作結(jié)束，即求得2至10中的全部素?cái)?shù)。在篩子中，值為-1時(shí)表示數(shù)i已被取走。 五.算法設(shè)計(jì)(20分)六.用任意一種編程語言編寫程序(25分)第2頁(共2頁)西安交通大學(xué)2004年攻讀碩士學(xué)位研究生入學(xué)考試試題)4.若AP(BθC)=A,則B=C.()13.如果無向圖G中恰有2個(gè)奇結(jié)點(diǎn)u,v,那么G中一定存在著從u到v二、(12分)設(shè)<G,*>是群，<H,*>是<G,*>的子群，建立G上的二元關(guān)系R如下：1)證明R是G上的等價(jià)關(guān)系；2)設(shè)Ng={0,1.2.3,4.5,6.7.8},對于i,j∈N。,今如果給定<G,*>為<N?