2015-2016-数据结构A期末试卷(A卷)【含答案】

试卷编号拟题教研室（或教师）签名乐晓波教研室主任签名长沙理工大学考试试卷（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所指元素前驱的条件是（）。A．P-next==Q-nextB．P-next==QC．Q-next==PD．P==Q2．从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（）个结点。A．nB．n/2C．(n-1)/2D．(n+1)/23．如果以链表作为栈的存储结构，则出栈操作时（）A．必须判别栈是否满B．必须判别栈是否空C．必须判别栈元素类型D．对栈可不做任何判别4．设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（）。An-iBn-1-iCn+1-iD不能确定5．下列说法不正确的是（）A．串中元素只能是字符B．串中元素只能是字母C．串是一种特殊的线性表D．串中可以含有空白字符6．线索二叉树中某结点R没有左孩子的充要条件是（）。A．R.lchild=NULL．BR.ltag=0C．R.ltag=1D．R.rchild=NULL7．树最适合用来表示()。A．有序数据元素B．无序数据元素C．元素之间具有分支层次关系的数据D．元素之间无联系的数据8．设有向无环图G中的有向边集合E={1，2，2，3，3，4，1，4}，则下列属于该有向图G的一种拓扑排序序列的是（）。A．1，2，3，4B．2，3，4，1C．1，4，2，3D．1，2，4，39．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={1，2，2，3，3，4，4，1}，则数据结构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）两小题：intarrange(inta[],int1,inth,intx){//1和h分别为数据区的下界和上界inti,j,t；i=1；j=h；while(ij){while(ij&&a[j]=x)j--；while(ij&&a[i]=x)i++；if(ij){t=a[j]；a[j]=a[i]；a[i]=t；}}if(a[i]x)returni；elsereturni－1；}（1）写出该函数的功能；（5分）（2）写一个调用上述函数实现下列功能的算法：对一整型数组b[n]中的元素进行重新排列，将所有负数均调整到数组的低下标端，将所有正数均调整到数组的高下标端，若有零值，则置于两者之间，并返回数组中零元素的个数。（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分)1．B2．D3．B4．C5．B6．C7．C8．A9．C10．A11．B四、算法设计题(3小题,共32分)1．解：voidDel(ListNode*head,inti,intk){node*p,*q;intj;if(i==1)For(j=1;j=k;j++)//删除前k个元素{p=head;//p指向要删除的结点head=head-next;Free(p);}else{p=head;for(j=1;j=i-2;j++)p=p-next;//p指向要删除的结点的前一个结点for(j=1;j=k;j++){q=p-next;//q指向要删除的结点p-next=q-next;free(q);}}}2．解：voidcountnode(bitree*bt,int&count){if(bt!=0){count++;countnode(bt-lchild,count);countnode(bt-rchild,count);}}3．解答：（1）该函数的功能是：调整整数数组a[]中的元素并返回分界值i，使所有＜x的元素均落在a[1..i]上，使所有≥x的元素均落在a[i＋1..h]上。（2）intf(intb[],intn)或intf(intb[],intn){{intp,q；intp,q；p=arrange(b,0,n－1,0)；p=arrange(b,0,n－1,1)；q=arrange(b,p+1,n－1,1)；q=arrange(b,0,p,0)；returnq－p；returnp－q；}}五、填空题(5小题,共10分)1．节省存储空间，降低上溢发生的机率2．0（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中以项点表示事件，以有向边表示活动，边上的权值表示该活动持续的时间，则此带权有向图称为用边表示活动的网(ActivityOnEdgenetwork)，简称AOE网。2．答：线性结构：数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。