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

一、算法设计题（每题15分，共60分）

答题要求：

①用自然语言说明所采用算法的思想；

②给出每个算法所需的数据结构定义，并做必要说明；

③写出对应的算法程序，并做必要的注释。

1、有一个带头结点的单链表，每个结点包括两个域，一个是整型域info，另一个是指向下

一个结点的指针域next。假设单链表已建立，设计算法删除单链表中所有重复出现的结点，

使得info域相等的结点只保留一个。

3、约瑟夫环问题（Josephus问题）是指编号为1、2、…，n的n（n0）个人按顺时针方向

围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下

一个人重新开始报数，数到第m的人又出列，…，如此重复直到所有的人全部出列为止。

现要求采用循环链表结构设计一个算法，模拟此过程。

4、编程实现单链表的就地逆置。

23．在数组A[1..n]中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求

链中数据从小到大排列，重复的数据在链中只保存一个.

5、设计一个尽可能的高效算法输出单链表的倒数第K个元素。

3、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序

列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。（15

分）

（1）下面所示的序列中哪些是合法的？

A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO

（2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回

true，否则返回false（假定被判定的操作序列已存入一维数组中）。

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

否则若（S0）或(S0且n1)

则Knap←false

否则若Knap(1),_=true

则print(W[n])；Knap←true

否则Knap←Knap(2)_,_

设有一个顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素的出栈顺序为s2,s3,s4,

s6,s5,s1，则顺序栈的容量至少应为多少？画出具体进栈、出栈过程。

假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存

储空间。例如：

str1str

ing

str2be

设str1和str2是分别指向两个单词的头结点，请设计一个尽可能的高效算法，找出两个单

词共同后缀的起始位置，分析算法时间复杂度。

将n(n1)个整数存放到一维数组R中。设计一个尽可能高效（时间、空间）的算

法，将R中保存的序列循环左移p（0pn）个位置，即将R中的数据（x,x,x,…,x），

012n-1

变换为(x，x,…,x,xx…,x)。

pp＋1n-10,1,p-1

4．编