11届数据结构期中考

1、数据构造中考卷纸总4页第1页一、选择题（20分）1、数据构造中，与所使用的计算机没关的是数据的（）构造。A.储蓄B.物理C.逻辑D.物理和储蓄2、除第一个和最后一个数据元素外每个数据元素只有一个前驱数据元素和一个后继数据元素的构造是（）A.树构造B.图构造C.非线性构造D.线性构造3、算法指的是（）。A.计算方法B.排序方法C.解决问题的有限运算序列D.调动方法4、已知L是一个不带表头的单链表,在表首插入结点*p的操作是（）。A.p=L;p-next=L;B.p-next=L;p=L;C.p-next=L;L=p;D.L=p;p-next=L;5、在n个结点的次序表中，算法的时间复杂度是O（1

2、）的操作是（）。接见第i个结点（1in）和求第i个结点的直接前驱（2in）在第i个结点后插入一个新结点（1in）删除第i个结点（1in）将n个结点从小到大排序6、设单链表中结点的构造为（data,next）。已知指针q所指结点是指针p所指结点的直接前驱，若在q与p之间插入结点s，则应履行的操作是（）。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;7、串是一种特其余线性表，其特别性表此刻（）A.能够次序储蓄B.数据元素是一个字符C.能够链接储蓄D.数据元素能够是多

3、个字符8、假如次序循环行列中有一个单元向来空着，不用来寄存数据元素，那么判断这样一个循环行列QU(最多元素为m0)为满的条件是（）。A.QU-front=（QU-rear+1）%m0QU-front！=（QU-rear+1）%m0C.QU-front=QU-rearD.QU-front！=QU-rear精选数据构造中考卷纸总4页第2页9、判断一个栈ST（最多元素为m0）为空的条件是（）。AST.top!=0B.ST.top=0CST.top!=m0D.ST.top=m010、次序表第一个元素的储蓄地点是100，每个元素的长度为二，则第6个元素的地点是（）。A110B108C100D120二、填

4、空题（30分）1算法设计应满足五条目标，分别是正确性，可读性，（1），（2），高空间效率。2设单链表中结点的构造为（data,next）,带有一个头结点的单链表head为空的条件是（3）。3设有一个二维数组A1020，按行寄存于一个连续的储蓄空间中，A00的储蓄地址是200，每个数组元素占1个储蓄字，则A62的储蓄字地点是（4）。4.为了防范“假溢出”，次序行列平常采用（5）构造。5.设栈S和行列Q的初始状态为空。元素a,b,c,d,e,f依次经过栈S,并且元素出栈后，即进入行列Q，若出队的次序为b,d,c,f,e,a,则栈S的容量最少应当为(6)。一个算法的基本操作履行次数为(3n2+2nl

5、og2n+4n-7)/(5n)，则其时间复杂度表示为（7）。ListNode表示循环链行列，rear是指向以循环链表表示的行列的队尾指针，link表示指针域。EnLQueue函数实现把x插入到队尾的操作。DeLQueue函数实现删除队头元素并赋给x的操作。依照题意按标号把合适的内容填写到算法后边相应标号的地点。（行列元素的数据种类为DataType）voidEnLQueue(ListNode*rear,DataTypex)/rear是指向以循环链表表示的行列的队尾指针，插入x为新的队尾元素。ListNode*p;p=(ListNode*)malloc(sizeof(ListNode);p-da

6、ta=x;_(8)_;精选数据构造中考卷纸总4页第3页rear-link=p;rear=p;intDeLQueue(ListNode*rear,DataType*x)rear是指向以循环链表表示的行列的队尾指针，若行列不空，则删除队头元素，并以x带回，并返回1,否则返回0,x没心义if(rear=NULL)return0;if(rear-link=rear)x=rear-data;rear=NULL;return1;ListNode*p=rear-link;rear-link=p-link;_(9)_;Free(p);_(10)_;三、应用题（27分）指出算法的功能和时间复杂度，若n=20，则

7、求出函数的返回值。intfun(intn)inti=1,s=1;while(sn)s+=+i;returni;设有以下递归算法:intvol(intn)if(n=0)return0;精选数据构造中考卷纸总4页第4页elsereturnvol(n-1)+2;如该函数被调用时，参数n值为3，函数调用结束时返回值为多少?用图示描绘函数的递归调用履行过程。3、写出以下程序段的输出结果（栈的元素种类DataType为char）。voidmain()StackS;/Stack为栈种类Charx,y;InitStack(S);/栈初始化X=c;y=k;Push(S,x);Push(S,Push(S,y);a/Push为入栈操作，Pop为出栈操作Pop(S,x);Push(S,t);Push(S,x);Pop(S,x);Push(S,s);while(!StackEmpty(S)Pop(S,y);printf(y);Printf(x);四、算法设计题（13）试设计一个算法，实此刻整数次序表A中查找出最大值和最小值整数。要求经过参数Max和Min分别返回最大整数及最小整数。次序表的种类定义为：typedefstruc