版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
數(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)于線性表的說法不正確的是()。
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),試的答案中選擇合適的語句序列,實(shí)現(xiàn)刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列是⑥①⑨。
①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)無前驅(qū)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)。
10.單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)表示。
11.棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表。
12.在棧頂指針為HS的鏈棧中,判定??盏臈l件是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依次通過棧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)單鏈表中,既無頭結(jié)點(diǎn)也無頭指針,p為指向該鏈表中某個(gè)結(jié)點(diǎn)的指一個(gè)刪除該結(jié)點(diǎn)直接前驅(qū)結(jié)點(diǎn)的算法。
voiddelete(LinkListp)
{
//在一個(gè)既無頭結(jié)點(diǎn)也無頭指針的長(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ù)且無序,寫算法按遞增順序打印鏈表方法是:反復(fù)找出鏈表中最小的元素,打印并刪除之,直至表空為止。
3.voidrearrange(LinkList&la){
//將頭指針是la的單鏈表按遞增順序打印出來
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ǔ)空
間仍占用原來的鏈表。
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之間的元素逆置,
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 領(lǐng)導(dǎo)力與管理技能培訓(xùn)
- 低溫多效海水淡化裝置相關(guān)行業(yè)投資規(guī)劃報(bào)告
- 如何制定靈活的生產(chǎn)安排計(jì)劃
- 餐廳員工職業(yè)發(fā)展計(jì)劃培訓(xùn)
- 2024-2025學(xué)年年八年級(jí)數(shù)學(xué)人教版下冊(cè)專題整合復(fù)習(xí)卷第21章 二次根式 荔灣區(qū)金道中學(xué)單元檢測(cè)AB卷(含答案)
- 8物北師期末阜陽市臨泉縣2023-2024學(xué)年八年級(jí)上學(xué)期期末考試物理試題
- 《數(shù)字影像特征匹配》課件
- 文明科室評(píng)選報(bào)告范文
- 企業(yè)動(dòng)態(tài)報(bào)告范文
- 應(yīng)用文報(bào)告的范文
- 無極繩絞車司機(jī)培訓(xùn)課件
- 【培訓(xùn)課件】5S培訓(xùn)課程講義
- 軀體移動(dòng)障礙的護(hù)理措施
- 初中物理基于新課程標(biāo)準(zhǔn)的教-學(xué)-評(píng)價(jià)一體化設(shè)計(jì)
- 第10章-氫發(fā)動(dòng)機(jī)
- 2024年初級(jí)經(jīng)濟(jì)師考試初級(jí)經(jīng)濟(jì)基礎(chǔ)真題及答案
- 寵物鮮食品牌設(shè)計(jì)開題報(bào)告
- 貴州省黔東南州2023-2024學(xué)年九年級(jí)上學(xué)期期末道德與法治試題
- 徽派建筑賞析(宏村)
- 新課標(biāo)下小學(xué)高年級(jí)數(shù)學(xué)核心素養(yǎng)培養(yǎng)實(shí)踐
- 外聯(lián)專員-開展對(duì)外合作與資源拓展的工作計(jì)劃
評(píng)論
0/150
提交評(píng)論