第2部分 习题解答.docx
- 文档编号:17233176
- 上传时间:2023-07-23
- 格式:DOCX
- 页数:58
- 大小:303.04KB
第2部分 习题解答.docx
《第2部分 习题解答.docx》由会员分享,可在线阅读,更多相关《第2部分 习题解答.docx(58页珍藏版)》请在冰点文库上搜索。
第2部分习题解答
第2部分习题解答
习题1
1.
参考答案:
数据元素之间的关系在计算机中有四种表示方法:
(1)顺序存储方式。
数据元素顺序存放,每个存储结点只包含一个元素。
存储位置反映数据元素间的逻辑关系。
存储密度较大,但有些操作(如插入、删除)效率较低。
(2)链式存储方式。
每个存储结点除包含数据元素信息外,还包含一组(至少一个)指针。
指针反映数据元素间的逻辑关系。
这种方式不要求存储空间连续,便于动态操作(如插入、删除等),但存储空间开销大(用于指针),另外不能进行二分查找等。
(3)索引存储方式。
除数据元素存储在一个地址连续的内存空间外,尚需建立一个索引表,索引表中索引指示存储结点的存储位置(下标)或存储区间端点(下标),兼有静态和动态特性。
(4)散列存储方式。
通过散列函数和解决冲突的方法,将关键字散列在连续的、有限的地址空间内,这种存储方式称为散列存储。
其特点是存取速度快,只能按关键字随机存取,不能顺序存取,也不能二分存取。
2.
参考答案:
评价好的算法有四个方面:
(1)算法的正确性;
(2)算法的易读性;
(3)算法的健壮性;
(4)算法的时空效率。
3.
参考答案:
(1)算法的时间复杂度是算法所求解问题规模n的函数。
问题规模是算法求解问题的输入量或初始数据量。
有时考虑算法在最坏情况下的时间复杂度或平均时间复杂度。
(2)算法是对特定问题求解步骤的描述,是指令的有限序列,其中每一条指令表示一个或多个操作。
算法具有五个重要特性:
有穷性、确定性、可行性、输入和输出。
(3)在分析算法的时间复杂度时,需要计算语句的执行次数。
一个语句的执行次数称为语句频度。
4.
参考答案:
逻辑结构、存储结构、操作(运算)。
5.
参考答案:
应从两方面进行讨论,若通讯录较少变动(如城市私入电话号码),主要用于查询,以顺序存储较为方便,既能顺序查找也可随机查找;若通讯录经常有增删操作,用链式存储结构较为合适,将每个人的情况作为一个元素(即一个结点存放一个人),把姓名作为关键字,链表安排成有序表,这样可提高查询速度。
6.
参考答案:
将学号、姓名、平均成绩看成一个记录(元素,含三个数据项),将100个这样的记录存于数组中。
因一般无增删操作,故宜采用顺序存储。
typedefstruct
{intnum;/*学号*/
charname[8];/*姓名*/
floatscore;/*平均成绩*/
}node;
nodestudent[100];
7.
参考答案:
(1)n+1
(2)n(3)n(n+3)/2(4)n(n+1)/2
习题2
1.
算法代码:
voidInsert_SqList(SqList*va,intx)/*把x插入递增有序表va中*/
{
inti;
if(va->length>MAXSIZE)return;
for(i=va->length-1;va->data[i]>x&&i>=0;i--)
va->data[i+1]=va->data[i];
va->data[i+1]=x;
va->length++;
}/*Insert_SqList*/
2.
算法代码:
intListComp(SqListA,SqListB)
{
inti;
for(i=1;i<=A.length&&i<=B.length;i++)
if(A.data[i]!
=B.data[i])
returnA.data[i]>B.data[i]?
1:
-1;
if(A.length==B.length)return0;
returnA.length>B.length?
1:
-1;
/*当两个顺序表可以互相比较的部分完全相同时,哪个较长,哪个就较大*/
}/*ListComp*/
3.
算法代码:
voidListConcat(LinkListha,LinkListhb,LinkList*hc){/*把链表hb接在ha后面形成链表hc*/
LinkListp;
*hc=ha;
p=ha;/*由指针p指向ha的尾元结点*/
while(p!
=NULL)p=p->next;
p->next=hb->next;
free(hb);
}/*ListConcat*/
4.
算法代码:
voidInsert(LinkList*L,inti,intb){
LinkListp,new;
new=(LinkList)malloc(sizeof(LNode));
new->data=b;
if(i==1)
{/*插入在链表头部*/
new->next=*L;
*L=new;
}
else
{/*插入在第i个元素的位置*/
p=*L;
while(--i>1)p=p->next;
new->next=p->next;
p->next=new;
}
}/*Insert*/
5.
算法代码:
voidDelete_Between(LinkList*L,intmink,intmaxk){
LinkListp,q;
p=*L;
while(p->next->data<=mink)
p=p->next;/*p是最后一个不大于mink的元素*/
if(p->next)/*如果还有比mink更大的元素*/
{q=p->next;
while(q->data q=q->next;/*q是第一个不小于maxk的元素*/ p->next=q; } }/*Delete_Between*/ 6. 算法代码: voidDelete_Equal(LinkList*L){ LinkListp,q,r; p=(*L)->next; q=p->next;/*p和q指向相邻的两个元素*/ while(p->next){ if(p->data! =q->data)/*若相邻两元素不相等时,p和q都向后推一步*/ { p=p->next; q=p->next; } else{ while(q->data==p->data){/*当相邻元素相等时删除多余元素*/ r=q; q=q->next; free(r); } p->next=q; p=q; q=p->next; }/*else*/ }/*while*/ }/*Delete_Equal*/ 7. 算法代码: voidLinkList_reverse(LinkListL) { LinkListp,q,s; if(! L->next||! L->next->next)return; 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->next=p; s->next=q; L->next=s; }/*LinkList_reverse*/ 8. 算法代码: voidmerge1(LinkListA,LinkListB,LinkList*C) { LinkListp,q,s,t; p=A->next; q=B->next; *C=A; while(p&&q){ s=p->next; p->next=q;/*将B的元素插入*/ if(s){ t=q->next; q->next=s;/*若A非空,将A的元素插入*/ } p=s; q=t;/*指针p和q同时后移*/ }/*while*/ }/*merge1*/ 9. 算法代码: voidreverse_merge(LinkListA,LinkListB,LinkList*C){ LinkListpa,pb,pc,pre,q; pa=A->next; pb=B->next;/*pa和pb分别指向A和B的当前元素*/ pre=NULL; while(pa||pb){ if(pa->data pb)/*将A的元素插入新表*/ {pc=pa;q=pa->next;pa->next=pre;pa=q;} else/*将B的元素插入新表*/ {pc=pb;q=pb->next;pb->next=pre;pb=q;} pre=pc; } *C=A; A->next=pc;/*构造新表头*/ }/*reverse_merge*/ 10. 算法代码: voidSqList_Intersect_Delete(SqList*A,SqListB,SqListC){ inti,j,k,m; intsame; i=0;j=0;k=0;m=0;/*i指示A中元素原来的位置,m为移动后的位置*/ while(i<(*A).length&&j { if(B.data[j] elseif(B.data[j]>C.data[k])k++; else{ same=B.data[j];/*找到了相同元素same*/ while(B.data[j]==same)j++; while(C.data[k]==same)k++;/*j和k后移到新的元素*/ while(i<(*A).length&&(*A).data[i] (*A).data[m++]=(*A).data[i++];/*需保留的元素移动到新位置*/ while(i<(*A).length&&(*A).data[i]==same)i++;/*跳过相同的元素*/ } }/*while*/ while(i<(*A).length) (*A).data[m++]=(*A).data[i++];/*A的剩余元素重新存储*/ (*A).length=m; }/*SqList_Intersect_Delete*/ 习题3 1. 参考答案: 栈是只允许在一端进行插入和删除操作的线性表,允许插入和删除的一端叫栈顶,另一端叫栈底。 最后插入的元素最先删除,故栈也称后进先出表。 队列是允许在一端插入而在另一端删除的线性表,允许插入的一端叫队尾,允许删除的一端叫队头。 最先插入队的元素最先离开(删除),故队列也常称先进先出表。 2. 参考答案: 输入序列为123456,不能得出435612,其理由是,输出序列最后两元素是12,前面4个元素4356得到后,栈中元素剩余12,且2在栈顶,不可能栈底元素1在栈顶元素2之前出栈。 得到135426的过程如下: 1入栈并出栈,得到部分输出序列1;然后2和3入栈,3出栈,部分输出序列变为13;接着4和5入栈,5,4和2依次出栈,部分输出序列变为13542;最后6入栈并退栈,得最终结果135426。 3. 参考答案: 设顺序队列用一维数组Q[m]表示,其中m为队列中元素个数,队列中的元素下标从0到m﹣1。 设队头指针为front,队尾指针是rear,约定front指向队头元素,rear指向队尾元素的下一位置。 当front=rear=0时,表示队空,当rear=m﹣1时,表示队满。 由于队列的性质,在队头进行出队操作,而在队尾进行入队操作,所以当队尾指针rear=m﹣1时,若front不为0,则队列中仍有空闲单元,即队列的实际可用空间并未占满,这时若有入队操作,会造成“假溢出”。 解决“假溢出”的办法有两种,一是将队列元素向前“平移”,占用0至rear-front-1号单元;二是将队列看成一个首尾相接的环状空间,即循环队列。 在循环队列下,当front=rear时,仍表示队空,而表示队满,则有两种办法,一是牺牲一个单元,即(rear+1)%m=front时,表示队满。 另一种方法是设一个标志tag,若tag=0且front=rear时,表示队空;若tag=1且front=rear时,表示队满。 4. 算法代码: voidEnQueue(LinkListrear,ElemTypex) {/*rear是带头结点的循环链队列的尾指针,本算法将元素x插入到队尾*/ LinkLists; s=(LinkList)malloc(sizeof(LNode));/*申请结点空间*/ s->data=x; s->next=rear->next;/*将s结点链入队尾*/ rear->next=s; rear=s;/*rear指向新队尾*/ } voidDeQueue(LinkListrear) {/*rear是带头结点的循环链队列的尾指针,本算法执行出队操作,操作成功输出队头元素;否则给出出错信息*/ LinkLists; if(rear->next==rear){printf("队空\n");return;} s=rear->next->next;/*s指向队头元素*/ rear->next->next=s->next;/*队头元素出队*/ printf("出队元素是: %d",s->data); if(s==rear)rear=rear->next;/*空队列*/ free(s); } 5. 算法代码: intMaxValue(inta[],intn) {/*设整数序列存于数组a中,共有n个,本算法求解其最大值*/ intmax; if(n==1)max=a[1]; elseif(a[n]>MaxValue(a,n-1))max=a[n]; elsemax=MaxValue(a,n-1); return(max); } 6. 算法代码: voidconversion(intN){ SqStacks; intx; Init_SqStack(&s); if(N<0)return; while(N){ Push_SqStack(&s,N%16);/*余数入栈*/ N=N/16;/*商作为被除数继续*/ } while(! Empty_SqStack(&s)) { x=Pop_SqStack(&s); if(x>=10) printf("%c",'A'+x-10); else printf("%d",x); } } 7. 算法代码: voidreverse(SqStack*s){ SqStacks1,s2;/*s,s1,s2均为栈类型*/ ElemTypex;/*栈中元素的类型,用于存储从栈中取出元素的临时变量*/ Init_Stack(&s1);/*栈的初始化*/ Init_Stack(&s2); while(! Empty_Stack(s))/*如果栈不空,将s栈中的内容移到s1栈中*/ { x=Pop_Stack(s);/*取栈顶元素放入变量x中*/ Push_Stack(&s1,x);/*将变量x入栈*/ } while(! Empty_Stack(&s1))/*如果栈不空,将s1栈中的内容移到s2栈中*/ { x=Pop_Stack(&s1); Push_Stack(&s2,x); } while(! Empty_Stack(&s2))/*如果栈不空,将s2栈中的内容移到s栈中*/ { x=Pop_Stack(&s2); Push_Stack(s,x); } } 8. 算法代码: #defineMAXSIZE100/*最大队列长度*/ typedefintElemType; typedefstruct{ ElemTypedata[MAXSIZE];/*队列存储空间*/ intrear;/*尾指针,若队列不空,指向队列尾元素*/ intlength;/*队列中元素的个数*/ }CyQueue; intFullQueue(CyQueue*Q){/*判队满,队中元素个数等于空间大小*/ returnQ->length==MAXSIZE; } voidEnQueue(CyQueue*Q,ElemTypex){/*入队*/ if(FullQueue(Q)){printf("队已满,无法入队");return;} Q->data[Q->rear]=x; Q->rear=(Q->rear+1)%MAXSIZE;/*在循环意义上的加1*/ Q->length++; } ElemTypeDeQueue(CyQueue*Q){/*出队*/ intfront;/*设一个临时队头指针*/ if(Q->length==0) printf("队已空,无元素可出队"); front=(Q->rear+MAXSIZE-Q->length)%MAXSIZE; Q->length--; returnQ->data[front]; } 9. 算法代码: voidInitStack(DuStack*S)/*初始化双向栈*/ { S->top[0]=-1; S->top[1]=STACKSIZE; } intEmptyStack(DuStack*S,inti)/*判栈空(栈号i)*/ {return(i==0&&S->top[0]==-1||i==1&&S->top[1]==STACKSIZE);} intFullStack(DuStack*S)/*判栈满*/ {return(S->top[0]==S->top[1]-1);} voidPush(DuStack*S,inti,ElemTypex)/*进栈(栈号i)*/ { if(FullStack(S))/*若上溢,则退出*/ printf("Stackoverflow"); if(i==0)S->data[++S->top[0]]=x;/*栈0入栈*/ if(i==1)S->data[--S->top[1]]=x;/*栈1入栈*/ } ElemTypePop(DuStack*S,inti)/*出栈(栈号i)*/ { if(EmptyStack(S,i))/*若下溢,则退出*/ printf("Stackunderflow"); if(i==0) return(S->data[S->top[0]--]);/*返回栈顶元素,指针值减1*/ if(i==1) return(S->data[S->top[1]++]);/*该栈是以另一端为底的,所以指针加1*/ } 10. 算法代码: voidsympthy(LinkListhead,intn,SqStack*s)/*长度为n的字符串存于单链表head中*/ { inti=1; LinkListp=head->next; while(i<=n/2)/*前一半字符进栈*/ { Push_Stack(s,p->data); p=p->next; } if(n%2! =0)p=p->next;/*奇数个结点时跳过中心结点*/ while(p&&p->data==Pop_Stack(s))p=p->next; if(p==NULL) printf("链表中心对称"); else printf("链表不是中心对称"); }/*算法结束*/ 11. 算法代码: #defineMAXSIZE100/*最大队列长度*/ typedefintElemType; typedefstruct{ ElemTypedata[MAXSIZE];/*队列存储空间*/ intfront;/*头指针,若队列不空,指向队列头元素*/ intrear;/*尾指针,若队列不空,指向队列尾元素的下一个位置*/ inttag; }CyQueue; voidenqueue(CyQueue*Q,ElemTypex) {/*将x插入循环队列Q中,Q具有队头和队尾指针*/ if((Q->tag==1)&&(Q->rear==Q->front))/*判断队满*/ printf("queueisfull! \n"); else { Q->data[Q->rear]=x; Q->rear=(Q->rear+1)%MAXSIZE; } if(Q->front==Q->rear)Q->tag=1; } ElemTypedequeue(CyQueue*Q)/*删除队列Q的队头元素,并返回该元素*/ { ElemTypex; if((Q->tag==0)&&(Q->rear==Q->front)) printf("queueisempty! \n");/*判断队空*/ else { Q->front=(Q->front+1)%MAXSIZE; x=Q->data[Q->front]; } if(Q->front==Q->rear)Q->tag=0; returnx; } 习题4 1. 参考答案: 空格是一个字符,其ASCII码值是32。 空格串是由空格组成的串,其长度等于空格的个数。 空串是不含任何字符的串,即空串的长度是零。 2. 参考答案: 设数组元素A[i][j]存放在起始地址为Loc(i,j)的存储单元中。 Loc(2,2)=Loc(0,0)+2*n+2=644+2*n+2=676 n=(676-2-644)/2=15 Loc(3,3)=Loc(0,0)+3*15+3=644+45+3=692 3. 参考答案: (1)数组B共有1+2+3++n=(n+1)*n/2个元素。 (2)只存下三角部分时,若i≥j,则数组元素A[i][j]前面有i﹣1行(1~i﹣1),第1行有1个元素,第2行有2个元素,,第i﹣1行有i﹣1个元素。 在第i行中,第j号元素排在第j个元素位置,因此,数组元素A[i][j]在数组B中的存放位置为: 1+2++(i﹣1)+j=(i﹣1)*i/
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第2部分 习题解答 部分 习题 解答
![提示](https://static.bingdoc.com/images/bang_tan.gif)