广东海洋大学 2015 —— 2016 学年第二学期
《 数据结构与算法 》课程试题
课程号： 19232502
√ 考试
□ 考查
√ A卷
□ B卷
√ 闭卷
□ 开卷
100 题 号 一 二 三 四 五 六 七 八 九 十 总分 阅卷教师 各题分数 20 20 8 10 10 12 10 10 实得分数 密
一、 单项选择题（每小题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. 可执行性、可移植性和可扩充性 C. 确定性、有穷性和稳定性
B. 可执行性、有穷性和确定性
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；
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
b1
封 8A Uni--20--20学年第一学期工作计划9864 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. 对一棵二叉排序树进行 遍历，可以得到一个键值从小到大次序排列的有序序列。 9. for(i=1，t=1，s=0；i<=n；i++) {t=t*i；s=s+t；}的时间复杂度为_________。
10. 对一组记录（54，96，23，15，72，60，45，83）进行直接插入排序，当把第5个记录72插入到有序表时，为寻找插入位置需要比较 次。
三、（8分）假设用于通讯的电文仅由8个字母A、B、C、D、E、F、G、H组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10，请为这8个字母设计哈夫曼编码。
b2
8A Uni--20--20学年第一学期工作计划9864
四、（10分）给定关键码集合｛25，21，34，24，64，41，45｝，设定装填因子为0.7，请给出除留余数法的散列函数，画出采用线性探测法处理冲突构造的散列表，并计算查找成功的平均查找长度。
五、（10分）已知图G如下所示，根据Prim算法，构造最小生成树。（要求给出生成过程）
v08v2242v6v3756v448v17v58v7
b3
8A Uni--20--20学年第一学期工作计划9864
六、（12分）已知数据序列为（15, 4, 8, 19, 6, 13, 23），写出直接插入排序及堆排序每一趟的结果。
b4
8A Uni--20--20学年第一学期工作计划9864
七、（10分）写出在顺序存储结构下将线性表逆转的算法，要求使用最少的附加空间。
八、（10分）设待排序的记录序列用单链表作存储结构，试写出简单选择排序算法。
鞠躬尽瘁，死而后已。——诸葛亮
b5
因篇幅问题不能全部显示，请点此查看更多更全内容