数据结构-专升本 期末考试试题及参考答案

出题教

教师试做时间李兰取题时间教研室主任

师审

使用班核

出题单位计算机学院考试日期院（部）长

级

考试成绩期望印刷份规定完成时交教务科印刷日

值数间期

学号：姓名：专业：年级：函授站:

OO密。,。

封。。。

线。…

20_〜20_学年第一学期《数据结构》课试卷试卷类型：专升本卷

题号—三四五六七八九十总成绩

得分

阅卷入

一、判断题（20分，每题2分）

1.一个栈的入栈序列是a,b,c,d,e,则dceab是一个不可能的输出序列。（）

2.广义表（a,（a,b）,d,c,（（i,j）,k））的深度是2。（）

3.树是一种重要的线性数据结构。（）

4.调月一次深度优先遍历可以访问到图中的所有顶点。（）

5.分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（）

6.冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（）

7.满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（）

8.线性表的顺序存储结构比链式存储结构更好。（）

9.中序遍历二叉排序树可以得到一个有序的序列。（）

10.快速排序是排序算法中平均性能最好的一种排序。（）

二、选择题（20分，每题2分）

L设一个栈的入栈元素序列为a,b,c,d,c,则不可得到出栈的元素序列有（）。

A.cdcbaB.d?cbaC.dceabD.abcdc

2.又是一棵满二叉树。（）

A.二叉排序树B.深度为5有31个结点的二叉树

C.有15个结点的完全二叉树D.哈夫曼（Huffman）树

3.折半查找有序表（2,5,8.20,25,36,40,60）,若查找元素60,需依次与表中元素进行比较0（）

A.20,36,40,60B.25,40

C.25,40,60D.20,36,40

4.查找哈希（Hash）表,解决冲突的方法有（）0

A.链地址法B.线性探测再散列法C.直接地址法D.除留余数法

5.下面程序的时间复杂为（）

for（i=l,s=0；i<=n；i++）{t=l；for（j=l；j<=i；j++）t=t*j；s=s+t；}

A.O（n）B.O（n2）C.O（n3）D.O（n4）

6.设指针变量p指向单链表中结点A,若删除单链表中结点A,则需要修改指针的操作序列为（）。

A.q=p->next；p->data=q->data；p->next=q->next；free（q）；

B.q=p->next；q->data=p->data；p->next=q->next；free（q）；

C.q=p->next；p->next=q->next；free（q）；

D.q=p->next；p->data=q->data；free（q）；

7.设一组初始关键字记录关键字为（20,15,14,21,36,4（）,10）,则以20为基准记录的一

趟快速排序结束后的结果为（）o

试卷类型：（A）卷考核方式：（闭）卷第1页共5页

试题要求：1.试题后标注本题得分;2.试卷应附有评卷用标准答案，并有每题每步得分标准3试卷必须提前一周送考试中心;4.

考试前到指定地点领取试卷；5.考生不得拆散试卷，否则试卷无效。

8.设连通图G中的边集E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},则从顶点a出发可以得到一种深

度优先遍历的顶点序列为()U

(A)abedfc(B)acfebd(C)aebdfc(D)aedfcb

9.设输入序列是1、2、3、……、n,经过栈的作用后输出序列的第一个元素是n,则输出序列中第i个输出元素是

()o

(A)n-i(B)n-l-i(C)n+l-i(D)不能确定

10设一组初始记录关键字序列为(45,30,55,40,42,85),则以第一个记录关键字45为基准而得到一趟快速排序的

结果是()。

(A)40,42,45,55,80,83(B)42,40,45,80,85,88

(C)42,40,45,55,80,85(D)42,40,45,85,55,80

三、填空题(20分，每空2分)

1.栈是一种特殊的线性表,它允许在表的一端进行操作，栈中元素的进出原则为

_________________O

2.深度为k的二叉树其结点数最多有____个结点。

3.在一棵二叉树中，度为零的结点个数为|一度为2的结点个数为I：,则有।。

4.树的度是指的最大值。

5.在一个有向图中，某个结点的度是指该结点的和之和。

6.在线性表的二分查找法中要求线性表的存储结构必须是采用___________且表中的元素必须是

°

7.在快速排序、堆排序、归并排序中，排序是稳定的。

四、程序填空题(20分，每空4分)

将下面单链表的插入算法补充完整，算法说明：在带有头结点的单链线性表中第i个位置之前插入元素x:

typedef________________

{DataTypedata;

structnode*next;

JLNode,*LinkList;

intlistinsert(LinkListhead,inti,DataTypex)

{LinkListp=head.s

intj=O;

while(p!-NULL&&j<i-l)

j++；

}

if(p==NULL)return(0);

s=inalloc(sizeof(LNodc));

s->data=x;

return(1);

)

五、算法设计题(20分，每题10分)

1.假设在长度大于1的循环链表中，既无头结点，也无头指针，P为指向该链表中某个结点的指针。设计一个算法，删

除P指向结点的前趋结点。

2.已知关键字序列为{46,57,84,32,73,36,15,48,90,20},要求：

(1)构造一棵二叉排序树；

(2)在等概率情况下，该二叉排序树查找成功的平均查找长度。

试题答案

一.判断题

VxxxVVVxVV

二.选择题

CBAABAABCC

三,填空题

1.插入或删除后进先出

2.2k-l

3.112+1

4.树中所有结点度

5.出度入度

6.顺序关键字有序(升序或降序)排列

7.归并

四.程序填空题

structLNode

p=p->next;

(LinkList)

s->noxt=p->next;

p->next=s;

五.算法设计题

3

1.已知指向这个结点的指针是P.那么要删除这个结点的直接前趋结

点，就只要找到一个结点，它的指针域是指向P的直接前趋，然后

用后删结点法，将结点P的直接前趋结点删除即可。

算法如下：

voidDeleteNode(ListNode*p)

{〃删除单循环链表中指定结点的直接前趋结点