数据结构课程设计分类题目

1、线性表顺序表：K设有一元素为整数的线性表“匕,g辽宀,存放在一维数组AN中设计一个算法, 以表中盟作为参考元素，將该表分为左、右两局部其中左半局部每个元素小于等于右半 局部每个元素都大于5 d位于分界位置上要求结果仍存放在AN中人2一设线性表存于Al"涮的前num各分量中,且递增有序。请设计一个算法，将x插入 到线性表的适当位置上，以保持线性表的有序性*3. 线性表仏 如曲"山中元素递地有序且按顺序存储于计算机内。要求设计一算法完成: Q用最少时间在表中查找数值为X的元素6C刃假设找到将共与后维元素位置相交换。3 ：假设找不到将其插入表中并使表中元素仍递增有序o4己知数组A

2、COlnl的元素类型为int,试设计算法将其调整为左右两个局部左边所有 元素为奇数耿右边所有元素为偶数。5、设计一个算法从顺序表L中删除所有值为x的元素6、设计一介算法从顺序表L中删除所有值为x到y之间皿可?的元素 *4丫 <©链表： 上工1>假设有两个按元素值递增次序排列的线性表,均以单链表形式存储6请编写算法将这两' 个单链表归并为一个按元素值递减次序排列的单链表，:并要求利用原来两个单链表的结点存 放归并后的单链表，2. 己知LI、L2分别为两循环单链表的头结点指针 m,n分别为LX L2表中数据结点个数。 要求设计算法.用最快速度将两表合并成个带头结点的循

3、坏单链表A了 r£ f FGF；3. 设L为单链表的头结点地址F其数据结点的数据都是正整数且无相同的,设计一个将该 链表整理成数据递增的有序单链表的算法右5、设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B级G,其中B表的 结点为A表中值小于零的结点，而C表的结点为A表中值夫于零的结点C链表扎的元素类型 为整型，要求B/C表利用A表的结点人6、试编写在带头结点的单链表中删除K一个最歩值结点的高效算法g7、设L为单链表的头结点地址，请写一算血 将链表中数据域值最小的那个链结点移到链 表的最前面臨要求;不得额外申请新的链结啟8、己知两个单链表A和民其头指针分别为hada和h

4、eadb,编写一个过程从单链表A申删 除自第i个元素起的共 山 个元素，然后将单链表A插入到单链表B的第j个元素之前宴9、递增有序的单链表A,B分别存僻了亠个集纭请设计算法以求岀两个集合A和B的 姝A-B ®仪由程A中出现而忝津且中出M云素所构翩掳佑九并図同粹册绒存储, 同时返回该集音的元素个数.5；10、己知r卒单链表中每个结点存放一个整数，并且结点数不少于2,请设计算法以判断 该链表中第二项起的每个元素值是否等于其序号的平方减去其前驱的值訂假设满足那么返回丁 V*9%9*"tiire> 否那么返回 false. . r . . . . 11、两个整数序列A=alt

5、：a2f a3,:am和B=bl, b2, b3,bn已经存入两个单链表中箕设计一 金算法；判断序列B是否是序列A的子序列o12、：p指向双向循坏链表中的一个结点其结点结构为data. Llink、Fink三个域, 写出算法change p,交换p所指向的结点和它的前缀结点的顾序.13、设有一个由正整数组成的无序单链表'编写莞成以下功能的算法工1找出最小值结点；且打印该数值；2假设该数值是奇数，那么将其与直接后继结点的数值交换；2交假设该数值是偶数，那么将其直接后继结点删除和14、在一个递增有序的线性表中，有数值相同的元素存在。假设存储方式为单链表，设计算法 去掉数值相同的元素，使表中

6、不再有重复的元素。例如j 広10, ：10, 21, ：30, 42, 42 . 42, 51, 70?将变作7, 10, 21, 30, 42, 51, 70；15、设有一个正整数序列组成的有序单链表按递增次序有序，且允许有相等的整数存在* 试编写能实现以下功能的算法：要求用最少的时间和最小的空闾确麗在序列申比正整数&大的数看几个相同的数只计負一洛 如序列.20> 20,17,16, 15/15,11,10, 8, £ 7, 5. 4中比 10 夫的数有 5个；2在单链表将比正鹽数x小的数按递减次序排列；inn 将正整数4比川夫的偶数从单链表中删除。16、编写一个算法

7、来交换单链表中指针P所指结点身其后继结点，HEAD是该链表的头指针, P指向该琏表中某一结点°斤lial17；. B知三个带头结点的线性链表A, B和C中的结点均依元素值自小至夫非递减排列可 能存在两个以上值相同的结点?编写算法对A表进行如下操作：使操作后的链表A中仅留 卞三个表中均包含的数据元素的结点，且没有值相同的结点趴并释放所有无用结点.限定算 法的时间复杂度为0 nrhl+pT其車m、n和卫分别为三个表的长度©栈和队列 L.设计一个算法，利用栈的根本运算将指定栈中的内容逆转也2、设计一个算法，利用栈的根本运算返回指定栈中栈底元素。3、设有两个栈Si,0都采用顺序栈方

8、式，并且共享一个存储区0. - maxsize-lL为了尽量利 用空间，减少溢出的可能.可采用栈顶相向厂迎面增长的存僻方式。试设讦S对空有关入栈 和出栈的操作算法§4、设从键盘输入一整数的序列:如隔as,，比,试编写算法实现：用栈结构存储输入的 整数，当辺亠1时将亦进栈；Ma 1时片输出栈顶整数并出栈。算法应对异常情况入 栈满等工给出相应的信息电4设表达式以字符形式已存入数组EM中为表达式的结束符，试写出判断表达式中 括号和是否配对的C语言描述算法：EXYX(E)算法中可调用栈操作的基M氐)5、从犍盘上输入1个逆波兰表达式用伪码写出其求值程序-规定：逆波兰表达式的长度. 不超过：短

9、以$符作为输入结束，操作数之间用空格分隔二操作符只可能有2皐*、/四种 运算。例如躍234 34+2*$6、写出f 算法，:判定所给的操作序列是否合法孕假设合法，返回truer否那么返回false (假 定被判定的操作序列已存入一维数组中)。，:7“设计r冷算法，判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的 单循坏链表中.每个结点有两个域；eh和link,其中品域为字符类型、8. 请利用两个栈S1和S2来模拟一个队列.己知栈的兰个运算定叉如艮PUSH(ST,x)：元素 r.2A 刍x A ST g； POP (ST, x): ST栈顶元素出栈,赋给变量心Sempty (ST)

10、:判ST；栈是否为空唆 那么如何刹用横的运昴冈现達虞列的三个运龜由询曄嗨:质入严木茹素入凰预h趣触如! 删除一个元素出队列:queueempty：判队列为空盘(请写明算法的思想及必要的注释)9. 假设以帯头结点的循环链表表示队列并且只设一个指针指向队尾结点，但不设头指针， 如下图(编者略/请写出相应的入队列和出队列算法。10. 如果允许在循环队列的两端都可以进行插入和删除操作。要求(D写出循环队列的类型定义：(2)写出童从队尾删除"和餵从队头插入的算法电11. 在一个循环链队中貝有尾指针(乜为rear结点结构为数据域data,指针域next), 请给出这种队列的入队和出队操作的实现过

11、程事12. 己知Q是一个非空队列.S是一个空栈勺仅用队列和栈的操作編写一个算法，将队列Q 中的所宥元素逆置。13. 求两个正整数m与II的最犬公因子的过程用自然语言可以表述为反复执行如卞动作= 第一步厂假设n等于零，那么返回眄 第二步:善m小于m那么m身n相宜交换;杏那么总:保存m 然后将n送m,将保存的m除以n的余数送M£1?将上述过程用递归函数表达出来C设求x除以y的余数可以用次MOD y形武表示人 (2)写出求解该递归函数的非递归算法° p 14. 试将以下递归过程改写为非递归过程。void test (int: &sum) int x；scanf(x)；:i

12、f (x=0) sum=0 else test (sum)sum+=X7卜 printf (sum) ；.树和二叉树U二叉树用二叉链表存储，写一个算法将二叉树中的叶子结点按从右至左的顺序建立f 单碎；2知二叉树用二叉链表存储，写出求二叉树宽度的算法.所谓宽度是指在二叉树的各层上, 具有结点数最多的那一层上的结点总数。3、叉树用二叉链表存储，写一个算法交换各结点的左右子树。4、二叉树用二叉链表存储？假设结点的左孩子的数据域的值犬于右孩子数据域的值那么交换 其左右子松5、6s叉树用二叉链表存储，：編写亠算法,判别给定的二叉树是否为完全二叉树?个结点的完全二叉树以一维数组为存储结构,编写非递归算法实

13、现对该树的先序遍 历i编写一算法在二叉树中查找值为X的结点，并打印值为X的结点的所有祖先结髭U!编写中序遍历二叉树的非递归算法右编写先序遍历二叉树的非递归算法10、编写后序二叉树的非递归負法鱼11、叉树用二叉链表存储，任给一个二叉树表示的四那么运算表达式，编写算法，由该二叉树 输出该表达式,着原表达式有括号亦加上12、有n个结点的完全U叉树存放在一维数组Al.n中试据此建立;一棵用二叉链表表示 的二叉树根由tree指向*13、二叉树排序方法如下：(1) 将第一个数据放在树根.(2) 将随后读入的数据与树根中的数据相比拟,.假设比树根戈：那么置于右子树，反之那么 置于左子树建成一棵二叉树；(3)

14、 利用中序遍历打印排序结果-用C语言编写二叉树的排序程序“14、二叉树结点的平衡因子(bf)定义为该结点的左子树高度与右子树高度之差。编写算法 讦算二叉树中辛令结点的平衡因長15设计算法丫统计一棵二叉树申所有叶结点的数目及非叶结点的数目。心己知二叉树以二叉链表存储厂编写算法完成对于树中每一个元素值为裏的结点复，删去 以它为根的子树，并释放相应的空歐17试编写算法，对一棵以孩子一兄弟链表表示的树统计叶子的个数。18、设r棵二叉树中各结点的值互不相同卜其前序序列和中序序列分别存于两个一维数组 preL小和midtL . n 申，试遍写算法建立该二叉树的二叉链表乜19、试设讦一个算法打印出由根结点出

15、发到达叶结点的所看路径。20、试写出算法?求任意二叉树中第-条最长的路注长度,并输出此路径上各结点的值。21、给定一组项及其权值复假定项都存放于二叉树的树叶结点,那么具有最小带权外部路径长 度的树称为huff man树。编写构造huff man树的算法®22i :一中序线索二叉树写一算法完成对它的中序扫描厲23中序线索二叉树T右子树不空。设计算法，将S所指的结点作为T的右子树中的一 个叶孑结点插入进去并使之成为T的右子树的(中序序列)第一个结点同时要修改相应 的线索关系I1¥24. 写出算法求出中序线索二叉树中给定值为x的结点之后继结点,返回孩后継结点的指针°线索

16、树中结点结构为:(ltag, lc, data, re, rtag)®其中氏data存放结点的M; lc» re 为指向左.右孩子或该结点前驱或后继的指针：班询h屈为标志域，各值为：0 m：ic, re为指向左右孩子的指针;值为1那么g re为指向某前驱后继结点的指针25、镀后序妁蠢材申绪点构猊触無，诅盟些理與RQKi ld»舉唧».奂机匚坦筋僅为、 O At诚五4&嗣迅班别疝叨喻h咅那么涵另直蕨斶，左癒繼的线為 無諭社 后序线索树上找給定结点p：的直接前驱谊的算法叭1. 设无向图G有n个顶点八m条边。试编写用邻接表存储该图的算法设顶点值用Kn

17、戒Ur注T.覇号2有向图有n个顶点;请写算法,根据用户输入的偶对建立该有向图的邻接表。即接受 用户输入的vvjm其中之一为0标志结束人对于每条这样的边，申请一个结点?并插入 到的单链表中如此反龙直到将图中所有边处理完毕提示:先产生邻接衣的忑个头结点其 结点数值域从到迫七3、给出以十字链表作存储结构建佥图的算法相输入® j ®其中id为顶点号宀为权值。4. 设有向G图有n个点用h2 rn表示心条边，写一算法建立有向图的逆邻接表。5、6、7>设已给出图的邻接矩阵，要求将图的邻接矩阵转化为邻接表，试实现其算法， 编写算法,将图的邻接矩阵存储改为邻接表的存储。试写一算法，判断

18、以邻接表方式存储的有向图中是杏存在由顶点哲到顶点碍的路径 8己知无向图采用邻接表存储方式,.试写出删除边订3的算法牛9、假设有向图以邻接表存储，试编写算法删除弧%碇的算法。10i假设有向图以十字链表存储,试编写算法，插入弧V沢12、设有向图用邻接表表示，图有n个顶馬表示为1至n,试写一个算法求顶鳥k的入度 lXk3 :14*15；16,1旅13. 写出图的深度优先搜索DFS算法的非递归算激 带权图用邻接矩阵表示,.编习函数实现用Kruskal 法构造最小生成树的算法" 编写函数实现用Prim算法构造最小生成树的竟法。编写函数实现从指定顶点到其余各顶点的最短路径的Dijkstra算法。实现图的拓扑排序算法查找和排序k设计一个二分查找的递归算法牡2、设计一个會法，利用二分查找算法在一个有序表中插入一个元素&并保持表的有序性。3、实现散列表的相关算法(1) 给定一个序列和散列函数,：并利用线性探测再散列处理冲突，建立