《11届数据结构期中考.docx》由会员分享，可在线阅读，更多相关《11届数据结构期中考.docx（5页珍藏版）》请在三一文库上搜索。
1、一、选择题20分1、 数据结构中，与所使用的计算机无关的是数据的结构。A. 存储 B. 物理 C. 逻辑D.物理和存储2、除第一个和最后一个数据元素外每个数据元素只有一个前驱数据元素和一个后继数据元素的结构是)A.树结构B.图结构C.非线性结构 D.线性结构3、算法指的是)°A.计算方法B.排序方法C.解决冋题的有限运算序列D.调度方法4、L是 丨不带表头的单链表,在表自插入结点*p 的操作是°A. p = L;p->n ext :=L;B. p->n ext = L; p = L1C. p->n ext = L; L = p;D. L = p; p-&g
2、t;n ext= L;5、在n个结点的顺序表中，算法的时间复杂度是0 1的操作是 。A. 访问第i个结点K i < n和求第i个结点的直接前驱2< i < nB. 在第i个结点后插入一个新结点K i < nC. 删除第i个结点K i < nD. 将n个结点从小到大排序6、设单链表中结点的结构为data, next 。指针q所指结点是指针p所指结点的 直接前驱，假设在q与p之间插入结点s，那么应执行的操作是。A. s->n ext=p->n ext; p->n ext=s;B. q->n ext=s; s->n ext=p;C. p-&
3、gt;n ext=s->n ext; s->n ext=p;D. p->n ext=s; s->n ext=q;7、串是一种特殊的线性表，其特殊性表达在A.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符8如果顺序循环队列中有一个单元始终空着，不用来存放数据元素，那么判定这样一个循环队列QU最多元素为mO为满的条件是A. QU->front= (QU->rear+1) %mOB. QU->front! =(QU->rear+1) %m0C. QU->fro nt= QU->rearD.QU->fron
4、t! = QU->rear9、判定一个栈ST (最多元素为mO)为空的条件是()A. ST.top!=0B. ST.top=0C. ST.top!=m0D. ST.top=m010、 顺序表第一个元素的存储地址是 100,每个元素的长度为二，那么第6个元素的地址是 ()。A. 110 B . 108 C . 100D . 120二、填空题(30分)1. 算法设计应满足五条目标，分别是正确性，可读性， (1), (2),高空间效率。2. 设单链表中结点的结构为(data, next),带有一个头结点的单链表head为空的条件是(3)。3. 设有一个二维数组A1020，按行存放于一个连续的存
5、储空间中，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 )。6. 一个算法的根本操作执行次数为(3n2+2nlog2n+4n-7)/(5n)，那么其时间复杂度表示为(7)07. ListNode表示循环链队列，rear是指向以循环链表表示的队列的队尾指针，link表示指针域。EnLQueue函数实现把x插入到队尾的操作。DeLQ
6、ueue函数实现删除队头元素 并赋给x的操作。根据题意按标号把适宜的内容填写到算法后面相应标号的位置。(队列元素的数据类型为DataType)void En LQueue(ListNode *rear, DataType x)/ rear是指向以循环链表表示的队列的队尾指针，插入x为新的队尾元素。ListNode *p;p=(ListNode *)malloc(sizeof(ListNode);p->data=x;(8) _ ;rear->li nk=p; rear=p;；int DeLQueue(ListNode *rear, DataType *x)/ rear是指向以循环链表
7、表示的队列的队尾指针，假设队列不空，那么删除队头元 素，并以x带回，并返回1,否那么返回0, x 无意义if(rear=NULL) return 0;if (rear->li nk=rear) x=rear->data; rear=NULL; retur n 1;ListNode *p=rear->li nk; rear->li nk=p->li nk;(9);Free(p);(10);三、应用题(27分)1.指出算法的功能和时间复杂度，假设 n=20,贝U求出函数的返回值。int fun (i nt n)int i=1, s=1;while(s <n) s
8、+=+i;retur n i;2.设有以下递归算法：int vol(int n)if(n二=0)return 0;elseretur n vol( n-1)+2;如该函数被调用时，参数n值为3,函数调用结束时返回值为多少？用图示描述函数 的递归调用执行过程。3、写出以下程序段的输出结果(栈的元素类型DataType为char)void mai n( )Stack S;/Stack 为栈类型Char x,y;InitStack(S);/ 栈初始化X=' c' ;y= ' k'Push(S,x); Push(S, Pop(S,x); Push(S, Pop(S,x)
9、; Push(S,'Pdsh(S,y)/Push为入栈操作，Pop为出栈操作 't ' ); Push(S,x);s );while(!StackEmpty(S) Pop(S,y);printf(y); ;Prin tf(x);四、算法设计题(13)试设计一个算法，实现在整数顺序表A中查找出最大值和最小值整数。要求通过参数Max和Min分别返回最大整数及最小整数。顺序表的类型定义为：typedef structDateType listMaxSize;int size;SeqList;注意，算法中可使用顺序表的如下两个函数：int Len gth(SeqList A );求表的长度；int getData (SeqList A , int k);提取第 k 个元素的值。