2007年數(shù)據(jù)結(jié)構(gòu)期末試卷

PAGEPAGE3軟件學(xué)院2006級<<數(shù)據(jù)結(jié)構(gòu)>>期終試題2007.12.30姓名學(xué)號12345678得分填充題（20分，每題5分）1)樹的機內(nèi)表示(實現(xiàn))有、、。2）最小代價生成樹有兩種實現(xiàn)算法：Prim算法與Kruscal算法。兩者分別適用于何種情況,。3）采用堆排序方法將初始序列{8,23,12,5,28}按從小到大順序排序,則建立初始堆和排序過程中序列依次變化為、、、、。4)在具有6個結(jié)點的無向簡單圖中，邊數(shù)最少為11條時，才能確保該圖一定是連通圖。2．算法分析題（10分）利用大“O”記號將下列函數(shù)在最壞情況下運行時間表示為n的函數(shù)（要求給出推導(dǎo)過程）voidmystery(intn){for(inti=1;i<=n-1;i++)for(intj=i+1;j<=n;j++)for(intk=1;k<=j;k++){SomestatementrequiringO(1)time}}答：3．（15分，每題5分）1）設(shè)有一字符串P=”3*y-a/y↑2”,試寫出利用棧將P改為”3y*ay2↑/-”的操作步驟。（請用X代表掃描該字符串過程中順序取一字符進棧的操作，用S代表從棧中取出一字符加入到新字符串尾的出棧操作。例如，要使”ABC”變?yōu)椤盉CA”，則操作步驟為XXSXSS）。答：2)設(shè)數(shù)組Q[m]表示一個環(huán)形隊列（下標(biāo)為0到m–1）,rear為隊列中最后一個元素的實際位置，length為隊列中元素的個數(shù),求隊列中第一個元素的實際位置（要求寫出計算公式）答：3)試說明一棵二叉樹無論進行先序、中序或后序遍歷，其葉結(jié)點的相對次序不發(fā)生改變。答:4．(10分)對下列無向圖，按照Dijkstra算法,寫出從頂點1到其它各個頂點的最短路徑和最短路徑長度。（順序不能顛倒）10586911710586911777246答：5.（10分）設(shè)散列表長度為11,散列函數(shù)H(K)=(K的第一個字母在英文字母表中的序號，設(shè)A的序號為1)%11,若輸入順序為(B,D,M,CI,I,K,TM,X),處理沖突方法為線性探測法,要求：1)構(gòu)造此散列表。2).對表中所有鍵值分別查找1次,求出總的比較次數(shù)。答：6.（10分，每題5分）下列各圖都是平衡二叉樹，請按指定的關(guān)鍵碼插入，分別畫出插入后的平衡二叉樹。1525插入56792036518502）MARAUGMAY插入FEB (按字母順序)APRJANNOVDECJULY答：7.(10分)假設(shè)一棵帶索引的二叉搜索樹，root指向其根結(jié)點，樹中每個結(jié)點具有如下形式：Lsizeleftdataright其中，Lsize域的值為該結(jié)點左子樹中的結(jié)點個數(shù)加1；left,right分別指向該結(jié)點的左、右子樹，且假設(shè)data域為int型。試用java語言寫一個遞歸的findk函數(shù)，即搜索這棵帶索引的二叉搜索樹中第K個小的關(guān)鍵碼結(jié)點。答：8.（15分）已知（k1,k2,k3,…,kn）是一個最小堆，試寫一個函數(shù)將（k1,k2,k3