PAGEPAGE1考試科目名稱數據結構(A卷)考試方式：開卷閉卷考試日期年月日教師陳珮珮系（專業(yè)）軟件學院年級二年級(07級)班級學號姓名成績題號一二三四五六七八九十分數得分1．算法分析題（10分）利用大“O”記號將下列函數在最壞情況下運行時間表示為n的函數（要求給出推導過程）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}}答：得分2．（20分，每題5分）深度為k（設根結點為1層）的二叉樹上，只有度為0和度為2的結點，則這類二叉樹上所含結點總數最少為個。至多為個。2)設有序順序表中的元素依次為017,094,154,170,275,503,509,512,553,612,677,765,897,908.試畫出對其進行折半搜索時的判定樹,并計算搜索成功的平均搜索長度。答：3)設有一字符串P=”3*y-a/y↑2”,試寫出利用棧將P改為”3y*ay2↑/-”的操作步驟。（請用X代表掃描該字符串過程中順序取一字符進棧的操作，用S代表從棧中取出一字符加入到新字符串尾的出棧操作。例如，要使”ABC”變?yōu)椤盉CA”，則操作步驟為XXSXSS）。答：4)設W為一個二維數組，其每個數據元素占用6個字節(jié)，行下標i從0到8,列下標j從0到3,則二維數組W的數據元素共占用______個字節(jié)。W中第6行的元素和第4列的元素共占用______個字節(jié)。若按行主順序存放二維數組W,其起始地址為100,則二維數組W的最后一個數據元素的起始地址為______。得分3．（10分）對下列無向圖，按照Dijkstra算法,寫出從頂點1到其它各個頂點的最短路徑和最短路徑長度。（順序不能顛倒）10586911710586911777246答：得分4.（10分）設散列表HT[13]，散列函數為H(key)=key%13,用閉散列法解決沖突，對關鍵碼序列{12,23,45,57,20,03,78,31,15,36}構造散列表，用線性探查法尋找下一個空位，畫出散列表，并計算等概率下搜索成功的平均搜索長度ASLsucc。答：得分5.(10分)對關鍵碼序列{23，17，12，61，26，8，70，75，53},用堆排序方法進行排序，畫出排序過程中所建的初始堆，以及輸出前三個關鍵碼過程的示意圖。（要求建立的堆為任一父母結點的關鍵碼都小于其子女結點的關鍵碼）得分(10分)下列各圖都是AVL樹(平衡二叉樹)，請按指定的關鍵碼插入，分別畫出插入后的AVL樹(平衡二叉樹)。1525插入5679203651850MARAUGMAY插入FEB， (按字母順序)APRJANNOVDECJULY得分7.（10分）請畫出往下圖的5階B-樹中插入一個關鍵碼390后得到的B-樹，以及再刪除關鍵碼100后得到的B-樹。1002003004002040150180240260310320350370420430答：得分8.(10分)以下算法是用無表頭結點的循環(huán)鏈表解Josephus(約瑟夫)問題，請在下劃線部分填上正確的語句。nolink其中：n表示有n個人參加該游戲；nolinkm表示每次報的數；鏈表的結點(ListNode))表示為no表示人的編號rear一開始指向循環(huán)鏈表的尾結點。ListNodeJosephus(intn,intm){intw=m;ListNodehead,p;for(inti=1;i<=n-1;i++){for(intj=1;j<=w-1;j++)1;if(i==1){head=rear.link;p=head;}else{p.link=rear.link;p=rear.link;}2;}3；rear.link=NULL;returnhead;}得分9.（10分）給定一棵二叉樹t，其根指針為root，結點結構為：leftda