文档库

最新最全的文档下载
当前位置:文档库 > 2周《数据结构》课程设计任务书

2周《数据结构》课程设计任务书

沈阳工程学院

课程设计任务书

课程设计题目:数据结构与算法课程设计

系别信息工程系班级

学生姓名学号

指导教师职称

课程设计进行地点:

任务下达时间:年月日

起止日期:年月日起——至年月日止教研室主任年月日批准

一、课程设计的原始资料及依据

数据结构与算法课程设计是在完成数据结构理论课程学习之后进行的一个综合性的实践教学环节,是对课程理论和课程实验的一个补充。通过课程设计,培养学生综合运用已学过的理论和技能去分析和解决实际问题的能力,并使所学知识得到进一步巩固、深化和扩展。

二、课程设计主要内容及要求

设计内容:

1、设有一元素为整数的线性表L=(a1,a2,a3,…,an),存放在一维数组A[N]中,设计

一个算法,以表中an作为参考元素,将该表分为左、右两部分,其中左半部分每个元素小于等于an,右半部分每个元素都大于an, an位于分界位置上(要求结果仍存放在A[N]中)。

2、设线性表存于A[1..size]的前num各分量中,且递增有序。请设计一个算法,

将x插入到线性表的适当位置上,以保持线性表的有序性。

3、线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计

一算法完成:

4、用最少时间在表中查找数值为x的元素。

5、若找到将其与后继元素位置相交换。

6、若找不到将其插入表中并使表中元素仍递增有序。

7、已知数组A[0:n-1]的元素类型为int,试设计算法将其调整为左右两个部分,

左边所有元素为奇数,右边所有元素为偶数。

8、设计一个算法从顺序表L中删除所有值为x的元素

9、设计一个算法从顺序表L中删除所有值为x到y之间(x<=y)的元素

10、假设有两个按元素值递增次序排列的线性表,均以单链表形式存储。请

编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表,并要求利用原来两个单链表的结点存放归并后的单链表。

11、已知L1、L2分别为两循环单链表的头结点指针,m,n分别为L1、L2表

中数据结点个数。要求设计一算法,用最快速度将两表合并成一个带头结点的循环单链表。

12、设L为单链表的头结点地址,其数据结点的数据都是正整数且无相同的,

设计一个将该链表整理成数据递增的有序单链表的算法。

13、设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、

C,其中B表的结点为A表中值小于零的结点,而C表的结点为A表中值大于零的结点(链表A的元素类型为整型,要求B、C表利用A表的结点)。

14、试编写在带头结点的单链表中删除(一个)最小值结点的(高效)算法。

15、设L为单链表的头结点地址,请写一算法,将链表中数据域值最小的那

个链结点移到链表的最前面。要求:不得额外申请新的链结点。

16、已知两个单链表A和B,其头指针分别为heada和headb,编写一个过程

从单链表A中删除自第i个元素起的共len个元素,然后将单链表A插入到单链表B的第j个元素之前。

17、已知递增有序的单链表A,B分别存储了一个集合,请设计算法以求出两

个集合A和B 的差集A-B(即仅由在A中出现而不在B中出现的元素所构成的集合),并以同样的形式存储,同时返回该集合的元素个数。

18、已知一个单链表中每个结点存放一个整数,并且结点数不少于2,请设

计算法以判断该链表中第二项起的每个元素值是否等于其序号的平方减去其前驱的值,若满足则返回ture,否则返回false.

19、两个整数序列A=a1,a2,a3,…,am和B=b1,b2,b3,…,bn已经存入两个单

链表中,设计一个算法,判断序列B是否是序列A的子序列。

20、已知p指向双向循环链表中的一个结点,其结点结构为data、llink、

rlink三个域,写出算法change(p),交换p所指向的结点和它的前缀结点的顺序。

21、设有一个由正整数组成的无序单链表,编写完成下列功能的算法:

(1)找出最小值结点,且打印该数值;

(2)若该数值是奇数,则将其与直接后继结点的数值交换;

(3)若该数值是偶数,则将其直接后继结点删除。

22、在一个递增有序的线性表中,有数值相同的元素存在。若存储方式为单

链表,设计算法去掉数值相同的元素,使表中不再有重复的元素。例如:(7,10,10,21,30,42,42,42,51,70)将变作(7,10,21,30,42,51,70)。

23、编写一个算法来交换单链表中指针P所指结点与其后继结点,HEAD是该

链表的头指针,P指向该链表中某一结点。

24、已知三个带头结点的线性链表A、B和C中的结点均依元素值自小至大非

递减排列(可能存在两个以上值相同的结点),编写算法对A表进行如下操作:使操作后的链表A中仅留下三个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O(m+n+p),其中m、n和p分别为三个表的长度。

25、设计一个算法,利用栈的基本运算将指定栈中的内容逆转。

26、设计一个算法,利用栈的基本运算返回指定栈中栈底元素。

27、设有两个栈S1,S2都采用顺序栈方式,并且共享一个存储区

[O..maxsize-1],为了尽量利用空间,减少溢出的可能,可采用栈顶相向,迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。

28、设从键盘输入一整数的序列:a1, a2, a3,…,an,试编写算法实现:用

栈结构存储输入的整数,当ai≠-1时,将ai进栈;当ai=-1时,输出栈顶整数并出栈。算法应对异常情况(入栈满等)给出相应的信息。

29、设表达式以字符形式已存入数组E[n]中,‘#’为表达式的结束符,试写

出判断表达式中括号(‘(’和‘)’)是否配对的C语言描述算法:EXYX(E);

(注:算法中可调用栈操作的基本算法。)

30、从键盘上输入一个逆波兰表达式,用伪码写出其求值程序。规定:逆波

兰表达式的长度不超过一行,以$符作为输入结束,操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如:234 34+2*$

31、写出一个算法,判定所给的操作序列是否合法。若合法,返回true,否

则返回false(假定被判定的操作序列已存入一维数组中)。

32、设计一个算法,判断一个算术表达式中的括号是否配对。算术表达式保

存在带头结点的单循环链表中,每个结点有两个域:ch和link,其中ch域为字符类型。

33、请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下:

PUSH(ST,x):元素x入ST栈;POP(ST,x):ST栈顶元素出栈,赋给变量x;

Sempty(ST):判ST栈是否为空。那么如何利用栈的运算来实现该队列的三个运算:enqueue:插入一个元素入队列; dequeue:删除一个元素出队列;

queue_empty:判队列为空。(请写明算法的思想及必要的注释)

34、假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾结点,

但不设头指针,如图所示(编者略),请写出相应的入队列和出队列算法。

35、如果允许在循环队列的两端都可以进行插入和删除操作。要求:

(1)写出循环队列的类型定义;

(2)写出“从队尾删除”和“从队头插入”的算法。

36、在一个循环链队中只有尾指针(记为rear,结点结构为数据域data,指

针域next),请给出这种队列的入队和出队操作的实现过程。

37、已知Q是一个非空队列,S是一个空栈。仅用队列和栈的操作编写一个

算法,将队列Q中的所有元素逆置。

38、已知求两个正整数m与n的最大公因子的过程用自然语言可以表述为反

复执行如下动作:第一步:若n等于零,则返回m;第二步:若m小于n,则m与n相互交换;否则,保存m,然后将n送m,将保存的m除以n的余数送n。

(1)将上述过程用递归函数表达出来(设求x除以y的余数可以用x MOD y 形式表示)。

(2)写出求解该递归函数的非递归算法。

39、试将下列递归过程改写为非递归过程。

void test(int &sum)

{ int x;

scanf(x);

if(x=0) sum=0 else {test(sum); sum+=x;}

printf(sum); }

40、二叉树用二叉链表存储,写一个算法将二叉树中的叶子结点按从右至左

的顺序建立一个单链表。

41、知二叉树用二叉链表存储,写出求二叉树宽度的算法。所谓宽度是指在

二叉树的各层上,具有结点数最多的那一层上的结点总数。

42、叉树用二叉链表存储,写一个算法交换各结点的左右子树。

43、二叉树用二叉链表存储,若结点的左孩子的数据域的值大于右孩子数据

域的值,则交换其左右子树。

44、叉树用二叉链表存储,编写一算法,判别给定的二叉树是否为完全二叉

树。

45、个结点的完全二叉树以一维数组为存储结构,编写一非递归算法实现对

该树的先序遍历。

46、编写一算法,在二叉树中查找值为x的结点,并打印值为x的结点的所

有祖先结点。

47、编写中序遍历二叉树的非递归算法。

48、编写先序遍历二叉树的非递归算法。

49、编写后序遍历二叉树的非递归算法。

50、叉树用二叉链表存储,任给一个二叉树表示的四则运算表达式,编写算

法,由该二叉树输出该表达式,若原表达式有括号亦加上。

51、有n个结点的完全二叉树存放在一维数组A[1..n]中,试据此建立一棵

用二叉链表表示的二叉树,根由tree指向。

52、二叉树排序方法如下:

(1)将第一个数据放在树根。

(2)将随后读入的数据与树根中的数据相比较,若比树根大,则置于右子树,反之则置于左子树,建成一棵二叉树;

(3)利用中序遍历打印排序结果。

用C语言编写二叉树的排序程序。

53、二叉树结点的平衡因子(bf)定义为该结点的左子树高度与右子树高度

之差。编写算法计算二叉树中各个结点的平衡因子。

54、设计算法:统计一棵二叉树中所有叶结点的数目及非叶结点的数目。

55、已知二叉树以二叉链表存储,编写算法完成:对于树中每一个元素值为

x的结点,删去以它为根的子树,并释放相应的空间。

56、试编写算法,对一棵以孩子—兄弟链表表示的树统计叶子的个数。

57、设一棵二叉树中各结点的值互不相同,其前序序列和中序序列分别存于

两个一维数组pre[1..n ]和mid[1..n ]中,试遍写算法建立该二叉树的二叉链表。

58、试设计一个算法打印出由根结点出发到达叶结点的所有路径。

59、试写出算法,求任意二叉树中第一条最长的路径长度,并输出此路径上

各结点的值。

60、给定一组项及其权值,假定项都存放于二叉树的树叶结点,则具有最小

带权外部路径长度的树称为huffman 树。编写构造huffman 树的算法。

61、已知一中序线索二叉树,写一算法完成对它的中序扫描。

62、已知中序线索二叉树T右子树不空。设计算法,将S所指的结点作为T

的右子树中的一个叶子结点插入进去,并使之成为T的右子树的(中序序列)第一个结点(同时要修改相应的线索关系)。

63、写出算法,求出中序线索二叉树中给定值为x的结点之后继结点,返回

该后继结点的指针。线索树中结点结构为:(ltag,lc,data,rc,rtag)。其中,data存放结点的值;lc,rc为指向左、右孩子或该结点前驱或后继的指针;

ltag,rtag为标志域,各值为:0,则lc,rc为指向左、右孩子的指针;值为1,则lc,rc为指向某前驱后继结点的指针

64、设后序线索树中结点构造为(Ltag,Lchild,Data,Rchild,Rtag)。其

中:Ltag,Rtag 值为0时,Lchild、Rchild 分别为儿子指针;否则分别为直接前驱,直接后继的线索。请写出在后序线索树上找给定结点p^ 的直接前驱q 的算法。

65、设无向图G有n个顶点,m条边。试编写用邻接表存储该图的算法。(设

顶点值用1~n或0~n-1编号)

66、已知有向图有n个顶点,请写算法,根据用户输入的偶对建立该有向图的

邻接表。即接受用户输入的(以其中之一为0标志结束),对于每条这样的边,申请一个结点,并插入到的单链表中,如此反复,直到将图中所有边处理完毕。提示:先产生邻接表的n个头结点(其结点数值域从1到n)。67、给出以十字链表作存储结构,建立图的算法,输入(i,j,v)其中i,j为顶

点号,v为权值。

68、设有向G图有n个点(用1,2,…,n表示),e条边,写一算法建立有向图的

逆邻接表。

69、设已给出图的邻接矩阵,要求将图的邻接矩阵转化为邻接表,试实现其

算法。

70、编写算法,将图的邻接矩阵存储改为邻接表的存储。

71、试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点V

i

到顶

点V

j

的路径(i<>j)。

72、已知无向图采用邻接表存储方式,试写出删除边(i,j)的算法。

73、假设有向图以邻接表存储,试编写算法删除弧

i,V

j

>的算法。

74、假设有向图以十字链表存储,试编写算法,插入弧

i ,V

j

>。

75、设有向图用邻接表表示,图有n个顶点,表示为1至n,试写一个算法求顶

点k的入度(1

76、写出图的深度优先搜索DFS算法的非递归算法。

77、写出图的广度优先搜索算法的非递归算法。

78、已知带权图用邻接矩阵表示,编写函数实现用Kruskal算法构造最小生

成树的算法。

79、编写函数实现用Prim算法构造最小生成树的算法。

80、编写函数实现从指定顶点到其余各顶点的最短路径的Dijkstra 算法。

81、实现图的拓扑排序算法。

82、设计一个二分查找的递归算法。

83、设计一个算法,利用二分查找算法在一个有序表中插入一个元素x,并

保持表的有序性。

84、实现散列表的相关算法

(1)给定一个序列,和散列函数,并利用线性探测再散列处理冲突,建立散列表。

(2)编写函数,查找某一个关键字

(3)编写函数,删除找某一个关键字

85、设计一个顺序查找算法

86、编写一个算法,统计一个字符串中出现字符的次数。

87、实现二叉查找树的相关算法

(1)给定序列,创建一二叉查找树

(2)判定一棵树是否为二叉查找树

(3)采用递归和非递归算法,查找某一个关键字

(4)编写函数,删除找某一个关键字

88、线索二叉树

●问题描述:建立一个中序线索二叉树,并且完成中序遍历。求该中序线

索二叉树上已知结点在中序的前驱和后继;

89、约瑟夫环问题

●问题描述:设编号为1,2,3,……,n的n(n>0)个人按顺时针方向围

坐一圈,每个人持有一个正整数密码。开始时任选一个正整数作为报数

上限m,从第一个人开始顺时针方向自1起顺序报数,报到m是停止报

数,报m的人出列,将他的密码作为新的m值,从他的下一个人开始

重新从1报数。如此下去,直到所有人全部出列为止。令n最大值取30。

要求设计一个程序模拟此过程,求出出列编号序列。

90、表达式求值(※)

●问题描述:从键盘上输入中缀算数表达式,计算出表达式的值。

●基本要求:

1.程序对所输入的表达式做简单的判断,如果表达式有错,能给出适当

的提示。

2.能处理+、-、×、÷这四种基本的算术运算符。

91、求图的中心点(※)

●问题描述:假设有一个公司在某个地区有n个产品销售点,现根据业务

需要打算在其中某个销售点上建立一个中心仓库负责向其他销售点提

供产品。由于运输路线不同,运输费用也不同。假定每天需要向每个销

售点运输一次产品,那么应将中心仓库建在哪个销售点上才能使运输费

用最低。

92、集合的交、并和差运算的实现(※)

●问题描述:用有序单链表表示集合,实现集合的交、并、差运算

●基本要求:空间复杂度为O(1)

93、单链表实现十进制大整数运算(※)

●问题描述:使用单链表实现不限大小的整数,每个结点存储一位数字,

要求实现加、减运算。即能从键盘上输入两个大整数,比如:

12345123451234512345和-11111111111111111111,则加的结果应为:

01234012340123401234;减的结果应为:23456234562345623456。

●基本要求:从键盘上输入运算数和运算符,输出结果。

94、哈夫曼编码(※)

●问题描述:利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信

息传输时间,降低传输成本。这就要求在发送端通过一个编码系统对待

传数据预先编码,在接收端将传来的数据进行译码。对于双工信道(即可

以双向传输信息的信道),每端都需要一个完成的编\译码系统。试为这

样的信息收发站写一个哈夫曼的编\译码系统。

●基本要求:

1.初始化。从终端读入字符集大小n,以及n个字符和n个权值,

建立哈夫曼树。

2.编码。利用已建好的哈夫曼树,对正文进行编码。

3.译码。对编码好的内容进行译码。

4.打印编码。

95、稀疏矩阵运算器(※)

●问题描述:实现两个稀疏矩阵的加、减、乘运算。

●基本要求:可用三元组顺序表存储稀疏矩阵,矩阵的运算结果以通常的

阵列形式输出。

96、校园导游程序(※)

●问题描述:用无向图表示你所在学校的景点平面图,图中顶点表示主要

景点,存放景点的编号、名称、简介等信息,图中的边表示景点间的道

路,存放路径长度等消息。

●基本要求:

1.能查询各景点的相关信息

2.为来访客人提供景点的问路查询,即已知一个景点,查询到某

景点之间的一条最短路径及长度。

97、八皇后问题(※)

●问题描述:八皇后问题,是一个古老而著名的问题,是回溯算法的典型

例题。该问题是十九世纪著名的数学家高斯1850年提出:在8×8格的

国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能

处于同一行、同一列或同一斜线上。

●基本要求:统计总共有多少种摆法,并以一定方式输出摆好的格局。

98、平衡二叉树操作演示(※)

●问题描述:利用平衡二叉树实现动态查找表。

●基本要求:设计平衡二叉树实现动态查找表的操作演示。

(1)实现动态查找表的三种基本功能:查找、插入、删除。

(2)合并两棵平衡二叉树。

(3)分解两棵平衡二叉树。

99、设有一个正整数序列组成的有序单链表(按递增次序有序,且允许有相

等的整数存在),试编写能实现下列功能的算法:(要求用最少的时间和最小的空间)(※)

(1)确定在序列中比正整数x大的数有几个(相同的数只计算一次,如序列

{20,20,17,16,15,15,11,10,8,7,7,5,4}中比10大的数有5个);

(2) 在单链表将比正整数x小的数按递减次序排列;

(3) 将正整数比x大的偶数从单链表中删除。

设计要求:

(1)每名同学任选三题;标※号的题为选做题,完成有加分;

(2)学生应明确设计任务和要求,并拟定设计计划,按时完成;

(3)设计分阶段进行,每一阶段的设计没有原则错误时才能允许进行下一阶段设计;

(4)设计过程中,提倡独立思考、深入钻研,主动地、创造性地进行设计;

(5)要求设计态度严肃认真、有错必改。

三、对课程设计说明书撰写内容、格式、字数的要求

1.课程设计说明书是体现和总结课程设计成果的载体,主要内容包括:设计题目、设计目的、设备器材、设计原理及内容、设计步骤、遇到的问题及解决方法、设计总结、参考文献等。一般不应少于3000字。

2.在适当位置配合相应的实验原理图、功能模块图、算法流程图等图表进行说明。应做到文理通顺,内容正确完整,书写工整,装订整齐。

3.设计总结部分主要写本人完成工作简介以及自己的设计体会,包括通过课程设计学到了什么,哪里遇到了困难,解决的办法以及今后的目标。

4.课程设计说明书手写或打印均可。手写要用学校统一的课程设计用纸,用黑或蓝黑墨水工整书写;打印时采用A4纸,页边距均为20mm,正文采用宋体小四号字,行间距18磅。文中大标题采用黑体小三号字,一级节标题采用黑体四号字,二级节标题采用黑体小四号字,表题与图题采用宋体五号字。

5.课程设计说明书装订顺序为:封面、任务书、成绩评定表、目录、正文、参考文献。

四、设计完成后应提交成果的种类、数量、质量等方面的要求

1.完成“任务书”中指定的功能,运行结果正确。

2.课程设计报告。

五、时间进度安排

顺序阶段日期计划完成内容备注

1 第1天阅读资料及系统分析设计

2 第2-5天程序编制

3 第6-7天程序调试

4 第8-9天成绩评定

5 第10天书写课程设计说明书

六、主要参考资料(文献)

[1]《数据结构》,清华大学出版社,2001,严蔚敏吴伟民

[2]《数据结构题集》,清华大学出版社,1999,严蔚敏吴伟民

[3]《数据结构习题与解析》,清华大学出版社,2006,李春葆

[4]《数据结构》,高等教育出版社,2006,许卓群

[5]《数据结构习题解析》,清华大学出版社,2011,殷人昆