數(shù)據(jù)結(jié)構(gòu)自測(cè)題

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)自測(cè)題一．緒論1.1單項(xiàng)選擇題

1.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中,數(shù)據(jù)元素的①、數(shù)據(jù)信息在計(jì)算機(jī)中的②以及一組相關(guān)的運(yùn)算等的課程。

①A．操作對(duì)象Ｂ．計(jì)算方法Ｃ．規(guī)律結(jié)構(gòu)Ｄ．?dāng)?shù)據(jù)映象②A．存儲(chǔ)結(jié)構(gòu)Ｂ．關(guān)系Ｃ．運(yùn)算Ｄ．算法2.數(shù)據(jù)結(jié)構(gòu)DS(DataStruct)可以被形式地定義為DS=（D，R），其中D是①的有限集合，R是D上的②的有限集合。

①A．算法Ｂ．?dāng)?shù)據(jù)元素Ｃ．?dāng)?shù)據(jù)操作Ｄ．?dāng)?shù)據(jù)對(duì)象②A．操作Ｂ．映象Ｃ．存儲(chǔ)Ｄ．關(guān)系3.在數(shù)據(jù)結(jié)構(gòu)中，從規(guī)律上可以把數(shù)據(jù)結(jié)構(gòu)分成。

A．動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)Ｂ．緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)Ｃ．線性結(jié)構(gòu)和非線性結(jié)構(gòu)Ｄ．內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)4.算法分析的目的是①，算法分析的兩個(gè)主要方面是②。

①A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入和輸出的關(guān)系

C.分析算法的效率以求改進(jìn)D.分析算法的易懂性和文檔性②A.空間繁雜性和時(shí)間繁雜性B.正確性和簡(jiǎn)明性

C.可讀性和文檔性D.數(shù)據(jù)繁雜性和程序繁雜性

5.計(jì)算機(jī)算法指的是①，它必具備輸入、輸出和②等五個(gè)特性。①A.計(jì)算方法B.排序方法

C.解決問(wèn)題的有限運(yùn)算序列D.調(diào)度方法

②A.可行性、可移植性和可擴(kuò)展性B.可行性、確定性和有窮性C.確定性、有窮性和穩(wěn)定性D.易讀性、穩(wěn)定性和安全性

1.2填空題（將正確的答案填在相應(yīng)的空中）

1.數(shù)據(jù)規(guī)律結(jié)構(gòu)包括、和三種類型，樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為。

2.在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有個(gè)前驅(qū)結(jié)點(diǎn)；最終一個(gè)結(jié)點(diǎn)后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有個(gè)后續(xù)結(jié)點(diǎn)。

3.在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒(méi)有結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有個(gè)直接前驅(qū)結(jié)點(diǎn)，葉子結(jié)點(diǎn)沒(méi)有結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的直接后續(xù)結(jié)點(diǎn)可以。

4.在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以。

5.線性結(jié)構(gòu)中元素之間存在關(guān)系，樹形結(jié)構(gòu)中元素之間存在關(guān)系，圖形結(jié)構(gòu)中元素之間存在關(guān)系。

6.算法的五個(gè)重要特性是____,____,____,____,____。7.分析下面算法（程序段），該算法的時(shí)間繁雜度是____。

for(i=0;inext=p->next->next;B.p=p->next;C.p=p->next->next;D.next=p;

6、設(shè)單鏈表中指針p指向結(jié)點(diǎn)ai，指針f指向?qū)⒁迦氲男陆Y(jié)點(diǎn)x，問(wèn)：（1）當(dāng)x插在鏈表中兩個(gè)數(shù)據(jù)元素ai和ai+1之間時(shí)，只要先修改______后修改______即可。

A.p->next=fB.p->next=p->next->nextC.p->next=f->nextD.f->next=p->nextE.f->next=NULLF.f->next=p

（2）在鏈表中最終一個(gè)結(jié)點(diǎn)an之后插入時(shí)，只要先修改______后修改______即可。

A.f->next=pB.f->next=p->nextC.p->next=fD.p->next=f->nextE.f=NULL

7、在一個(gè)單鏈表中，若要在p所指向的結(jié)點(diǎn)之前插入一個(gè)新結(jié)點(diǎn)，則此算法的時(shí)間繁雜度為________。

A.O(n)B.O(n/2)C.O(1)D.O(n)8、不帶頭結(jié)點(diǎn)的單鏈表L為空的判定條件為_________。A.L==NULLB.L->next==NULLC.L->next==LD.L!=NULL9、帶頭結(jié)點(diǎn)的單鏈表L為空的判定條件為_________。A.L==NULLB.L->next==NULLC.L->next==LD.L!=NULL

10、指針p指向雙向鏈表中的結(jié)點(diǎn)ai，ai-1為ai的前驅(qū)結(jié)點(diǎn)，指針f指向?qū)⒁迦氲男陆Y(jié)點(diǎn)x。x插在ai-1和ai之間，此時(shí)需要修改指針的操作依次為_________________。

A.p->prior->next=fB.p->prior=f

C.f->next=pD.f->prior=p->prior

11、在一個(gè)帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表中，若要在指針p所指的結(jié)點(diǎn)之后插入一個(gè)q指針?biāo)赶虻慕Y(jié)點(diǎn)，則需要對(duì)q->next賦值為______。A.p->priorB.p->next

C.p->next->nextC.p->prior->prior

二、填空題：

1、線性表的兩種存儲(chǔ)結(jié)構(gòu)分別為__________和_______________。

2、若經(jīng)常需要對(duì)線性表進(jìn)行插入和刪除運(yùn)算，則最好采用_______存儲(chǔ)結(jié)構(gòu)，若經(jīng)常需要對(duì)線性表進(jìn)行查找運(yùn)算，則最好采用________存儲(chǔ)結(jié)構(gòu)。3、訪問(wèn)一個(gè)線性表中具有給定值元素的時(shí)間繁雜度為__________。

3

4、對(duì)于一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線性表，在表頭插入元素的時(shí)間繁雜度為______，在表尾插入元素的時(shí)間繁雜度為___________。5、單鏈表是____________的鏈接存儲(chǔ)表示。6、在一個(gè)單鏈表中指針p所指向的結(jié)點(diǎn)的后面插入一個(gè)指針q所指向的結(jié)點(diǎn)時(shí)，首先把_______的值賦給q->next，然后把__________的值賦給p->next。

7、在一個(gè)單鏈表中的p所指結(jié)點(diǎn)之前插入一個(gè)s所指結(jié)點(diǎn)時(shí)，可執(zhí)行如下操作：（1）s->next=?______________;（2）p->next=s;（3）t=p->data;

（4）p->data=?______________;（5）s->data=?______________;

8、假定指向單鏈表中第一個(gè)結(jié)點(diǎn)的表頭指針為head，則向該單鏈表的表頭插入指針p所指向的新結(jié)點(diǎn)時(shí)，首先執(zhí)行____________賦值操作，然后執(zhí)行________________賦值操作。9、在一個(gè)單鏈表中刪除指針p所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)時(shí)，需要把_____________的值賦給p->next指針域。

10、在一個(gè)單鏈表中刪除指針p所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行以下操作：

q=p->next;

p->data=p->next->data;p->next=___________;free(q);

11、在________鏈表中，既可以通過(guò)設(shè)定一個(gè)頭指針也可以通過(guò)設(shè)定一個(gè)尾指針來(lái)確定它，即通過(guò)頭指針或尾指針可以訪問(wèn)到該鏈表中的每個(gè)結(jié)點(diǎn)。12、在一個(gè)雙向循環(huán)鏈表中指針p所指向的結(jié)點(diǎn)之前插入一個(gè)新結(jié)點(diǎn)時(shí)，其時(shí)間繁雜性的量級(jí)為___________________。

三、簡(jiǎn)答題

1、對(duì)于線性表的兩種存儲(chǔ)結(jié)構(gòu)，假使線性表的總數(shù)基本穩(wěn)定，并且很少進(jìn)行插入和刪除操作，但是要求以最快的速度存取線性表中的元素，則應(yīng)選中用哪種存儲(chǔ)結(jié)構(gòu)？試說(shuō)明理由。

2、有哪些鏈表可僅由一個(gè)尾指針來(lái)唯一確定，即從尾指針出發(fā)能訪問(wèn)到鏈表上任何一個(gè)結(jié)點(diǎn)？

3、在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點(diǎn)，不知道頭指針，能否將結(jié)點(diǎn)*p從相應(yīng)的鏈表中刪除？若可以，其時(shí)間繁雜度各為多少？

4

四、算法閱讀題

讀下面的程序段，畫出執(zhí)行過(guò)程的示意圖及所完成的功能。1.

#defineN6voidmain(){

SqListL;intA[N];

inti,j,m,elem;

InitList_Sq(L);//初始化順序表for(j=0;jnext;P=L;while(P->next)P=P->next;P->next=Q;Q->next=NULL;}