14章习题答案DOC.docx
- 文档编号:9402520
- 上传时间:2023-05-18
- 格式:DOCX
- 页数:21
- 大小:58.59KB
14章习题答案DOC.docx
《14章习题答案DOC.docx》由会员分享,可在线阅读,更多相关《14章习题答案DOC.docx(21页珍藏版)》请在冰点文库上搜索。
14章习题答案DOC
一、名词解释(见教材)
数据结构、数据结构的逻辑结构、数据结构的物理结构、算法、算法评价、时间复杂度、大O表示法、线性表、栈、队列、广义表、稀疏矩阵
二、填空
1、数据的逻辑结构被分为_集合结构_、_线性结构___、_树形结构__、__图形结构__4种。
2、数据的存储结构被分为_顺序结构__、链接结构_、索引结构_、和__散列结构__4种。
3、在定义某种数据结构时,其数据域的数据类型可分为简单类型和结构体类型两种,为增强其通用性,应将其再定义为通用数据类型。
4、如果将线性数据结构关系描述为1:
1,那么树型和图型数据结构应分别为1:
N、M:
N。
5、数据结构简单地说是指数据以及相互之间的联系。
6、算法应具备以下5个特性:
有穷性、正确性、可行性、输入和输出。
7、在分析各种算法的时间复杂度时,一般只讨论相应的数量级,用f(n)表示,请问其中n的含义是处理问题的样本量。
8、对于一个单链表,在表头插入结点的时间复杂度为O
(1),在表尾插入元素的时间复杂度为O(n)。
9、在表长为n的顺序表中,在等概率情况下,插入和删除一个元素平均需移动表长的一半(即n/2)个元素,具体移动元素的个数与表长(n)和该元素在表中的位置有关。
10、顺序表的定义如下:
typedefintElemType;
structList{
ElemType*list;
intsize;
intMaxSize;
};
其中ElemType的含义是:
通用数据类型;size的含义是:
顺序表中元素的个数。
11、设单链表中指针p指向结点A,q指针指向其后继结点。
若要删除A的后继结点(假设A存在后继结点),则需修改指针的操作为p->next=q->next;。
12、栈的运算规则为后进先出,队列的运算规则为先进先出。
13、一个函数调用了自身,这是递归调用。
14、非零元素个数远远少于零元素个数的矩阵称为稀疏矩阵。
非零元素所在的行;t的含义是:
非零元素的个数。
三、选择题
1、顺序表物理结构中的存储单元(A)。
A.一定是连续的B.一定是不连续的
C.不一定是连续的D.经删除操作后不连续
2、对一个线性表的存取操作很少,而插入和删除操作较多时应采用B数据结构。
A.线性表B.队列C.图D.树
3、对一个线性表的随机读取操作较多时,应采用B存储结构。
A.静态顺序存储B.动态顺序存储C.动态链接存储D.静态链接存储
4、顺序表适用于(A)的场合。
A.频繁查询B.频繁插入与删除
C.问题规模较小D.问题规模较大
5、链表不具有的特点是(A)。
A.可随机访问任一元素B.插入、删除不需要移动元素
C.不必事先估计存储空间D.所需空间与线性表长度成正比
6、栈的插入和删除操作在(A)进行。
A.栈顶B.栈底C.栈顶或栈底D.任意位置
7、向一个顺序栈S(栈顶指针为top)中插入元素x时,首先要(B)。
A.S->stack[S->top]=x;B.S->top++;
C.S->top--;D.x=S->stack[S->top];
8、对一个顺序存储结构的栈,栈满的判断条件是(D)
A.S.top==-1B.S.top==0
C.S.top==MaxSizeD.S.top==MaxSize-1
9、若循环队列有n个顺序存储单元,front、rear分别为队首和队尾元素的下标,front指向队首元素之前的一个位置,为则判断队满的条件是(C)
A.front==rearB.(front-1)%n==rear
C.(rear+1)%n==frontD.(rear-1)%n==front
10、若循环队列有n个顺序存储单元,front、rear分别为队首和队尾元素的下标,front指向队首元素之前的一个位置,为则判断队空的条件是(A)
A.front==rearB.(front-1)%n==rear
C.(rear+1)%n==frontD.(rear-1)%n==front
11、队的插入操作在(C)进行。
A.队首B.队首或队尾C.队尾D.任意位置
12、下面程序段的时间复杂度为(C)。
for(inti=0;i for(intj=0;j a[i][j]=i*j; A.O(m2)B.O(n2)C.O(m×n)D.O(m+n) 13、一个求从1到正整数n之间所有正整数之和的单循环语句的时间复杂度为(B)。 A.O (1)B.O(n)C.O(n2)D.O(n3) 14、下列是顺序存储线性表排序的算法 voidSort(List&L) { inti,j; ElemTypex; for(i=1;i { x=L.list[i]; for(j=i-1;j>=0;j--) if(x L.list[j+1]=L.list[j]; else break; L.list[j+1]=x; }; } 问: 此算法的时间复杂性为: B A.O(n)B.(n2)C.(n*i)D.(n*j) 15、下面程序段的时间复杂度为(B)。 for(inti=1;i<=n;i++) for(intj=1;j<=n;j++) printf(“%d*%d=%d\n”,i,j,i*j); A.O(n)B.O(n2)C.O (1)B.O(n3) 四、简答题 1、简述数据的逻辑结构和物理结构的关系 答: 数据结构是指数据元素之间逻辑关系的整体,是从具体问题抽象出来的数据模型,有线性结构、树型结构和图型结构三种类型。 物理结构是数据及其逻辑结构在计算机中的表示,分为顺序存储和非顺序存储两种类型。 数据的逻辑结构属于用户视图,是面向问题的,反映了数据内部的构成方式;数据的存储结构属于具体实现的视图,是面向计算机的。 一种数据的逻辑结构可以用多种存储结构来存储,而采用不同的存储结构,其数据处理的效率往往是不同的。 2、叙述顺序表和链表在存储方式、空间占用、读取操作、插入和删除操作等方面的不同; 【答案要点】 1.两者的存储结构不同。 顺序用物理相邻实现逻辑相邻,大多用数组实现,链接存储用链接的方式实现逻辑相邻,物理上不一定相邻; 2.存储相同数量的数据,顺序存储占用空间小,链接存储占用空间大; 3.读取操作: 顺序存储为按元素序号随机访问,效率较高;链接存储为按元素序号顺序访问,效率较低; 4.插入和删除操作: 顺序存储要移动约半数元素,效率较低;链接存储不需移动现有元素,效率较高; 3、举例说明顺序存储的栈在元素出栈和进栈时栈顶指针的变化。 4、说明顺序存储的队列,在解决队满与队空的判断条件时,为什么将队首指针指向第一个元素之前? 这样解决后存储容量有什么变化? 5、用f(n)=n! 为例说明栈与递归算法之间的关系。 答: (参考答案) 要点1: 栈只能在栈顶操作; 要点2: 递归算法是解决一个问题时,是通过解决与它具有相同解法的子问题而得到的; 要点3: 在进行递归调用时,计算机系统自动建立栈,用于存储递归调用参数(下例中的)n和返回地址(下例中的r),进栈; 要点4: 当在一定条件下结束递归调用时,系统按照栈中存储的系数和返回地址逐步返回(出栈)到最初调用处,并得到最终结果。 要点4: 例: 求f(n)=n! f(n)=1n=0 f(n)=n*f(n-1)n>0 当n=3时进栈退栈 n f(n) 0 f(0)=1 1 1 1*f(1-1) 1*1=1 2 2*f(2-1) 2*1=2 3 3*f(3-1) 3*2=6 五、基本要求: 1、写出顺序表定义 2、写出链表结点定义 3、写出堆栈定义 4、写出循环顺序队列定义 5、写出链队定义 六、算法分析 以下有一组算法,请根据各算法的不同,回答不同的问题。 算法1: //利用数组a[]排序 voidsort(inta[],intn) { inti,j,k,t; for(i=0;i { j=i; for(k=i+1;k if(a[k]>a[j])j=k; t=a[i]; a[i]=a[j]; a[j]=t; } } 问题1: 此算法的时间复杂度为: O(n2)。 问题2: 此算法属于: A.。 A.直接选择排序B.直接插入排序 算法2: intFindList(structList*L,ElemTypex) { inti; for(i=0;i if(L->list[i]==x){ x=L->list[i]; returni; } return-1; } 问题1、算法适用的数据结构? 问题2、算法功能? 问题3、算法返回? 问题4、算法有无健壮性? 若有,是哪(些)语句? 问题5、算法的关键语句是哪(些)语句? 问题6、算法的时间复杂度大O()? 算法3: //在链表的表尾插入一个元素 voidInsertLastList(structsNode**HL,ElemTypex) { structsNode*newp; newp=malloc(sizeof(structsNode)); if(newp==NULL) { printf("Memoryallocationfailare! \n"); exit (1); } newp->data=x; newp->next=NULL; if(*HL==NULL) *HL=newp; else{ structsNode*p=*HL; while(p->next! =NULL) p=p->next; p->next=newp; } } 问题1、算法适用的数据结构? 问题2、算法功能? 问题3、算法返回? 问题4、算法有无健壮性? 若有,是哪(些)语句? 问题5、算法的关键语句是哪(些)语句? 问题6、算法的时间复杂度大O()? 算法4: //根据数据结构的类型的定义分析算法 typedefintElemType; structStackSq{ intMaxSize; ElemType*stack; inttop; }; voidPush(structStackSq*S,ElemTypex) { if()againMalloc(S); S->top++; S->stack[S->top]=x; } 问题1: 根据此算法定义的数据结构的类型,此算法的功能是向顺序栈中推入一个元素。 问题2: if语句中的条件应为: B.。 A.S.top==S.MaxSizeB.S.top==S.MaxSize-11 算法5: ElemTypeOutQueue(structQueueSq*Q) { if(Q->front==Q->rear) { printf("Queueisempty! \n"); exit (1); } Q->front=(Q->front+1)%Q->MaxSize; returnQ->queue[Q->front]; } 问题1、算法适用的数据结构? 问题2、算法功能? 问题3、算法返回? 问题4、算法有无健壮性? 若有,是哪(些)语句? 问题5、算法的关键语句是哪(些)语句? 问题6、算法的时间复杂度大O()? 七、分析题 1、有一个顺序存储的栈,最大存储空间MaxSize=5,栈顶指针top,现有A、B、C、D四个元素。 要求1: 写出顺序存储栈结构定义。 要求2: 画出初始化状态。 要求3: 画出以上四个元素依次进栈后的状态。 要求4: 在要求3的基础上,画出三个元素出栈后,又有E、F二个元素进栈,画出队首、队尾指针位置。 要求5: 以下是从栈中删除元素,并将被删除的元素值由函数返回的算法,请填写算法中缺失的语句。 答1: typedefcharElemType; structStack{ ElemType*stack[]; inttop; intMaxSize; }; 答2: 答3: 答4: 答5: ElemTypePop(Stack&S) { if(S.top==-1){ cerr<<"Stackisempty! "< exit (1); } ElemTypetemp=S.stack[S.top]; S.top--; returntemp; } 2、有一个顺序存储的循环队列,最大存储空间为5,假设队首指针指向队首元素的前一个位置,队尾指针指向队尾元素,现队列中已有A、B、C、三个元素。 要求1: 已有顺序存储队列结构的定义,请填写定义中缺失的语句。 要求2: 填写出初始化算法语句。 要求3: 画出经初始化后,以上三个元素依次进队后,队首、队尾指针位置。 要求4: 画出以上三个元素依次出队后,元素D、E依次进队后队首、队尾指针位置。 要求5: 以下是向队列中插入元素的算法,在不考虑扩充空间的前提下,请填写算法中缺失的语句或语句缺失的部分。 答1: TypedefintElemType; structQueue{ intMaxSize; intfront,rear; ElemType*queue; }; 答2: voidInitQueue(Queue&Q) { Q.front=Q.rear=0; } 答3: 答4: 答5: voidQInsert(Queue&Q,constElemType&item) { intk=(Q.rear+1)%QueueMaxSize; if(k==Q.front) { cerr<<"Queueoverflow! "< exit (1); } Q.rear=k; Q.queue[k]=item; } 八、写出下列中缀表达式的后缀表达式和栈的变化,并写出求值过程栈的变化。 1、35+6×(27-6)+6/2 2、16+5×27+8-5×4 3、7×(5+77)/2+6×9 十一、使用栈在计算机语言的编译过程中进行语法检查,只检查C++程序中的花括号、方括号、圆括号是否配对,算法: 试分析流程图后对下面算法中横线上空缺的语句进行填充,并在//符号后对语句进行文字说明,将填充的内容填入到程序中的字母序列中。 intBracketsCheck(char*fname) { Stacka; InitStack(a); charch; while(ifstr>>ch) { switch(ch) { case'{': case'[': case'(': Push(a,ch);//A: 字符进栈 break; case'}': if(Peek(a)=='{')//B: 读栈顶元素进行判断 Pop(a);//C: 栈顶元素出栈 else return0; break; case']': if(D: Peek(a)==’[‘) Pop(a); else return0; break; case')': if(Peek(a)=='(') E: Pop(a); else return0; } } if(F: StackEmpty(a)){ cout<<"ok! "< return1;} else{ cout<<"bad! "< return0;} 十二、已知线性表A={a1、a2、……an}采用链接存储结构,其数据域由4个值域组成,假设依次为 charcode[] charname[] intmax intmin 要求: 1、定义单链表结点(包括对数据域的定义); 2、从单链表的表头删除一个结点。 (参考答案) 答1: goods{charcode[5]; charname[15]; intmax; intmin; }; ypedefstructtgoodsElemType; structsNode{ElemTypedata; structsNode*next; }; 答2: ElemTypeDeleteFirstList(structsNode**HL) { ElemTypetemp; structsNode*p=*HL; if(*HL==NULL){ printf("Deletingfromanemptylist! \n"); exit (1); } *HL=(*HL)->next; temp=p->data; free(p); returntemp; } 十三、画出P15【算法1-3】简单选择排序的流程图,并带入5个整型数值进行排序过程分析,写出排序在执行过程中数组元素的变化。 inti,j,k,x i=0 N i Y k=i j=i+1 N j Y b[j] Y k=j j++ b[i]b[k] i++ end 十四、教材上的习题:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 14 习题 答案 DOC
![提示](https://static.bingdoc.com/images/bang_tan.gif)