数据结构课程设计题目参考2010

1． 以邻接矩阵的方式确定一个图，完成： ⑴建立并显示出它的邻接链表；

⑵以非递归的方式进行深度优先遍历，显示遍历的结果，（并随时显示栈的入、出情况）； ⑶对该图进行广度优先遍历，显示遍历的结果，（并随时显示队列的入、出情况）。

2．以邻接矩阵的方式确定一个图，完成： ⑴建立并显示出它的邻接链表；

⑵给出它的关键路径（要求：显示出VE，VL，E，L，L-E的结果）。

3．以邻接矩阵的方式确定一个图，完成： ⑴建立并显示出它的邻接链表；

⑵分别用普里姆算法和克鲁斯卡尔算法构造其最小生成树，随时显示其构造的过程；

4．建立一棵二叉树，并用非递归方式对它进行先序、中序、后序遍历，给出遍历过程中栈的变化情况；

5．哈夫曼树、编码、译码

(1)输入一组字符集的大小、字符及权值，建立哈夫曼树，显示该哈夫曼树，并给出每个字符的哈夫曼编码

(2)给出一串字符，按照已建立的哈夫曼树进行编码，显示结果或存入文件 (3)用(2)的结果，按照哈夫曼树进行译码。

6．二叉排序树的建立和删除

给出一组关键值，建立相应的二叉排序树，完成结点的删除操作。要求 ⑴可以实现删除根结点、叶子结点以及其它任意结点的功能； ⑵随时显示操作的结果。

7. 几种排序，随时给出某一趟的变化情况 ⑴直接插入排序、折半插入排序、希尔排序； ⑵冒泡排序、快速排序； ⑶简单选择排序 (4)堆排序

8. 要求是：(1)从键盘输入一个表达式，如（23-（4×5.2-2.8））/5= (2)支持+，-，×，/,( )等符号 (3)支持运算符的优先级 (4)支持括号的嵌套 (5)支持小数点及负数

(6)有查错功能，如非法字符，小数点过多（如3.44.3），括号不匹配等错误。

9. 以邻接矩阵的方式确定一个图，完成： ⑴建立并显示出它的邻接链表；

⑵给出某一确定顶点到所有其它顶点的最短路径；

10. 约瑟夫环问题 [问题描述]

编号是1，2，??,n的n个人按照顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。 [基本要求]1.利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。此题所用的循环链表中不需要“头结点”，请注意空表和非空表的界限。

2.向上述程序中添加在顺序结构上实现的部分。

[测试数据] m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=则正确的输出是什么？ 要求：

输入数据：首先输入待处理人员数及他们的密码，然后输入m的初值，建立单循环链表。 输出形式：建立一个输出函数，将正确的出列序列输出。

11. 任意长的整数加法

问题描述：设计一个程序实现两个任意长的整数的求和运算。

基本要求：利用双向循环链表，设计一个实现任意长的整数进行加法运算的演示程序。要求输入和输出每四位一组，组间用逗号隔开。如：1，0000，0000，0000，0000。

12. 串的查找和替换

问题描述：打开一篇英文文章，在该文章中找出所有给定的单词，然后对所有给定的单词替换为另外一个单词，再存盘。

13. 括号匹配问题

问题描述：假设一个算术表达式中可包含三种括号：圆括号，方括号和花括号且这三种括号可按任意次序嵌套使用。试利用栈的运算，编写判别给定表达式中所含括号是否正确配对出现的算法。

14. 一元多项式简单计算

问题描述：设计一个一元多项式简单的计算器。 基本要求：一元多项式简单计算器的基本功能为：

(1) 输入并建立多项式； (2)输出多项式；

(3)两个多项式想加，建立并输出和多项式； (4)两个多项式相减，建立并输出差多项式。

实现提示：可选择带头结点的单向循环链表或单链表存储多项式，头结点可存放多项式的参

数，如项数等。

15. 迷宫问题

问题描述：迷宫实验是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经多次试验终于得到它学习走迷宫的路线。设计一个计算机程序对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

要求：在给出入口和出口的前提下，给出动态的迷宫行走路线。

16. 八皇后问题

要求：试编写程序实现将八个皇后放置在国际象棋棋盘的无冲突的位置上的算法，并给出所

有的解。 提示：在国际象棋上放置皇后时，任何一个皇后的水平、竖直和斜45o都不能有另一个皇后。

解决该问题采用逐次试探的方法，即采用递归调用putchess函数的方法。首先将第一个皇后放于第一行第一列，然后开始向下一行递归。每一步递归中，首先检测待放置位置是否与已放置的皇后冲突，如不冲突，则进行下一行的放置，否则，选择该行的下一个位置进行检测。如整行的位置都冲突，则回到上一行，重新选择位置。

17. 程序分析 [问题描述]

读入一个C程序，统计程序中代码、注释和空行的行数以及函数的个数和平均行数，并利用统计信息分析评价该程序的风格。

[基本要求]

(1)把C程序文件按字符顺序读入源程序；

(2)边读入程序，边识别统计代码行、注释行和空行，同时还要识别函数的开始和结束，以便统计其个数和平均行数。

(3)程序的风格评价分为代码、注释和空行三个方面。每个方面分为A，B，C和D四个等级，

等级的划分标准是： 代码(函数平均长度) 注释(占总行数比率) 空行(占总行数比率) A级 B级 C级 5～7或21～24行 D级 <5或>24行 10～15行 8～9或16～20行 15～25 ％ 10～14或26～30 ％ 5～9或31—35 ％ <5 ％ 或>35 ％ 15～25 ％ 10～14或26～30 ％ 5—9或31—35 ％ <5 ％ 或>35 ％ 以下是对某程序文件分析的输出结果示例： The resulfs Of analystag program“ProgAnal．C”； lanes Of code： 180 lanes Of comments：63

B1ank 1ines： 52 ， Code Comments Space 61％ 2l％ 18％

The program includes 9 functions．

The average 1ength Of a section O{cOde is 12.9 lines． Grade A：Exeellent routine size style． Grade A：Excellent commenting style. Grade A：Excellent white space style． [测试数据]

先对较小的程序进行分析。当你的程序能正确运行时，对你的程序本身进行分析。

[实现提示]

为了实现的方便，可作以下约定：

(1)头两个字符是”//”的行称为注释行(该行不含语句)。除了空行和注释行

外，其余均为代码行(包括类型定义、变量定义和函数头)。

(2)每个函数代码行数(除去空行和注释行)称为该函数的长度。

(3)每行最多只有一个“{”、“}”、“switch”和\”(便于识别函

数的结束行)。

18. 集合的并、交和差运算 [问题描述]

编制一个能演示执行集合的并、交和差运算的程序。 [基本要求]

(1)集合的元素限定为小写字母字符[‘a’? 'z']。 (2)演示程序以用户和计算机的对话方式执行。 [测试数据]

(1)Setl＝”magazine”，Set2＝”paper\，

Setl∪Set2＝”aeginmprz\，Setl∩Set2＝”ae”，Setl一Set2＝\。 (2)Setl＝”0120per4a6tion89\，Set2＝”error data\，

Setl∪Set2＝”adeinoprt\，Setl∩Set2＝”aeort”，Setl一Set2＝”inp”。 [实现提示]

以有序链表表示集合。

19.数组的应用举例——魔方阵

魔方阵是一个古老的智力问题，它要求在一个n×n的矩阵中填入1到n2的数字（n

为奇数），使得每一行、每一列、每条对角线的累加和都相等，如图所示。

编写算法实现魔方阵.

20. 稀疏矩阵运算器 [问题描述]

稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。 [基本要求]

以三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示．而运算结果的矩阵则以通常的阵列形式列出。

[实现提示]

1．首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作

的运算是否相匹配。可设矩阵的行数和列数均不超过20。

2．程序可以—对三元组的输入顺序加以限制，例如，按行优先。

3．在用三元组表示稀疏矩阵时，相加或相减所得结果矩阵应该另生成，乘积矩阵也可用二维数组存放。

21.回文词

回文词是一种对称的字符串，即从左到右读和从右到左读的结果一样。任意给定一个字符串，通过插入若干字符，都可以变成一个回文词。请编写一个程序，求出将给定字符串变成回文词所需插入的最少字符数。 [输入数据]

输入数据的第一行包含一个整数N，表示给定字符串的长度（3～5000）。 第二行是一个长度为N的字符串，它由大写字母，小写字母和数字组成。大小写被认为不同。 [输出数据]

输出一个整数，表示需要插入的最少字符数。并输出一个插入后的示例。

本文来源：https://www.bwwdw.com/article/yd3f.html