《数据结构》期末考试及答案
更新时间:2023-10-02 13:39:01 阅读量: 综合文库 文档下载
- 数据结构期末考试题推荐度:
- 相关推荐
位号:
《数据结构》 期末考试试卷
考生注意:1.本试卷满分100分。
(C)、各叶子结点的带权路径长度之和 (D)、根结点的值 10.线索二叉链表是利用( )域存储后继结点的地址。 (A)、lchild (B)、data (C)、rchild (D)、root 二、
填空题(每题2分,共计14分)
1.逻辑结构决定了算法的 ,而存储结构决定了算法的 。 2.栈和队列都是一种 的线性表,栈的插入和删除只能在 进行。 3.线性表(a1,a2,…,an)的顺序存储结构中,设每个单元的长度为L,元素ai的存储地址LOC(ai)为
座 密 : 号 学 封 :业 专 : 名姓 线 :站授函 2.考试时间90分钟。
3.卷面整洁,字迹工整。 4.已知一双向链表如下(指针域名为next和prior): 4.填写内容不得超出密封线。
x y
总分 题号 一 二 三 四 五 六 q 核分人 题分 20 14 66 p e
复查人 得分 现将p所指的结点插入到x和y结点之间,其操作步骤为: ; ; ; ;
5.n个结点无向完全图的的边数为 , 一、 单项选择题(每题2分,共计20分)
1.对于一个算法,当输入非法数据时,也要能作出相应的处理,这种要求称为( )。 n个结点的生成树的边数为 。 (A)、正确性 (B). 可行性 (C). 健壮性 (D). 输入性
6.已知一有向无环图如下: 2.设S为C语言的语句,计算机执行下面算法时,算法的时间复杂度为( )。
B for(i=n-1;i>=0;i--)
F D for(j=0;j
2
(A)、n (B). O(nlgn) (C). O(n) (D). O(n)
E 3.折半查找法适用于( )。
任意写出二种拓扑排序序列: 、 。
(A)、有序顺序表 (B)、有序单链表
7.已知二叉树的中序遍历序列为BCA,后序遍历序列为CBA,则该二叉树的先序遍历序列(C)、有序顺序表和有序单链表都可以 (D)、无限制 为 ,层序遍历序列为 。
4.顺序存储结构的优势是( )。
(A)、利于插入操作 (B)、利于删除操作 三、 应用题(每题11分 共计66分)
(C)、利于顺序访问 (D)、利于随机访问
1.设散列函数H(k)=k % 13,设关键字系列为{22,12,24,6,45,7,8,13,21},要求用线性探测法处理冲5.深度为k的完全二叉树,其叶子结点必在第( )层上。
突。(6分)
(A)、k-1 (B)、k (C)、k-1和k (D)、1至k
(1) 构造HASH表。
6.具有60个结点的二叉树,其叶子结点有12个,则度过1的结点数为( )
(2) 分别求查找成功和不成功时的平均查找长度。 (A)、11 (B)、13 (C)、48 (D)、37
7.图的Depth-First Search(DFS)遍历思想实际上是二叉树( )遍历方法的推广。 (A)、先序 (B)、中序 (C)、后序 (D)、层序 8.在下列链队列Q中,元素a出队的操作序列为( )
front a b c d ∧
Q (A)、p=Q.front->next; p->next= Q.front->next; (B)、p=Q.front->next; Q.front->next=p->next; (C)、p=Q.rear->next; p->next= Q.rear->next; (D)、p=Q->next; Q->next=p->next; 9. Huffman树的带权路径长度WPL等于( )
(A)、除根结点之外的所有结点权值之和 (B)、所有结点权值之和
2. 给定表(19,14,22,15,20,21,56,10).(8分)
第 1 页 共 3 页
(1) 按元素在表中的次序,建立一棵二叉排序树
(2) 对(1)中所建立的二叉排序树进行中序遍历,写出遍历序列。 (3) 画出对(2)中的遍历序列进行折半查找过程的判定树。
3. 已知二个稀疏矩阵A和B的压缩存储三元组表如下: A B i 1 2 2 4 5 j 3 4 5 2 2 V -5 6 2 -1 9
i 2 3 4 5 5 j 5 3 1 2 5 V 2 7 3 -9 8 A B C D E F
A??651????B?6??53???C?5??7?2???D?157?64?E??3?6?6???F????246???(1)求从顶点A开始的最小生成树。
(2)分别画出以A为起点的DFS生成树和BFS生成树。
6.已知数据六个字母及在通信中出现频率如下表: A 0.15 B 0.15 C 0.1 D 0.1 E 0.2 F 0.3 写出A-B压缩存储的三元组表。(5分)
4. 已知一维数组中的数据为(18,12,25,53,18), 试写出插入排序(升序)过程。并指出具有n个元素的插入排序的时间复杂度是多少?(5分)
5. 已知一网络的邻接矩阵如下,求从顶点A开始的最小生成树。(8分,要有过程)
把这些字母和频率作为叶子结点及权值,完成如下工作(7分,要有过程)。
(1) 画出对应的Huffman树。 (2) 计算带权路径长度WPL。
(3) 求A、B、C、D、E、F的Huffman编码。
第 2 页 共 3 页
《数据结构》期末考试答案
选择题(每题1分)
1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 一、填空题 1.设计、实现 2.特殊、栈顶
3.LOC(a1)+(i-1)*L
4.p->next=q->next;q->next->prior=p;
5 5 8 4、 初始关键字: [18] 12 25 53 18 第 一 趟:[12 18] 25 53 18 第 二 趟:[12 18 25] 53 18 第 三 趟:[12 18 25 53] 18 第 四 趟:[12 18 18 25 53] (4分)
O(n2)(1分)。 5、7分 (1)4分 A
q->next=p;p->prior=q; B 1 C 5.n(n-1)/2、n-1
3 2 6.ADCBFEG、ABCDEFFG 5 D 4 7.ABC、ABC E F 二、应用题
1 (1)Hash表(4分) 地址 0 1 2 3 4 5 6 7 8 9 10 11 12 关键安 13 21 6 45 7 22 8 24 12 探测次数 1 7 1 2 3 1 3 1 1 (2)查找成功的平均查找长度:(1分) (5*1+1*2+2*3+1*7)/9=20/9
查找不成功的平均查找长度:(1分)
(2+1+9+8+7+6+5+4+3+2+1)/13= 2(1)、构造(3分) 19 14 22 10 15 20 56 21
(2)、10 14 15 19 20 21 22 56(2分) (3)、(3分)
3、(5分,每行0.5) i j v 1 3 -5 2 4 6 3 3 7 4 1 3 4 2 -1 5 2 18
(2)4分
6、(1) 3分 E F A B C D (2)WPL=0.1*3+0.1*3+0.2*2+0.15*3+0.15*3+03*21= (3)A:010 B:011 C:110 D:111 E:00 F;10
第 3 页 共 3 页
(1分) 3分) (
正在阅读:
《数据结构》期末考试及答案10-02
基于51单片机的循迹避障小车的设计05-20
看图列式09-28
厂区室外雨水排水管道安装施工方案详解12-10
2014年浙江省普通高校招生理科第二批志愿填报成绩分段表参考11-04
白酒黄金期已过01-23
七年级数学下册10数据的收集整理与描述单元测试六数据的收集整理03-29
湖北第二师范建筑经济管理专业毕业设计01-24
数学与应用数学专业毕业论文参考题目04-16
关于撤销兴盛乡设立兴盛镇的请示09-30
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 数据结构
- 期末
- 答案
- 考试
- 软件项目管理实验三 项目规模成本估算 - 软件0801何飞
- 补虚药作业2
- 华中农业大学大一上英语期末试题答案
- 2018年上半年公共卫生整改措施
- 农大项目管理与评估在线作业1
- 21-25套生物化学习题
- 张登中学安全工作自查报告
- 2011年1月自考计算机应用部分试题答案(网友版)
- 金蝶KIS专业版现金流量项目指定分析
- 不含括号的三步混合运算 详细教案
- 一、有效课堂提问的涵义
- 苏教版小学科学五年级上册《简单电路》教学实录1
- 天津科技大学PCB教学指导书 - 图文
- 4A Unit6 At the snack bar 单元教案
- 基于多孔梁的有限元分析 - 图文
- 《它们吸水吗》教学设计
- 新视野第三版读写2单元作文范文
- 五年级上册英语句型归类
- 高中语文古汉语中常见的单音节和双音节词古今异义专题辅导
- 西南交大大物作业答案