试卷编号拟题教研室（或教师）签名乐晓波教研室主任签名长沙理工大学考试试卷（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．每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储区里...