清华大学出版社数据结构(C++版)(第2版)课后习题答案最全整理

⑻ 判断带头结点的双循环链表是否对称。

【解答】设工作指针p和q分别指向循环双链表的开始结点和终端结点，若结点p和结点q的数据域相等，则工作指针p后移，工作指针q前移，直到指针p和指针q指向同一结点（循环双链表中结点个数为奇数），或结点q成为结点p的前驱（循环双链表中结点个数为偶数）。如图2-12所示。

学习自测及答案

1. 已知一维数组A采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144，则第一个元素的地址是（ ）。 A 108 B 180 C 176 D 112 【解答】D

2．在长度为n的线性表中查找值为x的数据元素的时间复杂度为： （ ）。 A O(0) B O(1) C O(n) D O(n2) 【解答】C

3．在一个长度为n的顺序表的第（i1≤i≤n+1）个元素之前插入一个元素，需向后移动（ ）个元素，删除第i（1≤i≤n）个元素时，需向前移动（ ）个元素。

【解答】n-i+1，n-i

4．在单链表中，除了头结点以外，任一结点的存储位置由（ ）指示。 【解答】其前趋结点的指针域

5．当线性表采用顺序存储结构时，其主要特点是（ ）。 【解答】逻辑结构中相邻的结点在存储结构中仍相邻

6．在双链表中，每个结点设置了两个指针域，其中一个指向（ ）结点，另一个指向（ ）结点。 【解答】前驱，后继

7．设A是一个线性表（a1, a2, …, an），采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为多少？若元素插在ai与ai+1之间（1≤i≤n）的概率为数又是多少？ 【解答】

，则平均每插入一个元素所要移动的元素个

， 。

8．线性表存放在整型数组A[arrsize]的前elenum 个单元中，且递增有序。编写算法，将元素x插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。

【解答】本题是在一个递增有序表中插入元素x，基本思路是从有序表的尾部开

始依次取元素与x比较，若大于x，此元素后移一位，再取它前面一个元素重复上述步骤；否则，找到插入位置，将x插入。具体算法如下：

9. 已知单链表中各结点的元素值为整型且递增有序，设计算法删除链表中所有大于mink且小于maxk的所有元素，并释放被删结点的存储空间。 【解答】因为是在有序单链表上的操作，所以，要充分利用其有序性。在单链表中查找第一个大于mink的结点和第一个小于maxk的结点，再将二者间的所有结点删除。

10．设单循环链表L1，对其遍历的结果是：x1, x2, x3,…, xn-1, xn。请将该循环链表拆成两个单循环链表L1和L2，使得L1中含有原L1表中序号为奇数的结点且遍历结果为：x1, x3,… ；L2中含有原L1表中序号为偶数的结点且遍历结果为：… , x4, x2。 【解答】算法如下：

第 3 章 特殊线性表——栈、队列和串 课后习题讲解 1. 填空

⑴ 设有一个空栈，栈顶指针为1000H，现有输入序列为1、2、3、4、5， 经过push，push，pop，push，pop，push，push后，输出序列是（ ），栈顶指针为（ ）。 【解答】23，1003H

⑵ 栈通常采用的两种存储结构是（ ）；其判定栈空的条件分别是（ ），判定栈满的条件分别是（ ）。

【解答】顺序存储结构和链接存储结构（或顺序栈和链栈），栈顶指针top= -1和top=NULL，栈顶指针top等于数组的长度和内存无可用空间

⑶（ ）可作为实现递归函数调用的一种数据结构。 【解答】栈

【分析】递归函数的调用和返回正好符合后进先出性。

⑷ 表达式a*(b+c)-d的后缀表达式是（ ）。 【解答】abc+*d-

【分析】将中缀表达式变为后缀表达式有一个技巧：将操作数依次写下来，再将算符插在它的两个操作数的后面。

⑸ 栈和队列是两种特殊的线性表，栈的操作特性是（ ），队列的操作特性是（ ），栈和队列的主要区别在于（ ）。

【解答】后进先出，先进先出，对插入和删除操作限定的位置不同 ⑹ 循环队列的引入是为了克服（ ）。 【解答】假溢出