1、软件水平考试中级软件设计师上午基础知识（数据结构与算法基础）模拟试卷 1及答案与解析 1 以下关于线性表采用链式存储时删除结点运算的描述，正确的是 ( )。 （ A）带头结点的线性链表删除结点时，不需要更改头指针 （ B）带头结点的线性链表删除第一个结点时，需要更改头指针 （ C）不带头结点的线性链表删除结点时，需要更改头指针 （ D）不带头结点的线性链表删除第一个结点时，不需要更改头指针 2 给定一个有 n个元素的有序线性表。若采用顺序存储结构，则在等概率前提下，删除其中的一个元素平均需要移动 ( )个元素。 （ A） （ B） （ C） （ D） 1 3 下列叙述中，不正确的是 ( )。
2、（ A）线性表在链式存储时，查找第 i个元素的时间与 i的值成正比 （ B）线性表在链式存储时，查找第 i个元素的时间与 i的值有关 （ C）线性表在顺序存储时，查找第 i个元素的时间与 i的值成正比 （ D）线性表在顺序存储时，查找第 i个元素的时间与 i的值无关 4 双向循环链表中，在 p所指向的结点之后插入 s指向的结点，其修改指针的操作是 ( )，其中 p指向的不是最后一个结点。 （ A） p-next=s； s-preV=p； p-next-prev=s； s=next=p-next； （ B） p-next-prev=s； p next=s； s-prev=p； s-next=p-
3、next； （ C） s-prev=p； s-next=p-next； p-next=-s； p-next-prev=s； （ D） s-prev=p； s-next=p-next； p-next-prev=s； p-next=-s； 5 若元素 a， b， c， d， e， f依次进栈，允许进栈、退栈操作交替进行。 但不允许连续三次进行退栈工作，则不可能得到的出栈序列是 ( )。 （ A） dcebfa （ B） cbdaef （ C） bcaefd （ D） afedcb 6 一个栈的入栈元素序列是 1、 2、 3、 4、 5，若允许出栈操作可在任意可能的时刻进行，则下面的序列中，不可能出
4、现的出栈序列是 ( )。 （ A） 3、 4、 2、 5、 1 （ B） 2、 5、 4、 1、 3 （ C） 2、 3、 1、 5、 4 （ D） 3、 5、 4、 2、 1 7 下面二叉树中一定是完全二叉树的是 ( )。 （ A）平衡二叉树 （ B）满二叉树 （ C）单枝二叉树 （ D）二叉排序树 8 在一棵度为 4的树 T中，若有 20个度为 4的结点， 10个度为 3的结点， 1个度为 2的结点， 10个度为 1的结点，则树 T的叶子结点的个数是 ( )。 （ A） 41 （ B） 82 （ C） 113 （ D） 122 9 已知某二叉树的先序序列为 abcde，它可能的中序序列为
5、( )。 （ A） bdaec （ B） bcade （ C） ecadb （ D） beacd 10 一棵度为 3的树中，有 3度结点 100个，有 2度结点 200个，有叶子结点 ( )个。 （ A） 399 （ B） 400 （ C） 401 （ D） 402 11 在查找算法中，可用平均查找长度 (记为 ASL)来衡量一个查找算法的优劣，其定义为： 此处 Pi为表中第 i个记录被查找的概率， Ci为查找第 i个记录时同关键字比较的次数， n为表中记录数。以下叙述中均假定每一个记录被查找的概率相等，即 Pi=1 n(i=1， 2， ， n)。当表中的记录连续有序存储在一个一维数组中时，采
6、用顺序查找与折半查找方法查找的值分别是 ( )。 （ A） O(n)， O(n) （ B） D(n)， O(1bn) （ C） D(n1bn)， O(n) （ D） O(1bn)， O(1bn) 12 根据使用频率，为 5个字符设计哈夫曼编码不可能是 ( )。 （ A） 111， 110， 10， 01， 00 （ B） 000， 001， 010， 011， 1 （ C） 001， 000， 10， 01， 11 （ D） 110， 100， 101， 11， 1 13 二叉树在线索化后，仍不能有效解决的问题是 ( )。 （ A）先序线索二叉树中求先序后继 （ B）中序线索二叉树中求中序后继
7、 （ C）中序线索二叉树中求中序前驱 （ D）后序线索二叉树中求后序后继 14 由元素序列 (27， 16， 75， 38， 51)构造平衡二叉树，则首次出现的最小不平衡子树的根 (即离插入结点最近且平衡因子的绝对值为 2的结点 )为 ( )。 （ A） 27 （ B） 38 （ C） 51 （ D） 75 15 若 G是一个具有 36条边的非连通无向图 (不含自回路和多重边 )，则图 G至少有( )个顶点。 （ A） 11 （ B） 10 （ C） 9 （ D） 8 16 有向图 1 1的所有拓扑排序序列有 ( )个。 （ A） 2 （ B） 4 （ C） 6 （ D） 7 17 设下三角矩
8、阵 (上三角部分的元素值都为 0)A0 n， 0 n如图 1 2所示，将该三角矩阵的所有非零元素 (即行下标不小于列下标的元素 )按行优先压缩存储在容量足够大的数组 M口中 (下标从 1开始 )，则元素 Ai,j(0in， ji)存储在数组 M的 ( )中。 （ A） （ B） （ C） （ D） 18 在内排序的过程中，通常需要对待排序的关键码集合进行多遍扫描。采用不同排序方法，会产生不同的排序中间结果。设要将序列 中的关键码按字母的升序重新排列，则 ( )是冒泡排序一趟扫描的结果。 （ A） F， H， C， D， P， A， M， Q， R， S， Y， X （ B） P， A， C，
9、S， Q， D， F， X， R， H， M， Y （ C） A， D， C， R， F， Q， M， S， Y， P， H， X （ D） H， C， Q， P， A， M， S， R， D， F， X， Y 19 用插入排序和归并排序算法对数组 i进行从小到大排序，则分别需要进行 ( )次数组元素之间的比较。 （ A） 12， 14 （ B） 10， 14 （ C） 12， 16 （ D） 10， 16 20 递归算法的执行过程，一般来说，可先后分成 ( )两个阶段。 （ A）试探和回归 （ B）递推和回归 （ C）试探和返回 （ D）递推和返回 21 若有数组声明 a0 3， 0 2，
10、1 4，设编译时为 a分配的存储空间首地址为 base a，且每个数组元素占据一个存储单元。当元素以行为序存放 (即按a0， 0， 1， a0， 0,2， a0， 0,3， a0， 0,4， a0， 1， 1， a0， 1， 2， ， a3，2,4顺序存储 )，则数组元素 a2,2,2在其存储空间中相对 base a的偏移量是 ( )。 （ A） 8 （ B） 12 （ C） 33 （ D） 48 22 一个具有 967个结点的完全二叉树，其叶子结点个数为 ( )。 （ A） 483 （ B） 484 （ C） 485 （ D） 486 23 若循环队列以数组 Q0， ， m-1作为其存储结构
11、，变量 rear表示循环队列中队尾元素的实际位置，其移动按 Fear=(rear+1)mod m进行，变量 length表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是 ( )。 （ A） rear-length （ B） (irear-length+m)mod m （ C） (1+rear+m-length)mod m （ D） m-length 24 若一棵哈夫曼树共有 13个顶点，则其叶子结点的个数为 ( )。 （ A） 5 （ B） 6 （ C） 7 （ D） 8 25 若广义表 L=(a， b， c)， e)，则 L的长度和深度分别为 ( )。 （ A） 2和 1 （
12、B） 2和 2 （ C） 4和 2 （ D） 4和 1 26 若二叉树的先序遍历序列为 ABDECF，中序遍历序列为 DBEAFC，则其后序遍历序列为 ( )。 （ A） DEBAFC （ B） DEFBCA （ C） DEBCFA （ D） DEBFCA 27 已知一个线性表 (38， 25， 74， 63， 52， 48)，假定采用散列函数 h(key)=key 7计算散列地址，并散列存储在散列表 A0， ， 6中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为 ( )。 （ A） 1 5 （ B） 1 7 （ C） 2 0 （ D） 2 3 28 设某算法的
13、计算时间可用递推关系式 T(n)=2T(n 2)n表示，则该算法的时间复杂度为 ( )。 （ A） O(lgn) （ B） O(nlgn) （ C） O(n) （ D） O(n2) 29 算法策略与递归技术的联系最弱。 （ A）分治 （ B）动态规划 （ C）贪心 （ D）回溯 30 对于具有 n个元素的一个数据序列，若只需得到其中第 k个元素之前的部分排序，最好采用 ( )。 （ A）直接插入排序 （ B）希尔排序 （ C）快速排序 （ D）堆排序 软件水平考试中级软件设计师上午基础知识（数据结构与算法基础）模拟试卷 1答案与解析 1 【正确答案】 A 【试题解析】 带头结点的线性链表的头指
14、针指向其头结点，而该头结点是不能被删除的，所以头指针的值不需要更改。不 带头结点的线性链表在删除第一个结点后，需要将头指针指向新的第一个结点，而如果删除其他结点，则不需要更改头指针。 2 【正确答案】 C 【试题解析】 题目要求计算进行删除操作时平均移动元素个数，如图 1 3所示，若要删除 f，则无须移动任何元素，直接删除即可；若要删除 e，则需要移动 1个元素，即把 f移至 e位置；若要删除 d，则需要移动 2个元素，把 e移至 d位置，再把 f移至 e位置；依此类推，要删除第 1个元素，则需要移动 n一 1个元素。由于每个元素被删除的概率是相等的，所以平均需要移动的元素个数为：所以此题答案
15、为 C。 3 【正确答案】 C 【试题解析】 顺序存储结构的特点是 “顺序存储，随机存取 ”，也就是说，线性表在顺序存储时，查找第 i个元素的时间与 i的值无关。 链式存储结构的特点则是 “随机存储，顺序存取 ”，也就是说，链式存储结构的数据元素可以随机地存储在内存单元中，但访问其中的任意一个数据元素时，都必须从其头指针开始逐个进行访问。 4 【正确答案】 D 【试题解析】 其插入方法如图 1 4所示。一般情况下，做此类题的一个捷径是判断代码 “p-next=s”后是否还有通过指针 “p-next”访问 p以前的 直接后继的引用，有则错误。因为一旦执行完代码 “p-next=s”， p的直接后
16、继就更改为 s，此后 “p一 next”不再是 p以前的直接后继。例如，试题中 A、 B和 C选项均在 “p-next=s”之后使用了 “p-next”，所以选项 A、 B和 C错误，根据排除法，选项 D正确。另外，建议考生在编写插入代码时，将 “p-next=s”写成插入算法的最后一步。 5 【正确答案】 D 【试题解析】 栈按照后进先出的原则操作数据。 选项 A可以按照 a入栈、 b入栈、 c入栈、 d入栈、 d出栈、 c出栈、 e入栈、 e出栈、 b出 栈、 f入栈、 f出栈、 a出栈的方式得到。只有连续 2次出栈操作，符合试题要求。 选项 B可以按照 a入栈、 b入栈、 c入栈、 c出
17、栈、 b出栈、 d入栈、 d出栈、 a出栈、 e入栈、 e出栈、 f入栈、 f出栈的方式得到。只有连续 2次出栈操作，符合试题要求。 选项 C可以按照 a入栈、 b入栈、 b出栈、 c入栈、 c出栈、 a出栈、 d入栈、 e入栈、 e出栈、 f入栈、 f出栈、 d出栈的方式得到。只有连续 2次出栈操作，符合试题要求。 选项 D可以按照 a入栈、 a出栈、 b入栈、 c入栈、 d入栈、 e入栈、 f入栈、 f出栈、 e出栈、 d出栈、 c出栈、 b出栈的方式得到，但这个顺序不符合题目中不允许连续三次进行退栈的要求。 6 【正确答案】 B 【试题解析】 栈的特点是先进后出，按照以下步骤可以很快找到
18、答案： (1)选择出栈序列的第一个元素 a，入栈序列中在 a之前的元素必须按照逆序出现在出栈序列中，如果不按照逆序出栈，则此出栈序列不合法，否则执行下一步。 (2)从入栈序列和出栈序列中将元素 a删除，如果删除 a后出栈序列为空，则说明此出栈序列合法，否则回到上一步继续执行。 在本题中， B选项的第一个出栈元素为 2，在 2之前入栈 的元素的为 1，由于只有一个元素，故无论如何将会逆序出栈；在序列中剔除 2，则入栈序列为 1、 3、4、 5，出栈序列变为 5、 4、 1、 3。分析元素 5，在新的入栈序列中， 5之前的元素入栈序列为 1、 3、 4，而出栈序列为 4、 1、 3，不满足逆序出栈
19、的条件，所以选项B是不可能出现的出栈序列。 7 【正确答案】 B 【试题解析】 满二叉树除最后一层外，每一层上的所有结点都有两个子结点，满二叉树中每一层上的结点的数都达到最大，即在满二叉的第 k层上有 2k-1个结点，否则就不是满二叉树。深度为 m的满二叉树有 2m-1个结点。 完全 二叉树除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。满二叉树也是完全二叉树，反之完全二叉树不一定是满二叉树。平衡二叉树，单支二叉树和二叉排序树既不一定是满二叉树，也不一定是完全二叉树。 8 【正确答案】 B 【试题解析】 在树中，除根结点外，其余所有结点都是由其双亲结点引出的。一个
20、度为 n的结点表示由该结点引出 n个孩子结点，因此，树 T的结点个数为204+103+12+101+1=123，其中最后的 1为根结点，则叶子结点数为 123-(20+10+1+10)=82个。 9 【正确答案】 B 【试题解析】 二叉树的先序序列可以分为连续的 3个部分：根结点、左子树部分、右子树部分。中序遍历也可以分为 3个部分：左子树部分、根结点、右子树部分。题目给出的先序序列为 abcde，可知 a为根结点。 在 A选项中，给出的中序序列 bdaec表示 bd是左子树部分， ec是右子树部分，这与先序序列 abcde矛盾 (在先序序列中， bd不在一起， ec也不在一起 )，因此，不是
21、可能的中序序列。 在 B选项中，给出的序列 bcade表示 bc是左子树部分， de是右子树部分，这与先序序列 abcde不矛盾，是可能的中序序列。对左子树部分而言，在先序序列中的顺序是 bc，说明 b是根结点；在中序序列中的顺序也是 bc，说明 c是 b的右孩子。对右子树而言，在先序序列中的顺序是 de，说明 d是根结点；在中序序列中的顺序也是 de，说明 e是 d的右孩子。因此， B选项符合要求。 在 C选项中，给出的中序序列 ecadb表示 ec是左子树部分， db是右子树部分，这与先序序列 abcde矛盾 (在先序序列中， ec不在一起， db也不在一起 )，因此不是可能的中序序列。
22、在 D选项中，给出的中序序列 beacd表示 be是左子树部分 ， cd是右子树部分，这与先序序列 abcde矛盾 (在先序序列中， be不在一起 )，因此，不是可能的中序序列。 10 【正确答案】 C 【试题解析】 先推导这种题目的一般解法得到结论，然后再将已知条件代入。 首先，统计树中结点的总数 n。设树中度为 0的结点个数为 n0，度为 1的结点个数为 n1，度为 2的结点个数为 n2，度为 3的结点个数为 n3，则树的结点总数为n=n0+n1+n2+n3。因为树的根结点没有双亲结点，进入它的边数为 0，其他每个结点都有一个且仅有一个双亲结点，进入它们的边数各为 1，故树中总的边数为 e
23、-=n一 1=n0+n1+n2+n31。 又由于每个度为 0的结点发出 0条边，每个度为 1的结点发出 1条边，每个度为 2的结点发出 2条边，每个度为 3的结点发出 3条边，因此，总的边数可以表示为 e=n1+2*n2+3*n3。 将 e的等式等同起来，有n0+n1+n2+n31=n1+2*n2+3*n3，则有 n0=n2+2*n3+1。 在本题中，由题意可知，n2=200， n3=100，则 n0=401。 11 【正确答案】 B 【试题解析】 顺序查找的基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和 给定值 k相比较。若当前扫描到的结点关键字与 k相等，则查找成功
24、；若扫描结束后，仍未找到关键字等于 k的结点，则查找失败。顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构。 成功的顺序查找的平均查找长度如下： 在等概率情况下， pi=1n(1in)，故成功的平均查找长度为 (n+2+1) n=(n+1) 2，即查找成功时的平均比较次数约为表长的一半。若 k值不在表中，则需进行 n+1次比较之后才能确定查找失败。查找时间复杂度为 O(n)。 若事先知道表中各结点的查找概率不相等，以及它们的分布 情况，则应将表中结点按查找概率由小到大的顺序存放，以便提高顺序查找的效率。 顺序查找的优点是算法简单，且对表的结构无任何要求，无论是用向量还是用
25、链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。其缺点是查找效率低，因此，当 n较大时不宜采用顺序查找。 二分法查找又称折半查找，是一种效率较高的查找方法。二分法查找要求线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。 二分法查找的基本思想是 (设 Rlow， ， high是当前的查找区间 )： (1)确定该区间的中点位置： mid=(10w+high) 2。 (2)将待查的 k值与 Rmid key比较，若相等，则查找成功并返回此位置，否则需确定新的查找区间，继续二分查找，具体方法如下： 若 Rmid keyk，则由表的有序性可知 Rmid， ， n ke
26、y均大于 k，因此若表中存在关键字等于 k的结点，则该结点必定是在位置 mid左边的子表Rlow， ， mid一 1中。因此，新的查找区间是左子表 Rlow， ， high，其中high=mid一 1。 若 Rmid key2n)。 12 【正确答案】 B 【试题解析】 哈夫 曼编码属于前缀编码，根据前缀编码的定义，任一字符的编码都不是另一字符编码的前缀。而在选项 D中， 1是前面 4个字符的前缀，明显违反了这一原则，所以不属于哈夫曼编码。 13 【正确答案】 D 【试题解析】 在中序线索二叉树中，查找结点 P的中序后继分为以下两种情况。 (1)若结点 P的右子树为空，则直接得到中序后继。 (
27、2)若结点 P的右子树非空，则中序后继是 P的右子树中最左下的结点。 在中序线索二叉树中，查找结点 P的中序前驱也有两种情况。 (1)若结点 P的左子树为空，则直接得 到中序前驱。 (2)若结点 P的左子树非空，则中序前驱是 P的左子树中最右下的结点。 因此，在中序线索二叉树中，查找中序前驱和中序后继都可以有效解决。 在先序线索二叉树中，查找结点先序后继很简单，仅从 P出发就可以找到，但是找其先序前驱必须要知道 P的双亲结点。 在后序线索二叉树中，仅从 P出发就可以找到结点后序前驱，但是找其后序后继也必须要知道 P的双亲结点。 14 【正确答案】 D 【试题解析】 平衡二叉树的构造过程如图 1
28、-5所示。 根据题中要求，首次出现最小不平衡子树的根就是 75。 15 【正确答案】 B 【试题解析】 因为 G为非连通图，所以 G中至少含有两个连通子图，而且该图不含有回路和多重边。题目问的是至少有多少个顶点，因此一个连通图可看成是只有 1个顶点，另一个连通图可看成是一个完全图 (因为完全图在最少顶点的情况下能得到的边数最多 )，这样，该问题就转化为 “36条边的完全图有多少个顶点 ”，因为具有 n个顶点的无向完全图的边的条数为 n(n1) 2，可以算出 n=9满足条件。再加上另一个连通图 (只有一个点 )，则图 G至少有 10个顶点。 16 【正确答案】 A 【试题解析】 在图 1一 1中
29、，其拓扑排序序列有如下规定： A必须是序列的第一个元素， E必须是序列的最后一个元素， D必须是序列的倒数第二个元素。即序列形如 A*DE，其中 “*”为 B或 C，所以共两种拓扑排序序列。 17 【正确答案】 A 【试题解析】 对于这个题目，可以这样理解，题目要求按行优先，其含义就是存储第一行后，开始存储第二行，然后再存储第三行的非 0元素，依次类推。这样可以发现了一个规律，第 1行只有一个元素，第二行 2个元素，第三行 3个元素，第 n行 n个元素。 显然，这个规律是一个递增数 列。那么元素 Ai， j是第几行第几列就变得明显了。由于下标是从 0开始的 (这个要特别注意 )，那么下标为 f
30、的应该就是第汁 1行，因此在存储下标为 i的这行之前，应该存放了 i行元素，其中第 i行的元素个数为 i个，那么在存放第 i+1行之前，应该存放的元素个数总和为 i(i+1) 2，。那么当存放到第 i+1行时，在存放下标为 j的元素前，同样的道理应该存放了 j个元素，因此在存放元素 Ai,j之前，总共存放了的元素个数总和为 i(i+1) 2+j，因此元素 Ai,j应该是第 i(i+1) 2+j+1个要存放的元素，由于存放的数 组 M是从下标为 1开始的。因此元素 Ai,j存储在数组 M的 Mi+1) 2+j+1中。 18 【正确答案】 D 【试题解析】 此题比较容易，但从历年试题看来，考的几率
31、是比较高的，这里只将一些考生有疑问的地方提出来讲一讲。以前有考生提出疑问： “冒泡排序一趟扫描的结果标准答案为： H， C， Q， P， A， M， S， R， D， F， X， Y。如果按照冒泡排序的基本思想是先比较 An一 1和 An一 2一直到 A0，那么冒泡排序一趟扫描的结果得到应该是： A， Q， H， C， Y， P， D， M， S， R， F， X。 ”考生提出这种 疑问是因为对冒泡排序的规则不清楚。冒泡排序可以先比较 An一 1和An一 2一直到 A0，也可以先比较 A0和 A1一直到 An一 1。 如果先比较 An一 1和 An一 2，详细过程如下： 1 Q， H， C，
32、Y， P， A， M， S， R， D， F， X F和 X比较， FD，所以交换 R和 D； 4 Q， H， C， Y， P， A， M， D， S， R， F， X S和 D比较， SD，所以交换 S和 D； 5 Q， H， C， Y， P， A， D， M， S， R， F， X M和 D比较， MD，所以交换 M和 D； 6 Q， H， C， Y， P， A， D， M， S， R， F， X A和 D比较， AA，所以交换 P和 A； 8 Q， H， C， A， Y， P， D， M， S， R， F， X Y和 A比较， YA，所以交换 Y和 A； 9 Q， H， A， C， Y，
33、 P， D， M， S， R， F， X C和 A比较， CA，所以交换 C和 A； 10 Q， A， H， C， Y， P， D， M， S， R， F， X H和 A比较， HA，所以交换 H和 A； 11 A， Q， H， C， Y， P， D， M， S， R， F， X Q和 A比较， QA，所以交换 Q和 A。 用同样的方法可以推出标准答案 H， C， Q， P， A， M， S， R， D， F， x， Y也是正确的。所以答案选 D。 19 【正确答案】 A 【试题解析】 插入排序的基本思想是逐个将待排序元素插入到已排序的有序表中。用插入排序对数组 进行排序的过程为： 原元素序列
34、： 监视哨 (3)， 1， 4， 1， 5， 9， 6， 5 第一趟排序： 3(1， 3)， 4， 1， 5， 9， 6， 5 3插入时与 l比较 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和
35、5分别比较 1次 第七趟排序： 5(1， 1， 3， 4， 5， 5， 6， 9)5插入时与 9， 6， 5分别比较 1次 因此整个排序过程需要比较的次数为 12次。 归并排序的思想是将两个相邻的有序子序列归并为一个有序序列，然后再将新产生的相邻序列进行归并，当只剩下一个有序序列时算法结束。那么用归并排序对数组 进行排序的过程为： 原元素序列： 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，
36、5， 5， 6， 95分别与 1， 1， 3， 4比较一次 所以整个排序过程需要比较的次数为 14次。 20 【正确答案】 B 【试题解析】 递归算法的执行过程分递推和回归两个阶段。在递推阶段，把较复杂的问题 (规模为 n)的求解推到比原问题简单一些的问题 (规模小于 n)的求解。 在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解。 下面举一个经 典的递归算法例子 斐波那契数列问题来说明这一过程。 斐波那契数列为： 0， 1， 1， 2， 3， ，即 fib(0)=0； fib(1)=1； fib(n)=fib(n一 1)+fib(n一 2) (当 n1时 ) 写成递归函数
37、有： int fib(int n) if (n=0) return 0； if (n=1) return 1； if (n1) return fib(n一 1)+fib(n一 2)； 这个例子的递推过程为：求解 fib(n)，把它推到求解 fib(n一 1)和 fib(n一 2)。也就是说，为计算 fib(n)，必须先计算 fib(n一 1)和 fib(n一 2)，而计算 fib(n一 1)和fib(n一 2)，又必须先计算 fib(n一 3)和 fib(n一 4)。依次类推，直至计算 fib(1)和fib(0)，分别能立即得到结果 1和 0。在递推阶段，必须要有终止递归的情况。例如在函数 f
38、ib(n)中，当 n为 1和 0的情况。 回归过程为：得到 fib(1)和 fib(0)后，返回得到 fib(2)的结果 在得到了 fib(n一1)并 fib(n-2)的结果后，返回得到 fib(n)的结果。 21 【正确答案】 C 【试题解析】 本题考查数据结构的多维数组，是常考的知识点。 以前学过的是二维数组的存储，按 “行 ”或 “列 ”来保存，然后求某元素相对于首地址的偏移量。但这个题目是考查三维数组，更复杂，但是道理是一样的。按 “行 ”序来存，仍是从最后一维开始，再往左到第一维进行变化。题目中数组口的大小为 5行、 4列、 4纵，这里要注意题目给出的下标，则数组元素 a2,2,2的
39、位置处在第 3行、第 3列、第 2纵，求它的偏移 量分两部分，第一部分，前两行的偏移位置是 2*4*4=32；第二部分，在第 3行的偏移位置是 2*4+2=10，但计算偏移位置是本位置之前的大小，所以是 10-1=9。则数组元素 a2,2,2在其存储空间中相对basea的偏移量是 32+9=41， C选项正确。 22 【正确答案】 B 【试题解析】 假设 n0为度为 0的结点总数 (即叶子结点数 )， n1为度为 1的结点总数， n2为度为 2的结点总数，由二叉树的性质可知 n=n0+n1+n2 (1) 其中 n为完全二叉树的结点总数。又根据二叉树的定义，有 n=n1+2n2+1 (2) 由公
40、式 (1)和 (2)可得 n2=n0 1 (3) 把 (3)式代入 (1)式，可得 n=2n0+n1一 1 (4) 根据本题的条件，有967=2n0+n1一 1，即 968-n1=2n0。现在只需确定 n1就能求得 n0了。根据完全二叉树的定义，一棵 K层的完全二叉树，上面的 K 1层为满二叉树，最后一层的结点都靠左边，又因为满二叉树中只有度为 0和度为 2的结点，没有度为 1的结点，这也就意味着在完全二叉树中，只有倒数第二层，才可能有度为 1的结点，这就限制了完全二叉树只可能有 0个或 1个度为 1的结点，对于 968 n1=2n0， n1显然为 0，所以 n0=968 2=484。 23
41、【正确答案】 C 【试题解析】 其实这种题目在考场上最好的解题方法是找一个实际的例子，往里面一套便知道了。下面解释一下原理。因为 rear表示的是队列尾元素的实际位置(注意，不是队尾指针 )。而且题中有 “移动按 rear=-(rear +1)mod m进行 ”，这说明：队列存放元素的顺序为： Q1， Q2， ， Qm一 1， Q0。所以在理想情况下 rear-length+1能算出队首元素的位置，即当 m=8， rear=5， length=2时，rear-length+1=4， 4就是正确的队首元素实际位置。但 rear-length+1有一种情况无法处理，即当 m=8， rear=1，
42、length=5时，无法算出。 所以在 rear+1length的基础上加上 m再与 m求模，以此方法来计算。 24 【正确答案】 C 【试题解析】 哈夫曼首先给出了对于给定的叶子数目及其权值构造最优二叉树的方法，根据这种方法构造出来的二叉树称为哈夫曼树。具体过程如下所述。 假设有 n个权值，则构造出的哈夫曼树有 n个叶子结点。 n个权值分别设为 w1，w2， ， wn，则哈夫 曼树的构造规则如下。 (1)将 w1， w2， ， wn看成是有 n棵树的森林 (每棵树仅有一个结点 )。 (2)在森林中选出两个根结点的权值最小的树，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权
43、值之和。 (3)从森林中删除选取的两棵树，并将新树加入森林。 (4)重复第 (2)和第 (3)步，直到森林中只剩一棵树为止，该树即为所求的哈夫曼树。 从以上构造过程可知，哈夫曼树是严格的二叉树，没有度数为 1的分支结点。设二叉树的 0度结点(即叶子结点 )个数为 n0， 2度结点个数为 n2，则树的总结点数 n=n0+n2。又因为二叉树有性质：对任何一棵二叉树，如果其叶子结点数为 n0，度为 2的结点数为n2，则 n0=n2+1。所以 n=n2+1+n2。即 13=n2+1+n2， n2=6， n0=7。 25 【正确答案】 B 【试题解析】 广义表记做 LS=(a1， a2， ， an)其中
44、 LS是广义表名， n是它的长度，所以本表的长度为 2。而广义表中嵌套括号的层数为其深度，所以 L深度为2。 26 【正确答案】 D 【试题解析】 此题要求根据二叉树的先序遍历和中序遍历求后序遍历。可以根据这棵二叉树的先序和中序遍历画出这棵二叉树。根据 先序和中序来构造二叉树的规则是这样的：首先看先序，先序遍历中第一个访问的结点是 A，这说明 A是二叉树的根结点 (因为先序遍历顺序是：根、左、右 )。然后看中序，中序中 A前面有结点 D， B， E，后面有结点 F， C。这说明 D， B， E是 A的左子树， F， C是 A的右子树。再回到先序遍历中看 D， B， E的排列顺序 (此时可以不看
45、其他结点 )，发现在先序中 B排在最前，所以 B是 A左子树的根结点。接下来又回到了中序，中序中 D在 B前面， E在 B后面，所以 D是 B的左子树， E是 B的右子树。依此规则可构造二叉树，如图 1 6所示。然后对这棵二叉树进行后 序遍历得到DEBFCA。 27 【正确答案】 C 【试题解析】 要计算散列表上的平均查找长度，首先必须知道在建立这个散列表时，每个数据存储时进行了几次散列。这样就知道哪一个元素的查找长度是多少。散列表的填表过程如下：首先存入第 1个元素 38，由于 h(38)=38 7=3，又因为 3号单元现在没有数据，所以把 38存入 3号单元，如图 1-7所示。 接着存入第
46、 2个元素 25，由于 h(25)=25 7=4，又因为 4号单元现在没有数据，所以把25存入 4号单元，如图 1-8所示。 接着存入第 3个元素 74，由于 h(74)=747=4，此时的 4号单元已经被 25占据，所以进行线性再散列，线性再散列的公式为： Hi=(H(key) m，其中的 di=1， 2， 3， 4， ，所以 H1=(4+1) 7=5，此时的单元 5没有存数据，所以把 74存入到 5号单元，如图 1-9所示。 接着存入第4个元素 63，由于 h(63)=63 7=0，此时的 0号单元没有数据，所以把 63存入 0号单元，如图 1-10所示。 接着存入第 5个元素 52，由于
47、 h(52)=52 7=3，此时的 3号单元已被 38占据，所以进行线性再散列 H1=(3+1) 7=4，但 4号单元也被占据了，所 以再次散列 H2=(3+2) 7=5，但 5号单元也被占据了，所以再次散列H3=(3+3) 7=6， 6号单元为空，所以把 52存入 6号单元，如图 1-11所示。最后存入第 6个元素 48，由于 h(48)=48 7=6，此时的 6号单元已被占据，所以进行线性再散列 H1=(6+1) 7=0，但 0号单元也被占据了，所以再次散列 H2=(6+2)7=1， 1号单元为空，所以把 48存入 1号单元，如图 1-12所示。 如果一个元素存入时，进行了 N次散列，相应
48、的查找次数也是 N，所以 38， 25， 63这三个元素的查找长度为 1， 74的查找长度 为 2， 48的查找长度为 3， 52的查找长度为 4。平均查找长度为 (1+1+1+2+3+4) 6=2。 28 【正确答案】 B 【试题解析】 递推关系式 T(n)=2T(n 2)n其实是在给 n个元素进行快速排序时最好情况 (每次分割都恰好将记录分为两个长度相等的子序列 )下的时间递推关系式，其中 T(n 2)是一个子表需要的处理时间， n为当次分割需要的时间。注意，这里实际上是用比较次数来度量时间。可以对此表达式进行变形得 用 n 2代替上式中的 n可得 继续用 n 2代替上式中的 n可得 算法
49、共需要进行 1bn+1次分割 (n个元素的序列的对半分割树的高度跟具有 n个结点的完全二叉树高度相等，软设级别的只需知道即可，不必深究 )，将上述 1bn+1个式子相加，删除相互抵消的部分得 而 T(1)=1，那么上式可转化为 T(n)=n1bn+2n而在求时间复杂度时关注 “大头 ”，注意到 O(n) 29 【正确答案】 C 【试题解析】 分治法：对于一个规模为 n的问题，若该问题可以容易地解决 (如说规模 n较小 )则直接解决；否则将其分解为 k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解 合并得到原问题的解。 动态规划法：这种算法也用到了分治思想，它的做法是将问题实例分解为更小、
