數(shù)據(jù)結(jié)構(gòu)與算法分析模擬試卷

1、PAGE 20PAGE 71四川大學(xué)數(shù)據(jù)結(jié)構(gòu)與算法分析課程考試模擬試卷 模擬試卷一單選題（每題 2 分，共20分）以下數(shù)據(jù)結(jié)構(gòu)中哪一個是線性結(jié)構(gòu)？( ) A. 有向圖 B. 隊列 C. 線索二叉樹 D. B樹在一個單鏈表HL中，若要在當(dāng)前由指針p指向的結(jié)點后面插入一個由q指向的結(jié)點，則執(zhí)行如下( )語句序列。 A. p=q; p-next=q; B. p-next=q; q-next=p; C. p-next=q-next; p=q; D. q-next=p-next; p-next=q;以下哪一個不是隊列的基本運算？（ ） A. 在隊列第i個元素之后插入一個元素 B. 從隊頭刪除一個元素 C

2、. 判斷一個隊列是否為空 D.讀取隊頭元素的值字符A、B、C依次進(jìn)入一個棧，按出棧的先后順序組成不同的字符串，至多可以組成( )個不同的字符串？ A.14 B.5 C.6 D.8由權(quán)值分別為3,8,6,2的葉子生成一棵哈夫曼樹，它的帶權(quán)路徑長度為( )。EAGCBDF圖1A 11 B.35 C. 19 D. 53以下6-8題基于圖1。該二叉樹結(jié)點的前序遍歷的序列為( )。E、G、F、A、C、D、B E、A、G、C、F、B、DE、A、C、B、D、G、F E、G、A、C、D、F、B該二叉樹結(jié)點的中序遍歷的序列為( )。A. A、B、C、D、E、G、FB. E、A、G、C、F、B、D C. E、A、

3、C、B、D、G、F B、D、C、A、F、G、E 該二叉樹的按層遍歷的序列為( )。 AE、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B下面關(guān)于圖的存儲的敘述中正確的是( )。 A用鄰接表法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點個數(shù)無關(guān) B用鄰接表法存儲圖，占用的存儲空間大小與圖中邊數(shù)和結(jié)點個數(shù)都有關(guān) C. 用鄰接矩陣法存儲圖，占用的存儲空間大小與圖中結(jié)點個數(shù)和邊數(shù)都有關(guān) D用鄰接矩陣法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點個數(shù)無關(guān)設(shè)有關(guān)鍵碼序列(q，g，m，z，a，n，p，x，h)，下面

4、哪一個序列是從上述序列出發(fā)建堆的結(jié)果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z填空題（每空1分，共26分）數(shù)據(jù)的物理結(jié)構(gòu)被分為_、_、_和_四種。對于一個長度為n的順序存儲的線性表，在表頭插入元素的時間復(fù)雜度為_，在表尾插入元素的時間復(fù)雜度為_。向一個由HS指向的鏈棧中插入一個結(jié)點時p時，需要執(zhí)行的操作是_;刪除一個結(jié)點時，需要執(zhí)行的操作是_（假設(shè)棧不空而且無需回收被刪除結(jié)點）。對于一棵具有n個結(jié)點的二叉樹，一個結(jié)點的編號為i(1in)，若它有左孩子則左孩子結(jié)點

5、的編號為_，若它有右孩子，則右孩子結(jié)點的編號為_，若它有雙親，則雙親結(jié)點的編號為_。當(dāng)向一個大根堆插入一個具有最大值的元素時，需要逐層_調(diào)整，直到被調(diào)整到_位置為止。以二分查找方法從長度為10的有序表中查找一個元素時，平均查找長度為_。表示圖的三種常用的存儲結(jié)構(gòu)為_、_和_。對于線性表（70，34，55，23，65，41，20）進(jìn)行散列存儲時，若選用H（K）=K %7作為散列函數(shù)，則散列地址為0的元素有_個，散列地址為6的有_個。在歸并排序中，進(jìn)行每趟歸并的時間復(fù)雜度為_，整個排序過程的時間復(fù)雜度為_，空間復(fù)雜度為_。在一棵m階B_樹上，每個非樹根結(jié)點的關(guān)鍵字?jǐn)?shù)目最少為_個，最多為_個，其子樹

6、數(shù)目最少為_，最多為_。運算題（每題 6 分，共24分）圖2寫出下列中綴表達(dá)式的后綴形式：3X/(Y-2)+12+X*(Y+3)試對圖2中的二叉樹畫出其：順序存儲表示的示意圖；二叉鏈表存儲表示的示意圖。判斷以下序列是否是小根堆? 如果不是, 將它調(diào)整為小根堆。（1） 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 （2） 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 已知一個圖的頂點集V和邊集E分別為： V=1,2,3,4,5,6,7; E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(

7、3,4)15,(3,5)12,(3,6)9,(4,6)4, (4,7)20,(5,6)18,(6,7)25; 按照普里姆算法從頂點1出發(fā)得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。閱讀算法（每題7分，共14分）void AE(Stack& S) InitStack(S); Push(S,3); Push(S,4); int x=Pop(S)+2*Pop(S); Push(S,x); int i,a5=1,5,8,12,15; for(i=0;i5;i+) Push(S,2*ai); while(!StackEmpty(S) coutPop(S)left,c1,c2); c1+; if

8、 (BT-left=NULL&BT-right=NULL) c2+; ABC(BT-right,c1,c2); /if 該函數(shù)執(zhí)行的功能是什么？算法填空（共8分）向單鏈表的末尾添加一個元素的算法。Void InsertRear(LNode*& HL,const ElemType& item)LNode* newptr;newptr=new LNode;If (_)cerrMemory allocation failare!next=NULL;if (HL=NULL) HL=_;elseLNode* P=HL;While (P-next!=NULL) _;p-next=newptr; 編寫算法（

9、共8分）編寫從類型為List的線性表L中將第i個元素刪除的算法，（假定不需要對i的值進(jìn)行有效性檢查,也不用判別L是否為空表。） void Delete(List& L, int i)模擬試卷一參考答案 單選題（每題2分，共20分）1.B 2.D 3.A 4.B 5.B 6.C 7.A 8.C 9.B 10.B 填空題（每空1分，共26分）順序 鏈表 索引 散列O(n) O(1)p-next=HS;HS=p HS=HS-next2i 2i+1 i/2（或i/2）圖3向上 根2.9鄰接矩陣 鄰接表 邊集數(shù)組1 4O(n) O(nlog2n) O(n)m/2-1 m-1 m/2 m 運算題（每題6分

10、，共24分） (1) 3 X * Y 2 - / 1 + 2 X Y 3 + * + （1）012345678910111213141516123456789 （2）見圖3所示： (1)不是小根堆。調(diào)整為：12,65,33,70,24,56,48,92,86,33 (2)是小根堆。 普里姆算法從頂點1出發(fā)得到最小生成樹為：(1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)20閱讀算法（每題7分，共14分）30 24 16 10 2 10該函數(shù)的功能是：統(tǒng)計出BT所指向的二叉樹的結(jié)點總數(shù)和葉子總數(shù) 算法填空（共8分，每一空2分）newptr=NULL n

11、ewptr-=data newptr p=p-next編寫算法（8分） void Delete(List& L, int i) for(int j=i-1;jnext=HL; B. p-next=HL-next; HL-next=p; C. p-next=HL; p=HL; D. p-next=HL; HL=p; 若順序存儲的循環(huán)隊列的QueueMaxSize=n,則該隊列最多可存儲（ ）個元素. A. n B.n-1 C. n+1 D.不確定下述哪一條是順序存儲方式的優(yōu)點？（ ） A存儲密度大 B.插入和刪除運算方便 C. 獲取符合某種條件的元素方便 D.查找運算速度快設(shè)有一個二維數(shù)組Amn

12、，假設(shè)A00存放位置在600(10)，A33存放位置在678(10)，每個元素占一個空間，問A23(10)存放在什么位置？(腳注(10)表示用10進(jìn)制表示,m3) A658 B648 C633 D653下列關(guān)于二叉樹遍歷的敘述中，正確的是( ) 。A. 若一個樹葉是某二叉樹的中序遍歷的最后一個結(jié)點，則它必是該二叉樹的前序遍歷最后一個結(jié)點B若一個點是某二叉樹的前序遍歷最后一個結(jié)點，則它必是該二叉樹的中序遍歷的最后一個結(jié)點 C若一個結(jié)點是某二叉樹的中序遍歷的最后一個結(jié)點，則它必是該二叉樹的前序最后一個結(jié)點 D若一個樹葉是某二叉樹的前序最后一個結(jié)點，則它必是該二叉樹的中序遍歷最后一個結(jié)點k層二叉樹的

13、結(jié)點總數(shù)最多為( ). A2k-1 B.2K+1 C.2K-1 D. 2k-1對線性表進(jìn)行二分法查找，其前提條件是( ).線性表以鏈接方式存儲，并且按關(guān)鍵碼值排好序 線性表以順序方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序線性表以順序方式存儲，并且按關(guān)鍵碼值排好序線性表以鏈接方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序?qū)個記錄進(jìn)行堆排序，所需要的輔助存儲空間為 A. O（1og2n） B. O（n） C. O（1） D. O（n2）對于線性表（7，34，77，25，64，49，20，14）進(jìn)行散列存儲時，若選用H（K）=K %7作為散列函數(shù)，則散列地址為0的元素有（ ）個， A1 B2 C3 D4下

14、列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是( ).數(shù)組是不同類型值的集合 遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉樹是一種線性結(jié)構(gòu)用一維數(shù)組存儲一棵完全二叉樹是有效的存儲方法填空題（每空1分，共26分）數(shù)據(jù)的邏輯結(jié)構(gòu)被分為_、_、_和_四種。一個算法的時間復(fù)雜度為(3n3+2000nlog2n+90)/n2，其數(shù)量級表示為_。對于一個長度為n的單鏈存儲的隊列，在表頭插入元素的時間復(fù)雜度為_，在表尾插入元素的時間復(fù)雜度為_。假定一棵樹的廣義表表示為A（D（E，G），H（I，J），則樹中所含的結(jié)點數(shù)為_個，樹的深度為_，樹的度為_。后綴算式79 2 30 + - 4 2 / *的值為_。中綴算式（3+

15、X*Y）-2Y/3對應(yīng)的后綴算式為_。在一棵高度為5的理想平衡樹中，最少含有_個結(jié)點，最多含有_個結(jié)點。在樹中，一個結(jié)點的直接后繼結(jié)點稱為該結(jié)點的_。一個結(jié)點的直接前趨結(jié)點稱為該結(jié)點的_。在一個具有10個頂點的無向完全圖中，包含有_條邊，在一個具有n個頂點的有向完全圖中，包含有_條邊。假定一個線性表為(12,17,74,5,63,49,82,36)，若按Key % 4條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個子表，則得到的四個子表分別為_、_、_和_。對一棵B_樹進(jìn)行刪除元素的過程中，若最終引起樹根結(jié)點的合并時，會使新樹的高度比原樹的高度_。在堆排序的過程中，對任一分支結(jié)點進(jìn)行篩運算的時間復(fù)雜度

16、為_，整個堆排序過程的時間復(fù)雜度為_。在線性表的散列存儲中，裝填因子又稱為裝填系數(shù)，若用m表示散列表的長度，n表示待散列存儲的元素的個數(shù)，則等于_。運算題（每題 6 分，共24分）在如下數(shù)組A中鏈接存儲了一個線性表，表頭指針存放在A 0.next，試寫出該線性表。 A 0 1 2 3 4 5 6 7 data605078903440next4052713已知一棵二叉樹的前序遍歷的結(jié)果是ABKCDFGHIJ, 中序遍歷的結(jié)果是KBCDAFHIGJ, 試畫出這棵二叉樹。已知一個圖的頂點集V為： V=1,2,3,4,5,6,7; 其共有10條邊。該圖用如下邊集數(shù)組存儲：起點1225522613終點6

17、454767775權(quán)1122233457試用克魯斯卡爾算法依次求出該圖的最小生成樹中所得到的各條邊及權(quán)值。畫出向小根堆中加入數(shù)據(jù)4, 2, 5, 8, 3, 6, 10, 1時，每加入一個數(shù)據(jù)后堆的變化。閱讀算法（每題7分，共14分）在下面的每個程序段中，假定線性表La的類型為List，元素類型ElemType為int，并假定每個程序段是連續(xù)執(zhí)行的。試寫出每個程序段執(zhí)行后所得到的線性表La。InitList(La); Int a=100,26,57,34,79; For (i=0;i5;i+) Insert(La,ai); TraverseList(La);DeleteFront(La);In

18、sertRear(La, DeleteFront(La); TraverseList(La);ClearList(La); For (i=0;i5;i+) InsertFront(La,ai); TraverseList(La);現(xiàn)面算法的功能是什么？void ABC(BTNode * BT) if BT coutdataleft); ABC(BT-right); 算法填空（共8分）二分查找的遞歸算法。 Int Binsch(ElemType A,int low,int high,KeyType K) if _ int mid=(low+high)/2; if (_) return mid;

19、/查找成功，返回元素的下標(biāo) else if (KAmid.key) return Binsch(A,low,mid-1,K); /在左子表上繼續(xù)查找 else return_； /在右子表上繼續(xù)查找 else _； /查找失敗，返回-1 編寫算法（共8分）HL為單鏈表的表頭指針，試寫出在該單鏈表中查找具有給定的元素item的算法。bool Find(LNode* HL, ElemType &item)模擬試卷二參考答案 單選題（每題2分，共20分）1.B 2.B 3.A 4.C 5.D 6.A 7.C 8.C 9.D 10.D 填空題（每空1分，共26分）集合結(jié)構(gòu) 線性結(jié)構(gòu) 樹結(jié)構(gòu) 圖結(jié)構(gòu)O(

20、n)O(1) O(1)7 2 294 3 X Y * + 2 Y * 3 / -16 31孩子（或子）結(jié)點 雙親（或父）結(jié)點45 n(n-1)（12，36） （17,5,49） （74，82） （63）減少1（或減少）O(log2n) O(nlog2n)n/m運算題（每題6分，共24分）線性表為：（90，40，78，50，34，60）當(dāng)前序序列為ABKCDFGHIJ，中序序列為KBCDAFHIGJ時，逐步形成二叉樹的過程如下圖4所示： AAAAFBBFFBGKCGKCHIGJCDKFHIGJHDJHIJDIKBCD圖4用克魯斯卡爾算法得到的最小生成樹為： (1,6)1, (2,4)1, (2,

21、5)2, (5,7)2, (2,6)3, (3,5)7見圖5。222444555244423881222253553351064310486484868圖5閱讀算法（每題7分，共14分）(1) La=(26,34,57,79,100) (2)La=(57,79,100,34) (3)La=(79,34,57,26,100) 前序遍歷鏈?zhǔn)酱鎯Φ亩鏄?。算法填空（每?分，共8 分）(lowdata=item) return true; else p=p-next; return false;模擬試卷三單選題（每題 2 分，共20分）對一個算法的評價，不包括如下（ ）方面的內(nèi)容。 A健壯性和可讀性

22、 B并行性 C正確性 D時空復(fù)雜度在帶有頭結(jié)點的單鏈表HL中，要向表頭插入一個由指針p指向的結(jié)點，則執(zhí)行( )。 A. p-next=HL-next; HL-next=p; B. p-next=HL; HL=p; C. p-next=HL; p=HL; D. HL=p; p-next=HL;對線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？( ) A.經(jīng)常需要隨機地存取元素 B.經(jīng)常需要進(jìn)行插入和刪除操作 C.表中元素需要占據(jù)一片連續(xù)的存儲空間 D.表中元素的個數(shù)不變一個棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是( ) A. 2 3 1B. 3 2 1 C. 3 1 2 D. 1

23、 2 3AOV網(wǎng)是一種（ ）。 A有向圖 B無向圖 C無向無環(huán)圖 D有向無環(huán)圖采用開放定址法處理散列表的沖突時，其平均查找長度（ ）。A低于鏈接法處理沖突 B. 高于鏈接法處理沖突 C與鏈接法處理沖突相同 D高于二分查找若需要利用形參直接訪問實參時，應(yīng)將形參變量說明為（ ）參數(shù)。A值 B函數(shù) C指針 D引用在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結(jié)點都具有相同的（ ）。A行號 B列號 C元素值 D非零元素個數(shù)快速排序在最壞情況下的時間復(fù)雜度為（ ）。AO(log2n) BO(nlog2n) C0(n) D0(n2)從二叉搜索樹中查找一個元素時，其時間復(fù)雜度大致為( )。 A. O(

24、n) B. O(1) C. O(log2n) D. O(n2)運算題（每題 6 分，共24分）數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的_。當(dāng)結(jié)點之間存在M對N（M：N）的聯(lián)系時，稱這種結(jié)構(gòu)為_。隊列的插入操作是在隊列的_進(jìn)行，刪除操作是在隊列的_進(jìn)行。當(dāng)用長度為N的數(shù)組順序存儲一個棧時，假定用top=N表示棧空，則表示棧滿的條件是_。對于一個長度為n的單鏈存儲的線性表，在表頭插入元素的時間復(fù)雜度為_，在表尾插入元素的時間復(fù)雜度為_。設(shè)W為一個二維數(shù)組，其每個數(shù)據(jù)元素占用4個字節(jié)，行下標(biāo)i從0到7 ，列下標(biāo)j從0到3 ，則二維數(shù)組W的數(shù)據(jù)元素共占用_個字節(jié)。W中第6 行的元素和第4 列的元素共占用_個字節(jié)

25、。若按行順序存放二維數(shù)組W，其起始地址為100，則二維數(shù)組元素W6，3的起始地址為_。廣義表A= (a,(a,b),(a,b),c),則它的深度為_，它的長度為_。二叉樹是指度為2的_樹。一棵結(jié)點數(shù)為N的二叉樹，其所有結(jié)點的度的總和是_。對一棵二叉搜索樹進(jìn)行中序遍歷時，得到的結(jié)點序列是一個_。對一棵由算術(shù)表達(dá)式組成的二叉語法樹進(jìn)行后序遍歷得到的結(jié)點序列是該算術(shù)表達(dá)式的_。對于一棵具有n個結(jié)點的二叉樹，用二叉鏈表存儲時，其指針總數(shù)為_個，其中_個用于指向孩子，_個指針是空閑的。若對一棵完全二叉樹從0開始進(jìn)行結(jié)點的編號，并按此編號把它順序存儲到一維數(shù)組A中，即編號為0的結(jié)點存儲到A0中。其余類推，

26、則A i 元素的左孩子元素為_,右孩子元素為_，雙親元素為_。在線性表的散列存儲中，處理沖突的常用方法有_和_兩種。當(dāng)待排序的記錄數(shù)較大，排序碼較隨機且對穩(wěn)定性不作要求時，宜采用_排序；當(dāng)待排序的記錄數(shù)較大，存儲空間允許且要求排序是穩(wěn)定時，宜采用_排序。運算題（每題6分，共24分）已知一個65稀疏矩陣如右所示，試：寫出它的三元組線性表；給出三元組線性表的順序存儲表示。設(shè)有一個輸入數(shù)據(jù)的序列是 46, 25, 78, 62, 12, 80 , 試畫出從空樹起，逐個輸入各個數(shù)據(jù)而生成的二叉搜索樹。對于圖6所示的有向圖若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結(jié)點都是按照終點序號從小到大的次序鏈接

27、的，試寫出：(1) 從頂點出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；(2) 從頂點出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹； 已知一個圖的頂點集V和邊集E分別為： 圖6 V=1,2,3,4,5,6,7;E=,;若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結(jié)點都是按照終點序號從小到大的次序鏈接的，按主教材中介紹的拓樸排序算法進(jìn)行排序，試給出得到的拓樸排序的序列。閱讀算法（每題7分，共14分）int Prime(int n) int i=1; int x=(int) sqrt(n); while (+ix) return 1; else return 0; 指出該算法的功能；該算法的時間復(fù)雜度

28、是多少？寫出下述算法的功能： void AJ(adjlist GL, int i, int n) Queue Q; InitQueue(Q); coutiadjvex; if(!visitedj) coutjnext; 算法填空（共8分）如下為二分查找的非遞歸算法，試將其填寫完整。Int Binsch(ElemType A ,int n,KeyType K)int low=0;int high=n-1;while (low=high)int mid=_；if (K=Amid.key) return mid; /查找成功，返回元素的下標(biāo) else if (Kmid.key) _; /在左子表上繼

29、續(xù)查找 else _; /在右子表上繼續(xù)查找return -1; /查找失敗，返回-1編寫算法（共8分）HL是單鏈表的頭指針，試寫出刪除頭結(jié)點的算法。ElemType DeleFront(LNode * & HL)模擬試卷三參考答案單選題（每題2分，共20分）1.B 2.A 3.B 4.C 5.D 6.B 7.D 8.A 9.D 10.C填空題（每空1分，共26分）聯(lián)系 圖（或圖結(jié)構(gòu)）尾 首top=0O（1） O（n）128 44 1083 3 65515132-145-2515637 圖7有序 n-1有序序列 后綴表達(dá)式（或逆波蘭式）2n n-1 n+12i+1 2i+2 (i-1)/2開放

30、定址法 鏈接法快速 歸并運算題（每題6分，共24分）（1） (1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7) (3分)（2） 三元組線性表的順序存儲表示如圖7示。圖8如圖8所示。DFS： BFS： 拓樸排序為： 4 3 6 5 7 2 1 閱讀算法（每題7分，共14分）(1) 判斷n是否是素數(shù)（或質(zhì)數(shù)） （2）O（）功能為：從初始點vi出發(fā)廣度優(yōu)先搜索由鄰接表GL所表示的圖。算法填空（8 分） (low+high)/2 high=mid-1 low=mid+1 編寫算法（8分）ElemType DeleFront(LNode * & HL)if (HL=NUL

31、L) cerr空表next;ElemType temp=p-data;delete p;return temp; 模擬試卷四單選題（每題 2 分，共20分）以下數(shù)據(jù)結(jié)構(gòu)中哪一個是線性結(jié)構(gòu)？( ) A. 有向圖 B. 棧 C. 二叉樹 D. B樹若某鏈表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除最后一個結(jié)點，則采用( )存儲方式最節(jié)省時間。 A.單鏈表 B.雙鏈表 C.帶頭結(jié)點的雙循環(huán)鏈表D.單循環(huán)鏈表以下哪一個不是隊列的基本運算？（ ） A. 在隊列第i個元素之后插入一個元素 B. 從隊頭刪除一個元素 C. 判斷一個隊列是否為空 D.讀取隊頭元素的值字符A、B、C、D依次進(jìn)入一個棧，按

32、出棧的先后順序組成不同的字符串，至多可以組成( )個不同的字符串？ A.15 B.14 C.16 D.21由權(quán)值分別為4,7,6,2的葉子生成一棵哈夫曼樹，它的帶權(quán)路徑長度為( )。A 11 B.37 C. 19 D. 53以下6-8題基于下面的敘述：若某二叉樹結(jié)點的中序遍歷的序列為A、B、C、D、E、F、G，后序遍歷的序列為B、D、C、A、F、G、E。則該二叉樹結(jié)點的前序遍歷的序列為( ). A. E、G、F、A、C、D、B B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. E、G、A、C、D、F、B該二叉樹有（ ）個葉子。 A3 B.2 C.5 D.4該二叉樹的按層

33、遍歷的序列為( ) AE、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B下面的二叉樹中，( )不是完全二叉樹。設(shè)有關(guān)鍵碼序列(q，g，m，z，a)，下面哪一個序列是從上述序列出發(fā)建的小根堆的結(jié)果?( ) A. a，g ，m，q， z B. a，g ，m，z,q C. g ，m，q，a，z D. g， m， a，q，z填空題（每空1分，共26分）數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的_。當(dāng)結(jié)點之間存在1對N（1：N）的聯(lián)系時，稱這種結(jié)構(gòu)為_。一個廣義表中的元素分為_元素和_元素兩類。對于一個長度為n的順序存儲的線性表，在表頭插

34、入元素的時間復(fù)雜度為_，在表尾插入元素的時間復(fù)雜度為_。向一個由HS指向的鏈棧中插入一個結(jié)點時p時，需要執(zhí)行的操作是_;刪除一個結(jié)點時，需要執(zhí)行的操作是_（假設(shè)棧不空而且無需回收被刪除結(jié)點）。棧又稱為_表，隊列又稱為_表。在稀疏矩陣所對應(yīng)的三元組線性表中，每個三元組元素按_為主序、_為輔序的次序排列。若一棵二叉樹中只有葉子結(jié)點和左、右子樹皆非空的結(jié)點，設(shè)葉結(jié)點的個數(shù)為K，則左、右子樹皆非空的結(jié)點個數(shù)是_。以折半（或二分）查找方法從長度為8的有序表中查找一個元素時，平均查找長度為_。表示圖的三種常用的存儲結(jié)構(gòu)為_、_和_。對于線性表（78，4，56，30，65）進(jìn)行散列存儲時，若選用H（K）=K

35、 %5作為散列函數(shù)，則散列地址為0的元素有_個，散列地址為4的有_個。在歸并排序中，進(jìn)行每趟歸并的時間復(fù)雜度為_，整個排序過程的時間復(fù)雜度為_，空間復(fù)雜度為_。在n個帶權(quán)葉子結(jié)點構(gòu)造出的所有二叉樹中，帶權(quán)路徑長度最小的二叉樹稱為_。WPL稱為_。在索引表中，若一個索引項對應(yīng)主表的一個記錄，則此索引為_索引 ，若對應(yīng)主表的若干條記錄，則稱此索引為_索引。運算題（每題 6 分，共24分）寫出下列中綴表達(dá)式的后綴形式：3X/(Y-2H)+12+X*(Y+3)假定一棵二叉樹廣義表表示為a(b(c),d(e,f)，分別寫出對它進(jìn)行先序、中序、后序、按層遍歷的結(jié)果。 先序： 中序： 后序： 按層： ab

36、cde已知一個無向圖的頂點集為a, b, c, d, e ,其鄰接矩陣如下所示 (1) 畫出該圖的圖形； （2）根據(jù)鄰接矩陣從頂點a出發(fā)進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應(yīng)的遍歷序列。已知一個圖的頂點集V和邊集E分別為： V=0,1,2,3,4,5,6,7; E=(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10, (4,6)4,(5,7)20;按照普里姆算法從頂點0出發(fā)得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。閱讀算法（每題7分，共14分）void AE(Stack& S) InitStack(S); Push

37、(S,3); Push(S,4); int x=Pop(S)+2*Pop(S); Push(S,x); int i,a5=2,5,8,22,15; for(i=0;i5;i+) Push(S,ai); while(!StackEmpty(S) coutPop(S)data;/查找成功 return true; else if(itemdata) BST=BST-_; else BST=BST-_;/while return _;/查找失敗編寫算法（共8分）用遞歸的算法編寫出對存入在an+1數(shù)組中的n個有序元素進(jìn)行二分（又稱折半）查找（假定a0單元不用）的程序。int halfsearch(SS

38、Table *a, KeyType k,int low,int high)模擬試卷四參考答案 單選題（每題2分，共20分）1.B 2.C 3.A 4.B 5.B 6.C 7.A 8.C 9.C 10.B 填空題（每空1分，共26分）聯(lián)系 樹（或樹結(jié)構(gòu)）單 （子）表O(n) O(1)p-next=HS;HS=p HS=HS-next先進(jìn)后出 先進(jìn)先出行 列k-12.625鄰接矩陣 鄰接表 邊集數(shù)組2 1O(n) O(nlog2n) O(n)哈夫曼樹 帶權(quán)路徑長度稠密 稀疏 運算題（每題6分，共24分） (1) 3 X * Y 2 H *- / 1 + （2） 2 X Y 3 + * + 先序：

39、a,b,c,d,e,f 中序： c,b,a,e,d,f 后序： c,b,e,f,d,a 圖9 按層： a,b,d,c,e,f （1）該圖的圖形如圖9示： （2）深度優(yōu)先遍歷序列為：abdce 廣度優(yōu)先遍歷序列為：abedc普里姆：(0,3)2, (0,2)5, (0,1)8, (1,5)6, (3,6)10, (6,4)4, (5,7)20閱讀算法（每題7分，共14分）15 22 8 5 2 10該函數(shù)的功能是： 求：算法填空（共8分，每一空2分） BST-data left right false編寫算法（8分） 遞歸算法 ： int halfsearch(SSTable *a, KeyTy

40、pe k,int low,int high) if (lowhigh) return 0; else int mid=(low+high)/2 if EQ(k,amid.key) return mid; else if LT(k,amid.key) return halfsearch(a,k,low,mid-1); else return halfsearch(a,k,mid+1,high); 模擬試卷五單選題（每題 2 分，共20分）棧和隊列的共同特點是( )。A.只允許在端點處插入和刪除元素B.都是先進(jìn)后出 C.都是先進(jìn)先出D.沒有共同點 用鏈接方式存儲的隊列，在進(jìn)行插入運算時( ). A

41、. 僅修改頭指針 B. 頭、尾指針都要修改 C. 僅修改尾指針 D.頭、尾指針可能都要修改以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？( ) A. 隊列 B. 棧 C. 線性表 D. 二叉樹設(shè)有一個二維數(shù)組Amn，假設(shè)A00存放位置在644(10)，A22存放位置在676(10)，每個元素占一個空間，問A33(10)存放在什么位置？腳注(10)表示用10進(jìn)制表示。 A688 B678 C692 D696樹最適合用來表示( )。 A.有序數(shù)據(jù)元素 B.無序數(shù)據(jù)元素 C.元素之間具有分支層次關(guān)系的數(shù)據(jù) D.元素之間無聯(lián)系的數(shù)據(jù)二叉樹的第k層的結(jié)點數(shù)最多為( ). A2k-1 B.2K+1 C.2K-1 D.

42、 2k-1若有18個元素的有序表存放在一維數(shù)組A19中，第一個元素放A1中，現(xiàn)進(jìn)行二分查找，則查找A3的比較序列的下標(biāo)依次為( ) A. 1，2，3B. 9，5，2，3 C. 9，5，3D. 9，4，2，3對n個記錄的文件進(jìn)行快速排序，所需要的輔助存儲空間大致為 A. O（1） B. O（n） C. O（1og2n） D. O（n2）對于線性表（7，34，55，25，64，46，20，10）進(jìn)行散列存儲時，若選用H（K）=K %9作為散列函數(shù)，則散列地址為1的元素有（ ）個， A1 B2 C3 D4設(shè)有6個結(jié)點的無向圖，該圖至少應(yīng)有( )條邊才能確保是一個連通圖。 A.5 B.6 C.7 D.

43、8填空題（每空1分，共26分）通常從四個方面評價算法的質(zhì)量：_、_、_和_。一個算法的時間復(fù)雜度為(n3+n2log2n+14n)/n2，其數(shù)量級表示為_。假定一棵樹的廣義表表示為A（C，D（E，F(xiàn)，G），H（I，J），則樹中所含的結(jié)點數(shù)為_個，樹的深度為_，樹的度為_。后綴算式9 2 3 +- 10 2 / -的值為_。中綴算式（3+4X）-2Y/3對應(yīng)的后綴算式為_。若用鏈表存儲一棵二叉樹時，每個結(jié)點除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個指針。在這種存儲結(jié)構(gòu)中，n個結(jié)點的二叉樹共有_個指針域，其中有_個指針域是存放了地址，有_個指針是空指針。對于一個具有n個頂點和e條邊的有向圖和無向圖，

44、在其對應(yīng)的鄰接表中，所含邊結(jié)點分別有_個和_個。AOV網(wǎng)是一種_的圖。在一個具有n個頂點的無向完全圖中，包含有_條邊，在一個具有n個頂點的有向完全圖中，包含有_條邊。假定一個線性表為(12,23,74,55,63,40)，若按Key % 4條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個子表，則得到的四個子表分別為_、_、_和_。向一棵B_樹插入元素的過程中，若最終引起樹根結(jié)點的分裂，則新樹比原樹的高度_。在堆排序的過程中，對任一分支結(jié)點進(jìn)行篩運算的時間復(fù)雜度為_，整個堆排序過程的時間復(fù)雜度為_。在快速排序、堆排序、歸并排序中，_排序是穩(wěn)定的。運算題（每題 6 分，共24分）在如下數(shù)組A中鏈接存儲了一

45、個線性表，表頭指針為A 0.next，試寫出該線性表。 A 0 1 2 3 4 5 6 7 data605078903440next3572041圖10請畫出圖10的鄰接矩陣和鄰接表。已知一個圖的頂點集V和邊集E分別為： V=1,2,3,4,5,6,7; E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25; 用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。畫出向小根堆中加入數(shù)據(jù)4, 2, 5, 8, 3時，每加入一個數(shù)據(jù)后堆的變化。閱讀算法（

46、每題7分，共14分）LinkList mynote(LinkList L) /L是不帶頭結(jié)點的單鏈表的頭指針 if(L&L-next) q=L；L=Lnext；p=L； S1： while(pnext) p=pnext； S2： pnext=q；qnext=NULL； return L； 請回答下列問題： （1）說明語句S1的功能； （2）說明語句組S2的功能； （3）設(shè)鏈表表示的線性表為（a1,a2, ,an）,寫出算法執(zhí)行后的返回值所表示的線性表。void ABC(BTNode * BT) if BT ABC (BT-left); ABC (BT-right); coutdatadata)

47、 item=BST-data;/查找成功 return _; else if(itemdata) return Find(_,item); else return Find(_,item); /if編寫算法（共8分）統(tǒng)計出單鏈表HL中結(jié)點的值等于給定值X的結(jié)點數(shù)。 int CountX(LNode* HL,ElemType x)模擬試卷五參考答案 單選題（每題2分，共20分）1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A 填空題（每空1分，共26分）正確性 易讀性 強壯性 高效率O(n)9 3 3-1 3 4 X * + 2 Y * 3 / -2n n-1 n

48、+1e 2e有向無回路n(n-1)/2 n(n-1)（12，40） （ ） （74） （23,55，63）增加1O(log2n) O(nlog2n)歸并運算題（每題6分，共24分）線性表為：（78，50，40，60，34，90）鄰接矩陣： 鄰接表如圖11所示：圖11用克魯斯卡爾算法得到的最小生成樹為： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20見圖122224445552444238823584圖12閱讀算法（每題7分，共14分）（1）查詢鏈表的尾結(jié)點（2）將第一個結(jié)點鏈接到鏈表的尾部，作為新的尾結(jié)點 （3）返回的線性表為（a2,a3,an

49、,a1） 遞歸地后序遍歷鏈?zhǔn)酱鎯Φ亩鏄?。算法填空（每?分，共8 分）true BST-left BST-right 編寫算法（8分）int CountX(LNode* HL,ElemType x) int i=0; LNode* p=HL;/i為計數(shù)器 while(p!=NULL) if (P-data=x) i+; p=p-next; /while, 出循環(huán)時i中的值即為x結(jié)點個數(shù) return i; /CountX模擬試卷六一、單項選擇題（在每小題的四個備選答案中，選出一個正確的答案，并將其號碼填在題干后的括號內(nèi)。每小題1分，共10分）1下面程序段for(i=1;i=n;i+) for

50、(j=1;j=0）。（）6n階下三角矩陣的非零元素的個數(shù)最多為。（）7二叉樹只能采用二叉鏈表來存儲。（）8圖G的某一最小生成樹的代價一定小于其它生成樹的代價。（）9B+樹是一種特殊的二叉樹。（）10所有的簡單排序（即時間復(fù)雜度為O(n2)的排序）都是穩(wěn)定排序。（）四、簡答題（每小題4分，共20分）1對于下列雙向鏈表，設(shè)結(jié)構(gòu)為(prior,data,next)，結(jié)點類型為lnode，試寫出在p所指結(jié)點之前插入元素x的語句序列。2對于下圖，用Prim算法從結(jié)點1出發(fā)構(gòu)造出一棵最小生成樹，要求圖示出每一步的變化情況。3已知一棵二叉樹的先序序列與中序序列分別如下，試畫出此二叉樹。先序序列：ABCDEF

51、GHIJ中序序列：CBEDAGHFJI4給定一組權(quán)值3，4，7，14，15，20，試畫出相應(yīng)的哈夫曼樹，并計算帶樹路徑長度WPL的值。5有關(guān)鍵字序列7,23,6,9,17,19,21,22,5，Hash函數(shù)為H(key)=key % 5，采用鏈地址法處理沖突，試構(gòu)造哈希表。五、算法題（共25分）1程序填空題(每空2分，共8分)下面程序的功能是二叉樹的中序遍歷的非遞歸算法，其中二叉樹的結(jié)點結(jié)構(gòu)為(lchild,data,rchild)，棧的常用方法有：入棧Push，出棧Pop，判空StackEmpty；試將程序補充完整。templateBiTreeNode *BiTree:GoFarLeft(B

52、iTreeNode *T, Stack BiTreeNode *& S) if (!T ) return NULL; while (T-lchild ) Push(S, T); T = ; return T;templatevoid BiTree:Inorder(BiTreeNode *T, void (*visit)(Type & e) Stack BiTreeNode *& S; t = GoFarLeft(T, S); / 找到最左下的結(jié)點 while(t) visit(t-data); if (t-rchild) t = GoFarLeft( , S); else if ( !Stac

53、kEmpty(S ) t = ; else t = ; / ?？毡砻鞅闅v結(jié)束 / while/ Inorder 2程序填空題(每空2分，共8分)下面程序的功能是用線性探測再散列處理沖突（即Hi=(H(key)+i)%m），哈希函數(shù)為H(key)=key % m，進(jìn)行哈希表的插入算法。（如表中已存在關(guān)鍵字相同的記錄或無插入位置，則不進(jìn)行插入），試將程序補充完整。typedef enumSUCCESS,UNSUCCESS,OVERFLOWStatus;templatetypedef struct Type *elem; int m;HashTable;templateStatus SerchHas

54、hTable(HashTable H,Type e) int i=0,k= ; / i為沖突的次數(shù),k為哈希函數(shù)的值 while(ielem.key!=e.key) ; p=(p+i)%m; /while if(i=m)return OVERFLOW; else if(p-elem.key!=e.key)return ; else H.elemp.elem= ; return SUCCESS; /if /SerchHashTable3（9分）閱讀下面算法，試回答：根據(jù)鄰接表畫出對應(yīng)的圖； （2）當(dāng)圖的鄰接表如下時，執(zhí)行算法T(g,1)時，輸出的結(jié)果是什么？（3）函數(shù)T的功能是什么？圖的鄰接表為

55、：templatevoid AdjGraph:T(AdjGraph g;int i) ArcNode *p; coutadjvex) T(p-adjvex); p=p-next; /while/T六、寫算法（共20分）1(12分)以單鏈表為存儲結(jié)構(gòu)實現(xiàn)簡單選擇排序，排序的結(jié)果是單鏈表按關(guān)鍵字值升序排序，試編寫此算法。算法申明如下：templatevoid LinkList: SimpleSelectSort (Lnode *la)2(8分)下面是一個二叉樹的中序遍歷的遞歸算法，試改寫此算法，消去第二個遞歸調(diào)用MidOrder(T-rchild,visit)。templatevoid BiTre

56、e:PreOrder(BiTreeNode *T, void (*Visit)(Type& e) if(T) MidOrder(T-lchild, Visit); Visit(T-data); MidOrder(T-rchild, Visit); /if/MidOrder 模擬試卷六參考答案_一、單項選擇題（在每小題的四個備選答案中，選出一個正確的答案，并將其號碼填在題干后的括號內(nèi)。每小題1分，共10分）1B）2D）3B）4A）5D）6A）7B）8B）9D）10C）二、填空題（每空1分，共15分）1參考答案：sizeof(LNode)2參考答案：O(n2)3參考答案：4參考答案：(i-1)*n

57、+j-15參考答案：O(1)6參考答案：隊尾隊頭7參考答案：258參考答案：n-1n0= n2-19參考答案：210參考答案：n(n-1)/2n(n-1)11參考答案：選擇（直接選擇排序或堆排序）12參考答案：操作三、判斷改錯題（判斷正誤，將正確的劃上“”，錯誤的劃上“”，每小題1分，共10分）1參考答案：2參考答案：3參考答案：4參考答案：5參考答案：6參考答案：7參考答案：8參考答案：9參考答案：10參考答案：四、簡答題（每小題4分，共20分）1參考答案： s=new lnode;s-data=x;p-prior-next=s;s-prior=p-prior;s-next=p;p-prio

58、r=s;2參考答案：本題用Prim算法構(gòu)造出最小生成樹共需四步，具每一步的變化情況如如：3參考答案：4參考答案：哈夫曼樹如下圖所示：WPL=20*2+15*2+14*2+7*3+3*4+4*4=1475參考答案：哈希表如下圖所示：五、算法題（共25分）1參考答案：T-lchildt-rchildPop(S)NULL2參考答案：e.key % m +i UNSUCCESS e3(1)參考答案：（2）參考答案：V1 V2 V4 V3（3）參考答案：從頂點Vi出發(fā)進(jìn)行深度優(yōu)先搜索圖。六、寫算法（共20分）1參考答案：templatevoid LinkList: SimpleSelectSort (L

59、node *la) /用單鏈表為存儲結(jié)構(gòu)實現(xiàn)選擇排序 Lnode *p,q; Type x; if(la-next) p=la-next; while(p-next) minp=p; q=p-next; while(q) if(minp-dataq.data)minp=q; q=q-next; /while if(minp!=p x=p-data; p-data=minp-data; minp-data:=x; /if p=p-next; /while /if /SimpleSelectSort2參考答案：templatevoid BiTree:MidOrder(BiTreeNode *T,

60、void (*Visit)(Type& e) while(T) MidOrder(T-lchild, Visit); Visit(T-data); T=T-rchild; /while/MidOrder 模擬試卷七一、單項選擇題（在每小題的四個備選答案中，選出一個正確的答案，并將其號碼填在題干后的括號內(nèi)。每小題1分，共10分）1假設(shè)執(zhí)行語句S的時間為O（1），則執(zhí)行下列程序段for(i=1;i=n;i+) for(j=i;jnext=p-next; p-next=s;B）q-next=s; s-next=p;C）p-next=s-next; s-next=p;D）p-next=s; s-nex