数据结构试卷2016A

更新时间：2023-12-27 11:20:01 阅读量：教育文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

班级：姓名密：学号：封试题共线 6 页加白纸 1 张

GDOU-B-11-302

广东海洋大学 2015 —— 2016 学年第二学期

《数据结构与算法》课程试题

√ 闭卷

课程号： 19232502

√ 考试

√ A卷

□ 考查

□ B卷

□ 开卷

题号一二三四五六七八九十总分阅卷教师各题分数 20 20 8 10 10 12 10 10 100 实得分数

一、单项选择题（每小题2分，共20分） 1. 以下数据结构中哪一个是非线性结构？( )

A. 队列 B. 栈 C. 线性表 D. 二叉树 2. 判断一个循环队列Q（最多n个元素）为满的条件是（）。 A. Q->rear= =Q->front

B. Q->rear= =Q->front+1

C. Q->front= =(Q->rear+1) % n

D. Q->front= =(Q->rear-1)% n

3. 计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（）等5个特性.

A. 可执行性、可移植性和可扩充性

B. 可执行性、有穷性和确定性

C. 确定性、有穷性和稳定性

D. 易读性、稳定性和确定性

4．线性表Ｌ在（）情况下适用于使用链式结构实现.

A．需经常修改Ｌ中的结点值 B. 需不断对Ｌ进行删除插入 C. Ｌ中含有大量的结点 D. Ｌ中结点结构复杂

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

A. q=p->next；p->data=q->data；p->next=q->next；delete q； B. q=p->next；q->data=p->data；p->next=q->next；delete q； C. q=p->next；p->next=q->next；delete q； D. q=p->next；p->data=q->data；delete q；

第 1 页共 6 页

6. 设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发不可以得到一种深度优先遍历的顶点序列为（）. A. abedfc B. acfebd C. aebdfc D. aedfcb 7. 对n个记录的文件进行快速排序，所需要的最好时间是（）. A. O（1） B. O（n） C. O(nlog2n) D. O（n2）

8. 设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）. A. O(n) B. O(nlog2n) C. O(1) D. O(n2)

9. 设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（）. A. 99

B. 97

C. 91

D. 93

10. 设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（）方法可以达到此目的。

A．快速排序 B. 插入排序 C. 归并排序 D.堆排序二、填空题（每小题2分，共20分）

1．从逻辑关系上讲，数据结构主要分为_________、__________、和___________。

2. 设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过次比较。

3. 设连通图G中有n个顶点e条边，则对应的最小生成树上有___________条边。 4. 设一棵二叉树的中序遍历序列为BDCA，后序遍历序列为DBAC，则这棵二叉树的前序序列为____________________。

5. 设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则以d=4为增量的一趟希尔排序结束后的结果为________________________ _____。 6. 带头结点的单链表head为空的条件是。

7. 解决散列表冲突的两种方法是________________和__________________。 8. 对一棵二叉排序树进行遍历，可以得到一个键值从小到大次序排列的有序序列。