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