耿国华数据结构实习题

《耿国华数据结构实习题》由会员分享，可在线阅读，更多相关《耿国华数据结构实习题（4页珍藏版）》请在金锄头文库上搜索。

1、耿国华数据结构实习题耿国华数据结构实习题整理者整理者 小马驹走天涯小马驹走天涯 4/25/2018 3:21:11 上午上午 备注：黑体字表示重点实习题。备注：黑体字表示重点实习题。 吐槽：表示俺整理得好辛苦。一直都没搜到这些实习题，所以整理出来跟大家吐槽：表示俺整理得好辛苦。一直都没搜到这些实习题，所以整理出来跟大家 分享一下。咯咯分享一下。咯咯 第一章 绪论 问题一 设计实现抽象数据类型“有理数” 。基本操作包括有理数的加法、减法、乘法、除法，以 及求有理数的分子、分母。第二章 线性表 问题二 将若干城市的信息存入一个带头结点的单链表，结点中的城市信息包括城市名、城市的位 置坐标。要求：

2、（1） 给定一个城市名，返回其位置坐标； （2） 给定一个位置坐标 P 和一个距离 D，返回所有与 P 的 距离小于等于 D 的城市。问题三 约瑟夫环问题。约瑟夫环问题。 约瑟夫问题的一种描述是： 编号为 1，2，n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数） 。 一开始任选一个整数作为报数上限值 m,从第一个人开始顺时针自 1 开 始顺序报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一 个人开始重新从 1 报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求出 出列顺序。 利用单向循环链表作为存储结构模拟此过程，按照

3、出列顺序打印出各人的编号。 例 如 m 的初值为 20；n=7，7 个人的密码依次是：3，1，7，2，4，8，4，出列的顺序为 6，1，4，7，2，3，5。第三章 限定性线性表栈和队列 问题四 回文判断。 称正读与反读都相同的字符序列为“回文”序列。 试写一个算法，判断依次读入的一个 以为结束符的字母序列，是否为形如序列 1 &序列 2模式的字符序列。其中序列 1 和 序列 2 中都不含字符& ，且序列 2 是序列 1 的逆序列。例如， a+b&b+a是属该模式 的字符序列，而+&则不是。 问题五问题五 停车场管理。停车场管理。 设停车场是一个可停放 n 辆车的狭长通道，且只有一个大门可供汽车

4、进出。在停车场 内，汽车按到达的先后次序，由北向南依次排列（假设大门在最南端） 。若车场内已停满 n 辆车，则后来的汽车需在门外的便道上等候，当有车开走时，便道上的第一辆车即可开入。 当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开 出大门后，其它车辆再按原次序返回车场。每辆车离开停车场时，应按其停留时间的长短交费（在便道上停留的时间不收费） 。 试编写程序，模拟上述管理过程。要求以顺序栈模拟停车场，以链队列模拟便道。从 终端读入汽车到达或离去的数据，每组数据包括三项：是“到达”还是“离去” ；汽车 牌照号码；“到达”或“离去”的时刻。与每组输入信息相应的输出信息

5、为：如果是到 达的车辆，则输出其在停车场中或便道上的位置；如果是离去的车辆，则输出其在停车场 中停留的时间和应交的费用。 （提示：需另设一个栈，临时停放为让路而从车场退出的车。 ）车 库暂时退车道便道车 库暂时退车道便道问题六 商品货架管理。 商品货架可以看成一个栈，栈顶商品的生产日期最早，栈底商品的生产日期最近。上 货时，需要倒货架，以保证生产日期较近的商品在较下的位置。用队列和栈作为周转，实 现上述管理过程。第四章 串 第五章 数组与广义表 问题七 若矩阵 Amn 中的某个元素 aij 是第 i 行中的最小值，同时又是 第 j 列中的最大值， 则称此元素为该矩阵中的一个马鞍点。假设以二维数

6、组存储矩阵，试编写算法求出矩阵中 的所有马鞍点。第六章 二叉树 问题八 问题描述 建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序） ，打印 输出遍历结果。 基本要求 从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立）并对其进行遍历（先序、中序、后序） ，然后将遍历结果打印输出。要求采用递归和非递归 两种方法实现。 测试数据 ABCDEGF（其中 表示空格字符）输出结果为： 先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA问题九 已知二叉树按照二叉链表方式存储，编写算法，要求实现二叉树的竖向显示（竖向显 示就是二叉树的按层显示） 。 提示

7、： （1）参习题 6.20，实现逐层遍历 （2）队中保存每个结点的打印位置，其左、右子的距离问题十 如题 1 要求建立好二叉树，按凹入表形式打印二叉树结构，如图 6.34 所示。AFCEDBCFEA DB问题十一 按凹入表形式打印树形结构，如图 6.35 所示。 提示：参 P.129 例，用先根遍历。ADGCFEBABEFCGDADGCFEBABEFCGD第七章 图 问题十二 分别用邻接矩阵和邻接表实现图的深度优先遍历和广度优先遍历。分别用邻接矩阵和邻接表实现图的深度优先遍历和广度优先遍历。问题十三 校园导游程序。 用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、

8、 名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。 要求实现以下功能： （1）查询各景点的相关信息； （2）查询图中任意两个景点间的最短路径。 （3）查询图中任意两个景点间的所有路径。问题十四 编程求解关键路径问题。第八章 问题十五 哈希表设计。 为 30 个人的姓名设计一个哈希表，假设姓名用汉语拼音表示。要求用除留余数法构造 哈希函数，用线性探测再散列法处理冲突，平均查找长度的上限为 2。问题十六 简单的员工管理系统。 每个员工的信息包括：编号、姓名、性别、出生年月、学历、职务、电话、住址等。 系统的功能包括： （1）查询：按特定条件查找员工。 （2）修改：按编号对某个员工的某项信息进行修改。 （3）插入：加入新员工的信息。 （4）删除：按编号删除已离职的员工的信息。 （5）排序：按特定条件对所有员工的信息进行排序。