《数据结构》期中考试卷.docVIP

郑州大学西亚斯学院2012-2013学年第一学期期中试卷 考试科目： 数据结构 试卷类型： 题号 一 二 三 四 总分 得分 阅卷人 得分 一 .选择题(共 30 分，每题 2 分)  算法的计算量的大小称为计算的（????）。 A．效率?????????．?复杂性??????．?现实性???????????．难度? 算法的时间复杂度取决于（?）A．问题的规模??????．待处理数据的初态?????．?和? 从逻辑上可以把数据结构分为（????）两大类。 A．动态结构、静态结构??????B．顺序结构、链式结构??? ．线性结构、非线性结构???? ?．初等结构、构造型结构? A．．．．程序段?for??i=n-1;??i=1;?i--)????????????for?(j=1;j=?I;j++)? ????????? if?a[j]a[j+1]? ??????????????????then??a[j]与a[j+1]对换；? 其中?n为正整数，则最后一行的语句频度是（???）?  A．?（n）???．?(nlogn)????C．(n3)?????D．(n2)??? 设有两个串p和q，求q在p中首次出现的位置的运算称作。?A． 连接 B． 模式匹配 C．求子串 D． 求串长设串s1=’ABCDEFG’，s2=’PQRST’，函数con (x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con (subs (s1,2,len (s2)),subs (s1,len (s2),2))的结果串是。? A BCDEF B. BCDEFG C.BCPQRST D. BCDEFEF 对于栈操作数据的原则是（ ）。A．先进先出 B．后进先出 C．后进后出 D．不分顺序设有三个元素X，Y，Z 顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是( )。A．XYZ B． YZX C． ZXY D． ZYX表达式a*(b+c)-d 的后缀表达式是( )。A．abcd*+- B. abc+*d- C. abc*+d- D. -+*abc 在单链表指针为p的结点之后插入指针为s的结点，正确的操（??? A．p-next=s;s-next=p-next;B．s-next=p-next;p-next=s;C．p-next=s;p-next=s-next;? D．p-next=s-next;p-next=s;栈和队列的共同点是（ ）。 A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点假设以数组A[m]存放循环队列的元素,其头尾指针分别为front 和rear， 则当前队列中的元素个数为（ ）。 A．(rear-front+m)%m??? B．rear-front+1??? C．(front-rear+m)%m????D．(rear-front)%mvoid CRE(){ char x; node *head,*s; int n=0; head=NULL;  x=getchar();  while(x!=‘#’) { s=（node *）malloc(sizeof(node)); s-data=x; s-next=head; head=s;n++; x=getchar();}}此程序段的功能： 按照下列题目中的算法功能说明，将算法描述片段中的错误改正过来。（1）下面的算法描述片段用于在双链表中删除指针变量p所指的结点（4分）： p-rlink=p-llink-rlink; p-llink=p-rlink-llink free(p);（2）下面的算法描述片段用于在双链表中指针变量p所指结点后插入一个新结点（6分）： new(q);????????q-llink=p;?????? ?p-rlink=q;?????? q-rlink=p-rlink;????? q=p-rlink-llink;? 用栈实现将中缀表达式8-(3+5)*(5-6/2)转换成后缀表达式，画出栈的变化过程。 设目标为S=‘abcaabbcaaabababaabca’，模式为P=‘babab’，（1）手工计算模式P的nextval数组的值；(5分)（2）写出利用求得的nextval数组，按KMP算法对目标S进行模式匹配的过程。?(5分) ?? 三．算法设计（20分） 1．设有一个由正整数组成的无序（向后）单链表，编写完成下列功能