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

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

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

3、分， 左边所有元素为奇数，右边所有元素为偶数.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个元素，然后将单链表A插入到 单链表B的

5、第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、编写一个算法来交换单链表中指针 P所

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

8、尽量利用空间，减少溢出的可能，可采用栈顶相向， 迎面增长的存储方式试设计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)，请给出这种队列的入队和出队操作的实现过程.37

11、、已知Q是一个非空队列，S是一个空栈.仅用队列和栈的操作编写一个算 法，将队列Q中的所有元素逆置.38、已知求两个正整数 m与n的最大公因子的过程用自然语言可以表述为反 复执行如下动作：第一步：若 n等于零，则返回m第二步：若m小于n， 则m与n相互交换；否则，保存 m,然后将n送m将保存的m除以n的余 数送n.(1) 将上述过程用递归函数表达出来(设求 x除以y的余数可以用x MOW 形式表示).(2) 写出求解该递归函数的非递归算法.39、试将下列递归过程改写为非递归过程.void test(i nt &sum) int x；sca nf(x)；if(x=0) sum=0 else

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

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

14、结果. 用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的结点之后继结点，返回该后继结点的指针.线索树中结点结构为：（ltag,lc,

16、data,rc,rtag ）.其中， data存放结点的值；lc，rc为指向左、右孩子或该结点前驱或后继的指针； ltag，rtag为标志域，各值为：0，则lc，rc为指向左、右孩子的指针；值 为1，则lc，rc为指向某前驱后继结点的指针64、设后序 线索树中结点 构造为（Ltag,Lchild,Data,Rchild,Rtag）. 其中:Ltag,Rtag 值为0时丄child、Rchild分别为儿子指针；否则分别为直 接前驱,直接后继的线索.请写出在后序线索树上找给定结点pA的直接前驱q的算法.65、设无向图G有n个顶点，m条边.试编写用邻接表存储该图的算法.（设 顶点值用1n或0n-1编

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

18、邻接表的存储.71、试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点V到顶点V的路径（i<>j ）.72、已知无向图采用邻接表存储方式，试写出删除边（i , j ）的算法.73、假设有向图以邻接表存储，试编写算法删除弧<V，V>的算法.74、假设有向图以十字链表存储，试编写算法，插入弧<V,Vj>.75、设有向图用邻接表表示,图有n个顶点,表示为1至n,试写一个算法求顶 点k的入度（1<k<n）.76、写出图的深度优先搜索DFS算法的非递归算法.77、写出图的广度优先搜索算法的非递归算法.78、已知带权图用邻接矩阵表示，编写函数实现用Kr

19、uskal算法构造最小生成树的算法.79、编写函数实现用Prim算法构造最小生成树的算法.80、编写函数实现从指定顶点到其余各顶点的最短路径的Dijkstra 算法.81、实现图的拓扑排序算法.82、设计一个二分查找的递归算法.83、设计一个算法，利用二分查找算法在一个有序表中插入一个元素x，并保持表的有序性.84、实现散列表的相关算法（1）给定一个序列，和散列函数，并利用线性探测再散列处理冲突，建立散列表.（2）编写函数，查找某一个关键字（3）编写函数，删除找某一个关键字85、设计一个顺序查找算法86、编写一个算法，统计 一个字符串中出现字符的次数87、实现二叉查找树的相关算法（1）给定序列

20、，创建一二叉查找树（2）判定一棵树是否为二叉查找树（3）采用递归和非递归算法，查找某一个关键字（4）编写函数，删除找某一个关键字88、线索二叉树问题描述：建立一个中序线索二叉树，并且完成中序遍历求该中序线索二叉树上已知结点在中序的前驱和后继；89、约瑟夫环问题问题描述：设编号为1, 2, 3，n的n（n>0）个人按顺时针方向围 坐一圈，每个人持有一个正整数密码.开始时任选一个正整数作为报数上 限m,从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数， 报m的人出列，将他的密码作为新的 m值，从他的下一个人开始重新 从1报数.如此下去，直到所有人全部出列为止.令n最大值取30.要求设

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

22、表表示集合，实现集合的交、并、差运算基本要求：空间复杂度为0（1）93、单链表实现十进制大整数运算（探）问题描述：使用单链表实现不限大小的整数，每个结点存储一位数字， 要求实现加、减运算.即能从键盘上输入两个大整数，比如：和,则加的结果应为： 减的结果应为：23456234562345623456.基本要求： 从键盘上输入运算数和运算符，输出结果.94、哈夫曼编码（探）问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本.这就要求在发送端通过一个编码系统对待 传数据预先编码，在接收端将传来的数据进行译码.对于双工信道（即可 以双向传输信息的信道），每端都需要一

23、个完成的编译码系统.试为这样的信息收发站写一个哈夫曼的编译码系统 基本要求：1. 初始化从终端读入字符集大小n,以及n个字符和n个权值，建 立哈夫曼树.2. 编码.利用已建好的哈夫曼树，对正文进行编码.3. 译码.对编码好的内容进行译码.4. 打印编码.95、稀疏矩阵运算器(探)问题描述：实现两个稀疏矩阵的加、减、乘运算 基本要求：可用三元组顺序表存储稀疏矩阵，矩阵的运算结果以通常的 阵列形式输出.96、校园导游程序(探)问题描述：用无向图表示你所在学校的景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道 路，存放路径长度等消息.基本要求：1. 能查询各

24、景点的相关信息2. 为来访客人提供景点的问路查询，即已知一个景点，查询到某 景点之间的一条最短路径及长度.97、八皇后问题(探)问题描述：八皇后问题，是一个古老而著名的问题，是回溯算法的典型 例题.该问题是十九世纪著名的数学家高斯 1850年提出：在8X 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) 每名同学任选三题；标号的题为选做题，完成有加分