（完整版）数据结构复习题（附答案）.pdf

（（完完整整版版））数数据据结结构构复复习习题题（（附附答答案案））

⼀、算法设计题（每题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.IOIIOIOO

B.IOOIOIIO

.IIIOIOIO

D.IIIOOIOO

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

操作序列已存⼊⼀维数组中）。

5、设从键盘输⼊⼀整数的序列：a1,a2,a3，…，an,试编写算法实现：⽤栈结构存储输⼊的整数，当ai≠-1时，将ai进栈；当

ai=-1时，输出栈顶整数并出栈。算法应对异常情况（⼊栈满等）给出相应的信息。

设有⼀个背包可以放⼊的物品重量为S，现有n件物品，重量分别为W1，W2，...，Wn。问能否从这n件物品中选择若⼲件放

⼊背包，使得放⼊的重量之和正好是S。设布尔函数Knap(S，n)表⽰背包问题的解，Wi(i=1,2,...，n)均为正整数，并已顺序存

储地在数组W中。请在下列算法的下划线处填空，使其正确求解背包问题。

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，则顺序栈的容量⾄少应为多少？画出具体进栈、出栈过程。

假定采⽤带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如：

设str1和str2是分别指向两个单词的头结点，请设计⼀个尽可能的⾼效算法，找出两个单词共同后缀的起始位置，分析算法时

间复杂度。

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

法，将R中保存的序列循环左移p（0pn）个位置，即将r中的数据（x0,x1,=x2,…,=x=n-1），变换为(x=p，x=p

＋1,=…=,=n-1=,x0,=x1,…,=p-1)。=p=bdsfid=96