2015-2016 数据结构A期末试卷(A卷).doc

试卷编号 拟题教研室（或教师）签名 乐晓波 教研室主任签名 长沙理工大学考试试卷（A卷）课程名称（含档次） 数据结构A 课程代号 0812002615 课程编号 002131 专 业 计算机相关专业 层次（本、专） 本科 考试方式（开、闭卷） 闭卷 一、应用题(2小题,共8分)设有一个栈，元素进栈的次序为：A，B，C，D，E，用I表示进栈操作，O表示出栈操作，写出下列出栈的操作序列。（1）C，B，A，D，E （2）A，C，B，E，D二、判断正误(5小题,共10分)1顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 ( )2一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D。( )3子串“ABC”在主串“AABCABCD”中的位置为2。( )4设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（ ）5调用一次深度优先遍历可以访问到图中的所有顶点。（ ）三、单项选择题(11小题,共22分)1两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素前驱的条件是（ ）。AP-next=Q-next BP-next= Q CQ-next= P DP= Q2从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（ ）个结点。A n B n/2 C (n-1)/2 D (n+1)/23如果以链表作为栈的存储结构，则出栈操作时（ ） A必须判别栈是否满B必须判别栈是否空 C必须判别栈元素类型D对栈可不做任何判别4设输入序列是1、2、3、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（ ）。 A n-i B n-1-i C n+1-i D 不能确定5下列说法不正确的是（ ） A串中元素只能是字符B串中元素只能是字母 C串是一种特殊的线性表 D串中可以含有空白字符 6线索二叉树中某结点R没有左孩子的充要条件是（ ）。A R.lchild=NULL B R.ltag=0 C R.ltag=1 D R.rchild=NULL7树最适合用来表示( )。A有序数据元素 B无序数据元素C元素之间具有分支层次关系的数据D元素之间无联系的数据8设有向无环图G中的有向边集合E=，则下列属于该有向图G的一种拓扑排序序列的是（ ）。 A1，2，3，4 B2，3，4，1 C1，4，2，3 D1，2，4，39设数据结构A=(D，R)，其中D=1，2，3，4，R=r，r=，则数据结构A是（ ）。 A 线性结构 B 树型结构 C 图型结构 D 集合10每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储区里，这种存储结构称为（ ）结构。 A. 顺序存储 B. 链式存储 C. 索引存储 D. 散列存储11下列叙述中，错误的是（）A数据的存储结构与数据处理的效率密切相关 B数据的存储结构与数据处理的效率无关 C数据的存储结构在计算机中所占的空间不一定是连续的 D一种数据的逻辑结构可以有多种存储结构四、算法设计题(3小题,共32分)1已知一个单链表，编写一个函数从单链表中删除自第i个结点起的k个结点。（11分）2设计一个在链式存储结构上统计二叉树中结点个数的算法。（11分）3先阅读下列函数arrange() ，再做下面（1）和（2）两小题： int arrange(int a,int 1,int h,int x)/1和h分别为数据区的下界和上界 int i,j,t； i=1；j=h； while(ij) while(i=x)j-； while(ij & ai=x)i+； if(ij) t=aj；aj=ai；ai=t； if(aix) return i； else return i1； （1）写出该函数的功能；（5分）（2）写一个调用上述函数实现下列功能的算法：对一整型数组bn中的元素进行重新排列，将所有负数均调整到数组的低下标端，将所有正数均调整到数组的高下标端，若有零值，则置于两者之间，并返回数组中零元素的个数。（5分）五、填空题(5小题,共10分)1由两个栈共享一个存储空间的好处是（ ）2设长度为n的链队列用单循环链表表示，若只设尾指针，则出队操作的时间复杂度为( )。3设无向图G中顶点数为n，则图G至少有（ ）条边，至多有（ ）条边。4在无向图的邻接矩阵中，第i行（列）中“1”的个数是第i个顶点的 ，矩阵中“1”的个数的一半是图中的 。5顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构中的数据元素之间的逻辑关系是由（ ）表示的。六、简答题(2小题,共10分)1请说明顺序表和单链表各有何优缺点。2设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。七、名词解释(2小题,共8分)1什么是AOE网?2简述下列概念：线性结构、非线性结构。长沙理工大学计算机与通信工程学院2015-2016学年一学期数据结构A期末考试试卷(A卷)（答案部分）一、应用题(1小题,共8分)1解：（1）IIIOOOIOIO （2）IOIIOOIIOO二、判断正误(5小题,共10分)1（） 2（） 3（） 4（） 5（）三、单项选择题(11小题,共22分)1B 2D 3B 4C 5B 6C 7C 8A 9C 10A 11B四、算法设计题(3小题,共32分)1解：void Del(ListNode *head,int i,int k) node *p,*q;int j;if (i=1) For (j=1;jnext; Free(p); else p=head; for (j=1;jnext; / p指向要删除的结点的前一个结点 for (j=1;jnext; / q 指向要删除的结点 p-next=q-next; free(q); 2解：void countnode(bitree *bt,int &count) if(bt!=0) count+; countnode(bt-lchild,count); countnode(bt-rchild,count);3解答：（1）该函数的功能是：调整整数数组a中的元素并返回分界值i，使所有x的元素均落在a1.i上，使所有x的元素均落在ai1.h上。（2）int f(int b,int n) 或 int f(int b,int n) int p,q； int p,q；p=arrange(b,0,n1,0)； p=arrange(b,0,n1,1)；q= arrange(b,p+1,n1,1)； q= arrange(b,0,p,0)；return qp； return pq； 五、填空题(5小题,共10分)1节省存储空间，降低上溢发生的机率20（1）3 0，n(n-1)/24 度 边数5 存储位置 指针六、简答题(2小题,共10分)1答：（1）顺序表的优点： 无需为表示表中元素之间的逻辑关系而增加额外的存储空间； 可以快速地存取表中任一位置的元素（即随机存取）。顺序表的缺点： 插入和删除操作需移动大量元素； 表的容量难以确定； 造成存储空间的“碎片”。（2）单链表的优点： 不必事先知道线性表的长度； 插入和删除元素时只需修改指针，不用移动元素。单链表的缺点： 指针的结构性开销； 存取表中任意元素不方便，只能进行顺序存取。2答：q-llink=p; q-rlink=p-rlink; p-rlink-llink=q; p-rlink=q;七、名词解释(2小题,共8分)1答：若在带权有向图G中以项点表示事件，以有向边表示活动，边上的权值表示该活动持续的时间，则此带权有向图称为用边表示活动的网(Acti