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

1、一. 選擇題 1. 向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變，平均要移動(dòng)（ ）個(gè)元素。 A8 B. 63.5 C. 63 D. 72. 設(shè)有一個(gè)二維數(shù)組Amn，假設(shè)A00存放位置在644（10），A22存放位置在676（10），每個(gè)元素占一個(gè)空間，則A33在（ ）位置，（10）表明用10進(jìn)數(shù)表示。！P113 A692（10） B. 626（10） C. 709（10） D. 724（10）3. 一個(gè)有序順序表有255個(gè)對(duì)象，采用順序搜索查表，平均搜索長度為（ ）。？ A128 B. 127 C. 126 D. 2554. 含5個(gè)結(jié)點(diǎn)（元素值均不相同）的二叉樹搜索樹有（ ）

2、種。 A54 B. 42 C. 36 D. 655N個(gè)頂點(diǎn)的連通圖至少有（ ）條邊。 AN1 B. N C. N1 D. 06 對(duì)于兩個(gè)函數(shù)，若函數(shù)名相同，但只是（ ）不同則不是重載函數(shù)。 A參數(shù)類型 B. 參數(shù)個(gè)數(shù) C. 函數(shù)類型 D.函數(shù)個(gè)數(shù) 7 若需要利用形參直接訪問實(shí)參，則應(yīng)把形參變量表明為（ ）參數(shù)。 A指針 B.引用 C. 值 D.地址8 下面程序的時(shí)間復(fù)雜度為（ ）。！ for(int i=0; im;i+) for(int j=0; jlink=p-link; p-link =s; B. q-link=s; s-link =p; C. p-link=s-link; s-link

3、 =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è)操作（ ）。！Ap-link=p-link-link; B. p=p-link; p-link=p-link-linkC. p-link=p-link; D. p=p-link-link;12. 棧的插入和刪除操作在（ ）進(jìn)行。！ A棧頂 B. 棧底 C. 任意位置 D. 指定位置13若讓元素1，2，3依次進(jìn)棧，則出棧次序不可能出現(xiàn)哪種情況（ ）。！ A3，2，1 B. 2，1，3 C. 3，1，2 D. 1，3，2#14 廣義表A(a)

4、,則表尾為（ ）。Aa B. () C. 空表 D. （a）#15 下列廣義表是線性表的有（ ）。 AE(a,(b,c) B. E(a,E) C. E(a,b) D. E(a,L()16. 折半搜索與二叉搜索樹（即二叉排序樹）的時(shí)間性能（ ）。 A相同 B. 完全不同 C. 有時(shí)不相同 D. 不確定17 采用折半搜索算法搜索長度為n的有序表時(shí)，元素的平均搜索長度為（ ）。！AO(nlog2n) B. O(n) C. O(log2n) D. O(n)18. 采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于二叉樹的（ ）。！ A中序遍歷 B. 前序遍歷 C. 后序遍歷 D. 按層次遍歷19 每次從無序表

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

6、n表示棧空，則表示棧滿的條件為_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)的樹，該樹中所有結(jié)點(diǎn)的度數(shù)之和為_n-1_。7.在一個(gè)堆的順序存儲(chǔ)中，若一個(gè)結(jié)點(diǎn)的下標(biāo)為i，則它的左子女結(jié)點(diǎn)的下標(biāo)為_2i+1_，右子女結(jié)點(diǎn)的下標(biāo)為_2i+2_。8. 請指出在順序表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ǔ)單元

7、，第一個(gè)元素的存儲(chǔ)地址為100,則第12個(gè)元素的存儲(chǔ)地址是_144_。10. 在一個(gè)長度為n 的順序表中，向第i個(gè)元素（1 i n）之前插入一個(gè)新元素時(shí)，需要向后移動(dòng)_n-i+1_個(gè)元素。？11.設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作_求子串_。12.以折半搜索方法搜索一個(gè)線性表時(shí)，此線性表必須是_順序_存儲(chǔ)的_有序_表。13.在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的 _2_倍。14.判定一個(gè)循環(huán)隊(duì)列QU(最多元素為m)為滿隊(duì)列的條件是_QU-front = = (QU-rear+1)% m_。_。#15設(shè)有廣義表【不要求廣義表】D(a,b,D)，其長度為_3_，深度為_

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

9、算法的_時(shí)間復(fù)雜度_。 25.在一個(gè)無向圖的鄰接表中，若表結(jié)點(diǎn)的個(gè)數(shù)是m，則圖中邊的條數(shù)是_m/2_條。 26. 對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的圖，若采用鄰接矩陣表示 ，則矩陣大小為_n的平方_。 三、判斷題 （y ）1. 直接選擇排序是一種不穩(wěn)定的排序方法。（ n）2. 折半搜索只適用于有序表，包括有序的順序表和有序的鏈表。（ y）3. 數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(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ù)的特

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

11、動(dòng)某個(gè)結(jié)點(diǎn)的指針，使它由空變?yōu)榉强占纯伞＃▂ ）14. 有n（n1）個(gè)頂點(diǎn)的有向強(qiáng)連通圖最少有n條邊。（ n）15. 連通分量是無向圖中的極小連通子圖。 （ n）16.二叉樹中任何一個(gè)結(jié)點(diǎn)的度都是2。（n ）17.單鏈表從任何一個(gè)結(jié)點(diǎn)出發(fā)，都能訪問到所有結(jié)點(diǎn)。 四、程序閱讀填空 1. 在順序表中第 i 個(gè)位置插入新元素 x ！template int SeqList:Insert (Type & x, int i) if (ilast+1|last=MaxSize-1)return 0; /插入不成功 else last+; for(int j=last;ji;j-)dataj=dataj-1

12、; datai = x; return 1; /插入成功 2. 刪去鏈表中除表頭結(jié)點(diǎn)外的所有其他結(jié)點(diǎn)template void List : MakeEmpty ( ) ListNode *q; while (firstlink!=NULL)q=first link; first link=q link; /將表頭結(jié)點(diǎn)后第一個(gè)結(jié)點(diǎn)從鏈中摘下 delete q; /釋放它 last = first; /修改表尾指針3. 刪去鏈?zhǔn)疥?duì)頭結(jié)點(diǎn)（隊(duì)頭指針為QueueNode *front），并返回隊(duì)頭元素的值template Type Queue:DeQueue( ) assert (!IsEmpty

13、( ); /判隊(duì)空的斷言 QueueNode *p =_front_; Type retvalue = pdata; /保存隊(duì)頭的值 _front=front link_; /新隊(duì)頭 delete p; return retvalue;#4. 最小堆的向下調(diào)整算法（沒有）template void MinHeap:FilterDown(int start, int EndOfHeap) int i = start, j = 2*i+1; / j 是 i 的左子女 Type temp = heapi; while ( j = EndOfHeap ) if ( j heapj+1.key ) j+

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

15、 x ) mid = BinarySearch ( x, low, mid -1 ); return mid;6. 直接插入排序的算法（按關(guān)鍵碼 Key 非遞減順序?qū)?shù)據(jù)表list進(jìn)行排序）（無）template void InsertionSort(datalist & list) for(int i=1; ilist.CurrentSize; i+)_inter(list,i)_ _;template viod Insert(datalist & list, int i) Element temp = list.Vectori; int j = i; /從后向前順序比較 while(j0

16、& temp.getKey( )list.Vectorj-1.getKey( ) _list.vectorj=list.vectorj-1_ _; j-; list.Vectorj = temp; 7. 直接選擇排序的算法:（沒） template void SelectSort(datalist & list) for(int i=0; ilist.CurrentSize-1; i+) _SelectExchange(list,i)_ _;template viod SelectExchange(datalist & list, const int i)int k = i; for(int

17、j=i+1;j list.CurrentSize;j+)if(list.Vectorj.getKey()rLink, *q=DL-lLink; While(p!=q & p-rLink!=q & sym=1)if(p-data=q-data) _p=p rLink_;_q=q lLink_;else sym=0; return sym; 五、簡答題 1. 給定權(quán)值集合15, 03, 14, 02, 06, 09, 16, 17, 構(gòu)造相應(yīng)的霍夫曼樹, 并計(jì)算它的帶權(quán)外部路徑長度。 ！()05171609061415F：17160906021415020303()1716091415201614

18、15()17110911060502030605()332029020329161720()161711091514141109150506060502030203()05171609061415F：17160906021415020303()171609141520161415()17110911060502030605()332029020329161720()16171109151414110915050606050203020382()4933()4933172920161716292014110915110915140605060503020302此樹的帶權(quán)路徑長度WPL = 229

19、。2. 線性表可用順序表或是鏈表存儲(chǔ)，此兩種存儲(chǔ)表示各有哪些特點(diǎn)，優(yōu)缺點(diǎn)？！ P503. 設(shè)有一個(gè)輸入數(shù)據(jù)的序列是46,25,78, 62, 12, 37, 70, 29，試畫出從空樹起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉搜索樹。 按順序逐個(gè)輸入 46 / 25 78 / / 12 37 62 / 29 704. 對(duì)于如右圖所示的有向圖，試寫出：！(1) 從頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹； (2) 從頂點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹； P178#5.用廣義表的帶表頭結(jié)點(diǎn)的存儲(chǔ)表示法表示下列集合。 A = ( ) B = (6, 2)C = (a,( 5, 3, x)D

20、= (B, C, A) E = (B, D) 6.右圖所示為一有向圖，請給出該圖的下述要求： （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)，分別畫出該圖的一個(gè)深度優(yōu)先生成樹和一個(gè)寬度優(yōu)先生成樹； （3）給出該圖的鄰接矩陣； （4）給出該圖的鄰接表； （5）給出該圖的逆鄰接表； 7. 已知二叉樹的先序、中序和后序序列分別如下，但其中有一些已模糊不清，試構(gòu)造出該二叉樹。先序序列_BC_EF_中序序列BDE_AG_H 后序序列e_DCb_GHf_A 8. 已某個(gè)不帶權(quán)的無向圖采用鄰接矩陣存儲(chǔ)方法依次將頂點(diǎn)的數(shù)據(jù)信息存放于一維數(shù)組ABCDEFGH中，邊的信息存放于鄰接矩陣中，鄰接矩陣為 0 1 1 0 0 0 0 01 0 0 0 1 0 1 11