试卷编号拟题教研室(或教师）签名乐晓波教研室主任签名
长沙理工大学考试试卷(Ａ卷) ………………………………………………………………………………………………………课程名称（含档次）数据结构A 课程代号08１２00２61５课程编号0０2131
专业计算机相关专业层次(本、专) 本科考试方式(开、闭卷）闭卷
一、应用题(2小题,共8分）
设有一个栈,元素进栈的次序为:A，B，C，D，E，用I表示进栈操作，O表示出栈操作,写出下列出栈的操作序列。
(1)Ｃ，Ｂ，A，D，E(2）A，C,Ｂ,E，D
二、判断正误(5小题,共10分)
1.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。( )
2．一个栈的输入序列为:A,Ｂ，C,Ｄ，可以得到输出序列:C，Ａ，B,D。( )
３.子串“ＡBC”在主串“ＡＡBCAＢCD”中的位置为2。( )
４．设一棵树T可以转化成二叉树BT，则二叉树BＴ中一定没有右子树。( ）
５．调用一次深度优先遍历可以访问到图中的所有顶点。（)
三、单项选择题(1１小题,共２2分)
1.两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素前驱的条件是（)。
Ａ．P->ｎeｘt＝＝Q->next Ｂ.P－>ｎｅxt＝= Q Ｃ．Ｑ->ｎext＝= Ｐ D.P== Ｑ
2.从一个具有n个结点的单链表中查找其值等于x结点时,在查找成功的情况下,需平均比较( )个结点。
A．ｎＢ. n/2 C．（n-１)／2 Ｄ.(n+１）/2
3．如果以链表作为栈的存储结构,则出栈操作时( )
A．必须判别栈是否满 B.必须判别栈是否空
C．必须判别栈元素类型 D.对栈可不做任何判别
4.设输入序列是1、２、3、……、n,经过栈的作用后输出序列的第一个元素是ｎ，则输出序列中第i个输出元素是( )。
Ａｎ－i B ｎ-１-i C n+１-i D不能确定
5．下列说法不正确的是( )
A．串中元素只能是字符 B.串中元素只能是字母
C．串是一种特殊的线性表D．串中可以含有空白字符
6.线索二叉树中某结点Ｒ没有左孩子的充要条件是( )。ﻫA. R.lchild=NULL .B
R．ltag=0 C．R.ltag＝１ D. R.rｃhiｌd=NＵLＬ
7．树最适合用来表示（)。
A.有序数据元素
B.无序数据元素
C.元素之间具有分支层次关系的数据
D.元素之间无联系的数据
８.设有向无环图G中的有向边集合E={<１,2＞,＜2,3>,<３，４＞，＜1,4>},则下列属于该有向图G的一种拓扑排序序列的是（)。
A．1，2，３,４B．2，3,4,1 C.１,4，2，3 D.1,2,4，3
9.设数据结构A=（Ｄ,R)，其中D=｛1,2,3，４｝,R=｛r}，r={<1，2>，<2,3>，<3，4>，＜4，1＞}，则数据结构A是( )。
Ａ线性结构B树型结构 C图型结构 D 集合
10.每个结点只含有一个数据元素,所有存储结点相继存放在一个连续的存储区里,这种存储结构称为（)结构。
Ａ. 顺序存储 B. 链式存储 C. 索引存储D．散列存储
１1.下列叙述中，错误的是()
Ａ.数据的存储结构与数据处理的效率密切相关
Ｂ.数据的存储结构与数据处理的效率无关
C.数据的存储结构在计算机中所占的空间不一定是连续的
D.一种数据的逻辑结构可以有多种存储结构
四、算法设计题(3小题,共３２分)
1.已知一个单链表，编写一个函数从单链表中删除自第ｉ个结点起的ｋ个结点。（11分)
2．设计一个在链式存储结构上统计二叉树中结点个数的算法。(1１分）
３．先阅读下列函数ａｒrange（) ,再做下面(1)和(2)两小题:
int aｒrａｎge(int a[］,ｉnｔ1,ｉnt h,ｉnt x）
{//1和h分别为数据区的下界和上界
int i，ｊ,t;
i=1；j=ｈ；
whｉle(ｉwhilｅ(iwhile(iｉf（i{ t=a[j]；ａ[ｊ]=a[i]；a［i］=t；}
}
if(a[ｉ]else returnｉ-１；
}
（１)写出该函数的功能；(５分）
(2)写一个调用上述函数实现下列功能的算法：对一整型数组ｂ[n]中的元素进行重新排列,将所有负数均调整到数组的低下标端,将所有正数均调整到数组的高下标端，若有零值，则置于两者之间,并返回数组中零元素的个数。（５分）
五、填空题(5小题,共１0分)
1.由两个栈共享一个存储空间的好处是（）
２.设长度为n的链队列用单循环链表表示,若只设尾指针，则出队操作的时间复杂度为（)。
3.设无向图G中顶点数为n，则图Ｇ至少有( )条边，至多有（）条边。
４．在无向图的邻接矩阵中，第ｉ行(列)中“1”的个数是第i个顶点的,矩阵中“１”
的个数的一半是图中的。
5.顺序存储结构中数据元素之间的逻辑关系是由（)表示的,链接存储结构中的数据元素
之间的逻辑关系是由（)表示的。
六、简答题(2小题,共10分)
１．请说明顺序表和单链表各有何优缺点。
2.设指针变量p指向双向链表中结点A,指针变量q指向被插入结点B，要求给出在结点A 的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llｉnk和ｒlink）。
七、名词解释（２小题，共8分)
1.什么是AOE网?
2.简述下列概念：线性结构、非线性结构。
ﻬ长沙理工大学计算机与通信工程学院
２015-201６学年一学期数据结构A期末考试试卷(A卷)
(答案部分）
一、应用题(１小题，共8分)
1．解:(1)IIIOOOＩOIO(2)IＯIIOOIIOO
二、判断正误（5小题，共１０分)
1．（×) 2．（×）3．（√） 4.（√) 5.（×）
三、单项选择题（1１小题,共22分)
