2017年上海理工大学光电信息与计算机工程学院848数据结构及操作

目录

2017年上海理工大学光电信息与计算机工程学院848数据结构及操作系统之数据结构考研强化模拟题（一） (2)

2017年上海理工大学光电信息与计算机工程学院848数据结构及操作系统之数据结构考研强化模拟题（二） (12)

2017年上海理工大学光电信息与计算机工程学院848数据结构及操作系统之数据结构考研强化模拟题（三） (22)

2017年上海理工大学光电信息与计算机工程学院848数据结构及操作系统之数据结构考研强化模拟题（四） (33)

2017年上海理工大学光电信息与计算机工程学院848数据结构及操作系统之数据结构考研强化模拟题（五） (43)

第1 页，共52 页

第 2 页，共 52 页 2017年上海理工大学光电信息与计算机工程学院848数据结构及操作系统之数据结

构考研强化模拟题（一）

说明：①本资料为VIP 学员内部使用，严格按照2017考研专业课大纲及历年常考题型出题。 ————————————————————————————————————————

一、选择题

1． 在一个采用CSMA/CD 协议的网络中，传输介质是一根完整的电缆，传输速率为1Gbps ,电缆中的信号传播速度是200000km/s 。若最小数据帧长度减少800bit ，则最远的两个站点之间的距离至少需要（ ）。

A.增加160m

B.增加80m

C.减少160m

D.减少80m

【答案】D

【解析】以太网采用CSMA/CD 访问协议，在发送的同时要进行冲突检测，这就要求在能检测出冲突的最大时间内数据包不能够发送完毕，否则冲突检测不能有效地工作。所以，当发送的数据包太短时必须进行填充。最小帧长度=碰撞窗口大小x 报文发送速率，本题最小数据帧长度减少800b ，那么碰撞的窗口也要减少，因此距离也要减少，从而（800×2×）/（l ×）=160m ，由于时间延时存在两倍的关系，因此减少的距离为80m 。

2． 向一个栈顶指针为h 的带头结点的链栈中插入指针S 所指的结点时，应执行（ ）。

【答案】D

【解析】本题是向一个链栈中插入结点，可从头结点后插入。先将s 结点指向第一个头结点之后的结点之前，再将头结点指向s 结点。

3． 下列有关RAM 和ROM 的叙述中，正确的是（ ）。

I.RAM 是易失性存储器，ROM 是非易失性存储器

II.RAM 和ROM 都采用随机存取方式进行信息访问

III.RAM 和ROM 都可用作Cache

IV.RAM 和ROM 都需要进行刷新

A.仅I 和II

B.仅II 和III

C.仅 I 、II 和IV

D.仅II 、III 和IV

【答案】A

【解析】RAM中的内容断电后即丢失（易失性），ROM中的内容断电后不会丢失（非易失性），同时RAM和ROM都采用随机存取方式（即CPU对任何一个存储单元的存取时间相同），区别在于RAM可读可写，ROM只读不写。而ROM显然不可用作Cache,也不需要刷新，所以III和IV 的叙述都是错误的。

4．当在一个有序的顺序存储表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（）。

A.必定快

B.不一定

C.在大部分情况下要快

D.取决于表递增还是递减

【答案】C

【解析】对于有序顺序存储表折半查找的效率较高，但是不是所有情况下都是如此，比如要查找的元素就是第一个时，用顺序查找比它就快的多了。这类情况外折半都高于顺序查找。

5．若则下列表达式采用8位定点补码运算实现时，会发生溢出的是（）

A.x+y

B.-x+y

C.x-y

D.-x-y

【答案】C

【解析】8位定点补码能表示的数的范围为：

A结果为78, B结果为-128, D结果为-78都在此范围内，只有C结果128超过了8位定点补码能表示的数的范围，会发生溢出

6．已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（），i=j = 5，则下次开始匹配时，i和j的值分别是（）。

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。

第3 页，共52 页

第 4 页，共 52 页 7． 若线性表最常用的操作是存取第I 个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（ ）。

A.单链表

B.双向链表

C.单循环链表

D.顺序表

【答案】D

【解析】线性表采用顺序表，便于进行存取任一指定序号的元素。

8． 某网络拓扑如下图所示，路由器R1只有到达子网192.168.1.0/24的路由。为使R1可以将IP 分组正确地路由到图中所有子网，则在R1中需要増加一条路由（目的网络，子网掩码，下一跳）是（ ）。

A.192.168.2.0, 255.255.255.128, 192.168.1.1

B.192.168.2.0, 255.255.255.0, 192.168.1.1

C.192.168.2.0, 255.255.255.128, 192.168.1.2

D.192.168.2.0, 255.255.255.0, 192.168,1,2

【答案】D

【解析】首先从题目给出的路由表项可以确定下一跳肯定是路由器R1直接相连的R2的地址，因此是 192.168.1.2,此时可以排除A 和B 两个选项了。进而分析路由器R2所连接的网络特点，注意其连接了 2个网络分别是192.168.2.0/25和192.168.2.128/25，但答案选项中只有一条信息，因此这里用到了超网的概念，超网是与子网类似的概念一IP 地址根据子网掩码被分为独立的网络地址和主机地址。但是，与子网把大网络分成若干小网络相反，它是把一些小网络组合成一个大网络——超网，这里192.168.2.00000000/25和192.168.2.10000000/25 前24位是相同的，因此所构成的超网就是192.168.2.0/24，那么子网掩码就是255.255.255.00000000即 255.255.255.0,因此答案是 D 。

9． 假设5个进

程共享三类资

源这些资源总数分别

为

时刻的资源分配情况如题表所示，此时存在的一个安全序列是（ ）。

题表资源分配情况表

本文来源：https://www.bwwdw.com/article/o4wq.html