数据结构中考答案2015

试题、试卷纸总3页第1页（A）卷1数据结构期中试卷答案（计算机）以下各题若没有求解过程，酌情扣5-10分。1.（20分）阅读下列算法,并回答问题：（1）p-link=rear-link此题详解：使新插入结点P的链域指向队头结点（2）*x=p-data此题详解：把队头结点的元素值取出来（3）return1此题详解：出队成功则返回12.（10分）计算下列程序段的时间复杂度intfun(intn){inti=1,s=1;while(sn)s+=++i;returni;}答：功能：返回自然数数列前i项和不小于n的第一个i值；此题详解：s+=++i等价于i=i+1;s=s+i;所以有i=1时，s=1+2=3i=2时，s=3+3=6i=3时，s=6+4=10i=4时，s=10+5=15i=5时，s=15+6=21时间复杂度为O（n1/2）；当满足S=1+2+3+……+(f(n)+1)=f(n)*(f(n)+1)/2+1=n时循环执行，求出f(n)的变化趋势。f(n)*f(n)f(n)*(f(n)+1)=2(n-1),所以T(n)=O（n1/2）3.（15分）设有下列递归算法:intvol(intn){if(n==0)return0;试题、试卷纸总3页第2页（A）卷2elsereturnvol(n-1)+2;}如该函数被调用时，参数n值为3，函数调用结束时返回值为多少?用图示描述函数的递归调用执行过程。答：参数n值为3,函数调用结束时返回值为6，调用执行过程：vol(3)vol(2)return2+vol(2)vol(2)vol(1)return2+vol(1)vol(1)vol(0)return2+vol(0)vol(0)return0vol(3)02464.（10分）令模式串t=”abcabaa”,根据KMP算法的思想，试求出t的next[j]值。tabcabaaj0123456Next[j]01112325.（5分）假设二维数组A[8][10]按行优先顺序存储,若每个元素占2个存储单元,元素A[0][0]的存储地址为100,则元素A[5][6]的存储地址是多少？100+((5*10)+6)*2=2126.（20分）试设计一个算法，实现在整数顺序表A中查找出最大值和最小值整数。要求通过参数Max和Min分别返回最大整数及最小整数。顺序表的类型定义为：typedefstruct{DateTypelist[MaxSize];intsize;}SeqList;注意，算法中可使用顺序表的如下两个函数：intLength(SeqListA);求表的长度；试题、试卷纸总3页第3页（A）卷3intgetData(SeqListA,intk);提取第k个元素的值。答：voidFindMaxMin(SeqListA,int*Max,int*Min){inti;*Max=getData(A,0);*Min=getData(A,0);for(i=1;iLength(A);i++){if(*MaxgetData(A,i))*Max=getData(A,i);if(*MingetData(A,i))*Min=getData(A,i);}}7.（20分）算法设计：设计算法在带头结点的单链表L中删除数据值最大的结点（设链表中各结点数据值均不相同）。函数的原型为：voiddelete（ListNode*L）单链表类型定义如下：typedefstructnode{intdata;structnode*next;}ListNode;voiddelete(LinkListL){LinkListp,q,pre,s;intmax;p=L-next;pre=L;max=p-data;q=L;while(p-next!=NULL){pre=p;p=p-next;if(p-datamax){q=pre;max=p-data;}}s=q-next;q-next=q-next-next;free(s);}