1.7 本章例题分析

例题1（2011年5月试题36）

若二维数组arr[1..8，1..6]的首地址为base，数组元素按列存储，且每个元素占用4个存储单元，则元素arr[5,5]在该数组空间的地址为 （36） 。

（36）

A．base+(4*8+4)*4

B．base+(5*8+5)*4

C．base+(4*6+4)*4

D．base+(5*6+5)*4

例题分析

在本题中，题目告诉我们二维数组arr是一个8行6列的数组，那么每一列有8个元素，而按列存储的意思就是先将第一列的元素全部存放完后，再开始存放第二列的元素，依次类推。

另外从题目给出的二维数组arr[1..8，1..6]我们可以看出，下标是从1开始的，因此元素arr[5,5]描述的是第5行第5列的元素，那么在存储该元素前，应该先存储完前4列的所有元素，并且第5列的前4个元素也都已经存放完毕，所有元素arr[5,5]在该数组空间的地址为base+(4*8+4)*4。

例题答案：

（36）A

例题2（2011年5月试题37）

设线性表(59，53，46，48，37，31，25)采用散列（Hash）法进行存储和查找，散列函数为H(Key)=KeyMOD 7（MOD表示整除取余运算）。若用链地址法解决冲突（即将相互冲突的元素存储在同一个单链表中）构造散列表，则散列表中与哈希地址 （37） 对应的单链表最长。

（37）

A．2

B．3

C．4

D．6

例题分析

根据题目给出的散列函数我们可以分别计算出关键字(59，53，46，48，37，31，25)对应的散列地址分别为(3，4，4，6，2，3，4)。

在链地址方法中，散列表地址域的每个元素都是一个指针，指向一个单链表，这个单链表存储所有该散列地址上的同义词，比如本题中的59和31就是同义词，因为它们的散列地址都是3。那么很显然，对应散列地址为4的元素有3个，而对应其他散列地址的元素个数都小于3，因此最长的单链表对应散列地址4。所以本题答案选C。

例题答案：

（37）C

例题3（2011年5月试题38）

设递增序列A为a ₁ ，a ₂ ，…，a _n ，递增序列B为b ₁ ，b ₂ ，…，b _m ，且m＞n，则将这两个序列合并为一个长度为m+n的递增序列时，当 （38） 时，归并过程中元素的比较次数最少。

（38）

A．a _n ＞b _m

B．a _n ＜b ₁

C．a ₁ ＞b ₁

D．a ₁ ＜b _m

例题分析

题目告诉我们两个序列都是递增序列，那么如果一个序列的最小值大于另一个序列的最大值时，归并过程的比较次数最少，所以本题答案选B。

例题答案：

（38）B

例题4（2011年5月试题39）

已知某带权有向图G（顶点数为6，顶点编号为1至6）的邻接表如下所示，其中表结点的结构为：

则图G中含有的弧数为 （36） 。

（39）

A．9

B．11

C．15

D．18

例题分析

根据题目给出的表结点的结构我们可以知道，其中各结点中最左边的是邻接顶点编号，而最中间是边上的权值，右边是指向下一个邻接顶点的指针。根据题目给出的邻接表，我们可以得到如图1-22所示的有向图，所以图G中含有9条弧。

例题答案：

（39）A

例题5（2011年5月试题40）

当二叉树的结构形如 （40） 时，其后序遍历序列和中序遍历序列相同。

（40）A．B．C．D．

例题分析

本题主要考查二叉树的遍历。

中序遍历的思想是：如果二叉树为空，则直接返回。否则，首先按中序遍历根结点的左子树，然后访问根结点，最后再按中序遍历根结点的右子树。

后序遍历的思想是：如果二叉树为空，则直接返回。否则，首先按后序遍历根结点的左子树，然后按后序遍历根结点的右子树，最后再访问根结点。

对于选项A的中序遍历，首先应该遍历根结点的左子树，因此其中序遍历序列为从下至上，而其后续遍历也同样先遍历根结点的左子树，因此其后序遍历序列也为从下至上。

例题答案：

（40）A

例题6（2011年5月试题41）

对长度为n的有序表进行二分（折半）查找时，无论查找指定的一个元素是否成功，最多只与表中的 （41） 个元素进行比较即可。

（41）

A．

B．

C．n/2

D．n－1

例题分析

二分（折半）查找的基本思想为：在有序表中，先确定待查元素所在的区域，再逐步缩小这个区域，直到在区域中找到该元素（查找成功）或者区域缩小为0也没有找到该元素（查找失败）为止。通常采用如下递归步骤：

（1）将区域分为左、中、右三个部分，其中区域中间的元素单独处于中间区域，该元素左、右两边的元素分别属于左、右区域，则左、右区域所包含的元素相等（或相差1个），数量为原区域元素的一半；

（2）比较给定关键字与中央区域元素的关键字，如果相等则查找成功，该元素即为所求；

（3）如果给定关键字较大，那么待查元素只可能出现在中间元素右边，则继续对右区域执行步骤1～4；

（4）否则给定关键字较小，则待查元素只可能出现在中间元素左边，继续查找左区域即可。

在二分（折半）查找时，无论查找成功与否，最多只与表中的 个元素进行比较，例如，对含有12个元素的有序表｛1，4，10，16，17，18，23，29，33，40，50，51｝进行折半查找，如果要查找17，那么首先应该与第6个元素比较，由于17小于18，那么应该在前半部分查找，那么接着应该与第3个元素比较，由于大于10，那么应该接着与16比较，最后与17比较，然后查找成功，一共比较了4次。如果要查找19，那么首先应该与第6个元素比较，由于19大于18，那么应该在后半部分查找，那么接着应该与第9个元素比较，由于大于33，那么应该接着与29比较，最后与23比较，然后查找失败，一共也比较了4次，即 。

例题答案：

（41）B

例题7（2011年5月试题42）

输入受限的双端队列是指只有一端可以进行入队操作而从两端都可以进行出队操作的队列，如图1-23所示。对于输入序列1 2 3 4，经过一个初始为空且输入受限的双端队列后，不能得到的输出序列为 （42） 。

（42）

A．1 2 3 4

B．4 3 2 1

C．1 2 4 3

D．4 2 1 3

例题分析

本题给出的是一个特殊的队列，即只有一端可以进行入队操作而从两端都可以进行出队操作的队列。下面我们分别来分析各选项的情况。

对于选项A，各元素依次入队后，然后在另一端依次出队，即可得到选项A的序列。对于选项B，等元素全部入队以后，然后在入队端进行出队操作，即可得到选项B的出队序列。对于选项C，各元素依次入队后，元素1和2在左端进行出队，然后是4元素在右端进行出队，最后是3元素出队，即可得到选项C的出队序列。而选项D无论采用哪种出队策略，都不能实现。

例题答案：

（42）D

例题8（2011年5月试题43）

对于具有n个元素的关键字序列{K1，K2，…，Kn}，当且仅当满足关系 且 时称为大根堆。据此可以断定 （43） 不是大根堆。

（43）

A．59, 53, 48, 46, 37, 31, 25

B．59, 46, 53, 48, 37, 31, 25

C．59, 37, 53, 25, 31, 46, 48

D．59, 53, 48, 31, 25, 46, 37

例题分析

本题主要考查大根堆的相关内容。题目告诉我们大根堆必须满足的关系，我们可以知道选项B不是大根堆，因为其第4个元素48大于第2个元素46，所以不是大根堆。

例题答案：

（43）B

例题9（2011年5月下午试题3）

阅读以下说明和C函数，回答问题l和问题2，将解答填入答题纸的对应栏内。

【说明】

对于具有n个元素的整型数组a，需要进行的处理是删除a中所有的值为0的数组元素，并将a中所有的非O元素按照原顺序连续地存储在数组空间的前端。下面分别用函数CompactArr_v1和CompactArr v2来实现上述处理要求，函数的返回值为非零元素的个数。

函数CompactArr_vl(int a[]，int n)的处理思路是：先申请一个与数组a的大小相同的动态数组空间，然后顺序扫描数组a的每一个元素，将遇到的非0元素依次复制到动态数组空间中，最后再将动态数组中的元素传回数组a中。

函数CompactArr_v2(int a[]，int n)的处理思路是：利用下标i（初值为0）顺序扫描数组a的每一个元素，下标k（初值为0）表示数组a中连续存储的非0元素的下标。扫描时，每遇到一个数组元素，i就增1，而遇到非0元素并将其前移后k才增1。

【问题1】

请根据说明中函数CompactArr_v1的处理思路填补空缺（1）～（3），根据CompactArr_v2的处理思路填补空缺（4）。

【问题2】

请说明函数CompactArr_vl存在的缺点。

例题分析

本题是一个对数组进行操作的问题。题目要求删除数组a中所有的值为0的数组元素，并将a中所有的非0元素按照原顺序连续地存储在数组空间的前端。并且在题目中给出了两个实现函数分别为函数CompactArr_v1和CompactArr_v2。

根据题目说明，我们可知本题的逻辑关系并不复杂，只要找到数组中值不为0的元素，然后按原来的顺序连续存储即可，这里可以借助其他的存储空间来完成，也可以不借助其他的存储空间来完成。下面我们就来具体分析CompactArr_v1和CompactArr_v2。

前面三空都在函数CompactArr_v1中，在函数CompactArr_v1的开始处定义了一个指针变量temp，并使其指向一块动态分配的存储空间，而空（1）就在该动态分配存储空间的语句中，根据函数malloc的格式我们可以知道函数malloc后面括号中要给出分配空间的大小，结合整个函数CompactArr_v1来看，这里动态分配的存储空间是用来临时存放数组中非0元素的，因此其空间大小应该为n乘以一个整型变量所占的空间，而这可以通过函数sizeof求得，因此空（1）处应填sizeof(int)。

空（2）在函数的第一个for循环结构中，从题目意思及结合程序不难看出，该for循环的作用是变量整个数组，并找出数组中值不为0的元素，而空（2）所在的赋值语句是在数组当前元素的值不等于0的情况下执行的语句，并且是将数组的当前元素赋值给空（2），很显然，这里是将非0元素存放到动态分配的存储空间中，因此本空应填temp[k++]。k是temp数组的下标。

空（3）是第二个for循环的结束条件，根据题目意思和程序不难看出该循环的作用是将存放在临时空间的非0 元素依次存放至数组a中，因此循环结束的条件是循环变量i小于非0元素的个数，从上一个循环中可以看出变量k的值就是非0元素的个数值。因此本空应填i＜k。

第（4）空在函数CompactArr_v2中，根据题目意思，函数CompactArr_v2没有借助其他的存储空间来完成删除数组0元素的任务，这里采用覆盖前面元素的方式来实行。再看程序，空4所在的赋值语句是在数组当前元素的值不等于0的情况下执行的语句，并且是将数组的当前元素赋值给空（4），因此本空应填a[k++]，当然填*（a+k++）也是一样的。

本题的函数CompactArr_vl在完成题目要求的功能时，利用了其他的辅助存储空间，很显然，其空间和时间效率都比函数CompactArr_v2要低，而且在动态申请存储空间时，有可能会失败，从而导致函数功能无法实现。

例题答案：

【问题1】

（1）sizeof(int)

（2）temp[k++] 或 *(temp+k++)或等价表示

（3）i＜k 或等价表示

（4）a[k++] 或 *（a+k++）或 等价表示

【问题2】

可能由于动态内存申请操作失败而导致函数功能无法实现，时间和空间效率低。

例题10（2011年5月下午试题4）

阅读以下说明和C函数，填补C函数中的空缺（1）～（5），将解答写在答题纸的对应栏内。

【说明】

假设一个算术表达式中可以包含以下三种括号：“（”和“）”、“[”和“]”、“{”和“}”，并且这三种括号可以按照任意的次序嵌套使用。

下面仅考虑表达式中括号的匹配关系，其他问题暂时忽略。例如，表达式“[a．(b．5)]*c[{}]”中的括号是完全匹配的，而表达式“[a-(b-5]))*c”中的括号不是完全匹配的，因为“（”与“]”不能匹配，而且多了一个“）”，即缺少一个与“）”相匹配的“（”。

函数ifMatched (char expr[])的功能是用栈来判断表达式中的括号是否匹配，表达式以字符串的形式存储在字符数组expr中。若表达式中的括号完全匹配，则该函数的返回值为Matched，否则返回值为Mismatched。

该函数的处理思路如下：

（1）设置一个初始为空的栈，从左至右扫描表达式。

（2）若遇上左括号，则令其入栈；若遇上右括号，则需要与栈顶的左括号进行匹配。

（3）若所遇到的右括号能与栈顶的左括号配对，则令栈顶的左括号出栈，然后继续匹配过程；否则返回Mismatched，结束判断过程。

（4）若表达式扫描结束，同时栈变为空，则说明表达式中的括号能完全匹配，返回Matched。

函数ifMatched中用到了两种用户自定义数据类型BOOL和STACK，其中，BOOL类型的定义如下：

STACK（即栈类型）的定义省略，栈的基本操作的函数原型说明如下：

● void InitStack(STACK *S):初始化一个空栈。

● void Push(STACK *S，char e):将一个字符压栈，栈中元素数目增1。

● void Pop(STACK *S)：栈顶元素出栈，栈中元素数目减1。

● char Top(STACK S)：返回非空栈S的栈顶元素值，栈中元素数目不变。

● int IsEmpty(STACK S)：若S是空栈，则返回1，否则返回0。

例题分析

本题主要考查栈结构的应用。

题目告诉我们函数ifMatched的功能是用栈来判断表达式中的括号是否匹配，表达式以字符串的形式存储在字符数组expr中。若表达式中的括号完全匹配，则该函数的返回值为Matched，否则返回值为Mismatched。另外，题目也告诉了我们函数ifMatched的出来思路。

下面我们结合题目意思来具体分析本题的程序。

在函数ifMatched中，首先定义了一个字符型指针变量cptr和栈S，然后初始化一个空栈，根据题目意思接下来应该从左至右扫描表达式，这里用到了一个for循环，而空（1）正好是循环的步长，这里很显然是逐个元素扫描，因此步长为1，因此本空应填cptr++或++cptr。

再根据处理思路第2条，我们可以知道，如果扫描的过程中，碰上左括号，则应该入栈，而第（2）空前面的if语句显然是判断扫描的元素是否为左括号，因此第（2）空应填元素入栈的操作，根据题目给出的函数，可知应该用函数Push进行入栈操作，而它的两个参数分别是栈地址和入栈的元素，因此本空的答案为Push (&S,*cptr)。

如果扫描的元素不是左括号，就应该判断其是否是右括号，如果是右括号，则需要与栈顶的左括号进行匹配。空（3）和空（4）都是在扫描的元素为右括号的情况下执行的语句。其中空（3）所在语句的作用通过注释可以了解到，是完成取栈顶的左括号，但这里到底是要用出栈函数Pop还是取栈顶元素值函数Top呢？根据题目处理思路第3条的描述和程序我们不难知道，这里应该是取栈顶元素值来判断其是否能与扫描的右括号匹配，如果能匹配，再出栈，否则就不出栈。因此第（3）空应填Top(S)，这里大家一定要注意题目给出的函数的参数。

空（3）后面的3条语句都是用来判断栈顶元素值是否与扫描的右括号匹配用的，如果不匹配，则按题目要求返回Mismatched。如果匹配的话，那么栈顶元素应该出栈，第（4）空是完成栈顶元素的出栈操作，第（4）空应填Pop(&S)。

第（5）空是判断条件的条件表达式，如果该条件为真，则返回Matched，根据题目给出的处理思路第四条我们可以知道，这个时候应该是表达式扫描结束，并且栈变为空。因此本空应填IsEmpty(S)。

例题答案：

（1）cptr++ 或 ++cptr 或 cptr +=1 或 cptr = cptr+1

（2）Push(&S,*cptr)

（3）Top(S)

（4）Pop(&S)

（5）IsEmpty(S)

例题11

【说明】

本程序的函数sum(int,i int total,int sigma,int rear,int d[],int n) 用来从已知数组 d 的前 n 个元素中找出所有部分元素序列之和等于total的元素序列，约定数组d的元素都是正整数，且都小于等于total。

函数sum使用递归方法找出全部解答。参数i表示递归函数当前考虑元素d[i]，参数sigma 是调用前已选取的部分序列的元素和，参数rear是后面还未考虑的那部分元素的元素和。

函数对元素d[i]有两种可能的选择方案：

（1）考虑元素d[i]被包含在新的部分元素序列中的可能性。如果在当前部分元素序列之后接上d[i]，新序列的元素和不超过total，则函数将d[i]包含在当前部分元素序列中。如果新的部分元素序列的元素和等于total时，新的部分元素序列就是一个解答，函数将其输出；否则，若继续考虑后面的元素还有可能找到解答时，函数就递归去考虑后面的元素，寻找解答。最后，函数应恢复原来部分元素序列中不包含d[i]的状态。

（2）考虑元素d[i]不被包含在新的部分元素序列中的可能性。如果继续向d[i]之后考虑还是有希望能得到和为total的部分元素序列，函数将新序列不包含d[i]也作为一种可能的选择，并递归去考虑后面的元素，寻找解答。

例题分析

经对比分析我们发现，本程序问题和背包问题很相似，但比背包问题简单。背包问题是求同时满足总重量之和等于某个数和价值最高这两个条件的组合，而本程序问题只是求满足总重量之和这个条件的组合。

由程序说明可知，程序依次递归考察数组中每个元素。对当前考察的元素d[i]，考虑两种情况：一个是将该元素加入到解组合中，另一个是不考虑该元素加入到解组合中。

填空（1）所在子程序sum()的功能是考察数组中d当前元素d[i]加入解组合序列和不加入解组合序列的情况。仔细阅读这段程序，当第一个if语句中的条件sigma+d[i]＜= total成立，则当前元素d[i]可以加入到解组合序列中，设置加入标志后程序执行第二个if语句，由该if语句后面的程序段很明显可知，这个if语句是判断是否找到解，找到解的条件应该是当前已经选取的元素和sigma加上新加入解组合序列的元素b[i]等于total，故填空（1）应该是sigma+d[i]。

继续阅读程序，填空（2）语句位于第二个判断是否形成解的if语句相对应的else语句中。很明显，该语句是处理加入d[i]到组合序列后并没有形成解的情况，这时就需要递归调用sum()找解。考察sum()函数中各个参数的意义，填空（2）应该为形参sigma的实参，sigma的意义是“调用前已选取的部分序列的元素和”，故解组合序列中加入了d[i]后考察d[i＋1]时，sigma的值显然应该加上新加入的元素d[i]。故填空（2）应该是sigma+d[i]。

再看填空（3）的语句位置，其位于找解递归函数调用之后，则应该是找到解后程序应该执行的动作。从程序说明可知，寻找解答，函数应恢复原来部分元素序列中不包含d[i]的状态，故填空（3）应该将元素d[i]排除到解组合序列之外，即修改d[i]元素的加入标志flg[i]为0。故填空（3）应该是flg[i]=0。

理解了上面的解题思路，则可知填空（4）考虑元素d[i]不被包含在新的部分元素序列中的可能性。既然d[i]没有加入到解组合序列中，则递归考虑下一个元素d[i＋1]的加入与否时，sigma的值应该不变。故填空（4）应该还是sigma。

不难看出填空（5）是考察初始调用sum()函数时，形参rear的赋值情况。形参rear的意义是后面还未考虑的那部分元素的元素和，由于初始时还没有开始考虑任何元素，故此时rear应该等于所有元素之和，而从程序中可以看成，s正是所有元素的叠加之和。故填空（5）应该是s。

例题答案：

（1）sigma+d[i]

（2）sigma+d[i]

（3）flg[i]=0

（4）sigma

（5）s

例题12

【说明】

“背包问题”的基本描述是：有一个背包，能盛放的物品总重量为 S，设有 N 件物品，其重量分别为w ₁ ，w ₂ ，…，w _n ，希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于S。

如下程序均能求得“背包问题”的一组解，其中，程序1-8是“背包问题”的递归解法，而程序1-9是“背包问题”的非递归解法。

例题分析

背包问题是历年试题考得最多的一个经典问题，其可由递归和非递归两种算法实现。不管是递归，还是非递归，程序算法的思路都是先依次考察每个物品，对物品i，考察两种可能情况：首先，考察物品i被选择的情况，这种可能性当且仅当包含它不会超过方案总重量的限制时才是可行的，物品i被选择后，继续考察下一个物品（可采用递归考察或非递归）；其次，考察物品i不被选择的情况，当且仅当不包含物品i时，这种可能性也有可能找到价值更大方案的情况，考察完物品i后，也要继续考察下一个物品（也可采用递归考察或非递归）。

程序1-8用递归算法实现“背包问题”。对每个物品i，考察选择放入和不放入背包两种情况，函数knap ( int s，int n)，形参s中是考察完物品i后，背包还能装载的重量；n为考察完物品i后下一个待考察的物品。每次选择一个物品放入背包，那么剩余的物品和背包剩余的重量，又构成一个“背包问题”。分析填空（1）上下的语句，显然是考察物品i放入背包的情况，既然放入背包，则背包剩余可装重量为s w[n]，继续考察物品n 1。因此填空（1）应该是knap(s w[n],n 1)。

填空（2）显然是处理不包含物品i时的情况。既然物品i（这里为n）没有放入背包，则背包可装载重量当然还是s，而同时应该继续考察下一个物品n 1。不难得出填空（2）应该是knap(s,n 1)。

程序1-9是用非递归算法实现背包问题。程序使用栈（即数组stack表示）来保存到已经考察过的物品。经分析，程序中比较重要的一些变量所表示的功能为：结构变量KNAPTP表示经过考察的物品，其中的分量s表示考察过该物品后，背包所能盛放的物品的重量，分量n表示待考察的下一个物品在数组w中的下标，分量job表示物品当前的状态，job等于1，表示物品n可以放入背包，job等于2，表示物品不能放入背包，那么在以后的选取中，将不再考虑该物品，初始时，job等于0，表示背包中没有放入任何物品；当k＝1时，则求得了一组解，可知k为是否求得解的标志，k等于0表示没有解，需继续求解，k等于1表示求得了一组解；rep是一个标志变量，rep等于0，表示结束当前的动作，rep等于

1，表示继续进行当前的动作，当栈顶物品不能装入背包时，将rep置为0，表示下一步不再从数组w中取物品，rep初值为1；x为工作结点。

程序开始时将数组中下标最大的物品放入栈中，然后开始考察该物品（栈顶元素出栈），以后所考察的物品都从栈顶获取。对于填空（3），当k为1找到解时，则退出while（（3））循环，那么可知填空（3）有！k语句，同时考虑到当top＝0时，则找不到解，可知填空（3）应该是top＞0&&！k。

while（3）循环体内的语句可以肯定是考察各个物品i（这里为n）的选择情况。分析程序可知，对物品n，程序先考察将物品n放入背包的情况，显然如果物品n满足放入背包的条件，则填空（4）和（5）完成将物品放入背包的操作，其中（4）应该将工作结点x的s分量值减去所考察物品的重量，且n要减去1，修改背包可容纳物品的重量和设置下一个待考察物品，而（5）则需要将修改后的工作结点x送栈顶，将下一个待考察的物品放入栈中。故填空（4）应该是x.s w[x.n ]，填空（5）应该是stack[++top]。

继续往下阅读程序，语句if ( !k )后的语句是处理所考察的物品不满足放入背包的条件时的情况（rep＝0，while(!k && rep)循环结束），则将该物品从背包中取出，修改其job值为2，用以标识该物品不能放入背包，那么在以后的选取中，将不再考虑该物品。修改完成后跳出while(top＞＝1 && rep)循环，因此需要将rep置为0，用以结束循环while(top＞＝1 && rep)。所以填空（6）应该是rep=0。

例题答案：

（1）knap(s - w[n],n - 1)

（2）knap(s,n - 1)

（3）top ＞= 1 && !k或top ＞ 0 &&！

（4）x.s - w[x.n -]

（5）stack[++ top]

（6）rep=0 U6gDV+H1mf6hRIj7k1E0Vg9Unzzy/bh3a3R9dAul6JUmiANE6O6irX9w1xP+wpPB