1、综合模拟试卷 20 及答案与解析一、单项选择题1 某算法的时间复杂度为 0(n2)，表明该算法的( ) 。（A）问题规模是 n2（B）执行时间等于 n2（C）执行时间与 n2 成正比（D）问题规模与 n2 成正比2 设线性表有 n 个元素，以下操作中，( )在顺序表上实现比在链表上实现效率更高。（A）输出第 i(1in)个元素值（B）交换第 1 个元素与第 2 个元素的值（C）顺序输出这 n 个元素的值（D）输出与给定值 x 相等的元素在线性表中的序号3 设 n 个元素进栈序列是 1，2，3，n，其输出序列是 P1，P 2，P n 若 P=3，则 P2 的值为( )。（A）一定是 2（B）一定
2、是 1（C）不可能是 1（D）以上都不对4 设循环队列中数组的下标是 0N1，其头尾指针分别为 f(指向队头元素的前一位置)和 r(指向队尾元素的位置) ，则其元素个数为( )。（A）r-f（B） r-f-1（C） (r-f)N+1（D）(r-f+N)N5 若将 n 阶上三角矩阵 A 按列优先顺序压缩存放在一维数组中，第一个非零元素0。存于 B0中。则应存放到 Bk中的非零元素 ija(1in，1ji)的下标 ij 与 k 的对应关系是( ) 。（A）i(i+1)2+j（B） i(i 一 1)2+j1（C） j(j+1)2+i（D）j(j 一 1)2+i 一 16 设高度为 h(根结点为第 1
3、 层)的二叉树上只有度为 O 和度为 2 的结点，则此类二叉树所包含的结点数至少为( )。（A）2h（B） 2h 一 1（C） 2h+1（D）h+17 无向图的邻接矩阵是一个( )。（A）对称矩阵（B）零矩阵（C）上三角矩阵（D）对角矩阵8 对线性表进行二分查找时，要求线性表必须( )。（A）以顺序方式存储（B）以链表方式存储（C）以顺序方式存储，且结点按关键字有序排序（D）以链表方式存储，且结点按关键字有序排序9 以下排序算法中，( ) 不能保证每趟排序至少能将一个元素放到其最终位置上。（A）快速排序（B）希尔排序（C）堆排序（D）冒泡排序二、简答题10 有 5 个字符，根据其使用频率，设计
4、对应的哈夫曼编码，以下哪些是可能的哈夫曼编码?(1)000，001， 010，011，1(2)0000，0001 ，001，01，1(3)000，001， 01，10，11(4)00，100， 101，110，11111 一个有向图 G 的邻接表存储如下图所示，现按深度优先搜索遍历，从顶点 1 出发，所得到的顶点序列是什么?12 已知一个有序表为(12，18，20，25，29，32，40，62，83，90，95，98)，当二分查找值为 29 和 90 的元素时，分别需要多少次比较才能查找成功?若采用顺序查找时，分别需要多少次比较才能查找成功?13 按 13、24、37、90、53 的次序形成二
5、叉平衡树，回答以下问题：14 该二叉平衡树的高度是多少?15 其根结点是谁?16 左子树中的数据是什么?17 右子树中的数据是什么?三、设计题18 (设计一个算法 intincrease(LinkL*ist*L)，判定带头结点单链表 L 是否是递减的，若是，返回 1，否则返回 0。19 假设二又树采用二叉链存储结构存储，试设计一个算法，输出该二叉树中第一条最长的路径长度，并输出此路径上各结点的值。综合模拟试卷 20 答案与解析一、单项选择题1 【正确答案】 A【试题解析】 算法花费的时间与算法中语句的执行次数成正比，算法中哪个语句执行次数多，它花费的时间就多。一个算法中的语句执行次数称为语句频
6、度或时间频度，记为 T(n)，n 为问题规模。当 n 不断变化时，时间频度 T(n)也会不断变化。一般情况下，算法中基本操作重复执行的次数是问题规模 n 的某个函数，用 T(n)表示。若有某个辅助函数 f(n)，使得当 n 趋近于无穷大时，T(n)f(n)的极限值为不等于零的常数，则称 f(n)是 T(n)的同数量级函数。记作 T(n)=O(f(n)，称 O(f(n)为算法的渐进时间复杂度，简称时间复杂度。2 【正确答案】 A【试题解析】 B、C、D 三种情况在顺序表和链表中的实现效率是一样的。3 【正确答案】 C【试题解析】 因为 3 是第一个输出的元素，则从栈中输出 3 后，此时 1 和
7、2 保留在栈中，且 1 在 2 的下面，故 1 不可能在 2 之前出栈。故选 C。4 【正确答案】 D【试题解析】 循环队列的定义决定的。尾指针减去头指针后要加上数组总大小修正，以保证结果为正值。5 【正确答案】 D【试题解析】 a ij，前面共有 1+2+3+(j 一 1)+(i1)，求和得到结果为 D。6 【正确答案】 B7 【正确答案】 A【试题解析】 无向图定义决定的。8 【正确答案】 C【试题解析】 二分查找要求线性表必须为关键字有序表，又因为二分查找根据下标确定下一个参与比较的关键字，故需要线性表以顺序存储方式存储。9 【正确答案】 B【试题解析】 快速排序是直接选择排序的变型，与
8、直接选择排序一样可以保证每趟排序完后，有一个元素在最终位置上。冒泡排序每趟选择出一个元素放到最终位置上。堆排序的堆顶元素总为最大(大根堆)或最小(小根堆)，堆顶与堆的最末一个元素交换，然后调整堆，这决定了堆排序每趟可以把一个元素放到最终位置上。二、简答题10 【正确答案】 如果在对字符的二进制编码中不存在某一个字符的编码是另一个字符编码的前缀，那么就称这种编码方式为非前缀编码，Huffman 编码就是一种非前缀编码。比如 A：00B：10C：0100D：0101 为非前缀编码；A：01B：10C ：010D ：0000 为前缀编码。先判断(1)、(2)、(3)、(4)种情况均为非前缀编码。下面
9、我们查看是否为哈夫曼树。由编码恢复出树分别为：可见，这 4 棵树都满足哈夫曼树的定义，故它们都是哈夫曼编码。11 【正确答案】 V 1V2V3V5V412 【正确答案】 二分查找：需经过 32、20、25、29 共 4 次比较后找到 29；经过32、83、95、90 共 4 次比较后找到 90。顺序查找：经过 5 次查找找到 29；经过 10次查找找到 90。13 【正确答案】 构造出的平衡二叉树为： 故：14 【正确答案】 高度为 3。在严蔚敏的数据结构(C 语言版)中二叉树的深度定义是这样的：“ 结点的层次从根开始定义，根为第一层，树中结点的最大层次为树的深度或高度” 。15 【正确答案】
10、 根结点是 24。16 【正确答案】 左子树上的数据是 13。17 【正确答案】 右子树上的数据是 53、37、90。三、设计题18 【正确答案】 #include“stdi0 h”intincrease(LinkList*L)intrain；记录链表中的最小值LinkList*P，*q；辅助指针P=L 一next ：if(P)rain=p 一data ；因为链表带头结点q=P 一next ：while(q!=null)if(q 一datamin)return0；当前元素的值大于其相邻的前一个元素的值，则不为降序elserain：q 一data ；修改最小值q=q 一 next；指针后移re19 【正确答案】 structStackNodeBinTreeNode*ptr；enumtagL，R；classSeqStackinttop；栈顶指针Type*elements；栈元素数组intmaxSize；栈最大容量voidFirstMaxPath(BinTreeNode*T)SeqStackS(10)；StackNodeCnode；TypeLongestPathMAXSIZE；保存最长路
