本文格式為Word版，下載可任意編輯——廣工2023數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題目及答案《數(shù)據(jù)結(jié)構(gòu)-C語言版》

第一章緒論

單項(xiàng)選擇題

1．在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的基本單位是_________。

A.數(shù)據(jù)項(xiàng)B.數(shù)據(jù)類型C.數(shù)據(jù)元素D.數(shù)據(jù)變量2．?dāng)?shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素之間的規(guī)律關(guān)系被稱為______。

A.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)B.數(shù)據(jù)的基本操作C.程序的算法D.數(shù)據(jù)的規(guī)律結(jié)構(gòu)3．在數(shù)據(jù)結(jié)構(gòu)中，與所使用計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的_______。

A.存儲(chǔ)結(jié)構(gòu)B.規(guī)律和物理結(jié)構(gòu)C.規(guī)律結(jié)構(gòu)D.物理結(jié)構(gòu)4．在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，數(shù)據(jù)之間的關(guān)系是通過________表達(dá)的。A.數(shù)據(jù)在內(nèi)存的相對位置B.指示數(shù)據(jù)元素的指針C.數(shù)據(jù)的存儲(chǔ)地址D.指針5．計(jì)算算法的時(shí)間繁雜度是屬于一種_______。

A.事前統(tǒng)計(jì)的方法B.事前分析估算的方法C.事后統(tǒng)計(jì)的方法D.事后分析估算的方法

6．在對算法的時(shí)間繁雜度進(jìn)行估計(jì)的時(shí)候，以下最正確的時(shí)間繁雜度是______。A.n2B.nlognC.nD.logn

7．設(shè)使用某算法對n個(gè)元素進(jìn)行處理，所需的時(shí)間是T(n)=100nlog2n+200n+2000，則該算法的漸近時(shí)間繁雜度為_______。

A.O(1)B.O(n)C.O(200n)D.O(nlog2n)

1

CDCBBDD

其次章線性表

單項(xiàng)選擇題

1．鏈表不具有的特點(diǎn)是________。

A.可隨機(jī)訪問任一元素B.插入和刪除時(shí)不需要移動(dòng)元素C.不必事先估計(jì)存儲(chǔ)空間D.所需空間與線性表的長度正比

2．設(shè)順序表的每個(gè)元素占8個(gè)存儲(chǔ)單元。第1個(gè)單元的存儲(chǔ)地址是100，則第6個(gè)元素占用的最終一個(gè)存儲(chǔ)單元的地址為。

A.139B.140C.147D.1483．在線性鏈表存儲(chǔ)結(jié)構(gòu)下，插入操作算法。A.需要判斷是否表滿B.需要判斷是否表空C.不需要判斷表滿D.需要判斷是否表空和表滿

4．在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行。A.p->next=p->next->next;B.p->next=p->next;

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

5．將長度為n的單鏈表接在長度為m的單鏈表之后的算法時(shí)間繁雜度為。A.O(n)B.O(1)C.O(m)D.O(m+n)

6．需要預(yù)分較大空間，插入和刪除不需要移動(dòng)元素的線性表，其存儲(chǔ)結(jié)構(gòu)是。A.單鏈表B.靜態(tài)鏈表C.線性鏈表D.順序存儲(chǔ)方式ACCABB填空題

1．在帶表頭結(jié)點(diǎn)的單鏈表中，當(dāng)刪除某一指定結(jié)點(diǎn)時(shí)，必需找到該結(jié)點(diǎn)的_____結(jié)點(diǎn)。2．在單鏈表中，指針p所指結(jié)點(diǎn)為最終一個(gè)結(jié)點(diǎn)的條件是。

3．將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是。4．在一個(gè)長度為n的順序表中第i個(gè)元素（1≤i≤n）之前插入一個(gè)元素時(shí)，需向后移動(dòng)元素的個(gè)數(shù)是。

5．在長度為n的順序表中插入一個(gè)元素的時(shí)間繁雜度為。1前驅(qū)2p->next==NULL

2

3.14.n-i+15.O(n)例題解析

編寫一個(gè)算法將一個(gè)單鏈表逆轉(zhuǎn)，要求在原表上進(jìn)行，不允許重新建鏈表。解：該算法可以在遍歷原表的時(shí)候?qū)⒏鹘Y(jié)點(diǎn)的指針逆轉(zhuǎn)，從原表的第一個(gè)結(jié)點(diǎn)開始，頭結(jié)點(diǎn)的指針在最終修改成指向原表的最終一個(gè)結(jié)點(diǎn)，即新表的第一個(gè)結(jié)點(diǎn)。實(shí)現(xiàn)此題功能的函數(shù)如下：

voidinverse(Lnode*h){s=h->next;

if(s==NULL)return;q=NULL;p=s;

while(p!=NULL){p=p->next;

s->next=q;/*逆轉(zhuǎn)指針*/q=s;/*指針前移*/s=p;}

h->next=q;/*頭指針h的后繼是p*/}

編寫一算法將兩個(gè)按元素值遞增有序排列的單鏈表A和B歸并成一個(gè)按元素值遞增有序排列的單鏈表C。

解：對于兩個(gè)或兩個(gè)以上的，結(jié)點(diǎn)按元素值有序排列的單鏈表進(jìn)行操作時(shí)，應(yīng)采用“指針平行移動(dòng)，依次掃描完成〞的方法。從兩表的第一個(gè)結(jié)點(diǎn)開始順鏈表逐個(gè)將對應(yīng)數(shù)據(jù)元素進(jìn)行比較，復(fù)制小的并插入c表尾。當(dāng)兩表中之一已到表尾，則復(fù)制另一個(gè)鏈表的剩余部分，插入到c表尾。設(shè)pa、pb分別指向兩表當(dāng)前結(jié)點(diǎn)，p指向c表的當(dāng)前表尾結(jié)點(diǎn)。若設(shè)A中當(dāng)前所指的元素為a，B中當(dāng)前所指的元素為b，則當(dāng)前應(yīng)插入到C中的元素c為

?ac???b例如：A=(3,5,8,11)B=(2,6,8,9,11,15,20)

則C=(2,3,5,6,8,8,9,11,11,15,20)實(shí)現(xiàn)此題功能的函數(shù)如下：Lnode*hb(Lnode*pa,Lnode*pb){Lnode*p,*q,*pc;

a?ba?bpc=(Lnode*)malloc(sizeof(Lnode));/*建立表c的頭結(jié)點(diǎn)pc*/

3

p=pc;/*p指向C表頭結(jié)點(diǎn)*/while(pa!=NULL/*建立新結(jié)點(diǎn)q*/

if(pb->datadata)/*比較A、B表中當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)域值的大小*/{q->data=pb->data;/*B中結(jié)點(diǎn)值小，將其值賦給q的數(shù)據(jù)域*/pb=pb->next;/*B中指針pb后移*/}else

{q->data=pa->data;/*相反，將A結(jié)點(diǎn)值賦給q的數(shù)據(jù)域*/pa=pa->next;/*A中指針pa后移*/}

p->next=q;/*將q接在p的后面*/p=q;/*p始終指向C表當(dāng)前尾結(jié)點(diǎn)*/}

while(pa!=NULL)/*若表A比B長，將A余下的結(jié)點(diǎn)鏈在C表尾*/{q=(Lnode*)malloc(sizeof(Lnode));q->data=pa->data;pa=pa->next;p->next=q;p=q;}

while(pb!=NULL)/*若表B比A長，將B余下的結(jié)點(diǎn)鏈在C表尾*/{q=(Lnode*)malloc(sizeof(Lnode));q->data=pb->data;pb=pb->next;p->next=q;p=q;}

p->next=NULL;

p=pc;/*p指向表C的頭結(jié)點(diǎn)pc*/

pc=p->next;/*改變指針狀態(tài)，使pc指向p的后繼*/free(p);/*釋放p空間*/return(pc);}

此算法的時(shí)間繁雜度為O(m+n)，其中m，n分別是兩個(gè)被合并表的表長。

4

第三章

單項(xiàng)選擇題

棧和隊(duì)列

1．在初始為空的堆棧中依次插入元素f，e，d，c，b，a以后，連續(xù)進(jìn)行了三次刪除操作，此時(shí)棧頂元素是。

A.ｃB.ｄC.ｂD.ｅ

2．若某堆棧的輸入序列是1，2，3，...，n，輸出序列的第一個(gè)元素為n，則第i個(gè)輸出元素為。

A.iB.n-iC.n-i+1D.哪個(gè)元素?zé)o所謂3．向一個(gè)棧頂指針為h的帶頭結(jié)點(diǎn)鏈棧中插入指針s所指的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行。A.h->next=s;B.s->next=h;

C.s->next=h;h=h->next;D.s->next=h->next;h->next=s;

4．一個(gè)棧的入棧序列是a，b，c，d，e，則棧的不可能的輸出序列是。A.edcbaB.decbaC.dceabD.abcde5．棧和隊(duì)列的共同點(diǎn)是。

A.都是先進(jìn)后出B.都是先進(jìn)先出C.只允許在端點(diǎn)處插入和刪除元素D.沒有共同點(diǎn)6．對于循環(huán)隊(duì)列。

A.無法判斷隊(duì)列是否為空B.無法判斷隊(duì)列是否為滿C.隊(duì)列不可能滿D.以上說法都不是

7.若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前隊(duì)尾指針rear和隊(duì)頭指針front的值分別為0和3。當(dāng)從隊(duì)列中刪除一個(gè)元素，再參與兩個(gè)元素后，rear和front的值分別為。

A.1和5B.2和4C.4和2D.5和18.判定一個(gè)循環(huán)隊(duì)列QU（最多元素為m0）為滿隊(duì)列的條件是。

A.QU->front==QU->rearB.QU->front!=QU->rear

C.QU->front==(QU->rear+1)%m0D.QU->front!=(QU->rear+1)%m09.判定一個(gè)循環(huán)隊(duì)列QU（最多元素為m0）為空的條件是。

A.QU->front==QU->rearB.QU->front!=QU->rear

C.QU->front==(QU->rear+1)%m0D.QU->front!=(QU->rear+1)%m0

BCDCCDACA填空題

1．在求表達(dá)式值的