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.以下將ah，…am，和am+1…an，兩個(gè)有序序列(它們相應(yīng)的關(guān)鍵字值滿足Kh≤Km，Km+1≤…Kn，)合并成一個(gè)有序序列Rh，…，Rn，(使其關(guān)鍵字值滿足Kh，'≤…≤Kn，')。請(qǐng)分析算法，并在______上填充適當(dāng)?shù)恼Z(yǔ)句。

voidmerge(lista,listR,inth,intm,intn)

{i=h;k=h;j=m+1;

while((i＜m)&&(j＜=n))

{if(a[i].key<=a[i].key){R[k]=______;______;}

else{R[k]=______;______;}

k++;

}

while(i＜=______){R[k]=a[i];i++;k++;)

while(j＜=______){R[k]=a[j];j++;k++;}

}

此算法的執(zhí)行時(shí)間為______。2.對(duì)于一個(gè)具有N個(gè)頂點(diǎn)的圖，如果我們采用鄰接矩陣法表示，則此矩陣的維數(shù)應(yīng)該是

A.(N-1)×(N-1)B.N×NC.(N+1)×(N+1)D.不確定3.多維數(shù)組和廣義表是一種非常復(fù)雜的非線性結(jié)構(gòu)，它們的邏輯特點(diǎn)是______。4.寫出向某個(gè)有序文件中插入一個(gè)記錄的程序。5.在一個(gè)長(zhǎng)度為n的單鏈表L中，刪除鏈表中*p的前驅(qū)結(jié)點(diǎn)的時(shí)間復(fù)雜度為______。6.若對(duì)關(guān)鍵字序列(43,02,80,48,26,57,15,73,21,24,66)進(jìn)行一趟增量為3的希爾排序，則得到的結(jié)果為______。7.廣義表的深度是指______。8.假設(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ì)列為空(即沒(méi)有任何元素進(jìn)入)；

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

(3)A出隊(duì)；

(4)B，C出隊(duì)，此時(shí)隊(duì)列為空。9.假設(shè)以帶頭結(jié)點(diǎn)的單鏈表表示有序表，單鏈表的類型定義如下：

typedefstructnode{

DataTypedata;

structnode*next

}LinkNode,*LinkList;

編寫算法，從有序表A中刪除所有和有序表B中元素相同的結(jié)點(diǎn)。10.在下面的程序中，語(yǔ)句S的執(zhí)行次數(shù)為

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

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

{S;

}

11.一棵樹中非葉子結(jié)點(diǎn)的個(gè)數(shù)為n，與樹對(duì)應(yīng)的二叉樹中右子樹為空的結(jié)點(diǎn)的個(gè)數(shù)為m，則m=______。12.判斷一個(gè)有向圖是否存在回路，除了可以利用拓?fù)渑判蚍椒?，還可以利用

A.求關(guān)鍵路徑的方法B.求最短路徑的Dijkstra方法C.廣度優(yōu)先遍歷方法D.深度優(yōu)先遍歷方法13.若序列中關(guān)鍵字相同的記錄在排序前后的相對(duì)次序不變，則稱該排序算法是______的。14.以下算法在有序表R中用二分查找法查找鍵值等于K的元素，請(qǐng)分析程序，并在______上填充合適的語(yǔ)句。

intbinsearch(sqtableR,keytypeK)

{low=l;hig=R.n;/*置查找區(qū)間初值。low，hig分別標(biāo)記查找區(qū)間的下、上界*/

while(low＜=hig)

{mid=(low+hig)/2;

switch

{caseK==R.item[i].key:return(mid);

/*找到，返回位置mid*/

caseK＜R.item[i].key:______.break;/*縮小區(qū)間*/

caseK＞R.item[i].key:______;break/*縮小區(qū)間*/

}

}

return(0);

/*若區(qū)間長(zhǎng)度已為0但仍不成功，則返回0，表示查找不成功*/

}15.在長(zhǎng)度為32的有序表中進(jìn)行二分查找時(shí)，所需進(jìn)行的關(guān)鍵字比較次數(shù)最多為

A.4B.5C.6D.716.對(duì)于如下一個(gè)有序的關(guān)鍵字序列{5,9,12,18,23,31,37,46,59,66,71,78,85)，現(xiàn)在要求用二分法進(jìn)行查找值為18的關(guān)鍵字，則經(jīng)過(guò)幾次比較之后能查找成功?17.數(shù)據(jù)元素之間的邏輯關(guān)系稱為數(shù)據(jù)的______結(jié)構(gòu)。18.產(chǎn)生沖突現(xiàn)象的兩個(gè)關(guān)鍵字稱為該散列函數(shù)的______。19.若序列中關(guān)鍵字相同的記錄在排序前后的相對(duì)次序不變，則稱該排序算法是______的。20.就文件而言，按用戶的觀點(diǎn)所確定的基本存儲(chǔ)單元稱為______。按外設(shè)的觀點(diǎn)所確定的基本存儲(chǔ)單元稱為______。21.在循環(huán)雙鏈表的p所指結(jié)點(diǎn)之后插入s所指結(jié)點(diǎn)的操作是

A.P—＞next=s；B.p—＞next=s；

s—＞prior=p；

p—＞next—＞prior=s；

p—＞next—＞prior=s；

s—＞prior=p；

s—＞next=p—＞next；

s—＞next=p—＞nextC.s—＞prior=p；D.s—＞prior=p；

s—＞next=p—＞next；

s—＞next=p—＞next；

p—＞next=s；

p—＞next—＞prior=s；

p—＞next—＞prior=s；

p—＞next=s；22.在一般情況下用直接插入排序、選擇排序和冒泡排序的過(guò)程中，所需記錄交換次數(shù)最少的是______。23.非空的單循環(huán)鏈表L的尾結(jié)點(diǎn)P↑，滿足

A.P↑.next=NULL;B.P=NULL;C.P↑.next=L;D.P=L24.已知圖G的鄰接表如下圖所示。

從頂點(diǎn)v1出發(fā)進(jìn)行深度優(yōu)先搜索，得到的深度優(yōu)先搜索序列是______。25.在按照順序存儲(chǔ)方式存儲(chǔ)的數(shù)組中，元素aij的存儲(chǔ)地址應(yīng)該是數(shù)組的______加上排在aij前面的元素所占用的單元數(shù)。26.對(duì)序列(8，13，26，55，29，44)從小到大進(jìn)行基數(shù)排序，第一趟排序的結(jié)果是______A.(13，44，55，26，8，29)B.(13，26，55，44，8，29)C.(8，13，26，29，44，55)D.(29，26，8，44，55，13)27.對(duì)于如圖所示的二叉樹，請(qǐng)畫出其順序存儲(chǔ)結(jié)構(gòu)圖。

28.假設(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=______。29.設(shè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表的頭指針為head，指針變量P指向尾結(jié)點(diǎn)的條件是______A.p-＞next-＞next==headB.p-＞next==headC.p-＞next-＞next==NULLD.p-＞next==NULL30.如果二叉樹中任何一個(gè)結(jié)點(diǎn)的值都小于它的左子樹上所有結(jié)點(diǎn)的值而大于右子樹上所有結(jié)點(diǎn)的值，要得到各結(jié)點(diǎn)值的遞增序列，應(yīng)按下列哪種次序排列結(jié)點(diǎn)

A.先根B.中根C.后根D.層次31.散列函數(shù)的作用是：______。32.INITIATE()的功能是建立一個(gè)空表。請(qǐng)?jiān)赺_____處填上正確的語(yǔ)句。

lklistinitiate_lklist()

/*建立一空表*/

{______;

______;

return(t);

}33.已知循環(huán)隊(duì)列的存儲(chǔ)空間大小為m，隊(duì)頭指針front指向隊(duì)頭元素，隊(duì)尾指針rear指向隊(duì)尾元素的下一個(gè)位置，則在隊(duì)列不滿的情況下，隊(duì)列的長(zhǎng)度是______。34.在下面的排序方法中，不需要通過(guò)比較關(guān)鍵字就能進(jìn)行排序的是

A.箱排序B.快速排序C.插入排序D.希爾排序35.從具有n個(gè)結(jié)點(diǎn)的單鏈表中查找值等于x的結(jié)點(diǎn)時(shí)，在查找成功的情況下，平均需比較

個(gè)結(jié)點(diǎn)。A.nB.n/2C.(n-1)/2D.(n+1)/236.以下運(yùn)算實(shí)現(xiàn)在循環(huán)隊(duì)上的入隊(duì)列，請(qǐng)?jiān)赺_____處用適當(dāng)?shù)恼Z(yǔ)句予以填充。

intEnCycQueue(CycquetaeTp*sq,DataTypex)

{if((sq—＞rear+1)%maxsize==______)

{error("隊(duì)滿");return(0);)

else{______;

______;

return(1);

}

}37.______與數(shù)據(jù)元素本身的內(nèi)容和形式無(wú)關(guān)。38.與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、個(gè)數(shù)無(wú)關(guān)的是數(shù)據(jù)的

A.存儲(chǔ)結(jié)構(gòu)B.存儲(chǔ)實(shí)現(xiàn)C.邏輯結(jié)構(gòu)D.運(yùn)算實(shí)現(xiàn)39.對(duì)于數(shù)組，通常具有的基本操作有______種，它們分別是______。40.假設(shè)一個(gè)循環(huán)隊(duì)列的容量為50，對(duì)其進(jìn)行人隊(duì)和出隊(duì)操作，則經(jīng)過(guò)一段時(shí)間之后，有：

(1)front=35，rear=12；

(2)front=12，rear=35。

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

求：循環(huán)隊(duì)列中元素的個(gè)數(shù)?41.算法分析的目的是

A.辨別數(shù)據(jù)結(jié)構(gòu)的合理性B.評(píng)價(jià)算法的效率C.研究算法中輸入與輸出的關(guān)系D.鑒別算法的可讀性42.已知L是無(wú)表頭結(jié)點(diǎn)的單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語(yǔ)句序列。(1)在P結(jié)點(diǎn)之前插入S結(jié)點(diǎn)的語(yǔ)句序列是______；(2)在表首插入S結(jié)點(diǎn)的語(yǔ)句序列是______。

a

P—＞nex=S

b

P—＞next=P—＞next—＞next

cP—＞next=S—＞next

dS—＞next=P—＞next

e

S—＞next=L

f

Q=P

gwhile(P—＞next!=Q＞P=P—＞next

hwhile(P—＞next!=NULL)P=P—＞next

i

P=L

j

L=S43.散列表的目的是

A.插入B.刪除C.快速查找D.排序44.在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有______個(gè)元素。45.棧和隊(duì)列均可視為特殊的線性表，所不同的在于對(duì)這二種特殊線性表______和______運(yùn)算的限定不一樣。46.在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置是由______指示。47.請(qǐng)根據(jù)下面所給出的鄰接矩陣畫出相應(yīng)的有向圖或者是無(wú)向圖(頂點(diǎn)vi表示)。

48.下面四種內(nèi)排序方法中，要求內(nèi)存容量最大的是

A.插入排序B.選擇排序C.快速排序D.歸并排序49.假設(shè)在圖G中任意的頂點(diǎn)設(shè)為vi，此頂點(diǎn)對(duì)應(yīng)的度為D(vi)，此圖的頂點(diǎn)數(shù)為n。則邊數(shù)e和度數(shù)之間的關(guān)系為______。50.如果T2是由有序樹T轉(zhuǎn)換而來(lái)的二叉樹，那么T中結(jié)點(diǎn)的后序就是T2中結(jié)點(diǎn)的

A.前序B.中序C.后序D.層次序第1卷參考答案一.歷年考點(diǎn)試題黑鉆版1.參考答案：a[i]

i++

a[j]

j++

mn

P(n-h+1)2.參考答案：B3.參考答案：一個(gè)數(shù)據(jù)元素可能有多個(gè)直接前趨和多個(gè)直接后繼4.參考答案：所謂有序文件是指文件的記錄按關(guān)鍵字由小到大(或由大到小)順序存放。為方便起見，可設(shè)文件的每一個(gè)記錄是一個(gè)整數(shù)，文件上數(shù)據(jù)是按由小到大順序存放。設(shè)插入數(shù)據(jù)是命令行的第3個(gè)參數(shù)，且設(shè)為d。若原文件中沒(méi)有數(shù)據(jù)，則d寫入文件；若有數(shù)據(jù)，則找到第1個(gè)比d大的數(shù)據(jù)i，先寫入d，再將i和其后各數(shù)據(jù)寫回文件中，可通過(guò)調(diào)用fseek函數(shù)采實(shí)現(xiàn)插入。相應(yīng)程序?yàn)椋?/p>

#include＜stdio.h＞

#include＜stdlib.h＞

#include＜io.h＞

#include＜fcntl.h＞

#defineLENsizeof(int)

voidmain(intargi,char**argc)

{intfp,i,d;

if(argi＜3)

{printf("filenameint\11")

exit(0);

}

d=atoi(argc[2]);

fp=open(argc[1],O_GREAT|O_RDWRIO_BINARY,s_IREAD|S_IWRITE);

while(1)

{if(read(fp,&I,LEN)!=LEN)

{write(fp，&d,LEN):

/*文件結(jié)束，d添加到文件尾端*/

break;)

if(i＞=d)

/*文件中讀出數(shù)據(jù)i，若i＞=d，則先存d*/

{do

{fseek(fp,-1L*lan,SEEK_CUR);

/*文件指針后退1個(gè)記錄*/

write(fp,&d,LEN);

/*d寫到文件中*/

d=i;

/*原i作d，以便處理其他數(shù)據(jù)*/

}while(read(fp,&i,LEN)==LEN);

write(fp，&d,LEN);/*繼續(xù)讀數(shù)據(jù)，并判別文件是否結(jié)束*/

break;

}

}

close(fp);

}

/*main*/5.參考答案：O(n)6.參考答案：15,02,21,24,26,57,43,66,80,48,737.參考答案：廣義表展開后所含括號(hào)的最大層數(shù)8.參考答案：

根據(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相等。9.參考答案：參考答案一：

voidf34(LinkListha,LinkListhb)

{

//hb和hb分剮為存放A和B有序鏈表的頭指針

LinkListp,q,r;

p=ha;

q=hb—＞next;

while(p—＞next&&q){

if(p—＞next—＞data＜q-＞data)

p=p—＞next;

else{

if(p—＞next—＞data==q—＞data){

r=p—＞next;

p—＞next=r—＞next;

free(r);

}

//從A表刪除相同的元素結(jié)點(diǎn)

q=q—＞next;

}

}

}

參考答案二：

voidf34(LinkListha,LinkListhb)

{

//hb和hb分別為存放A和B有序鏈表的頭指針

LinkListp,q,r;

r=ha;p=ha—＞next;

q=hb—＞next;

while(p&&q){

if(p—＞data＜q—＞data){

r=p;p=p-＞next;

}else{

if(p—＞data==q—＞data){

r—＞next=p—＞next;

free(p);

p=r—＞next;

}

//從A表刪除相同的元素結(jié)點(diǎn)

q=q—＞next

}

}

}10.參考答案：B11.參考答案：n+112.參考答案：D13.參考答案：穩(wěn)定14.參考答案：hig=mid-1low—low+115.參考答案：C16.參考答案：根據(jù)二分查找的過(guò)程，我們可以得到如下的比較結(jié)果：

第一次比較：[5,9,12,18,23,31,37,46,59,66,71,78,85,]

↑

第二次比較：[5,9,12,18,23,31],37,46,59,66,71,78,85

↑

第三次比較：5,9,12[18,23,31],37,46,59,66,71,78,85

↑

第四次比較：5,9,12[18]23,31,37,46,59,66,71,78,85

↑

則從上面的比較過(guò)程我們可以看出：經(jīng)過(guò)四次比較之后，就可以查找到值為18的關(guān)鍵字。17.參考答案：邏輯[考點(diǎn)]數(shù)據(jù)的邏輯結(jié)構(gòu)的概念

[解析]數(shù)據(jù)元素之間的邏輯關(guān)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。18.參考答案：同義詞19.參考答案：穩(wěn)定20.參考答案：邏輯記錄

物理記錄21.參考答案：D22.參考答案：選擇排序23.參考答案：C24.參考答案：v1、v4、v3、v5、v2[考點(diǎn)]圖的遍歷

[解析]深度優(yōu)先搜索(DFS)類似于樹的先根遍歷。深度優(yōu)先遍歷圖的方法是從圖中某頂點(diǎn)v出發(fā)：(1)訪問(wèn)頂點(diǎn)v；(2)依次從v的未被訪問(wèn)的鄰接點(diǎn)出發(fā)，對(duì)圖進(jìn)行深度優(yōu)先遍歷；直至圖中和v有路徑相通的頂點(diǎn)都被訪問(wèn)；(3)若此時(shí)圖中尚有頂點(diǎn)