《数据结构课程设计分类题目》由会员分享，可在线阅读，更多相关《数据结构课程设计分类题目（7页珍藏版）》请在金锄头文库上搜索。
1、线性表顺序表：1、设有一元素为整数的线性表L=（a ,a ,a3, ,&）,存放在一维数组AN中，设计一个算法，1 2 n以表中a作为参考元素，将该表分为左、右两部分其中左半部分每个元素小于等于a ,右半nn部分每个元素都大于a, a位于分界位置上（要求结果仍存放在AN中）。n n2、设线性表存于A1.size的前num各分量中，且递增有序。请设计一个算法，将x插入 到线性表的适当位置上，以保持线性表的有序性。3、线性表（a1,a2,a3,a“）中元素递增有序且按顺序存储于计算机内。要求设计一算法完成：（1）用最少时间在表中查找数值为x的元素。（2）若找到将其与后继元素位置相交换。（3）若找不
2、到将其插入表中并使表中元素仍递增有序。4、已知数组A0:n-1的元素类型为int,试设计算法将其调整为左右两个部分，左边所有 元素为奇数，右边所有元素为偶数。5、设计一个算法从顺序表L中删除所有值为x的元素6、设计一个算法从顺序表L中删除所有值为x到y之间（x=y）的元素链表：1、假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两 个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存 放归并后的单链表。2、已知L1、L2分别为两循环单链表的头结点指针，m,n分别为L1、L2表中数据结点个数。 要求设计一算法，用最快速度将两表合并成一个带头结
3、点的循环单链表。3、设L为单链表的头结点地址，其数据结点的数据都是正整数且无相同的，设计一个将该 链表整理成数据递增的有序单链表的算法。5、设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C,其中B表的 结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型 为整型，要求B、C表利用A表的结点）。6、试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。7、设L为单链表的头结点地址，请写一算法，将链表中数据域值最小的那个链结点移到链 表的最前面。要求：不得额外申请新的链结点。8、已知两个单链表A和B,其头指针分别为heada和headb,编写
4、一个过程从单链表A中删 除自第i个元素起的共len个元素，然后将单链表A插入到单链表B的第j个元素之前。9、已知递增有序的单链表A,B分别存储了一个集合，请设计算法以求出两个集合A和B的 差集A-B （即仅由在A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储, 同时返回该集合的元素个数。10、已知一个单链表中每个结点存放一个整数，并且结点数不少于2，请设计算法以判断 该链表中第二项起的每个元素值是否等于其序号的平方减去其前驱的值，若满足则返回 ture，否则返回false.11、两个整数序列A=a1,a2,a3,，am和B=b1,b2,b3,bn已经存入两个单链表中，设计一 个算
5、法，判断序列B是否是序列A的子序列。12、已知p指向双向循环链表中的一个结点，其结点结构为data、llink、rlink三个域， 写出算法change（p）,交换p所指向的结点和它的前缀结点的顺序。13、设有一个由正整数组成的无序单链表，编写完成下列功能的算法：（1）找出最小值结点，且打印该数值；（2）若该数值是奇数，则将其与直接后继结点的数值交换；（3）若该数值是偶数，则将其直接后继结点删除。14、在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法 去掉数值相同的元素，使表中不再有重复的元素。例如：（7，10，10，21，30，42，42，42， 51，70）将变
6、作（7，10，21，30，42，51，70）。15、设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在）， 试编写能实现下列功能的算法 ：（要求用最少的时间和最小的空间）（1）确定在序列中比正整数 x 大的数有几个（相同的数只计算一次， 如序列20,20,17,16,15,15,11,10,8,7,7,5,4中比10大的数有5个）；（2）在单链表将比正整数x小的数按递减次序排列；（3）将正整数（比）x大的偶数从单链表中删除。16、编写一个算法来交换单链表中指针P所指结点与其后继结点，HEAD是该链表的头指针, P 指向该链表中某一结点。17、.已知三个带头结点的线性链表
7、A、B和C中的结点均依元素值自小至大非递减排列（可 能存在两个以上值相同的结点），编写算法对A表进行如下操作：使操作后的链表A中仅留 下三个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算 法的时间复杂度为0 （m+n+p）,其中m、n和p分别为三个表的长度。栈和队列1、设计一个算法，利用栈的基本运算将指定栈中的内容逆转。2、设计一个算法，利用栈的基本运算返回指定栈中栈底元素。3、设有两个栈Si5S2都采用顺序栈方式，并且共享一个存储区O.maxsize-1,为了尽量利 用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计s1,s2有关入栈 和出栈的操作
8、算法。4、设从键盘输入一整数的序列：a1, a2,巴，an，试编写算法实现：用栈结构存储输入的 整数，当aM-l时，将a进栈；当；=-1时，输出栈顶整数并出栈。算法应对异常情况(入iii栈满等)给出相应的信息。4、设表达式以字符形式已存入数组En中，#为表达式的结束符，试写出判断表达式中 括号(和)是否配对的C语言描述算法：EXYX(E);(注：算法中可调用栈操作的基 本算法。)5、从键盘上输入一个逆波兰表达式，用伪码写出其求值程序。规定：逆波兰表达式的长度 不超过一行，以$符作为输入结束，操作数之间用空格分隔,操作符只可能有+、-、*、/四种 运算。例如：234 34+2*$6、写出一个算法
9、，判定所给的操作序列是否合法。若合法，返回true，否则返回false (假 定被判定的操作序列已存入一维数组中)。7、设计一个算法，判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的 单循环链表中，每个结点有两个域：ch和link,其中ch域为字符类型。8、请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下：PUSH(ST,x):元素 x入ST栈；POP(ST,x): ST栈顶元素出栈，赋给变量x； Sempty(ST):判ST栈是否为空。 那么如何利用栈的运算来实现该队列的三个运算:enqueue:插入一个元素入队列；dequeue: 删除一个元素出队列；queue
10、_empty：判队列为空。(请写明算法的思想及必要的注释)9、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针， 如图所示(编者略)，请写出相应的入队列和出队列算法。10、如果允许在循环队列的两端都可以进行插入和删除操作。要求：(1) 写出循环队列的类型定义；(2)写出“从队尾删除”和“从队头插入”的算法。11、在一个循环链队中只有尾指针(记为rear，结点结构为数据域data,指针域next), 请给出这种队列的入队和出队操作的实现过程。12、已知Q是一个非空队列，S是一个空栈。仅用队列和栈的操作编写一个算法，将队列Q 中的所有元素逆置。13、已知求两个正整数m与
11、n的最大公因子的过程用自然语言可以表述为反复执行如下动作： 第一步：若n等于零，则返回m；第二步：若m小于n,则m与n相互交换；否则，保存m, 然后将n送m,将保存的m除以n的余数送n。(1) 将上述过程用递归函数表达出来(设求x除以y的余数可以用xMODy形式表示)。(2) 写出求解该递归函数的非递归算法。14、试将下列递归过程改写为非递归过程。void test(int &sum) int x；scanf(x)；if(x=0) sum=0 else test(sum); sum+=x;printf(sum)；树和二叉树1、二叉树用二叉链表存储，写一个算法将二叉树中的叶子结点按从右至左的顺序
12、建立一个 单链表。2、知二叉树用二叉链表存储，写出求二叉树宽度的算法。所谓宽度是指在二叉树的各层上， 具有结点数最多的那一层上的结点总数。3、叉树用二叉链表存储，写一个算法交换各结点的左右子树。4、二叉树用二叉链表存储，若结点的左孩子的数据域的值大于右孩子数据域的值，则交换 其左右子树。5、叉树用二叉链表存储，编写一算法，判别给定的二叉树是否为完全二叉树。6、个结点的完全二叉树以一维数组为存储结构，编写一非递归算法实现对该树的先序遍 历。7、编写一算法，在二叉树中查找值为x的结点，并打印值为x的结点的所有祖先结点。8、编写中序遍历二叉树的非递归算法。9、编写先序遍历二叉树的非递归算法。10、编
13、写后序二叉树的非递归算法。11、叉树用二叉链表存储，任给一个二叉树表示的四则运算表达式，编写算法，由该二叉树 输出该表达式，若原表达式有括号亦加上。12、有n个结点的完全二叉树存放在一维数组Al.n中，试据此建立一棵用二叉链表表示 的二叉树，根由 tree 指向。13、二叉树排序方法如下：（1）将第一个数据放在树根。（2）将随后读入的数据与树根中的数据相比较，若比树根大，则置于右子树，反之则 置于左子树，建成一棵二叉树；（3）利用中序遍历打印排序结果。用C语言编写二叉树的排序程序。14、二叉树结点的平衡因子（bf）定义为该结点的左子树高度与右子树高度之差。编写算法 计算二叉树中各个结点的平衡因
14、子。15、设计算法：统计一棵二叉树中所有叶结点的数目及非叶结点的数目。16、已知二叉树以二叉链表存储，编写算法完成:对于树中每一个元素值为x的结点，删去 以它为根的子树，并释放相应的空间。17、试编写算法，对一棵以孩子兄弟链表表示的树统计叶子的个数。18、设一棵二叉树中各结点的值互不相同，其前序序列和中序序列分别存于两个一维数组 pre1.n 和mid1.n 中，试遍写算法建立该二叉树的二叉链表。19、试设计一个算法打印出由根结点出发到达叶结点的所有路径。20、试写出算法，求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。21、给定一组项及其权值，假定项都存放于二叉树的树叶结点，则
15、具有最小带权外部路径长 度的树称为huffman树。编写构造huffman树 的算法。22、已知一中序线索二叉树,写一算法完成对它的中序扫描。23、已知中序线索二叉树T右子树不空。设计算法，将S所指的结点作为T的右子树中的一 个叶子结点插入进去，并使之成为T的右子树的（中序序列）第一个结点（同时要修改相应 的线索关系）。24、写出算法，求出中序线索二叉树中给定值为x的结点之后继结点，返回该后继结点的指 针。线索树中结点结构为：(ltag,lc,data,rc,rtag)。其中，data存放结点的值；lc, rc 为指向左、右孩子或该结点前驱或后继的指针；ltag，rtag为标志域，各值为：0,则lc, rc为指向左、右孩子的指针；值为1,则lc, rc为指向某前驱后继结点的指针25、设后序线索树中结点构造为(Ltag,Lchild,Data,Rchild,Rtag)。其中：Ltag,Rtag值为 0时丄child、Rchild分别为儿子指针；否则分别为直接前驱，直接后继的线索。请写出在 后序线索树上找给定结点p的直接前驱q的算法。1、设无向图G有n个顶点，m条边
