武漢大學(xué)數(shù)據(jù)結(jié)構(gòu)考試題附答案

.下面程序段的執(zhí)行次數(shù)為(A)for(i=0;i<n-1;i++)for(j=n;j〉i;j--)state;A.n(n+2)2B.(n-1)(n+2)2C.n(n+1)2D.(n-1)(n+2).一個向量第一個元素的存儲地址是100,每個元素的長度為2,則第5個元素的地址是(B)A.110B.108C.100D.120.一個棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是(C)A.edcbaB.decbaC.dceabD.abcde.循環(huán)隊列用數(shù)組A[0,m—1]存放其元素值，已知其頭尾指針分別是front和rear,則當(dāng)前隊列中的元素個數(shù)是(D)A.(rear-front+m)%mB.read-front+1C.read-front-1D.read-front.不帶頭結(jié)點的單鏈表head為空的判定條件是(A)A.head=NULLB.head-next=NULLC.head-next=headD.head!=NULL.在一個單鏈表中，若p所指的結(jié)點不是最后結(jié)點，在p之后插入s所指結(jié)點，則執(zhí)行(B)A.s-next=p;p-next=s;B.s-next=p-next;p-next=s;C.s-next=p-next;p=s;D.p-next=s;s-next=p;.從一個具有n個結(jié)點的單鏈表中查找其值等于x結(jié)點時，在查找成功的情況下，需平均比較多少個結(jié)點(D)A.nB.n2C.(n-1)2D.(n+1)28.從一個棧頂指針為HS的鏈棧中刪除一個結(jié)點時，用x保存被刪結(jié)點的值，則執(zhí)行(D)A.x=HS;HS=HS-next;B.x=HS-data;C.HS=HS-next;x=HS-data;D.x=HS-data;HS=HS-next;9.串是一種特殊的線性表，其特殊性體現(xiàn)在(B)A.可以順序存儲B.數(shù)據(jù)元素是一個字符C.可以鏈接存儲 D.數(shù)據(jù)元素可以是多個字符11.二維數(shù)組M的元素是4個字符(每個字符占一個存儲單元)組成的串，行下標(biāo)i的范圍從0到4,列下標(biāo)j的范圍從0到5,M按行存儲時元素M[3][5]的起始地址與M按列存儲時下列哪一元素的起始地址相同(B)A.M[2][4]B.M[3][4]C.M[3][5]D.M[4][4]12.數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標(biāo)i從1到8,列下標(biāo)j從1到10,從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，元素A[8][5]的起始地址為(C)A.SA+144B.SA+180C.SA+222D.SA+225.設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點，則此類二叉樹中所包含的結(jié)點數(shù)至少為：（B）A.2hB.2h-1C.2h+1D.h+1.已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是（D）A.acbedB.decabC.deabcD.cedba.樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里，我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵樹對應(yīng)的二叉樹。下列結(jié)論哪個正確（A）A.樹的先根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同B.樹的后根遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同C.樹的先根遍歷序列與其對應(yīng)的二叉樹的中序遍歷序列相同D.以上都不對16.具有6個頂點的無向圖至少應(yīng)有多少條邊才能確保是一個連通圖（A）A.5B.6C.7D.8.順序查找法適合于存儲結(jié)構(gòu)為（B）的線性表A.散列存儲B.順序存儲或鏈接存儲C.壓縮存儲 D.索引存儲.采用順序查找方法查找長度為n的線性表每個元素的平均查找長度為（C）A.nB.n2C.（n+1）2D.（n-1）2.有一個長度為12的有序表，按二分查找法對該表進(jìn)行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為（B）A.3512B.3712C.3912D.4312.有一個有序表為｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，當(dāng)二分查找值82為的結(jié)點時，幾次比較后查找成功（C）二、填空題（每空1分，共20分）1.在線性表的順序存儲中，元素之間的邏輯關(guān)系是通過物理存儲位置，決定的；在線性表的鏈接存儲中，元素之間的邏輯關(guān)系是通過鏈域的指針值決定的。2.對于一個具有N個結(jié)點的單鏈表，在已知的結(jié)點P后插入一個新結(jié)點的時間復(fù)雜度為0（1），在給定值為X的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為0（N）。 3.有一空棧，現(xiàn)有輸入序列1,2,3,4,5，經(jīng)push,push,pop,push,pop,push,push后，輸出序列為2,3。.在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的2倍 5.對于一棵具有n個結(jié)點的樹，該樹中所有結(jié)點的度數(shù)之和為n-1。.在一棵三叉樹中，度為3的結(jié)點數(shù)有2個，度為2的結(jié)點數(shù)有1個，度為1的結(jié)點數(shù)為2個，那么度為0的結(jié)點數(shù)有6個.在霍夫曼編碼中，若編碼長度只允許小于等于4,則除了已對兩個字符編碼為0和10外，還可以最多對4個字符編碼。.對于一個具有n個頂點和e條邊的連通圖，其生成樹中的頂點數(shù)和邊數(shù)分別為 n和n-1 。.對20個記錄進(jìn)行歸并排序時，共需要進(jìn)行5趟歸并，在第三趟歸并時是把長度為4的有序表兩兩歸并為長度為8的有序表。三、問答題1.簡述下面算法的功能(棧和隊列的元素類型均為int)voidalgo3(Queue&Q){StackS;intd;InitStack(S);while(!QueueEmpty(Q)){DeQueue(Q,d);Push(S,d);)while(!StackEmpty(S)){Pop(S,d);EnQueue(Q,d);))算法的功能：利用棧作輔助，將隊列中的數(shù)據(jù)元素進(jìn)行逆置已知一棵二叉樹的中序遍歷序列和先序遍歷序列為，試問能不能唯一確定一棵二叉樹。若給定先序遍歷序列和后序遍歷序列，能不能唯一確定呢？由中序遍歷序列和先序遍歷序列能唯一確定一棵二叉樹。由先序遍歷和后序遍歷序列不能唯一確定一棵二叉樹.。一、選擇題1.下面程序段的執(zhí)行次數(shù)為()for(i=0;i<n-1;i++)for（j=n;j〉i;j--）state;A.n（n+2）2B.（n-1）（n+2）2C.n（n+1）2D.（n-1）（n+2）.判定一個棧ST（最多元素為m0）為空的條件是：（ ）A.ST-top0 B.ST-top=0C.ST-topm0D.ST-top=m0.一個棧的入棧序列是a,b,c,d,e，則棧的不可能的輸出序列是（ ）A.edcbaB.decbaC.dceabD.abcde.在一個單鏈表中，若p所指的結(jié)點不是最后結(jié)點，在p之后插入s所指結(jié)點，則執(zhí)行（）A.s-next=p;p-next=s;B.s-next=p-next;p-next=s;C.s-next=p-next;p=s;D.p-next=s;s-next=p;.在一個鏈隊中，假設(shè)f和r分別為隊首和隊尾指針，則刪除一個結(jié)點的運算時（ ）A.r=f-next;B.r=r-next;C.f=f-next;D.f=r-next;6.串是一種特殊的線性表，其特殊性體現(xiàn)在（）A.可以順序存儲B.數(shù)據(jù)元素是一個字符 C.可以鏈接存儲D.數(shù)據(jù)元素可以是多個字符7.稀疏矩陣一般的壓縮方法有兩種，即（ ）A.二維數(shù)組和三維數(shù)組B.三元組和散列C.三元組和十字鏈表D.散列和十字鏈表8.將遞歸算法轉(zhuǎn)換成對應(yīng)的非遞歸算法時，通常需要使用（ ）A.棧B.隊列C.鏈表D.樹9.二維數(shù)組M的元素是4個字符（每個字符占一個存儲單元）組成的串，行下標(biāo)i的范圍從0到4,列下標(biāo)j的范圍從0到5,M按行存儲時元素M[3][5]的起始地址與M按列存儲時下列哪一元素的起始地址相同（ ）A.M[2][4]B.M[3][4]C.M[3][5]D.M[4][4]10.數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標(biāo)i從1到8,列下標(biāo)j從1到10,從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，元素A[8][5]的起始地址為（ ）A.SA+144B.SA+180C.SA+222D.SA+22511.如果T2是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點的后序就是T2中結(jié)點的（ ）A.前序B.中序C.后序D.層次序12.一個有n個頂點的無向圖最多有多少邊（）A.nB.n（n-1）C.n（n-1）2D.2n13.按照二叉樹的定義，具有3個結(jié)點的二叉樹有（）種A.3 B.4C.5D.614.在一非空二叉樹的中序遍歷序列中，根結(jié)點的右邊（）A.只有右子樹上的所有結(jié)點B.只有右子樹上的部分結(jié)點C.只有左子樹上的部分結(jié)點 D.只有左子樹上的所有結(jié)點15.在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的多少倍（）A.12 B.1C.2D.4.采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的（）A.先序遍歷 B.中序遍歷C.后序遍歷 D.按層遍歷.采用順序查找方法查找長度為 n的線性表每個元素的平均查找長度為()A.nB.n2C.(n+1)2D.(n-1)2二、填空題1.算法的計算量的大小稱為計算的— —。.數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的 和 以及他們之間的相互關(guān)系，并對這種結(jié)構(gòu)定義相應(yīng)的運算，設(shè)計出相應(yīng)的 ，而確保經(jīng)過這些運算后所得的新結(jié)構(gòu)是結(jié)構(gòu)類型。.在一個單鏈表中刪除p結(jié)點，應(yīng)執(zhí)行下列操作：q=p-next;p-data=p-next-data;TOC\o"1-5"\h\zp-next= ;free(q);.有一空棧，現(xiàn)有輸入序列5,4,3,2,1,經(jīng)push,push,pop,push,pop,push,push后，輸出序列為 。.在雙向鏈表中每個結(jié)點包含兩個指針域，一個指向 結(jié)點，另一個指向結(jié)點。.一維數(shù)組的邏輯結(jié)構(gòu)是 ，存儲結(jié)構(gòu)是 。7.對于一棵含有40個結(jié)點的理想平衡樹，它的高度為 。8.假定對長度n=50的有序表進(jìn)行折半搜索，則對應(yīng)的判定樹高度為 ，判定樹中前5層的結(jié)點數(shù)為 ，最后一層的結(jié)點數(shù)為 。 9.假定一組記錄的排序碼為(46,79,56,38,40,80)，對其進(jìn)行歸并排序的過程中，第二趟歸并后的結(jié)果為 。10.假定一組記錄的排序碼為(46,79,56,38,40,80),對其進(jìn)行快速排序的一次劃分的結(jié)果為。三、簡答題1.假定有四個元素A,B,C,D依次進(jìn)棧，進(jìn)棧過程中允許出棧，試寫出所有可能的出棧序列？2.一棵含有n個結(jié)點的k叉樹，可能達(dá)到的最大深度和最小深度各為多少？3.設(shè)有5000個無序的元素，希望用最快速度挑選出其中前10個最大的元素，在以下的排序方法中，采用哪種方法最好？為什么？(快速排序，堆排序，基數(shù)排序)一、選擇題1.B2.B3. C4.B 5. C 6.B9. C10.A11.B12.C13.B14.C15.C16.A 17.C 18. A19.C

二、填空題1.復(fù)雜度 2. 物理結(jié)構(gòu)二、填空題1.復(fù)雜度 2. 物理結(jié)構(gòu).4,3 5.前驅(qū)，后續(xù)6., 31 , 19線性結(jié)構(gòu) ，順序結(jié)構(gòu)7.5 8.9. [38465679][4084] 。10.(84,79,56,38,40,46)三、問答題1.答:共有14種可能的出棧序歹IJ為:ABCD,ABDC,ACBD,ACDB,BACD,ADCB,BADC,BCAD,BCDA,BDCA,CBAD,CBDA,CDBA,DCBA2.答：顯然能達(dá)到最大深度的是單支樹其深度為n；深度最小的是完全k叉樹。3.答：用堆排序最好，因為堆排序不需要等整個排序結(jié)束就可挑出前10個最大元素，而快速排序和基數(shù)排序都需等待整個排序結(jié)束才能知道前10個最大元素。.下面程序段的執(zhí)行次數(shù)為(A)for(i=0;i<n-1;i++)for(j=n;j〉i;j--)state;A.n(n+2)2B.(n-1)(n+2)2C.n(n+1)2D.(n-1)(n+2).一個向量第一個元素的存儲地址是100,每個元素的長度為2,則第5個元素的地址是(B)A.110B.108C.100D.120.一個棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是(C)A.edcbaB.decbaC.dceabD.abcde.循環(huán)隊列用數(shù)組A[0,m—1]存放其元素值，已知其頭尾指針分別是front和rear,則當(dāng)前隊列中的元素個數(shù)是(D)D.read-frontA.(rear-front+m)%mB.read-front+1C.read-front-1D.read-front.不帶頭結(jié)點的單鏈表head為空的判定條件是（A）A.head=NULLB.head-next=NULLC.head-next=headD.head!=NULL.在一個單鏈表中，若p所指的結(jié)點不是最后結(jié)點，在p之后插入s所指結(jié)點，則執(zhí)行（B）A.s-next=p;p-next=s;B.s-next=p-next;p-next=s;C.s-next=p-next;p=s;D.p-next=s;s-next=p;.從一個具有n個結(jié)點的單鏈表中查找其值等于x結(jié)點時，在查找成功的情況下，需平均比較多少個結(jié)點（D）A.nB.n2C.（n-1）2D.（n+1）28.從一個棧頂指針為HS的鏈棧中刪除一個結(jié)點時，用x保存被刪結(jié)點的值，則執(zhí)行（D）A.x=HS;HS=HS-next;B.x=HS-data;C.HS=HS-next;x=HS-data;D.x=HS-data;HS=HS-next;9.串是一種特殊的線性表，其特殊性體現(xiàn)在（B）A.可以順序存儲B.數(shù)據(jù)元素是一個字符C.可以鏈接存儲 D.數(shù)據(jù)元素可以是多個字符11.二維數(shù)組M的元素是4個字符（每個字符占一個存儲單元）組成的串，行下標(biāo)i的范圍從0到4,列下標(biāo)j的范圍從0到5,M按行存儲時元素M[3][5]的起始地址與M按列存儲時下列哪一元素的起始地址相同（B）A.M[2][4]B.M[3][4]C.M[3][5]D.M[4][4].數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標(biāo)i從1到8,列下標(biāo)j從1到10,從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，元素A[8][5]的起始地址為（C）A.SA+144B.SA+180C.SA+222D.SA+225.設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點，則此類二叉樹中所包含的結(jié)點數(shù)至少為：（B）A.2hB.2h-1C.2h+1D.h+1.已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列是（D）A.acbedB.decabC.deabcD.cedba.樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里，我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵樹對應(yīng)的二叉樹。下列結(jié)論哪個正確（A）A.樹的先根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同B.樹的后根遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同C.樹的先根遍歷序列與其對應(yīng)的二叉樹的中序遍歷序列相同D.以上都不對 16.具有6個頂點的無向圖至少應(yīng)有多少條邊才能確保是一個連通圖（A）A.5B.6C.7D.8.順序查找法適合于存儲結(jié)構(gòu)為（B）的線性表A.散列存儲B.順序存儲或鏈接存儲C.壓縮存儲D.索引存儲.采用順序查找方法查找長度為n的線性表每個元素的平均查找長度為(C)A.nB.n2C.(n+1)2D.(n-1)2.有一個長度為12的有序表，按二分查找法對該表進(jìn)行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為(B)A.3512B.3712C.3912D.4312.有一個有序表為｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，當(dāng)二分查找值82為的結(jié)點時，幾次比較后查找成功(C)二、填空題(每空1分，共20分)1.在線性表的順序存儲中，元素之間的邏輯關(guān)系是通過物理存儲位置，決定的；在線性表的鏈接存儲中，元素之間的邏輯關(guān)系是通過鏈域的指針值決定的。2.對于一個具有N個結(jié)點的單鏈表，在已知的結(jié)點P后插入一個新結(jié)點的時間復(fù)雜度為O(1)，在給定值為X的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為 O(N)。3.有一空棧，現(xiàn)有輸入序列1,2,3,4,5，經(jīng)push,push,pop,push,pop,push,push后，輸出序列為2,3。.在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的2倍 5.對于一棵具有n個結(jié)點的樹，該樹中所有結(jié)點的度數(shù)之和為n-1。.在一棵三叉樹中，度為3的結(jié)點數(shù)有2個，度為2的結(jié)點數(shù)有1個，度為1的結(jié)點數(shù)為2個，那么度為0的結(jié)點數(shù)有6個.在霍夫曼編碼中，若編碼長度只允許小于等于4,則除了已對兩個字符編碼為0和10外，還可以最多對4個字符編碼。.對于一個具有n個頂點和e條邊的連通圖，其生成樹中的頂點數(shù)和邊數(shù)分別為 n和n-1 。.對20個記錄進(jìn)行歸并排序時，共需要進(jìn)行5趟歸并，在第三趟歸并時是把長度為4的有序表兩兩歸并為長度為8的有序表。三、問答題1.簡述下面算法的功能(棧和隊列的元素類型均為int)voidalgo3(Queue&Q)｛StackS;intd;InitStack(S);while(!QueueEmpty(Q)){DeQueue(Q,d);Push(S,d);)while(!StackEmpty(S)){Pop(S,d);EnQueue(Q,d);))算法的功能：利用棧作輔助，將隊列中的數(shù)據(jù)元素進(jìn)行逆置2.已知一棵二叉樹的中序遍歷序列和先序遍歷序列為，試問能不能唯一確定一棵二叉樹。若給定先序遍歷序列和后序遍歷序列，能不能唯一確定呢？由中序遍歷序列和先序遍歷序列能唯一確定一棵二叉樹。由先序遍歷和后序遍歷序列不能唯一確定一棵二叉樹.。一、選擇題.下面程序段的執(zhí)行次數(shù)為()for(i=0;i<n-1;i++)for(j=n;j>i;j--)state;A.n(n+2)2B.(n-1)(n+2)2C.n(n+1)2D.(n-1)(n+2).判定一個棧ST(最多元素為m0)為空的條件是：( )A.ST-top0 B.ST-top=0C.ST-topm0D.ST-top=m0.一個棧的入棧序列是 a,b,c,d,e，則棧的不可能的輸出序列是()A.edcbaB.decbaC.dceabD.abcde.在一個單鏈表中，若p所指的結(jié)點不是最后結(jié)點，在p之后插入s所指結(jié)點，則執(zhí)行()A.s-next=p;p-next=s;B.s-next=p-next;p-next=s;C.s-next=p-next;p=s;D.p-next=s;s-next=p;.在一個鏈隊中，假設(shè)f和r分別為隊首和隊尾指針，則刪除一個結(jié)點的運算時（ ）A.r=f-next;B.r=r-next;C.f=f-next;D.f=r-next;6.串是一種特殊的線性表，其特殊性體現(xiàn)在（）A.可以順序存儲B.數(shù)據(jù)元素是一個字符C.可以鏈接存儲D.數(shù)據(jù)元素可以是多個字符7.稀疏矩陣一般的壓縮方法有兩種，即（ ）A.二維數(shù)組和三維數(shù)組B.三元組和散列C.三元組和十字鏈表D.散列和十字鏈表8.將遞歸算法轉(zhuǎn)換成對應(yīng)的非遞歸算法時，通常需要使用（ ）A.棧B.隊列C.鏈表D.樹9.二維數(shù)組M的元素是4個字符（每個字符占一個存儲單元）組成的串，行下標(biāo)i的范圍從0到4,列下標(biāo)j的范圍從0到5,M按行存儲時元素M[3][5]的起始地址與M按列存儲時下列哪一元素的起始地址相同（ ）A.M[2][4]B.M[3][4]C.M[3][5]D.M[4][4]10.數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標(biāo)i從1到8,列下標(biāo)j從1到10,從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，元素A[8][5]的起始地址為（ ）A.SA+144B.SA+180C.SA+222D.SA+22511.如果T2是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點的后序就是T2中結(jié)點的（ ）A.前序B.中序C.后序D.層次序12.一個有n個頂點的無向圖最多有多少邊（）A.nB.n（n-1）C.n（n-1）2D.2n13.按照二叉樹的定義，具有3個結(jié)點的二叉樹有（）種A.3 B.4C.5D.614.在一非空二叉樹的中序遍歷序列中，根結(jié)點的右邊（）A.只有右子樹上的所有結(jié)點B.只有右子樹上的部分結(jié)點C.只有左子樹上的部分結(jié)點 D,只有左子樹上的所有結(jié)點15.在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的多少倍（）A.12 B.1C.2D.4.采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的（）A.先序遍歷 B.中序遍歷C.后序遍歷D.按層遍歷.采用順序查找方法查找長度為n的線性表每個元素的平均查找長度為（）A.nB.n2C.（n+1）2D.（n-1）2二、填空題1.算法的計算量的大小稱為計算的— —。.數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的 和 以及他們之間的相互關(guān)系，并對這種結(jié)構(gòu)定義相應(yīng)的運算，設(shè)計出相應(yīng)的 ，而