《数据结构各章节试题.doc》由会员分享，可在线阅读，更多相关《数据结构各章节试题.doc（19页珍藏版）》请在金锄头文库上搜索。
1、第一章一、填空题1 .数据元素.是数据的基本单位，.数据项.是具有独立含义的最小标识单位。3 数据之间的关系（逻辑结构）有四种.集合.、.线性结构.、.树形结构.、.网状结构.，可分为.顺序映像. .、.非顺序映像.两大类。4 数据的存储结构包括.顺序存储结构.、.链式存储结构.。.二、问答题1. 什么是数据结构?什么是数据类型?数据结构是相互之间存在一种或多种特定关系的数据元素的集合，数据类型是一个值的集合和定义，在这个值集上的一组操作的总称。2. 叙述算法的定义与特性。算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。特性：有穷性，确定性，可行性，
2、输入，输出。3. 叙述算法的时间复杂度。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f（n），算法的时间量度记作：T（n）=0（f（n），它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。三、判断题（在各题后填写“”或“”）1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（错 ）2下列几种数量级从小到大的排列顺序为： O(1) 、O(logn)、O(n) 、O(nlogn) 、O(n2) 、O(n3 ) 、O(2n) 。（对 ）四、算法分析1 计算机执行下面的语句时，语句s的执行频度（重复执行
3、的次数）为n（n+1）/2-3 FOR(i=l；i=i;j-) s; 2有下列运行时间函数： （1）T1 (n)=1000; （2）T2(n)=n2+1000n; （3）T3(n)=3n3+100n2+n+1;分别写出相应的大O表示的运算时间。（1）0（1）.（2）0（n二次方），（3）0（n三次方）3 设n为正整数，利用大O记号，将该程序段的执行时间表示为n的函数，则下列程序段的时间复杂度可表示为 （1） 0（n） （2）0（n二次方）1)float sum1(int n) /* 计算1！+2！+n! */ p=1; sum1=0; for (i=1; i=n; +i) p=p*i; sum
4、1=sum1+p /* sum1 */(2) float sum2(int n) /* 计算1！+2！+n! */sum2=0; for (i=1; i=n; +i) p=1; for (j=1; j=i; +j) p=p*j; sum2=sum2+p; /* sum2 */3. n是描述问题规模的非负整数规模，下面程序片段的时间复杂度是0。(2011)i=2； WHILE（ inext=Pointer B NEW-next=Pointer-next Pointer=NEW Pointer-next=NEWC Pointer-next=NEW-next D 以上皆非NEW-next=Point
5、er5. 在单链表中,增加头结点的目的是 （ C ） A. 使单链表至少有一结点 B. 标志表中首结点位置 C. 方便运算的实现 D.说明单链表是线性表的链式存储实现6 线性表在 情况下适用于使用链式结构实现。（ B ）（）需经常修改中的结点值 （）需不断对进行删除插入 （）中含有大量的结点 （）中结点结构复杂7、向一个有127个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动（ B ）个元素。A、8 B、63.5 C、63 D、7三、算法设计1 设顺序表L中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。答1. Status Insert_SqLi
6、st(SqList &va,int x)/把x插入递增有序表va中if(va.length+1va.listsize) return ERROR;va.length+;for(i=va.length-1;va.elemix&i=0;i-)va.elemi+1=va.elemi;va.elemi+1=x;return OK;/Insert_SqList ！ 2 分别写出算法将单链表和顺序表就地逆置（用尽可能少的附加空间在原存储出空间内将将线性表a1,a2,a3,an逆置为ana3,a2,a1）。答（1）.void reverse(SqList &A)/顺序表的就地逆置for(i=0,j=A.le
7、ngth-1;ij;i+,j-)A.elemiA.elemj;/reverse （2）分析:本算法的思想是,逐个地把L的当前元素q插入新的链表头部,p为新表表头.（void LinkList_reverse(Linklist &L)/另一种方法，节省指针 p=L-next;q=p-next;while(q)p-next=q-next;q-=L-next;L-next=q;q=p-next; *3删除元素递增排列的链表L中所有值相同的元素。答3 .Status Delete_Equal(Linklist &L)/删除元素递增排列的链表L中所有值相同的元素p=L-next;q=p-next; /p
8、,q指向相邻两元素while(p-next)if(p-data!=q-data)p=p-next;q=p-next; /当相邻两元素不相等时,p,q都向后推一步elsewhile(q-data=p-data) s=q-next;free(q); q=s; p-next=q;p=q;q=p-next; /当相邻元素相等时删除多余元素/else/while/Delete_Equal 第三章1. 元素a,b,c,d,e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是 B .(2011) A.3 B.4 C.5 D.62. 设栈
9、S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag，则栈S的容量至少是 C (2009)A1 B.2 C.3 D.43.对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。若在逻辑上看一个环，则队列中元素的个数为 (4) (1).R-F .n+R-F .(R-F+1)mod n .(n+R-F)mod n4. 若一个序列的进栈顺序为1,2,3,4, 那么不可能的出栈序列是 A A. 4,2,3,1 B. 3,2,1,4 C. 4,3,2,1 D. 1,2,3,45、一个递归的定义可以用递归过程求解，也可以用
10、非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程（ B ）A较快 B较慢 C相同 D 不确定！6.简述以下算法的功能（栈和队列的元素类型均为int）（） Void alog(stack &S,int e) Stack T; int d; InitStack(T);while(!StackEmpty(S) Pop(S,d) ; if (d!=e) Push(T,d); while(!StackEmpty(T) Pop(T,d); Push(S,d); （2）void proc_1(Stack S) int i, n, A255; n=0; while(!EmptyStack(S) n+; Pop(S, An); for(i=1; i=n; i+) Push(S, Ai);（） void alog3(ueue &Q) Stack S; int d; InitStack(S);while(!QueueEmpty(Q) DeQueue(Q,d);Push(S,d); while(!StackEmpty(S) Pop(S,d); EnQueue(Q
