




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、第1章 緒論1.8 設(shè)n為正整數(shù)。試確定下列各程序段中前置以記號的語句的頻度:(1) i=1; k=0; while(i<=n-1) k += 10*i; i+; (2) i=1; k=0; do k += 10*i; i+; while(i<=n-1);(3) i=1; k=0; while (i<=n-1) i+; k += 10*i; (4) k=0; for(i=1; i<=n; i+) for(j=i; j<=n; j+) k+; (5) for(i=1; i<=n; i+) for(j=1; j<=i; j+) for(k=1; k<
2、=j; k+) x += delta; (6) i=1; j=0; while(i+j<=n) if(i>j) j+; else i+; (7) x=n; y=0; / n是不小于1的常數(shù) while(x>=(y+1)*(y+1) y+; (8) x=91; y=100; while(y>0) if(x>100) x -= 10; y-; else x+; 解:(1) n-1 (2) n-1 (3) n-1 (4) n+(n-1)+(n-2)+.+1= (5) 1+(1+2)+(1+2+3)+.+(1+2+3+.+n)= = = (6) n (7) 向下取整 (8
3、) 11001.9 假設(shè)n為2的乘冪,并且n>2,試求下列算法的時間復(fù)雜度及變量count的值(以n的函數(shù)形式表示)。int Time(int n) count = 0;x=2;while(x<n/2) x *= 2;count+;return count;解:count=1.11 已知有實(shí)現(xiàn)同一功能的兩個算法,其時間復(fù)雜度分別為和,假設(shè)現(xiàn)實(shí)計(jì)算機(jī)可連續(xù)運(yùn)算的時間為秒(100多天),又每秒可執(zhí)行基本操作(根據(jù)這些操作來估算算法時間復(fù)雜度)次。試問在此條件下,這兩個算法可解問題的規(guī)模(即n值的范圍)各為多少?哪個算法更適宜?請說明理由。解:n=40 n=16 則對于同樣的循環(huán)次數(shù)n,
4、在這個規(guī)模下,第二種算法所花費(fèi)的代價要大得多。故在這個規(guī)模下,第一種算法更適宜。1.16 試寫一算法,自大至小依次輸出順序讀入的三個整數(shù)X,Y和Z的值解:void print_descending(int x,int y,int z)/按從大到小順序輸出三個數(shù) scanf("%d,%d,%d",&x,&y,&z); if(x<y) x<->y; /<->為表示交換的雙目運(yùn)算符,以下同 if(y<z) y<->z; if(x<y) x<->y; /冒泡排序 printf("%d
5、 %d %d",x,y,z);/print_descending 第2章 線性表2.2 填空題。解:(1) 在順序表中插入或刪除一個元素,需要平均移動表中一半元素,具體移動的元素個數(shù)與元素在表中的位置有關(guān)。 (2) 順序表中邏輯上相鄰的元素的物理位置必定緊鄰。單鏈表中邏輯上相鄰的元素的物理位置不一定緊鄰。 (3) 在單鏈表中,除了首元結(jié)點(diǎn)外,任一結(jié)點(diǎn)的存儲位置由其前驅(qū)結(jié)點(diǎn)的鏈域的值指示。 (4) 在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是插入和刪除首元結(jié)點(diǎn)時不用進(jìn)行特殊處理。2.4 對以下單鏈表分別執(zhí)行下列各程序段,并畫出結(jié)果示意圖。解: 2.5 畫出執(zhí)行下列各行語句后各指針及鏈表的示意圖。L=(
6、LinkList)malloc(sizeof(LNode);P=L;for(i=1;i<=4;i+)P->next=(LinkList)malloc(sizeof(LNode);P=P->next;P->data=i*2-1;P->next=NULL;for(i=4;i>=1;i-) Ins_LinkList(L,i+1,i*2);for(i=1;i<=3;i+) Del_LinkList(L,i);解:2.11 設(shè)順序表va中的數(shù)據(jù)元素遞增有序。試寫一算法,將x插入到順序表的適當(dāng)位置上,以保持該表的有序性。解:Status Insert_SqList
7、(SqList &va,int x)/把x插入遞增有序表va中 if(va.length+1>va.listsize) return ERROR; va.length+; for(i=va.length-1;va.elemi>x&&i>=0;i-) va.elemi+1=va.elemi; va.elemi+1=x; return OK;/Insert_SqList 2.22 試寫一算法,對單鏈表實(shí)
8、現(xiàn)就地逆置。void LinkList_reverse(Linklist &L)/鏈表的就地逆置;為簡化算法,假設(shè)表長大于2 p=L->next;q=p->next;s=q->next;p->next=NULL; while(s->next) q->next=p;p=q; q=s;s=s->next; /把L的元素逐個插入新表表頭 q->
9、;next=p;s->next=q;L->next=s;/LinkList_reverse分析:本算法的思想是,逐個地把L的當(dāng)前元素q插入新的鏈表頭部,p為新表表頭. 第3章 棧和隊(duì)列3.1 若按教科書3.1.1節(jié)中圖3.1(b)所示鐵道進(jìn)行車廂調(diào)度(注意:兩側(cè)鐵道均為單向行駛道),則請回答:(1) 如果進(jìn)站的車廂序列為123,則可能得到的出站車廂序列是什么?(2) 如果進(jìn)站的車廂序列為123456,則能否得到435612和135426的出站序列,并請說明為什么不能得到或者如何得到(即寫出以 S表示進(jìn)棧和以 X表示出棧的棧操作序列)。解:(1) 123 231 321 213 13
10、2 (2) 可以得到135426的出站序列,但不能得到435612的出站序列。因?yàn)?356出站說明12已經(jīng)在棧中,1不可能先于2出棧。3.3 寫出下列程序段的輸出結(jié)果(棧的元素類型SElemType為char)。void main()Stack S;char x,y;InitStack(S);x= c; y= k;Push(S,x);Push(S, a);Push(S,y);Pop(S,x);Push(S, t);Push(S,x);Pop(S,x);Push(S, s);while(!StackEmpty(S) Pop(S,y); printf(y); printf(x);解:stack3.
11、4 簡述以下算法的功能(棧的元素類型SElemType為int)。(1) status algo1(Stack S) int i,n,A255;n=0;while(!StackEmpty(S) n+; Pop(S,An); for(i=1;i<=n;i+) Push(S,Ai);(2) status algo2(Stack S,int e)Stack T; int d;InitStack(T);while(!StackEmpty(S)Pop(S,d);if(d!=e) Push(T,d);while(!StackEmpty(T)Pop(T,d);Push(S,d);解:(1) 棧中的數(shù)據(jù)
12、元素逆置 (2) 如果棧中存在元素e,將其從棧中清除3.12 寫出以下程序段的輸出結(jié)果(隊(duì)列中的元素類型QElemType為char)。void main()Queue Q;InitQueue(Q);char x= e, y= c;EnQueue(Q, h);EnQueue(Q, r);EnQueue(Q, y);DeQueue(Q, x);EnQueue(Q, x);DeQueue(Q, x);EnQueue(Q, a);While(!QueueEmpty(Q)DeQueue(Q,y);printf(y);printf(x);解:char3.13 簡述以下算法的功能(棧和隊(duì)列的元素類型均為i
13、nt)。 void algo3(Queue &Q)Stack S;int d;InitStack(S);while(!QueueEmpty(Q)DeQueue(Q, d);Push(S, d);while(!StackEmpty(S)Pop(S, d);EnQueue(Q, d);解:隊(duì)列逆置3.18 試寫一個判別表達(dá)式中開、閉括號是否配對出現(xiàn)的算法。解:Status Bracket_Test(char *str)/判別表達(dá)式中小括號是否匹配 count=0; for(p=str;*p;p+) if(*p='(') count+;
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 【正版授權(quán)】 ISO 24566-2:2024 EN Drinking water,wastewater and stormwater systems and services - Adaptation of water services to climate change impacts - Part 2: Stormwater services
- 【正版授權(quán)】 ISO 10218-1:2025 EN Robotics - Safety requirements - Part 1: Industrial robots
- 2025年鄉(xiāng)村振興工作計(jì)劃
- 2025年度二手車品牌代理居間合同
- 2025年度船舶制造用粘結(jié)劑材料采購合同
- 2025年激光影像輸出膠片項(xiàng)目建議書
- 醫(yī)療設(shè)備培訓(xùn)工作的總體回顧計(jì)劃
- 企業(yè)如何通過品牌塑造競爭優(yōu)勢計(jì)劃
- 如何有效評估品牌的市場定位計(jì)劃
- 激發(fā)幼兒學(xué)習(xí)興趣的方式計(jì)劃
- 2024年《公務(wù)員法》相關(guān)法律法規(guī)知識考試題庫含完整答案(必刷)
- 手術(shù)室氣體的使用
- 學(xué)習(xí)解讀2024年新制定的學(xué)位法課件
- 數(shù)字證書使用承諾函
- 運(yùn)河古街項(xiàng)目招商規(guī)劃方案
- 汽車銷售經(jīng)理年終總結(jié)
- 《社區(qū)康復(fù)》課件-第十章 養(yǎng)老社區(qū)康復(fù)實(shí)踐
- 《社區(qū)康復(fù)》課件-第八章 視力障礙患者的社區(qū)康復(fù)實(shí)踐
- 透析患者的血糖管理
- 漢堡王行業(yè)分析
- 肝硬化“一病一品”
評論
0/150
提交評論