试卷编号拟题教研室（或教师）签名乐晓波教研室主任签名。
长沙理工大学考试试卷（a卷）
课程名称（含档次） 数据结构a 课程代号 0812002615 课程编号 002131
专业计算机相关专业层次（本、专） 本科考试方式（开、闭卷） 闭卷
一、应用题(2小题，共8分)
设有一个栈，元素进栈的次序为：a，b，c，d，e，用i表示进栈操作，o表示出栈操作，写出下列出栈的操作序列。
1）c，b，a，d，e2）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->next b．p->next== q c．q->next== p d．p== q
2．从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（ ）个结点。
a． n b． n/2 c． (n-1)/2 d． (n+1)/2
3．如果以链表作为栈的存储结构，则出栈操作时（ ）
a．必须判别栈是否满 b．必须判别栈是否空。
c．必须判别栈元素类型 d．对栈可不做任何判别。
4．设输入序列是、…n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（ ）
a n-i b n-1-i c n+1-i d 不能确定。
5．下列说法不正确的是（ ）
a．串中元素只能是字符 b．串中元素只能是字母
c．串是一种特殊的线性表 d．串中可以含有空白字符
6．线索二叉树中某结点r没有左孩子的充要条件是（ ）
a． ．b c． d．
7．树最适合用来表示( )
a．有序数据元素 b．无序数据元素。
c．元素之间具有分支层次关系的数据 d．元素之间无联系的数据。
8．设有向无环图g中的有向边集合e=，则下列属于该有向图g的一种拓扑排序序列的是（ ）
a．1，2，3，4 b．2，3，4，1 c．1，4，2，3 d．1，2，4，3
9．设数据结构a=(d，r)，其中d=，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(i while(i=x)j--；
while(i if(i
if(a[i] else return i－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分)
三、单项选择题(11小题，共22分)
1．b 2．d 3．b 4．c 5．b 6．c 7．c 8．a 9．c 10．a 11．b
四、算法设计题(3小题，共32分)
1．解：void del(listnode *head,int i,int k)
node *p,*q;
int j;
if (i==1) for (j=1;j<=k;j++)删除前k个元素。
3．解答：1）该函数的功能是：调整整数数组a中的元素并返回分界值i，使所有＜x的元素均落在a[1..i]上，使所有≥x的元素均落在a[i＋1..h]上。
2）int f(int b,int n) 或 int f(int b,int n)
int p,qint p,q；
p=arrange(b,0,n－1,0p=arrange(b,0,n－1,1)；
q= arrange(b,p+1,n－1,1q= arrange(b,0,p,0)；
return q－preturn p－q；
2019《数据结构》期末试卷A卷
一 本题10分 1 线性表和广义表的主要区别是什么？2 已知广义表 c a,b,a,b a,b a,b 则tail head tail c 二 本题10分 简述二叉树的两种存储结构 顺序存储和链式存储 的数据结构及主要优缺点。在哈夫曼树中，使用哪种存储结构，并说明理由。三 本题10分 一棵二叉树的先...
2019《数据结构》期末试卷B卷
一 本题10分 1 线性表和广义表的主要区别点是什么？已知广义表 c a,b,a,b a,b a,b 则tail head tail c 2 满足什么条件可以实施二分查找？二分查找的时间复杂度是多少？二 本题10分 证明 一棵二叉树的先序序列和中序序列可惟一确定这棵二叉树。三 本题15分 某带权有向...
数据结构20071期末试卷a卷
莆田学院期末考试试卷 a 卷。2007 2008 学年第一学期。课程名称 数据结构适用年级 专业 06 计应 计教 试卷类别开卷 闭卷 学历层次本科考试用时 120分钟 考生注意 答案要全部抄到答题纸上，做在试卷上不给分 一 单项选择 每小题2分，共20分 1 算法的计算量的大小称为计算的 a 可读...