2016年赣南师范学院数学计算机科学学院、脐橙学院数据结构(同等学力加试)复试笔试最后押题五套卷.doc

2016年赣南师范学院数学计算机科学学院、脐橙学院数据结构(同等学力加试)复试笔试最后押题五套卷一、选择题1． 某网络拓扑如下图所示，路由器R1只有到达子网192.168.1.0/24的路由为使R1可以将IP 分组正确地路由到图中所有子网，则在R1中需要増加一条路由（目的网络，子网掩码，下一跳）是（ ） A.192.168.2.0, 255.255.255.128, 192.168.1.1B.192.168.2.0, 255.255.255.0, 192.168.1.1C.192.168.2.0, 255.255.255.128, 192.168.1.2D.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 2． 对于栈操作数据的原则是（ ）A. 先进先出B. 后进先出C. 后进后出D. 不分顺序答:B【解析】先进先出是队列操作数据的原则先进后出是栈操作数据的原则，栈限定在表尾进行插入和删除 3． 下列文件物理结构中，适合随机访问且易于文件扩展的是（ ）A. 连续结构B. 索引结构C. 链式结构且磁盘块定长D. 链式结构且磁盘块变长答:B【解析】连续结构的优点是结构简单，缺点是不易于文件扩展，不易随机访问链式结构的优点是文件易于扩展，缺点是不易随机访问索引结构的优点是具有链式结构的优点并克服了它的缺点，可随机存取，易于文件扩展 4． 若数据元素序列11, 12, 13, 7, 8, 9, 23, 4, 5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（ ）。

A. 起泡排序B. 插入排序C. 选择排序D. 二路归并排序答:B【解析】经过两趟排序后，A 项起泡排序的结果是两个最小或最大的元素放到了序列的最终位置；B 项插入排序的结果是前三个数有序即可；C 项选择排序结果是两个最小的元素在最前面按顺序排好；D 项二路归并排序的结果是长度为4的子序列有序，即前4个数排好序，接下来的4个数排好序显然题目中的元素序列只能是插入排序第二趟排序后的结果，因此，B 项正确 5． 若对n 阶对称矩阵A 以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组中，则在B 中确定 的位置k 的关系为（ ） 答:B【解析】将n 阶对称矩阵存人一维数组中，一维数组的大小需为中，当时，i 与k 的关系为依次通过栈S ，一个元素出栈则栈S 的容量至少应该是（ ）对n 阶对称矩阵A以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组 6． 设栈S 和队列Q 的初始状态为空，元素后即进队列Q ，若6个元素出队的序列是A.6B.4C.3D.2答:C 7． 已知字符串S 为“abaabaabacacaabaabcc ”，模式串t 为“abaabc ”，采用KMP 算法进行匹配，第一次出现“失配” （A.i=l，j=0B.i=5，j=0C.i=5，j=2D.i=6，j=2答:C【解析】模式匹配（KMP ）算法对普通的暴力匹配的改进在于：每当匹配过程中匹配失败时，主串（本题为S ）的指针（i ）不需要回溯，而是利用已经得到的“部分匹配”的结果将模式串（t ）向右“滑动”尽可能远的一段距离后，继续进行比较。

模式串“滑动”的距离是由模式串（t ）本身决定的，即t 的子串中前缀串和后缀串相等的最长长度本题中第一次失配i=5, 字串为“abaab”，其相等且最长的前后缀为“ab”，一次下一个j = 2 8． 若对如下的二叉树进行中序线索化，则结点x 的左、右线索指向的结点分别是（ ） A. B. C. D.，i=j = 5，则下次开始匹配时，i 和j 的值分别是（ ）） 答:D【解析】此二叉树的中序遍历序列为：debxac ，由于节点x 左右孩子都为空，所有进行中序线索化时，它的左右孩子指针分别指向它的中序遍历序列的直接前驱结点b 和直接后继结点a , 所以选D 9． 下列介质访问控制方法中，可能发生冲突的是（ ）A.CDMAB.CSMAC.TDM ACD.FDMA答:B【解析】介质访向控制协议中能够发生冲突的是CSMA 协议，答案为B 一、选择题考研试题。