華工數(shù)據(jù)結(jié)構(gòu)卷

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

2、結(jié)點(diǎn)(元素值均不相同)的二叉樹(shù)搜索樹(shù)有()種。A. 54B. 42C. 36D. 655. N 個(gè)頂點(diǎn)的連通圖至少有()條邊。A. N 1B. NC. N + 1D. 06.對(duì)于兩個(gè)函數(shù)，若函數(shù)名相同，但只是()不同則不是重載函數(shù)。A.參數(shù)類型B.參數(shù)個(gè)數(shù)C.函數(shù)類型D.函數(shù)個(gè)數(shù)則應(yīng)把形參變量表明為()參數(shù)。C.值D.地址)!C. O(m*n)D. O(m+n)!C. O(n2)D. O(n!)10.設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為(data, link) 已知指針 q 所指結(jié)點(diǎn)是指針 p 所指 結(jié)點(diǎn)的直接前驅(qū)，若在*q 與*p 之間插入結(jié)點(diǎn)*s，則應(yīng)執(zhí)行下列哪一個(gè)操作( )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.設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為(data, link)。若想摘除結(jié)點(diǎn)*p 的直接后繼，則應(yīng)執(zhí) 行下列哪一個(gè)操作()。！A. p-link=p-link-link;B. p=p-link; p-link=p-link-link7.若需要利用形參直接訪問(wèn)實(shí)參,A.指針B 引用8.下面程序的時(shí)間復(fù)雜度為(for(int i=0; ivm;i+)for(int j=0; jlink=p-link;D. p=p-link-lin

4、k;12.棧的插入和刪除操作在（）進(jìn)行。！A 棧頂B.棧底C.任意位置D.指定位置13若讓元素 1，2, 3 依次進(jìn)棧，則出棧次序不可能出現(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.折半搜索與二叉搜索樹(shù)（即二叉排序樹(shù)）的時(shí)間性能（）。A.相同B.完全不同C.有時(shí)不相同D.不確定仃.采用折半搜索算法搜索長(zhǎng)度為n 的有序表時(shí)，元素的平均搜索長(zhǎng)度

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

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

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

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

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

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

11、 n 1)個(gè)頂點(diǎn)的有向強(qiáng)連通圖最少有n 條邊。n) 15.連通分量是無(wú)向圖中的極小連通子圖。n) 16.二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)的度都是 2o(n ) 17.單鏈表從任何一個(gè)結(jié)點(diǎn)出發(fā)，都能訪問(wèn)到所有結(jié)點(diǎn)。四、程序閱讀填空1.在順序表中第 i 個(gè)位置插入新元素 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.刪去鏈表中除表頭結(jié)點(diǎn)外的所有其他結(jié)點(diǎn)template vclass Typevoid ListvType : MakeEmpty ( ) ListNode *q;while (first link!=NULL)q=first link;first link=q link;II 將表頭結(jié)點(diǎn)后第一個(gè)結(jié)點(diǎn)從鏈中摘下 delete q;II 釋放它last = first;II 修改表尾指針3.刪去鏈?zhǔn)疥?duì)頭結(jié)點(diǎn)(隊(duì)頭指針為QueueNode *front)，并返回隊(duì)頭元素的值template vclass Type Type Queue:DeQueue( ) ass

13、ert (!IsEmpty ();判隊(duì)空的斷言QueueNode *p =_ ront_ ;Type retvalue = p data;II 保存隊(duì)頭的值_front=front link_;新隊(duì)頭delete p; return retvalue;#4.最小堆的向下調(diào)整算法(沒(méi)有)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. 直接插入排序的算法(按關(guān)鍵碼 Key 非遞減順序?qū)?shù)據(jù)表 list 進(jìn)行排序) (無(wú))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. 直接選擇排序的算法：(沒(méi))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_ ;當(dāng)前具有最小關(guān)鍵碼的對(duì)象if(k!=i) Swap(list.Vectori, list.Vectork); / 交換#8.判斷一個(gè)帶表頭結(jié)點(diǎn)的雙向循環(huán)鏈表 L 是否對(duì)稱相等的算

18、法如下所示：(無(wú))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;五、簡(jiǎn)答題1.給定權(quán)值集合15, 03, 14, 02, 06, 09, 16,仃,構(gòu)造相應(yīng)的霍夫曼樹(shù),并計(jì)算它 的帶權(quán)外部路徑長(zhǎng)度。！F:03n11（皿）do(V)200209161749（02（03曲（03(V)11X 14】15（山）邏）邏）（2

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

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