全國(guó)2011年10月自考試卷02331數(shù)據(jù)結(jié)構(gòu)

　　數(shù)據(jù)結(jié)構(gòu)試題

　　課程代碼：02331

　　一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)

　　在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫(xiě)在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。

　　1、在數(shù)據(jù)的邏輯結(jié)構(gòu)中，樹(shù)結(jié)構(gòu)和圖結(jié)構(gòu)都是( )

　　A.非線性結(jié)構(gòu) B.線性結(jié)構(gòu)

　　C.動(dòng)態(tài)結(jié)構(gòu) D.靜態(tài)結(jié)構(gòu)

　　2.在一個(gè)長(zhǎng)度為n的順序表中插入一個(gè)元素的算法的時(shí)間復(fù)雜度為( )

　　A.O(1) B.O(log n)

　　C.O(n) D.O(n2)

　　3.指針p1和p2分別指向兩個(gè)無(wú)頭結(jié)點(diǎn)的非空單循環(huán)鏈表中的尾結(jié)點(diǎn)，要將兩個(gè)鏈表鏈接成一個(gè)新的單循環(huán)鏈表，應(yīng)執(zhí)行的操作為( )

　　A.p1->next=p2->next;p2->next=p1->next;

　　B. p2->next=p1->next;p1->next=p2->next;

　　C. p=p2->next; p1->next=p;p2->next=p1->next;

　　D. p=p1->next; p1->next= p2->next;p2->next=p;

　　4.設(shè)棧的初始狀態(tài)為空，入棧序列為1，2，3，4，5，6，若出棧序列為2，4，3，6，5，1，則操作過(guò)程中棧中元素個(gè)數(shù)最多時(shí)為( )

　　A.2個(gè) B.3個(gè)

　　C.4個(gè) D.6個(gè)

　　5.隊(duì)列的特點(diǎn)是( )

　　A.允許在表的任何位置進(jìn)行插入和刪除

　　B.只允許在表的一端進(jìn)行插入和刪除

　　C.允許在表的兩端進(jìn)行插入和刪除

　　D.只允許在表的一端進(jìn)行插入，在另一端進(jìn)行刪除

　　6.一個(gè)鏈串的結(jié)點(diǎn)類(lèi)型定義為

　　﹟define NodeSize 6

　　typedef struct node{

　　char data[NodeSize];

　　struct node*next;

　　}LinkStrNode;

　　如果每個(gè)字符占1個(gè)字節(jié)，指針占2個(gè)字節(jié)，該鏈串的存儲(chǔ)密度為( )

　　A.1/3 B.1/2

　　C.2/3 D.3/4

　　7.廣義表A=(a,B,(a,B,(a,B,……)))的長(zhǎng)度為( )

　　A.1 B.2

　　C.3 D.無(wú)限值

　　8.已知10×12的二維數(shù)組A，按“行優(yōu)先順序”存儲(chǔ)，每個(gè)元素占1個(gè)存儲(chǔ)單元，已知A[1][1]的存儲(chǔ)地址為420，則A[5][5]的存儲(chǔ)地址為( )

　　A.470 B.471

　　C.472 D.473

　　9.在一棵二叉樹(shù)中，度為2的結(jié)點(diǎn)數(shù)為15，度為1的結(jié)點(diǎn)數(shù)為3，則葉子結(jié)點(diǎn)數(shù)為( )

　　A.12 B.16

　　C.18 D.20

　　10.在帶權(quán)圖的最短路徑問(wèn)題中，路徑長(zhǎng)度是指( )

　　A.路徑上的頂點(diǎn)數(shù) B.路徑上的邊數(shù)

　　C.路徑上的頂點(diǎn)數(shù)與邊數(shù)之和 D.路徑上各邊的權(quán)值之和

　　11.具有n個(gè)頂點(diǎn)、e條邊的無(wú)向圖的鄰接矩陣中，零元素的個(gè)數(shù)為( )

　　A.e B.2e

　　C.n2-2e D.n2-1

　　12.要以O(shè)(n log n)時(shí)間復(fù)雜度進(jìn)行穩(wěn)定的排序，可用的排序方法是( )

　　A.歸并排序 B.快速排序

　　C.堆排序 D.冒泡排序

　　13.若希望在1000個(gè)無(wú)序元素中盡快求得前10個(gè)挺大元素，應(yīng)借用( )

　　A.堆排序 B.快速排序

　　C.冒泡排序 D.歸并排序

　　14.對(duì)有序表進(jìn)行二分查找成功時(shí)，元素比較的次數(shù)( )

　　A.僅與表中元素的值有關(guān) B.僅與表的長(zhǎng)度和被查元素的位置有關(guān)

　　C.僅與被查元素的值有關(guān) D.僅與表中元素按升序或降序排列有關(guān)

　　15.散列文件是一種( )

　　A.順序存取的文件 B.隨機(jī)存取的文件

　　C.索引存取的文件 D.索引順序存取的文件

　　二、填空題(本大題共10小題，每小題2分，共20分)

　　請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。

　　16.若一個(gè)算法中的語(yǔ)句頻度之和為T(mén)(n)=3n3-200nlog2n+50n，則該算法的漸近時(shí)間復(fù)雜度為_(kāi)_________.

　　17.在單鏈表中，除了第1個(gè)元素結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置均由_____________指示。

　　18.棧的修改是按__________的原則進(jìn)行。

　　19.字符串中任意個(gè)連續(xù)的字符組成的子序列稱(chēng)為該串的__________。

　　20.假設(shè)一個(gè)10階的上三角矩陣A按行優(yōu)先順序壓縮存儲(chǔ)在一維數(shù)組B中，若矩陣中的第1個(gè)元素a11在B中的存儲(chǔ)位置k=0，則元素a55在B中的存儲(chǔ)位置k=__________。

　　21.在一棵具有n個(gè)結(jié)點(diǎn)的嚴(yán)格二叉樹(shù)中，度為1的結(jié)點(diǎn)個(gè)數(shù)為_(kāi)_________。

　　22.對(duì)于稀疏圖，采用__________表示法較為節(jié)省存儲(chǔ)空間。

　　23.在排序過(guò)程中，如果_____________，則稱(chēng)其為外部排序。

　　24.設(shè)有一組記錄的關(guān)鍵字為{19，14，23，1，68，12，10，78，25｝，用鏈地址法構(gòu)造散列表，散列函數(shù)為h(key)=key%11,散列地址為1的鏈中有__________個(gè)記錄。

　　25.多關(guān)鍵字文件的特點(diǎn)是除主文件和主索引外，還建有__________。

　　三、解答題(本大題共4小題，每小題5分，共20分)

　　26.對(duì)于下列稀疏矩陣(注：矩陣元素的行列下標(biāo)均從1開(kāi)始)

　　(1)畫(huà)出三元組表;

　　(2)畫(huà)出三元組表的行表。

　　(1)

　　(2)

　　27.已知一個(gè)森林的前序遍歷序列為CBADHEGF，后序遍歷序列為ABCDEFGH。

　　(1)畫(huà)出該森林;

　　(2)畫(huà)出該森林所對(duì)應(yīng)的二叉樹(shù)。

　　(1)

　　(2)

　　28.對(duì)關(guān)鍵字序列(429，653，275，897，170，908，473，256，726)進(jìn)行基數(shù)排序，寫(xiě)出每一趟的排序結(jié)果。

　　29.對(duì)下列關(guān)鍵字序列

　　(87，25，310，08，27，132，68，96，187，133，70，63，47，135)

　　構(gòu)造散列表，假設(shè)散列函數(shù)為h(key)=key%13,用拉鏈法解決沖突。

　　(1)畫(huà)出該散列表;

　　(2)求等概率情況下查找成功的平均查找長(zhǎng)度ASL;

　　(3)寫(xiě)出刪除值為70的關(guān)鍵字時(shí)所需進(jìn)行的關(guān)鍵字比較次數(shù)。

　　(1)

　　(2)

　　(3)

　　四、算法閱讀題(本大題共4小題，每小題5分，共20分)

　　30.閱讀下列算法，并回答問(wèn)題：

　　(1)假設(shè)L=(3，7，7，11，20，20，20，51，51)，寫(xiě)出執(zhí)行函數(shù)f30(&L)后的L;

　　(2)簡(jiǎn)述f30的功能。

　　void f30(SeqList*L)

　　{ ∥L為非空的有序表

　　int i=1,k=0;

　　while(ilength)

　　{

　　if(L->data[i]!=L->data[k])

　　L->data[++k]=L->data[i];

　　i++;

　　}

　　L->length=k+1;

　　}

　　(1)

　　(2)

　　31.閱讀下列算法，并回答問(wèn)題：

　　(1)假設(shè)棧S=(3，8，6，2，5)，其中5為棧頂元素，寫(xiě)出執(zhí)行函數(shù)f31(&S)后的S;

　　(2)簡(jiǎn)述函數(shù)f31的功能。

　　void f31(Stack *S){

　　Queue Q;InitQueue(&Q);

　　while(!StackEmpty(S))

　　EnQueue(&Q,Pop(&S));

　　while(!QueueEmpty(Q))

　　Push(&S,DeQueue(&Q));

　　}

　　(1)

　　(2)

　　32.假設(shè)具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)順序存儲(chǔ)在向量BT[1.. n]中，閱讀下列算法，并回答問(wèn)題：

　　(1)若向量BT為：

　　ABCDEFG

　　1 2 3 4 5 6 7

　　畫(huà)出執(zhí)行函數(shù)f32(BT,7,1)的返回結(jié)果;

　　(2)簡(jiǎn)述函數(shù)f32的功能。

　　BinTree f32(DataType BT[],int n,int i)

　　{

　　BinTree p;

　　if (i>n) return NULL;

　　p=(BinTNode*)malloc(sizeof(BinTNode));

　　p->data=BT[i];

　　p->lchild=f32(BT,n,i*2);

　　p->rchild=f32(BT,n,i*2+1);

　　return p;

　　}

　　(1)

　　(2)

　　33.已知有向圖的鄰接表和鄰接矩陣定義如下：

　　﹟define MaxNum 50 ∥圖的挺大頂點(diǎn)數(shù)

　　typedef struct node {

　　int adjvex; ∥鄰接點(diǎn)域

　　struct node *next; ∥鏈指針域

　　} EdgeNode; ∥邊表結(jié)點(diǎn)結(jié)構(gòu)

　　typedef struct{

　　char vertex; ∥頂點(diǎn)域

　　EdgeNode *firstedge; ∥邊表頭指針

　　} VertexNode; ∥頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)

　　typedef struct {

　　VertexNode adjlist [MaxNum]; ∥鄰接表

　　int n,e; ∥圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù)

　　} ALGraph; ∥鄰接表描述的圖

　　typedef struct{

　　char vertex[MaxNum]; ∥頂點(diǎn)表

　　int adjmatrix [MaxNum][MaxNum]; ∥鄰接矩陣

　　int n,e; ∥圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù)

　　} AMGraph; ∥鄰接矩陣描述的圖

　　下列算法是將鄰接表描述的圖G1改為鄰接矩陣描述的圖G2，在空白處填上適當(dāng)內(nèi)容使算法完整：

　　void f33(ALGraph G1,AMGraph *G2)

　　{ int i, j;

　　EdgeNode *p;

　　G2->n=G1.n;

　　G2->e= (1) ;

　　for (i=0; i

　　{ G2->vertex[i]= (2) ;

　　p=G1.adjlist[i].firstedge;

　　for (j=0; jadjmatrix[i][j]=0;

　　while (p)

　　{ G2->adjmatrix[i][p->adjvex]=1;

　　(3) ;

　　}

　　}

　　}

　　(1)

　　(2)

　　(3)

　　五、算法設(shè)計(jì)題(本題10分)

　　34.設(shè)順序表L是一個(gè)遞增有序表。編寫(xiě)算法，要求利用二分查找法確定插入位置，將元素x插入到L中，使L保持有序。

　　本自考試題下載：全國(guó)2011年10月自考試卷02331數(shù)據(jù)結(jié)構(gòu)

山東自考助學(xué)報(bào)名預(yù)約

請(qǐng)選擇您的報(bào)考層次 大專(zhuān) 本科 專(zhuān)本套讀

提交報(bào)名信息 重置信息

我已閱讀并同意《用戶隱私條款》

個(gè)人信息授權(quán)與保護(hù)聲明

關(guān)閉

鑒于網(wǎng)絡(luò)的特性，本網(wǎng)站將無(wú)可避免地與您產(chǎn)生直接或間接的互動(dòng)關(guān)系，故特此說(shuō)明本網(wǎng)站對(duì)用戶個(gè)人信息所采取的收集、使用和保護(hù)政策，請(qǐng)您務(wù)必仔細(xì)閱讀：

信息收集范圍

我們根據(jù)合法、正當(dāng)、必要的原則，僅收集為您提供服務(wù)所必要的信息。包括：

1、您在使用我們服務(wù)時(shí)主動(dòng)提供的信息

(2)您通過(guò)電話咨詢方式提供的姓名、電話、住址、微信/QQ、備注等信息。

(3)您在使用網(wǎng)上咨詢服務(wù)所提供的姓名、電話、住址、微信/QQ、備注等信息。

(4)您參與我們線上活動(dòng)時(shí)填寫(xiě)的調(diào)查問(wèn)卷中可能包含您的姓名、電話、地址等信息。

我們的部分服務(wù)可能需要您提供特定的個(gè)人敏感信息來(lái)實(shí)現(xiàn)特定功能。

若您選擇不提供該類(lèi)信息，則可能無(wú)法正常使用服務(wù)中的特定功能，但不影響您使用服務(wù)中的其他功能。

若您主動(dòng)提供您的個(gè)人敏感信息，即表示您同意我們按本政策所述目的和方式來(lái)處理您的個(gè)人敏感信息。

本次報(bào)名數(shù)據(jù)服務(wù)由本網(wǎng)站提供，本網(wǎng)站不承擔(dān)由于內(nèi)容的不一致性所引起的一切爭(zhēng)議和法律責(zé)任，報(bào)名結(jié)果以最終輔導(dǎo)報(bào)名系統(tǒng)為準(zhǔn)。

信息使用用途

我們嚴(yán)格遵守法律法規(guī)的規(guī)定及與用戶的約定，將收集的信息用于以下用途。若我們超出以下用途使用您的信息，我們將再次向您進(jìn)行說(shuō)明，并征得您的同意。

1、通過(guò)微信、電話形式建立溝通，向您提供學(xué)歷咨詢服務(wù)。

2、滿足您的個(gè)性化需求。例如，學(xué)歷途徑規(guī)劃、學(xué)歷評(píng)估等。

3、項(xiàng)目開(kāi)發(fā)和服務(wù)優(yōu)化。例如，通過(guò)您的咨詢問(wèn)題及服務(wù)過(guò)程中您的建議等，優(yōu)化我們的服務(wù)。

4、向您推薦您可能感興趣的學(xué)校、資訊等。

5、學(xué)校推薦。例如，我們會(huì)根據(jù)您的具體要求以您所具備的條件向您推薦合適的院校。

為了讓您有更好的體驗(yàn)、改善我們的服務(wù)或經(jīng)您同意的其他用途，在符合相關(guān)法律法規(guī)的前提下，我們可能將通過(guò)某些服務(wù)所收集的信息用于我們的其他服務(wù)。例如，將您在使用我們某項(xiàng)服務(wù)時(shí)的信息，用于另一項(xiàng)服務(wù)中向您展示個(gè)性化的內(nèi)容或廣告、用于用戶研究分析與統(tǒng)計(jì)等服務(wù)。

信息保護(hù)

我們僅在本《隱私政策》所述目的所必需的期間和法律法規(guī)要求的時(shí)限內(nèi)保留您的個(gè)人信息。

本網(wǎng)站將對(duì)您所提供的資料進(jìn)行嚴(yán)格的管理及保護(hù)，本網(wǎng)站將使用相應(yīng)的技術(shù)，防止您的個(gè)人資料丟失、被盜用或遭篡改。

當(dāng)政府機(jī)關(guān)依照法定程序要求本網(wǎng)站披露個(gè)人資料時(shí)，本網(wǎng)站將根據(jù)執(zhí)法單位之要求或?yàn)楣舶踩康奶峁﹤€(gè)人資料。在此情況下之任何披露，本網(wǎng)站均得免責(zé)。

由于您將用戶密碼告知他人或與他人共享注冊(cè)帳戶，由此導(dǎo)致的任何個(gè)人資料泄露。任何由于計(jì)算機(jī)問(wèn)題、黑客政擊、計(jì)算機(jī)病毒侵入或發(fā)作、因政府管制而造成的暫時(shí)性關(guān)閉等影響網(wǎng)絡(luò)正常經(jīng)營(yíng)之不可抗力而造成的個(gè)人資料泄露、丟失、被盜用或被篡改情況時(shí)本網(wǎng)站亦毋需承擔(dān)任何責(zé)任。

未成年人保護(hù)

本網(wǎng)站將建立和維持一合理的程序，以保護(hù)未成年人個(gè)人資料的保密性及安全性。本網(wǎng)站鄭重聲明：任何16歲以下的未成年人參加網(wǎng)上活動(dòng)應(yīng)事先得到家長(zhǎng)或其法定監(jiān)護(hù)人的可經(jīng)查證的同意。若您是未成年人的監(jiān)護(hù)人，當(dāng)您對(duì)您所監(jiān)護(hù)的未成年人的個(gè)人信息有相關(guān)疑問(wèn)時(shí)，請(qǐng)通過(guò)與我們聯(lián)系。

適用范圍

我們的所有服務(wù)均適用本政策。但某些服務(wù)有其特定的隱私指引/聲明，該特定隱私指引/聲明更具體地說(shuō)明我們?cè)谠摲?wù)中如何處理您的信息。如本政策與特定服務(wù)的隱私指引/聲明有不一致之處，請(qǐng)以該特定隱私指引/聲明為準(zhǔn)。

您必須完全同意以上協(xié)議才能使用本網(wǎng)站的在線報(bào)名服務(wù)。