资源描述：
《安徽大学08—09数据结构考试试卷及答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、安徽大学计算机科学与技术学院2009——2010学年第二学期计算机科学与技术专业2008年级数据结构课程(测验)学号姓名得分（闭卷120分钟）得分一、不定项选择题（每小题2分，共16分）1．线性表不具有的特点是（B）。A．可随机访问任一元素B．插入删除不需要移动元素C．不必事先知道存储空间D．所需空间与线性表长度成正比2．已知L是带头结点的单链表，指针P指向的结点既不是首元结点，也不是尾元结点，在P结点后插入S结点的语句序列是BC。A．P->next=S->nextB．S->next=P->nextC．P->next=SD．S->next=P3．设一个
2、栈的输入序列为1，2，3，4，则所得的输出序列可能是ABC。A．1，2，3，4B．4，3，2，1C．1，3，4，2D．4，1，2，34．队列操作的原则是A。A．先进先出B．后进先出C．只能进行插入D．只能进行删除5.串是D。A．不少于一个字母的序列B．任意个字母的序列C．不少于一个字符的序列D．有限个字符的序列6．在主串S中查找子串t的第1次出现的位置的操作称为BC。A．字符串的查找B．字符串的定位C．模式匹配D．字符串的操作7.在数组A中,每个元素占3个字节,行下标i从1到8,列下标j从1到10,从首地址SA开始连续存放在存储器中,该数组按列存放时,
3、元素A[5][8]的起始地址为B。A．SA+141B．SA+180C．SA+222D．SA+2258．广义表（（a,b），c,d）的表头是C。A．aB．（a）第7页共7页C．（a,b）D．（（a））得分二、填空题（每空２分，共12分）1．下面程序段中语句k+=10*i的执行次数是n-1。i=1;k=0;while(i<=n-1){k+=10*i;i++;}2．在顺序表中插入一个元素，需要平均移动n/2元素，具体移动的元素个数与_插入位置和表长__________________有关。3．在单链表L中，删除指针P所指结点的后继结点的语句是p->next=
4、p->next->next。4．取出广义表A=((x,y,z),(a,b,c,d))中原子b的函数是____GetHead(GetTail(GetHead(GetTail(A))))________________________。5．设递归函数如下，递归体为f(n)=f(n-1)+f(n-2)。1n=1或n=2f(n)=f(n-1)+f(n-2)其它得分三、算法分析题（每题8分，共40分）1．简述以下算法的功能。StatusA(LinkedListL){//L是无表头结点的单链表第7页共7页if(L&&Lànext){Q=L;L=Lànext;P=L
5、;while(Pànext)P=Pànext；Pànext=Q；Qànext=NULL；}returnOK;}删除首元结点并将其插入到表尾2．简述以下算法的功能。Statusalgo(StackS,inte){StackT,intd;initStack(T);while(!StackEmpty(S)){pop(S,d);if(d!=e)Push(T,d);}while(!StackEmpty(T)){pop(T,d);Push(S,d);}}利用栈T，删除栈S中所有值为e的元素3．设函数如下：voidprint(intw){inti;if(w!=0){
6、print(w-1);第7页共7页for(i=1;i<=w;i++)printf(“%3d”,w);printf(“”);}}写出调用语句print（5）的结果。1223334444555554．写出以下程序段的输出结果（队列中的元素类型为char，EnQueue（Q，x）表示元素x进队Q，DeQueue（Q，x）表示队头元素出队后保存在x中）voidmain（）{charx=’e’,y=’c’;EnQueue（Q，’h’）;EnQueue（Q，’r’）;EnQueue（Q，y）;DeQueue（Q，x）;EnQueue（Q，x）；DeQueue（
7、Q，x）；EnQueue（Q，’a’）;while(!QueueEmpty(Q){DeQueue（Q，y）;printf(y);}Printf(x);}char5．写出以下函数产生的输出结果voida（）{StrAssign（s，‘THISISABOOK’）；Replace(s,Substring(s,3,7),’ESEARE’);StrAssign(t,Concat(s,’S’));StrAssign(u,’XYXYXYXYXYXY’);第7页共7页StrAssign(v,SubString(u,6,3));StrAssign(w,’W’);Prin
8、tf(‘t=’,t,’v=’,v,’u=’,Replace(u,v,w));}t=THESEA
