南邮数据结构B期末试卷
更新时间:2023-12-08 11:50:01 阅读量: 教育文库 文档下载
数 据 结 构B 期末试卷
班级 学号 姓名 得分
题号 分数 一 二 三 四 五 六 一、解答题:(共82分)
1、下列程序段或函数的时间复杂度。(10%)
(1) for (int k=0;k for (int j=0;j (3) int Prime(int n) (4)k=1; x=0; { int k=2 , x=(int)sqrt(n) ; do { while (k<=x) { x++; k*=2; if (n % k= =0) break; } k++; } while (k if (k>x) return 1; else return 0; } 2、有A、B、C、D四个元素依次入栈,即入栈序列唯一,问共能得到多少种出栈序列?能否得到以下四种出栈序列:ABCD、BDAC、CBDA、DBAC。对能得到的序列,请写出Push、Pop序列;对不能得到的序列,请说明理由。(6%) 3、矩阵Am*n以行优先方式从1000H处开始存放,元素类型未知,已知:A[2][3]存放在1011H处,A[1][1]存放在1005H处,求元素A[2][0]的存放位置。(6%) 1 4、根据下图所示的树回答问题:(共13%) (1)画出该树等效的二叉树。 (3%) 等效的二叉树 A B C D E F G H I J K L (2)、写出对该树进行先序、后序遍历的结点序列。(4%) (3)用带右链的先序表示法来存储此树,填写下表。(6%) 下标 0 1 2 3 4 5 6 7 8 sibling ltag element 9 10 11 5、假设用于通讯的电文仅由 {ABCDEFGH} 8个字母组成,字母在电文中出现的频率分别为0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10。请画出哈夫曼树并在树中标明编码情况,给出这8个字母的哈夫曼编码,最后求出WPL。(9%) 2 6、对下图,要求:(共13%) 1 6 3 5 7 4 4 5 7 3 4 5 2 5 5 8 8 3 5 6 6 (1)画出它的邻接表。(3%) (2)写出从顶点1到顶点8的四条路径长度为3的简单路径。(2%) (3)分别写出从顶点1出发根据(1)所示的邻接表用深度优先搜索和广度优先搜索遍历图得到的顶点序列。(4%) 3 (4)求出它的一棵最小代价生成树(方法任选),其代价是多少?你所求出的最小代价生成树是唯一的吗?(4%) 7、 一项工程P由P1,P2,P3,P4,P5,P6六个子工程组成,这些工程之间有下列关系:P1>P2, P1>P3, P1>P4, P2>P3, P2>P5, P3>P6, P4>P6, P5>P6。其中符号“>”表示先于关系,例如P1>P2表示只有在工程P1完成之后才能进行P2的工作。请:(7%) (1) 画出该工程的AOV网 (2) 给出工程P的其中四种可能的施工顺序。 8、按如下关键字序列(60,88,107,15,8,23,100)从空树开始建立一棵AVL搜索树,画出建树的步骤以及调整平衡的过程(6%) 4 9、设散列表ht[13],散列函数h(key)=key % 13。采用二次探查法解决冲突,试用关键字值序列:{56,78,14,27,41,70,51,66,24,50,36}建立散列表。(6%) i 0 1 2 3 4 5 6 7 8 9 10 11 12 ht[i] 10、元素序列:{55,71,12,98,4,70,51 } ,请写出用冒泡排序法和2路合并排序法进行排序的各趟排序结果。(6%) 冒泡排序法 2路合并排序法 二、算法填空:(8%) 以下算法实现二叉搜索树的删除,根据给定的关键字k,找到待删除元素后将元素值通过参数e返回,若成功删除则返回true;找不到待删除元素则返回false. template ________ BSTree BTNode q=p; if (k 5
正在阅读:
南邮数据结构B期末试卷12-08
2015宁波鄞州区、北仑区、镇海区、江东区、江北区模拟选择题汇编03-09
中国石油大学(北京)远程教育学院2015年秋季期末考试《 安全管理05-07
江苏省继续开展运输船舶吨位丈量01-21
第十三单元 时间02-27
2011年雏雁英语考试真题05-14
我变成了蜜蜂作文400字07-07
2011年1月襄阳市高三调研英语答案09-16
- exercise2
- 铅锌矿详查地质设计 - 图文
- 厨余垃圾、餐厨垃圾堆肥系统设计方案
- 陈明珠开题报告
- 化工原理精选例题
- 政府形象宣传册营销案例
- 小学一至三年级语文阅读专项练习题
- 2014.民诉 期末考试 复习题
- 巅峰智业 - 做好顶层设计对建设城市的重要意义
- (三起)冀教版三年级英语上册Unit4 Lesson24练习题及答案
- 2017年实心轮胎现状及发展趋势分析(目录)
- 基于GIS的农用地定级技术研究定稿
- 2017-2022年中国医疗保健市场调查与市场前景预测报告(目录) - 图文
- 作业
- OFDM技术仿真(MATLAB代码) - 图文
- Android工程师笔试题及答案
- 生命密码联合密码
- 空间地上权若干法律问题探究
- 江苏学业水平测试《机械基础》模拟试题
- 选课走班实施方案
- 数据结构
- 期末
- 试卷
- 透镜及其应用物理笔记
- 中质协注册黑带考试模拟题 2012年08月(Jack 附答案)
- 插花艺术大专试题
- PEP小学五年级上册英语复习教案 - 图文
- 2015年电类模拟电子技术期末复习题
- 中医内科学试卷1(162学时)
- 分析广告的诉求策略
- 苏教版五年级下册数学 最大公因数 最小公倍数易错题和重点题型
- 名人名言诗词名句
- (认证)软件工程课程设计大纲
- 毕业设计 - zl50装载机驱动桥的设计(设计)
- 误差和分析数据处理习题
- 川大《民法学1017》15春在线作业2 答案
- 某某县龙山新区12号道路工程建设项目可行性研究报告 - 图文
- 浪涌保护器原理分析
- 金工实习考试题库(含答案)
- 戏曲知识
- 中式菜肴的特点及风味流派
- 2018秦淮区一模(含答案)
- 优化纳税服务的几点思考