2023年自考類計(jì)算機(jī)類(工學(xué)類)數(shù)據(jù)結(jié)構(gòu)歷年高頻考題帶答案難題附詳解

2023年自考類計(jì)算機(jī)類(工學(xué)類)數(shù)據(jù)結(jié)構(gòu)歷年高頻考題帶答案難題附詳解（圖片大小可自由調(diào)整）第1卷一.歷年考點(diǎn)試題黑鉆版(共50題)1.深度為k的二叉樹，所含葉子的個(gè)數(shù)最多為

A.2KB.KC.2K-1D.2K-12.已知有一組長(zhǎng)度為9的關(guān)鍵字序列為{22,63,72,54,97,17,37,80,92}，現(xiàn)在假設(shè)散列表的地址空間為T[0..10]，請(qǐng)用除余法構(gòu)造散列函數(shù)，如果存在沖突問題，請(qǐng)用線性探查法解決沖突，并給出相應(yīng)的散列表。3.排序的重要目的是為了以后對(duì)已排序的數(shù)據(jù)元素進(jìn)行

A.打印輸出B.分類C.查找D.合并4.對(duì)于一個(gè)非空的線性表，以下關(guān)于其邏輯結(jié)構(gòu)特征的描述，錯(cuò)誤的是______A.開始元素沒有前趨B.終端元素沒有后繼C.內(nèi)部元素有且僅有一個(gè)直接前趨和一個(gè)直接后繼D.所有數(shù)據(jù)元素都既有前趨和后繼5.______查找法的平均查找長(zhǎng)度與元素個(gè)數(shù)n無關(guān)。6.鄰接表存儲(chǔ)結(jié)構(gòu)下圖的深度優(yōu)先遍歷算法結(jié)構(gòu)類似于于叉樹的

A.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷7.已知有如下一個(gè)關(guān)鍵字序列{96,47,104,32,73,136,15,38,90,180}，按照上述插入順序構(gòu)造一棵二叉排序樹，則請(qǐng)給出二叉排序樹的構(gòu)造過程，說明其深度，并在等概率的條件下求出平均查找長(zhǎng)度。8.無向圖的鄰接矩陣是______，并且主對(duì)角線上的元素的值為______。9.設(shè)s="IAMAATHLETE"，t="GOOD"，則執(zhí)行下列串操作序列之后得到的suhl為______。

substr(sub1,s,5,2);substr(sub2,s,6,8);strcpy(t1,t);

strcat,(t1,sub2);strcat(sub1,t1);10.對(duì)表長(zhǎng)為9000的索引順序表進(jìn)行分塊查找，假設(shè)每一塊的長(zhǎng)度均為15，且以順序查找確定塊，則在各記錄的查找概率均相等的情況下，其查找成功的平均查找長(zhǎng)度為______。11.假設(shè)一個(gè)循環(huán)隊(duì)列的容量為50，對(duì)其進(jìn)行人隊(duì)和出隊(duì)操作，則經(jīng)過一段時(shí)間之后，有：

(1)front=35，rear=12；

(2)front=12，rear=35。

其中front和rear分別是隊(duì)頭和隊(duì)尾指針。

求：循環(huán)隊(duì)列中元素的個(gè)數(shù)?12.已知散列函數(shù)為H(K)=Kmod12，鍵值序列為25,37,52,43,84,99,120,15,26,11,70,82，采用拉鏈法處理沖突，試構(gòu)造開散列表，并計(jì)算查找成功的平均查找長(zhǎng)度。13.已知森林F={T1，T2,T3,T4,T5)，各棵樹Ti(i=1,2,3,4,5)中所含結(jié)點(diǎn)的個(gè)數(shù)分別為7,3,5,1,2，則與F對(duì)應(yīng)二叉樹的右子樹中的結(jié)點(diǎn)個(gè)數(shù)為

A.2B.3C.8D.1114.在下面的排序方法中，不需要通過比較關(guān)鍵字就能進(jìn)行排序的是

A.箱排序B.快速排序C.插入排序D.希爾排序15.設(shè)一個(gè)鏈棧的棧頂指針為ls，棧中結(jié)點(diǎn)兩個(gè)字段分別為info和next，其中next是指示后繼結(jié)點(diǎn)的指針，?？盏臈l件是______。如果棧不空，則退棧操作為p：=ls；______；dispose(p)。16.假設(shè)有一個(gè)容量為5的隊(duì)列，假設(shè)其初始狀態(tài)為front=rear=0，則對(duì)此隊(duì)列進(jìn)行下列操作之后，請(qǐng)畫出此時(shí)的頭、尾指針的變化情況和相應(yīng)的隊(duì)列內(nèi)元素的存儲(chǔ)情況。

(1)隊(duì)列為空(即沒有任何元素進(jìn)入)；

(2)A，B，C入隊(duì)；

(3)A出隊(duì)；

(4)B，C出隊(duì)，此時(shí)隊(duì)列為空。17.刪除雙向循環(huán)鏈表中*p的前驅(qū)結(jié)點(diǎn)(存在)應(yīng)執(zhí)行的語(yǔ)句是______。18.長(zhǎng)度為12的按關(guān)鍵字有序的查找表采用順序組織方式。若采用二分查找方法，則在等概率情況下，查找失敗時(shí)的ASL值是

A.37/12B.62/13C.39/12D.49/1319.由權(quán)值為1,2,3,4,5,6的六個(gè)葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹，則帶權(quán)的路徑的長(zhǎng)度為______。20.假設(shè)Q是一個(gè)具有11個(gè)元素存儲(chǔ)空間的循環(huán)隊(duì)列(隊(duì)尾指針指向隊(duì)尾元素的下一個(gè)位置，隊(duì)頭指針指向隊(duì)頭元素)，初始狀態(tài)Q.front=Q.rear=0；寫出依次執(zhí)行下列操作后頭、尾指針的當(dāng)前值。

a，b，c，d，e，f入隊(duì)，a，b，c，d出隊(duì)；(1)Q.front=______；Q.rear=______。

g，h，i，j，k，1入隊(duì)，e，f，g，h出隊(duì)；(2)Q.front=______；Q.rear=______。

M，n，o，P入隊(duì)，i，j，k，l，m出隊(duì)；(3)Q.front=______；Q.rear=______。21.如果需要對(duì)線性表頻繁進(jìn)行______或______操作，則不宜采用順序存儲(chǔ)結(jié)構(gòu)。22.對(duì)長(zhǎng)度為n的關(guān)鍵字序列進(jìn)行堆排序的空間復(fù)雜度為

A.O(log2n)B.O(1)C.O(n)D.O(n*log2n)23.以下有關(guān)數(shù)據(jù)結(jié)構(gòu)的敘述，正確的是

A.線性表的線性存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B.二叉樹的第i層上有2i-1個(gè)結(jié)點(diǎn)，深度為K的二叉樹上有2k-1個(gè)結(jié)點(diǎn)C.二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表D.棧的操作方式是先進(jìn)先出24.______查找法的平均查找長(zhǎng)度與元素個(gè)數(shù)n無關(guān)。25.以下算法在開散列表HP中查找鍵值等于K的結(jié)點(diǎn)，成功時(shí)返回指向該點(diǎn)的指針，不成功時(shí)返回空指針。請(qǐng)分析程序，并在______上填充合適的語(yǔ)句。

pointerresearch_openhash(keytypeK,openhashHP)

{i=H(K);

/*計(jì)算K的散列地址*/

p=HP[i];

/*i的同義詞子表表頭指針傳給P*/

while(______)p=p—＞next;

/*未達(dá)到表尾且未找到時(shí)，繼續(xù)掃描*/

______;

}26.就文件而言，按用戶的觀點(diǎn)所確定的基本存儲(chǔ)單元稱為______。按外設(shè)的觀點(diǎn)所確定的基本存儲(chǔ)單元稱為______。27.數(shù)組的長(zhǎng)度是______，線性表的長(zhǎng)度是______。28.在下面的程序中，語(yǔ)句S的執(zhí)行次數(shù)為

for(i=1;i＜=n-1;i++)

{for(j=n;j＞=i;j--)

{S;

}

29.樹的前序遍歷序列等同于該樹對(duì)應(yīng)二叉樹的______遍歷序列。30.假設(shè)一個(gè)順序棧存放在S.data[max]中，max-1是其棧底，則判斷棧滿的條件是______，判斷?？盏臈l件是______。31.對(duì)磁帶上的順序文件進(jìn)行更新某個(gè)記錄時(shí)，必須______整個(gè)文件。而在順序文件的最后添加新的記錄時(shí)，則不必______整個(gè)文件。32.若非連通無向圖G含有21條邊，則G的頂點(diǎn)個(gè)數(shù)至少為

A.7B.8C.21D.2233.在棧和隊(duì)列中，存取數(shù)據(jù)的原則分別是______A.先進(jìn)先出；先進(jìn)先出B.先進(jìn)后出；先進(jìn)先出C.先進(jìn)后出；先進(jìn)后出D.進(jìn)出的先后無所謂34.在按層次遍歷二叉樹的算法中，需要借助的輔助數(shù)據(jù)結(jié)構(gòu)是

A.隊(duì)列B.棧C.線性表D.有序表35.以下為單鏈表的定位運(yùn)算，分析算法，請(qǐng)?jiān)赺_____處填上正確的語(yǔ)句。

intlocate_iklist(1klisthead,datatypex)

/*求表head中第一個(gè)值等于x的結(jié)點(diǎn)的序號(hào)。不存在這種結(jié)點(diǎn)時(shí)結(jié)果為0*/

{p=head;j=O;

while(______){p=p—＞next;j++;}

if(p—＞data==x)return(j);

else{return(0);

}36.內(nèi)部排序的方法有許多種，

方法是從未排序序列中依次取出元素，與已排序序列中的元素作比較，將其放入已排序序列的正確位置上。A.歸并排序B.插入排序C.快速排序D.選擇排序37.______與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。38.從樹的根結(jié)點(diǎn)到樹中的其余結(jié)點(diǎn)之間的路徑______惟一的。39.在分塊查找法中，首先查找______，然后再查找相應(yīng)的______。40.設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱為

A.連接B.模式匹配C.求子串D.求串長(zhǎng)41.下列說法中正確的是

A.任何一棵二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2B.任何一棵二叉樹中的每個(gè)結(jié)點(diǎn)的度為2C.任何一棵二叉樹中的度肯定等于2D.任何一棵二叉樹中的度可以小于242.在一個(gè)具有N個(gè)頂點(diǎn)的無向完全圖中，包含的邊的總數(shù)是

A.N(N-1)/2B.N(N-1)C.N(N+1)D.N(N+1)/243.用S表示入棧操作，X表示出棧操作，若元素入棧的順序?yàn)?、2、3、4，為了得到1、3、4、2的出棧順序，相應(yīng)的S和X的操作序列為______。44.

方法是對(duì)序列中的元素通過適當(dāng)?shù)奈恢媒粨Q將有關(guān)元素一次性地放置在其最終位置上。A.歸并排序B.插入排序C.快速排序D.選擇排序45.對(duì)于數(shù)組，通常具有的基本操作有______種，它們分別是______。46.求下面算法中變量count的值：(假設(shè)n為2的乘冪，并且n＞2)

intTime

{intn

count=0;x=2;

while(x＜n/2)

{x*=2;count++;

}

return(count)

}47.設(shè)線性表L=(a1，a2，…，an)(n＞2)，表中元素按值的遞增順序排列。對(duì)一個(gè)給定的值k，分別用順序檢索和二分法檢索查找與k相等的元素，比較次數(shù)分別為s和b，若檢索不成功，則s和b的數(shù)量關(guān)系是______。48.對(duì)于棧頂指針為top的順序棧S，判斷?？盏臈l件是______A.S.top=0B.S.top＜0C.S.top=StackSize-1D.S.top=StackSize49.對(duì)于一個(gè)具有N個(gè)頂點(diǎn)的圖，如果我們采用鄰接矩陣法表示，則此矩陣的維數(shù)應(yīng)該是

A.(N-1)×(N-1)B.N×NC.(N+1)×(N+1)D.不確定50.已知完全二叉樹T的第5層只有7個(gè)結(jié)點(diǎn)，則該樹共有______個(gè)葉子結(jié)點(diǎn)。第1卷參考答案一.歷年考點(diǎn)試題黑鉆版1.參考答案：C2.參考答案：因?yàn)樯⒘泻瘮?shù)為：h(key)=key%11，則根據(jù)此函數(shù)得到上述關(guān)鍵字序列的散列地址為：(0,8,6,10,9,6,1,3,4)，前5個(gè)關(guān)鍵字在插入時(shí)，其相應(yīng)的地址是開放地址，可以直接插入到T[0]，T[8]，T[6]，T[10]，T[9]中，在插入到6個(gè)關(guān)鍵字時(shí)，其散列地址6已被關(guān)鍵字72占用，所以探查h1=(6+1)%11=7。此地址開放，所以將關(guān)鍵字17插入到T[7]中，然后再依次將關(guān)鍵字34，80，92插入到相應(yīng)的散列地址中即可。則相應(yīng)的散列袁為：

3.參考答案：C4.參考答案：D[考點(diǎn)]非空線性表的邏輯結(jié)構(gòu)特征

[解析]非空線性表的邏輯結(jié)構(gòu)特征是開始元素沒有前趨，終端元素沒有后繼，內(nèi)部元素有且僅有一個(gè)直接前趨和一個(gè)直接后繼。5.參考答案：散列表6.參考答案：A7.參考答案：根據(jù)二叉排序樹的生成過程，我們可以得到如下二叉排序樹的構(gòu)造結(jié)果：

此二叉排序樹的深度(即高度)為4，在二叉樹上，要找到第i層上的結(jié)點(diǎn)恰好需要比較i次，而在此二叉排序樹上，第1,2,3,4層上分別有1,2,3,4個(gè)結(jié)點(diǎn)，則在等概率的條件下，查找成功的平均查找長(zhǎng)度為：

8.參考答案：對(duì)稱零9.參考答案："AGOODATHLETE"10.參考答案：308.511.參考答案：如果一個(gè)循環(huán)隊(duì)列的總?cè)萘繛镹，則當(dāng)rear-front時(shí)，循環(huán)隊(duì)列中的元素的個(gè)數(shù)為rear-front，當(dāng)ear＜front時(shí)，循環(huán)隊(duì)列中的元素的個(gè)數(shù)為N+(rear-front)。所以此題中：(1)循環(huán)隊(duì)列中元素的個(gè)數(shù)為35-12=23；(2)循環(huán)隊(duì)列中元素的個(gè)數(shù)為50+(12-35)=27。12.參考答案：

查找成功的平均查找長(zhǎng)度為：(4*2+8)，12=4/313.參考答案：D14.參考答案：A15.參考答案：ls=null這是指鏈棧沒有設(shè)置頭結(jié)點(diǎn)的情況，一般情況下也不必設(shè)置ls：=ls↑.next；這一操作讓頭指針指示下一個(gè)結(jié)點(diǎn)16.參考答案：

根據(jù)隊(duì)列的操作規(guī)則：進(jìn)隊(duì)時(shí)，將新元素插入到rear所指的位置，然后將rear加1，front不變，出隊(duì)時(shí)，刪除front所指的元素，然后將front加1，rear不變，則有：A，B，C進(jìn)隊(duì)列后，rear指針指向3，front不變，A出隊(duì)列時(shí)，刪除A，將front加1，所以front指向1，rear不變，B，C都出隊(duì)時(shí)，fron加2，rear不變，此時(shí)，rear和front相等。17.參考答案：p—＞prior=p—＞prior—＞prior;

p—＞prior—＞next=p;

(或p—＞prior—＞prior—＞next=p;

p—＞prior=p—＞prior—＞prior;18.參考答案：B19.參考答案：5520.參考答案：Q.front=4；Q.rear=6。

Q.front=8；Q.rear=1。

Q.front=2；Q.rear=5。[考點(diǎn)]循環(huán)隊(duì)列的操作21.參考答案：插入

刪除22.參考答案：B[解析]由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。堆排序是就地排序，輔助空間為0(1)，但它是不穩(wěn)定的。23.參考答案：C24.參考答案：散列表25.參考答案：(P!=NULL)&&(p—＞ke