數(shù)據(jù)結(jié)構(gòu)課堂習(xí)題1.doc

第1章 緒論1.8 設(shè)n為正整數(shù)。試確定下列各程序段中前置以記號(hào)的語句的頻度：(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=j; k+) x += delta; (6) i=1; j=0; while(i+jj) j+; else i+; (7) x=n; y=0; / n是不小于1的常數(shù) while(x=(y+1)*(y+1) y+; (8) x=91; y=100; while(y0) if(x100) 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) 11001.9 假設(shè)n為2的乘冪，并且n2，試求下列算法的時(shí)間復(fù)雜度及變量count的值（以n的函數(shù)形式表示）。int Time(int n) count = 0;x=2;while(xn/2) x *= 2;count+;return count;解：count=1.11 已知有實(shí)現(xiàn)同一功能的兩個(gè)算法，其時(shí)間復(fù)雜度分別為和，假設(shè)現(xiàn)實(shí)計(jì)算機(jī)可連續(xù)運(yùn)算的時(shí)間為秒（100多天），又每秒可執(zhí)行基本操作（根據(jù)這些操作來估算算法時(shí)間復(fù)雜度）次。試問在此條件下，這兩個(gè)算法可解問題的規(guī)模（即n值的范圍）各為多少？哪個(gè)算法更適宜？請(qǐng)說明理由。解：n=40 n=16 則對(duì)于同樣的循環(huán)次數(shù)n，在這個(gè)規(guī)模下，第二種算法所花費(fèi)的代價(jià)要大得多。故在這個(gè)規(guī)模下，第一種算法更適宜。1.16 試寫一算法，自大至小依次輸出順序讀入的三個(gè)整數(shù)X，Y和Z的值解：void print_descending(int x,int y,int z)/按從大到小順序輸出三個(gè)數(shù) scanf(%d,%d,%d,&x,&y,&z); if(xy) xy; /為表示交換的雙目運(yùn)算符,以下同 if(yz) yz; if(xy) xy; /冒泡排序 printf(%d %d %d,x,y,z);/print_descending 第2章 線性表2.2 填空題。解：(1) 在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)表中一半元素，具體移動(dòng)的元素個(gè)數(shù)與元素在表中的位置有關(guān)。 (2) 順序表中邏輯上相鄰的元素的物理位置必定緊鄰。單鏈表中邏輯上相鄰的元素的物理位置不一定緊鄰。 (3) 在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由其前驅(qū)結(jié)點(diǎn)的鏈域的值指示。 (4) 在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是插入和刪除首元結(jié)點(diǎn)時(shí)不用進(jìn)行特殊處理。2.4 對(duì)以下單鏈表分別執(zhí)行下列各程序段，并畫出結(jié)果示意圖。解： 2.5 畫出執(zhí)行下列各行語句后各指針及鏈表的示意圖。L=(LinkList)malloc(sizeof(LNode);P=L;for(i=1;inext=(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;iva.listsize) return ERROR;va.length+;for(i=va.length-1;va.elemix&i=0;i-)va.elemi+1=va.elemi;va.elemi+1=x;return OK;/Insert_SqList 2.22 試寫一算法，對(duì)單鏈表實(shí)現(xiàn)就地逆置。void LinkList_reverse(Linklist &L)/鏈表的就地逆置;為簡(jiǎn)化算法,假設(shè)表長大于2p=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的元素逐個(gè)插入新表表頭q-next=p;s-next=q;L-next=s;/LinkList_reverse分析:本算法的思想是,逐個(gè)地把L的當(dāng)前元素q插入新的鏈表頭部,p為新表表頭. 第3章 棧和隊(duì)列3.1 若按教科書3.1.1節(jié)中圖3.1(b)所示鐵道進(jìn)行車廂調(diào)度（注意：兩側(cè)鐵道均為單向行駛道），則請(qǐng)回答：(1) 如果進(jìn)站的車廂序列為123，則可能得到的出站車廂序列是什么？(2) 如果進(jìn)站的車廂序列為123456，則能否得到435612和135426的出站序列，并請(qǐng)說明為什么不能得到或者如何得到（即寫出以 S表示進(jìn)棧和以 X表示出棧的棧操作序列）。解：(1) 123 231 321 213 132 (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.4 簡(jiǎn)述以下算法的功能（棧的元素類型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ù)元素逆置 (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 簡(jiǎn)述以下算法的功能（棧和隊(duì)列的元素類型均為int）。 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 試寫一個(gè)判別表達(dá)式中開、閉括號(hào)是否配對(duì)出現(xiàn)的算法。解：