2017年南昌大学信息工程学院838数据结构[专业硕士]考研题库

目录

2017年南昌大学信息工程学院838数据结构[专业硕士]考研题库（一） ................................ 2 2017年南昌大学信息工程学院838数据结构[专业硕士]考研题库（二） .............................. 10 2017年南昌大学信息工程学院838数据结构[专业硕士]考研题库（三） .............................. 18 2017年南昌大学信息工程学院838数据结构[专业硕士]考研题库（四） .............................. 27 2017年南昌大学信息工程学院838数据结构[专业硕士]考研题库（五） .............................. 35

2017年南昌大学信息工程学院838数据结构[专业硕士]考研题库（一）

说明：①本资料为VIP包过学员内部使用资料。涵盖了历年考研常考题型和重点题型。

——————————————————————————————————————————

一、选择题

1． 设有一棵3阶B树，如题图所示。删除关键字78得到一棵新B树，其最右叶结点所含的关键字是（ ）。

题图二叉树图

A.60

B.60,62 C.62,65 D.65

【答案】D。

【解析】本题主要考查B树删除操作。即被删关键字所在的结点中的关键字个数等于而与该结点相邻的右兄弟（或左兄弟）结点中的关键字数目大于

则需将其兄弟结点中最

小（或最大）的关键字上移至双亲结点中，而将双亲结点中小于（或大于）且紧靠该上移关键字的关键字下移至被删关键字所在结点中。题目中删除关键字78得到一棵新B树如下，其最右叶结点所含的关键字是65。

2． 假定基准程序A在某计算机上的运行时间为100秒，其中90秒为CPU时间，其余为间。若CPU

速度提高

A.55秒 B.60秒 C.65秒 D.70秒 【答案】D。 CPU速度提高【解析】

即CRJ性能提高比为1.5,改进之后的CPU运行时间

秒。速度不变，仍维持10秒，所以运行基准程序A所耗费的时间为70秒。

3． 用海明码对长度为8位的数据进行检/纠错时，若能纠正一位错，则校验位数至少为（ ）

A.2

时

速度不变，则运行基准程序A所耗费的时间是（ ）。

B.3 C.4 D.5

【答案】C

【解析】设校验位的位数为k，数据位的位数为n，根据海明码编码k和n

应满足下述关系。

当k=4时，

符合要求，校验位至少是4位，故答案为C。

4． 假设某系统总线在一个总线周期中并行传输4字节信息，一个总线周期占用2个时钟周期，总线时钟频率为10MHz,则总线带宽是（ ）。

A.lOMB/s B.20MB/S C.40MB/S D.80MB/S 【答案】B

【解析】因为一个总线周期占用2个时钟周期，完成一个32位数据的传送。总线时钟频率为10MHz,时钟周期为0.1押，总线周期占用2个时钟周期，为0.2两。一个总线周期中并行传输4=20MB/s。 字节信息,则总线带宽是4B÷

5． 以太网的MAC协议提供的是（ ）。

A.无连接不可靠服务 B.无连接可靠服务 C.有连接不可靠服务 D.有连接可靠服务 【答案】A。

【解析】考查以太网MAC协议，考虑到局域网信道质量好，以太网采取了两项重要的措施以使通信更简洁：①采用无连接的工作方式；②不对发送的数据帧进行编号，也不要求对方发回确认。因此，以太网提供的服务是不可靠的服务，即尽最大努力交付，差错的纠正由高层完成。

6． —个进程的读磁区操作完成后，操作系统针对该进程必做的是（ ）

A.修改进程状态为就绪态 B.降低进程优先级 C.进程分配用户内存空间 D.增加进程的时间片大小 【答案】A

【解析】进程等待的操作完成便会从等待状态转移到就绪状态。

7． 以太网交换机进行转发决策时使用的PDU地址是（ ）。

A.目的物理地址 B.目的IP地址

C.源物理地址 D.源IP地址 【答案】A

【解析】交换机会监测发送到每个端口的数据帧，通过数据帧中的有关信息（源结点的MAC地址、目的结点的MAC地址）,就会得到与每个端口所连接结点的MAC地址,并在交换机的内部建立一个“端口-MAC地址”映射表。建立映射表后，当某个端口接收到数据帧后，交换机会读取出该帧中的目的结点的MAC地址，并通过“端口-MAC地址”的对应关系，迅速将数据帧转发到相应的端口，注意这里的交换机工作在数据链路层，因此关于IP地址的选项是不对的，因此答案为A。

8．

循环两列放在一维数组

中，endl指向队头元素，end2指向队尾元素的后一个位置。

假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空，下列判断队空和队满的条件中，正确的是（ ）

A.队空：B.队空：C.队空：D.队空：【答案】A

【解析】在循环队列中，在少用一个元素空间的前提下，可约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等，则队满。而队空的条件还是首尾指针是否相等。

9． 折半查找的时间复杂性为（ ）。

【答案】D

【解析】顺序查找的事件复杂度为

因为折半查找是查找效率最高的算法，它的事件复杂

度为

10．在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）。

A.0（n） B.0（n+e） C.0（n*n） D.0（n*n*n） 【答案】B

【解析】由于输出每个顶点的同时还要删除以它为起点的边，故拓扑排序的时间复杂度为0（n+e）

11．下列调整中，不可能导致饥饿现象的是（ ）

A.时间片转移 B.静态优先及调度 C.非抢占式作业优先

队满：队满：

队满：

modM; 队满：

D.抢占式短作业优先 【答案】A

【解析】时间片转移方法能在一个周期内使每个进程都得到一个时间片的CPU使用时间，不会产生饥饿的现象，其余三个都会产生饥饿。

12．设栈S和队列Q的初始状态为空，元素后即进队列Q，若6个元素出队的序列是

A.6 B.4 C.3 D.2

【答案】C

依次通过栈S，一个元素出栈 则栈S的容量至少应该是（ ）。

二、算法设计题

13．已知非空双向链表由d指出，结点结构为（llink，data,rlink），请设计算法将链表中数据域值最大（假定唯一）的那个结点移至链表的最前面。要求：不得额外申请新的双链表结点。

【答案】算法如下：

14．假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法（注： 己知树中的结点数）。

【答案】算法如下：

int Depth （PTree t） //求以双亲表示法作为存储结构的树的深度

{int maxdepth=O; For（i=l;i<=t.n;i++） {temp=0;f=i;

while（f>0） {temp++;f=t.nodes[f].parent;}

// 深度加1，并取新的双亲

if（temp>maxdepth） maxdepth=temp; //最大深度更新 }

return （maxdepth};//返问树的深度） //结束Depth

15．已知两个线性表A,B均以带头结点的单链表作存储结构，且表中元素按值递增有序排列。设，并同样以元素值的递增有序的单链表形计算法求出A与B的交集C，要求C另开辟存储空间。式存储。

【答案】算法如下：

16．请编写完整的程序。如果矩阵A中存在这样的一个元素矩阵A的所有马鞍点。

【答案】算法如下：

满足 …… 此处隐藏：2461字，全部文档内容请下载后查看。喜欢就下载吧 ……