1、程序员-数据结构与算法(二)及答案解析(总分：29.00，做题时间：90 分钟)一、综合知识试题(总题数：8，分数：8.00)1.当二叉树的结构形如_时，其后序遍历序列和中序遍历序列相同。（分数：1.00）A.B.C.D.2.设线性表(59，53，46，48，37，31，25)采用散列(Hash)法进行存储和查找，散列函数为 H(Key)=KeyMOD 7(MOD 表示整除取余运算)。若用链地址法解决冲突(即将相互冲突的元素存储在同一个单链表中)构造散列表，则散列表中与哈希地址_对应的单链表最长。（分数：1.00）A.2B.3C.4D.63.对长度为 n 的有序表进行二分(折半)查找时，无论查
2、找指定的一个元素是否成功，最多只与表中的_个元素进行比较即可。（分数：1.00）A.log2n-1B.log2n+1C.n/2D.n-14.对于具有 n 个元素的关键字序列(K 1，K 2，K n)，当且仅当满足关系 KiK 且 2ikik 2i+1 （分数：1.00）A.59，53，48，46，37，31，25B.59，46，53，48，37，31，25C.59，37，53，25，31，46，48D.59，53，48，31，25，46，375.输入受限的双端队列是指只有一端可以进行入队操作而从两端都可以进行出队操作的队列，如图 123所示。对于输入序列 1 2 3 4，经过一个初始为空且输入
3、受限的双端队列后，不能得到的输出序列为_。（分数：1.00）A.1 2 3 4B.4 3 2 1C.1 2 4 3D.4 2 1 36.设递增序列 A 为 a1，a 2，an，递增序列 B 为 b1，b 2，b m，且 mn，则将这两个序列合并为一个长度为 m+n 的递增序列时，当_时，归并过程中元素的比较次数最少。（分数：1.00）A.anb mB.anb 1C.a1b 1D.a1b m7.若二维数组 arr18，16的首地址为 base，数组元素按列存储，且每个元素占用 4 个存储单元，则元素 arr5，5在该数组空间的地址为_。（分数：1.00）A.base+(4*8+4)*4B.bas
4、e+(5*8+5)*4C.base+(4*6+4)*4D.base+(5*6+5)*48.已知某带权有向图 G(顶点数为 6，顶点编号为 1 至 6)的邻接表如下所示，其中表结点的结构为：（分数：1.00）A.9B.11C.15D.18二、案例分析试题(总题数：0，分数：0.00)三、试题一(总题数：1，分数：5.00)说明对于具有 n 个元素的整型数组 a，需要进行的处理是删除 a 中所有的值为 0 的数组元素，并将 a 中所有的非 0 元素按照原顺序连续地存储在数组空间的前端。下面分别用函数 CompactArr_v1 和 CompactArr_v2 来实现上述处理要求，函数的返回值为非零
5、元素的个数。函数 CompactArr_v1(int a，intn)的处理思路是：先申请一个与数组 a 的大小相同的动态数组空间，然后顺序扫描数组 a 的每一个元素，将遇到的非 0 元素依次复制到动态数组空间中，最后再将动态数组中的元素传回数组 a 中。函数 CompactArr_v2(int a，int n)的处理思路是：利用下标 i(初值为 0)顺序扫描数组 a 的每一个元素，下标 k(初值为 0)表示数组 a 中连续存储的非 0 元素的下标。扫描时，每遇到一个数组元素，i 就增1，而遇到非 0 元素并将其前移后 k 才增 1。程序 1-4int CompactArr_v1(int a,i
6、nt n)int i，k；int*temp=(int*)malloc(n* (1) if(!temp)return-1；for(i=0，k=0;in；i+)if(ai!=0)(2) =ai；for(i=0； (3) ；i+)ai=tempi；return k；程序 1-5int CompactArr v2(int a，int n)int i，k；for(i=0,k=0；in；i+)if(ai!=0)(4) =ai；return k；（分数：5.00）(1).请根据说明中函数 CompactArr_v1 的处理思路填补空缺(1)(3)，根据 CompactArr_2 的处理思路填补空缺(4)。（
7、分数：2.50）填空项 1:_(2).请说明函数 CompactArr_v1 存在的缺点。（分数：2.50）填空项 1:_四、试题二(总题数：1，分数：5.00)说明假设一个算术表达式中可以包含以下三种括号：“(”和“)”、“”和“”、“”和“”，并且这三种括号可以按照任意的次序嵌套使用。下面仅考虑表达式中括号的匹配关系，其他问题暂时忽略。例如，表达式“a.(b.5)*c”中的括号是完全匹配的，而表达式“a-(b-5)*c”中的括号不是完全匹配的，因为“(”与“”不能匹配，而且多了一个“)”，即缺少一个与“)”相匹配的“(”。函数 ifMatched(char expr)的功能是用栈来判断表达
8、式中的括号是否匹配，表达式以字符串的形式存储在字符数组 expr 中。若表达式中的括号完全匹配，则该函数的返回值为 Matched，否则返回值为该函数的处理思路如下：(1)设置一个初始为空的栈，从左至右扫描表达式。(2)若遇上左括号，则令其入栈；若遇上右括号，则需要与栈顶的左括号进行匹配。(3)若所遇到的右括号能与栈顶的左括号配对，则令栈顶的左括号出栈，然后继续匹配过程；否则返回Mismatched，结束判断过程。(4)若表达式扫描结束，同时栈变为空，则说明表达式中的括号能完全匹配，返回 Mached。函数 ifMached 中用到了两种用户自定义数据类型 BOOL 和 STACK，其中，BO
9、OL 类型的定义如下：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。程序 16BOOL ifMatched(char expr)char*cptr; /*cptr 指向表达式中的字
10、符*/STACK S;char e;InitStack(*cptr!=/0; (1) if(*cptr=(|*cptr=|*cptr=)(2) ;elseif(*cptr=)|*cptr=)if(IsEmpty(S)return Mismatched；e= (3) ； /*取栈顶的左括号*/if(*cptr=)/flgj=0；j+)；printf(“%4d=%d“，total，dj)；for(j+；j=i;j+)if(flgj)printf(“+%d“，dj)；printf(“n“)；else /*继续考虑后面的元素有可能找到解答时*/if(in-1in；i+)if(ai!=0)(2) =ai
11、；for(i=0； (3) ；i+)ai=tempi；return k；程序 1-5int CompactArr v2(int a，int n)int i，k；for(i=0,k=0；in；i+)if(ai!=0)(4) =ai；return k；（分数：5.00）(1).请根据说明中函数 CompactArr_v1 的处理思路填补空缺(1)(3)，根据 CompactArr_2 的处理思路填补空缺(4)。（分数：2.50）填空项 1:_ （正确答案：(1)sizeof(int)(2)tempk+或*(temp+k+)或等价表示(3)ik 或等价表示(4)ak+或。(a+k+)或等价表示）解析
12、：解析 本题是一个对数组进行操作的问题。题目要求删除数组 a 中所有的值为 0 的数组元素，并将 a 中所有的非 0 元素按照原顺序连续地存储在数组空间的前端。并且在题目中给出了两个实现函数分别为函数 CompactArr_v1 和 CompactArr_v2。根据题目说明，我们可知本题的逻辑关系并不复杂，只要找到数组中值不为 0 的元素，然后按原来的顺序连续存储即可，这里可以借助其他的存储空间来完成，也可以不借助其他的存储空间来完成。下面我们就来具体分析 CompactArr_v1 和 CompactArr_v2。前面三空都在函数 CompactArr v1 中，在函数 CompactArr
13、_v1 的开始处定义了一个指针变量 temp，并使其指向一块动态分配的存储空间，而空(1)就在该动态分配存储空间的语句中，根据函数 malloc 的格式我们可以知道函数 malloc 后面括号中要给出分配空间的大小，结合整个函数 CompactArr_v1 来看，这里动态分配的存储空间是用来-临时存放数组中非 0 元素的，因此其空间大小应该为 n 乘以一个整型变量所占的空间，而这可以通过函数 sizeof 求得，因此空(1)处应填 sizeof(int)。空(2)在函数的第一个 for 循环结构中，从题目意思及结合程序不难看出，该 for 循环的作用是变量整个数组，并找出数组中值不为 0 的元
14、素，而空(2)所在的赋值语句是在数组当前元素的值不等于 0 的情况下执行的语句，并且是将数组的当前元素赋值给空(2)，很显然，这里是将非 0 元素存放到动态分配的存储空间中，因此本空应填 tempk+。k 是 temp 数组的下标。空(3)是第二个 for 循环的结束条件，根据题目意思和程序不难看出该循环的作用是将存放在临时空间的非 0 元素依次存放至数组 a 中，因此循环结束的条件是循环变量 i 小于非 0 元素的个数，从上一个循环中可以看出变量 k 的值就是非 0 元素的个数值。因此本空应填 ik。第(4)空在函数 CompactArr_v2 中，根据题目意思，函数 CompactArr_
15、v2 没有借助其他的存储空间来完成删除数组 0 元素的任务，这里采用覆盖前面元素的方式来实行。再看程序，空 4 所在的赋值语句是在数组当前元素的值不等于 0 的情况下执行的语句，并且是将数组的当前元素赋值给空(4)，因此本空应填ak+，当然填*(a+k+)也是一样的。(2).请说明函数 CompactArr_v1 存在的缺点。（分数：2.50）填空项 1:_ （正确答案：可能由于动态内存申请操作失败而导致函数功能无法实现，时间和空间效率低。）解析：解析 本题的函数 CompactArr_v1 在完成题目要求的功能时，利用了其他的辅助存储空间，很显然，其空间和时间效率都比函数 CompactAr
16、r_v2 要低，而且在动态申请存储空间时，有可能会失败，从而导致函数功能无法实现。四、试题二(总题数：1，分数：5.00)说明假设一个算术表达式中可以包含以下三种括号：“(”和“)”、“”和“”、“”和“”，并且这三种括号可以按照任意的次序嵌套使用。下面仅考虑表达式中括号的匹配关系，其他问题暂时忽略。例如，表达式“a.(b.5)*c”中的括号是完全匹配的，而表达式“a-(b-5)*c”中的括号不是完全匹配的，因为“(”与“”不能匹配，而且多了一个“)”，即缺少一个与“)”相匹配的“(”。函数 ifMatched(char expr)的功能是用栈来判断表达式中的括号是否匹配，表达式以字符串的形式
17、存储在字符数组 expr 中。若表达式中的括号完全匹配，则该函数的返回值为 Matched，否则返回值为该函数的处理思路如下：(1)设置一个初始为空的栈，从左至右扫描表达式。(2)若遇上左括号，则令其入栈；若遇上右括号，则需要与栈顶的左括号进行匹配。(3)若所遇到的右括号能与栈顶的左括号配对，则令栈顶的左括号出栈，然后继续匹配过程；否则返回Mismatched，结束判断过程。(4)若表达式扫描结束，同时栈变为空，则说明表达式中的括号能完全匹配，返回 Mached。函数 ifMached 中用到了两种用户自定义数据类型 BOOL 和 STACK，其中，BOOL 类型的定义如下：STACK(即栈类
18、型)的定义省略，栈的基本操作的函数原型说明如下： 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。程序 16BOOL ifMatched(char expr)char*cptr; /*cptr 指向表达式中的字符*/STACK S;char e;In
19、itStack(*cptr!=/0; (1) if(*cptr=(|*cptr=|*cptr=)(2) ;elseif(*cptr=)|*cptr=)if(IsEmpty(S)return Mismatched；e= (3) ； /*取栈顶的左括号*/if(*cptr=)/flgj=0；j+)；printf(“%4d=%d“，total，dj)；for(j+；j=i;j+)if(flgj)printf(“+%d“，dj)；printf(“n“)；else /*继续考虑后面的元素有可能找到解答时*/if(in-1&rear+sigma=total)sum(i+1，total， (2) ，rear
20、-di，d，n)；(3) ；/*考虑元素 di不被包含在新的部分元素序列中的可能性*/if(in-1&rear-di+tigma=total)sum(i+1，total， (4) ，rear-di，d，n)；main()int ij，n，total，s，d；printf(“输入 total!/n“)；scanf(“%d“,&total)；printf(“输入 n!/n“)；scanf(“%d“,&n)；for(s=i=0；in；=printf(“输入第%d 个元素0 且=%d)n“，i+1,total；scanf(“%d“，&d)；if(d1 | dtotal)printf(“出错，请重新输入
21、!n“)；continue；S+=ai+=d；sum(0,total，0， (5) ，a，n)；printf(“nn“)；（分数：5.00）填空项 1:_ （正确答案：sigma+d(）解析：填空项 1:_ （正确答案：sigma+di）解析：填空项 1:_ （正确答案：flgi=0）解析：填空项 1:_ （正确答案：sigma）解析：填空项 1:_ （正确答案：s）解析：解析 经对比分析我们发现，本程序问题和背包问题很相似，但比背包问题简单。背包问题是求同时满足总重量之和等于某个数和价值最高这两个条件的组合，而本程序问题只是求满足总重量之和这个条件的组合。由程序说明可知，程序依次递归考察数组
22、中每个元素。对当前考察的元素 di，考虑两种情况：一个是将该元素加入到解组合中，另一个是不考虑该元素加入到解组合中。填空(1)所在子程序 sum()的功能是考察数组中 d 当前元素 di加入解组合序列和不加入解组合序列的情况。仔细阅读这段程序，当第一个 if 语句中的条件 sigma+di=total 成立，则当前元素 di可以加入到解组合序列中，设置加入标志后程序执行第二个 if 语句，由该 if 语句后面的程序段很明显可知，这个 if 语句是判断是否找到解，找到解的条件应该是当前已经选取的元素和 sigma 加上新加入解组合序列的元素 bi等于 total，故填空(1)应该是 sigma+
23、di。继续阅读程序，填空(2)语句位于第二个判断是否形成解的 if 语句相对应的 else 语句中。很明显，该语句是处理加入 di到组合序列后并没有形成解的情况，这时就需要递归调用 sum()找解。考察 sum()函数中各个参数的意义，填空(2)应该为形参 sigma 的实参，sigma 的意义是“调用前已选取的部分序列的元素和”，故解组合序列中加入了 di后考察 di+1时，sigma 的值显然应该加上新加入的元素 di。故填空(2)应该是 sigma+di。再看填空(3)的语句位置，其位于找解递归函数调用之后，则应该是找到解后程序应该执行的动作。从程序说明可知，寻找解答，函数应恢复原来部分
24、元素序列中不包含 di的状态，故填空(3)应该将元素 di排除到解组合序列之外，即修改 di元素的加入标志 flgi为 0。故填空(3)应该是 figi=0。理解了上面的解题思路，则可知填空(4)考虑元素 di不被包含在新的部分元素序列中的可能性。既然di没有加入到解组合序列中，则递归考虑下一个元素 di+1的加入与否时，sigma 的值应该不变。故填空(4)应该还是 sigma。不难看出填空(5)是考察初始调用 sum()函数时，形参 rear 的赋值情况。形参 rear 的意义是后面还未考虑的那部分元素的元素和，由于初始时还没有开始考虑任何元素，故此时 rear 应该等于所有元素之和，而从
25、程序中可以看成，s 正是所有元素的叠加之和。故填空(5)应该是 s。六、试题四(总题数：1，分数：6.00)说明“背包问题”的基本描述是：有一个背包，能盛放的物品总重量为 S，设有 N 件物品，其重量分别为w1，W 2，W n，希望从 N 件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于 s。如下程序均能求得“背包问题”的一组解，其中，程序 18 是“背包问题”的递归解法，而程序 1-9 是“背包问题”的非递归解法。程序 18#includestdio.h#define N 7#define S 15int WN+1=0，1，4，3，4，5，2，7；int k
26、nap(int s，int n)if(s=0)return 1；if(s0|(s0&n1)return 0；if(1) /*考虑物品 n 被选择的情况*/printf(“4d“wn)；return 1；return(2)； /*考虑不选择物品 n 的情况*/main()if(knap(S，N)printf(“OK!n“)；else printf(“N0!/n“)；程序 1-9#includestdio.h#define N 7#define S 15typedef structint s；int n；int job；KNAPTP；int wN+1=0，1，4，3，4，5，2，7)；int kn
27、ap(int S，int n)；main()if(knap(S，N)printf(“OK!/n“)；else printf(“NO!/n“)；int knap(int s,int n)KNAPTP stack100,x；int top，k，rep；x.s=s；x.n=n；x.job=0：top=1；stacktop=x；k=0：while(3)x=stacktop；rep=1：while(!k&rep)if(x.s=0)k=1； /*已求得一组解*/else if(x.s0 | x.n=0)rep=O；elsex.s(4)；x.job=1；(5)=x：if(!k)rep=1；while(top
28、=1&rep)X=stacktop-；if(x.job=1)x.S+=wx.n+1；x.job=2；stack+top=x：(6)；if(k) */输出一组解*/while(top=1)x=stacktop-；if(x.job=1)printf(“M/t, wx.n+1)；return k；（分数：6.00）_正确答案：(knap(s-Wn，n-1)解析：_正确答案：(knap(s，n-1)解析：_正确答案：(top=1&!k 或 top0&!)解析：_正确答案：(x.s-wx.n-)解析：_正确答案：(stack+top)解析：_正确答案：(rep=0)解析：解析 背包问题是历年试题考得最多
29、的一个经典问题，其可由递归和非递归两种算法实现。不管是递归，还是非递归，程序算法的思路都是先依次考察每个物品，对物品 i，考察两种可能情况：首先，考察物品 i 被选择的情况，这种可能性当且仅当包含它不会超过方案总重量的限制时才是可行的，物品 i被选择后，继续考察下一个物品(可采用递归考察或非递归)；其次，考察物品 i 不被选择的情况，当且仅当不包含物品 i 时，这种可能性也有可能找到价值更大方案的情况，考察完物品 i 后，也要继续考察下一个物品(也可采用递归考察或非递归)。程序 1-8 用递归算法实现“背包问题”。对每个物品 i，考察选择放入和不放入背包两种情况，函数knap(int s，in
30、t n)，形参 s 中是考察完物品 i 后，背包还能装载的重量；n 为考察完物品 i 后下一个待考察的物品。每次选择一个物品放入背包，那么剩余的物品和背包剩余的重量，又构成一个“背包问题”。分析填空(1)上下的语句，显然是考察物品 i 放入背包的情况，既然放入背包，则背包剩余可装重量为 s wn，继续考察物品 n 1。因此填空(1)应该是 knap(s wn，n 1)。填空(2)显然是处理不包含物品 i 时的情况。既然物品 i(这里为 n)没有放入背包，则背包可装载重量当然还是 s，而同时应该继续考察下一个物品 n 1。不难得出填空(2)应该是 knap(s，n 1)。程序 1-9 是用非递归
31、算法实现背包问题。程序使用栈(即数组 stack 表示)来保存到已经考察过的物品。经分析，程序中比较重要的一些变量所表示的功能为：结构变量 KNAPTP 表示经过考察的物品，其中的分量s 表示考察过该物品后，背包所能盛放的物品的重量，分量 n 表示待考察的下一个物品在数组 w 中的下标，分量 job 表示物品当前的状态，job 等于 1，表示物品 n 可以放入背包，job 等于 2，表示物品不能放入背包，那么在以后的选取中，将不再考虑该物品，初始时，job 等于 0，表示背包中没有放入任何物品；当k=1 时，则求得了一组解，可知 k 为是否求得解的标志，k 等于 0 表示没有解，需继续求解，k
32、 等于 1 表示求得了一组解；rep 是一个标志变量，rep 等于 0，表示结束当前的动作，rep 等于 1，表示继续进行当前的动作，当栈顶物品不能装入背包时，将 rep 置为 0，表示下一部不再从数组 w 中取物品，rep 初值为1；x 为工作结点。程序开始时将数组中下标最大的物品放入栈中，然后开始考察该物品(栈顶元素出栈)，以后所考察的物品都从栈顶获取。对于填空(3)，当 k 为 1 找到解时，则退出 while(3)循环，那么可知填空(3)有!k 语句，同时考虑到当 top=0 时，则找不到解，可知填空(3)应该是 top0&!k。while(3)循环体内的语句可以肯定是考察各个物品 i
33、(这里为 n)的选择情况。分析程序可知，对物品 n，程序先考察将物品 n 放入背包的情况，显然如果物品 n 满足放入背包的条件，则填空(4)和(5)完成将物品放入背包的操作，其中(4)应该将工作结点 x 的 s 分量值减去所考察物品的重量，且 n 要减去 1，修改背包可容纳物品的重量和设置下一个待考察物品，而(5)则需要将修改后的工作结点 x 送栈顶，将下一个待考察的物品放入栈中。故填空(4)应该是 x.s wx.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。
