数据结构课堂习题1.doc

《数据结构课堂习题1.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章绪论1.8设n为正整数。试确定下列各程序段中前置以记号@的语句的频度：(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+j

2、<=n){@if(i>j)j++;elsei++;}(7)x=n;y=0;//n是不小于1的常数while(x>=(y+1)*(y+1)){@y++;}(8)x=91;y=100;while(y>0){@if(x>100){x-=10;y--;}elsex++;}解：(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假设n为2的乘幂，并且n>2，试求下列算法的时间复杂度及变量count的值（以n的函数形式表示）。intTime(i

3、ntn){count=0;x=2;while(x

4、解：voidprint_descending(intx,inty,intz)//按从大到小顺序输出三个数{scanf("%d,%d,%d",&x,&y,&z);if(xy;//<->为表示交换的双目运算符,以下同if(yz;if(xy;//冒泡排序printf("%d%d%d",x,y,z);}//print_descending第2章线性表2.2填空题。解：(1)在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。(2)顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物

5、理位置不一定紧邻。(3)在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。(4)在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。2.4对以下单链表分别执行下列各程序段，并画出结果示意图。解：2.5画出执行下列各行语句后各指针及链表的示意图。L=(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--)I

6、ns_LinkList(L,i+1,i*2);for(i=1;i<=3;i++)Del_LinkList(L,i);解：2.11设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。解：StatusInsert_SqList(SqList&va,intx)//把x插入递增有序表va中{  if(va.length+1>va.listsize)returnERROR;  va.length++;  for(i=va.length-1;va.elem[i]>x&&i>=0;i--)    va.elem[i+1]=va.elem[i];  v

7、a.elem[i+1]=x;  returnOK;}//Insert_SqList2.22试写一算法，对单链表实现就地逆置。voidLinkList_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->n