答:在队列的顺序存储结构中，设头指针为front，队尾指针rear，队的容量(存储空间的大小)为MaxSize。当有元素加入到队列时，若rear=MaxSize（初始时rear=0）则发生队列的上溢现象，该元素不能加入队列。特别要注意的是队列的假溢出现象：队列中还有剩余空间但元素却不能进入队列，造成这种现象的原因是由于队列的操作方法所致。 解决队列上溢的方法有以下几种： （1） （2） 【1】 【2】 位置； 【3】

采用循环队列方式：把队列看成一个首尾相接的循环队列，在循环队列上进行插入或删除运

算时仍然遵循“先进先出”的原则。

5.利用两个栈S1、S2模拟一个队列时，如何用栈的运算实现队列的入队、出队以及队列的判空运算？请简述算法思想。

答：利用两个栈S1和S2模拟一个队列的基本思想是：用一个栈S1作为输入栈，另一个栈S2作为输出栈。入队时，总是将元素输入S1,出队时，若输出栈S2已空，则将S1中元素全部输入到S2中，然后由S2输出元素。若输出栈S2不空，则直接由S2输出元素。显然，只有输入栈、输出栈均为空时队列才为空。 6.设输入元素为1，2，3，P和A，输入次序为123PA，元素经过栈后到达输出序列，当所有元素到达输出序列后，有哪些序列可作为高级语言的变量名（以字母开头的字母数字串）。 答：AP321，PA321,P3A21,P32A1,P321A。 3.4.5

算法设计题

1. 用一个一维数组S（设大小为MAX）作为两个栈的共享空间。请说明共享方法，栈满、栈空的判断条件，并用C/C++语言设计公用的初始化栈运算InitStack(st)、入栈运算Push(st，i，x)和出栈运算Pop(st,i,x)和出栈运算Pop(st,i,x)，其中i为0或1，用于表示栈号，x为入栈元素。

解：设用一维数组S[MaxSize]作为两个栈的共享空间，整型变量top1、top2分别作为两个栈的栈顶指针，并约定栈顶指针指示当前元素的下一个位置。S1的栈底位置设在S[0]，S2的栈底位置设在S[MaxSize-1]，栈S1空的条件是top1==-1，栈S1满的条件是top1==top2-1，栈S2空的条件是top2==MaxSize，栈S2满的条件是top1==top2-1，栈S2空的条件是top2==MaxSize，栈S2满的条件是top2==top1+1。归纳起来，栈S1和S2满的条件都是top1==top2-1。 对应的算法如下：

#define Maxsize 100 5.4补充练习题及参考答案 5．4.1 单项选择题

1.数组A[0..5,0..6]的每个元素占5个单元，将其按列优先次序存储在起始地址为1000的连续内存单元中，则元素a[5][6]的地址为__________。 A.1175 B.1180 C.1205 D.1210

答：a[5][6]的地址=1000+（5*6+5）*5=1175.所以本题答案是A.

2.一个n*n的对称矩阵，如果以行或列为主序放入内存，则容量为_____________。 A.n B.n/2 C.n (n+1)/2 D.(n+1)/2

答：对称矩阵只需存储上（下）三角形（含主对角线）元素，以存放下三角形（含主对角线）元素为例，第1行1个元素，第2行2个元素，?，第n行n个元素，共有1+2+?+n=n(n+1)/2个元素。本题答案C. 3.对矩阵压缩存储是为了___________。

A.方便运算 B.节省空间 C.方便存储 D.提高运算速度 答：B 4.与三元组顺序表相比，稀疏矩阵用十字链表表示，其优点在于____________。

9

2

2

2

建立一个足够大的存储空间，但这样做会造成空间的使用效率降低。 当出现假溢出时可采用以下几种方法：

采用平移元素的方法：每当队列中加入一个元素时，队列中已有的元素向队头移动一个位置每当删除一个队头元素时，则依次移动队中的元素，始终使front指针指向队列中的第一个

（当然要有空闲的空间可供移动）；

A.便于实现增加或减少矩阵中非零元素的操作 B.便于实现增加或减少矩阵元素的操作 C.可以节省存储空间

D.可以更快地查找到某个非0元素 答：A 5.对稀疏矩阵采用压缩存储，其缺点之一是____________。 A.无法判断矩阵有多少行多少列 B.无法根据行列号查找某个矩阵元素 C.无法根据行列号计算矩阵元素的存储地址

D. 使矩阵元素之间的逻辑关系更加复杂 答：C 5.4.2 填空题

1.一维数组的逻辑结构是____①____，存储结构是_____②_____；对于二维或多维数组，分为按____③____和____④____两种不同的存储方式答①线性结构 ②顺序结构 ③按行优先顺序 ④按列优先顺序。 2.数组A[1..10，-2..6，2..8]以行优先顺序存储，设第一个元素的首地址为100，每个元素占3个单元的存储空间，则元素A[5][0][7]的存储地址为_________。

答：LOC(A[5][0][7])=100+[(5-1)*(6-(-2)+1)*(8-2+1)+(0-(-2))*(8-2+1)+(7-2)]*3=913

3.三位数组R[c1..d1,c2..d2,c3..d3]共含有__________个元素。答：（d1-c1+1）*（d2-c1+1）*（d3-c3+1） 5.4.3 判断题判断以下叙述的正确性。 （1） （2） （3） （4） （5） （6）

用一位数组表示矩阵，可以简化对矩阵的存取操作。 对角矩阵的特点是非零元素只出现在矩阵的两条对角线上。 在n阶三对角矩阵中，每一行都有n个元素。 稀疏矩阵的特点是矩阵中元素较少。

在表示稀疏矩阵的三元组顺序表中，各元素的排列顺序与矩阵元素值的大小有关。 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对

该矩阵的转置运算。答：（1）错误。（2）错误。（3）正确。（4）错误。（5）错误。 （6）错误。因为三元组是以行序存储的，这种下标互换方法没有考虑行序。 5.4.4 简答题

1.数组A[1..3,0..1,1..2]有多少个元素？

答：该数组时一个三维数组，各维的大小分别为3、2和2，所以元素个数=3*2*2=12个。

2. 二维数组A[4][4](即A[0..3][0..3])的元素起始地址是loc(A[0][0])=1000,元素的长度为2，则loc(A[2][2])为多少？

答：loc(A[2][2])=loc(A[0][0])+[(2-0)*(3-0+1)+(2-0)]*2=1020。

3.对于给定的数组a[n][2*n-1]，现将3个顶点分别为a[0][n-1]、a[n-1][0]和a[n-1][2*n-2]的三角形上的所有元素按行序依次存放在一维数组b[n*n]中。例如，当n=3时，数组a[3][5]中用线连成的三角形如图5.3所示。

a00

a01 a02 a03 a04

a10 a11 a12 a13 a14

a20 — a21 — a22 — a23 — a24 图5.3 矩阵元素连成的三角形

若把三角形上的所有元素按行序依次存放在一维数组b[3*3]上，则有： i 0 1 2 3 4 5 6 7 8 b[i] a02 a11 a12 a13 a20 a21 a22 a23 a24

10

如果位于三角形上的元素a[i][j]存放于b[k]中，那么试给出求得下标值k的计算公式k=f(n,i,j)。对于上例中的a[2][1]，根据计算公式可求得k=5。

答：在三角形中，行号i中元素个数为2i+1，因此，该三角形中0~i -1行的所有元素个数之和=1+3+?+2i - 1=（1+2i-1）*i/2 =i。

设第i行在三角形中的第1个元素的列号为m，则有： i=0,m=2 i=1,m=1 i=2,m=0 ??

归纳起来有：i+m=n/2，即m=n/2 – i，这样： k =i – (n/2 – i)+j

所以，f(n,i,j)=i – (n/2 – i)+j

对于本题图，n=4,i=2,j=1时，k=2*2 – (4/2 – 2)+1=5。

4．特殊矩阵和稀疏矩阵哪一种压缩存储后会失去随机存取的功能？为什么？

答：稀疏矩阵压缩存储后失去了随机存取功能，因为压缩存储采用的三元组（i,j,aij）不是连续的，也就是说，i、j与该三元组在三元组表中的地址没有线性关系，而特殊矩阵在压缩存储后都有这种关系。 5．4．5算法设计题

1.当三对角矩阵采用压缩存储时，写一算法求三对角矩阵在这种压缩存储表示下的转置矩阵。

2

2

2

10.4 补充练习题及参考答案

10.4.1 单项选择题

1.在二叉排序树中，凡是新插入的结点，都是没有 的。 A A.孩子 B.关键字 C.平衡因子 D.赋值

2.只有在顺序存储结构上才能实现的查找方法是 法。 B A. 顺序查找 B. 二分查找 C.树型查找 D. 哈希查找

3.在数据元素有序，元素个数较多而且固定不变的情况下，宜采用 法。 A A.二分查找 B.分块查找 C.二叉排序树查找 D.顺序查找

4.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下，查找成功所需的平均次数为 。 B

A.35/12 B.37/12 C.39/12 D.43/12

5.有一个有序表R[1?13]={1，3，9，12，32，41，45，62，75，77，82，95，100}，当用二分查找法查找值为82的结点时，经 次比较后查找成功。 C A.1 B.2 C.4 D.8

6.如图10.4(a)所示的一棵二叉排序树，其不成功的平均查找长度是 。 A A.21/7 B.28/7 C.15/6 D.21/6

7.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定节点所在的块，则每块分为 个结点最佳。 B A.9 B.25 C.6 D.625 8.具有5层结点的AVL树至少有 个结点。 B A.10 B.12 C.15 D.17

9.下面关于B-树和B+树的叙述中，不正确的结论是 。 A

A. B-树和B+树都能有效地支持顺序查找 B. B-树和B+树都能有效地支持随机查找

11

C. B-树和B+树都是平衡的多分树 D. B-树和B+树都可用于文件索引结构 10.设有n个关键字，散列查找法的平均查找长度是 。 A A.O(1) B.O(n) C.O(lbn) D.O(n)

11.设哈希表的长m=14，哈希函数H(key)=key mod 11。表中已有4个结点addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，其余地址为空。如用二次探测再散列法处理冲突，则关键字为49的结点的地址是 。 D

A.8 B.3 C.5 D.9 12.散列表的平均查找长度 。 A

A.与处理冲突方法有关而与表的长度无关 B.与处理冲突方法无关而与表的长度有关 C.与处理冲突方法有关而与表的长度有关 D.与处理冲突方法无关而与表的长度无关 10.4.2 填空题

1.衡量查找算法性能好坏的主要标准是 。 答：关键字的比较次数 2.为了实现分块查找，线性表必须采用 方法存储。 答：索引

3.对二叉排序树进行 遍历，可以得到按关键字从小到大排列的结点序列。 答：中序 4.在高度为h含n个结点的二叉排序树上查找一个关键字至多比较次数为 。 答：h

5.在一个10阶的B-树上，每个树根结点中所含的关键字的数目最多允许为 ① 个，最少允许为 ② 个。 答：m=10，[m/2]≤j≤m-1，即4≤j≤9，本题答案为：① 9 ② 4

6.当向B-树中插入关键字时，可能引起节点的 ① ，最终可能导致整个B-树的高度 ② ，当从B-树中删除关键字时，可能引起节点 ③ ，最终可能导致整个B-树的高度 ④ 。 答：① 分裂 ② 增加1 ③ 合并 ④减少1

7.采用哈希存储方法时，用于计算节点存储地址是 。 答：哈希函数 8.评价哈希函数好坏的标准是 。 答：哈希函数取值是否均匀

9.在各种查找方法中，其平均查找长度与节点个数n无关的查找方法是 。 答：哈希表查找法 10.在散列存储中，装填因子α的值越大，则 ① ；α的值越小，则 ② 。

答：由散列查找法可知本题答案为：① 存取元素时发生冲突的可能性就越大 ②存取元素时发生冲突的可能性就越小 10.4.3 判断

1.判断以下叙述的正确性。

⑴顺序查找方法只能在顺序存储结构上进行。 ⑵二分查找可以在有序的双向链表上进行。 ⑶分块查找的效率与线性表被分成多少块有关。 ⑷二叉排序树是用来进行排序的。

⑸在二叉排序树中，每个结点的关键字都比左孩子的关键字大，比右孩子的关键字小。

⑹每个结点的关键字都比左孩子的关键字大，比右孩子的关键字小，这样的二叉树都是二叉排序树。 ⑺在二叉排序树中，新插入的关键字总是处于最底层。 ⑻在二叉排序树中，新结点总是作为树叶来插入的。 ⑼二叉排序树的查找效率和二叉排序树的高度有关。 ⑽在平衡二叉排序树中，每个结点的平衡因子值是相等的。 ⑾在平衡二叉排序树中，以每个分支结点为根的子树都是平衡的。 ⑿哈希存储法只能存储数据元素的值，不能存储数据元素之间的关系。 ⒀哈希冲突是指同一个关键字对应多个不同的哈希地址。

⒁哈希查找的过程中，关键字的比较次数和哈希表中关键字的个数直接相关。

⒂在用线性探测法处理冲突的哈希表中，哈希函数值相同的关键字总是存放在一片连续的存储单元中。 答：⑴错误。顺序查找方法也可以在顺序存储结构上进行。

12

2