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

《2015-2016 数据结构A期末试卷(A卷)【含答案】 》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、试卷编号拟题教研室（或教师）签名乐晓波教研室主任签名长沙理工大学考试试卷（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、，而链表适宜于进行随机存取。()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->next  B．P->next==Q    C．Q->next==P      D．

3、P==Q 2．从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（  ）个结点。 A．n        B．n/2         C．(n-1)/2        D．(n+1)/2 3．如果以链表作为栈的存储结构，则出栈操作时（ ）  A．必须判别栈是否满　　　　　B．必须判别栈是否空  C．必须判别栈元素类型　　　　D．对栈可不做任何判别 4．设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（ ）。    A n-i                 

4、    B n-1-i              C n+1-i                   D 不能确定5．下列说法不正确的是（   ）  A．串中元素只能是字符　　　　B．串中元素只能是字母   C．串是一种特殊的线性表  　　D．串中可以含有空白字符 6．线索二叉树中某结点R没有左孩子的充要条件是（　　）。A．R.lchild=NULL     ．BR.ltag=0      C．R.ltag=1      D．R.rchild=NULL7．树最适合用来表示(     )。A．有序数据元素                  

5、   　　　　　B．无序数据元素C．元素之间具有分支层次关系的数据　　D．元素之间无联系的数据8．设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是（ ）。    A．1，2，3，4         B．2，3，4，1              C．1，4，2，3         D．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线性

6、结构        B 树型结构    C 图型结构        D 集合10．每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储区里，这种存储结构称为（   ）结构。    A. 顺序存储       B. 链式存储        C. 索引存储       D. 散列存储 11．下列叙述中，错误的是（）A．数据的存储结构与数据处理的效率密切相关B．数据的存储结构与数据处理的效率无关C．数据的存储结构在计算机中所占的空间不一定是连续的D．一种数据的逻辑结构可以有多种存储结构 四、算法设计题(3小题,共32分)1．已知一个

7、单链表，编写一个函数从单链表中删除自第i个结点起的k个结点。（11分）2．设计一个在链式存储结构上统计二叉树中结点个数的算法。（11分）3．先阅读下列函数arrange()，再做下面（1）和（2）两小题：   intarrange(inta[],int1,inth,intx) {//1和h分别为数据区的下界和上界   inti,j,t；    i=1；j=h；     while(i=x)j--；        while(i

8、j)          { t=a[j]；a[j]=a[i]；a[i]=t；}     }        if(a[i]