数据结构题目解读.doc

第一章：基础知识 第二章：校园导游咨询 【问题描述】 （1）设计你的学校的校园平面图，所含景点不小于5个。以图中的顶点表示学校的各个景点，存放景点名称，代号，简介等信息；以边表示路径，存放路径，存放路径的长度等相关信息。 （2）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的最短的简单路径。 【目的】 了解数据结构，熟悉图的应用，并利用迪杰斯特拉算法求得2点之间的最短路径。 第三章：稀疏矩阵运算器 【问题描述】 稀疏矩阵是指那么多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。 【目的】 了解数据结构，熟悉稀疏矩阵的应用， 第四章：同学录 【问题描述】 随着社会发展，时代的前进，人与人的交往越来越密切，通讯成为当代社会发展必不可少的一大服务业，目前在我国较为有影响力的通讯产业有中国移动、中国联通、中国电信等，它们的产生给人们生活、交往带来极大的便利，通讯录由此而生，方便了同学、亲戚朋友的交往。说到通讯录，从字面意思来看，即通讯的记录，方便人们的交往，在我看来，通讯录的主要意义也就在于有助于人与人之间的通讯，便捷地找到自己想找到的人,其实通讯录无处不在,根据需要设计本程序。 一个简单的通讯录系统应具有以下功能： 1、通讯录成员的输入（输入通讯录成员的个数由用户自己决定，当在“请输入姓名”后面输入为空时，结束输入） 2、通讯录成员的删除（输入要删除成员的姓名，当此成员存在通讯录中，即可删除此成员，若是输入的姓名未能找到，系统会提示“没有此人信息”。） 3、浏览通讯录（显示通讯录中所有成员的信息，成员的信息有姓名、地址、邮编、电话、QQ。） 4、查找通讯录中某些成员（输入要查找成员的姓名，显示要查找成员的所有信息。） 5、对通讯录中的所有信息的保存（将通讯录中的所有信息保存在mylist文件中，方便用户的操作。） 6、对通讯录某些成员进行修改（输入需要修改成员的姓名，输入其正确的信息。） 7、系统清屏（当屏幕内容过多时，清屏。） 8、退出通讯录（完成通讯录的所有操作，退出系统。） 9、数据结构如此定义：姓名、性别、地址由字符组成，最大字符数分别为 10个，2个和16个；邮编、电话、QQ由数字字符组成，最在字符数分别为6个，11个和9个；当输入的输的字符超过上面所规定的最大字符数时，系统会提示“输入字符太长，请重新输入”。 【目的】 熟悉链表的使用 第五章：哈希表的设计与实现 【问题描述】 设计哈希表实现电话号码查询系统。基本要求： 1、设每个记录有下列数据项：电话号码、用户名、地址； 2、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表； 3、采用再哈希法解决冲突； 4、查找并显示给定电话号码的记录； 5、查找并显示给定用户名的记录。 【目的】 利用哈希表实现电话号码的查询，利用数据链实现对电话记录的增加和删除 第六章：八皇后 【问题描述】 求出在一个n×n的棋盘上，放置n个不能互相捕捉的国际象棋“皇后”的所有布局。 【目的】 算法的使用 第七章：Josephu问题 【问题描述】 Josephu问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1=k=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。 提示：用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。 【目的】 选择单项链表作为存储结构模拟整个过程，并依次输出出列的个人编号。 第八章：n阶魔阵问题 【问题描述】 给定一奇数n，构造一个n阶魔阵。n阶魔阵是一个n阶方阵，其元素自由然数1，2，3，…，n*n组成。魔阵的每行元素之和，每列元素之和以及主,副对角线之和均相等。既对于给定的奇数n以及i=1，2，3……，n。魔阵a满足以上条件。 提示：依次将自然数填入方阵中，共填n 轮，每轮填n次。第一轮的第一次，将1填入方阵的中间一行的最后一列位置。设前一次填入的位置是aij。 (1)每轮中第2至第n次将数填入ai+1,j+1，若遇到下列情况之一，则填写位置按以下规则调整： 1.aij是最后一列（即j=n）位置，则将下一个数填入ai+1,1； 2.aij是最后一行（即i=n）位置，则将下一个数填入a1,j+1； (2)新一轮的第一次填入ai,j-1。 【目的】 数组的使用 第九章：停车场管理问题 【问题描述】 设有一个可以停放n辆汽车的狭长停车