当前位置:问答库>考研试题

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, 而根据哈夫