2018年闽南师范大学计算机学院821计算机学科专业基础综合[专业硕士]之数据结构考研强化五套模拟题
● 摘要
一、填空题
1. 数据结构中评价算法的两个重要指标是_____。
【答案】算法的时间复杂度和空间复杂度
2. 对于一个具有n 个结点的二叉树,当它为一棵_____二叉树时具有最小高度, 当它为一棵_____时,具有最大高度。
【答案】完全;只有一个叶结点的二叉树
3. 克鲁斯卡尔算法的时间复杂度为_____,它对_____图较为适合。 【答案】;边稀疏
4. 在下面的程序段中,对X 的赋值语句的时间复杂度为_____ (表示为n 的函数) 。
【答案】1+(1+2) +(1+2+3) +…+(l+2+…+n) =n(n+1)(n+2)/6,即O(n)
【解析】当i =l 时,赋值语句就被执行了一次。当i =2时,赋值语句被执行了1+2次。当i =3时,赋值语句被执行了1+2+3次。...... 可以推出赋值语句总共被执行了1+(1+2) +(1+2+3) +…+(l+2+... +n) =n(n+1)(n+2)/6次。
5. 起始地址为480,大小为8的块,其伙伴块的起始地址是_____;若块大小为32, 则其伙伴块的起始地址为_____; 。
【答案】480+8=488,480-32=448
【解析】起始地址为P ,大小为的内存块,其伙伴块的起始地址计算公式如下:
根据上述公式起始地址就为488。
6. 高度为h 的堆中,最多有_____元素,最少有_____个元素。 【答案】
。当最后一层只有【解析】当这个堆构成的是满二叉树时,元素的个数最多,元素个数为
一个元素时,此时堆的元素个数最少,元素个数为
。
二、单项选择题
7. 已知一棵有2011个结点的树, 其叶结点个数为116, 该树对应的二叉树中无右孩子的结点个数是( )。
A.115
B.116
C.1895
D.1896
【答案】D
【解析】每个非终端结点转换成二叉树后都对应一个无右孩子的结点(因为一个非终端结点至少有一个孩子结点, 其最右边的孩子结点转换成二叉树后一定没有右孩子) , 另外, 树根结点转换成二叉树后也没有右孩子。题目中树的总结点数是2011, 叶结点个数是116, 则非终端结点个数是2011-116=1895, 则该树对应的二叉树中无右孩子的结点个数是1895+1=1896。
8. 已知字符串S 为“abaabaabacacaabaabcc ”, 模式串t 为“abaabc ”, 采用KMP 算法进行匹配, 第一次出现“失配”(
A.i=l, j=0
B.i=5, j=0
C.i=5, j=2
D.i=6, j=2
【答案】C
【解析】模式匹配(KMP)算法对普通的暴力匹配的改进在于:每当匹配过程中匹配失败时, 主串(本题为S) 的指针(i)不需要回溯, 而是利用已经得到的“部分匹配”的结果将模式串(t)向右“滑动”尽可能远的一段距离后, 继续进行比较。模式串“滑动”的距离是由模式串(t)本身决定的, 即t
的子串
中前缀串和后缀串相等的最长长度。本题中第一次失配i=5, 字串为“abaab”, 其相等且最长的前后缀为“ab”, 一次下一个j=2。
9. 二叉树在线索化后,仍不能有效求解的问题是( )。
A. 前序线索二叉树中求前序后继
B. 中序线索二叉树中求中序后继
C. 中序线索二叉树中求中序前驱
D. 后序线索二叉树中求后序后继
【答案】D
【解析】后序线索二叉树求后序后继要分3种情况,比较复杂,不是仅仅线索化后就能求解的,算法上还要要分情况讨论。
10.一棵二叉树高度为h ,所有结点的度或为0或为2,则这棵二叉树最少有( )个结点。
A.2h
) 时, i=j=5, 则下次开始匹配时, i 和j 的值分别是( )。
B.2h ﹣1
C.2h +l
D.h +1
【答案】B
【解析】此树满足哈夫曼树,除根节点外每层有两个节点。
11.内部异常(内中断) 可分为故障(fault)、陷阱(trap)和终止(abort)三类。下列有关内部异常的叙述中, 错误的( )。
A. 内部异常的产生与当前执行指令相关
B. 内部异常的检测由CPU 内部逻辑实现
C. 内部异常的响应发生在指令执行过程中
D. 内部异常处理后返回到发生异常的指令继续执行
【答案】D
【解析】内中断分为:
①由软中断指令启动的中断; ②在一定条件下由CPU 自身启动的中断。
D 项错误, 如突然掉电引发的内中断经处理后不会继续执行。
12.设计一个判别表达式中左、右括号是否配对出现的算法,采用( )数据结构最佳。
A. 线性表的顺序存储结构
B. 队列
C. 线性表的链式存储结构
D. 栈
【答案】D
【解析】用栈更合适,如果是左括号,进栈;如果是右括号,看栈顶是不是左括号,如果是,则左括号出栈;否则不配对(可以直接结束算法) 。处理完所有符号号,如果栈为空则配对成功。
13.下列选项给出的是从根分别到达两个叶节点路径上的权值序列, 能属于同一棵哈夫曼树的是( )。
A.24, 10, 5和24, 10, 7
B.24, 10, 5和24, 12, 7
C.24, 10, 10和24, 14, 11
D.24, 10, 5和24, 14, 6
【答案】D
【解析】哈夫曼树是带权路径长度最短的二叉树。由根节点出发到两个叶子节路径中, 第二个被访问的两个结点的权值要么相等, 要么和为根节点的权值, 故B 项错误。同理, 通过第三个被访问的节点排除A 项。C 项, 由两条路径可推出三个叶子节点的权值分别是:3、10和11, 而根据哈夫