2016年东北理工大学机械与电子工程学院数据结构(同等学力加试)考研复试题库
● 摘要
目录
2016年东北理工大学机械与电子工程学院数据结构（同等学力加试）考研复试题库（一） . .... 2
2016年东北理工大学机械与电子工程学院数据结构（同等学力加试）考研复试题库（二） . .. 10
2016年东北理工大学机械与电子工程学院数据结构（同等学力加试）考研复试题库（三） . .. 18
2016年东北理工大学机械与电子工程学院数据结构（同等学力加试）考研复试题库（四） . .. 26
2016年东北理工大学机械与电子工程学院数据结构（同等学力加试）考研复试题库（五） . .. 34
一、选择题
1． 在有向图的邻接表存储结构中，顶点V 在链表中出现的次数是（ ）。
A. 顶点V 的度 B. 顶点V 的出度 C. 顶点V 的入度 D. 依附于顶点V 的边数
答:B
【解析】在有向图中，第j 个链表中的结点个数只是顶点Vi 的出度，为求入度，必须遍历整个邻接表。因此顶点V 在链表中出现的次数是顶点V 的出度。
2． 下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是（ ）。
A. 先来先服务
B. 高响应比优先
C. 时间片轮转
D. 非抢占式短任务优先
答:B
【解析】分析该题目可以看到，本题所提到的问题是涉及短任务调度也就是属于作业调度，因此首先排除时 间片轮转算法；因为作业调度算法中没有时间片轮转的算法。其次，因为问题提到短任务，则先来先服务的算法也可以排除了，它与短任务无关。剩余高响应比优先算法和非抢占式短任务优先是哪一个? 我们可以通过分析得到，非抢占式短任务优先算法不能解决饥饿问题，因为当一个系统短任务源源不断到达是，长任务必然会得不到 调度，产生饥饿。而解决此方法的最好方式就是采用计算响应比的方法，并以高响应比值优先调度。这样，无论短任务或长任务，均可以得到调度，而且，较短任务会得到优先的调度。故满足短任务优先且不会发生饥饿现象的调度算法只有尚响应比优先算法。
3． 已知字符串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 ，i=j = 5，则下次开始匹配时，i 和j 的值分别是（ ））。
【解析】模式匹配（KMP ）算法对普通的暴力匹配的改进在于：每当匹配过程中匹配失败时，主串（本题为S ）的指针（i ）不需要回溯，而是利用已经得到的“部分匹配”的结果将模式串（t ）向右“滑动”尽可能远的一段距离后，继续进行比较。模式串“滑动”的距离是由模式串（t ）本身决
定的，即t 的子串中前缀串和后缀串相等的最长长度。本题中第一次失配i=5, 字串为“abaab”，其相等且最长的前后缀为“ab”，一次下一个j = 2。
4． 5个字符有如下4种编码方案，不是前缀编码的是（ ） A. B. C. D.
答:D
【解析】在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀。约定左分支
表示字符
右分支表示字符则可以用从根结点到叶子结点的路径上的分支字符串作为该叶子结点字符的编码。如此得到的编码必是前缀编码。D 选项中，编码110是编码1100的前缀，故不符合前缀编码的定义。
5． 二叉树在线索化后，仍不能有效求解的问题是（ ）。
A. 前序线索二叉树中求前序后继
B. 中序线索二叉树中求中序后继
C. 中序线索二叉树中求中序前驱
D. 后序线索二叉树中求后序后继
答:D
【解析】后序线索二叉树求后序后继要分3种情况，比较复杂，不是仅仅线索化后就能求解的，算法上还要要分情况讨论。
6． 下列指令中，不能在用户态执行的是（ ）
A.trap 指令
B. 跳转指令
C. 后栈指令
D. 关中断指令
答:D
【解析】关中断指令必须在和心态才能执行，trap 指令可以在用户态下执行，执行了就转到和心态，跳转与退栈指令都是可以在用户态下执行的指令。
7． 程序P 在机器M 上的执行时间是20秒，编译优化后，P 执行的指令数减少到原来的CPI 増加到原来的1.2倍，则P 在M 上的执行时间是（ ）
A.8.4 秒
B.11.7 秒
C.14 秒
D.16.8 秒
而
相关内容
相关标签