数据结构试题14_第1页
数据结构试题14_第2页
数据结构试题14_第3页
数据结构试题14_第4页
全文预览已结束

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、一、简答题:(每小题3分,共15分)1.2.3.4.5.在哈希查找法中,为什么平均查找长度与关键字个数无关? 对于无向图,如何用遍历算法判断图中是否存在回路? Huffman树是否唯一?请举例说明。栈和队列各有哪些基本操作?二、判断正误:(每小题1分,共5分)在一个与堆序列对应的完全二叉树中,从根结点到任一个叶结点的路径 上的关键字序列有何特点?为什么?正确在()内打/,否则打 。()1.折半搜索只适用于有序表,包括有序顺序表和有序单链表。()2.由树的中序表示和前序表示可以导出树的后序表示。()3.查找n个关键字的散列表时,平均查找长度与n无关。()4.希尔排序是一种不稳定的排序方法。()5

2、.给定一个关键字集合,将得到唯一的一棵二叉排序树,与关键字的插 入顺序无关。三、单项选择题:(每小题1分,共5分)某二叉树结点的中序序列为A、B、C、D、E、F、G,后序序列为B、D、C、 A、F、G、E,则该二叉树根的右子是:A) EB)F C)DD)G在长度为n的顺序表的第i ( 1 i 个位置上插入一个元素,元素的移动 次数为:A) n-i+1 B) n-i C) iD) i-13 .下面关于图的存储的叙述中正确的是0)邻接矩阵占用的存储空间只与图中结点个数有关,而与边数无关;B)邻接矩阵占用的存储空间只与图中边数有关,而与结点个数无关;C)邻接表占用的存储空间只与图中结点个数有关,而与

3、边数无关;D)邻接表占用的存储空间只与图中边数有关,而与结点个数无关。在待排序记录已基本有序的前提下,下述排序方法中效率最高的是:A)直接插入排序 B)简单选择排序C)快速排序D)归并排序栈S最多能容纳4个元素。现在6个元素按A、B、C、D、E、F的顺序进 栈,下列哪一个序列是不可能的出栈序列?A) A、B、C、D、E、FB) A、F、E、D 、C、BC) C、B、E、D、A、F D) C、D、B、F、 E、 A、填空题:(每小题2分,共20分)向一个有n个元素的有序表中插入一个新元素并保持原来顺序不变,平均要移动 个元素。2.设广义表 L=(),(),则 head(L)是; tail(L)是

4、L的长度是;深度是。3 在双向循环单链表中,删除指针P所指结点的操作 是; 。4.设根结点的层数为1,则高度为k的二叉树具有的结点数目,最 少为,最多为。5.10000个结点构成的二叉排序树,在等概率查找的假设下,查 找成功时的平均查找长度的最大值可能达到。 有3个结点的、不同结构的二叉树共有棵。将10阶的下三角矩阵A按列优先顺序压缩存储在一维数组C中, 则C数组的大小应为。8.在n个结点的线索二叉链表中,有.个线索指针。已知二维数组A1020采用行序为主方式存储,每个元素占2 个存储单元,并且A00的存储地址是1024,则A618的存储地址是字符A、B、C依次进入一个栈,按出栈的先后顺序组成

5、不同的 字符串,至多可以组成个不同的字符串。五、构造题:(每小题6分,共30分)1.已知关键字序列:(SUN, MON, TUE, WED, THU, FRI, SAT),哈希函数为:H(K)= (K中最后一个字母在字母表中的序号)MOD 7用线性探测法处理冲突,要求构造一个装填因子为0.7的哈希表,并 分别计算出在等概率情况下查找成功与不成功的平均查找长度。一个二叉树按顺序方式存储在一个一维数组中,如图1所示(空 元素对应虚结点)。(1 )画出二叉树,(2 )给出后序遍历序列。012 34567 89 10 11 12 13 14ABCDEFGHJ假设字符a, b, c, d, e, f的使用频度分别是0.07, 0.09, 0.12, 0.22, 0.23, 0.27,画出哈夫曼树,并给出a, b, c, d, e, f的哈夫曼编码。已知无向图如图2所示,(1)给出图的邻接表。(2)从C开始,给出深度优先遍历序列和深度优先搜索树。5 .将下列关键字序列筛成一个大根堆:(A, C, D, G, H, M, P, Q, R, X),要求给出建堆过程图示。六

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论