2023年份全國(guó)高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題

2023年1月份全國(guó)高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題課程代碼：02331一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分。在每小題的四個(gè)備選答案中，選出一個(gè)對(duì)的答案，并將對(duì)的答案的序號(hào)填在題干的括號(hào)內(nèi))1.下面程序段的時(shí)間復(fù)雜度是(

)for(i=0;i<n;i++)

for(j=1;j<m;j++)

A[i][j]=0；A.O(n)

B.O(m+n+1)

C.O(m+n)

D.O(m*n)2.在單鏈表中，指針p指向元素為x的結(jié)點(diǎn)，實(shí)現(xiàn)“刪除x的后繼”的語(yǔ)句是(

)A.p=p->next;

B.p->next=p->next->next;C.p->next=p;

D.p=p->next->next;3.在頭指針為head且表長(zhǎng)大于1的單循環(huán)鏈表中，指針p指向表中某個(gè)結(jié)點(diǎn)，若p->next->next=head,則(

)A.p指向頭結(jié)點(diǎn)

B.p指向尾結(jié)點(diǎn)C.*p的直接后繼是頭結(jié)點(diǎn)

D.*P的直接后繼是尾結(jié)點(diǎn)4.鑒定“帶頭結(jié)點(diǎn)的鏈隊(duì)列為空”的條件是(

)A.Q.front==NULL

B.Q.rear==NULLC.Q.front==Q.rear

D.Q.front!=Q.rear5.設(shè)有兩個(gè)串T和P，求P在T中初次出現(xiàn)的位置的串運(yùn)算稱作(

)A.聯(lián)接

B.求子串

C.字符定位

D.子串定位6.廣義表A=(a,(b),(),(c,d,e))的長(zhǎng)度為(

)A.4

B.5

C.6

D.77.一棵含18個(gè)結(jié)點(diǎn)的二叉樹的高度至少為(

)A.3

B.4

C.5

D.68.已知二叉樹的先序序列為ABDECF，中序序列為DBEAFC，則后序序列為(

)A.DEBAFC

B.DEFBCA

C.DEBCFA

D.DEBFCA9.無(wú)向圖中一個(gè)頂點(diǎn)的度是指圖中(

)A.通過該頂點(diǎn)的簡(jiǎn)樸途徑數(shù)

B.與該頂點(diǎn)相鄰接的頂點(diǎn)數(shù)C.通過該頂點(diǎn)的回路數(shù)

D.與該頂點(diǎn)連通的頂點(diǎn)數(shù)10.已知一個(gè)圖如下所示，從頂點(diǎn)a出發(fā)進(jìn)行廣度優(yōu)先遍歷也許得到的序列為(

)A.acefbdB.acbdfeC.acbdefD.acdbfe11.在下列排序方法中，平均時(shí)間性能為O(nlogn)且空間性能最佳的是(

)A.快速排序

B.堆排序

C.歸并排序

D.基數(shù)排序12.已知一組關(guān)鍵字為{25,48,36,72,79,82,23,40,16,35}，其中每相鄰兩個(gè)為有序子序列。對(duì)這些子序列進(jìn)行一趟兩兩歸并的結(jié)果是(

)A.{25,36,48,72,23,40,79,82,16,35}B.{25,36,48,72,16,23,40,79,82,35}C.{25,36,48,72,16,23,35,40,79,82}D.{16,23,25,35,36,40,48,72,79,82}13.設(shè)順序存儲(chǔ)的線性表共有123個(gè)元素，按分塊查找的規(guī)定等提成3塊。若對(duì)索引表采用順序查找來擬定塊，并在擬定的塊中進(jìn)行順序查找，則在查找概率相等的情況下，分塊查找成功時(shí)的平均查找長(zhǎng)度為(

)A.21

B.23

C.41

D.6214.索引非順序文獻(xiàn)的特點(diǎn)是(

)A.主文獻(xiàn)無(wú)序，索引表有序

B.主文獻(xiàn)有序，索引表無(wú)序C.主文獻(xiàn)有序，索引表有序

D.主文獻(xiàn)無(wú)序，索引表無(wú)序15.倒排文獻(xiàn)的重要優(yōu)點(diǎn)是(

)A.便于進(jìn)行插入和刪除運(yùn)算

B.便于進(jìn)行文獻(xiàn)的恢復(fù)C.便于進(jìn)行多關(guān)鍵字查詢

D.節(jié)省存儲(chǔ)空間二、填空題(本大題共10小題，每小題2分，若有兩個(gè)空格，每個(gè)空格1分，共20分)16.抽象數(shù)據(jù)類型的特點(diǎn)是將____________和____________封裝在一起，從而現(xiàn)實(shí)信息隱藏。17.從順序表中刪除一個(gè)元素時(shí)，表中所有在被刪元素之后的元素均需____________一個(gè)位置。18.在隊(duì)列中，允許進(jìn)行插入操作的一端稱為____________，允許進(jìn)行刪除操作的一端稱為____________。19.如圖兩個(gè)棧共享一個(gè)向量空間，top1和top分別為指向兩個(gè)棧頂元素的指針，則“棧滿”的鑒定條件是____________。20.設(shè)S1="good",S2="

",S3="book"，則S1，S2和S3依次聯(lián)接后的結(jié)果是____________。21.假設(shè)三維數(shù)組A按行優(yōu)先順序存儲(chǔ)，若每個(gè)元素占3個(gè)存儲(chǔ)單元，且首地址為100，則元素A

的存儲(chǔ)地址是____________。22.已知在一棵具有n個(gè)結(jié)點(diǎn)的樹中，只有度為k的分支結(jié)點(diǎn)和度為0的葉子結(jié)點(diǎn)，則該樹中具有的葉子結(jié)點(diǎn)的數(shù)目為____________。23.可以成功完全拓?fù)渑判虻膱D一定是一個(gè)____________。24.假如在排序前，關(guān)鍵字序列已接近正序或逆序，則在堆排序和快速排序兩者之中，選用____________較為適當(dāng)。25.假設(shè)哈希表的表長(zhǎng)為m，哈希函數(shù)為H(key)，若用線性探查法解決沖突，則探查地址序列的形式表達(dá)為____________。三、解答題(本大題共4小題，每小題5分，共20分)26.假設(shè)通信電文使用的字符集為{a,b,c,d,e,f}，名字符在電文中出現(xiàn)的頻度分別為：34，5，12，23，8，18，試為這6個(gè)字符設(shè)計(jì)哈夫曼編碼。請(qǐng)先畫出你所構(gòu)造的哈夫曼樹(規(guī)定樹中左孩子結(jié)點(diǎn)的權(quán)值小于右孩子結(jié)點(diǎn)的權(quán)值)，然后分別寫出每個(gè)字符相應(yīng)的編碼。27.已知一個(gè)圖如下所示，其頂點(diǎn)按a、b、c、d、e、f順序存放在鄰接表的頂點(diǎn)表中，請(qǐng)畫出該圖的鄰接表，使得按此鄰接表進(jìn)行深度優(yōu)先遍歷時(shí)得到的頂點(diǎn)序列為acbefd，進(jìn)行廣度優(yōu)先遍歷時(shí)得到的頂點(diǎn)序列為acbdfe。28.已知兩個(gè)4×5的稀疏矩陣的三元組表分別如下：01416

0113212218

122－22234－25

2256934228

33425

44251請(qǐng)畫出這兩個(gè)稀疏矩陣之和的三元組表。29.從空樹起，依次插入關(guān)鍵字40，8，90，15，62，95，12，23，56，32，構(gòu)造一棵二叉排序樹。(1)畫出該二叉排序樹(2)畫出刪去該樹中元素值為90的結(jié)點(diǎn)之后的二叉排序樹。四、算法閱讀題(本大題共4小題，每小題5分，共20分)30.如圖所示，運(yùn)用同一循環(huán)向量空間實(shí)現(xiàn)兩個(gè)隊(duì)列，其類型Queue2定義如下：typedefstruct{

DataTypedata[MaxSize];

intfront,length;}Queue2;對(duì)于i=0或1,front[i]和length[i]分別為第i個(gè)隊(duì)列的頭指針和長(zhǎng)度域。請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，實(shí)現(xiàn)第i個(gè)循環(huán)隊(duì)列的入隊(duì)操作。intEnQueue(Queue2*Q,inti,DataTypex){//若第i個(gè)隊(duì)列不滿，則元素x入隊(duì)列，并返回1，否則返回0

if(i<0||i>1)return0;

if(

(1)

)

return0;

Q->data[

(2)

]=x;

Q->length[

(3)

]++;

return1;}(1)(2)(3)31.某二叉樹的線索鏈表存儲(chǔ)結(jié)構(gòu)如圖(b)所示，其中p為指向根結(jié)點(diǎn)的指針，圖(a)為結(jié)點(diǎn)結(jié)構(gòu)。閱讀下列算法，并回答問題：(1)寫出執(zhí)行函數(shù)調(diào)用f(p)的輸出結(jié)果；(2)簡(jiǎn)述函數(shù)f的功能。voidf(BinThrTreet){

while(t)

{

printf(t->data);

if(t->lchild)

t=t->lchild;

else

t=t->rchild;

}}(1)(2)32.下列函數(shù)FindCycle(G,i)的功能是，對(duì)一個(gè)采用鄰接表作存儲(chǔ)結(jié)構(gòu)的有向圖G，運(yùn)用深度優(yōu)先搜索策略尋找一條通過頂點(diǎn)vi的簡(jiǎn)樸回路。數(shù)組cycle_path用于保存搜索過程中形成的回路，cycle_path[k]=j(j≥0)表達(dá)在回路中頂點(diǎn)vk的下一個(gè)頂點(diǎn)是vj。請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，使其成為一個(gè)完整的算法。vertexfirstedge已知鄰接表的頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)為：adjvexnext邊表結(jié)點(diǎn)EdgeNode結(jié)構(gòu)為：intcycle_path[MaxNum];intFindCycle(ALGraph*G,inti){//若回路存在，則返回1，否則返回0

intj;

for(j=0;j<G->n;j++)cycle_path[j]=-1;

returnDFSPath(G,i,i);}intDFSPath(ALGraph*G,intj,inti){

EdgeNode*p;

intcycled=0;

for(p=G->adjlist[j].firstedge;p&&!cycled;p=p->next)

{

cycle_path[j]=p->adjvex;

if(

(1)

)cycled=1;//已找到回路

else

if(cycle_path[p->adjvex]==-1)cycled=

(2)

;

}

return

(3)

}(1)(2)(3)33.閱讀下列函數(shù)algo,并回答問題。(1)假設(shè)整型數(shù)組A[1..8]中的元素依次為(3，8，9，1，7，4，2，6)。執(zhí)行函數(shù)調(diào)用algo(A,8)時(shí)，外層while的循環(huán)體執(zhí)行多少次?函數(shù)的返回值是多少?(2)簡(jiǎn)述函數(shù)algo(L,n)的功能。intalgo(intL&#;,intn){

inti=0,j,s=1,t=n;

while(i!=(n+1)/2)

{

intx=L[s]；

i=s;j=t;

while(i<j)

{

while(i<j&&L[j]>=x)j--;

L[i]=L[j];

while(i<j&&L[i]<=x)i++;

L[j]=L[i];

}

L[i]=x;

if(i<(n+