2017年扬州大学信息工程学院858程序设计与数据结构之数据结构考研仿真模拟题
● 摘要
目录
2017年扬州大学信息工程学院858程序设计与数据结构之数据结构考研仿真模拟题（一）.... 2 2017年扬州大学信息工程学院858程序设计与数据结构之数据结构考研仿真模拟题（二）.. 12 2017年扬州大学信息工程学院858程序设计与数据结构之数据结构考研仿真模拟题（三）.. 22 2017年扬州大学信息工程学院858程序设计与数据结构之数据结构考研仿真模拟题（四）.. 33 2017年扬州大学信息工程学院858程序设计与数据结构之数据结构考研仿真模拟题（五）.. 44
一、选择题
1． 设栈S 和队列Q 的初始状态均为空，元素a , b , c ，d ，e , f ，g 依次进入栈S 。若每个元素出栈 后立即进入队列Q ，且7个元素出队的顺序是b ，d ，c ，f , e , a ，g ，则栈S 的容量至少是（ ）。
A.1 B.2 C.3 D.4
【答案】C
【解析】由于栈具有先进后出的特性，队列具有先进先出的特性，出队顺序即为人队顺序。在本题中，每个元素出栈S 后立即进入队列Q ，出栈顺序即为入队顺序，所以本题中队列的作用形同虚设，根据题意出队顺序即为出栈顺序。根据出栈顺序可以分析各个元素进出栈的过程：第一个出栈元素为b , 表明栈内还有元素a ，b 出栈前的深度为2; 第二个出栈元素为d ，栈内元素为a 和c ，d 出栈前的深度为3; c 出栈后，剩余元素为a ，c 出栈前的深度为2; f 出栈后，剩余元素为a 和e ，f 出栈前的深度为3; e 出栈后，剩余元素为a ，e 出栈前的深度为2; a 出栈后，无剩余元素，a 出栈前的深度为1; g 出栈后，无剩余元素，g 出栈前的深度为1。所以栈容量至少是3。
2． 文件系统中，文件访问控制信息存储的合理位置是（ ）。
A. 文件控制块 B. 文件分配表 C. 用户口令表 D. 系统注册表 【答案】A
【解析】文件控制块是文件存在的标志，文件的相关信息（基本信息、存取控制信息以及使用信息）都存储在文件控制块中，系统对文件的管理全是依靠文件控制块里的信息。
3． 数据序列只能是下列排序算法中的（ ）的两趟排序后的结果。
A. 选择排序 B. 起泡排序 C. 插入排序 D. 堆排序 【答案】C
【解析】选择排序、起泡排序和堆排序两趟排序后，在序列的某一端应该有序列的两个最大
值或者最小值。
4． 在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）。
A.0（n ） B.0（n+e） C.0（n*n） D.0（n*n*n） 【答案】B
【解析】由于输出每个顶点的同时还要删除以它为起点的边，故拓扑排序的时间复杂度为0（n+e）
5． 在下列存储形式中，哪一个不是树的存储形式？（ ）
A. 双亲表示法 B. 孩子链表表示法 C. 孩子兄弟表示法 D. 顺序存储表示法 【答案】D
【解析】顺序存储就是利用一段连续的存储单元依次存储线性表中的元素。树中某个结点的孩子可以有多个，这就意味着，无论用哪种顺序将树中所有的结点存储到数组中，结点的存储位置都无法直接反映逻辑关系。因此简单的顺序存储表示不能满足树的基本要求。常用的三种树的表示法为：双亲表示法、孩子链表示法、孩子兄弟表示法。
6． 循环队列存放其元素值，用front 和rear 分别表示队头和队尾，则当前队列中的元素数是（ ）。
【答案】A
【解析】对于循环队列，需要深刻理解队头在队尾进行进队操作。
和队尾
的概念，在队头进行出队操作，
如果为负则元
可能为正也可能为负，为正时元素个数=
素的个数=所以统一的公式就是
7． n 个结点的线索二叉树上含有的线索数为（ ）。
【答案】C
【解析】线索二叉树是利用二叉树的空链域加上线索，n 个结点的二叉树有n+1个空链域。
8． 某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为字节，页表项大小为2字节，逻辑地址结构为：
逻辑地址空间大小为（ ）。
A.64
页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是
B.128 C.256 D.512 【答案】B
【解析】地址空间分为逻辑地址空间和物理地址空间。页的大小为采用二级页表，一页可存放要
9． 在子网192.168.4.0/30中， 能接收目的地址为192.168.4.3的IP 分组的最大主机数是（ ）。A.0 B.1 C.2 D.4
【答案】C
【解析】每个子网中忽略子网内全为0和全为1的地址剩下的就是有效主机地址，本题中由于子网的比特数是30, 因此用于主机的只有2位，即00, 01, 10, 11，有效主机地址是2个，这里192.168.4.3显然是其广播地址，因此答案是C 。
10．主机甲向主机乙发送一个
A. （SYN=0, ACK=0, seq=11221, ack=11221） B. （SYN=1, ACK=1, seq=11220, ack=11220） C. （SYN=1，ACK=1, seq= 11221，ack= 11221） D. （SYN=0, ACK=0, seq= 11220, ack= 11220） 【答案】C
【解析】TCP 是面向连接的，所谓面向连接，就是当计算机双方通信时必需先建立连接，然后数据传送，最后拆除三个过程，也就是客户主动打开TCP 传输，服务器被动打开。第一次握手：客户发送SYN=1，seq=x 给服务器，即客户的TCP 向服务器发出连接请求报文段，其首部中的同步位SYN=1，并选择序号seq=x，表明传送数据时的第一个数据字节的序号是X 。第二次握手：服务器发送SYN=1, ACK=1, Seq=y, ack=X+l给客户，即服务器的TCP 收到连接请求报文段后，如同意则发回确认。服务器在确认报文段中应使SYN=1，使 ACK=1，其确认号ack=x+l, 自己选择的序号seq=y。第三次握手：客户发送ACK=1, seq=x+l, ack=y+l 给服务器，即客户收到此报文段后向服务器给出确认，其ACK=1, 确认号aCk=y+l。客户的TCP 通知上层应用进程，连接已经建立。服务器的TCP 收到主机客户的确认后，也通知其上层应用进程：TCP 连接已经建立。 因此，本题中x=11220, y是主机乙自动选取的序号，可以与x 相同，也可以不相同，从而主机乙所ACK=1, seq=y, ack=x+l，ACK=1, seq=y，ack=11221，发出的TCP 段应该是SYN=1，即 SYN=1，从而答案是 C 。
字节，页表项大小为2B ，
字节，故最少需
’个页表项，本题中逻辑地址空间大小为
个页面来保存页表项，故本题答案为B 。
的TCP 段，期望与主机乙建立TCP 连接，
若主机乙接受该连接请求，则主机乙向主机甲发送的正确的TCP 段可能是（ ）。
相关内容
相关标签