數(shù)據(jù)結(jié)構(gòu)教學(xué)-作業(yè)布置

(注:各題的題號(hào)為課后練習(xí)的題號(hào))筆做1-4什么是抽象數(shù)據(jù)類型？試用C++的類定義“復(fù)數(shù)”的抽象數(shù)據(jù)類型。要0；第三個(gè)構(gòu)造函數(shù)將兩個(gè)雙精度浮點(diǎn)數(shù)分別賦給復(fù)數(shù)的實(shí)部和1-9(1)countvoidd(ArrayElementx[],intn){inti=1;dox[i]+=2;i+=}while(i<=n i=while(i<=(n/2))x[i]+=x[i+1];}}count上機(jī)1-8試編寫一個(gè)函數(shù)計(jì)算n!*2n的值，結(jié)果存放于數(shù)組A[arraySize]的第n個(gè)數(shù)組元素中，0narraySizemaxIntnarraySize或k(0kn)k!*2kmaxInt時(shí)，應(yīng)按出錯(cuò)處理?？捎腥缦氯N不同的cerrexit(1)0,1在函數(shù)的參數(shù)表設(shè)置一個(gè)型的整型變量來區(qū)別是正常返回還是某種錯(cuò)誤返回。思考數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)對(duì)象與對(duì)象中數(shù)據(jù)元間關(guān)系的集合數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元間的邏輯關(guān)系，是用戶按使用需要建立的所謂數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元間的邏輯關(guān)系1-7n為正整數(shù)(1)for(inti=1;i<=n; (2)x=0;y=for(intj=1;j<=n;j++){ for(inti=1;i<=n;i++)c[i][j]=0.0; for(intj=1;j<=i;j++)for(intk=1;k<=n;k++) for(intk=1;k<=j;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j]; x=x+y;}(3)inti=1,j=1; (4)inti=1;while(i<=n&&j<=n){ do{i=i+1;j=j+ for(intj=1;j<=n; i=i+}while(i<100+n參考輸入、輸出、(①)、有窮性和可執(zhí)行性等特性。算法效率的度量分為(②)和(③)。(②)主要通過在算法的某些部位插裝時(shí)間函數(shù)來測(cè)定算法完成某一規(guī)定功能所需的時(shí)間。而(③)不實(shí)際運(yùn)行算法，它是分析算法中語程序所需的空間包含兩個(gè)部分(④)和(⑤)。(④)空間的大小與輸入輸出數(shù)據(jù)的個(gè)數(shù)多少，數(shù)值大小無關(guān)；(⑤)空間主要包括其大小與問題規(guī)模有關(guān)的成分變量所占空間，變量所占空間，以及遞歸棧所用的空間，還有在算法運(yùn)行過程中動(dòng)態(tài)分配和回Ovoidout(floatx[][],intm,intn){floatsum[];for(inti=0;i<m;i++)sum[i]=for(intj=0;j<n;j++)sum[i]=x[i][j];}for(inti=0;i<m;i++cout<<"Line:"<<i<<":"<<sum[i]<<}筆做2-3設(shè)有一個(gè)線性表（e0e1…en-2,en-1）A[arraySize]n個(gè)數(shù)組元素位置。請(qǐng)編寫一個(gè)函數(shù)將這個(gè)線性表原地逆置，即將數(shù)組的前n個(gè)原址內(nèi)容置換為（en-1,en-2,…,e1,e0）。2-7A[m][n]A[0][0]644（10），A[2][2]676（10）A[3][3]（10）存放在什么位置？腳注（10）10進(jìn)制表2-9設(shè)有一個(gè)nn的對(duì)稱矩陣A，如圖（a）所示。為了節(jié)約，可以只存對(duì)角線及B中，如圖（b）和圖（c）所示。并稱之為對(duì)稱矩陣A的壓縮方式。試問：ABB0號(hào)位置開始存放，則如圖(a)B0號(hào)位置開始存放，則如圖(a)上機(jī)2-8(3)ixi不合理則顯示出錯(cuò)信息并退出(8)2-14replace(String&s,String&t,String&v)ts的子串，則用串v替換串ts中的ts的子串，則s不變。例如，若s為“aabbabcbaabaaacbab”，串t為“bab”，串v為“abdc”，則執(zhí)行replace操作后，串s中的結(jié)思考2-5順序表的插入和刪除要求仍然保持各個(gè)元素原來的次序。設(shè)在等概率情形下,127個(gè)元素的順序表進(jìn)行插入,平均需要移動(dòng)多少個(gè)元素?刪除一個(gè)元素,又平均需要移動(dòng)多2-10設(shè)A和B均為下三角矩陣，每一個(gè)都有n行。因此在下三角區(qū)域中各有（n+1）/2個(gè)元素。另設(shè)有一個(gè)二維數(shù)組C，它有n行n+1列。試設(shè)計(jì)一個(gè)方案，將兩個(gè)矩陣A和B中的下三角區(qū)域元素存放于同一個(gè)C中。要求將A的下三角區(qū)域中的元素存放于C的下三角區(qū)域中，BC的上三角區(qū)域中。并給出計(jì)AaijBbijC中的存放位置下標(biāo)的公式。213稀疏矩陣的三元組表可以用帶行指針數(shù)組的二元組表代替。稀疏矩陣有多少行，iii即為稀疏矩陣第i行的第一個(gè)非零元素在二元組表中的存放位置。二元組表中每個(gè)二元組只記錄非零元素的列號(hào)和元素值，且各二元組按行號(hào)遞增的順序排列。試對(duì)右圖所示的稀疏矩陣，分別建立它的三元組表和帶行指針數(shù)組的二元組表。參考線性表的順序表示優(yōu)于鏈?zhǔn)奖硎揪€性表若采用鏈?zhǔn)奖硎緯r(shí)所有單元的地址可連續(xù)可不連續(xù)線性結(jié)構(gòu)可用順序表或鏈表。試問AnAnA[arraySize]中有多個(gè)零元素試寫出一個(gè)函數(shù)將A中所有的非零元素依次移到AA[i](0i<arraySize)。An設(shè)有上三角矩陣A[n][n]，將其上三角元素逐行到一維數(shù)組B[m]中，使得B[k]=A[i][j]kf1(i)f2j)+Cf1(i)、f2(j)Cf1(i)f2(j)中不設(shè)有三對(duì)角矩陣A[n][n]，將其三條對(duì)角線中的元素逐行到一維數(shù)組B[3n-2]中，使B[k]=A[i][j]。試求：i,jkk表示i,j設(shè)有兩個(gè)整數(shù)類型的順序表A（有m個(gè)元素）和B（有n個(gè)元素），其元素均以從小到CC的元素也筆做3-3hahb分別是兩個(gè)帶表頭結(jié)點(diǎn)的非遞減有序單鏈表的表頭指針,試設(shè)計(jì)一個(gè)算法將這兩個(gè)有序鏈表合并成一個(gè)非遞增有序的單鏈表。要求結(jié)果鏈表仍使用原來兩個(gè)鏈表的空間,不另外占用其它的空間。表中允許有重復(fù)的數(shù)據(jù)。3-9Pn(x)=a0xn+a1xn-1+a2xn-2++an-1x+an的值，通常使用的方法是一種嵌套的方法。它可以描述為如下的迭代形式：b0=a0,bi+1=x*bi+ai+1,i=0,1,n-1bnpn（x）則問題可以寫為如下形式：Pn(x)=x*Pn-1(x)anPn-1=a0xn-1+a1xn-2++an-2x+an-1，這是問題的遞歸形式。試編寫一個(gè)遞歸函數(shù)，計(jì)算這上機(jī)3-2(4)createa[n]建立一個(gè)單鏈表，使單鏈表中各元素的次序與a[n]O(n)。3-10Locate運(yùn)算的函數(shù)。設(shè)有一個(gè)帶表頭結(jié)點(diǎn)的雙向鏈表L4priornext、存放數(shù)據(jù)的成員data和頻度freq。所有結(jié)點(diǎn)的freq初始時(shí)都為0。每當(dāng)在鏈表上進(jìn)行一次Locate(x)操作時(shí)，令元素值為x的結(jié)點(diǎn)的頻度freq加1，并將該結(jié)點(diǎn)前移，到與它的頻度相等的結(jié)點(diǎn)后面，使得鏈表中所有結(jié)點(diǎn)保持按頻度遞減的順序排列，思考3-1線性表可用順序表或鏈表。試問兩種表示各有哪些主要優(yōu)缺點(diǎn)3-6試寫出用單鏈表表示的字符串類及字符串結(jié)點(diǎn)類的定義，并依次實(shí)現(xiàn)它的構(gòu)造函7個(gè)成員函數(shù)。要求每個(gè)字符串結(jié)點(diǎn)中只存放一個(gè)字符。3-8ab是兩個(gè)用帶有表頭結(jié)點(diǎn)的循環(huán)鏈表表示的多項(xiàng)式。試編寫一個(gè)算法，計(jì)c=a*bab保持原狀。如果這兩個(gè)多項(xiàng)式的項(xiàng)數(shù)分別為nm,試說明該算法的執(zhí)行時(shí)間為O(nm2)O(n2m)。但若ab是稠密的,即其很少有系數(shù)為零的項(xiàng),O(nm)。參考設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data,link）qp所指結(jié)點(diǎn)的直接前驅(qū)，若在*q與*p之間插入結(jié)點(diǎn)*s，則應(yīng)執(zhí)行下列哪一個(gè)操作？s->link=p->link;p->link= (2)q->link=s;s->link=(3)p->link=s->link;s->link= (4)p->link=s;s->link=設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data,link）p所指結(jié)點(diǎn)不是尾結(jié)點(diǎn)，若在*p之后s->link=p;p->link= (2)s->link=p->link;p->link=(3)s->link=p->link;p= (4)p->link=s;s->link=設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data,link）。若想摘除結(jié)點(diǎn)*p的直接后繼，則應(yīng)執(zhí)行下列哪p->link=p->link->link;(2)p=p->link;p->link=p->link-(3)p->link=p- (4)p=p->link-已知head為單鏈表的表頭指針,鏈表中的都是整型數(shù)據(jù)，試寫出實(shí)現(xiàn)下列運(yùn)算的遞NULL。統(tǒng)計(jì)函數(shù)numberx整理函數(shù)tidyuph的單鏈表。試設(shè)計(jì)一個(gè)算法，通過遍歷一趟鏈表，將鏈表中所有結(jié)點(diǎn)的方向逆轉(zhuǎn)，如下圖所示。要求逆轉(zhuǎn)結(jié)果鏈表的表頭指針h指向原鏈表的最后一 ΛhΛΛhΛ設(shè)單循環(huán)鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data,link），rear是指向非空的帶表頭結(jié)點(diǎn)的單循環(huán)s=rear;rear=rear->link;rear=rear->link;rear=rear->link->link;s=rear->link->link;rear->link->link=s->link;有一個(gè)循環(huán)鏈表，它既沒有頭指針又沒有頭結(jié)點(diǎn)。只有一個(gè)指針p指向表中的某一結(jié)p所指結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)。判斷一個(gè)帶表頭結(jié)點(diǎn)的雙向循環(huán)鏈表L是否對(duì)稱相等的算法如下所示，請(qǐng)?jiān)谒惴ㄖ械膇ntsymmetry(DlinkListL){intsym=1;DlistNode*p=L->next,q=L-while((p!=q||p->prior==q) if(p->data==q->data) }elsesym=0;returnsym;}設(shè)雙向循環(huán)鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data,prior,next），且不帶表頭結(jié)點(diǎn)。若想在指針sp->next=s;s->prior=p;p->next->prior=s;s->next=p-p->next=s;p->next->prior=s;s->prior=p;s->next=p-s->prior=p;s->next=p->next;p->next=s;p->next->prior=s->prior=p;s->next=p->next;p->next->prior=s;p->next=(注:各題的題號(hào)為課后練習(xí)的題號(hào)筆做4-2鐵路進(jìn)行列車調(diào)度時(shí)1,23,4,5,6的六輛列車,順序開入棧式結(jié)構(gòu)的站臺(tái),則可能的出棧序列若進(jìn)站的六輛列車順序如上所述,那么是否能夠得到435612,325641,154623和135426的出站序列,如果不能,說明為什么不能;如果能,說明如何得到(即寫出"進(jìn)棧"或"出4-10Q[m]存放循環(huán)隊(duì)列中的元素,tagtag==0和tag==1來區(qū)別在隊(duì)頭指針(front)和隊(duì)尾指針(rear)相等時(shí)，隊(duì)列狀態(tài)為“空”還是“滿”。試編4-14——Bag類。寫出各個(gè)類的。統(tǒng)一命名各派生類的插入操作為Add，刪除操作為RemoveGetPutMakeEmptyEmpty，判滿操FullLength。上機(jī)4-12V[m]end1end2，并end1end2的初始化條件及隊(duì)空與隊(duì)滿條思考4-4將編號(hào)為0和1的兩個(gè)棧存放于一個(gè)數(shù)組空間V[m]中，棧底分別處于數(shù)組的兩端。當(dāng)?shù)?號(hào)棧的棧頂指針top[0]等于-1時(shí)該棧為空，當(dāng)?shù)?號(hào)棧的棧頂指針top[1]等于m0top[0]1top[1]1得到新的棧頂位置。top[0]+1top[1]時(shí)或top[0]=top[1]-1時(shí)，?？臻g滿，此時(shí)不能再向任一棧加入新的元4-9Q[m]存放循環(huán)隊(duì)列中的元素,rearlength分別指示循環(huán)隊(duì)列中的隊(duì)尾位置和隊(duì)列中所含元素的個(gè)數(shù)。試給出該循環(huán)隊(duì)列的隊(duì)空條件和隊(duì)滿條件并寫出4-11若使用循環(huán)鏈表來表示隊(duì)列，p是鏈表中的一個(gè)指針(視為隊(duì)尾指針)。試基于此結(jié)構(gòu)給出隊(duì)列的插入(EnQueue)和刪除(DlQueue)p為何值時(shí)隊(duì)列空。參考Ss1s2s3s4s5s66s2s3s4,s6,s5,s1，則順序棧的容量至少應(yīng)為多少？設(shè)順序棧SMaxSizePushSx)，要求當(dāng)棧stackFull(S)操作進(jìn)行棧滿處理。其功能是：動(dòng)態(tài)創(chuàng)建一個(gè)比原來的棧元素存MaxSize位置。設(shè)鏈?zhǔn)綏Ｖ薪Y(jié)點(diǎn)的結(jié)構(gòu)為（data,link），且top是指向棧頂?shù)闹羔?。若想在鏈?zhǔn)綏５臈ｍ攕所指的結(jié)點(diǎn)，則應(yīng)執(zhí)行下列哪一個(gè)操作？top->link= (2)s->link=top->link;top->link=(3)s->link=top;top= (4)s->link=top;top=top-設(shè)鏈?zhǔn)綏Ｖ薪Y(jié)點(diǎn)的結(jié)構(gòu)為（data,link），top是指向棧頂?shù)闹羔?。若想摘除鏈?zhǔn)綏５膞中，則應(yīng)執(zhí)行下列哪一個(gè)操作？x=top->data;top=top- (2)top=top->link;x=top-(3)x=top;top=top- (4)x=top-若使用循環(huán)鏈表來表示隊(duì)列，p是鏈表中的一個(gè)指針(視為隊(duì)尾指針)。試基于此結(jié)構(gòu)給出隊(duì)列的插入(EnQueue)和刪除(DlQueue)p為何值時(shí)隊(duì)列空。A*B*-A+b-C+A*-B+(A+B)*D+E/(F+A*D)+A&&B||!(EF){C++的優(yōu)先級(jí)!(A&&!((B<C)||(C>D)))||(C<postfixen個(gè)運(yùn)算符和分界符，問棧中最多可存入多少en6層，問棧中最多可存入a*xb/x↑2ax*bx2↑/-。寫出a+b*(c-d)-e↑f/筆做5-3sn件物品，重量分別w[1],w[2],…w[n]n件物品中選擇若干件放入此背包中，使得放入的重量s。如果存在一種符合上述要求的選擇，則稱此背包問題有解(或稱其解為真)；否則稱此背包問題無解(或稱其解為假)。試用遞歸方法設(shè)計(jì)求解背包問題的算法。（提

ss

物品件數(shù)不能為負(fù)所選物品中不包w[n]

所選物品中包 D(A(c),B(e),C(a,L(b,c,J1(J2(J1,a,J3(J1)),上機(jī)5-1A[n](1)An5-5已知f為單鏈表的表頭指針,鏈表中的都是整型數(shù)據(jù)，試寫出實(shí)現(xiàn)下列運(yùn)算的(3)思考5-4【八皇后問題】設(shè)在初始狀態(tài)下在國際象棋棋盤上沒有任何棋子(皇后)1288刻，棋盤的合法布局都必須滿足3布局。(nj列安放一個(gè)棋子時(shí)，需要記錄在行方向、列方向、j+1列。)利用廣義表的head和tail操作寫出函數(shù)表達(dá)式，把以下各題中的單元素banana從L1(apple,pear,banana,L2((apple,pear),(banana,L3(((apple),(pear),(banana),L4((((apple))),((pear)),(banana),L5((((apple),pear),banana),L6(apple,(pear,(banana),域mark，以記錄該結(jié)點(diǎn)是否過。一旦某一個(gè)共享的子表結(jié)點(diǎn)被作了標(biāo)志，以后就參考akm(m,n)

n

當(dāng)m0當(dāng)m0n0時(shí)當(dāng)m0n0已知f為單鏈表的表頭指針,鏈表中的都是整型數(shù)據(jù)，試寫出實(shí)現(xiàn)下列運(yùn)算的遞歸算筆做64在結(jié)點(diǎn)個(gè)數(shù)為n(n>1)的各棵樹中，高度最小的樹的高度是多少？它有多少個(gè)葉結(jié)點(diǎn)？多少個(gè)分支結(jié)點(diǎn)？高度最大的樹的高度是多少？它有多少個(gè)葉結(jié)點(diǎn)？多少個(gè)分支結(jié)點(diǎn)？6-9hk叉樹有如下性質(zhì):h層上的結(jié)點(diǎn)都是葉結(jié)點(diǎn),其余各層上每k棵非空子樹如果按層次自頂向下同一層自左向右1開始對(duì)全部結(jié)點(diǎn)進(jìn)行編號(hào),試問:各層的結(jié)點(diǎn)個(gè)數(shù)是多少i的結(jié)點(diǎn)的父結(jié)點(diǎn)(若存在)的編號(hào)是多少im個(gè)孩子結(jié)點(diǎn)(若存在)的編號(hào)是多少i的結(jié)點(diǎn)有右兄弟的條件是什么?其右兄弟結(jié)點(diǎn)的編號(hào)是多少n,hn的什么函數(shù)關(guān)系6-10(1)上機(jī)6-8若用二叉鏈表作為二叉樹的表示，試針對(duì)以下問題編寫遞歸算法(1)思考n11的結(jié)點(diǎn)n22的結(jié)點(diǎn),,nmm的結(jié)點(diǎn),0的結(jié)點(diǎn)?試推導(dǎo)之。(2)以二叉樹為參數(shù)，交換每個(gè)結(jié)點(diǎn)的左和右如何搜索指定結(jié)點(diǎn)的序下的后繼參考使用(1)順序表示和(2)二叉鏈表表示法，分別畫出右圖所示二叉樹的表示33n個(gè)結(jié)點(diǎn)的理想平衡二叉樹（即除離根最遠(yuǎn)的最底層外其他各層都是滿的，最底層有若干結(jié)點(diǎn)）0n來表示（n0）？假定在一棵二叉樹中，度為2的結(jié)點(diǎn)有15個(gè)，度為1200的結(jié)(注:各題的題號(hào)為課后練習(xí)的題號(hào)（續(xù)筆做6-14判斷以下序列是否是最小堆如果不是(1){100,86,48,73,35,39,42,57,66,21(2){12,70,33,65,24,56,48,92,86,33(3){103,97,56,38,66,23,42,12,30,52,06,20{05,56,20,23,40,38,29,61,35,76,28,1006-16在森林的二叉樹表示中，用llink指向結(jié)點(diǎn)第一個(gè)的指針，用rlink指向結(jié)點(diǎn)下一個(gè)兄弟的指針，用data結(jié)點(diǎn)的值。如果我們采用靜態(tài)二叉鏈表作為森林的表示，同時(shí)按森林的先根次序依次安放森林的所有結(jié)點(diǎn)，則可以在它們的結(jié)點(diǎn)中用ltagllinkrtagrlinkltag=0，若ltag0，則該結(jié)點(diǎn)有；若rtag=0，則該結(jié)點(diǎn)沒有下一個(gè)兄弟，若rtag0，llinkrlink已知一棵二叉樹的前序遍歷的結(jié)果是ABECDFGHIJ,中序遍歷的結(jié)果是EBCDAFHIGJ,已知一棵樹的先根次序遍歷的結(jié)果與其對(duì)應(yīng)二叉樹表示(長子-兄弟表示)的前序遍歷結(jié)果相同,樹的先根次序遍歷結(jié)果和后根次序遍歷結(jié)果能否唯一確定一棵樹?8c1,c2,c3,c4,c5,c6,c7,c8組成,各字母在電文5,25,3,6,1011,36,48Huffman編碼,并上機(jī)T[n]中，T[n]中存放的是各結(jié)點(diǎn)的值。T[0]開始順序讀出各結(jié)點(diǎn)的值，建立該二叉樹的二叉鏈表表示。思考試編寫一個(gè)算法，把一個(gè)新結(jié)點(diǎn)l作為結(jié)點(diǎn)s的左插入到一棵線索化二叉樹中，s原來的左變成l的左。6-17二叉樹的雙序遍歷(Double-ordertraversal)是指：對(duì)于二叉樹的每一個(gè)結(jié)點(diǎn)來說，先這個(gè)結(jié)點(diǎn)，再按雙序遍歷它的左子樹，然后再一次這個(gè)結(jié)點(diǎn)，接下來按雙序遍給定權(quán)值集合{15,03,14,02,06,09,16,17},構(gòu)造相應(yīng)的霍夫曼樹,并計(jì)算它的帶給定一組權(quán)值:23,15,66,07,11,45,33,52,39,26,58,4叉樹44,所有外部結(jié)點(diǎn)的度都04叉樹的帶權(quán)外部路徑長度是多少?(提示：如果權(quán)值個(gè)數(shù)不足以構(gòu)造擴(kuò)充44參考若用二叉鏈表作為二叉樹的表示，試編寫一個(gè)遞歸算法求二叉樹中指定結(jié)點(diǎn)所在層次。(hh=-1h=0)若用二叉鏈表作為二叉樹的表示，試編寫一個(gè)遞歸算法，將它按完全二叉樹的順序T[n]中，T[n]中存放各結(jié)點(diǎn)的值。voidPreOrder(BinTreeNode*t)iftNULL //遞歸結(jié)束coutt PreOrdert->leftChild PreOrdert->rightChild }}PreOrderPreOrder(t->rightChildPreOrder設(shè)二叉樹采用二叉鏈表表示，指針root指向根結(jié)點(diǎn)，指針p指向二叉樹中某一指定結(jié)點(diǎn)。試編寫一個(gè)算法，找出從根結(jié)點(diǎn)到結(jié)點(diǎn)*p之間的路徑。4,2,5,8,3,6,1014n0層，則其高度為（A）h（空二叉樹的高度為-10）的二叉樹20的結(jié)點(diǎn)，則該二叉樹中所含結(jié)點(diǎn)至少有（B）個(gè)。F轉(zhuǎn)換成一棵二叉樹后，其根結(jié)點(diǎn)的右子樹中有（C）個(gè)結(jié)點(diǎn)。F轉(zhuǎn)換成一棵二叉樹后，其根結(jié)點(diǎn)的左子樹中有（D）個(gè)結(jié)點(diǎn)。820號(hào)，其他結(jié)40號(hào)結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為（E）。②log2(n+1)-③log2nB：①②2h-③2h④h②③④E：①②③④筆做7-2試編寫一個(gè)算法，打印一個(gè)有窮集合中的所有成員。要求使用集合抽象數(shù)據(jù)類型7-7017,094,154,170,275,503,509,512,553,612,765,897,908。試畫出對(duì)其進(jìn)行折半搜索時(shí)的判定樹,并計(jì)算搜索成功的平均搜索長度和搜7-8n個(gè)元素的有序順序表和無序順序表進(jìn)行順序搜索,試就下列三種情況分別搜索失敗搜索成功,k的對(duì)象搜索成功,且表中有若干個(gè)關(guān)鍵碼等于給定值k的對(duì)象,7-15在二叉搜索樹上刪除一個(gè)有兩個(gè)的結(jié)點(diǎn)時(shí)，可以采用以下三種方法TLXXDECFEBNOVOCTJULSEPAUGAPR,MARMAYJUNJANAVLAVL樹，并標(biāo)從第7-18題所建立的AVL樹中刪除關(guān)鍵碼MAY，為保持AVL樹的特性，應(yīng)如何進(jìn)行刪除和調(diào)整?FEB，又應(yīng)如何刪除與調(diào)整?1,2,3,…2k-1AVL樹中。試證明結(jié)果樹是上機(jī)考慮向鏈表來實(shí)現(xiàn)一個(gè)有序表，使得能在這個(gè)表中進(jìn)行正向和反向搜索。若pp指示的結(jié)點(diǎn)出發(fā)沿任一方向進(jìn)行。p。最后請(qǐng)給出搜索成功和搜索不成功時(shí)的平均搜索長度。思考7-4ABABA7-5ABABB7-9head指向具有最小關(guān)鍵碼的結(jié)功時(shí)函數(shù)返回被檢索的結(jié)點(diǎn)地址，若搜索不成功則函數(shù)返回空指針0。請(qǐng)說明如何保持指current以減少搜索時(shí)的平均搜索長度。SS3部分：在該路徑左邊結(jié)點(diǎn)中的元素組成的集合S1；在該路徑上的結(jié)點(diǎn)中的元素組成的集合S2S3。S=S1S2S3aS1,bS2,cS3abc請(qǐng)給出下列操作序列運(yùn)算的結(jié)果：Union(1,2),Union(34),Union(35),Union(1,Union(3,6),Union(8,9),Union(1,8),Union(3,10),Union(3,11),Union(3,12),Union(3,Union(14,15),Union(1617Union(14,16),Union(13),Union(1,14)7-16(1)設(shè)Tn個(gè)內(nèi)結(jié)點(diǎn)的擴(kuò)充二叉搜索樹,I是它的內(nèi)路徑長度,E是它的外路E=I+2n,n1。(2)利用(1)的結(jié)果,試說明:SnSn=(1+1/n)Un-1,nAVL樹,其最大高度是多少?最小高度是多少?參考對(duì)線性表進(jìn)行折半搜索時(shí)，要求線性表必須（A）n的線性表時(shí)，元素的平均搜索長度為（B）n的線性表時(shí)，元素的平均搜索長度為（C）折半搜索與二叉搜索樹（即二叉排序樹）的時(shí)間性能（D）順序搜索算法適合于結(jié)構(gòu)為（E）的線性表A：①以數(shù)組方式②以數(shù)組方式且結(jié)點(diǎn)按關(guān)鍵碼有序排③以方式④以方式且結(jié)點(diǎn)按關(guān)鍵碼有序排列B：①n/2 ②n ③(n+1)/2 ④(n-1)/2C：①O(n2) ②O(nlog2n) ③O(log2n) ④O(n)D：①相同 ②不相同E：①散列②順序③壓縮④索017,094,154,170,275,503,509,512,553,612,677,765,908。試畫出對(duì)其進(jìn)行順序搜索時(shí)的判定樹,并計(jì)算搜索成功的平均搜索長度和搜索不成功4625,7862,12,37,7029}試畫出從空樹起，逐個(gè)輸入各55,31,11,37,46,73,63,02,07從空樹開始構(gòu)造平衡二叉搜索樹,畫出每加入一個(gè)新結(jié)點(diǎn)時(shí)二叉樹的形態(tài)。若發(fā)生不平衡,指明需做的平衡旋轉(zhuǎn)的類型及平衡旋轉(zhuǎn)的結(jié)果。筆做8-11下圖是通圖，請(qǐng)畫8-15Dijkstra算法計(jì)算得到的從頂點(diǎn)①到其它各個(gè)頂點(diǎn)的最短路徑和最短上機(jī)試擴(kuò)充深度優(yōu)先搜索算法，在遍歷圖的過程中建立生成森林的左-右兄弟鏈viodaph::S(constintv,intviitd[],TreeNode<n>*t)tv（v某一未過的鄰接頂點(diǎn)w向下遍歷之前，建立結(jié)點(diǎn)。但需要判斷是作為根的第一還是作為其的右兄弟鏈入生成樹。8-20AOEel()思考8-41000個(gè)頂點(diǎn)，1000條邊，則形成的鄰接矩陣有多8-58-7nij之間是否有邊相連？任意一個(gè)頂點(diǎn)的度是多少？用鄰接表表示圖時(shí)，頂點(diǎn)個(gè)數(shù)設(shè)為n，邊的條數(shù)設(shè)為e，在鄰接表上執(zhí)行有關(guān)圖O(n*e)O(n+e)O(max(n,e))？8-1704的一些優(yōu)先關(guān)系的集合，試問它們是否定義了一個(gè)偏序關(guān)0<1;1<3;1<2;2<3;2<4;8-21AOEG是將該網(wǎng)絡(luò)的邊去掉方向和權(quán)后O(n+e)G中是否有參考1個(gè)頂點(diǎn)、2個(gè)頂點(diǎn)、3個(gè)頂點(diǎn)、45n個(gè)n(n-1)/2。有n個(gè)頂點(diǎn)的無向連通圖至少有多少條邊？有n個(gè)頂點(diǎn)的有向強(qiáng)連通圖至少有多少條對(duì)任何用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(AOV網(wǎng))n(n≥1)n-1n(n≥1)nne（A），所有邊鏈表中邊結(jié)點(diǎn)的總數(shù)為（B）采用鄰接表的圖的深度優(yōu)先遍歷算法類似于二叉樹的（C）采用鄰接表的圖的廣度優(yōu)先遍歷算法類似于二叉樹的（D）判斷有向圖是否存在回路，除了可以利用拓?fù)渑判蚍椒ㄍ猓€可以利用（E） ② ④B：①e/2 ②e ③2e ④n+eC~D：①中序遍歷 ②前序遍歷 ③后序遍歷 ④按層次遍歷E：①求關(guān)鍵路徑的方 ④廣度優(yōu)先遍歷算成樹算法的實(shí)現(xiàn)。并以右圖為例，寫出求解過程中計(jì)算連通網(wǎng)絡(luò)的最小生成樹的Dijkstra算法可描述如下：將連通網(wǎng)絡(luò)中所有的邊以方便T中。每次選擇并加入一條邊時(shí)，需要判斷T的邊構(gòu)成回路。如果構(gòu)成了回路，則從這個(gè)回路中將權(quán)值最大的邊Dijkstra算法的思想，設(shè)計(jì)一個(gè)求最小生成樹的算法。G3vertex，邊上的權(quán)值length和邊鏈表的指針link。用集合T=V(G)S代替STG=(V,E)G2G中必有AABCDEF(注:各題的題號(hào)為課后練習(xí)的題號(hào)筆做9-2設(shè)待排序的排序碼序列為{12,2,16,30,28,10,16*,20,6,18},試分別寫出使用以下(1)(2)希爾排序((3)(4)(5)(6)(7)(8)(9)i趟對(duì)序列中的所有偶數(shù)項(xiàng)i掃描。若i]i+1]，則交換它們。第三趟有對(duì)所有的奇數(shù)項(xiàng)，第四趟對(duì)所有的偶數(shù)項(xiàng)，…，如此反復(fù)，直到整個(gè)序列全部排好序?yàn)橹埂?-12手工對(duì)以下各序列進(jìn)行堆排序的過程。給出形成初始堆及每選出一個(gè)排序碼按字母順序排序：Tim,DotEvaRom,KimguyAnn,JimKayRon,按數(shù)值遞增順序排序：2633,35,2919,12,7個(gè)數(shù)字，換一個(gè)初始排列，再按數(shù)值的地政順序排序：12,19,33,26,29,9-13如果只想在一個(gè)有n個(gè)元素的任意序列中得到其中最小的第k(k<<n)個(gè)元前的部分排序序列,那么最好采用什么排序方法?為什么?例這樣一個(gè)序列:{503,017,908,170,897,275,653,612,154,509,612*,677,765,094},要得到其第4個(gè)元前的部有序序列017,094,154,170},用所選擇的算法實(shí)現(xiàn)時(shí)要執(zhí)行多少次比較9-16試編寫一個(gè)算法，將對(duì)象序列(x1x2,…,xn)p個(gè)位置，0pn。要求該O(n)O(1)。4500754509-241230,44,8,6,3,20,60,18,9,62,68,85做4上機(jī)9-15n個(gè)待排序元素存放在一個(gè)不帶表頭結(jié)點(diǎn)的單鏈表中,每個(gè)鏈表結(jié)點(diǎn)只存放一個(gè)元素r。試設(shè)計(jì)一個(gè)算法對(duì)其進(jìn)行二路歸并排序,要求不移動(dòng)結(jié)點(diǎn)中的元素,只改各鏈結(jié)點(diǎn)中的指針,r仍指示結(jié)果鏈表的第一個(gè)結(jié)點(diǎn)。（提示：先對(duì)待排序的單鏈表進(jìn)行一次掃描,將它劃分為若干有序的子鏈表,其表頭指針存放在一個(gè)指針隊(duì)列中。當(dāng)隊(duì)列不空時(shí)重復(fù)執(zhí)行,從隊(duì)列中退出兩個(gè)有序子鏈表,對(duì)它們進(jìn)行二路歸并,結(jié)果鏈表的表頭指針存放到隊(duì)列中。如果隊(duì)列中退出一個(gè)有序子鏈表后變成空隊(duì)列則算法結(jié)束。這個(gè)有9-18在已排好序的序列中，一個(gè)對(duì)象所處的位置取決于具有更小排序碼的對(duì)象的個(gè)數(shù)?；谶@個(gè)思想，可得計(jì)數(shù)排序方法。該方法在對(duì)象時(shí)為每個(gè)對(duì)象增加一個(gè)計(jì)數(shù)域count，用于存放在已排好序的序列中該對(duì)象前面的對(duì)象數(shù)目，最后依count域的值，將序列重新排列，就可完成排序。試編寫一個(gè)算法，實(shí)現(xiàn)計(jì)數(shù)排序。并說明對(duì)于一個(gè)有ncountn(n-1)/2思考9-3在起泡排序過程中，什么情況下排序碼會(huì)朝向與排序相反的方向移動(dòng)，試舉例說9-4試修改起泡排序算法，在正反兩個(gè)方向交替進(jìn)行掃描，即第一趟把排序碼最大的9-7試設(shè)計(jì)一個(gè)算法,O(n)的時(shí)間內(nèi)重排數(shù)組,將所有取負(fù)值的排序碼排在所有若參加錦標(biāo)賽排序的排序碼有11試給出適用于錦標(biāo)賽排序的勝者樹的類型。并寫一個(gè)函數(shù)，對(duì)n個(gè)參加排序n2的冪。設(shè)初始?xì)w并段為(10,15,31,),(9,20,),(22,34,37,),(6,15,42,),(12,37,(84,95,k5設(shè)輸入文件包含以下記錄：1422,7,24,15,16,11,100,10,9,20,12,90,17,13,26,38,30,25,50,28,110,21,40?，F(xiàn)采用置換-5參考在使用非遞歸方法實(shí)現(xiàn)快速排序時(shí),通常要利用一個(gè)棧待排序區(qū)間的兩個(gè)端點(diǎn)。那么能否用隊(duì)列來代替這個(gè)棧?為什么?希爾排序、簡單選擇排序、快速排序和堆排序是不穩(wěn)定的排序方法序排列的單鏈表。要求利用原來的結(jié)點(diǎn)空間并在結(jié)點(diǎn)間傳送數(shù)據(jù)。下列程序是一個(gè)歸并算法merge，只需一個(gè)附加。設(shè)算法中參加歸并的兩個(gè)歸A[0]A[n-1]B[0]B[m-1]，歸并后結(jié)果歸并段放在原地。數(shù)據(jù)結(jié)構(gòu)定義為：typedeffloatvoidmerge(datatype&A[],datatype&B[],intn,intm){inti,j;datatypetemp;for(i=0;i<n;i++){if(A[i]>B[0]){temp=A[n-for(j=n-2;j>=i;j--)A[j+1]=A[j];A[i]=B[0];if(temp<=B[1])B[0]=temp;else{for(j=1;j<m;j++if(temp>B[j])B[j-1]=B[j];else{B[j-1]=temp;break;}}}}}A={12,28,35,42,67},B={9,31,70}。寫出每次執(zhí)行算法最外層循環(huán)后各數(shù)A[n],B[m]在什么條件下，MSDLSDnnlog2n次排序碼比3如果操作系統(tǒng)要求一個(gè)程序同時(shí)可用的輸入/15個(gè)，則按多筆做10-42個(gè)字節(jié)的整型數(shù)關(guān)鍵碼和一個(gè)變長的oWorld! ThisstringisratherThisisonew10-8下圖(a)是一個(gè)3階B樹。試分別畫出在插 、、、之后B樹的變化10-9