山東大學(xué)計(jì)算機(jī)學(xué)院數(shù)據(jù)結(jié)構(gòu)真題

2012年山東大學(xué)計(jì)算機(jī)學(xué)院數(shù)據(jù)結(jié)構(gòu)真題共13大題150分1、分析下列函數(shù)，描述函數(shù)功能，并求函數(shù)的時間復(fù)雜度。S=0For(inti=1;i<=n;i++){Intp=1;For(intj=1;j<=I;j++)P*=j:S+=p;}2、對于含有n個元素的有序數(shù)組，查找各個元素的概率相等，采取折半查找時，最少要比較多少次，最多要比較多少次，平均要比較多少次。當(dāng)n個元素?zé)o序時，采取折半查找，最多需要多少次，最少需要多少次。3、描述棧與隊(duì)列的相同點(diǎn)和不同點(diǎn)。4、二叉樹，先序遍歷得到abdfceg，中序遍歷得到fdbaceg，該二叉樹的葉節(jié)點(diǎn)是什么。5、有5000個無序元素，公式化描述（數(shù)組），要求最快速度選取最大的10個元素，請問，在快速排序，堆排序，基數(shù)排序，歸并排序四種方法中，采取哪種方法最好，為什么？6、構(gòu)建散列表，散列函數(shù)為hashf（k）=k%11.已知關(guān)鍵字序列為（8,15,27,2,13,31,19）（具體數(shù)字記不清了，我寫的數(shù)字性質(zhì)是一樣的），請畫圖表示采取線性開放式尋址和鏈表地址法存貯。7、（1）如果G1是一個具有n個頂點(diǎn)的連通無向圖，那么G1最多有多少條邊，最少有多少條邊？（2）如果G2是一個具有n個頂點(diǎn)的強(qiáng)連通有向圖，那么G2最多有多少條邊，最少有多少條邊？8、在一篇電碼中，由abcde字母組成，其分別出現(xiàn)的次數(shù)為4,8,25,37,6（具體數(shù)字記不清了，我寫的數(shù)字性質(zhì)是一樣的）。構(gòu)造huffman樹，給出各個字母的huffman編碼，該篇電碼的總電碼數(shù)是多少。9、有一圖，頂點(diǎn)為v1，v2，v3，v4，v5，邊的集合為（v2，v1），（v5，v3），（v1，v4）（v3，v2），（v1，v3），（v3，v4），（v4，v5），畫出該圖，該圖是強(qiáng)連通有向圖嗎？10、有一函數(shù)fun的功能是將字符串中每個單詞的最后一個字母改成大寫，例如Iamastudenttoexam.改成IaMAstudenTtOexaM.請將該函數(shù)補(bǔ)全。Voidfun(char*P){Intk=0;For(;p;p++)If(k=1){If(*p==‘’){【1】；【2】=upper(*(p-1));}}ElseK=1;}11、編寫算法，求出二叉樹中節(jié)點(diǎn)的度數(shù)為1的個數(shù)，并以n返回。（要求不能使用遞歸），寫出算法思想，并寫出程序。12、編寫程序，給一正整數(shù)m，求出在1至m之間（包括m）中，能夠被11或7整除的數(shù)字，保存在數(shù)組a中，函數(shù)返回在1至m之間（包括m）中，能夠被11或7整除的數(shù)字的個數(shù)，例如m為,30，則將（7,11,14,22,21，28）保存在數(shù)組a中，函數(shù)返回5.13、有向圖和無向圖，分別采取鄰接矩陣和鄰接鏈表的方法存儲。（1）怎樣求出圖中的邊的數(shù)目？（2）怎樣判斷在頂點(diǎn)i，j之間是否存在邊？（3）怎樣計(jì)算頂點(diǎn)i的度？山東大學(xué)07計(jì)算機(jī)真題（回憶整理）1.（8分）（1）for(inti=1;i<=n;i++){intp=1;for(intj=1;j<=I;j++)p*=j;s+=p;}描述功能，并分析時間復(fù)雜度。（2）對于1個n元素順序表，用折半查找，成功查找時，最大最小比較次數(shù)各是多少？2.（8分）n階三對角矩陣A，按行保存到一個數(shù)組B中，其中A[1][1]存入B[0]，問：（1）B中有多少元素（2）用i,j表示矩陣元素在B中的索引k（3）用k表示i,j3.（10分）（1）.一個中綴表達(dá)式為3*y-a/y↑2，求其后綴表達(dá)式（2）描述堆棧在處理后綴表達(dá)式中的作用（3）對于（1）中后綴式寫出棧的變化]4.（12分）寫出用數(shù)組實(shí)現(xiàn)字符串類String的類定義，并實(shí)現(xiàn)IsSym函數(shù)。其中IsSym表示該字符串是中心對稱的，例如xyzzyx，xyzyx，若是返回true，否則返回false5.（12分）寫出單鏈表類chain的類定義，并實(shí)現(xiàn)BubbleSort函數(shù)，不能創(chuàng)建新節(jié)點(diǎn)，也不能刪除舊節(jié)點(diǎn)，其他函數(shù)省略。BubbleSort表示將原鏈表按非遞減順序冒泡排序。6.（10分）一個二叉搜索樹，設(shè)任一條從根到葉子的路徑包含的節(jié)點(diǎn)集合為S2，這條路經(jīng)所有左邊的點(diǎn)的集合為S1，右邊所有點(diǎn)集合為S3，設(shè)a,b,c分別為S1，S2，S3中的任意元素，是否有a<b<c？為什么？7.（20分）（1）寫出最小堆的類聲明。（2）寫出用最小堆實(shí)現(xiàn)Huffman編碼的思想，并給出算法。8.（10分）一個8key值的3階B樹最多有多少節(jié)點(diǎn)？最少有多少？并畫出圖表示。9.（10分）如下圖所示的AVL搜索樹若先后插入70和60兩個數(shù)后，樹的最小不平衡樹各是哪個？怎樣旋轉(zhuǎn)能使其達(dá)到平衡？畫出樹的形態(tài)。為什么僅調(diào)整最小不平衡樹就不存在其他不平衡點(diǎn)？10.（20分）加權(quán)有向圖的鄰接矩陣類為AdjacencyWDigraph（1）舉出一個至少包括5個節(jié)點(diǎn)的例子，并寫出他的鄰接矩陣。（2）寫出AdjacencyWDigraph的類定義。（3）在此基礎(chǔ)上寫出寬度優(yōu)先搜索算法BFS，可以使用隊(duì)列類Queue。11.（20分）（1）從一點(diǎn)S出發(fā)對一個有向連通圖求最短路徑，按照如下貪婪準(zhǔn)則：每次選擇一個節(jié)點(diǎn)，該節(jié)點(diǎn)是與已選節(jié)點(diǎn)最近的尚未被選到的節(jié)點(diǎn)，直到到達(dá)目的節(jié)點(diǎn)。問：這種方法得到的是最短路徑嗎？（2）若不是，舉一反例，并寫出你認(rèn)為正確的一種方法。12（10分）.什么是分治法？有什么原則？有哪些算法用了這種思想？舉出一例，寫出算法思想。祝以后的學(xué)弟學(xué)妹們考個好成績，在考研中這個論壇給了我很大的幫助，現(xiàn)在我將我的考研經(jīng)驗(yàn)分享一下山東計(jì)算機(jī)的自主命題比較簡單，建議（1）將05年以后的真題，回憶版好好做一下，有重復(fù)，并且出題重點(diǎn)一脈相承。（2）對照考研大綱將原書看一遍，時間少也要將大綱標(biāo)明“掌握”的內(nèi)容精讀，時間多將標(biāo)明“了解”的內(nèi)容通讀，時間再多也不用去讀未明確的內(nèi)，或許山東本校都不學(xué)習(xí)。（3）買一本復(fù)習(xí)資料（算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析），機(jī)械工業(yè)出版社，一定要看，有原題，有解題方法。只要做好以上三點(diǎn)，考研130+在等你。相信你自己，你行的。寫于2012年考研結(jié)束第二天，為我自己留個mark，也希望看到的你能夠?qū)⑺鱾飨氯ァ＃槲壹易友笄笞８?，都快成孩他爹了，我容易嗎我?002年考研試題一、回答下列問題：（24分）1，如果用一個循環(huán)數(shù)組q[0..m-1]表示隊(duì)列時，該隊(duì)列只有一個隊(duì)列頭指針front，不設(shè)隊(duì)列尾指針rear，而改置計(jì)數(shù)器count用以記錄隊(duì)列中結(jié)點(diǎn)的個數(shù)。1）編寫實(shí)現(xiàn)隊(duì)列的基本運(yùn)算：判空、入隊(duì)、出隊(duì)（3分）2）隊(duì)列中能容納元素的最多個數(shù)是多少？（1分）2、設(shè)有對角矩陣a[1..n,1..n]把非零元素按列存儲在向量b[1..3*n-2]中，使得b[k]=a[I,j].求：（1）用I,j表示k的下標(biāo)變換公式（2分）（2）用k表示I,j的下標(biāo)變換公式（2分）3、設(shè)二叉排序樹中關(guān)鍵字由1到1000的整數(shù)組成，現(xiàn)要查找關(guān)鍵字為363的結(jié)點(diǎn)，下述評關(guān)鍵字序列哪一個不可能是在二叉排序樹中找到的序列？說明原因。（4分）（1）51，250，501，390，320，340，382，363（2）24，877，125，342，501，623，421，3634、設(shè)有n個無序元素，按非遞減次序排序，但只想得到前面長度為k的部分序列，其中n>>k，最好采用什么排序方法？為什么？（2分）如果有這樣一個序列{59，11，26，34，17，91，25}，得到的部分序列是：{11，17，25}，對于該例使用所選擇的方法實(shí)現(xiàn)時，共執(zhí)行多少次比較？（3分）5、在B-樹和B+樹中查找關(guān)鍵字時有什么不同？（2分）6、寫出對關(guān)鍵字序列{503，087，512，061，908，124，897，275，653，426}建立一棵平衡二叉樹的過程，并寫出調(diào)整平衡時的指針變化。（5分）二、解答下列問題：（10分）1、畫出對長度為10的有序表進(jìn)行二分查找的判定樹并求其等概率時查找成功的平均查找長度（5分）。2、設(shè)有一組關(guān)鍵字{9，01，23，14，55，20，84，27}，采用哈希函數(shù)：H（key）=keymod7，表長為10，用開放地址法的二次探測再散列方法Hi=(H(key)+di)mod10(di=1*1,2*2,3*3….)解決沖突。要求：對該關(guān)鍵字序列構(gòu)造哈希表，并計(jì)算查找成功的平均查找長度（5分）。三、已知L為沒有頭結(jié)點(diǎn)的的單鏈表中第一個結(jié)點(diǎn)的指針，每個結(jié)點(diǎn)數(shù)據(jù)域存放一個字符，該字符可能是英文字母字符或數(shù)字字符或其他字符，編寫算法構(gòu)造三個以帶頭結(jié)點(diǎn)的單循環(huán)鏈表表示的線性表，使每個表中只含同一類字符。（要求用最少的時間和最少的空間）（15分）四、對以二叉鏈表存儲的非空二叉樹，從右向左依次釋放所有的葉子結(jié)點(diǎn)，釋放的同時把結(jié)點(diǎn)值存放到一個向量中要求：（1）用文字寫出實(shí)現(xiàn)上述過程的基本思想（3分）（2）寫出算法（12分）五