![北华大学计算机科学技术学院2012数据结构试题_第1页](http://file1.renrendoc.com/fileroot_temp2/2020-12/1/3e74638a-09e9-4f08-8729-0d589f217031/3e74638a-09e9-4f08-8729-0d589f2170311.gif)
![北华大学计算机科学技术学院2012数据结构试题_第2页](http://file1.renrendoc.com/fileroot_temp2/2020-12/1/3e74638a-09e9-4f08-8729-0d589f217031/3e74638a-09e9-4f08-8729-0d589f2170312.gif)
![北华大学计算机科学技术学院2012数据结构试题_第3页](http://file1.renrendoc.com/fileroot_temp2/2020-12/1/3e74638a-09e9-4f08-8729-0d589f217031/3e74638a-09e9-4f08-8729-0d589f2170313.gif)
![北华大学计算机科学技术学院2012数据结构试题_第4页](http://file1.renrendoc.com/fileroot_temp2/2020-12/1/3e74638a-09e9-4f08-8729-0d589f217031/3e74638a-09e9-4f08-8729-0d589f2170314.gif)
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、北华大学计算机科学技术学院2012-2013学年第一学期 数据结构 课程期末考试试卷(3)题号一二三四总分得分评卷人核分:一、填空题(每小题2分,共14分)1.数据元素之间的关系有四种,包括集合、 线性结构 、树形结构和图状结构。2.二维数组A34采用行序为主方式存储,每个元素占2个存储单元,并且A10的存储地址是1000,则A22的地址是_1012_。3. 有一个长度为n的顺序表,若在第i个元素(0in-1)之后插入一个元素时,需向后移动_n-i-1_个元素。4.已知有n个结点的完全二叉树,如果按照从自上到下、从左到右从1开始顺序编号,若第i个结点有右孩子,则其右孩子结点的编号为_2n+1_
2、。5. 设某棵二叉树中度数为0的结点数为N0,度数为1的结点数为N1,则该二叉树中度数为2的结点数为 N0N1 。6. 设有向图G中有n个顶点,并有e条有向边,所有的顶点入度数之和为d,则e和d的关系为_。7. _中序_遍历二叉排序树中的结点可以得到一个递增的关键字序列(填先序、中序或后序)。二、选择题(每题2分,共16分)1.下面算法的时间复杂度为_A_。for(i=0; im; i+) for(j=0; jt; j+) cij=0;for(i=0; im; i+) for(j=0; jt; j+) for(k=0; knext=0C. head-next=headD. head!=04.
3、设一棵完全二叉树中有65个结点,则该完全二叉树的深度为 B 。A. 8B. 7C. 6D. 5 5. 如果在表示树的孩子兄弟链中有6个空的左指针域,7个空的右指针域,5个结点左、右指针域都为空,则该树中叶的个数_。A. 有7个 B. 有6个 C. 有5个 D. 不能确定6. 设有向图G中的有向边的集合E=,则不是该图的一个拓扑序列的为_。A. 1,2,4,6,5,3 B. 1,4,6,5,2,3 C. 1,4,2,6,5,3 D.1,4,6,2,3,57. 设无向图G中的边的集合E=(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c),则从顶点a出发进行深度优先遍
4、历可以得到的一种顶点序列为 。A. aedfcbB. acfebdC. aebcfdD. aedfbc8.如右侧图所示的一棵二叉排序树其成功的平均查找长度为_。A. 21/6 B. 15/6 C. 18/7 D. 28/7三、应用题(14题每题6分,56题每题8分,共40分)1.一个输入序列是123,请写出栈的一个输出序列和队列的输出序列。并总结栈和队列区别。 90302050408070大题得分1题得分2题得分2.假设字符a,b,c,d,e,f,g的使用频率分别是0.18,0.13,0.12,0.08,0.11,0.16,0.26 (1)画出赫夫曼树,要求左子树为权值最小的结点 (2)写出a
5、,b,c,d,e,f,g的赫夫曼编码,要求左子树编码为0,并写出accee的编码。3. 已知一个二叉树的中序和后序遍历序列分别为CDBAEGF和DCBGFEA,请画出此二叉树,并写出其先序序列。4.已知关键字序列49 38 65 97 76 13 27,写出执行快速排序算法(以第一个关键字为枢轴元素)前三趟升序排序的关键字序列的状态。3题得分4题得分5.已知AOV网如下,按关键路径算法: (1)找出其关键路径。 (2)计算:Ve (F)、Vl (F)(3)设弧称为活动a, 计算:e (a)和l(a)(4)完成此工程最少需要多少天。6. 假设有一批关键字序列18,75,60,23, 30,33,
6、46,20,给定哈希函数H(k)=k % 13,存贮区的内存地址从0到15,则计算每个关键字存储序号,并画出该哈希表。 四、算法设计(每小题10分,共30分)1. 已知顺序表的存储结构如下,请在空格上填写适当的语句,完成对顺序表L作一趟Shell排序插入算法,假定原顺序表L中元素按升序排序。typedef struct int *elem, length, listsize; SqList; void ShellInsert(SqList &L, int dk) for(i=dk+1;i0<(L.r0.key,L.rj.key); ) = L.rj; L.rj+dk = ; EAFDHCG
7、B335647449108865题得分6题得分大题得分1题得分2题得分2.线性表的单链表存储结构如下,请在空格上填写适当的语句,完成单链表的删除算法。typedef struct LNode Status ListDelete_L(LinkList ,ElemType &e) ElemType data; / 在带头结点的单链线性表L中删除第i个元素struct LNode *next; / 并由e返回其值 Lnode,*LinkList; p=L;j=0; while (p-next&jnext)|ji-1) return ERROR; q=p-next; ; ; ; return OK; /ListInsert_L3根据下面给出的二叉树树的存储结构,请用类C语言编写二叉排序树的插入算法,其中查找算法原型为Status SearchBST(BiTree &T,KeyType key,BiTree f,BiTree &p)。typedef struct Bi
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 腹腔镜子宫肌瘤剔除术患者实施快速康复护理的效果评价-现代护理医学杂志
- 策划一场别开生面的儿童主题乐园游戏活动
- 安全教育主题月活动策划
- 安全反恐防范活动计划
- 开学第一课 绪言 高一上学期化学人教版(2019)必修第一册+
- 第四章 物质结构元素周期律 测试题 高一上学期化学人教版(2019)必修第一册
- 高考英语热点写作素材积累之体育健康+知识清单
- 三国两晋南北朝的民族交融与隋唐统一多民族封建国家的发展单元练习- 高考历史统编版必修中外历史纲要上一轮复习
- 生物圈与植被 高一地理鲁教版(2019)必修第一册同步课时练作业
- 学校安全工作总结15篇
- 2022年ICD-10恶性肿瘤编码整理版
- 自然分娩VS剖宫产分娩PPT课件(PPT 44页)
- 11002公司法与企业法试卷答案
- 进贤县青岚湖防洪治涝施工组织设计
- 心理治疗治疗关系
- 寄生虫病学粪便检查(一)
- 《呕吐的常见原因》PPT课件
- 车辆转弯半径表及计算方法
- 实习证明(标准格式标准排版)
- 中英文版送货单
- (精选)水分析化学第三版答案Word版
评论
0/150
提交评论