哈尔滨工业大学数据结构与算法历年考题汇总 - 图文
更新时间:2023-11-01 11:11:01 阅读量: 综合文库 文档下载
[期末] 2005数据结构与算法试卷
试卷类型: 期末 试卷年份: 05 授课教师: 廖明宏 有无答案: 无答案
哈工大2005年春季学期
数据结构与算法 试 卷
一.填空题(每空1分,共10分)
1.假定对线性表(38,25,74,52,48)进行散列存储,采用H(K)=K %7作为散列函数,若分别采用线性探查法和链接法处理冲突,则对各自散列表进行查找的平均查找长度分别为_______和________。 2.假定一组记录的排序码为(46,79,56,38,40,80),对其进行归并排序的过程中,第二趟归并后的结果为________________。 3.在堆排序的过程中,对任一分支结点进行调整运算的时间复杂度为________,整个堆排序过程的时间复杂度为________。 4.有向图的邻接矩阵表示法中某一行非0元素的个数代表该顶点的 ,某一列非0元素的个数是该顶点的 。
5.对于下面的带权图G3,若从顶点v0出发,则按照普里姆(Prim)算法生成的最小生成树中,依次得到的各条边为______________。
6.由带权为3,9,6,2,5的5个叶子结点构成一棵哈夫曼树,则带权路径长度为
7.由三个结点构成的二叉树,共有 种不同结构。
二.选择题(每题1分,共10分)
1.快速分类在 的情况下不利于发挥其长处.
A. 待分类的数据量太大 B. 待分类的数据相同值过多
C. 待分类的数据已基本有序 D. 待分类的数据值差过大.
2.两路归并排序中,归并的趟数是 。
A. O(n) B. O(log2n) C. O(nlog2n) D. O(n2)
注意行为规范
遵守考场纪律
第1页,共6页
3.对外部分类的K路平衡归并,采用败者树时,归并的效率与K 。
A. 有关 B.无关 C.不能确定 D. 都不对
4.对于一个索引顺序文件,索引表中的每个索引项对应主文件中的 。
A. 一条记录 B.多条记录
C. 所有记录 D.三条以上记录
5..若线性表采用顺序存储结构,每个元素占用4个存储单元,第一个元素的存储地址为100,则第12个元素的存储地址时 。
A.112 B.144 C.148 D.412
6.若频繁地对线性表进行插入和删除操作,该线性表应该采用 存储结构。
A.散列 B.顺序 C.链式 D.索引
7.若长度为n的非空线性表采用顺序储存结构,删除表中第i个数据元素,需要移动表中 个数据元素。
A.n+i B.n-i C.n-i+1 D.n-i-1
8.栈和队列的相同之处是 。
A.元素的进出满足先进后出 B.元素的进出满足后进先出
C.只允许在端点进行插入和删除操作 D.无共同点
9.在一棵高度为k的二叉树中,最多含有( )个结点。
A.2k-1 B.2k-l C.2k-1 D.k
10.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序( )。
A.发生改变 B.不发生改变 C.不能确定 D.以上都不对
三.判断题,正确的在括号内画∨,错误的在括号内画╳。
(每小题1分,共10分)
1.树的父链表示就是用数组表示树的存储结构。( ).
2.任何二元树都唯一对应一个森林,反之亦然。.( )
3.有向图的邻接矩阵一定不是对称的。( )
4.AOE网中,只有一个入度为0的顶点(起始点),只有一个出度为0的顶点(结束点)。( )
5.关键路径可能不只一条,但缩短某一关键路径一定能够缩短工期。( )
6.顺序存储方式只能用于存储线性结构。( )
7.用循环链表作为存储结构的队列就是循环队列。( )
8.倒排文件的主要优点为便于节省空间( )。
9.一组记录的关键字为(46,79,56,38,40,84),则利用快速排序的方法,以第一个记录为基准元素得到的一次划分结果为40,38,46,56,79,84( )。
10. 算法分析的目的是分析算法的易读性( )。
四.简答题
1.简述如何用两个栈模拟一个队列的入队和出队操作.(6分)
2. 对于图G5所示的树:(7分)
(1) 写出先根遍历得到的结点序列;
(2) 写出按层遍历得到的结点序列;
(3) 画出转换后得到的二元树
图G5
五.算法设计
1.设二元树采用左右链存储,写出后序遍历该二元树的非递归算法。(12分)
2.设图中各边上的权值均相等,试以邻接表为存储结构,写出求源点Vi到Vj的最短路径算法。 (15分)..
正在阅读:
哈尔滨工业大学数据结构与算法历年考题汇总 - 图文11-01
复方制剂在高血压治疗中的地位04-13
15年电子工程师考证题(参考答案)07-04
路由基本概念及静态路由配置实验报告11-27
3月28建筑立面设计108-06
第一章计算机网络概述整理05-30
广州白云国际机场迁建工程场内10kV供电管网预埋工程施工组织设计03-04
办公室人员劳动合同04-03
(一)股票合作协议书03-03
- 人教新课标必修4 Unit2 Working the land名师导航
- 毕业生“校漂族”大行其道 - 0
- 江苏各市中考作文题出炉 - 0
- 暑期精品班 - 三角形 - 图文
- 情人节送什么礼物好??超强礼物已抵达
- 工程项目管理制度1
- 第四次业务学习 2016
- 会计要素与会计科目
- 欠发达地区小企业会计准则运用问题研究
- 一级锅炉水G4题库
- BBD双进双出筒式磨煤机安装使用说明书 SM-1
- 初一数学有理数教案
- 渝北区房地产评估市场调研报告
- iWebMall 数据字典
- 2018年小学入学教育工作计划
- 计量专业实务与案例分析 - 模拟题三 - 2013年版
- 启示录讲义
- 路基灰土改良(方案)
- 人行反洗钱岗位准入培训测试题集
- 2015电大《学前儿童发展心理学》期末试题及答案
- 哈尔滨工业大学
- 历年考题
- 数据结构
- 算法
- 汇总
- 图文
- 2018年中考历史总复习第二编热点专题突破专题7大国崛起习题
- 新实完小教导处管理制度
- Pxr-qz - k在2011年度选调生岗前培训会上的讲话
- 最新部编人教版二年级语文下册13、画杨桃教案(教学设计、导学案)
- 沪教版八年级(下)数学第二十章一次函数课课练及单元测试卷一和参考答案
- 2016-2022年中国鞋帽行业市场运营态势报告(目录) - 图文
- 区委书记在纪委全会上的讲话
- 深圳市城市更新单元规划制定计划申报指引 - 图文
- 光伏AGC系统操作说明 - 图文
- 第四讲 中心词分析法与层次分析法
- 新视野大学英语第三版第四册Unit 2 Secrets to Beauty 教案
- 2019-2020学年度最新幼儿园教育工作计划 - 图文
- 09-10学年第1学期机械设计试卷(A卷)标答及评分标准
- 数字信号处理试卷及答案
- 北京市雕塑工艺品企业名录140家
- 《俄罗斯》精品教案(第1课时)
- 云南高中英语会考模拟试卷六
- 青卫医妇字〔2011〕22号转发卫生部办公厅
- 校园欺凌预防的专题会议记录
- 讲话稿:市委常委、常务副市长在市政府系统建议提案办理工作交办会上的讲话