A. bbaa B. aabb C. abab D. baba 答案： B
32、表示\以字符a开头且仅由字符 a、b 构成的所有字符串\的正规式为（ ）。 A. a*b* B. (alb)*a C. a(alb)* D. (ab)* 答案： C
33、在单入口单出口的do...while循环结构（ ）。 A. 循环体的执行次数等于循环条件的判断次数 B. 循环体的执行次数多于循环条件的判断次数 C. 循环体的执行次数少于循环条件的判断次数 D. 循环体的执行次数与循环条件的判断次数无关 答案： A
do??while为先执行后判断，执行次数和判断次数相等
34、将源程序中多处使用的同一个常数定义为常量并命名，（ ）。 A. 提高了编译效率 B. 缩短了源程序长度
C. 提高了源程序的可维护性 D. 提高了程序的运行效率 答案： C
本题考查程序语言基础知识。编写源程序时，将程序中多处引用的常数定义为一个符号常量可以简化对此常数的修改操作(只需改一次)，并提高程序的可读性，以便于理解和维护。
35、递归函数执行时，需要（ ）来提供支持。 A. 栈 B. 队列 C. 有向图 D. 二叉树
答案： A
在递归调用中，需要在前期存储某些数据，并在后面又以存储的逆序恢复这些数据，以提供之后使用的需求，因此，需要用到栈来实现递归。简单的说，就是在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段，位于栈顶的局部变量、参数值和返回地址被弹出，用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态
36、函数main()、f()的定义如下所示。调用函数f()时，第一个参数采用传值 (call by value) 方式，第二个参数采用传引用 (call by reference )方式，main()执行后输出的值为（ ）。
A. 2 B. 4 C. 5 D. 8 答案： D
37、对于初始为空的栈S，入栈序列为a、b、c、d，且每个元素进栈、出栈各1次。若出栈的第一元素为d，则合法的出栈序列为（ ）。 A. d c b a B. d a b c C. d c a b D. d b c a 答案： A
38、对关键码序列（9，12，15，20，24，29，56，69，87）进行二分查找（折半查找），若要查找关键码15；则需依次与（ ）进行比较。 A. 87、29、15 B. 9、12、15 C. 24、12、15 D. 24、20、15 答案： C
二分法查找（折半查找）的基本思想是：（设R[low,?,high]是当前的查找区) （1）确定该区间的中点位置：mid=[(low+high)/2]；
（2）将待查的k值与R[mid].key比较，若相等，则查找成功并返回此位置，否则需确定新的查找区间，继续二分查找，具体方法如下。
若R[mid].key＞k，则由表的有序性可知R[mid,?,n].key均大于k，因此若表中存在关键字等于k的结点，则该结点必定是在位置mid左边的子表R[low,?,mid–1]中。因此，新的查找区间是左子表R[low,?,high]，其中high=mid–1。
若R[mid].key （3）下一次查找是针对新的查找区间进行，重复步骤（1）和（2）。 （4）在查找过程中，low逐步增加，而high逐步减少。如果high 39、对关键码序列（12，24，15，56，20，87，69，9）采用散列法进行存储和查找，并设散列函数为H(Key)=Key(%表示整除取余运算)。采用线性探查法（顺序地探查可用存储单元）解决冲突所构造的散列表为（ ）。 A. B. C. D. 答案： B 散列函数为H(Key)=KeyMOD11(MOD表示整除取余运算),因此只需要对线性表类数据分别与7进行取余运算。 12，24，15，56，20，87，69，9与11取余分别得到：1，2，4，1，9，10，3，9，按照序列依次存储到相应位置，若出现冲突则往后顺延 40、对下图所示的二叉树进行中序遍历（左子树，根结点，右子树）的结果是（ ）。 A. 5 2 3 4 6 1 B. 2 5 3 4 1 6 C. 2 4 6 5 3 1 D. 2 5 4 3 6 1 答案： D 前序遍历：先遍历根结点，然后遍历左子树，最后遍历右子树。 中序遍历：先遍历左子树，然后遍历根结点，最后遍历右子树。 后序遍历：先遍历左子树，然后遍历右子树，最后遍历根节点。 层序遍历：从上往下逐层遍历 41、对于下面的有向图，其邻接矩阵是一个（41）的矩阵, 采用邻接链表存储时，顶点0的表结点个数为 2，顶点3的表结点个数为0，顶点1的表结点个数为（42）。 A. 3X4 B. 4X3 C. 6X6 D. 7X7 答案： D 42、A. 0 B. 1 C. 2 D. 3 答案： C 43、对n个关键码构成的序列采用直接插入排序法进行升序排序的过程是：在插入第i个关键码Ki时，其前面的i-1个关键码己排好序，因此令Ki与Ki-1、Ki-2、...，依次比较，最多到K1为止，找到插入位置并移动相关元素后将Ki插入有序子序