數(shù)據(jù)結(jié)構(gòu)(本科)形成性考核冊答案-資料下載頁
2025-06-07 19:26本頁面
【正文】 ，653，462）請給出采用快速排序法對該序列作升序排列時(shí)的每一趟結(jié)果。原始序列：503，87，512，61，908，170，897，275，653，462第1趟： [462，87，275，61，170]503[897，908，653，512] 第2趟： [170，87，275，61] 462，503[897，908，653，512] 第3趟： [87，61]170[275] 462，503[897，908，653，512] 第4趟： 61 [87]170[275] 462，503[897，908，653，512]第5趟： 61 ，87，170，[275] 462，503[897，908，653，512]第6趟： 61 ，87，170，275，462，503[897，908，653，512]第7趟： 61 ，87，170，275，462，503[512，653]897[908]第8趟： 61 ，87，170，275，462，503，512，[653] 897[908]第9趟： 61 ，87，170，275，462，503，653，897[908]第10趟： 61 ，87，170，275，462，503，653，897，9085．設(shè)一組記錄的關(guān)鍵字序列為（49，83，59，41，43，47），采用堆排序算法完成以下操作：（要求小根堆，并畫出中間過程）（1）以二叉樹描述6個(gè)元素的初始堆（2）以二叉樹描述逐次取走堆頂元素后，經(jīng)調(diào)整得到的5個(gè)元素、4個(gè)元素的堆答：（1）49598341434783474143594949834147435983594941434783495941594741498343434741598349594741438349474183594349474143834959（2）6．(1)原序列16 15 20 53 64 7 15 16 20 53 7 64 n1趟 15 16 20 7 53 64 nj次 15 16 7 20 53 64 15 7 16 20 53 64 7 15 16 20 53 64715206416535(2)(3)平均查找長度=（1*1+2*2+3*3）/6=14/67．2461673185145（1）(2) 中序遍歷：2，3，4，5，6，7，14，16，18四、程序填空題1. （1）①j=0（2）②a[j]（3）③j（4）④temp2．（1）j=n1（2）i=nj（3）a[i]=a[i+1]（4）a[i+1]=temp（5）?當(dāng)某趟冒泡中沒有出現(xiàn)交換則已排好序結(jié)束循環(huán)。五、算法設(shè)計(jì)題1．編寫折半查找算法。折半查找算法如下；int Binary_Search(NODE a[],int n, int k)/* 在a[0]到a[n1]中，用折半查找算法查找關(guān)鍵字等于k的記錄，查找成功返回該記錄的下標(biāo)，失敗時(shí)返回1 */ { int low,mid,high。 low=0。 high=n1。 while(low=high) { mid=(low+high)/2。 if(a[mid].key==k) return mid。 /*查找成功，返回查找到的記錄的下標(biāo)*/ else if(a[mid].keyk) low=mid+1。 /*取后半查找區(qū)間*/ else high=mid1。 /*取前半查找區(qū)間*/ } return 1。 /*查找失敗*/ }2. 編寫順序查找算法。 順序查找算法如下： int search(NODE a[],int n, int k) /*在a[0]～a[n1]中順序查找關(guān)鍵字等于k的記錄。查找成功時(shí)返回該記錄的下標(biāo)，失敗時(shí)返回1*/ { int i=0。 while(in amp。amp。 a[i].key!=k) /*沒有查到同時(shí)查找過程沒有結(jié)束，則繼續(xù)查找*/ i++。 if(a[i].key=k) /*查找成功*/ return i。 else return 1。 /*查找失敗*/} 六、完成：實(shí)驗(yàn)3――棧、隊(duì)列、遞歸程序設(shè)計(jì) 實(shí)驗(yàn)4——圖的存儲(chǔ)方式和應(yīng)用根據(jù)實(shí)驗(yàn)要求（見教材P203）認(rèn)真完成本實(shí)驗(yàn)，并提交實(shí)驗(yàn)報(bào)告。15
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1