下载掌阅APP，畅读海量书库
立即打开
设下三角矩阵（上三角部分的元素值都为0） A [0．． n ，0．． n ]如图1-35所示，将该三角矩阵的所有非零元素（即行下标不小于列下标的元素）按行优先压缩存储在容量足够大的数组 M []中（下标从1开始），则元素 A [ i , j ]( O ≤ i ≤ n ， j ≤ i )存储在数组 M 的 （57） 中。
图1-35 状态转换图
例题分析：
本题考查数据结构基础知识。
如题图所示，按行方式压缩存储时，
A
[
i
,
j
]之前的元素数目为（1+2+…+
i
+
j
）个，因为第
i
行前面的每行的元素个数分别为1,2,3,…,
i
。数组
M
的下标从1开始，因此
A
[
i
,
j
]的值存储在
中。
例题答案： A
对 n 个元素的有序表A[1．． n ]进行顺序查找，其成功查找的平均查找长度（即在查找表中找到指定关键码的元素时，所进行比较的表中元素个数的期望值）为 （58） 。
（58）A．n B．(n+1)/2 C．log2n D．n2
例题分析：
本题主要考查顺序查找。
对于 n 个数据元素的表，若给定值key与表中第 i 个元素的关键字相等，则需进行 n - i +1次关键字比较，即 Ci = n - i +1。例如，当第 n 个元素的关键字为key时，需要比较1次( n - n +1=1)，又如，当第1个元素为所求结果时，需要比较 n 次( n -1+1= n )。因此，查找成功时，顺序查找的平均查找长度为：
其中Pi为每个元素的查找概率，假设所有元素的查找概率均相等，即
，则在等概率情况下有：
例题答案：B
在 （59） 中，任意一个结点的左、右子树的高度之差的绝对值不超过1。
（59）A．完全二叉树 B．二叉排序树
C．线索二叉树 D．最优二叉树
例题分析：
本题主要考查一些特殊二叉树的性质。
若二叉树中最多只有最下面两层的结点度数可以小于2，并且最下面一层的叶子结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树，因此在完全二叉树中，任意一个结点的左、右子树的高度之差的绝对值不超过1。
二叉排序树的递归定义如下：二叉排序树或者是一棵空树；或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于根结点的值；
（3）左右子树也都是二叉排序树。
在n个结点的二叉树链式存储中存在n+1个空指针，造成了巨大的空间浪费，为了充分利用存储资源，可以将这些空链域存放指向结点在遍历过程中的直接前驱或直接后继的指针，这种空链域就称为线索，含有线索的二叉树就是线索二叉树。
最优二叉树即哈夫曼树。
例题答案： A
设一个包含 N 个顶点、 E 条边的简单无向图采用邻接矩阵存储结构（矩阵元素 A [ i ][ j] 等于1/0分别表示顶点 i 与顶点 j 之间有/无边），则该矩阵中的非零元素数目为 （60） 。
（60）A．N B．E C．2E D．N+E
例题分析：
本题主要考查图的邻接矩阵存储结构。
设 G =( V ， E )是具有 n 个顶点的图，其中 V 是顶点的集合， E 是边的集合，那么邻接矩阵中的每个元素的定义如下：
从这个定义我们可以知道，一条边在矩阵中有两个1表示，比如顶点1和顶点2之间有一条边，那么矩阵元素 A [1,2]和 A [2,1]的值都是1。
在本题中，题目告诉我们有 E 条边，那么其邻接矩阵中的非零元素数目应该为2 E 。
例题答案： C
对于关键字序列(26，25，72，38，8，18，59)，采用散列函数H(Key)=Key mod 13构造散列表（哈希表）。若采用线性探测的开放定址法解决冲突（顺序地探查可用存储单元），则关键字59所在散列表中的地址为 （61） 。
（61）A．6 B．7 C．8 D．9
例题分析：
根据题目给出的散列函数我们可以分别计算出关键字(26，25，72，38，8，18，59)对应的散列地址分别为(0，12，7，12，8，5，7)。
开放定址处理冲突的基本思路是为发生冲突的关键字在散列表中寻找另一个尚未占用的位置，其解决冲突能力的关键取决于探测序列，在本题中，题目告诉我们采用顺序探查法，即增量为1的线性探测法，在该线性探测法中，设Hi (1≤i＜m)为第i次在散列表中探测的位置，其中增量序列为{1，2，3，4，5，…，m-1}则有：
H i = (H (Key)+ i )% m
其中H (Key)为散列函数，m为散列表长度，i为增量序列。而本题中m=13。因此本题的散列表构造过程如下：
（1）关键字26，25，72由散列函数H (key)得到没有冲突的散列地址而直接存入散列表中。
（2）计算关键38的散列地址为12，发生冲突（与关键字25冲突），其第一次线性探测地址为（12+1）%13=0，但仍然发生冲突（与关键字26冲突），因此需要进行第二次线性探测，其地址为（12+2）%13=1，这时没有发生冲突，即将38存入地址为1的空间。
（3）接着将关键字8，18计算其散列地址，由于没有冲突，即分别存入散列地址为8和5的空间中。
（4）计算关键59的散列地址为7，发生冲突（与关键字72冲突），其第一次线性探测地址（7+1）%13=8，但仍然发生冲突（与关键字8冲突），因此需要进行第二次线性探测，其地址为（7+2）%13=9，这时没有发生冲突，即将59存入地址为9的存储空间。
因此本题的答案选D。
例题答案： D
用插入排序和归并排序算法对数组＜3，1，4，1，5，9，6，5＞进行从小到大排序，则分别需要进行 （65） 次数组元素之间的比较。
（65）A．12，14 B．10，14 C．12，16 D．10，16
例题分析：
插入排序的基本思想是逐个将待排序元素插入到已排序的有序表中。假设n个待排序元素存储在数组R[n+1]中(R[0]预留），则：
（1）初始时数组 R [1..1]中只包含元素 R [1]，则数组 R [1..1]必定有序；
（2）从 i =2到 n ，执行步骤3；
（3）此时，数组 R 被划分成两个子区间，分别是有序区间 R [1.. i -1]和无序区间 R [i.. n ]，将当前无序区间的第1个记录R[i]插入到有序区间R[1.. i ]中适当的位置上，使R[1.. i ]变为新的有序区间。
在实现的过程中，设置监视哨 R [0]，并从 R [ i -1]到 R [0]查找元素 R [ i ]的插入位置
那么用插入排序对数组＜3，1，4，1，5，9，6，5＞进行排序的过程为：
原元素序列： 监视哨 （3），1，4，1，5，9，6，5
第一趟排序： 3 （1，3），4，1，5，9，6，5 3插入时与1比较1次
第二趟排序： 4 （1，3，4），1，5，9，6，5 4插入时与3比较1次
第三趟排序： 1 （1，1，3，4），5，9，6，5 1插入时比较3次
第四趟排序： 5 （1，1，3，4，5），9，6，5 5插入时与4比较1次
第五趟排序： 9 （1，1，3，4，5，9），6，5 9插入时与5比较1次
第六趟排序： 6 （1，1，3，4，5，6，9），5 6插入时与9和5分别比较1次
第七趟排序： 5 （1，1，3，4，5，5，6， 9） 5插入时与9,6,5分别比较1次
那么整个排序过程需要比较的次数为12次。
归并排序的思想是将两个相邻的有序子序列归并为一个有序序列，然后再将新产生的相邻序列进行归并，当只剩下一个有序序列时算法结束。其基本步骤如下：
（1）将
n
个元素的待排序序列中每个元素看成有序子序列，对相邻子序列两两合并，则将生成
个子有序序列，这些子序列中除了最后一个子序列长度可能小于2外，其他的序列长度都等于2；
（2）对上述
个长度为2的子序列再进行相邻子序列的两两合并，则产生
个子有序序列，同理，只有最后一个子序列的长度可能小于4；
（3）第i趟归并排序为，对上述
个长度为
i
的子序列两两合并，产生
个长度为2
i
的子有序序列；
（4）重复执行此步骤，直到生成长度为 n 的序列为止。
那么用归并排序对数组＜3，1，4，1，5，9，6，5＞进行排序的过程为：
原元素序列： 3，1，4，1，5，9，6，5
第一趟排序： [1，3]，[1，4]，[5，9]，[5，6]比较4次
第二趟排序： [1，1，3，4]， [5，5，6，9]前半部分比较3次，后半部分比较3次
第三趟排序： [1，1，3，4，5，5，6，9] 5分别与1,1,3,4比较一次
所以整个排序过程需要比较的次数为12次。
例题答案： D
算术表达式采用逆波兰式表示时不用括号，可以利用 （20） 进行求值。与逆波兰式ab-cd+*对应的中缀表达式是 （21） 。
（20）A．数组 B．栈 C．队列 D．散列表
（21）A．a-b+c*d B．(a-b)*c+d C．(a-b)*(c+d) D．a-b*c+d
例题分析：
逆波兰式也叫后缀表达式，即将运算符写在操作数之后的表达式，它不需使用括号，在将算术表达式转换为逆波兰式表示时，需要分配2个栈，一个作为临时存储运算符的栈 S 1（含一个结束符号），一个作为输入逆波兰式的栈 S 2（空栈）。
而逆波兰式 ab - cd +*转换为中缀表达式的过程为： ab - cd +* = ( ab -)*( cd +) = ( a - b )*( cd +) = ( a - b )*( c + d )。因此本题答案选C。
例题答案 ：（20）B（21）C