数据结构复习题(附答案)

算法设计题（每题15分，共60分）答题要求： = 1 \* GB3 ①用自然语言说明所采用算法的思想； = 2 \* GB3 ②给出每个算法所需的数据结构定义，并做必要说明； = 3 \* GB3 ③

一、 （每题15分，共60分） 算法设计题 答题要求： ① 用自然语言说明所采用算法的思想； ② 给出每个算法所需的数据结构定义，并做必要说明； ③ 写出对应的算法程序，并做必要的注释。 1info 、有一个带头结点的单链表，每个结点包括两个域，一个是整型域，另一个是指向下 next 一个结点的指针域。假设单链表已建立，设计算法删除单链表中所有重复出现的结点， info 使得域相等的结点只保留一个。 3Josephus12…nnn>0 、约瑟夫环问题（问题）是指编号为、、，的（）个人按顺时针方向 sm 围坐成一圈，现从第个人开始按顺时针方向报数，数到第个人出列，然后从出列的下 m… 一个人重新开始报数，数到第的人又出列，，如此重复直到所有的人全部出列为止。 现要求采用循环链表结构设计一个算法，模拟此过程。 4、编程实现单链表的就地逆置。 23．在数组A[1..n]中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求 链中数据从小到大排列，重复的数据在链中只保存一个. 5、设计一个尽可能的高效算法输出单链表的倒数第K个元素。 3IO 、假设以和分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序 IO 列可表示为仅由和组成的序列，称可以操作的序列为合法序列，否则称为非法序列。 15 （分） 1 （）下面所示的序列中哪些是合法的？ A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO 21 （）通过对（）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回 truefalse ，否则返回（假定被判定的操作序列已存入一维数组中）。 5 、设从键盘输入一整数的序列：a1,a2,a3，…，an,试编写算法实现：用栈结 构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出 栈。算法应对异常情况（入栈满等）给出相应的信息。 设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为W，W，...，W。问能 12n 否从这n件物品中选择若干件放入背包，使得放入的重量之和正好是S。设布尔函数Knap(S， n)表示背包问题的解，W(i=1,2,...，n)均为正整数，并已顺序存储在数组W中。请在下 地 i 列算法的下划线处填空，使其正确求解背包问题。 Knap(S，n) 若S=0 则Knap←true 否则若（S<0）或(S>0且n<1) 则Knap←false 否则若Knap(1),_=true 则print(W[n])；Knap←true 否则Knap←Knap(2)_,_