2017華工數(shù)據(jù)結構作業(yè)一、程序閱讀填空在次序表中第i個地址插入新元素xtemplate<classType>intSeqList<Type>::Insert(Type&x,inti){if(i<0||i>last+1||last==MaxSize-1)return0;//插入不行功else{last++;for(________intj=MaxSize-1________________;j>i;j--)___________data[j+1]=data[j]__________________;data[i]=x;return1;//插入成功}}直接選擇排序的算法template<classType>voidSelectSort(datalist<Type>&list){for(inti=0;i<list.CurrentSize-1;i++)_______SelectExchange(list,i)_________________;}template<classType>viodSelectExchange(datalist<Type>&list,constinti){intk=i;for(intj=i+1;j<list.CurrentSize;j++)if(list.Vector[j].getKey()<list.Vector[k].getKey())___k=j__________________;//當前擁有最小要點碼的對象if(k!=i)S[i],list.Vector[k]);//交換}3、刪去鏈表中除表頭結點外的全部其余結點template<classType>voidList<Type>::MakeEmpty(){ListNode<Type>*q;while(first→link!=NULL){____________q=first->link______________;_________fitst->link=q->link_________________;將表頭結點后第一個結點從鏈中摘下deleteq;//開釋它}last=first;//更正表尾指針}4、基于有序次序表的折半找尋遞歸算法（Element為有序次序表）template<classType>intorderedList<Type>::BinarySearch(constType&x,constintlow,constinthigh)const{intmid=-1;if(low<=high){________mid=(low+high)/2__________________;if(Element[mid].getKey()<x)mid=BinarySearch(__________x,mid+1,high________________);elseif(Element[mid].getKey()>x)mid=BinarySearch(x,low,mid-1);}returnmid;}5、在次序表中第i個地址插入新元素x。intinsert(sqlist*L,datatypex,inti){intj;if(L->n==maxsize){cout<<”表滿，不可以插入！（上溢）n”;return–1;}if(

i<0||i>=maxsize

)

{cout<<

”非法插入地址！n”;return0;}for(j=L->n;j>=i;j--)L->data[j]=L->data[j-1];

//節(jié)點后移L->data[j]=x

;

//插入

xL->n++;

//更正表長Return1;

//插入成功}6、直接選擇排序的算法voidSelectSort(listR,intn){inti,j,k;for(i=1;i<=n-1;i++)

{

//n-1

趟排序k=i

;for(j=i+1;j<=n,j++)//在當前無序區(qū)中找鍵值最小的記錄R[k]if(R[j].key<R[k].key)k=j;if(k!=i){R[0]=R[i];R[i]=R[k];R[k]=R[0];}}}二、簡答題線性表可用次序表或是鏈表儲存，此兩種儲存表示各有哪些優(yōu)弊端？答：1）次序儲存表示是將數(shù)據(jù)元素存放于一個聯(lián)系的儲存空間中，實現(xiàn)次序存取或（按下標）直接存取。次序儲存的優(yōu)弊端有：1）它的儲存效率高，存取速度快。但它的空間大小一經(jīng)定義，在程序整個運轉時期不會發(fā)生改變，所以，不易擴大。2）因為在插入或刪除是，為了保持原有次序（沒有規(guī)定元素進棧次序），均勻需要挪動一半（或近一半）元素，更正效率不高。）鏈表是一種物理儲存單元上非連續(xù)、非次序的儲存結構，數(shù)據(jù)元素的邏輯次序是經(jīng)過鏈表中的指針鏈接次序實現(xiàn)的。鏈表儲存的優(yōu)弊端有：1）只要儲存器中還有空間，就不會產(chǎn)生儲存溢出問題。2）在插入和刪除時不需要保存數(shù)據(jù)元素本來的物理次序，只要要保存本來的邏輯次序，所以不用挪動數(shù)據(jù)，只要更正它們的鏈接指針，更正效率較高。但存取表中的數(shù)據(jù)元素時，只好循鏈接次序接見，所以存取效率不高。2.設有一個輸入數(shù)據(jù)的序列是{46,25,78,62,12,37,70,29}，試畫出從空樹起，逐一輸入各個數(shù)據(jù)而生成的二叉找尋樹。答：挨次序逐一輸入：46\2578/\/123762/\29703.用廣義表的帶表頭結點的儲存表示法表示以下會集。A=()B=(6,2)C=(‘a(chǎn)’,(5,3,‘x’))D=(B,C,A)E=(B,D)答：4.上圖所示為一有向圖，請給出該圖的下述要求：（1）給出每個極點的入度和出度；2）以結點3為初步結點，分別畫出該圖的一個深度優(yōu)先生成樹和一個寬度優(yōu)先生成樹；3）給出該圖的毗鄰矩陣；4）給出該圖的毗鄰表；答：（1）極點入度出度1302223124135216232）深度優(yōu)先生成樹廣度優(yōu)生成樹1516624233（３）毗鄰矩陣000000100100010001001011100000110010毗鄰表對于如上圖所示的有向圖，試寫出：從極點①出發(fā)進行深度優(yōu)先找尋所獲取的深度優(yōu)先生成樹；從極點②出發(fā)進行廣度優(yōu)先找尋所獲取的廣度優(yōu)先生成樹；答：（1）以極點①為根的深度優(yōu)生樹（不獨一）：②③④⑤⑥①①②③或②③④⑤④⑤3）以極點②為根的廣度優(yōu)生成樹：④②③⑤①6.已知二叉樹的先序、中序和后序序列分別以下，但此中有一些已模糊不清，試構造出該二叉樹。先序序列_BC_EF__中序序列BDE_AG_H后序序列_DC_GH_A答：后續(xù)最后一個是A，所以A是先序的第一個獲取：先序序列ABC_EF_中序序列BDE_AG_H后序序列_DC_GH_A(A)/

\(BDE)

(G_H)先序的第二個元素時B，所以B是A的左子樹根節(jié)點，有中序B在最前，知道其他元素都在B的右子樹上。所以，后序序列為（DE_）B（B_H）A,比較已有的后序序列_DC_GH_A得后序序列為：EDCBGHFA,中序序列為：BDECAGFH先序序列ABC_EF_中序序列BDECAGFH后序序列EDCBGHFA所以（A）/

\(B)

(F)\

/

\(C)(G)(H)/(D)\(E)．解析以下兩個程序段的運轉時間（時間復雜度）。voidmystery(intn){inti,j,k;for(i=1;i<n;i++)for(j=i+1;j<=n;j++)for(k=1;k<=j;k++);}答：O(n3)void{

odd(intn)inti,j,x=0,y=0;for(i=1;i<=n;i++)ifodd(i){for(j=i;j<=n;j++)for(j=1;j<=i;j++)

x++;y++;}}答：O(n2)8.有一組數(shù)據(jù)：25，50，70，21，4，18，100，43，7，12。現(xiàn)采納汽泡排序算法進行排序，寫出每趟排序的結果，并注明第一趟數(shù)據(jù)的挪動狀況。答：第一趟：25，50，70，21，4，18，100，43，7，1225，50，70，21，4，18，100，43，7，1225，50，21，70，4，18，100，43，7，1225，50，21，4，70，18，100，43，7，1225，50，21，4，18，70，100，43，7，1225，50，21，4，18，70，100，43，7，1225，50，21，4，18，70，43，100，7，1225，50，21，4，18，70，43，7，100，1225，50，21，4，18，70，43，7，12，100第二趟：25，2