2023年自考類計算機類(工學類)數(shù)據(jù)結構歷年高頻考題帶答案難題附詳解

2023年自考類計算機類(工學類)數(shù)據(jù)結構歷年高頻考題帶答案難題附詳解（圖片大小可自由調整）第1卷一.歷年考點試題黑鉆版(共50題)1.一組字符(a，b，c，d)在文中出現(xiàn)的次數(shù)分別為(7，6，3，5)，字符'd'的哈夫曼編碼的長度為______。2.一棵含999個結點的完全二叉樹的深度為______。3.對于數(shù)組，通常具有的基本操作有______種，它們分別是______。4.設一個數(shù)組中，行下標i的范圍是從1到8，列下標的范圍是從1到10，假設此數(shù)組的初始存儲地址是A，則如果將此數(shù)組按照列優(yōu)先的順序連續(xù)存放，則元素Q[5][8]的起始地址是

A.1B.23C.24D.5295.以下為順序表的插入運算，分析算法，請在______處填上正確的語句。

voidinsert_sqlist(sqlistL,datatypex,inti)／*將X插人到順序表L的第i-1個位置*／

{if(L.1ast==maxsize)error("表滿");

if((i＜1)||(i＞L.last+1))error("非法位置");

for(j=L.last;j≥i;j--)

L.data[i-]=X;

L.last=L.last+1;

}6.對表長為9000的索引順序表進行分塊查找，假設每一塊的長度均為15，且以順序查找確定塊，則在各記錄的查找概率均相等的情況下，其查找成功的平均查找長度為______。7.無向圖G的鄰接矩陣一定是______A.對稱矩陣B.對角矩陣C.三角矩陣D.單位矩陣8.以下為單鏈表的建表算法，分析算法，請在______處填上正確的語句。

lklistcreate_iklist2()

/*直接實現(xiàn)的建表算法。*/

{head=malloc(size);

p=head;

scanf("%",&x);

while(X!='$')

{q=malloc(size);

q—＞data=x;

p—＞next=q;

______;

scanf("%",&x);

}

______;

return(head);

}

此算法的量級為______。9.已知散列函數(shù)為H(K)=Kmod12，鍵值序列為25,37,52,43,84,99,120,15,26,11,70,82，采用拉鏈法處理沖突，試構造開散列表，并計算查找成功的平均查找長度。10.求下面算法中變量count的值：(假設n為2的乘冪，并且n＞2)

intTime

{intn

count=0;x=2;

while(x＜n/2)

{x*=2;count++;

}

return(count)

}11.循環(huán)隊列用數(shù)組A[0…m-1]存放其元素值，已知其頭尾指針分別是front和rear，則當前隊列中的元素個數(shù)是

A.(rear-front+m)MODmB.rear-fomt+1C.rear-fribt-1D.rear-front12.已知二叉樹如下圖所示，請畫出該二叉樹的前序線索。

13.下列關于m階B樹的敘述中，錯誤的是______A.每個結點至多有m個關鍵字B.每個結點至多有m棵子樹C.插入關鍵字時，通過結點分裂使樹高增加D.刪除關鍵字時通過結點合并使樹高降低14.簡述一下算法的功能：

status

A

(1inkedlist

L)

{//L是無表頭結點的單鏈表

if

(L&&L—＞next)

{Q=L;L=L—＞next;P=L;

while(P—＞next)P=P—＞next;

P—＞next=Q;Q—＞next=NULL;

}

returnok;

)//A15.任意一棵具有n個結點的二叉樹，若它有m個葉子，則該二叉樹上度數(shù)為1的結點為______個。16.順序棧存放在S[m]中，S[0]為棧底，棧頂指針top初始值為-1，則棧滿的條件是top=______。17.無向圖的邊數(shù)的取值范圍為______

A．0～n(n-1)

B．0～n(n+1)

C．

D．18.請將下面的程序改成遞歸的過程。

voideditui(intn)

{inti;

i=n;

while(i＞1)

prinft(i--);

}19.對下圖進行拓撲排序，可以得到的拓撲序列是______

A.abcdeB.bacdeC.bcadeD.abdce20.寫出下列程序段的輸出結果。(假設此棧中元素的類型是char)

voidemain

{stacks;

charx,y;

InitStack(s)

x=‘1’,y=‘0’

push(s,x);

push(s,x);

push(s,y);

push(s,x)；

push(s,‘e’);

push(s,x);

pop(s,x);

push(s,‘h’);

while(!stackEmpty(s))

{pop(s,y);

printf(y);

}

prinft(x)

}21.對角矩陣中，除了______的元素之外，其余的元素都是零。則對于一個k對角線矩陣(k為奇數(shù))A是滿足下面的條件的矩陣；如果______，則元素a[ij=0。22.一個100×90的整型稀疏矩陣有10個非零元素，設每個整型數(shù)占2個字節(jié)，則用三元組表存儲該矩陣時，所需的字節(jié)數(shù)是______。23.以下算法在開散列表HP中查找鍵值等于K的結點，成功時返回指向該點的指針，不成功時返回空指針。請分析程序，并在______上填充合適的語句。

pointerresearch_openhash(keytypeK,openhashHP)

{i=H(K);

/*計算K的散列地址*/

p=HP[i];

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

while(______)p=p—＞next;

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

______;

}24.設線性表(a1，a2，…，a500)元素的值由小到大排列。對一個給定的k值，用二分法檢索查找表中與k相等的元素，在檢索不成功的情況下，至多需比較______次。25.對于一個具有N個頂點的圖，如果我們采用鄰接矩陣法表示，則此矩陣的維數(shù)應該是

A.(N-1)×(N-1)B.N×NC.(N+1)×(N+1)D.不確定26.Aarr和Barr兩個數(shù)組的說明如下：

VAR

Aarr:Array[O··7]ofchar;

Barr:Array[-5··2,3,··8]ofchar;這兩個數(shù)組分別能存放的字符的最大個數(shù)是

A.7和35B.1和5C.8和48D.1和627.刪除雙向循環(huán)鏈表中*p的前驅結點(存在)應執(zhí)行的語句是______。28.在一個長度為100的順序表中刪除第10個元素時，需移動______個元素。29.采用鄰接表表示n個頂點的有向圖時，若表結點的個數(shù)為m，則該有向圖的邊數(shù)為______。30.對于一個有向圖(有n個頂點)，假設用鄰接矩陣表示，那么該鄰接矩陣的大小是______A.n2B.nC.n(n-1)D.(n-1)231.若不帶頭結點的單鏈表的頭指針為head，則該鏈表為空的判定條件是

A.head==NULLB.head—＞next==NULLC.head!=NULLD.head—＞next==head32.當所有結點的權值都相等時，用這些結點構造的二叉排序樹上只有______。33.N個頂點的連通圖，至少有______條邊。34.以下為冒泡排序的算法。請分析算法，并在______處用適當?shù)恼Z句予以填充。

voidbubblesort(intn,listr)

/*fiag為特征位，定義為布爾型*/

{for(i=1;i＜=______，i++)

{______;

for(j=1;j＜=______;j++)

if(r[j+1].key＜r[j].key){flag=0;p=r[j];r[j]=r[j+1];r[j+1]=P;}

if(flag)return;

}

}35.下列算法用于判斷帶頭結點的循環(huán)雙鏈表A是否對稱相等，請在算法中的一填上正確的語句。

intdlink_symmetry(dlklists)

{j=true;

p=s—＞next;

q=s—＞prior;

while(p!=q)&(______)

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

{

(______);

(______);

}

else

j=false;

return(j);

}36.在一個長度為n的順序表(順序存儲的線性表)中，向第i個元素(1≤i≤n+1)之前插入一個新元素時，需向后移動

個元素。A.n-iB.n-i+1C.n-i-1D.i37.考慮下列四種排序方法，在排序過程中，關鍵碼比較的次數(shù)與記錄的初始排列順序無關的是

A.直接插入排序和快速排序B.快速排序和歸并排序C.直接選擇排序和歸并排序D.直接插入排序和歸并排序38.對任何一棵二叉樹，若其終端結點數(shù)為m0，度數(shù)為2的結點數(shù)為m2，那么m0和m2之間的關系是______。39.對無向圖，其鄰接矩陣是一個關于______對稱的矩陣。40.下面的程序在執(zhí)行時，S語句共被執(zhí)行了

次。

i=1;

while(i＜=n)

{for(j=i;j＜n;j++)

{

S

;

}

i=i+1;

}

41.已知一棵二叉樹的前序遍歷序列是ABDGCEFH，其中序遍歷序列為DGBAECHF。請畫出相應的二叉樹，并求出對應此二叉樹的后序遍歷序列，此二叉樹是完全二叉樹嗎?完全二叉樹有什么性質(特點)?42.求下面算法中變量count的值：(假設n為2的乘冪，并且n＞2)

intTime

{intn

count=0;x=2;

while(x＜n/2)

{x*=2;count++;

}

return(count)

}43.一個長度為10的有序表，按照二分查找法對該表進行查找，在表內各元素等概率的情況下，查找成功所需要的平均比較次數(shù)為

A.25/10B.27/10C.29/10D.31/1044.樹的孩子兄弟表示法又稱為二叉鏈表表示法，請畫出下圖樹T的二叉鏈表。

45.大多數(shù)排序算法都有兩個基本操作，它們是______和______。46.從一個順序存儲的循環(huán)隊列中刪除一個元素時，應該______。47.如果我們定義一個長度為N的串空間，則它最多能放______個字符。48.數(shù)組A[1..10，-2..6，2..8]以行優(yōu)先順序存儲，設第一個元素的首地址是100，每個元素占3個存儲長度的存儲空間，則元素A[5,0,7]的存儲地址為______。49.長度為12的按關鍵字有序的查找表采用順序組織方式。若采用二分查找方法，則在等概率情況下，查找失敗時的ASL值是

A.37/12B.62/13C.39/12D.49/1350.二叉排序樹的類型定義如下：

typedefstruetBSTNode{//二叉排序樹的結點結構

intdata;//數(shù)據(jù)域

structBSTNode*lchild,*rchild;//左、右孩子指針

}BSTNode,*BSTree;

設計遞歸算法，統(tǒng)計一棵二叉排序樹T中值小于a的結點個數(shù)。第1卷參考答案一.歷年考點試題黑鉆版1.參考答案：2[考點]哈夫曼編碼

[解析]先構造出相應的哈夫曼樹，然后進行編碼。2.參考答案：103.參考答案：兩

查找和修改4.參考答案：C5.參考答案：L.data[j]=L.data[j-1]6.參考答案：308.57.參考答案：A[考點]無向圖的鄰接矩陣表示法的特點

[解析]無向圖的鄰接矩陣是按主對角線對稱的，因此無向圖的鄰接矩陣一定是對稱的，而有向圖的鄰接矩陣不一定對稱，答案選A。8.參考答案：p=q

p—＞next=NULL

O(n)9.參考答案：

查找成功的平均查找長度為：(4*2+8)，12=4/310.參考答案：count=log2n11.參考答案：A12.參考答案：見下圖

[考點]二叉樹的線索化13.參考答案：A[考點]B樹的特征的判斷

[解析]m階B樹中，若樹非空，則根結點至少有一個關鍵字，最多有m-1個關鍵字。14.參考答案：本程序實現(xiàn)的功能就是：如果L的長度不小于2，則將首元結點刪去并插入到表尾。15.參考答案：n-2m+116.參考答案：m-1[考點]棧的順序存儲結構

[解析]設順序棧存放在S.data[maxsize]中，棧底位置是maxsize-1，?？盏臈l件S.top==maxsize，棧滿的條件S.top==0；設順序棧存放在S.data[maxsize]中，棧底位置是-1，?？諚l件是S.top==-1，棧滿條件是S.top==maxsize-1，由此可得答案為m-1。17.參考答案：C[考點]無向圖邊數(shù)的取值范圍。

[解析]根據(jù)圖的定義，圖中邊數(shù)最少為0，無向圖的邊數(shù)最多為，所以選C。18.參考答案：此遞推過程可以改寫成如下遞歸過程：

voidedkui(intj)

{if(i＞1)

{prind(j);

digui(j-1);

}

}19.參考答案：B[考點]拓撲排序

[解析]拓撲排序方法如下：

(1)在從有向圖中選擇一個沒有前驅(即入度為0)的頂點并且輸出。

(2)從網中刪去該頂點，并且刪去從該頂點發(fā)出的全部有向邊。

(3)重復上述兩步，直至全部頂點均已輸出，或者當前圖中剩余的頂點中沒有前趨(入度為0)頂點為止。

(4)輸出剩余的無前趨結點。

由于結點a的入度不為0，因此首先排除A，D；b的入度為0，輸出b，刪除頂點b和從該點出發(fā)的全部有向邊，接著找入度為0的結點，此時頂點a的入度為0，而頂點c的入度不為0，因此答案選B。20.參考答案：此題的輸出結果是hello。21.參考答案：主對角線和主對角線相臨兩側的若干條對角線上

i＞k或j＞k22.參考答案：60[考點]三元組表的存儲問題

[解析]稀疏矩陣共有10個非零元素，每個整型變量需要2個存儲單元，共需10×3×2=60個存儲單元。23.參考答案：(P!=NULL)&&(p—＞key!=K)return(p)24.參考答案：925.參考答案：B26.參考答案：C27.參考答案：p—＞prior=p—＞prior—＞prior;

p—＞prior—＞next=p;

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

p—＞prior=p—＞prior—＞prior;28.參考答案：9029.參考答案：m[考點]圖的鄰接表與圖的對應關系

[解析]有向圖的鄰接表中，表結點的個數(shù)等于有向圖的邊數(shù)。30.參考答案：A[考點]圖的鄰接矩陣表示法及鄰接矩陣的大小

[解析]鄰接矩陣的大小是和圖中頂點的個數(shù)有關的，當頂點個數(shù)為n時，鄰接矩陣的大小為n2。31.參考答案：A32.參考答案：右子樹33.參考答案：N—134.參考答案：n-1

flag-1

n-i35.參考答案：p—＞prior!=q||q—＞next!=P

p=p—＞next

q=q—＞prior。36.參考答案：B37.參考答案：C38.參考答案：m0=m2+1[考點]二叉樹中，終端結點的個數(shù)和度數(shù)為2的結點的個數(shù)之間的關系

[解析]終端結點的個數(shù)和度數(shù)為2的結點的個數(shù)之間的關系為m0=m2+1。39.參考答案：主對角線40.參考答案：A41.參考答案：根據(jù)二叉樹的遍歷規(guī)則，前序遍歷總是先訪問根結點，然后依次遍歷其左右子樹，而中序遍歷規(guī)則是先遍歷左子樹，再訪問根結點，然后訪問右子樹，則由以上規(guī)則，我們極易得出此二叉樹的根結點是A，中序遍歷序列中，根結點左右兩邊的結果分別屬于其左、右子樹，所以得出左子樹包含3個節(jié)點：B，D，G，右子樹包含四個結點C，E，F(xiàn)，H。在左子樹中，先序遍歷序B位于最前，而中序遍歷序列中，B位于最后，則可以得出結點B無右子樹，只有左子樹，又在B的子樹中，無論先序遍歷還是中序遍歷，D都位于G的前面，則G只能是D的右孩子，且D無左孩子，按照以上分析規(guī)則，我們同樣可以分析出此二叉樹的右子樹的結構。從而我們得到了此二叉樹的最終結構為：

此二叉樹的后序遍歷序列為：GDBEHFCA

從求出的二叉樹的形狀我們可以看出此二叉樹不是完全二叉樹，完全二叉樹的性