1、(A)二级公共基础知识(一)及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：46，分数：100.00)1.在链表结构中，采用_可以用最少的空间代价和最高的时间效率实现队列结构。A仅设置尾指针的单向循环链表 B仅设置头指针的单向循环链表C仅设置尾指针的双向链表 D仅设置头指针的双向链表（分数：2.00）A.B.C.D.2.若需将一个栈 S 中的元素逆置，则以下处理方式中正确的是_。A将栈 S 中的元素依次出栈并入栈 T，然后栈 T 中的元素依次出栈并进入栈 SB将栈 S 中的元素依次出栈并入队，然后使该队列的元素依次出队并进入栈 SC直接交换栈顶元素和栈底元素D直接
2、交换栈顶指针和栈底指针（分数：2.00）A.B.C.D.3.已知 N 个数已存入数组 A1M的前 N 个元素中(NM)，为在 Ai(1iN)之前插入一个新数，应先_，以挪出一个空闲位置插入该数。A从 Ai开始直到 A1，每个数向后移动一个位置B从 A1开始直到 Ai，每个数向后移动一个位置C从 Ai开始直到 AN，每个数向前移动一个位置D从 AN开始直到 Ai，每个数间后移动一个位置（分数：2.00）A.B.C.D.4.在以下情形中，_适合于采用队列数据结构。A监视一个火车票售票窗口等待服务的客户B描述一个组织中的管理机构C统计一个商场中的顾客数D监视进入某住宅楼的访客（分数：2.00）A.B
3、.C.D.5.将元素 3、1、2 依次全部进入一个栈后，然后陆续执行出栈操作，得到的出栈序列为_。A3、2、1 B3、1、2 C1、2、3 D2、1、3（分数：2.00）A.B.C.D.6.若 push、pop 分别表示入栈、出栈操作，初始栈为空且元素 1、2、3 依次进栈，则经过操作序列push、push、pop、pop、push、pop 之后，得到的出栈序列为_。A321 B213 C231 D123（分数：2.00）A.B.C.D.7.若 in、out 分别表示入队、出队操作，初始队列为空且元素 a、b、c 依次入队，则经过操作序列in、in、out、out、in、out 之后，得到的出
4、队序列为_。Acba Bbac Cbca Dabc（分数：2.00）A.B.C.D.8.数据结构主要研究数据的_。A逻辑结构 B存储结构C逻辑结构和存储结构 D逻辑结构和存储结构及其运算的实现（分数：2.00）A.B.C.D.9.PUSH 和 POP 命令常用于_操作。A队列 B数组 C栈 D记录（分数：2.00）A.B.C.D.10.数组是一种数据结构，对数组通常进行的两种基本操作是_。A插入和删除 B插入和赋值 C查找和修改 D查找和删除（分数：2.00）A.B.C.D.11.堆栈操作中，_保持不变。A堆栈的顶 B堆栈中的数据 C堆栈指针 D堆栈的底（分数：2.00）A.B.C.D.12.
5、字符串是一种线性表，其特殊性表现在_。A它的数据元素是一个字符 B它可以链式存储C它可以顺序存储 D它的数据元素可以是多个字符（分数：2.00）A.B.C.D.13.链表不具备的特点是_。A可随机访问任何一个元素 B插入、删除操作不需要引动元素C无须事先估计存储空间的大小 D所需存储空间与线性表长度成正比（分数：2.00）A.B.C.D.14.判断“链式队列为空”的条件是_(front 为头指针，rear 为尾指针)。Afront=NULL Brear=NULL Cfront=rear Dfront!=rear（分数：2.00）A.B.C.D.15.在程序的执行过程中，用_结构可以实现嵌套调用
6、函数的正确返回。A队列 B栈 C树 D图（分数：2.00）A.B.C.D.16._是线性结构的数据结构。A列表 B高维数组 C双端队列 D二叉树（分数：2.00）A.B.C.D.17.某线性表最常用的运算是插入和删除。插入运算是指在表尾插入一个新元素，删除运算是指删除表头第一个元素。那么采用_存储方式最节省运算时间。A仅有尾指针的单向循环链表 B仅有头指针的单向循环链表C单向链表 D双向链表（分数：2.00）A.B.C.D.18.若某二叉树的先序遍历序列和中序遍历序列分别为 PBECD、BEPCD，则该二叉树的后序遍历序列为_。APBCDE BDECBP CEBDCP DEBPDC（分数：2.
7、00）A.B.C.D.19.一棵二叉树如图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点(根结点的下标为 1，若某结点的下标为 i，则其左孩子位于下标 2i 处，右孩子位于下标 2i+1 处)，则该数组的大小至少为_。（分数：2.00）A.B.C.D.20.如果根的层次为 1，具有 61 个结点的完全二叉树的高度为_。A5 B6 C7 D8（分数：2.00）A.B.C.D.21.在一颗非空二叉树中，叶子结点的总数比度为 2 的结点总数多_个。A-1 B0 C1 D2（分数：2.00）A.B.C.D.22.在具有 100 个结点的树中，其边的数目为_。A101 B100 C99
8、D98（分数：2.00）A.B.C.D.23.前序遍历序列与中序遍历序列相同的二叉树为_。A根结点无左子树的二叉树B根结点无右子树的二叉树C只有根结点的二叉树或非叶子结点只有左子树的二叉树D只有根结点的二叉树或非叶子结点只有右子树的二叉树（分数：2.00）A.B.C.D.24.假设一棵二叉树的后序遍历序列为 DGJHEBIFCA，中序遍历序列为 DBGEHJACIF，则其前序遍历序列为_。AABCDEFGHIJ BABDEGHJCFI CABDEGHJFIC DABDEGJHCFI（分数：2.00）A.B.C.D.25.设某种二叉树有如下特点：结点的子树数目不是 2 个，则是 0 个。这样的一
9、棵二叉树中有 m(m0)个子树为 0 的结点时，该二叉树上的结点总数为_。A2m+1 B2m-1 C2(m-1) D2(m+1)（分数：2.00）A.B.C.D.26.树是结点的集合，它有_个根结点。A1 且只有 1 B1 或多于 1 C0 或 1 D至少 2（分数：2.00）A.B.C.D.27.确定算法是解决问题的关键步骤之一。算法的计算工作量大小称为计算的_。A实现性 B时间复杂度 C空间复杂度 D困难度（分数：2.00）A.B.C.D.28.堆排序是一种基于_的排序方法。A计数 B插入 C选择 D归并（分数：2.00）A.B.C.D.29.从未排序的序列中依次取出一个元素与已排序序列中
10、的元素进行比较，然后将其放在已排序序列的合适位置上，该排序方法称为_。A插入排序 B选择排序 C希尔排序 D归并排序（分数：2.00）A.B.C.D.30.在第一趟排序之后，一定能把数据表中最大或最小元素放在其最终位置上的排序算法是_。A冒泡排序 B基数排序 C快速排序 D归并排序（分数：2.00）A.B.C.D.31.在排序算法中，两两比较待排序的记录。当发现不满意顺序要求时，变更它们的相对位置，这就是_排序。A插入 B枚举 C交换 D归并（分数：2.00）A.B.C.D.32.每次从未排序的记录中挑出最小(或最大)关键码值的记录，加入已排序记录的末尾，这是_排序。A插入 B枚举 C交换 D
11、选择（分数：2.00）A.B.C.D.33.对具有 n 个元素的有序序列进行二分查找时，_。A查找元素所需的比较次数与元素的位置无关B查找序列中任何一个元素所需要的比较次数不超过log 2(n+1)C元素位置越靠近序列后端，查找该元素所需的比较次数越少D元素位置越靠近序列前端，查找该元素所需的比较次数越少（分数：2.00）A.B.C.D.34.若线性表采用链式存储结构，则适用的查找方法为_。A随机查找 B散列查找 C二分查找 D顺序查找（分数：2.00）A.B.C.D.35.设有 100 个结点，用二分法查找时，最大比较次数是_。A25 B50 C10 D7（分数：2.00）A.B.C.D.3
12、6._语言不是面向对象的程序设计语言。AJava BC+ CSmalltalk DFortran77（分数：2.00）A.B.C.D.37.SQL 是一种_程序设计语言。A过程式 B非过程式 C面向对象 D逻辑程序设计（分数：2.00）A.B.C.D.38.程序设计语言的定义一般包括_几个方面。A语法、语义和语 B语法、语义和语用C语义、语句和语用 D语法、语用和语句（分数：2.00）A.B.C.D.39.所有在函数中定义的变量都称为_。A全局变量 B局部变量 C简单变量 D寄存器变量（分数：2.00）A.B.C.D.40.函数 f、g 的定义如图所示，调用函数 f 时传递给形参 a 的值为
13、1。若采用传值(callby value)的方式调用 g(c)，则函数 f 的返回值为_。（分数：2.00）A.B.C.D.41.函数 f、g 的定义如图所示，调用函数 f 时传递给形参 a 的值为 1。若采用传引(callby reference)的方式调用 g(c)，则函数 f 的返回值为_。（分数：2.00）A.B.C.D.42.结构化程序中的基本结构不包括_。A嵌套 B顺序 C循环 D选择（分数：2.00）A.B.C.D.43.己知 n 为一个正整数，在下面的循环语句中，循环体的重复次数约为_。s=0; i=1;while (in)(i=i*2; s=s+i; )An-1 Bn/2 C
14、(n-1) 2 Dlog 2n（分数：4.00）A.B.C.D.44.若循环体执行的次数为 m，则在 do-while 循环中，循环条件的执行次数为_。Am-1 Bm Cm+1 D2m（分数：4.00）A.B.C.D.45.若循环体执行的次数为 m，则在 while-do 循环中，判断循环条件的次数为_。Am-1 Bm Cm+1 D2m（分数：4.00）A.B.C.D.46.程序语言的语句从功能上大体可分为_两大类。A声明语句和可执行语句 B简单语句和复杂语句C顺序语句和判定语句 D程序语句和注释语句（分数：4.00）A.B.C.D.(A)二级公共基础知识(一)答案解析(总分：100.00，做
15、题时间：90 分钟)一、单项选择题(总题数：46，分数：100.00)1.在链表结构中，采用_可以用最少的空间代价和最高的时间效率实现队列结构。A仅设置尾指针的单向循环链表 B仅设置头指针的单向循环链表C仅设置尾指针的双向链表 D仅设置头指针的双向链表（分数：2.00）A. B.C.D.解析：分析 循环链表和单链表相比，不同之处在于链表中表尾结点中的“指针域”并不是指向 Null，而是指向链表的头结点，这样只要知道表中任何一个结点的地址，就能够遍历表中其他任一结点。因此循环链表每个结点所需的空间和单链表是一样的，和双向链表相比空间代价要小得多。队列只需要在头(通过尾结点可访问)、尾结点(通过尾
16、指针可以获得)进行操作。但如果设置了头指针，那么寻找队尾需要遍历整个队列；而如果设置了尾指针，而可以很快找到头结点，因此设置尾指针的时间效率更高。2.若需将一个栈 S 中的元素逆置，则以下处理方式中正确的是_。A将栈 S 中的元素依次出栈并入栈 T，然后栈 T 中的元素依次出栈并进入栈 SB将栈 S 中的元素依次出栈并入队，然后使该队列的元素依次出队并进入栈 SC直接交换栈顶元素和栈底元素D直接交换栈顶指针和栈底指针（分数：2.00）A.B. C.D.解析：分析 假设栈 S 中有 4 个元素 a、b、c、d，栈顶元素是 d；如果按答案 A 的描述，其操作过程如图所示，操作完毕后，栈 S 的内容
17、并没有发生改变。如果按答案 B 的描述，其操作过程如图所示，操作完毕后，栈 S 的内容刚好完成了逆置。如果按答案 C 的描述，其操作过程如图所示，操作完毕后，栈 S 的栈顶和栈底元素刚好逆置，但其他的元素没有完成逆置。3.已知 N 个数已存入数组 A1M的前 N 个元素中(NM)，为在 Ai(1iN)之前插入一个新数，应先_，以挪出一个空闲位置插入该数。A从 Ai开始直到 A1，每个数向后移动一个位置B从 A1开始直到 Ai，每个数向后移动一个位置C从 Ai开始直到 AN，每个数向前移动一个位置D从 AN开始直到 Ai，每个数间后移动一个位置（分数：2.00）A. B.C.D.解析：分析 数组
18、是一种线性表，采用的是一种顺序存储方式，因此当需要插入一个新元素时，就需要通过移动原有元素挪出位置。根据题意，要在 Ai之前插入新数，则需要将 Ai开始移动，由于 iN，因此后面 N-i 个数也需要顺序向后移动一个位置，即答案 A 是正确的。4.在以下情形中，_适合于采用队列数据结构。A监视一个火车票售票窗口等待服务的客户B描述一个组织中的管理机构C统计一个商场中的顾客数D监视进入某住宅楼的访客（分数：2.00）A. B.C.D.解析：分析 队列数据结构的特点就是先进先出，因此对于火车票售票窗口等待服务这样的现实生活中的队列而言是最合适的。组织中的管理机构是一种层次结构；商场中顾客、住宅楼的访
19、客的进出都是随机的，无法利用队列来模拟，因此都不合适采用队列结构。5.将元素 3、1、2 依次全部进入一个栈后，然后陆续执行出栈操作，得到的出栈序列为_。A3、2、1 B3、1、2 C1、2、3 D2、1、3（分数：2.00）A.B.C.D. 解析：分析 栈是一种先进后出的数据结构，也就是最先入栈的元素将最后出栈，最后入栈的元素将最先出栈，因此出栈序列应该是 2、1、3。6.若 push、pop 分别表示入栈、出栈操作，初始栈为空且元素 1、2、3 依次进栈，则经过操作序列push、push、pop、pop、push、pop 之后，得到的出栈序列为_。A321 B213 C231 D123（分
20、数：2.00）A.B. C.D.解析：分析 根据栈的后进先出原则，不难得出整个操作的结果如图所示。7.若 in、out 分别表示入队、出队操作，初始队列为空且元素 a、b、c 依次入队，则经过操作序列in、in、out、out、in、out 之后，得到的出队序列为_。Acba Bbac Cbca Dabc（分数：2.00）A.B.C.D. 解析：分析 根据队的先进先出原则，不难得出整个操作的结果如图所示。8.数据结构主要研究数据的_。A逻辑结构 B存储结构C逻辑结构和存储结构 D逻辑结构和存储结构及其运算的实现（分数：2.00）A.B.C.D. 解析：分析 数据是信息的载体，是用来描述客观事物
21、属性的数、字符，以及所有能够输入计算机中并能够被程序识别和处理的符号集合。而数据结构则是指数据对象及其相互关系和构造方法。数据结构可以用一个二元组D，R表示。其中 D 是某种数据对象，是数据结构中数据(称为结点)的非空有限集合；R 是该对象中所有数据成员之间的关系的有限集合。数据结构主要研究的是数据的逻辑结构、存储结构以及其运算实现。逻辑结构是指数据结构中结点之间的关系，存储结构则是指其在计算机中的存储形式。9.PUSH 和 POP 命令常用于_操作。A队列 B数组 C栈 D记录（分数：2.00）A.B.C. D.解析：分析 堆栈是另一种特殊的线性表，它限定只能够在一端进行插入和删除运算，这一
22、端称为栈顶，不能够进行插入和删除运算的另一端称为栈底。因此通常称其为“后进先出(LIFO)”线性表。在栈上定义的运算主要有栈初始化、入栈(push)、出栈(pop)、取栈顶(top，只读不出栈)、判断栈是否为空 5 种。栈的用途很广，典型的有表达式计算、递归的实现。与队列类似，栈也可以采用顺序存储(顺序栈)和链式存储(链栈)两种方式。10.数组是一种数据结构，对数组通常进行的两种基本操作是_。A插入和删除 B插入和赋值 C查找和修改 D查找和删除（分数：2.00）A.B.C. D.解析：分析 数组是存储于一个连续存储空间中的相同数据类型的数据元素集合，通过数组元素的下标(位置序号)，就可以找到
23、存放该数组元素的存储地址，从而可以访问该数组元素的值。它通常用于实现顺序表，通常包括查找和修改运算。不过要注意的是，顺序表是一个一维数组，而多维数组则是典型的非线性结构。另外值得说明的是，数组的特点是：1)数组元素的数目固定，一旦定义了数组，就不再有元素的增减变化。2)数据元素具有相同的类型。3)数组的下标关系具有上下界的约束且下标有序。因此，数组一般不做插入和删除操作。11.堆栈操作中，_保持不变。A堆栈的顶 B堆栈中的数据 C堆栈指针 D堆栈的底（分数：2.00）A.B.C.D. 解析：分析 堆栈是另一种特殊的线性表，它限定只能够在一端进行插入和删除运算，这一端称为栈顶，不能够进行插入和删
24、除运算的另一端称为栈底。因此也称其为“后进先出(LIFO)”线性表。从而也不难得出在堆栈操作中，堆栈的底是保持不变的。12.字符串是一种线性表，其特殊性表现在_。A它的数据元素是一个字符 B它可以链式存储C它可以顺序存储 D它的数据元素可以是多个字符（分数：2.00）A. B.C.D.解析：分析 字符串是指以字符为数据元素，采用线性逻辑结构的数据。它是一类重要的、常用的非数值处理对象。可以把它看做是以字符为结点内容的线性表。字符串是由 0 个或多个字符组成的有穷序列，含有 0 个字符的串称为空串，用13.链表不具备的特点是_。A可随机访问任何一个元素 B插入、删除操作不需要引动元素C无须事先估
25、计存储空间的大小 D所需存储空间与线性表长度成正比（分数：2.00）A. B.C.D.解析：分析 链表的插入、删除操作是不需要引动元素的，只需要修改结点的指针，就可以完成这一调整；而由于在链表中新增结点时，可以再动态地申请空间，因此无须事先估计存储空间的大小；链表的每个结点所需的存储空间是一样大的，因此线性表的元素越多，其所需的总存储空间也肯定更多。它们之间是成正比关系的。如果要访问链表中的元素，必须从链表的头进行遍历，寻找要访问的元素，而不像数组那样可以通过指定下标来访问。因此在链表中无法随机访问任何一个元素，这也是链表所不具备的特点。14.判断“链式队列为空”的条件是_(front 为头指
26、针，rear 为尾指针)。Afront=NULL Brear=NULL Cfront=rear Dfront!=rear（分数：2.00）A. B.C.D.解析：分析 链表的第一个结点是队首结点，链表的最后一个结点是队尾结点，队尾结点的指针值为NULL。显然当队首结点的指针值为 NULL(也就是 front=NULL)时，说明队列为空。15.在程序的执行过程中，用_结构可以实现嵌套调用函数的正确返回。A队列 B栈 C树 D图（分数：2.00）A.B. C.D.解析：分析 嵌套调用函数的规则也是先调用的函数后结束，与栈的先进后出规则很匹配，因此最合适的结构显然是栈。16._是线性结构的数据结构。
27、A列表 B高维数组 C双端队列 D二叉树（分数：2.00）A.B.C. D.解析：分析 线性表是用来表示数据对象之间的线性结构。通俗地说，线性结构就是指所有结点是按“一个接着一个排列”的方式相互关联而组成一个整体。数组是存储于一个连续存储空间中的相同数据类型的数据元素集合。通过数组元素的下标(位置序号)，就可以找到存放该数组元素的存储地址，从而可以访问该数组元素的值。它通常用于实现顺序表，通常包括查找和修改运算。不过要注意的是，顺序表是一个一维数组，而多维数组则是典型的非线性结构。二叉树显然不是线性结构，而列表不是数据结构。因此只有双端队列属于线性结构的数据结构。17.某线性表最常用的运算是插
28、入和删除。插入运算是指在表尾插入一个新元素，删除运算是指删除表头第一个元素。那么采用_存储方式最节省运算时间。A仅有尾指针的单向循环链表 B仅有头指针的单向循环链表C单向链表 D双向链表（分数：2.00）A. B.C.D.解析：分析 由于题目中需要使插入和删除的时间最节省，这就需要有头指针和尾指针，因而比较合适的就是单向循环链表。而由于在循环链表中，尾结点的指针域将指向头结点，因此只要有尾指针，就可以很快定位头结点。而只有头指针，是不能够很快定义尾结点的，因此最省时间的存储方式显然是“仅有尾指针的单向循环链表”。18.若某二叉树的先序遍历序列和中序遍历序列分别为 PBECD、BEPCD，则该二
29、叉树的后序遍历序列为_。APBCDE BDECBP CEBDCP DEBPDC（分数：2.00）A.B.C. D.解析：分析 先序遍历的顺序是“根左右”，中序遍历是“左根右”。从先序遍历 PBECD 中可知 P 是根，再结合中序遍历可知 BE 是左子树，CD 是右子树。从先序遍历中可知左子树中 B 是根，再结合中序遍历可知 E 是右子结点。同时可知 C 是右子树中的根，D是 C 的右子结点。基于以上的分析结果，可以绘制出该树，如图所示。有了该图，根据后序遍历的规则不难得知其遍历顺序应该是 EBDCP。19.一棵二叉树如图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点(根结点的下
30、标为 1，若某结点的下标为 i，则其左孩子位于下标 2i 处，右孩子位于下标 2i+1 处)，则该数组的大小至少为_。（分数：2.00）A.B.C.D. 解析：分析 根据题意，可以得知该二叉树各个结点存储的位置如图所示，即该数组的大小至少应该是15。20.如果根的层次为 1，具有 61 个结点的完全二叉树的高度为_。A5 B6 C7 D8（分数：2.00）A.B. C.D.解析：分析 根据二叉树的性质，具有 n 个结点的完全二叉树的深度为log 2n(m运算是表示大于等于m 的整数)，因此含有 61 个结点的完全二叉树的高度为log 261，即应该为 6 层。21.在一颗非空二叉树中，叶子结点
31、的总数比度为 2 的结点总数多_个。A-1 B0 C1 D2（分数：2.00）A.B.C. D.解析：分析 用 n0表示度为 0(叶子结点)的结点总数，用 n1表示度为 1 的结点总数，n 2为度为 2 的结点总数，n 表示整个完全二叉树的结点总数。显然，n=n 0+n1+2，根据二叉树和树的性质，还可得到n=n1+2*n2+1(所有结点的度数之和+1=结点总数)。根据这两个公式，可得知：n 0+n1+n2=n1+2*n2+1=n，不难推出 n2=n0-1，将这个方程式代入公式 n=n0+n1+n2，可得到：n=2n 0+n1-1。22.在具有 100 个结点的树中，其边的数目为_。A101
32、B100 C99 D98（分数：2.00）A.B.C. D.解析：分析 这道题实际上是很简单的，在一根树中，除了根结点之外，每一个结点都有一条入边，因此总边数应该是 100-1，即 99 条。23.前序遍历序列与中序遍历序列相同的二叉树为_。A根结点无左子树的二叉树B根结点无右子树的二叉树C只有根结点的二叉树或非叶子结点只有左子树的二叉树D只有根结点的二叉树或非叶子结点只有右子树的二叉树（分数：2.00）A.B.C.D. 解析：分析 前序遍历的顺序是“根、左、右”，中序遍历的顺序为“左、根、右”，只有所有的子树都没有左子树，即“只有根结点的二叉树或非叶子结点只有右子树的二叉树”时，其前序遍历和
33、中序遍历的结果才相同。24.假设一棵二叉树的后序遍历序列为 DGJHEBIFCA，中序遍历序列为 DBGEHJACIF，则其前序遍历序列为_。AABCDEFGHIJ BABDEGHJCFI CABDEGHJFIC DABDEGJHCFI（分数：2.00）A.B. C.D.解析：分析 根据前序、后序遍历的特点，可以确定 A 是根结点(在后序遍历的最后一个)，再根据中序遍历的特点，可以知道 DBGEHJ 为左子树，CIF 为右子树。再看右子树的后序遍历为 IFC，可以确定 C 为右子树的根结点；再加上中序为 CIF，说明 C 无左子树，只有右子树。而左子树的后序遍历为 DGJHEB，因此 B 为左
34、子树的根结点，再结合中序遍历，可以得知 B 的左子树只有D，GEHJ 都是右子树。GEHJ 子树的后序遍历是 GJHE，说明 E 是根，HJ 为 E 的右子树，G 是 E 的左子树。最后可知 H 为 HJ 子树的根，J 为右子树。通过以上分析，可以绘制出这棵树，如图所示。25.设某种二叉树有如下特点：结点的子树数目不是 2 个，则是 0 个。这样的一棵二叉树中有 m(m0)个子树为 0 的结点时，该二叉树上的结点总数为_。A2m+1 B2m-1 C2(m-1) D2(m+1)（分数：2.00）A.B. C.D.解析：分析 m 个子树为 0 的结点，说明是 m 个叶子结点。而二叉树中子树数目为
35、2 的结点的数量应该是叶子结点数-1，因此就有 m-1 个。这样就可以得到结点总数为 m+m-1=2m-1。26.树是结点的集合，它有_个根结点。A1 且只有 1 B1 或多于 1 C0 或 1 D至少 2（分数：2.00）A. B.C.D.解析：分析 树有且只有一个根结点。27.确定算法是解决问题的关键步骤之一。算法的计算工作量大小称为计算的_。A实现性 B时间复杂度 C空间复杂度 D困难度（分数：2.00）A.B. C.D.解析：分析 算法复杂性包括两个方面：一个是算法效率的度量(时间复杂度)；一个是算法运行所需要的计算机资源量的度量(空间复杂度)，这也是评价算法优劣的重要依据。1)时间复
36、杂度。一个程序的时间复杂度是指程序运行从开始到结束所需要的时间。通常分析时间复杂度的方法是从算法中选取一种对于所研究的问题来说是基本运算的操作，以该操作重复执行的次数作为算法的时间度量。通常，算法中原操作重复执行的次数是规模 n 的某个函数 T(n)。由于许多情况下要精确计算T(n)是困难的，因此引入了渐进时间复杂度在数量上估计一个算法的执行时间。2)空间复杂度。一个程序的空间复杂度是指程序运行从开始到结束所需的存储量。它通常包括固定部分和可变部分两个部分。在算法的分析与设计中，经常会发现时间复杂度和空间复杂度之间有着微妙的关系，经常可以相互转换，也就是可以利用空间来换时间，也可以用时间来换空
37、间。28.堆排序是一种基于_的排序方法。A计数 B插入 C选择 D归并（分数：2.00）A.B.C. D.解析：分析 堆排序是利用堆这一特殊的树形结构进行的选择排序，它有效地改进了直接选择排序，提高了算法的效率。堆排序的整个过程是：构造初始堆，将堆的根结点和最后一个结点交换，重新调整成堆，再交换，再调整，直到完成排序。29.从未排序的序列中依次取出一个元素与已排序序列中的元素进行比较，然后将其放在已排序序列的合适位置上，该排序方法称为_。A插入排序 B选择排序 C希尔排序 D归并排序（分数：2.00）A. B.C.D.解析：分析 从未排序的序列中每次取出一个元素与已排序的元素比较，然后将其放在
38、已排序序列中的合适位置，这种方法是直接插入排序。30.在第一趟排序之后，一定能把数据表中最大或最小元素放在其最终位置上的排序算法是_。A冒泡排序 B基数排序 C快速排序 D归并排序（分数：2.00）A. B.C.D.解析：分析 冒泡排序的基本思想是，通过相邻元素之间的比较和交换，将排序码较小的元素逐渐从底部移向顶部。由于整个排序的过程就像水底下的气泡一样逐渐向上冒，因此称为冒泡算法。整个冒泡排序过程为：首先将 An-1和 An-2元素进行比较，如果 An-2An-1，则交换位置，使小的元素上浮，大的元素下沉；当完成一趟排序后，A0就成为最小的元素；然后就从 An-1A1之间进行排序。31.在排
39、序算法中，两两比较待排序的记录。当发现不满意顺序要求时，变更它们的相对位置，这就是_排序。A插入 B枚举 C交换 D归并（分数：2.00）A.B.C. D.解析：分析 交换排序的基本思想是：两两比较待排序记录的排序码，并交换不满足顺序要求的那些偶对，直到满足条件为止。交换排序的典型方法包括冒泡排序和快速排序。32.每次从未排序的记录中挑出最小(或最大)关键码值的记录，加入已排序记录的末尾，这是_排序。A插入 B枚举 C交换 D选择（分数：2.00）A.B.C.D. 解析：分析 选择排序的基本思想是每一步都从待排序的记录中选出排序码最小的记录，顺序存放在已排序的记录序列的后面。常见的选择排序有直
40、接选择排序和堆排序两种。33.对具有 n 个元素的有序序列进行二分查找时，_。A查找元素所需的比较次数与元素的位置无关B查找序列中任何一个元素所需要的比较次数不超过log 2(n+1)C元素位置越靠近序列后端，查找该元素所需的比较次数越少D元素位置越靠近序列前端，查找该元素所需的比较次数越少（分数：2.00）A.B. C.D.解析：分析 二分查找法又称为折半查找法，它是一种效率较高的查找方法。其基本思想是：首先确定查找区间的中点位置；然后将中点位置的值与要查找的值相比较，如果相等则返回，如果不等，则根据其大小关系决定是在前一区域还是后一区域，然后再次进行查询。因此“查找序列中任何一个元素所需要
41、的比较次数不超过log 2(n+1)”是显然的。而查找时所需的比较次数实际上是位置没有绝对关系。34.若线性表采用链式存储结构，则适用的查找方法为_。A随机查找 B散列查找 C二分查找 D顺序查找（分数：2.00）A.B.C.D. 解析：分析 随机查找是无规则查找，而链式存储对元素随机访问的支持不好，因此不适用。散列查找是根据关键码(查找码)与表项存储位置的映射关系，进行高效、精确的查找，因此也需要采用顺序结构存储。二分查找法又称为折半查找法，它是一种效率较高的查找方法，并且要求表按关键字排序，并使用顺序结构存储。顺序查找就是从表的一端开始，顺序扫描线性表，依次将扫描得到的结点关键字和给定值
42、k 相比较，如果相等，则表示查找成功，如果扫描到最后还没有找到相等的结点，则查找失败。因此对于链式存储结构是最合适的方法。35.设有 100 个结点，用二分法查找时，最大比较次数是_。A25 B50 C10 D7（分数：2.00）A.B.C.D. 解析：分析 二分法查找最大的比较次数应为 log2(n+1)，因此应为 7 次。36._语言不是面向对象的程序设计语言。AJava BC+ CSmalltalk DFortran77（分数：2.00）A.B.C.D. 解析：分析 Java 是一个纯面向对象的语言；C+是在 C 语言的基础上发展起来的，主要增加了类的功能，使其成为面向对象的程序设计语言
43、；Smalltalk 是最早的面向对象的语言；Fortran 是第一个广泛应用于科学计算的高级语言，其程序是由一个主程序和若干子程序组成的，Fortran 77 是 Fortran 的一个版本。37.SQL 是一种_程序设计语言。A过程式 B非过程式 C面向对象 D逻辑程序设计（分数：2.00）A.B. C.D.解析：分析 SQL 是关系数据库的标准查询语言，是一种介于关系代数与关系演算之间的非过程化语言，属于描述性(说明性)语言。当进行数据操作时，只要指出“做什么”，无须指出“怎么做”，存储路径对用户来说是透明的，提高了数据的独立性。38.程序设计语言的定义一般包括_几个方面。A语法、语义和
44、语 B语法、语义和语用C语义、语句和语用 D语法、语用和语句（分数：2.00）A.B. C.D.解析：分析 软件语言是用于书写计算机软件的语言。程序设计语言的定义一般包括语法、语义和语用3 个方面。39.所有在函数中定义的变量都称为_。A全局变量 B局部变量 C简单变量 D寄存器变量（分数：2.00）A.B. C.D.解析：分析 在函数中定义的变量，其作用域就是在该函数内，因此属于局部变量；全局变量需要定义在文件头中。40.函数 f、g 的定义如图所示，调用函数 f 时传递给形参 a 的值为 1。若采用传值(callby value)的方式调用 g(c)，则函数 f 的返回值为_。（分数：2.
45、00）A.B.C.D. 解析：分析 传值调用是指把实参的值传递给相应的形参，子程序不能通过这种方式传回任何结果。首先根据函数 f 的定义，可知在调用 g(c)之前将执行 int c=a+1，根据题意，a 的值为 1，因此在调用之前，c 的值应为 2。如果以传值调用的方式传递信息，那么，g(c)函数的执行并不会对变量 c 的值产生影响，因此 c 的值仍然是 2，最后函数 f 返回 a+c 时，其值就应该是 3。41.函数 f、g 的定义如图所示，调用函数 f 时传递给形参 a 的值为 1。若采用传引(callby reference)的方式调用 g(c)，则函数 f 的返回值为_。（分数：2.0
46、0）A.B.C. D.解析：分析 引用调用是指把实参的地址传递给相应的形参，此时子程序对形参的一次引用或赋值都是对形参的间接访问。首先根据函数 f 的定义，可知在调用 g(c)之前先执行 int c=a+1，根据题意，a 的值为 1，因此在调用之前，c 的值应为 2。如果以引用调用的方式传递信息，那么，执行语句 x=b*b；b=x/2+b 之后，b=4，而该值将影响变量 c 的值，因此在 g(c)执行完后，c 的值就成了 4，最后函数 f 返回 a+c 时，其值就应该是 5。42.结构化程序中的基本结构不包括_。A嵌套 B顺序 C循环 D选择（分数：2.00）A. B.C.D.解析：分析 顺序、分支(也称为选择)和循环是结构化程序中的三大基本结构。其中 if、switch-case语句是分支结构的代表，for、while、do-while 则是循环结构的代表。43.己知 n 为一个正整数，在下面的循环语句中，循环体的重复次数约为_。s=0; i=1;while (in)(i=i*2; s=s+i; )An-1 Bn/2 C(n-1) 2 Dlog 2n（分数：4.00）A.B.C.D. 解析：分析
