數(shù)據(jù)結(jié)構(gòu)期末考試試題及復(fù)習(xí)資料

數(shù)據(jù)結(jié)構(gòu)期末考試試題及答案

一、選擇題

1.評(píng)價(jià)一個(gè)算法時(shí)間性能的主要標(biāo)準(zhǔn)是()。

A、算法易于調(diào)試

B、算法易于理解

C、算法的穩(wěn)定性和正確性

D、算法的時(shí)間復(fù)雜度

2.計(jì)算機(jī)算法具備有輸入、輸出、（）等五個(gè)特性。

A、可行性、可移植性和可擴(kuò)充性

B、可行性、確定性和有窮性

C、確定性、有窮性和穩(wěn)定性

D、易讀性、穩(wěn)定性和安全性

3.帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（）。

A、head==NULL

B、head->next==NULL

C、head->next==head

D、head！=NULL

4.以下關(guān)于線性表的說(shuō)法不正確的是()。

A、線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型。

B、線性表中包含的數(shù)據(jù)元素個(gè)數(shù)不是任意的。

C、線性表中的每個(gè)結(jié)點(diǎn)都有且只有一個(gè)直接前趨和直接后繼。

D、存在這樣的線性表：表中各結(jié)點(diǎn)都沒有直接前趨和直接后繼。

5.在順序表中，只要知道()，就可在相同時(shí)間內(nèi)求出任一結(jié)點(diǎn)的存儲(chǔ)地址。

A、基地址

B、結(jié)點(diǎn)大小

C、向量大小

D、基地址和結(jié)點(diǎn)大小

6.()運(yùn)算中，使用順序表比鏈表好。

A、插入

B、刪除

C、根據(jù)序號(hào)查找

D、根據(jù)元素值查找

7.一個(gè)長(zhǎng)度為n的順序表中，向第i個(gè)元素之前插入一個(gè)新元素時(shí)，需要向后移動(dòng)（）個(gè)元

A、n-i

B、n-i+1

C、n-i-1

D、i

8.()適合作為經(jīng)常在首尾兩端操作線性表的存儲(chǔ)結(jié)構(gòu)。

A、順序表

B、單鏈表

C、循環(huán)鏈表

D、雙向鏈表

9.棧和隊(duì)列的共同點(diǎn)是()

A、都是先進(jìn)后出

B、都是先進(jìn)先出

C、只允許在端點(diǎn)處插入和刪除元素

D、沒有共同點(diǎn)

10.一個(gè)隊(duì)列的入列序列是1234，則隊(duì)列的輸出序列是()。

A、4321

B、1234

C、1432

D、3241

11.隊(duì)列與一般的線性表的區(qū)別在于()。

A、數(shù)據(jù)元素的類型不同

B、運(yùn)算是否受限制

C、數(shù)據(jù)元素的個(gè)數(shù)不同

D、邏輯結(jié)構(gòu)不同

12.“假上溢”現(xiàn)象會(huì)出現(xiàn)在()中。

A、循環(huán)隊(duì)列

B、隊(duì)列

C、鏈隊(duì)列

D、順序隊(duì)列

⑦P=L;

二、填空題

1．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)被分為集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖結(jié)構(gòu)。

2．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)被分為集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)。

3．下面程序段的時(shí)間復(fù)雜度是O（n）。

i=s=0;

while(s<n)

{i++;

s++;;

}

4．樹型結(jié)構(gòu)和圖形結(jié)構(gòu)合稱是非線性結(jié)構(gòu)。

5．在長(zhǎng)度為n的順序存儲(chǔ)線性表的第i個(gè)元素（1≤i≤n）之前插入一個(gè)元素時(shí)，

需要向后移動(dòng)n-i+1個(gè)元素。

6．在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線性表中，刪除第i個(gè)元素（1≤i≤n）時(shí)，

需要向前移動(dòng)n-i個(gè)元素。

7．指針p指向非空循環(huán)單鏈表head的尾結(jié)點(diǎn)，則p滿足p->next=head。

8．已知L是帶頭結(jié)點(diǎn)的非空單鏈表，且P結(jié)點(diǎn)既不是第一個(gè)數(shù)據(jù)結(jié)點(diǎn)，也不是最后一個(gè)結(jié)點(diǎn)，試的答案中選擇合適的語(yǔ)句序列，實(shí)現(xiàn)刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語(yǔ)句序列是⑥①⑨。

①P->next=P->next->next;

②P=P->next->next;

③while(P->next!=Q)P=P->next;

④while(P->next->next=Q)P=P->next;

⑤Q=P;

⑥Q=P->next;

⑧L=L->next;

⑨free(Q);

9．在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)無(wú)前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)。

10．單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)表示。

11．棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表。

12．在棧頂指針為HS的鏈棧中，判定棧空的條件是HS=NULL。

13．假設(shè)以S和X分別表示進(jìn)棧和退棧操作，則對(duì)輸入序列a、b、c、d、e進(jìn)行一系列棧操作SS后，得到的輸出序列為bceda。

14．設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素a、b、c、d、e、f依次通過(guò)棧S，一個(gè)元素出棧后即若這6個(gè)元素出隊(duì)列的順序是b、d、c、f、e、a，則棧S的容量至少應(yīng)該是3。

三、算法填空

1．已知一個(gè)順序表中的元素按關(guān)鍵字值非遞減有序，下列算法刪除順序表中關(guān)鍵字相同的多余元關(guān)鍵字不同的元素在表中只保留一個(gè)。

voidpurge_sq(SqList&la)

{

//刪除順序表la中關(guān)鍵字相同的多余元素，即使操作之后的順序表中只保留操作之前表中所有按不相同的元素

k=-1;//k指示新表的表尾

for(i=0;i<La.length;++i)//順序考察表中每個(gè)元素

{j=0;

while(j<=k&&la.elem[j]!=la.elem[i])

++j;//在新表中查詢是否存在和la.elem[i]相同的元素

if(k==-1||j>k)//k=-1表明當(dāng)前考察的是第一個(gè)元素

la.elem[++k]=la.elem[i];

}//for

la.length=k+1;//修改表長(zhǎng)

}//purge_sq

2．一個(gè)頭指針為head的單鏈表，其中每個(gè)結(jié)點(diǎn)存放一個(gè)整數(shù)，以下算法將其拆分為兩個(gè)單鏈表hea使head1中僅含有正整數(shù)，head2中僅含有負(fù)整數(shù)。

voidseparate(LinkList&head,LinkList&head1,LinkList&head2)

{

//將頭指針為head的單鏈表（帶頭結(jié)點(diǎn)）拆分為兩個(gè)單鏈表head1和head2，

//使head1中僅含有正整數(shù)，head2中僅含有負(fù)整數(shù)

head1=(LinkList)malloc(sizeof(Lnode));head1->next=NULL;

head2=(LinkList)malloc(sizeof(Lnode));head2->next=NULL;

p=head->next;

while(p)

{q=p->next;

if（p->dat=0）

{p->next=head1->next;

head1->next=p;

}

else{p->next=head2->next;

head2->next=p;

}

p=q;

}//while

free(head);

}//seperate

3．設(shè)一個(gè)長(zhǎng)度大于1的循環(huán)單鏈表中，既無(wú)頭結(jié)點(diǎn)也無(wú)頭指針，p為指向該鏈表中某個(gè)結(jié)點(diǎn)的指一個(gè)刪除該結(jié)點(diǎn)直接前驅(qū)結(jié)點(diǎn)的算法。

voiddelete(LinkListp)

{

//在一個(gè)既無(wú)頭結(jié)點(diǎn)也無(wú)頭指針的長(zhǎng)度大于一的循環(huán)鏈表中，

//刪除指針p所指的某個(gè)結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)

q=p;//查找p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)q

while(q->next!=p)

q=q->next;

r=q;//查找q結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)r

while(r->next!=q)

r=r->next;

r->next=p;

free(q);

}

四、計(jì)算題

1．設(shè)有頭指針為head的單鏈表。寫算法要求在鏈表中查找元素值等于x的結(jié)點(diǎn)，若找到則刪除復(fù)，直至所有值為x的元素全部刪除為止；若一個(gè)也找不到則給出相應(yīng)提示信息。

1．voidelemdelete_x(LinkList&l,ElemTypex)

{

//刪除頭指針為head的單鏈表中（帶頭結(jié)點(diǎn)）所有的值為x的元素

n=0;pre=l;//記下結(jié)點(diǎn)*p的前驅(qū)

p=l->next;

while(p)//順序考察表中每個(gè)元素

{

while(p&&p->data!=x)

{pre=p;p=p->next;}//在表中查詢是否存在和x相同的元素

if(p)//將結(jié)點(diǎn)＊p插入到新的表中

｛pre->next=p->next;

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

n++;

}//if

}//while

if(n==0)printf(“Notfoundx\n”);

}//elemdelete_x

2．有頭指針為head的單鏈表，寫算法在鏈表中查找出所有按先后順序出現(xiàn)的元素x和y，并將的所有結(jié)點(diǎn)全部刪除之。

2．voiddelete(LinkList&head,ElemTypex,ElemTypey)

{

//在頭指針為head的單鏈表中查找出所有按先后順序出現(xiàn)的元素x和y，

//并將x和y之間的所有結(jié)點(diǎn)全部刪除

p=head->next;

while(p){

while(p&&p->data!=x)

p=p->next;

if(!p)exit(1);//沒找到x

r=p->next;

while(r&&r->data!=y)

r=r->next;

if(!r)exit(1);//沒找到相應(yīng)的y

while(p->next!=r)

{q=p-next;

p->next=q->next;

free(q);

}//while

}//while

}

3．設(shè)某個(gè)單鏈表以la為頭指針，鏈表中每個(gè)元素均為整數(shù)且無(wú)序，寫算法按遞增順序打印鏈表方法是：反復(fù)找出鏈表中最小的元素，打印并刪除之，直至表空為止。

3．voidrearrange(LinkList&la){

//將頭指針是la的單鏈表按遞增順序打印出來(lái)

p=la->next;p1=la;

while(p->next!=NULL)

{a=p->data;q1=p;q=p->next;

while(q!=NULL)

{if(a>q->data)

{a=q->data;p1=q1;}//if

q1=q;q=q->next;

}//while

s=p1->next;

printf(s->data);

p1->next=p1->next->next;

free(s);

p1=la;p=la->next;

}//while

printf(p->data);

free(p);free(la);

}//rearrange

4．設(shè)有一個(gè)頭指針為head的單鏈表，每個(gè)結(jié)點(diǎn)存放一個(gè)整數(shù)。寫一算法將其按負(fù)整數(shù)在前部正整數(shù)在后部的次序存放（正整數(shù)與正整數(shù)之間、負(fù)整數(shù)與負(fù)整數(shù)之間不要求有序），存儲(chǔ)空

間仍占用原來(lái)的鏈表。

4．huafen(LinkList&L)

{//L為帶頭結(jié)點(diǎn)的單鏈表的頭指針

p=L->next;

while(p->next)p=p->next;

pt=p;pr=p;p0=L;

p=p0->next;3分

while(p!=pr)

if(p->data>=’0’&&p->data<=’9’)

{p0=p;p=p->next;}

else2分

{p0->next=p->next;

s=p;p=p->next;

pt->next=s;s->next=NULL;

pt=s;

}

}//huafen3分

5．設(shè)有一順序表a，寫算法在表中查找先后出現(xiàn)的元素x和y，將x和y之間的元素逆置，逆置部分不包含x和y。若找不到相應(yīng)的x和y則給出提示信息。

5．voidrevert(ElemType&R[],ints,intt)

{

//本算法將數(shù)組R中下標(biāo)自s到t的元素逆置

//即將（RRRR）改變?yōu)椋≧RRR）

S,s+1,…,t-1,tt,t-1,…,s+1,s

for(k=s;k<=(s+t)/2;k++)

{w=R[k];

R[k]=R[t-k+s];

R[t-k+s]=w;

}//for

}//revert

voidexchange(SqList&a,ElemTypex,ElemTypey)

{

//本算法實(shí)現(xiàn)在順序表a中查找先后出現(xiàn)的元素x和y之間的元素逆置，