版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
一、單項選擇題
1.C2.D3.B4.C5.D6.C7.B8.C9.A10.B*
11.C12.D13.C14.A15.B16.C17.C18.B19.B20.D
A
二、填空題lA&.n-i+l
△2.n-iA
3.集合線性結構樹形結構圖狀結構A
4.物理結構存儲結構
a5.線性結構非線性結構△
6.有窮性擬定性可形性有零個或多個輸入有零個或多個輸出7AA.圖狀結構A
8.樹形結構
9.線性結構
A10.n—1O(n)A
11.s—>next=p->next;
A12.head13.q—>next=p->next;l"A.p->next=head;A
15.單鏈表
16.順序存儲鏈式存儲
17.存儲結構
A18.兩個直接后繼直接前驅尾結點頭結點AA19.頭結點的指針指向第一個結點的
指針
A20.鏈式鏈表A
A三、問答題
1.簡述數(shù)據(jù)的邏輯結構和存儲結構的區(qū)別與聯(lián)系,它們如何影響算法的設計與實現(xiàn)?
答:若用結點表達某個數(shù)據(jù)元素,則結點與結點之間的邏輯關系就稱為數(shù)據(jù)的邏輯結構。數(shù)
據(jù)在計算機中的存儲表達稱為數(shù)據(jù)的存儲結構??梢姡瑪?shù)據(jù)的邏輯結構是反映數(shù)據(jù)之間的固
有關系,而數(shù)據(jù)的存儲結構是數(shù)據(jù)在計算機中的存儲表達。盡管因采用的存儲結構不同,邏
輯上相鄰的結點,其物理地址未必相同,但可通過結點的內部信息,找到其相鄰的結點,從
而保存了邏輯結構的特點。采用的存儲結構不同,對數(shù)據(jù)的操作在靈活性,算法復雜度等方
面差別較大。4
A2.解釋順序存儲結構和鏈式存儲結構的特點,并比較順序存儲結構和鏈式存儲結構的優(yōu)缺
陷。
A答:4順序結構存儲時,相鄰數(shù)據(jù)元素的存放地址也相鄰,即邏輯結構和存儲結構是統(tǒng)一的,,
規(guī)定內存中存儲單元的地址必須是連續(xù)的。八
優(yōu)點:一般情況下,存儲密度大,存儲空間運用率高。
缺陷:(1)在做插入和刪除操作時,需移動大量元素;(2)由于難以估計,必須預先分派較大的
空間,往往使存儲空間不能得到充足運用;⑶表的容量難以擴充。
鏈式結構存儲時,相鄰數(shù)據(jù)元素可隨意存放,所占空間分為兩部分,一部分存放結點值,另一部
分存放表達結點間關系的指針。4優(yōu)點:插入和刪除元素時很方便,使用靈活。
△缺陷:存儲密度小,存儲空間運用率低。
43.什么情況下用順序表比鏈表好?
△答:順序表適于做查找這樣的靜態(tài)操作,鏈表適于做插入和刪除這樣的動態(tài)操作。假如線
性表的變化長度變化不大,且其重要操作是查找,則采用順序表;假如線性表的長度變化較
大,且其重要操作是插入、刪除操作,則采用鏈表。
-4.解釋頭結點、第一個結點(或稱首元結點)、頭指針這三個概念的區(qū)別?
答:A
頭結點是在鏈表的開始結點之前附加的一個結點;第一個結點(或稱首元結點)是鏈表中存
儲第一個數(shù)據(jù)元素的結點;頭指針是指向鏈表中第一個結點(或為頭結點或為首元結點)的指
針。
A5.解釋帶頭結點的單鏈表和不帶頭結點的單鏈表的區(qū)別。A
答:4帶頭結點的單鏈表和不帶頭結點的單鏈表的區(qū)別重要體現(xiàn)在其結構上和算法操作上。
A在結構上,帶頭結點的單鏈表,不管鏈表是否為空,均具有一個頭結點,不帶頭結點的單鏈表
不含頭結點。
A在操作上,帶頭結點的單鏈表的初始化為申請一個頭結點。無論插入或刪除的位置是地第
一個結點還是其他結點,算法環(huán)節(jié)都相同。不帶頭結點的單鏈表,其算法環(huán)節(jié)要分別考慮插
入或刪除的位置是第一個結點還是其他結點。由于兩種情況的算法環(huán)節(jié)不同。4
AAA四、程序填空題
1.A
(l)p->data=N
(2)p->next=NULL3(.*-*)q->next=p
(4)q=P
A
A2.A
(1)head=pAn(2)q=p3(aa)p->next=NULL
(4)p->next=q->next
(5)q—>next=pA
3.AA(i)p=q->nexU
(2)q->next=p->nex
4五、完畢:實驗1一一線性表4根據(jù)實驗規(guī)定(見教材P201-202)認真完畢本實驗,并提交
實驗報告。-
作業(yè)2答案(本部分作業(yè)覆蓋教材第3-5章的內容)
AA一、單項選擇題
1.C2.B3.A4.C5.B6.A7.B8.C9.A10.C
A1l.B12.C13.B14.B15.A16.C17.B18.A19.C20.D
△2l.B22.D23.C24.B25.D26.A27.C28.D29.D30.C31.A32.DAA
A二、填空題4*1.后進先出42.下一個A
3.增1增1A&4.假上溢
5.
A棧是否滿s->top=MAXSIZE-1棧頂指針棧頂相應的數(shù)組元素棧是否空s->top=
-1棧頂元素修改棧頂指針AA6.bceda*
7.終止條件遞歸部分8AA.LU—>front==LU->rear*
9.運算符操作數(shù)ab+c/fde/------A
lO.s—>next=h;
11.h=h->next;A
12.r—>next=s;IAA3.f=f->next;
Al4.字符A
15.順序存儲方式鏈式存儲方改
16.0空格字符的個數(shù)A
17.特殊稀疏A
18.()(())2A
19.((d,e,f))
串長度相等且相應位置的字符相等行下標、列下標、非零元
20.21AA.j(j-1)/2+j22AA.
素偉
三、問答題
1.簡述棧和一般線性表的區(qū)別。A
答:棧是一種先進后出的線性表,棧的插入和刪除操作都只能在棧頂進行,而一般的線性表
可以在線性表的任何位置進行插入和刪除操作。
2.簡述隊列和一般線性表的區(qū)別。AA隊列是一種先進先出的線性表,隊列的插入只能在隊尾
進行,隊列的刪除只能在隊頭進行,而一般的線性表可以在線性表的任何位置進行插入和刪除
操作。AA
3.鏈棧中為什么不設頭結點?-答:由于鏈棧只在鏈頭插入和刪除結點,不也許在鏈表中間插
入和刪除結點,算法實現(xiàn)很簡樸,所以一般不設立頭結點。3
A
4.運用一個棧,則:
*(1)假如輸入序列由A,B,C組成,試給出所有也許的輸出序列和不也許的輸出序列。2(一)
假如輸入序列由A,B,C,D組成,試給出所有也許的輸出序列和不也許的輸出序列。
答:
(1)棧的操作特點是后進先出,因此輸出序列有:"A入,A出,B入,B出,C入C出,輸出序
列為ABC。
A入,A出,B入,C入,C出,B出,輸出序列為ACB。&
A入,B入,B出,A出,C入,C出,輸出序列為BAC。AAA入,B入,B出,C入,C出,A出,輸出
序列為BCAo
A入,B入,C入,C出,B出,A出,輸出序列為CBA。
由A,B,C組成的數(shù)據(jù)項,除上述五個不同的組合外,尚有一個C,A,B組合。但不也許先
把C出棧,再把A出棧,(A不在棧頂位置),最后把B出棧,所以序列CAB不也許由輸入序
列A,B,C通過棧得到。4(2)按照上述方法,也許的輸出序列有:
ABCD,ABDC,ACBD,ACDB,ADCB,BACD,BADC,BCAD,BCDA,BDCA,CBAD,CBDA,
CDBA,DCBAe
△不也許的輸出序列有:
DABC,ADBC,DACB,DBAC,BDAC,DBCA,DCAB,CDAB,CADB,CABD
A
A5.用S表達入棧操作,X表達出棧操作,若元素入棧順序為1234,為了得到1342出棧順序,
相應的S和X操作串是什么?A
答:應是SXSSXSXXo各操作結果如下*
S1入棧
△X1出棧輸出序列:1
&S2入棧
S3入棧
&X3出棧輸出序列:13A
S4入棧
X4出棧輸出序列:134*
X2出棧輸出序列:1342馬
A
6.有5個元素,其入棧順序為:A、B、C、D、E,在各種也許的出棧順序中,以元素C、D
最先的順序有哪兒個?△
答:從題中可知,要使C第一個且D第二個出棧,應是A入棧,B入棧,C入棧,C出棧,D入棧。
之后可以有以下幾種情況:
(1)B出棧,A出棧,E入棧,E出棧,輸出序列為:CDBAE。
(2)B出棧,E入棧,E出棧,A出棧,輸出序列為CDBEA。*
(3)E入棧,E出棧,B出棧,A出棧,輸出序列為CDEBA*
所以也許的順序有:CDBAE,CDBEA,CDEBA
A7.寫出以下運算式的后綴算術運算工6
(1)3x2+x-l/x+5
A(2)(A+B)*C-D/(E+F)+G
A答;相應的后綴算術運算式AA⑴3X2A*X+1X/-5+AA⑵AB+C*DEF+/-G2A
簡述廣義表和線性表的區(qū)別和聯(lián)系。A
答:廣義表是線性表的的推廣,它也是n(n>0)個元素al,a2...ai...an的有限序列,其中ai或者
是原子或者是一個廣義表。所以,廣義表是一種遞歸數(shù)據(jù)結構,而線性表沒有這種特性,線
性表可以當作廣義表的特殊情況,當ai都是原子時,廣義表退化成線性表。
八四、程序填空題A
1.A
(1)q—>front->next=p->next;
A(2)free(p)泠
(3)q->rear=q->front
五、綜合題
ALA
答:出隊序列是e2,e4,e3,e6,e5,e1的過程:心⑴el入棧(棧底到棧頂元素是el)AA⑵
e2入棧(棧底到棧頂元素是el,e2)A
⑶e2出棧(棧底到棧頂元素是e1)
(4)e3入棧(棧底到棧頂元素是el,e3)4⑸e4入棧(棧底到棧頂元素是el,e3,e4)
A
(6)e4出棧(棧底到棧頂元素是el,e3)
⑺e3出棧(棧底到棧頂元素是e1^(8)e5入棧(棧底到棧頂元素是el,e5)4⑼e6入
棧(棧底到棧頂元素是el,e5,e6)
A⑩e6出棧(棧底到棧頂元素是el,e5)
(IDe5出棧(棧底到棧頂元素是el)
A(12)el出棧(棧底到棧頂元素是空)
△棧中最多時有3個元素,所以棧S的容量至少是3。
2.4算法設計如下:4/*只有一個指針rear的鏈式隊的基本操作*/
A#include<stdio,h>*Atypedefcharelemtype;AAstructnode/*定義鏈隊列結
點*/
乂
△elemtypedata;
structnode*next;^A};A
typedefstruetqueue/*定義鏈隊列數(shù)據(jù)類型*/4{
Astructnode*rear;A
}LinkQueue;A
AAvoidinitqueue(LinkQueue*Q)/*初始化隊列*/—{
Q=(structqueue*)malloc(sizeof(structqueue))戶
Q->rear=NULL;
AAVoidenqueue(LinkQueue*Q,elemtypex)/*入隊算法*/
{A
structnode*s,*p;A
s=(structnode*)malloc(sizeof(structnode));AAs->data=x;a
if(Q->rear==NULL)/*原為空隊時57A
(
AQ—>rear=s;AAs->next=s;
A}
else/*原隊不為空時*/
(
Ap=Q->rear->next;/*p指向第一個結點*/
AQ-Arear->next=s;/*將s鏈接到隊尾*/
Q->rear=s;/*Q->rear指向隊尾*A
s—>next=p;AA}AA}
AAAVOiddelqueue(LinkQueue*Q)/*出隊算法*/
structnode*t;AAif(Q->rear==NULL)A{AA
Printf(H隊列為空!\n”);
Areturn(0);AA}
△elseif(Q->rear->next==Q->reaij/*只有一個結點時*/A
9
t=Q->rear;
AQ—>rear=NULL;
A}AAelse/*
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024年玻璃制光學元件項目發(fā)展計劃
- 2024年新能源掃路車項目合作計劃書
- 2024年異佛爾酮項目發(fā)展計劃
- 航空服務居間代理提成協(xié)議
- 2024版?zhèn)€人代理人保險代理合同書
- 2024版飛行培訓及雇傭意向合同書
- 汽車制造機械配送合同樣本
- 2024版合同編典型合同保證合同
- 2024版國際貨物買賣合同
- 民俗村裝修國家合同
- 保安公司掛靠合同模板
- 2024-2030年中國污泥處理行業(yè)發(fā)展分析及發(fā)展前景與趨勢預測研究報告
- 2024年中級注冊安全工程師《安全生產(chǎn)專業(yè)實務(道路運輸安全)》真題及答案
- 行長招聘面試題與參考回答(某大型集團公司)
- 2024年外研版英語小學四年級上冊期中檢測題附答案
- 河南省洛陽市2023-2024學年七年級上學期期中考試數(shù)學試卷(含答案)
- 三年級上冊道德與法治第8課《安全記心上》教案教學設計(第一課時)
- 演講學智慧樹知到答案2024年同濟大學
- GB/T 44405-2024工業(yè)互聯(lián)網(wǎng)平臺服務商評價方法
- (完整版)模擬電子技術測試試題及答案
- 2024年4月自考財務管理學試卷真題解析
評論
0/150
提交評論