数据结构试卷2016A.doc

《数据结构试卷2016A.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、GDOU-B-11-302班级：姓名：学号：试题共6页加白纸1张密封线广东海洋大学2015——2016学年第二学期《数据结构与算法》课程试题课程号：19232502√考试√A卷√闭卷□考查□B卷□开卷题号一二三四五六七八九十总分阅卷教师各题分数202081010121010100实得分数一、单项选择题（每小题2分，共20分）1.以下数据结构中哪一个是非线性结构？()A.队列B.栈C.线性表D.二叉树2.判断一个循环队列Q（最多n个元素）为满的条件是（）。A.Q->rear==Q->frontB.Q->rear==Q->front+1C.Q->front==(

2、Q->rear+1)%nD.Q->front==(Q->rear-1)%n3.计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（）等5个特性.A.可执行性、可移植性和可扩充性B.可执行性、有穷性和确定性C.确定性、有穷性和稳定性D.易读性、稳定性和确定性4．线性表Ｌ在（）情况下适用于使用链式结构实现.A．需经常修改Ｌ中的结点值B.需不断对Ｌ进行删除插入C.Ｌ中含有大量的结点D.Ｌ中结点结构复杂5.设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）.A.q=p->next；p->data=q->data

3、；p->next=q->next；deleteq；B.q=p->next；q->data=p->data；p->next=q->next；deleteq；C.q=p->next；p->next=q->next；deleteq；D.q=p->next；p->data=q->data；deleteq；第6页共6页6.设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发不可以得到一种深度优先遍历的顶点序列为（）.A.abedfcB.acfebdC.aebdfcD.aedfcb7.对n个记录的文

4、件进行快速排序，所需要的最好时间是（）.A.O（1）B.O（n）C.O()D.O（n2）8.设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）.A.O(n)B.O()C.O(1)D.O(n2)9.设某散列表的长度为100，散列函数H(k)=k%P，则P通常情况下最好选择（）.A.99B.97C.91D.9310.设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（）方法可以达到此目的。A．快速排序B.插入排序C.归并排序D.堆排序二、填空题（每小题2分，共20分）1．从逻辑关系上讲，数据结构主要

5、分为_________、__________、和___________。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、______________。6.带头结点的单链表head为空的条件是。7.解决散列表冲突的两种方法是________________和__________________。8.对一棵二叉排序树进行第6页共6页遍历，可以得到一个键值从小到大次序排列的有序序列。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

7、、B、C、D、E、F、G、H组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10，请为这8个字母设计哈夫曼编码。四、（10分）给定关键码集合｛25，21，34，24，64，41，45｝，设定装填因子为0.7，请给出除留余数法的散列函数，画出采用线性探测法处理冲突构造的散列表，并计算查找成功的平均查找长度。第6页共6页五、（10分）已知图G如下所示，根据Prim算法，构造最小生成树。（要求给出生成过程）第6页共6页六、（12分）已知数据序列为（15,4,8,19,6,13,23），写出直接插入排序及

8、堆排序每一趟的结果。七、（10分）写出在顺序存储结构