数据结构习题线性表 栈 队列 75

rlink三个域， 写出算法change(p),交换 p 所指向的结点和它的前缀结点的顺序。

37.. 线性表(a1,a2,a3,?,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法完成：

（1） 用最少时间在表中查找数值为 x 的元素。 （2） 若找到将其与后继元素位置相交换。

（3） 若找不到将其插入表中并使表中元素仍递增有序。 【东北大学 1996 三 ( 12 分)】

38. 设单链表的表头指针为 h，结点结构由 data 和 next 两个域构成，其中 data 域为字符型。写出算法dc(h,n),判断该链表的前 n 个字符是否中心对称。 例如 xyx, xyyx 都是中心对称。

39. 已知两个单链表 A和 B,其头指针分别为 heada和 headb，编写一个过程从单链表 A 中删除自第 i 个元素起的共 len 个元素，然后将单链表 A 插入到单链表 B 的第 j 个元素之前。

40. 设线性表存于 A[1..size]的前 num 各分量中，且递增有序。请设计一个算法，将 x 插入到线性表的适当位置上，以保持线性表的有序性，并在设计前说明设计思想，最后说明所设计算法的时间复杂度。

41．. 假设一个单循环链表，其结点含有三个域 pre、data、link。其中 data 为数据域；pre 为指针域，它

的值为空指针（NIL）；link 为指针域，它指向后继结点。请设计算法，将此表改成双向循环链表。

42. 已知递增有序的单链表 A,B 分别存储了一个集合，请设计算法以求出两个集合 A 和B 的差集 A-B（即仅由在 A 中出现而不在 B 中出现的元素所构成的集合） ，并以同样的形式存储，同时返回该集合的元素个数。

43. 已知一个单链表中每个结点存放一个整数，并且结点数不少于 2，请设计算法以判断该链表中第二项起的每个元素值是否等于其序号的平方减去其前驱的值，若满足则返回 ture，否则返回false.

44．两个整数序列 A=a1,a2,a3,?,am和 B=b1,b2,b3,?,bn 已经存入两个单链表中，设计一个算法，判断序列 B 是否是序列 A 的子序列。

45．知L 为链表的头结点地址，表中共有 m(m>3)个结点，从表中第i 个结点(1

45. 设有一带头结点的单链表,编程将链表颠倒过来.要求不用另外的数组或结点完成.

46. 试编写求倒排循环链表元素的算法。 。 47. 请设计算法将不带头结点的单链表就地逆置。

48. 试编写算法 ，将不设表头结点的、不循环的单向链表就地逆转。

49．设有一个由正整数组成的无序（向后）单链表，编写完成下列功能的算法： （1）找出最小值结点，且打印该数值；

（2）若该数值是奇数，则将其与直接后继结点的数值交换； （3）若该数值是偶数，则将其直接后继结点删除。

50.．已知L为没有头结点的的单链表中第一个结点的指针，每个结点数据域存放一个字符，该字符可能是英文字母字符或数字字符或其它字符，编写算法构造三个以带头结点的单循环链表表示的线性表，使每个表中只含同一类字符。 （要求用最少的时间和最少的空间）

51．在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如： （7，10，10，21，30，42，42，42，51，70）将变作（7，10，21，30，42，51，70） 。 52.在输入数据无序的情况下，建立一个数据值为整型的递增有序的顺序存储线性表 L，且要求当输入相同数据值时，线性表中不能存在数据值相同的数据元素，试写出其算法。

53．设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在） ，试编写能实现下列功能的算法 ：

(1)确定在序列中比正整数 x 大的数有几个（相同的数只计算一次，如序列{20,20,17,16,15,15,11,10,8,7,7,5,4}中比10 大的数有5 个） ； (2) 在单链表将比正整数 x 小的数按递减次序排列； (3) 将正整数（比）x 大的偶数从单链表中删除。

54. 编写一个算法来交换单链表中指针 P 所指结点与其后继结点，HEAD 是该链

表的头指针，P 指向该链表中某一结点。

55．设键盘输入 n 个英语单词，输入格式为 n, w1, w2, ?,wn,其中n 表示随后输入英语单词个数，试编一程序，建立一个单向链表，实现： （1）如果单词重复出现，则只在链表上保留一个。 。

（2）除满足（1）的要求外。链表结点还应有一个计数域，记录该单词重复出现的次数，然后输出出现次数最多的前 k(k<=n)个单词。

56. 已知长度为 n 的线性表 A 采用顺序存储结构，请写一时间复杂度为 0(n)、空间复杂度为 0(1)的算法，

该算法删除线性表中所有值为 item 的数据元素。 （O（1）表示算法的辅助空间为常量） 。

57．给定(已生成)一个带表头结点的单链表，设 head 为头指针，结点的结构为(data,next),data 为整型元素，next 为指针，试写出算法:按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间。

58．已知三个带头结点的线性链表 A、B 和 C 中的结点均依元素值自小至大非递减排列（可能存在两个以上值相同的结点） ，编写算法对 A 表进行如下操作：使操作后的链表 A 中仅留下三个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为 O（m+n+p） ，其中 m、n和 p 分别为三个表的长度。

栈和队列（17）

1. 利用栈的基本操作， 写一个返回S中结点个数的算法 int StackSize( SeqStack S),并说明S为何不作为指针参数?

2. 设计算法判断一个算术表达式的圆括号是否正确配对。 (提示： 对表达式进行扫描，凡遇到'('就进栈，遇')'就退掉栈顶的'('，表达式被扫描完毕，栈应为空。

3.少用一个元素空间的方法来区别循环队列的队空和队满，试为其设计置空队，判队空，判队满、出队、入队及取队头元素等六个基本操作的算法。

4. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空 、入队和出队等算法。

5. 假设循环队列中只设rear和quelen 来分别指示队尾元素的位置和队中

元素的个数，试给出判别此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回S队头元素。

6.假设以数组Q[m]存放循环队列中的元素, 同时以rear和length分别指示环形队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件, 并写出相应的插入(enqueue)和删除(dlqueue)元素的操作。 7．假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag，以tag == 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。

8. 若使用循环链表来表示队列，p是链表中的一个指针。试基于此结构给出队列的插入(enqueue)和删除(dequeue)算法，并给出p为何值时队列空。 9. 若将一个双端队列顺序表示在一维数组V[m]中，两个端点设为end1和end2，并组织成一个循环队列。试写出双端队列所用指针end1和end2的初始化条件及队空与队满条件，并编写基于此结构的相应的插入(enqueue)新元素和删除(dlqueue)算法。

10. 设用链表表示一个双端队列，要求可在表的两端插入，但限制只能在表的一端删除。试编写基于此结构的队列的插入(enqueue)和删除(dequeue)算法，并给出队列空和队列满的条件。

11. 设有两个栈 S1,S2 都采用顺序栈方式，并且共享一个存储区[O..maxsize-1],为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计 S1,S2有关入栈和出栈的操作算法。

12. 设从键盘输入一整数的序列：a1, a2, a3，?，an,试编写算法实现：用栈结构存储输入的整数，当 ai≠-1 时，将ai进栈；当ai=-1 时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。

13. 设表达式以字符形式已存入数组 E[n]中， ‘#’为表达式的结束符，试写出判断表达式中括号（ ‘ （’和‘） ’ ）是否配对的 C 语言描述算法：EXYX(E); (注：算法中可调用栈操作的基本算法。)

14. 从键盘上输入一个逆波兰表达式，用伪码写出其求值程序。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔,操作符只

可能有+、-、*、/四种运算。例如：234 34+2*$

15. 假设以 I 和 O 分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由 I 和 O 组成的序列，称可以操作的序列为合法序列，否则称为非法序列。

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

A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO （2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回 true，否则返回 false（假定被判定的操作序列已存入一维数组中） 。 16.设计一个算法，判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的单循环链表中，每个结点有两个域：ch 和 link，其中 ch 域为字符类型。

17. 请利用两个栈 S1 和 S2 来模拟一个队列。已知栈的三个运算定义如下：PUSH(ST,x):元素 x 入 ST 栈；POP(ST,x)：ST 栈顶元素出栈，赋给变量 x；Sempty(ST)：判 ST 栈是否为空。那么如何利用栈的运算来实现该队列的三个运算：enqueue:插入一个元素入队列； dequeue:删除一个元素出队列；queue_empty：判队列为空。 （请写明算法的思想及必要的注释）