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

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->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．设输入序列是1、2、3、 、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（ ）。

A n-i B n-1-i C n+1-i D 不能确定

5．下列说法不正确的是（ ）

A．串中元素只能是字符 B．串中元素只能是字母

C．串是一种特殊的线性表 D．串中可以含有空白字符

2015-2016学年一学期数据结构A期末考试试卷(A卷)

6．线索二叉树中某结点R没有左孩子的充要条件是（ ）。

A． R.lchild=NULL ．B R.ltag=0 C． R.ltag=1 D． R.rchild=NULL

7．树最适合用来表示( )。

A．有序数据元素 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，3 9．设数据结构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）两小题：

int arrange(int a[],int 1,int h,int x)

{//1和h分别为数据区的下界和上界

int i,j,t；

i=1；j=h；

while(i<j){

while(i<j && a[j]>=x)j--；

while(i<j && a[i]<=x)i++；

if(i<j)

{ t=a[j]；a[j]=a[i]；a[i]=t；}

}

if(a[i]<x) return i；

else return i－1；

2015-2016学年一学期数据结构A期末考试试卷(A卷)

}

（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卷)

长沙理工大学计算机与通信工程学院

2015-2016学年一学期数据结构A期末考试试卷(A卷)

（答案部分）

一、应用题(1小题,共8分)

1．解：（1）IIIOOOIOIO （2）IOIIOOIIOO

二、判断正误(5小题,共10分)

1．（×） 2．（×） 3．（√） 4．（√） 5．（×）

三、单项选择题(11小题,共22分)

1．B 2．D 3．B 4．C 5．B 6．C 7．C 8．A 9．C

四、算法设计题(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个元素

{

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; …… 此处隐藏：2339字，全部文档内容请下载后查看。喜欢就下载吧 ……