2017年南京师范大学地理科学学院645C语言程序设计(含数据结构)考研强化模拟题
● 摘要
一、选择题
1． 在有向图G 的拓扑序列中，若顶点V i 在顶点V j 之前，则下列情形不可能出现的是（ ） 。
A.G 中有弧
C.G 中没有弧 【答案】D 【解析】若想实现图的一个拓扑排序，需要满足的一个条件为：若顶点A 在序列中排在顶点B 的前面，则在图中不存在从顶点B 到顶点A 的路径。又因为若G 中有一条从V j 到V i 的路径，则在拓扑序列中V i 不可能在V j 前。 2． 由3个“1”和5个“0”组成的8位二进制补码，能表示的最小整数是（ ）。 A.-126 B.-125 C.-32 D.-3 【答案】B ；负数的补码和原码的转化是：【解析】能表示的最小整数一定是负数，符号位占用1个“1” 原码符号位不变，数值部分按位取反，末位加“1”。因此最小的整数的补码是“10000011”，原码 为“11111101”，即 3． 一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（ ）个不同的码字。 A.107 B.108 C.214 D.215 【答案】B 【解析】此题可转化为一棵哈夫曼树共有215个结点，共有多少叶子结点。又有 以 4． 数组 A.55 B.45 C.36 D.16 【答案】B 所 也就是说若对其进行哈夫曼编码，共能得到108个码字。中含有元素的个数（ ）。 【解析】该数组为三维数组。其个数为 5． 动态存储管理系统中，通常可有（ ）种不同的分配策略。 【答案】C 【解析】动态存储管理系统中有以下三种：首次拟合法、最佳拟合法、最差拟合法。①首次拟合法，从表头指针开始查找可利用空间表，将找到的第一个大小不小于n 的空闲块的一部分分配给用户。②最佳拟合法，将可利用空间表中一个不小于n 且最接近n 的空闲块的一部分分配给用户。则系统在分配前首先要对可利用空间表从头到尾扫视一遍，然后从中找出一块不小于n 且最接近n 的空闲块进行分配。③最差拟合法，将可利用空间表中不小于n 且是链表中最大的空闲块的一部分分配给用户。 6． 下列网络设备中，能够抑制广播风暴的是（ ）。 中继器 集线器 网桥 路由器 A. 仅和 B. 仅 D. 仅 C. 仅和 【答案】D 【解析】中继器和集线器工作在物理层，不能抑制网络风暴。为了解决冲突域的问题，提高共享介质的利用率，通常利用网桥和交换机来分隔互联网的各个网段中的通信量，以建立多个分离的冲突域。但是，当网桥和交换机接收到一个未知转发信息的数据帧时，为了保证该帧能被目的结点正确接收，将该帧从所有的端口广播出去。于是可以看出，网桥和交换机的冲突域等于端口的个数，广播域为1。因此网桥不能抑制网络风暴。 7． 下列关于IP 路由器功能的描述中，正确的是（ ）。 I. 运行路由协议，设置路由表；II. 监测到拥塞时，合理丢弃IP 分组；III. 对收到的IP 分组头进行差错校验，确保传输的IP 分组不丢失；IV . 根据收到的IP 分组的目的IP 地址，将其转发到合适的输出线路上。 A. 仅III 、IV B. 仅 I 、II 、III C. 仅 I 、II 、IV D.I 、II 、III 、IV 【答案】C 。 【解析】路由器的主要功能是路由和转发，因此I 和IV 是正确的，而针对II 和III ，可以从 ICMP 协议的差错控制出发，注意检测到拥塞时，合理丢弃IP 分组，并回传ICMP 源抑制报文，II 是正确的，而III 对收到的IP 分组头进行差错校验，确保传输的IP 分组不丢失，差错校验是正确的，但网络层不保证IP 分组不丢失，也就是不可靠的，因此III 的说法错误，正确的说法仅I 、II 、IV , 因此答案是C 。 8． 已知循环队列存储在一维数组 rear 的值分别是（ ）。 A.0, 0 B.0, n-1 C.n-1, 0 D.n-1, n-1 【答案】B 【解析】题目要求队列非空时front 和rear 分别指向队头元素和队尾元素，若初始时队列为空，且要求第1 个进入队列的元素存储在A[0]处，则此时front 和rear 的值都为0。由于进队操作要执行（rear+1） % n，则初始 时front 的值为0、rear 的值为n-1。 9． 假定基准程序A 在某计算机上的运行时间为100秒，其中90秒为CPU 时间，其余为间。若CPU 速度提高 A.55秒 B.60秒 C.65秒 D.70秒 【答案】D 。 CPU 速度提高【解析】即CRJ 性能提高比为1.5, 改进之后的CPU 运行时间秒。速度不变，仍维持10秒，所以运行基准程序A 所耗费的时间为70秒。 10．下列选项中，用于设备和控制器（’接口）之间互连的接口标准是（ ） A.PCI B.USB C.AGP D.PCI-Express 【答案】B 【解析】设备和设备控制器之间的接口是USB 接口，其余选项不符合，故答案为B 。 速度不变，则运行基准程序A 所耗费的时间是（ ）。 中，且队列非空时front 和rear 分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front 和时 二、判断题 11．最小生成树的Krusakl 算法是一种贪心法。（ ） 【答案】√ 【解析】在构建最小生成树常见的有三种贪心算法：kruskal , prim , soilion 。
相关内容
相关标签