数据结构及算法课程设计题目汇编.pdfVIP

数据结构与算法课程设计题目汇编 1．Skip List 的实现及分析 (1) 问题描述 Skip List 作为有序链表结构的一种扩展，如下图所示，其中 a 是普通的单链表； 而 b 是在次基础上加上第二层 （level 2 ）的额外指针，这些额外的指针指向间隔为 2 的下一个结点，skip list 因此得名；类似的 c 是加上 level 3 后的 skip list；d 是加上 level 4 后的 skip list。 图6-8 Skip List 的基本结构示意图 Skip List 上查找的基本思想是先从最高的 Level 层上查找，找到 key 所在的范围 后，再从较低的层次继续重复查找操作，直到 Level 1 。 Skip List 上的插入操作如下图所示。 图6-9 Skip List 上插入操作的示意图 Skip List 上的删除操作只需直接删除元素即可 （包括局部范围内的指针调整）。 本设计题目的基本内容是构造并实现 Skip List 的ADT，并能对其维护动态数据集 合的效率进行一定的实验验证。 (2) 课程设计目的 认识并应用 Skip List 数据结构，体会线性表结构的变形形式。 (3) 基本要求 ① ADT 中应包括初始化、查找、插入、删除等基本操作。 ② 分析各基本操作的时间复杂性。 ③ 针对实现 Skip List 上基本操作的动态演示 (图形演示)。 ④ 能对 Skip List 维护动态数据集合的效率进行实验验证，获得一定量的实验数 据，如给定随机产生 1000 个数据并将其初始化为严格 Skip List，在此基础上进行一些列插 入、删除、查找操作 （操作序列也可以随机生成），获得各种操作的平均时间 （或统计其基 本操作个数）；获得各操作执行时间的变化情况，应该是越来越大，当大到一定程度后应该 进行适当的整理，需设计相应的整理算法，并从数量上确定何时较为合适；能和其他简单线 性数据结构，如排序数组上的折半查找进行各类操作效率上的数量对比。 (4) 实现提示 需仔细设计整理算法。 2. B-Trees 的实现及分析 (1) 问题描述 B-Trees 是一类满足特殊条件的 M 路查找树。首先说明 M 路查找树，M 路查找树 是二元查找树的一般化，其结构如下图所示的 3 路查找树：M 路查找树中的任一结点 至多存放M-1个数据，并至多拥有M 棵子树；每个结点中的数据按升序排列V1 V2 ... Vk (k = M- 1)，每个数据 Vi 都存在一棵左子树和一棵右子树，如果左子树不空的话， 该子树中所有结点的值都小于 Vi,如果右子树不空的话，该子树中所有结点的值都大于 Vi 。 图6- 10 3-路查找树的结构示意图 2 B-Trees 是满足