本文格式為Word版，下載可任意編輯——北航軟院專業(yè)課2023真題及答案2023年“數(shù)據(jù)結(jié)構(gòu)與C程序設(shè)計(jì)〞(代碼991)試題

一、單項(xiàng)選擇題（此題共20分，每題各2分）

1．對(duì)于長(zhǎng)度為n的線性表，建立其對(duì)應(yīng)的單鏈表的時(shí)間繁雜度為()。A．O(1)；B．O(log2n)；．O(n)；D．O(n2)。

2．一般狀況下，在一個(gè)雙向鏈表中插入一個(gè)新的鏈結(jié)點(diǎn)，()。A．需要修改4個(gè)指針域內(nèi)的指針；B．需要修改3個(gè)指針域內(nèi)的指針；C．需要修改2個(gè)指針域內(nèi)的指針；D．只需要修改1個(gè)指針域內(nèi)的指針。

3．假設(shè)用單個(gè)字母表示中綴表達(dá)式中的一個(gè)運(yùn)算數(shù)(或稱運(yùn)算對(duì)象)，并利用堆棧產(chǎn)生中綴表達(dá)式對(duì)應(yīng)的后綴表達(dá)式。對(duì)于中綴表達(dá)式A+B*(C/D-E)，當(dāng)從左至右掃描到運(yùn)算數(shù)E時(shí)，堆棧中的運(yùn)算符依次是()。(注：不包含表達(dá)式的分界符)A．+*/-；B．+*(/-；C．+*-；．+*(-。

4．若某二叉排序樹的前序遍歷序列為50,20,40,30,80,60,70，則后序遍歷序列為()。A．30,40,20,50,70,60,80；B．30,40,20,70,60,80,50；C．70,60,80,50,30,40,20；D．70,60,80,30,40,20,50。

5．分別以6,3,8,12,5,7對(duì)應(yīng)葉結(jié)點(diǎn)的權(quán)值構(gòu)造的哈夫曼(Huffman)樹的深度為()。A．6；B．5；C．4；D．3。

6．以下關(guān)于圖的表達(dá)中，錯(cuò)誤的是()。A．根據(jù)圖的定義，圖中至少有一個(gè)頂點(diǎn)；

B．根據(jù)圖的定義，圖中至少有一個(gè)頂點(diǎn)和一條邊(弧)；C．具有n個(gè)頂點(diǎn)的無向圖最多有n(n-1)/2條邊；D．具有n個(gè)頂點(diǎn)的有向圖最多有n(n-1)條邊(弧)。

7．若在有向圖G的拓?fù)湫蛄兄?，頂點(diǎn)vi在頂點(diǎn)vj之前，則以下4種情形中不可能出現(xiàn)的是()。A．G中有?。籅．G中沒有?。?/p>

C．G中有一條從頂點(diǎn)vi到頂點(diǎn)vj的路徑；D．G中有一條從頂點(diǎn)vj到頂點(diǎn)vi的路徑。8．以下關(guān)于查找操作的表達(dá)中，錯(cuò)誤的是()。

A．在順序表中查找元素可以采用順序查找法，也可以采用折半查找法；B．在鏈表中查找結(jié)點(diǎn)只能采用順序查找法，不能采用折半查找法；C．一般狀況下，順序查找法不如折半查找法的時(shí)間效率高；D．折半查找的過程可以用一棵稱之為?判定樹?的二叉樹來描述。

9．在一棵m階B-樹中，除根結(jié)點(diǎn)之外的任何分支結(jié)點(diǎn)包含關(guān)鍵字的個(gè)數(shù)至少是()。A．m/2-1；B．m/2；C．m/2-1；D．m/2。

10．若對(duì)序列(49,38,65,97,76,13,27,49’)進(jìn)行快速排序，則第一趟排序終止(即確定了第1個(gè)分界元素的最終位置)時(shí)，序列的狀態(tài)是()。

A．(13,27,49’,38,49,76,97,65)；B．(13,38,27,49’,49,76,97,65)；C．(13,38,49’,27,49,97,76,65)；D．(13,38,49’,27,49,76,97,65)。

二、填空題(此題共20分，每題各2分)

1．非空線性表在采()存儲(chǔ)結(jié)構(gòu)的狀況下，刪除表的一個(gè)數(shù)據(jù)元素平均需要移動(dòng)表中近一半元素的位置。

2．將一個(gè)長(zhǎng)度為n的單鏈表鏈接到一個(gè)長(zhǎng)度為m的單鏈表后面，該算法的時(shí)間繁雜度用大O符

號(hào)表示為()。

3．若完全二叉樹的葉結(jié)點(diǎn)的數(shù)目為k，且最下面一層的結(jié)點(diǎn)數(shù)大于1，則該完全二叉樹的深度為()。

4．若深度為8的完全二叉樹的第7層有10個(gè)葉結(jié)點(diǎn)，則該二叉樹的結(jié)點(diǎn)總數(shù)為()。5．在具有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可以達(dá)到()。6．若對(duì)有向圖進(jìn)行拓?fù)渑判颍瑒t能夠得到拓?fù)湫蛄械臈l件是()。

7．已知長(zhǎng)度為10的順序表中數(shù)據(jù)元素按值從小到大排列。若在該表中進(jìn)行折半查找，則平均查找長(zhǎng)度(ASL)是()。

8．若在一棵m階B-樹的某個(gè)結(jié)點(diǎn)中插入一個(gè)新的關(guān)鍵字值而引起結(jié)點(diǎn)產(chǎn)生分裂，則該結(jié)點(diǎn)中原有的關(guān)鍵字值的數(shù)目是()。

9．有一種排序方法可能會(huì)出現(xiàn)這種狀況：最終一趟排序開始之前，序列中所有的元素都不在其最終應(yīng)當(dāng)在的位置上，這種排序方法是()。

10．若依照泡排序法的思想將序列(2,12,16,5,10)中元素按值從小到大進(jìn)行排序，整個(gè)排序過程中所進(jìn)行的元素之間的比較次數(shù)為()。

三、綜合題(此題共20分，每題各5分)

1．一般狀況下，當(dāng)一個(gè)算法中需要建立多個(gè)堆棧時(shí)可以選用以下三種處理方案之一。問：這三種方案之間相比較各有什么優(yōu)點(diǎn)和缺點(diǎn)？（1）多個(gè)堆棧共享一個(gè)連續(xù)的存儲(chǔ)空間；（2）分別建立多個(gè)采用順序存儲(chǔ)結(jié)構(gòu)的堆棧；（3）分別建立多個(gè)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的堆棧。

2．已知二叉樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，根結(jié)點(diǎn)指針為T，鏈結(jié)點(diǎn)類型定義為：typedefstructnode{

chardata;/*數(shù)據(jù)域*/

structnode*lchild,*rchild;/*指向左、右子樹的指針域*/}*BTREE；

下面的算法的功能是輸出二叉樹中所有葉結(jié)點(diǎn)的數(shù)據(jù)信息。請(qǐng)?jiān)谒惴ǖ目瞻滋?符號(hào)處)填入適合內(nèi)容，使算法完整。voidFUNC(BTREET){if(T!=NULL){if(()

printf(?%c?,T->data);FUNC();FUNC();}}

3．對(duì)給定AOE網(wǎng)(如題三3圖所示)，請(qǐng)完成

（1）分別求出各活動(dòng)ai(i=1,2,…,14)的最早開始時(shí)間與最晚開始時(shí)間；(以表格形式給出結(jié)果)

（2）求出所有關(guān)鍵路徑。(請(qǐng)以圖形方式畫出各關(guān)鍵路徑)

（說明：由于題三3圖在本網(wǎng)站內(nèi)無法顯示，可參見指定教材p280頁8-16題）

4．已知要將給定的關(guān)鍵字值序列(42,51,16,26,50,25,37,68,64,33,18)進(jìn)行散列存儲(chǔ)，并且要求裝填因子(也稱負(fù)載因子)α≈0.61，（1）請(qǐng)利用除留余數(shù)法構(gòu)造出適合的散列函數(shù)；

（2）請(qǐng)畫出利用該散列函數(shù)依次將序列中各關(guān)鍵字值插入到散列表以后表的狀態(tài)。設(shè)散列表初始為空，并且采用線性探測(cè)再散列法處理散列沖突。

四、算法設(shè)計(jì)題（此題15分）

假設(shè)長(zhǎng)度為n的順序表A[1..n]中每個(gè)數(shù)據(jù)元素為一整數(shù)，請(qǐng)寫出依照以下思想將表中數(shù)據(jù)元素按值從小到大進(jìn)行排序的算法：第1趟排序?qū)⒆钚≈翟胤旁贏[1]中，最大值元素放在A[n]中；第2趟排序?qū)⒋涡≈翟胤旁贏[2]中，次大值元素放在A[n-1]中；……，依此下去，直至排序終止。

五、填空題(此題共20分，每題各2分)

1．已知某等比數(shù)列的第一項(xiàng)a1為1，公比為3，以下程序的功能是輸出該數(shù)列中小于1000的最大項(xiàng)an及其對(duì)應(yīng)的n。

請(qǐng)?jiān)诔绦虻目瞻滋?符號(hào)處)填入適合內(nèi)容，使程序完整。main()

{intn=1,a=1,q=3;while(1){a=a*q;n++;if(a>=1000);}

printf(?n=%d,a=%d\\n?,n-1,);}

2．以下遞歸函數(shù)FUNC2的功能是判斷整型數(shù)組a[n]是否為遞增數(shù)組，即判斷數(shù)組的元素是否按值從小到大排列。若是一個(gè)遞增數(shù)組，則函數(shù)返回true，否則，函數(shù)返回false。請(qǐng)?jiān)诤瘮?shù)的空白處(符號(hào)處)填入適合內(nèi)容，使函數(shù)完整。boolFUNC2(inta[],intn){if(n==1)returntrue;if(n==2)return;

return}

3．以下程序的功能是主函數(shù)調(diào)用FUNC3函數(shù)求方陣a中兩條對(duì)角線上元素之和。請(qǐng)?jiān)诔绦虻目瞻滋?符號(hào)處)填入適合內(nèi)容，使程序完整。#defineN10

voidFUNC3(inta[N][N],int*p,int*q){inti;*p=0;*q=0;

for(i=0;ivoidFUNC4(intn){inti;i=n/10;if()FUNC4(i);putchar();}main(){intn;

printf(?請(qǐng)輸入一正整數(shù)n：?);scanf(?%d?,

printf(?轉(zhuǎn)換后的字符串是：?);FUNC4(n);}

5．以下程序的功能是將小寫字母轉(zhuǎn)換成對(duì)應(yīng)的大寫字母后的第2個(gè)字母，例如，將a轉(zhuǎn)換成C，將b轉(zhuǎn)換成D，其中，y轉(zhuǎn)換成A，z轉(zhuǎn)換成B。

請(qǐng)?jiān)诔绦虻目瞻滋?符號(hào)處)填入適合內(nèi)容，使程序完整。#includemain(){charch;

while((ch=getchar())!=‘\\n’)if(ch>=‘a(chǎn)’

if(ch>‘Z’}}

6．以下函數(shù)FUNC6的功能是刪除字符串s中的所有空白字符，包括Tab字符、回車符以及換行符。

請(qǐng)?jiān)诤瘮?shù)的空白處(符號(hào)處)填入適合內(nèi)容，使函數(shù)完整。

#include#include#includeFUNC6(char*s){inti,t;charc[80];

for(i=0,t=0;s[i];i++)if(!isspace())c[]=s[i];c[t]=‘\\0’;strcpy(s,c);}

7．以下程序的功能是判斷輸入的字符串是否是?回文?。(注：按順序讀與按逆序讀都一樣的字符串被稱為?回文?，例如：abcdcba)。

請(qǐng)?jiān)诔绦虻目瞻滋?符號(hào)處)填入適合內(nèi)容，使程序完整。#include#includemain()

{charch[81],*p=ch,*q;gets(p);q=p+;while(){if(*p==*q){p++;q--;}elsebreak;}if(p<q)

printf(?該字符串不是回文！\\n?);else

printf(?該字符串是回文！\\