2006年上海海事大学数据结构考研真题.doc

发布时间：2022-09-19 发布人：admin 分类：说明书资料大小：0.49M 资料格式：doc 举报版权申诉

第1页 / 共4页

第2页 / 共4页

第3页 / 共4页

第4页 / 共4页

文本预览

2006 年上海海事大学数据结构考研真题一.判断题（本题 20 分，每小题 2 分） 1.深度为 k 的二叉树至多有 2k 个结点; 2.数据结构在计算机内存中的表示是指数据的存储结构; 3.队列和栈都是线性表，都可以用顺序表存储; 4.串只能用顺序存储，不能用链式存储; 5.对于 n×n 对称矩阵，最多需要存储 n2/2 个元素∶ 6.根据先序遍历和后序遍历序列不能唯一确定一棵二叉树; 7.B+树中所有叶子结点都处在同一层次上，且每个叶子结点中关键字个数均相等; 8.排序的目的就是要将一组无序的记录序列按从小到大的顺序调整; 9.存储在顺序存储器上的顺序文件不能进行折半查找; 10.有 n 个顶点的带权无向连通图的最小生成树包含 n-1 条最小的边。二.填空题（本题 30 分，每空 2 分）三.选择题（本题 20 分，每空 2 分）

1.为了提高文件的存取效率，往往采用索引技术，按（1）对记录进行分类或排序。 A. 字符 B. 关键字值 C. 属性值集合 D.数据元素 2.建立次索引也是一种基本的检索方法，也称为（2），先给定次关键字，然后查找含有这个次关键字的各个记录。 A.散列表 B.属性地址表 C.倒排表 D.索引表 3.对 m 个初始归并段，采用 k 路归并时，所需的归并趟数为（3） 4.按排序所需的辅助空间，堆排序、快速排序、归并排序关系为（4） A. 堆排序<快速排序<归并排序 B.堆排序<归并排序<快速排序 C.堆排序>快速排序>归并排序 D.三种都不对 5.在待排序的元素基本有序的情况下，效率最高的排序方法是（5） A.快速排序 B.选择排序 C.插入排序 D.归并排序 6.设有两个串 p 和 q，求 q 在 p 中首次出现的位置的运算称作__（6） A.连接 B.模式匹配 C.求子串 D.求串长

7. 串是一种特殊的__（7） A.线性表 B.树 C.图 D. 队列四.（本题 20 分，每小题 4 分）已知待排序记录的关键字序列为{324，83，246，849，138，427，273，562，72，381}，需要按关键字值递增的次序进行排序，请分别写出用下列五种排序方法进行第一趟扫描的过程和结果。 1.冒泡排序 2.初始增量为 4 的 Shell 排序 3.以第一个元素为基准的快速排序 4.归并排序 5.堆排序初始建堆五.（本题 12 分）线性表的关键字集合{32，83，46，149，18，127，73，56，72，81，95，25，66}共有 13 个元素，按散列函数 H（key）=key MOD13 采用链地址法处理冲突，试画出链表的结构，并计算出该表成功查找的平均查找长度。六.（本题 12 分）有一份电文共有九个字母∶S、H、M、T、U、C、D、E、A，它们出现的频率依次是∶16、23、 5、9、14、10、26、12、19，试为这九个字母设计 Huffman 编码（构造和画出哈夫曼树，并确定各个字母的编码），并计算出该哈夫曼树带权路径长度。

八.编程题（本题 24 分，第 1 题 10 分，第 2 题 14 分） 1.编写一函数 ReverseQueue（ Queue &qu），利用队列和栈的基本运算将给定队列中的数据元素逆转顺序，同时简要说明所用到的每一个基本运算的功能。 2.有一个数学函数定义如下，试分别用递归法和非递归法编写程序实现。

分享到：

赞收藏

资料库

2006年上海海事大学数据结构考研真题.doc

相关推荐

考研

热门标签

最新资料