- 歡迎來(lái)到山東自考網(wǎng)!為考生提供山東自考信息服務(wù),網(wǎng)站信息供學(xué)習(xí)交流使用,非政府官方網(wǎng)站,官方信息以山東教育考試院www.sdzk.cn/為準(zhǔn)。
全國(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(i
{
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; j
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ù)約
上一篇:全國(guó)2011年10月自考試卷02120數(shù)據(jù)庫(kù)及其應(yīng)用
下一篇:全國(guó)2011年10月自考試卷02142數(shù)據(jù)結(jié)構(gòu)導(dǎo)論
(一)由于各方面情況的調(diào)整與變化本網(wǎng)提供的考試信息僅供參考,敬請(qǐng)以教育考試院及院校官方公布的正式信息為準(zhǔn)。
(二)本網(wǎng)注明信息來(lái)源為其他媒體的稿件均為轉(zhuǎn)載體,免費(fèi)轉(zhuǎn)載出于非商業(yè)性學(xué)習(xí)目的,版權(quán)歸原作者所有。如有內(nèi)容與版權(quán)問(wèn)題等請(qǐng)與本站聯(lián)系。聯(lián)系方式:郵件 1105058242@qq.com
最近更新
- 2024年4月山東自考00402學(xué)前教育史試題 05-11
- 2024年4月山東自考00385學(xué)前衛(wèi)生學(xué)試題 05-11
- 2024年4月是山東自考00371公安決策學(xué)試題 05-11
- 2024年4月山東自考00370形事證據(jù)學(xué)試題 05-11
- 2024年4月山東自考00369警察倫理學(xué)試題 05-11
- 2024年4月山東自考00321中國(guó)文化概論試題 05-11
- 2024年4月山東自考00315當(dāng)代中國(guó)政治... 05-11
- 2024年4月山東自考00292市政學(xué)試題 05-09
- 2024年4月山東自考00277行政管理學(xué)試題 05-09
山東自考
- 2024年10月濟(jì)南自學(xué)考試溫馨提示 10-25
- 2024年10月濱州自考考點(diǎn)安排 10-21
- 2024年10月濟(jì)寧自考考點(diǎn)安排 10-21
- 2024年10月威海自考考點(diǎn)安排 10-18
- 2024年10月棗莊自考考點(diǎn)安排 10-18
- 2024年10月聊城自考考點(diǎn)安排 10-17
- 2024年10月淄博市自考考點(diǎn)安排 10-16
- 2024年10月山東濟(jì)南自考準(zhǔn)考證打印入口 09-27
- 2024年10月山東青島自考準(zhǔn)考證打印入口 09-27
掃一掃加入微信交流群
與其他自考生一起互動(dòng)、學(xué)習(xí)探討,提升自己。
掃一掃關(guān)注微信公眾號(hào)
隨時(shí)獲取自考信息以及各類(lèi)學(xué)習(xí)資料、學(xué)習(xí)方法、教程。