2017華工數據結構作業(已做)_第1頁
2017華工數據結構作業(已做)_第2頁
2017華工數據結構作業(已做)_第3頁
2017華工數據結構作業(已做)_第4頁
2017華工數據結構作業(已做)_第5頁
已閱讀5頁,還剩9頁未讀 繼續免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

1、2017華工數據結構作業一、程序閱讀填空1. 在順序表中第 i 個位置插入新元素 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.Cur

2、rentSize-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_;/當前具有最小關鍵碼的對象 if(k!=i) Swap(list.Vectori, list.Vectork); /交換3、 刪去鏈表中除表頭結點外的所有其他結點template void List :

3、 MakeEmpty ( ) ListNode *q; while (firstlink!=NULL) _q=first-link_; _fitst-link=q-link_; /將表頭結點后第一個結點從鏈中摘下 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 個位置插入新元素 x 。int insert(sqlist *L, datatype x, int i) int j; if (L-n=maxsize) cout”表滿,不能插入!(上溢)n”; return 1; if( i=maxsize ) coutn;j=i;j-)L-dataj=L-dataj-1; /節點后移 L-dataj=x ; /插入xL-n+; /修改表長R

5、eturn 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+) /在當前無序區中找鍵值最小的記錄Rk if(Rj.keyRk.key) k=j ;if(k!=i) R0=Ri; Ri=Rk; Rk=R0;二、簡答題1. 線性表可用順序表或是鏈表存儲,此兩種存儲表示各有哪些優缺點?答:1)順序存儲表示是將數據元素存放于一個聯系的存儲空間中,實現順序存取或(按下標)直接存取。順序存儲的優缺點有:(1) 它的存儲效率高,

6、存取速度快。但它的空間大小一經定義,在程序整個運行期間不會發生改變,因此,不易擴充。(2) 由于在插入或刪除是,為了保持原有次序(沒有規定元素進棧順序),平均需要移動一半(或近一半)元素,修改效率不高。2)鏈表是一種物理存儲單元上非連續、非順序的存儲結構,數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表存儲的優缺點有:(1) 只要存儲器中還有空間,就不會產生存儲溢出問題。(2) 在插入和刪除時不需要保存數據元素原來的物理順序,只需要保存原來的邏輯順序,因此不必移動數據,只需修改它們的鏈接指針,修改效率較高。但存取表中的數據元素時,只能循鏈接順序訪問,因此存取效率不高。 2. 設有一個輸

7、入數據的序列是46,25,78, 62, 12, 37, 70, 29,試畫出從空樹起,逐個輸入各個數據而生成的二叉搜索樹。答:按順序逐個輸入:46 / 25 78 / / 12 37 62 / 29 703.用廣義表的帶表頭結點的存儲表示法表示下列集合。A = ( )B = (6, 2)C = (a,( 5, 3, x)D = (B, C, A)E = (B, D)答: 4.上圖所示為一有向圖,請給出該圖的下述要求:(1)給出每個頂點的入度和出度;(2)以結點3為起始結點,分別畫出該圖的一個深度優先生成樹和一個寬度優先生成樹;(3)給出該圖的鄰接矩陣;(4)給出該圖的鄰接表;答:(1)頂點

8、入度 出度 1 3 0 2 2 2 3 1 2 4 1 3 5 2 1 6 2 3 (2) 深度優先生成樹廣度優生成樹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. 對于如上圖所示的有向圖,試寫出:(1) 從頂點出發進行深度優先搜索所得到的深度優先生成樹;(2) 從頂點出發進行廣度優先搜索所得到的廣度優先生成樹;答:(1)以頂點 為根的深度優生樹(不唯一): 或 (3) 以頂點為根的廣度優生成樹: 6.已知二叉樹的先序、中序和后序序列

9、分別如下,但其中有一些已模糊不清,試構造出該二叉樹。先序序列_BC_EF_中序序列BDE_AG_H后序序列_DC_GH_A答:后續最后一個是A,所以A是先序的第一個得到:先序序列ABC_EF_中序序列BDE_AG_H后序序列_DC_GH_A (A) / (BDE) (G_H) 先序的第二個元素時B,所以B是A的左子樹根節點,有中序B在最前,知道其他元素都在B的右子樹上。所以,后序序列為(DE_)B(B_H)A ,對比已有的后序序列_DC_GH_A得后序序列為:EDCBGHFA , 中序序列為:BDECAGFH 先序序列 ABC_EF_ 中序序列BDECAGFH 后序序列EDCBGHFA 所以

10、(A) / (B) (F) / (C) (G) (H) / (D) (E) 7分析下列兩個程序段的運行時間(時間復雜度)。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(n

11、2)8.有一組數據:25,50,70,21,4,18,100,43,7,12。現采用汽泡排序算法進行排序,寫出每趟排序的結果,并標明第一趟數據的移動情況。答:第一趟: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,

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論