2017華工數(shù)據(jù)結(jié)構(gòu)作業(yè)(已做)

1、.2017華工數(shù)據(jù)結(jié)構(gòu)作業(yè)一、程序閱讀填空1. 在順序表中第 i 個(gè)位置插入新元素 xtemplate int SeqList:Insert (Type & x, int i) if (ilast+1|last=MaxSize-1) return 0; /插入不成功 else last+; for( _int j=MaxSize-1_;ji;j-) _ _dataj+1=dataj_ _; datai = x; return 1; /插入成功 1. 直接選擇排序的算法 template void SelectSort(datalist & list) for(int i=0; ilist.Cu

2、rrentSize-1; i+) _SelectExchange(list,i)_; template viod SelectExchange(datalist & list, const int i)int k = i; for(int j=i+1;j list.CurrentSize;j+)if(list.Vectorj.getKey()list.Vectork.getKey()_ k=j_;/當(dāng)前具有最小關(guān)鍵碼的對(duì)象 if(k!=i) Swap(list.Vectori, list.Vectork); /交換3、 刪去鏈表中除表頭結(jié)點(diǎn)外的所有其他結(jié)點(diǎn)template void List

3、: MakeEmpty ( ) ListNode *q; while (firstlink!=NULL) _q=first-link_; _fitst-link=q-link_; /將表頭結(jié)點(diǎn)后第一個(gè)結(jié)點(diǎn)從鏈中摘下 delete q; /釋放它 last = first; /修改表尾指針4、基于有序順序表的折半搜索遞歸算法（Element為有序順序表）template int orderedList :BinarySearch(const Type & x, const int low, const int high)const int mid = -1; if ( low = high )

4、_mid=(low+high)/2_; if ( Elementmid.getKey( ) x ) mid = BinarySearch ( x, low, mid -1 ); return mid;5、在順序表中第 i 個(gè)位置插入新元素 x 。int insert(sqlist *L, datatype x, int i) int j; if (L-n=maxsize) cout”表滿(mǎn)，不能插入?。ㄉ弦纾﹏”; return 1; if( i=maxsize ) coutn;j=i;j-)L-dataj=L-dataj-1; /節(jié)點(diǎn)后移 L-dataj=x ; /插入xL-n+; /修改表長(zhǎng)

5、Return 1; /插入成功6、直接選擇排序的算法void SelectSort( list R, int n ) int i, j, k; for (i=1; i=n-1;i+) /n-1趟排序 k=i ; for(j=i+1;j=n,j+) /在當(dāng)前無(wú)序區(qū)中找鍵值最小的記錄Rk if(Rj.keyRk.key) k=j ;if(k!=i) R0=Ri; Ri=Rk; Rk=R0;二、簡(jiǎn)答題1. 線(xiàn)性表可用順序表或是鏈表存儲(chǔ)，此兩種存儲(chǔ)表示各有哪些優(yōu)缺點(diǎn)？答：1）順序存儲(chǔ)表示是將數(shù)據(jù)元素存放于一個(gè)聯(lián)系的存儲(chǔ)空間中，實(shí)現(xiàn)順序存取或（按下標(biāo)）直接存取。順序存儲(chǔ)的優(yōu)缺點(diǎn)有：（1） 它的存儲(chǔ)效率高

6、，存取速度快。但它的空間大小一經(jīng)定義，在程序整個(gè)運(yùn)行期間不會(huì)發(fā)生改變，因此，不易擴(kuò)充。（2） 由于在插入或刪除是，為了保持原有次序（沒(méi)有規(guī)定元素進(jìn)棧順序），平均需要移動(dòng)一半（或近一半）元素，修改效率不高。2）鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表存儲(chǔ)的優(yōu)缺點(diǎn)有：（1） 只要存儲(chǔ)器中還有空間，就不會(huì)產(chǎn)生存儲(chǔ)溢出問(wèn)題。（2） 在插入和刪除時(shí)不需要保存數(shù)據(jù)元素原來(lái)的物理順序，只需要保存原來(lái)的邏輯順序，因此不必移動(dòng)數(shù)據(jù)，只需修改它們的鏈接指針，修改效率較高。但存取表中的數(shù)據(jù)元素時(shí)，只能循鏈接順序訪(fǎng)問(wèn)，因此存取效率不高。 2. 設(shè)有一個(gè)

7、輸入數(shù)據(jù)的序列是46,25,78, 62, 12, 37, 70, 29，試畫(huà)出從空樹(shù)起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉搜索樹(shù)。答：按順序逐個(gè)輸入：46 / 25 78 / / 12 37 62 / 29 703.用廣義表的帶表頭結(jié)點(diǎn)的存儲(chǔ)表示法表示下列集合。A = ( )B = (6, 2)C = (a,( 5, 3, x)D = (B, C, A)E = (B, D)答： 4.上圖所示為一有向圖，請(qǐng)給出該圖的下述要求：（1）給出每個(gè)頂點(diǎn)的入度和出度；（2）以結(jié)點(diǎn)3為起始結(jié)點(diǎn)，分別畫(huà)出該圖的一個(gè)深度優(yōu)先生成樹(shù)和一個(gè)寬度優(yōu)先生成樹(shù)；（3）給出該圖的鄰接矩陣；（4）給出該圖的鄰接表；答：（1）頂點(diǎn)

8、 入度 出度 1 3 0 2 2 2 3 1 2 4 1 3 5 2 1 6 2 3 （2） 深度優(yōu)先生成樹(shù)廣度優(yōu)生成樹(shù)415623 125463000 （）鄰接矩陣 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 1 1 0 0 0 0 0 1 1 0 0 1 0(4)鄰接表 5. 對(duì)于如上圖所示的有向圖，試寫(xiě)出：(1) 從頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹(shù)；(2) 從頂點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹(shù)；答：（1）以頂點(diǎn) 為根的深度優(yōu)生樹(shù)（不唯一）： 或 （3） 以頂點(diǎn)為根的廣度優(yōu)生成樹(shù)： 6.已知二叉樹(shù)的先序、中序和后序序

9、列分別如下，但其中有一些已模糊不清，試構(gòu)造出該二叉樹(shù)。先序序列_BC_EF_中序序列BDE_AG_H后序序列_DC_GH_A答：后續(xù)最后一個(gè)是A，所以A是先序的第一個(gè)得到：先序序列ABC_EF_中序序列BDE_AG_H后序序列_DC_GH_A (A) / (BDE) (G_H) 先序的第二個(gè)元素時(shí)B，所以B是A的左子樹(shù)根節(jié)點(diǎn)，有中序B在最前，知道其他元素都在B的右子樹(shù)上。所以，后序序列為（DE_）B（B_H）A ,對(duì)比已有的后序序列_DC_GH_A得后序序列為：EDCBGHFA , 中序序列為：BDECAGFH 先序序列 ABC_EF_ 中序序列BDECAGFH 后序序列EDCBGHFA 所以

10、 （A） / (B) (F) / (C) (G) (H) / (D) (E) 7分析下列兩個(gè)程序段的運(yùn)行時(shí)間（時(shí)間復(fù)雜度）。void mystery (int n) int i, 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 (int n) int i, j, x = 0, y = 0; for (i =1; i = n; i+) if odd(i) for(j = i; j = n; j+) x+; for( j = 1; j = i; j+) y+; 答：O(

11、n2)8.有一組數(shù)據(jù)：25，50，70，21，4，18，100，43，7，12?，F(xiàn)采用汽泡排序算法進(jìn)行排序，寫(xiě)出每趟排序的結(jié)果，并標(biāo)明第一趟數(shù)據(jù)的移動(dòng)情況。答：第一趟：25， 50 ，70 ，21， 4， 18， 100， 43， 7， 1225， 50， 70， 21， 4， 18， 100， 43， 7， 12 25， 50， 21， 70， 4， 18， 100， 43， 7 ，1225， 50， 21， 4， 70， 18， 100， 43， 7， 12 25， 50， 21， 4， 18， 70， 100， 43， 7， 12 25， 50， 21， 4， 18， 70， 100， 43， 7， 12 25， 50， 21， 4， 18， 70， 43， 100， 7， 12 25， 50， 21， 4， 18， 70， 43， 7， 100， 1225， 50， 21， 4， 18， 70， 43， 7， 12， 100第二趟：25， 21， 4， 18， 50， 43， 7， 12， 70， 100第三趟：21， 4， 18， 25， 43， 7