数据结构试卷2016A
更新时间:2024-03-11 17:00: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.线性表L在( )情况下适用于使用链式结构实现.
A.需经常修改L中的结点值 B. 需不断对L进行删除插入 C. L中含有大量的结点 D. L中结点结构复杂
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. 对一棵二叉排序树进行 遍历,可以得到一个键值从小到大次序排列的有序序列。
9. for(i=1,t=1,s=0;i<=n;i++) {t=t*i;s=s+t;}的时间复杂度为_________。
第 2 页 共 6 页
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个字母设计哈夫曼编码。
四、(10分)给定关键码集合{25,21,34,24,64,41,45},设定装填因子为0.7,请给出除留余数法的散列函数,画出采用线性探测法处理冲突构造的散列表,并计算查找成功的平均查找长度。
第 3 页 共 6 页
五、(10分)已知图G如下所示,根据Prim算法,构造最小生成树。(要求给出生成过程)
v08v2242v6v3756v448v17v58v7
第 4 页 共 6 页
六、(12分)已知数据序列为(15, 4, 8, 19, 6, 13, 23),写出直接插入排序及堆排序每一趟的结果。
七、(10分)写出在顺序存储结构下将线性表逆转的算法,要求使用最少的附加空间。
第 5 页 共 6 页
八、(10分)设待排序的记录序列用单链表作存储结构,试写出简单选择排序算法。
第 6 页 共 6 页
正在阅读:
数据结构试卷2016A03-11
2022年高考数学大一轮复习 空间点、直线、平面之间的位置关系课04-18
多项式的加法和乘法06-01
院自律部工作计划(共10篇)06-21
2018年中国生物质能源行业市场投资规划深度分析报告目录03-08
30万吨玉米深加工项目可行性分析报告04-27
物理九年级易错题有解析03-22
完善行政决策听证制度的思考04-06
- 小学生造句大全
- 增压泵投资项目可行性研究报告(模板)
- 高中语文人教版粤教版必修1-5全部文言文知识点归纳
- 两学一做专题民主生活会组织生活会批评与自我批评环节个人发言提
- 管理处环境保洁工作操作标准作业指导书
- 2012六一儿童节活动议程 - 图文
- 移树申请报告
- 《贵州省市政工程计价定额》2016定额说明及计算规则
- 计算机长期没有向WSUS报告状态
- 汉语拼音教学策略研究
- 发展西部领先的航空货运枢纽
- 司法所上半年工作总结4篇
- 如何提高银行服务水平
- 发电厂各级人员岗位职责
- 丰田汽车的外部环境分析
- 2017—2018年最新冀教版四年级数学下册《混合运算》教案精品优质
- 中建八局样板策划 - 图文
- 戚安邦《项目管理学》电子书
- 2015年高级项目经理笔记
- 弯桥的设计要点
- 数据结构
- 试卷
- 2016A
- 滴胶织带市场现状调研及发展前景分析报告(目录)
- 人教版五年级上册语文期中试卷1
- 注:剪羊毛教案湘教版音乐三年级下册
- 工业产品生产许可证核查人员管理规定(草案)
- 山东省郯城三中八年级语文上册《小石潭记》教案2 新人教版 - 图
- 中小型局域网试卷
- 2012年度浙江省会计从业资格考试试卷《会计基础》
- 关于举办潍坊市第四期中小学校长高级研修班的通知
- 走出写作障碍论文
- 关于融资性担保公司设立(确认)和变更工作有关事项的通知
- 韩语基础语法—总结
- 第2章 习题与思考题
- 《子路、曾皙、冉有、公西华侍坐》教案
- 高等数学方明亮版第十章答案
- 优品课件之苏教版三年级语文下册全册教案
- 机动车驾驶人考试工作规范
- 《财务报告分析》三个阶段测试卷参考答案(4)
- 体悟诗情,解读意象
- 杨浦区商务服务和基础性服务业发展十二五规划 - 图文
- 2011中考物理真题分类汇编:欧姆定律(200套) - 图文