数据结构期末考试题(1)(1)5页.doc

上传人:晟*** 文档编号:2133780 上传时间:2021-08-17 格式:DOC 页数:5 大小:94KB
返回 下载 相关 举报
数据结构期末考试题(1)(1)5页.doc_第1页
第1页 / 共5页
数据结构期末考试题(1)(1)5页.doc_第2页
第2页 / 共5页
数据结构期末考试题(1)(1)5页.doc_第3页
第3页 / 共5页
数据结构期末考试题(1)(1)5页.doc_第4页
第4页 / 共5页
数据结构期末考试题(1)(1)5页.doc_第5页
第5页 / 共5页
亲,该文档总共5页,全部预览完了,如果喜欢就下载吧!
资源描述

《数据结构期末考试题(1)(1)5页.doc》由会员分享,可在线阅读,更多相关《数据结构期末考试题(1)(1)5页.doc(5页珍藏版)》请在新文库网上搜索。

1、课程教研室软件使用专业计算机科学与技术(工、师)、软件工程年级07级班级学号考生姓名考试地点装订线北华大学计算机科学技术学院2008-2009学年第一学期 数据结构 课程期末考试试卷( 1 )题号一二三四五六七八总分得分评卷人核分:大题得分一、填空题(每题2分,共 14分)1. 下面程序段的时间复杂度是_。 for (i=1; in; i+ ) for (j=1; jnext =null B. L = nullC. L! = null D. Lnext != null 4. 判断下列叙述中哪个不正确 A. 将一棵树转换成二叉树后,根结点没有左子树; B. 用二叉树的先序遍历和中序遍历可以导出后

2、序遍历; C. 一棵深度为K且有2K-1 个结点的二叉树称为满二叉树D. 哈夫曼树是带权路径长度最短的树,路径上权值较大的结点离根较近.5按二叉树的定义,具有3个结点的二叉树有_种形态 A. 3 B. 4 C. 5 D. 66在一个具有n个顶点的无向图中,要连通全部顶点至少需要_条边。An Bn+l Cn-1 Dn27已知图G如下,求出该图的拓扑排序序列_。A CABDEFGH B ABCDEFGH C ACBDEFGH D ACBDFEHG8在待排序的元素序列基本有序的前提下,效率最高的排序方法是_。 A 插入排序 B 选择排序 C 快速排序 D 归并排序三、分析解答(1至4小题每题6分,5

3、至6小题每题8 分,共 40 分) 1二维数组A的每个元素是由4个字符组成的串,行下标的范围从09,列下标的范围是从09,则存放A至少需要多少个字节,A的第3列和第7行共占多少个字节,若A按行优先方式存储,元素A63的起始地址与当A按列优先方式存储时的哪个元素的起始地址一致。三、XXXXXXXXXXX(每小题 分,共 分)1. 2.四、XXXXXXXXXXXX ( x x 小题每题 分, xx小题5分,共40分)1.2.大题得分1题得分课程教研室使用专业年级班级学号考生姓名考试地点装订线 2. 已知一棵树如下图,请将此树转化为对应的二叉树,画出转化后的二叉树及二叉链表。 3. 已知某系统在通信

4、联络中出现的abcdef 六种字符,其频率为(13,12,35,15,9,16),试构造一棵Huffman树,并写出每种字符的Huffman编码。 4已知关键字序列503,17,512,908,897,275,170,653,426 ,请给出采用希尔排序法(d1=4,d2=2,d3=1)对该序列作升序排列时的每一趟的结果。5. 已知AOE网如下,按关键路径算法: (1) 找出其关键路径。 (2) 计算:Ve (v5)、 Vl (v3)(3) 设弧称为活动a, 计算:e (a)和L(a)6依据下列关键字序列25,15,21,23,40,48,32,22构成一棵二叉排序树。(1)请画出此二叉排序树

5、。 (2)若在二叉排序树中查找,则查找成功与查找不成功的平均查找长度分别是多少? 2题得分3题得分4题得分5题得分6题得分课程教研室使用专业年级班级学号考生姓名考试地点装订线 四、算法设计(每小题 10 分,共 30 分)1. 某大学图书馆中有一批图书,按其价格从低到高的次序构成了一个单链表存于计算机中,链表的每个结点指出同样价格书的数量,现在要清理书库,将价格为C元的图书清出库,即从单链表中删除价格为C元的结点。单链表存储结构与按此存储结构的算法如下,请在空格上填写适当的语句,完成该算法。typedef struct LNode float cost; int num; Struct LNo

6、de *next; LNode, *LinkList;void Delbooks ( LinkList &L, float c) q=L; p=q-next; while ( & p !=null ) q=p; p=p-next; if ( p!=null ) ; ; 2. 设二叉树采用二叉链表存储结构,PrintElement是对数据元素打印输出的应用函数。下面算法是用类C语言描述的,实现了按中序遍历二叉树T的递归算法,对每个数据元素调用函数PrintElement输出该结点的值。请在空格上填写适当的语句,完成该算法。 typedef struct BiTNode char data; st

7、ruct BitNode *Lchild, * Rchild; BitNode, *BiTree;2.大题得分1题得分2题得分课程教研室使用专业年级班级学号考生姓名考试地点装订线Status InOrderTraverse ( BiTree T) if ( ) if ( InOrderTraverse ( T-Lchild ) if ( ) if ( ) return OK;return ERROR ; else return Ok; Status PrintElement ( char e ) ; return Ok ; 3假设图采用邻接表存储表示,设计一个广度优先遍历算法。图与队列的存储结构如下,请依据此存储结构用类C语言编写算法。#define MAX_VERTEX_NUM 20 void BFSTraverse(ALGraph G,Status(*Visit)(int v) typedef struct ArcNode int adjvex; struct ArcNode *nextarc;ArcNode; typedef struct VNode Vertextype data; ArcNode *firstarc;VNode, AdjListMAX_VERTEX_NU

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 教育培训 > 信息产业

黔ICP备20002965号-1  客户服务热线:0857-3221888

Copyright © 2020-2021 www.xinwenku.com All rights reserved 新文库网 版权所有