數(shù)據(jù)結(jié)構(gòu)課堂習題

1、第1章 緒論1.8 設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 假設n為2的乘冪，并且n>2，試求下列算法的時間復雜度及變量count的值（以n的函數(shù)形式表示）。int Time(int n) count = 0;x=2;while(x<n/2) x *= 2;count+;return count;解：count=1.11 已知有實現(xiàn)同一功能的兩個算法，其時間復雜度分別為和，假設現(xiàn)實計算機可連續(xù)運算的時間為秒（100多天），又每秒可執(zhí)行基本操作（根據(jù)這些操作來估算算法時間復雜度）次。試問在此條件下，這兩個算法可解問題的規(guī)模（即n值的范圍）各為多少？哪個算法更適宜？請說明理由。解：n=40 n=16 則對于同樣的循環(huán)次數(shù)n，

4、在這個規(guī)模下，第二種算法所花費的代價要大得多。故在這個規(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; /<->為表示交換的雙目運算符,以下同 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ù)與元素在表中的位置有關。 (2) 順序表中邏輯上相鄰的元素的物理位置必定緊鄰。單鏈表中邏輯上相鄰的元素的物理位置不一定緊鄰。 (3) 在單鏈表中，除了首元結(jié)點外，任一結(jié)點的存儲位置由其前驅(qū)結(jié)點的鏈域的值指示。 (4) 在單鏈表中設置頭結(jié)點的作用是插入和刪除首元結(jié)點時不用進行特殊處理。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 設順序表va中的數(shù)據(jù)元素遞增有序。試寫一算法，將x插入到順序表的適當位置上，以保持該表的有序性。解：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 試寫一算法，對單鏈表實

8、現(xiàn)就地逆置。void LinkList_reverse(Linklist &L)/鏈表的就地逆置;為簡化算法,假設表長大于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的當前元素q插入新的鏈表頭部,p為新表表頭. 第3章 棧和隊列3.1 若按教科書3.1.1節(jié)中圖3.1(b)所示鐵道進行車廂調(diào)度（注意：兩側(cè)鐵道均為單向行駛道），則請回答：(1) 如果進站的車廂序列為123，則可能得到的出站車廂序列是什么？(2) 如果進站的車廂序列為123456，則能否得到435612和135426的出站序列，并請說明為什么不能得到或者如何得到（即寫出以 S表示進棧和以 X表示出棧的棧操作序列）。解：(1) 123 231 321 213 13

10、2 (2) 可以得到135426的出站序列，但不能得到435612的出站序列。因為4356出站說明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é)果（隊列中的元素類型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 簡述以下算法的功能（棧和隊列的元素類型均為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);解：隊列逆置3.18 試寫一個判別表達式中開、閉括號是否配對出現(xiàn)的算法。解：Status Bracket_Test(char *str)/判別表達式中小括號是否匹配  count=0;  for(p=str;*p;p+)      if(*p='(') count+;