计算机专业（基础综合）模拟试卷295
单选题
1.下列程常段的时间复杂度是( )
count=0；
for(k=1；k＜=n； k*2)
for(j=1；j＜=n；j+1)
count++；(C)
A. O(log2n)
B. O(n)
C. O(nlog2n)
D. O(n2)
解析：外部循环的退出条件是k＞n，而对于k，每次循环都执行k=k*2，所以循环次数为log2n：内部循环的退出条件是j＞n，对于j，每次循环都执行j=j+1，所以每次循环次数为n次。所以此程序段的时间复杂度为O(nlog2n)，即选C。
2.假设栈初始为空，将中缀表达式a／b+(c*d-c*f) ／g转换为等价后缀表达式的过程中，当扫描到f时，栈中的元素依次是( )(B)
A. +(*-
B. +(-*
C. ／+(*-*
D. ／+-*
解析：中缀表达式转后缀表达式遵循以下原则：
(1)遇到操作数，直接输出；
(2)栈为空时，遇到运算符，入栈；
(3)遇到左括号，将其入栈：
(4)遇到右括号，执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出；
(5)遇到其他运算符“+”、‘-’、‘*’、‘／’时，弹出所有优先级大于或等于该运算符的栈顶元素，然后将该运算符入栈：
(6)最终将栈中的元素依次出栈，输出。
所以扫描到‘／’，入栈：扫描到‘+’，由于‘+’优先级比“／’低，所以将“／’弹出，‘+’入栈：扫描到‘*’，优先级比‘+”高，入栈：扫描到‘(’，入栈：扫描到‘-’，将栈中优先级更高的‘*’弹出，‘-’入栈：扫描到‘*’，优先级比‘-’高，入栈。所以扫描到f的时候，栈中元素为：+(-*。
3.循环两列放在一维数组A[0…M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空，下列判断队空和队满的条件中，正确的是( )(A)
A. 队空：end1==end2：队满：end1==(end2+1)modM
B. 队空：end1==end2；队满：end2==(end1+1)mod(M-1)
C. 队空：end2==(end1+1)modM；队满：end1==(end2+1modM
D. 队空：end1==(end2+1)modM；队满：end2==(end1+1)mod(M-1)
解析：在循环队列中，在少用一个元素空间的前提下，可约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等，则队满。而队空的条件还是首尾指针是否相等。
4.若对如下的二叉树进行中序线索化，则结点x的左、右线索指向的结点分别是( )
(D)
A. e，c
B. e，a
C. d，c
D. b，a
解析：此二叉树的中序遍历序列为：debxac，由于节点x左右孩子都为空，所有进行中序线索化时，它的左右孩子指针分别指向它的中序遍历序列的直接前驱结点b和直接后继结点a，所以选D。
5.将森林F转换为对应的二叉树T，F中叶结点的个数等于( )(C)
A. T中叶结点的个数
B. T中度为1的结点个数
C. T中左孩子指针为空的结点个数
D. T中右孩子指针为空的结点个数
解析：森林转化为对应的二叉树是‘孩子-兄弟’存储的，即左孩子指针指向当前节点的孩子节点，右孩子指针指向当前节点的兄弟节点，所以在T中左孩子指针为空则代表它在森林中并没有孩子即为叶结点。所以选C。
6.5个字符有如下4种编码方案，不是前缀编码的是( )(D)
A. 01，0000，0001，001，1
B. 011，000，001，010，1
C. 000，001，010，011，100
D. 0，100，110，1110，1100
解析：在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀。约定左分支表示字符‘0’，右分支表示字符‘1’，则可以用从根结点到叶子结点的路径上的分支字符串作为该叶子结点字符的编码。如此得到的编码必是前缀编码。D选项中，编码110是编码1100的前缀，故不符合前缀编码的定义。
7.对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是( )
(D)
A. 3，1，2，4，5，6
B. 3，1，2，4，6，5
C. 3，1，4，2，5，6
D. 3，1，4，2，6．5
解析：拓扑排序方法如下：
(1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它；
(2)从图中删去该顶点，并且删去从该顶点发出的全部有向边；
(3)重复上述两步，直到剩余的网中不再存在没有前趋的顶点为止。
对于此有向图进行拓扑排序所有序列为：3，1，4，6，2，5和3，1，4，2，6，5。所以选D。
8.用哈希(散列)方法处理冲突(碰撞)时可能出现堆积(聚集)现象，下列选项中，会受堆积现象直接影响的是( )(D)
A. 存储效率
B. 数列函数
C. 装填(装载)因子
D. 平均查找长度
解析：哈希方法冲突会使在查找冲突的关键字时，还要根据冲突处理办法多次比较关键字，则直接影响了平均查找长度。
9.在一棵具有15个关键字的4阶B树中，含关键字
本文档预览：3000字符，共16528字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
