華工數(shù)據(jù)結構卷

1、華工數(shù)據(jù)結構卷一. 選擇題1.向一個有 127 個元素的順序表中插入一個新元素并保持原來順序不變，平均 要移動()個元素。A. 8B. 63.5C. 63D. 7 2.設有一個二維數(shù)組Amn，假設 A00存放位置在 644 (10), A22存放 位置在 676 (10),每個元素占一個空間，則 A33在( )位置，(10)表 明用 10 進數(shù)表示。！ P113A. 692 (10)B. 626 ( 10)C. 709 ( 10)D. 724 (10) 3. 一個有序順序表有255 個對象，采用順序搜索查表，平均搜索長度為( )。？A. 128B 127C. 126D. 255 4.含 5 個

2、結點(元素值均不相同)的二叉樹搜索樹有()種。A. 54B. 42C. 36D. 655. N 個頂點的連通圖至少有()條邊。A. N 1B. NC. N + 1D. 06.對于兩個函數(shù)，若函數(shù)名相同，但只是()不同則不是重載函數(shù)。A.參數(shù)類型B.參數(shù)個數(shù)C.函數(shù)類型D.函數(shù)個數(shù)則應把形參變量表明為()參數(shù)。C.值D.地址)!C. O(m*n)D. O(m+n)!C. O(n2)D. O(n!)10.設單鏈表中結點的結構為(data, link) 已知指針 q 所指結點是指針 p 所指 結點的直接前驅(qū)，若在*q 與*p 之間插入結點*s，則應執(zhí)行下列哪一個操作( )A. s-link=p-li

3、nk; p-link =s; B. q-link=s; s-link =p;C. p-link=s-link; s-link =q; D. p-link=s; s-link =q;11.設單鏈表中結點的結構為(data, link)。若想摘除結點*p 的直接后繼，則應執(zhí) 行下列哪一個操作()。！A. p-link=p-link-link;B. p=p-link; p-link=p-link-link7.若需要利用形參直接訪問實參,A.指針B 引用8.下面程序的時間復雜度為(for(int i=0; ivm;i+)for(int j=0; jlink=p-link;D. p=p-link-lin

4、k;12.棧的插入和刪除操作在（）進行。！A 棧頂B.棧底C.任意位置D.指定位置13若讓元素 1，2, 3 依次進棧，則出棧次序不可能出現(xiàn)哪種情況（）。!A. 3, 2, 1B. 2, 1, 3C. 3, 1, 2D.1, 3, 2#14. 廣義表 A（a）,則表尾為（)0A. aB.()C.空表D. (a)#15. 下列廣義表是線性表的有（）。A. E(a,(b,c)B. E(a,E) C. E(a,b) D. E(a丄丄()16.折半搜索與二叉搜索樹（即二叉排序樹）的時間性能（）。A.相同B.完全不同C.有時不相同D.不確定仃.采用折半搜索算法搜索長度為n 的有序表時，元素的平均搜索長度

5、為（）。！A. O（nlog2n）B. O（n）C. O（log2n）D. O（n）18. 采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的（）。！A.中序遍歷B.前序遍歷 C.后序遍歷 D.按層次遍歷19.每次從無序表中挑選出一個最小或最大元素，把它交換到有序表的一端，此種排序方法叫做（）排序。！A.插入B.選擇C.交換D.外排序20.采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的（）。A.中序遍歷B 前序遍歷C.后序遍歷 D.按層次遍歷二. 填空題1.算法是一個有窮的指令集，它為解決某一特定任務規(guī)定了一個運算序列。它應具有輸入、輸出、確定性_ 、有窮性和可執(zhí)行性等特性。！ 2.在一棵

6、度為 3 的樹中，度為 2 的結點個數(shù)是 1,度為 0 的結點個數(shù)是 6,則 度為 3的結點個數(shù)是_ 2_。！3._ 隊列的插入操作在 _隊尾_進行，刪除操作在 _隊頭_進行。4.當用長度為 n 的數(shù)組順序存儲一個棧時，若用top=n 表示棧空，則表示棧滿的條件為_ top=0_。 ！5. 對序列（49,38,65,97,76,27,13,50 采用快速排序法進行排序，以序列的第一個元素為基準元素得到的劃分結果是 13 27 384550 65 76 97。！6._對于一棵具有 n 個結點的樹，該樹中所有結點的度數(shù)之和為n-1 。7在一個堆的順序存儲中，若一個結點的下標為i，則它的左子女結點的

7、下標為_ 2i+1_ ，右子女結點的下標為 2i+2_。 8.請指出在順序表2、5、7、10、14、15、18、23、35、41、52中，用折半 查找關鍵碼 12 需做 4次關鍵碼比較。!9若線性表采用順序存儲結構，每個元素占用 4 個存儲單元，第一個元素的存儲 地址為 100,則第 12 個元素的存儲地址是 _ 144_。10.在一個長度為 n 的順序表中，向第 i 個元素(K ifront =(QU-rear+1)% m_ 。_ 。#15.設有廣義表【不要求廣義表】D(a,b,D)，其長度為3_ ，深度為。16.在一個具有n 個頂點的無向完全圖中，要連通所有頂點則至少需要_ n-1_ 條邊

8、，在一個具有 n 個頂點的有向完全圖中，包含有 _n(n-1)_ 條邊。仃.對于一個具有n 個頂點的圖，若采用鄰接矩陣表示，則矩陣大小為_ n*n_ 。18. 對于一個具有 n 個頂點和 e 條邊的連通圖，其生成樹中頂點數(shù)和邊數(shù)分別為_ n_和_n-1_ 。19. 在直接選擇排序中，記錄比較次數(shù)的時間復雜度為_O(n*n)_ ，記錄移動次數(shù)的時間復雜度為 _ O(n)_。20._快速排序在平均情況下的空間復雜度為 _O(logn)_ ，在最壞情況下的空間復雜度為_0(n)_。21.當問題的規(guī)模 n 趨向無窮大時，算法執(zhí)行時間T(n)的數(shù)量級被稱為算法的_ 時間復雜度_025. 在一個無向圖的鄰

9、接表中，若表結點的個數(shù)是m，則圖中邊的條數(shù)是_ m/2_o26. 對于一個具有 n 個頂點的圖，若采用鄰接矩陣表示，則矩陣大小為 _ n的平方 。三、判斷題(y ) 1.直接選擇排序是一種不穩(wěn)定的排序方法。n) 2.折半搜索只適用于有序表，包括有序的順序表和有序的鏈表。y) 3.數(shù)據(jù)的邏輯結構與數(shù)據(jù)元素本身的內(nèi)容和形式無關。n) 4.數(shù)據(jù)結構是指相互之間存在一種或多種關系的數(shù)據(jù)元素的全體。(n) 5.線性表的邏輯順序與物理順序總是一致的。(y) 6.線性表若采用鏈式存儲表示時所有存儲單元的地址可連續(xù)可不連續(xù)。y) 7.二叉樹是數(shù)的特殊情形。y) 8.若有一個葉子結點是二叉樹中某個子樹的中序遍歷

10、結果序列的最后一個 結點，則它一定是該子樹的前序遍歷結果序列的最后一個結點。n) 9.若有一個葉子結點是二叉樹中某個子樹的前序遍歷結果序列的最后一 個結點，則它一定是該子樹的中序遍歷結果序列的最后一個結點。n) 10.任一棵二叉搜索樹的平均搜索時間都小于用順序搜索法搜索同樣結點 的順序表的平均搜索時間。n) 11.對于同一組待輸入的關鍵碼集合，雖然各關鍵碼的輸入次序不同，但 得到的二叉搜索樹都是相同的。(y) 12.最優(yōu)二叉搜索樹的任何子樹都是最優(yōu)二叉搜索樹。(y ) 13.在二叉搜索樹上插入新結點時，不必移動其它結點，僅需改動某個結 點的指針，使它由空變?yōu)榉强占纯伞?y ) 14.有 n (

11、 n 1)個頂點的有向強連通圖最少有n 條邊。n) 15.連通分量是無向圖中的極小連通子圖。n) 16.二叉樹中任何一個結點的度都是 2o(n ) 17.單鏈表從任何一個結點出發(fā)，都能訪問到所有結點。四、程序閱讀填空1.在順序表中第 i 個位置插入新元素 x !template vclass Typeint SeqListvType:lnsert (Type & x, int i) if(iv0|ilast+1|last=MaxSize-1)return 0; /插入不成功 else last+;for(int j=last;ji;j-)dataj=dataj-1;datai = x;

12、 return 1;II插入成功2.刪去鏈表中除表頭結點外的所有其他結點template vclass Typevoid ListvType : MakeEmpty ( ) ListNode *q;while (first link!=NULL)q=first link;first link=q link;II 將表頭結點后第一個結點從鏈中摘下 delete q;II 釋放它last = first;II 修改表尾指針3.刪去鏈式隊頭結點(隊頭指針為QueueNode *front)，并返回隊頭元素的值template vclass Type Type Queue:DeQueue( ) ass

13、ert (!IsEmpty ();判隊空的斷言QueueNode *p =_ ront_ ;Type retvalue = p data;II 保存隊頭的值_front=front link_;新隊頭delete p; return retvalue;#4.最小堆的向下調(diào)整算法(沒有)template vclass Type void MinHeapvType:FilterDown(int start, intEndOfHeap)int i = start, j = 2*i+1;II j 是 i 的左子女Type temp = heapi;while ( j v= EndOfHeap ) if

14、 ( j v EndOfHeap & heapj.key heapj+1.key ) j+;兩子女中選小者if ( temp.key v= heapj.key ) break;else heapi = heapj; i = j; j=2*j+1 _ ； _heapi=temp;_;5 基于有序順序表的折半搜索遞歸算法(Element 為有序順序表)！template vclass Typeint orderedList :BinarySearch(const Type & x, const int low, const int high)const int mid = -1;i

15、f ( low = high ) _ mid=(low+high)/2_ ;if ( Elementmid.getKey( ) x )mid = BinarySearch ( x, low, mid -1 );return mid;6. 直接插入排序的算法(按關鍵碼 Key 非遞減順序?qū)?shù)據(jù)表 list 進行排序) (無)template vclass Type void InsertionSort(datalist & list)for(int i=1; ivlist.CurrentSize; i+)_ inter(list,i)_;template vclass Type viod

16、 Insert(datalist & list, int i) Elementtemp = list.Vectori;int j = i;/從后向前順序比較while(j0 & temp.getKey( )vlist.Vectorj-1.getKey( )_ ist.vectorj=list.vectorj-1_;j-;list.Vectorj = temp;7. 直接選擇排序的算法：(沒)template vclass Type void SelectSort(datalistvType & list)for(int i=0; ivlist.CurrentSize-1

17、; i+)_ SelectExchange(list,_ ; template vclass Type viod SelectExchange(datalistvType & list, constint i)(IV)int k = i;for(int j=i+1;jv list.CurrentSize;j+)if(list.Vectorj.getKey()vlistVectork.getKey()k=j_ ;當前具有最小關鍵碼的對象if(k!=i) Swap(list.Vectori, list.Vectork); / 交換#8.判斷一個帶表頭結點的雙向循環(huán)鏈表 L 是否對稱相等的算

18、法如下所示：(無)int symmetry(DblList DL)int sym=1;DblNode *p=DL-rLink, *q=DL-lLink;While(p!=q & p-rLink!=q & sym=1)if(p-data=q-data) _ =p rLink_ ;lLinkelse sym=0;return sym;五、簡答題1.給定權值集合15, 03, 14, 02, 06, 09, 16,仃,構造相應的霍夫曼樹,并計算它 的帶權外部路徑長度。！F:03n11（皿）do(V)200209161749（02（03曲（03(V)11X 14】15（山）邏）邏）（2

19、0（辺矽o11:16 :；172011.14(W)：33F:(H)(IV)(112.線性表可用順序表或是鏈表存儲，此兩種存儲表示各有哪些特點，優(yōu)缺 點？！P503.設有一個輸入數(shù)據(jù)的序列是46,25,78, 62, 12, 37, 70, 29，試畫出從空樹起,逐個輸入各個數(shù)據(jù)而生成的二叉搜索樹。按順序逐個輸入46/2578/123762/29704.對于如右圖所示的有向圖，試寫出：！(1) 從頂點出發(fā)進行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹;(2) 從頂點出發(fā)進行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹;/ /C6)C7 (20此樹的帶權路徑長度WPL = 229。#5用廣義表的帶表頭結點的存儲表示

20、法表示下列集合A =()B = (6, 2)C = (5, 3, XD = (B, C, A)E = (B, D) 6右圖所示為一有向圖，請給出該圖的下述要求:(1)給出每個頂點的入度和出度；1 3 02 2 23 1 24 3 15 2 16 1 4(2)以結點 3 為起始結點，分別畫出該圖的一個深度優(yōu)先生成樹和一個寬度優(yōu) 先生成樹；(3)給出該圖的鄰接矩陣;(4)給出該圖的鄰接表；(5)給出該圖的逆鄰接表；7.已知二叉樹的先序、中序和后序序列分別如下，但其中有一些已模糊不清, 試構造出該二叉樹。先序序列 _BC_EF_中序序列 BDE_AG_H后序序列 e_DCb_GHf_A&已某個不帶權的無向圖采用鄰接矩陣存儲方法依次將頂點的數(shù)據(jù)信息存放于 一維數(shù)組 ABCDEFGH 中，邊的信息存放于鄰接矩陣中，鄰接矩陣為0 1 1 0 0 0 0 01 0 0 0 1 0 1 11 0 0