数据结构与算法期中考试卷(含答案)

玉林师范学院期中课程考试试卷（2010——2011学年度第一学期）命题教师：刘恒命题教师所在系：数计系课程名称：数据结构与算法考试专业：信计考试年级：09级题号一二三四五总分应得分3010104010满分：100实得分评分：评卷人签名一、单项选择题（每题2分，共30分，把正确答案填入表格中）12345678CBCCDACA9101112131415CDBBBAD1、在数据结构中，从逻辑上可以把数据结构分成(C)。A、动态结构和静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、逻辑结构和存储结构2、结构中的数据元素之间存在一个对多个的关系，称为(B)结构。A、线性B、树形C、图状D、网状3、以下关于线性表的说法不正确的是(C)。A、线性表中的数据元素可以是数字、字符、记录等不同类型。B、线性表中包含的数据元素个数不是任意的。C、线性表中的每个结点都有且只有一个直接前驱和直接后继。D、存在这样的线性表：表中各结点都没有直接前驱和直接后继。4、关于单链表的说法，请选出不正确的一项(C)。A、逻辑相邻、物理不一定相邻B、不能随机存取C、插入与删除需移动大量元素D、表容量易于扩充5、关于顺序表的说法，请选出不正确的一项(D)。A、逻辑相邻、物理相邻B、可实现随机存取C、存储空间使用紧凑D、表容量易于扩充6、设N为正整数，试确定下列程序段中前置以记号@语句的频度为(A)。x=91;y=100;while(y0){@if(x100){x-=10;y--;}elsex++;}A、1100B、9100C、110D、9107、在顺序表中删除一个元素，平均需要移动(C)元素，设表长为n。A、n/2-1B、n/2+1C、n/2D、(n+1)/28、对单链表执行下列程序段，请选出正确的一项(A)。T=P;While(T-next!=NULL){T—data=T—data*2;T=T—next;}A、R-data=4B、R-data=8C、H-data=4D、Q-data=79、若一个栈的输入序列是1，2，3，┅，n，输出序列的第一个元素是n,则第k个输出元素是(C)。A、kB、n-k-1Cn-k+1D、不确定10、判断一个顺序栈S(最多有n个元素)为满的条件是()D。A、s.top!=0B、s.top==0C、s.top!=nD、s.top==n11、一个队列的出队序列是1234，则队列的入队序列是(B)。A、4321B、12342573┅84^PQRS考试时间年月日下午系(院):年级:专业:班别:学号:姓名:座位号:——————————————————————————————————————————————————————密封线内不要答题∞装订∞线∞HC、1432D、324112、选出合适的答案，“队列”结构实现的是(B)。(1)先进/后出(2)后进/先出(3)先来/先服务(4)先进/先出(5)后进/后出A、(1)、(2)B、(3)、(4)、(5)C、(1)、(4)、(5)D、(1)13、串是一种特殊的线性表，其特殊性体现在(B)。A、可以顺序存储B、数据元素是一个字符C、可以链接存储D、数据元素可以是多个字符14、设串s1=‘ABCDEFG’，s2=‘PQRST’，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的字串，len(s)返回串s的长度，则：con(subs(s1,3,len(s2)),subs(s1,len(s2),3))的结果串是(A)。A、CDEFGEFGB、CDEFEFGC、BCDEFEFGD、CDEFGEF15、下列说法哪个是不正确的：(D)。A、空格串≠空串B、数据元素是由若干数据项组成C、串也称字符串D、栈的表头端称为栈顶二、填空题（每题1分，共10分）1、数据结构是相互之间存在一种或多种特定关系的数据元素的集合。2、一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作T(n)=O(f(n))。3、线性表中每个结点包含两个指针域，称此线性表为双向链表。4、一个顺序表的开始地址是1000，每个元素的长度是8，则第7个元素的存储地址是1048。5、执行p=(JD*)malloc(sizeof(JD))的作用是生成一个JD型结点，并用指针变量p指向（答出前半句即得分）。6、所谓顺序表(Sqlist)是线性表的顺序存储表示。7、栈是限定仅在表尾进行插入或则删除操作的线性表。8、人们日常计算用到的表达式，都被称为中缀表达式，这是由于这种算术表达式的运算符被置于两个操作数中间。9、队列的插入操作是在队尾进行。10、设每个字符占1个字节，若结点大小为4的链串的存储密度为50%，则其每个指针占4个字节。三、名词解释（每题2分，共10分）1、抽象数据类型抽象数据类型－简称ADT，是指一个数学模型以及定义在该模型上的一组操作。可用三元组表示（D,S,P），其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。（1分）如：ADT抽象数据类型名{数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义}ADT抽象数据类型名（1分）2、物理结构数据结构在计算机中的表示（又称映像或存储结构）。（1分）数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。（1分）3、语句的频度该语句重复执行的次数。（2分）4、循环链表是线性表的一种链式存储结构。（1分）其特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。（1分）5、算法的可行性一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。（2分）注：可视答案的合理程度酌情给分。四、解答题（每题5分，共40分）1、分别写出循环队列中判断队空和队满的条件（设循环队列的最大存储空间是M）。队空：front==rear（2.5分）队满：(rear+1)%M==front（2.5分）2、已知L是带表头结点的非空单链表，且P结点既不是第一个元素结点，也不是最后一个元素结点，请写出删除P结点的直接后继结点的语句序列：Q=P-next;（2分）P-next=p-next-next;（2分）free(Q);（1分）3、简述以下算法的功能：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相等的元素删掉（5分）p223.4(2)4、写出下列程序段的输出结果（队列中的元素类型QElemType为char）。voidmain(){QueueQ;InitQueue(Q);Charx=’e’,y=’c’;EnQueue(Q,’h’);EnQueue(Q,’r’);EnQueue(Q,y);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,’a’);While(!QueueEmpty(Q)){DeQueue(Q,y);printf(y);}printf(x);}char（5分）p233.125、已知下列字符串:a=’THIS’,f=’ASAMPLE’,C=’GOOD’,D=’NE’,b=’’,s=Concat(a,Concat(SubString(f,2,7),Concat(b,SubString(a,3,2)))),t=Replace(f,SubString(f,3,6),c),AGOODu=Concat(SubString(c,3,1),D)ONE,g=’IS’,v=Concat(s,Concat(b,Concat(t,Concat(b,u)))),THISSAMPLEISAGOODONE试问：s,v,StrLength(s),Index(v,g),Index(u,g)各是什么？s:THISSAMPLEIS（1分）v:THISSAMPLEISAGOODONE（1分）StrLength(s)=14（1分）Index(v,g)=3（1分）Index(u,g)=0（1分）6、下面算法实现串的基本操作StrInsert(&S,pos,T)(S、T用定长顺序存储表示)，请填空完成。StatusStrInsert(SString&S,intpos,SStringT){if(pos1||posS[0]+1||S[0]+T[0]maxstrlen)returnERROR;S[pos+T[0]…S[0]+T[0]]=S[pos…S[0]];S[pos…pos+T[0]-1]=T[1…T[0]];（2.5分）S[0]=S[0]+T[0];（2.5分）ReturnOK;}7、设有3个元素A，B，C依次进栈，给出它们所有可能的出栈次序。ABCACBCBABCABAC8、下列算法的功能是:已知线性表La和Lb中的元素按值非递减排列。归并La和Lb得到新的线性表Lc，Lc的元素也按值非递减排列。填空完成该算法。voidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);La1┅Panai┅^i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);while((i=La.len)&&(j=Lb.len)){(2.5分)GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai=bj){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j;}}while(i=La_len){GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}while(j=Lb_len){GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}课本P21算法2.2五、算法设计题：编一段算法实现单链表的逆向生成（10分）LinklistCreaaList_L(LinklistL,intn){inti;Linklistp;L=(linklist)malloc(sizeof(LNode));L-next=NULL;for(i=n;i0;i--){p=(linklist)malloc(sizeof(LNode));p-data=x;p-next=L-next;L-next=p;}returnL;}第二章课件P18算法描述