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

1、沈 阳 工 程 学 院课程设计任务书 课程设计题目： 数据结构与算法课程设计 系 别 信息工程系 班级 学生姓名 学号 指导教师 职称 课程设计进行地点： 任 务 下 达 时 间： 年 月 日起止日期： 年 月 日起至 年 月 日止教研室主任 年 月 日批准一、课程设计的原始资料及依据数据结构与算法课程设计是在完成数据结构理论课程学习之后进行的一个综合性的实践教学环节，是对课程理论和课程实验的一个补充。通过课程设计，培养学生综合运用已学过的理论和技能去分析和解决实际问题的能力，并使所学知识得到进一步巩固、深化和扩展。二、课程设计主要内容及要求设计内容：1、 设有一元素为整数的线性表L=(a1,

2、a2,a3,an),存放在一维数组AN中,设计一个算法,以表中an作为参考元素,将该表分为左、右两部分,其中左半部分每个元素小于等于an,右半部分每个元素都大于an, an位于分界位置上(要求结果仍存放在AN中)。2、 设线性表存于A1.size的前num各分量中，且递增有序。请设计一个算法，将x插入到线性表的适当位置上，以保持线性表的有序性。3、 线性表(a1,a2,a3,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法完成：4、 用最少时间在表中查找数值为x的元素。5、 若找到将其与后继元素位置相交换。6、 若找不到将其插入表中并使表中元素仍递增有序。7、 已知数组A0:n-1的

3、元素类型为int，试设计算法将其调整为左右两个部分，左边所有元素为奇数，右边所有元素为偶数。8、 设计一个算法从顺序表L中删除所有值为x的元素9、 设计一个算法从顺序表L中删除所有值为x到y之间（x=y）的元素10、 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。11、 已知L1、L2分别为两循环单链表的头结点指针，m,n分别为L1、L2表中数据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。12、 设L为单链表的头结点地址，其数据结点的数据

4、都是正整数且无相同的，设计一个将该链表整理成数据递增的有序单链表的算法。13、 设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。14、 试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。15、 设L为单链表的头结点地址，请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。16、 已知两个单链表A和B,其头指针分别为heada和headb，编写一个过程从单链表A中删除自第i个元素起的共len个元素

5、，然后将单链表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指向双向

6、循环链表中的一个结点，其结点结构为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、 编写

7、一个算法来交换单链表中指针P所指结点与其后继结点，HEAD是该链表的头指针，P指向该链表中某一结点。24、 已知三个带头结点的线性链表A、B和C中的结点均依元素值自小至大非递减排列（可能存在两个以上值相同的结点），编写算法对A表进行如下操作：使操作后的链表A中仅留下三个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为O（m+n+p），其中m、n和p分别为三个表的长度。25、 设计一个算法，利用栈的基本运算将指定栈中的内容逆转。26、 设计一个算法，利用栈的基本运算返回指定栈中栈底元素。27、 设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区O.

8、maxsize-1,为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。28、 设从键盘输入一整数的序列：a1, a2, a3，an,试编写算法实现：用栈结构存储输入的整数，当ai-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。29、 设表达式以字符形式已存入数组En中，#为表达式的结束符，试写出判断表达式中括号（和）是否配对的C语言描述算法：EXYX(E); (注：算法中可调用栈操作的基本算法。) 30、 从键盘上输入一个逆波兰表达式，用伪码写出其求值程序。规定：逆波兰表达式的长度

9、不超过一行，以$符作为输入结束，操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如：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栈是否为

10、空。那么如何利用栈的运算来实现该队列的三个运算：enqueue:插入一个元素入队列； dequeue:删除一个元素出队列；queue_empty：判队列为空。（请写明算法的思想及必要的注释）34、 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，如图所示（编者略），请写出相应的入队列和出队列算法。35、 如果允许在循环队列的两端都可以进行插入和删除操作。要求：（1）写出循环队列的类型定义；（2）写出“从队尾删除”和“从队头插入”的算法。36、 在一个循环链队中只有尾指针（记为rear，结点结构为数据域data，指针域next），请给出这种队列的入队和出队操作的实现

11、过程。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 els

12、e test(sum); sum+=x; printf(sum)； 40、 二叉树用二叉链表存储，写一个算法将二叉树中的叶子结点按从右至左的顺序建立一个单链表。41、 知二叉树用二叉链表存储，写出求二叉树宽度的算法。所谓宽度是指在二叉树的各层上，具有结点数最多的那一层上的结点总数。42、 叉树用二叉链表存储，写一个算法交换各结点的左右子树。43、 二叉树用二叉链表存储，若结点的左孩子的数据域的值大于右孩子数据域的值，则交换其左右子树。44、 叉树用二叉链表存储，编写一算法，判别给定的二叉树是否为完全二叉树。45、 个结点的完全二叉树以一维数组为存储结构，编写一非递归算法实现对该树的先序遍历。4

13、6、 编写一算法，在二叉树中查找值为x的结点，并打印值为x的结点的所有祖先结点。47、 编写中序遍历二叉树的非递归算法。48、 编写先序遍历二叉树的非递归算法。49、 编写后序遍历二叉树的非递归算法。50、 叉树用二叉链表存储，任给一个二叉树表示的四则运算表达式，编写算法，由该二叉树输出该表达式，若原表达式有括号亦加上。51、 有n个结点的完全二叉树存放在一维数组A1.n中，试据此建立一棵用二叉链表表示的二叉树 ，根由tree指向。52、 二叉树排序方法如下： （1）将第一个数据放在树根。 （2）将随后读入的数据与树根中的数据相比较，若比树根大，则置于右子树，反之则置于左子树，建成一棵二叉树；

14、（3）利用中序遍历打印排序结果。用C语言编写二叉树的排序程序。53、 二叉树结点的平衡因子（bf）定义为该结点的左子树高度与右子树高度之差。编写算法计算二叉树中各个结点的平衡因子。54、 设计算法：统计一棵二叉树中所有叶结点的数目及非叶结点的数目。55、 已知二叉树以二叉链表存储，编写算法完成：对于树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。56、 试编写算法，对一棵以孩子兄弟链表表示的树统计叶子的个数。57、 设一棵二叉树中各结点的值互不相同，其前序序列和中序序列分别存于两个一维数组pre1.n 和mid1.n 中，试遍写算法建立该二叉树的二叉链表。58、 试设计一个算

15、法打印出由根结点出发到达叶结点的所有路径。59、 试写出算法，求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。60、 给定一组项及其权值，假定项都存放于二叉树的树叶结点，则具有最小带权外部路径长度的树称为huffman 树。编写构造huffman 树 的算法。61、 已知一中序线索二叉树,写一算法完成对它的中序扫描。62、 已知中序线索二叉树T右子树不空。设计算法，将S所指的结点作为T的右子树中的一个叶子结点插入进去，并使之成为T的右子树的（中序序列）第一个结点（同时要修改相应的线索关系）。63、 写出算法，求出中序线索二叉树中给定值为x的结点之后继结点，返回该后继结点的指针。线

16、索树中结点结构为：（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条边。试编写用邻接表存储该图的算法。

17、（设顶点值用1n或0n-1编号） 66、 已知有向图有n个顶点,请写算法,根据用户输入的偶对建立该有向图的邻接表。即接受用户输入的(以其中之一为0标志结束),对于每条这样的边,申请一个结点,并插入到的单链表中,如此反复,直到将图中所有边处理完毕。提示：先产生邻接表的n个头结点（其结点数值域从1到n）。 67、 给出以十字链表作存储结构，建立图的算法，输入(i,j,v)其中i,j为顶点号，v为权值。68、 设有向G图有n个点(用1,2,n表示),e条边,写一算法建立有向图的逆邻接表。69、 设已给出图的邻接矩阵，要求将图的邻接矩阵转化为邻接表，试实现其算法。70、 编写算法，将图的邻接矩阵存储改

18、为邻接表的存储。71、 试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径（ij）。72、 已知无向图采用邻接表存储方式，试写出删除边（i，j）的算法。73、 假设有向图以邻接表存储，试编写算法删除弧的算法。74、 假设有向图以十字链表存储，试编写算法，插入弧。75、 设有向图用邻接表表示,图有n个顶点,表示为1至n,试写一个算法求顶点k的入度(1k0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数作为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如

19、此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。90、 表达式求值（）l 问题描述：从键盘上输入中缀算数表达式，计算出表达式的值。l 基本要求：1. 程序对所输入的表达式做简单的判断，如果表达式有错，能给出适当的提示。2. 能处理+、 这四种基本的算术运算符。91、 求图的中心点（）l 问题描述：假设有一个公司在某个地区有n个产品销售点，现根据业务需要打算在其中某个销售点上建立一个中心仓库负责向其他销售点提供产品。由于运输路线不同，运输费用也不同。假定每天需要向每个销售点运输一次产品，那么应将中心仓库建在哪个销售点上才能使运输费用最低。92、 集

20、合的交、并和差运算的实现（）l 问题描述：用有序单链表表示集合，实现集合的交、并、差运算l 基本要求： 空间复杂度为O(1)93、 单链表实现十进制大整数运算（）l 问题描述：使用单链表实现不限大小的整数，每个结点存储一位数字，要求实现加、减运算。即能从键盘上输入两个大整数，比如：12345123451234512345和-11111111111111111111，则加的结果应为：01234012340123401234；减的结果应为：23456234562345623456。l 基本要求： 从键盘上输入运算数和运算符，输出结果。94、 哈夫曼编码（）l 问题描述：利用哈夫曼编码进行通信可以大

21、大提高信道利用率，缩短信息传输时间，降低传输成本。这就要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码。对于双工信道(即可以双向传输信息的信道)，每端都需要一个完成的编译码系统。试为这样的信息收发站写一个哈夫曼的编译码系统。l 基本要求：1. 初始化。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树。 2. 编码。利用已建好的哈夫曼树,对正文进行编码。 3. 译码。对编码好的内容进行译码。 4. 打印编码。 95、 稀疏矩阵运算器（）l 问题描述：实现两个稀疏矩阵的加、减、乘运算。l 基本要求：可用三元组顺序表存储稀疏矩阵，矩阵的运算结果以通常的阵列形式

22、输出。96、 校园导游程序（）l 问题描述：用无向图表示你所在学校的景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等消息。l 基本要求： 1. 能查询各景点的相关信息2. 为来访客人提供景点的问路查询，即已知一个景点，查询到某景点之间的一条最短路径及长度。97、 八皇后问题（）l 问题描述：八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在88格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。l 基本要求：统计总共有多少种摆法，并

23、以一定方式输出摆好的格局。98、 平衡二叉树操作演示（）l 问题描述：利用平衡二叉树实现动态查找表。l 基本要求：设计平衡二叉树实现动态查找表的操作演示。（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)设计分阶段进行，每