2011数据结构期中考试题目答案.ppt

一、选择题(30分) 1.算法指的是( D) A.计算机程序 B.解决问题的计算方法 C.排序算法 D.解决问题的有限运算序列 2.线性表采用链式存储时，结点的存储地址是(B ) A．必须是不连续的。 B. 连续与否均可。 C．必须是连续的。 D．和头结点的存储地址相连续。 3.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为(C ) A．O(1) B.O(n) C.O(m) D. O (m+n) 4 在一个单链表中，已知*q结点是*p结点的前趋结点，若在*q和*p之间插入*s结点， 则需执行(b ) A.s-next=p-next;p-next=s;B.q-next=s;s-next=p; C.p-next=s-next;s-next=p;D.p-next=s;s-next=q. 5. 一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是_C__. A、edcba B、decba C、dceab D、abcde (6) 设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其对头指针front的值是：( ) A.front=front+1; B.front=(front+1)%(m-1)。 C.front=(front-1)%m D.front=(front+1)%m。 二、填空(10分)： 1.数据的逻辑结构是从逻辑关系上描述描述数据，它与数据的物理结构(或存储结构)无关，是独立于计算机的。 2. 为度量一个有哪些信誉好的足球投注网站算法的性能，需要在时间复杂度和空间复杂度方面进行权衡。 三、编写一个函数，通过一趟遍历在顺序表中确定值最大的值(用结构体设计可采用如下的结构体，也可用类进行设计，结点的值可考虑为整型)。要求返回位置和值。(20分) struct SequentList  { elemtype data[MaxListSize]; //抽象类型elemtype定义的数组 int size;//数据元素个数 } void FindMax(SequentList s,int b[])//值 { int i; b[0]=s.data[0]; b[1]=0; for(i=1;is.size;i++) if(b[0]s.data[i]) {b[0]=s.data[i];b[1]=i;} return ; } 四、编写一个函数，通过一趟遍历在单链表中确定值最小的结点(要求设计带头结点的单链表，其中用结构体设计可采用如下的结构体，也可用类进行设计，结点的值可考虑为整型)。(20分) struct LinList{ int data; LinList *next; }; LinList *FindMin(LinList *head) { LinList *p=head-next,*q; q=p; while(p-next!=NULL) { if(p-dataq-data) q=p; p=p-next; } if(p-dataq-data) q=p; return q; } 五、(20分) 设计一个算法，统计在一个输入字符串中各个不同字符出现的频率。用顺序串实现。 struct seqstring { char ch[maxlen]; //存放串的值的一维数组 int curlen; //当前串的长度 }； 对设计的算法进行时间复杂度的计算。 解： int a[100];char b[100]; figure(seqstring s,a[100],b[100]) { int i,k=0,j=0; for(i=0;is.curlen;i++) { for(j=0;jk;j++) if(b[j]==s.ch[i]) a[j]++; if(j=k) {b[k]=s.ch[i];a[k]=0;k++;} } } * * * * *