2022年齐鲁工业大学理学院872数据结构考研导师圈点必考题汇编

目录

2017年齐鲁工业大学理学院872数据结构考研导师圈点必考题汇编（一） (2)

2017年齐鲁工业大学理学院872数据结构考研导师圈点必考题汇编（二） (12)

2017年齐鲁工业大学理学院872数据结构考研导师圈点必考题汇编（三） (23)

2017年齐鲁工业大学理学院872数据结构考研导师圈点必考题汇编（四） (33)

2017年齐鲁工业大学理学院872数据结构考研导师圈点必考题汇编（五） (43)

第1 页，共53 页

第 2 页，共 53 页 2017年齐鲁工业大学理学院872数据结构考研导师圈点必考题汇编（一）

说明：①本资料为VIP 学员内部使用，整理汇编了历届导师圈点的重点试题及常考试题。

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

一、选择题

1． 为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。

A.栈

B.队列

C.树

D.图

【答案】B

【解析】这类问题一般都先分析题目中的数据具有什么操作特性或是结构特性比如“先进后出”、“先进先出”等再判断其逻辑结构。栈和队列是操作受限的线性表，栈具有先进后出的特性而队列具有先进先出的特性。由于本题中先进入打印数据缓冲区的文件先被打印，因此打印数据缓冲区具有先进先出性，则它的逻辑结构应该是队列。

2． 当字符序列作为图输入时，输出长度为3的且可用作C 语言标识符的序列的有（ ）。

A.4个

B.5个

C.3个

D.6个

图

【答案】C

【解析】首先需要明白C 语言标识符的命名规则。数字不能作为标识符的开头，因此第一个字符只能为t 或者下划线。若首字符为t ,有两种结果若首字符为则只有一种结果因此总共有3种结果。

3． 下列选项中的英文缩写均为总线标准的是（ ）。

A.PCI 、CRT 、USB 、EISA

B.ISA 、CPI 、VESA 、EISA

C.ISA 、SCSI 、RAM 、MIPS

D.ISA、EISA、PCI、PCI-Express

【答案】D

【解析】选项A中的CRT和USB、选项B中的CPI、选项C中的RAM和MIPS均不是总线标准的英文缩写，只有选项D中的英文缩写均为总线标准。

4．FTP客户和服务器间传递FTP命令时，使用的连接是（）。

A.建立在TCP之上的控制连接

B.建立在TCP之上的数据连接

C.建立在UDP之上的控制连接

D.建立在UDP之上的数据连接

【答案】A

【解析】对于FTP,为了保证可靠性，选择TCP。FTP应用需要建立两条TCP连接：一条为控制连接，另一条为数据连接。FTP服务器打开21号端口，被动的等待客户的连接建立请求。客户则以主动方式与服务器建立控制连接，客户通过控制连接将命令传给服务器，而服务器则通过控制连接将应答传给客户，命令和响应都是以NVTASCII形式表示的。

5．假设某计算机按字编址，Cache有4个行，Cache和主存之间交换的块大小为1个字。若Cache 的内容初始为空，采用2路组相联映射方式和LRU替换算法，当访问的主存地址依次为0, 4, 8, 2, 0, 6, 8, 6, 4，8时，命中Cache的次数是（）。

A.1

B.2

C.3

D.4

【答案】C。

【解析】Cache有4个行，2路组相联，即Cache被分成2组，每组2行。主存地址为0?1、4?5、8?9 可映射到第0组Cache中，主存地址为2?3、6?7可映射到第1组Cache中。Cache 初始为空，采用LRU替换算法，当访问主存的10个地址依次为0, 4，8, 2, 0, 6，8, 6, 4, 8时，命中Cache的次数共有3次，分别发生在第7、8和10步时。

6．下列命中组合情况中，一次访存过程中不可能发生的是（）。

A.TLB未命中，Cache未命中，Page未命中

B.TLB未命中，Cache命中，Page命中

C.TLB命中，Cache未命中，Page命中

D.TLB命中，Cache命中，Page未命中

【答案】D

【解析】TLB （快表）和慢表（页表，Page）构成二级存储系统，若TLB命中，则Page必命中。因此不可能发生的是D选项。

第3 页，共53 页

第 4 页，共 53 页 7． 在系统总线的数据线上，不可能传输的是（ ）。

A.指令

B.操作数

C.握手（应答）信号

D.中断类型号型号

【答案】C

【解析】握手（应答）信号属于通信联络控制信号应该在通信总线上传输，不可能在数据总线上传输。而指令、操作数和中断类型码都可以在数据线上传输。

8． 已知两个长度分别为m 和n 的升序链表，若将它们合并为一个长度为m+n 的降序链表，则最坏情况下的时间复杂度是（ ）

A.

B.

C.

D.

【答案】D

【解析】m 和n 是两个升序链表长度分别为m 和n ，在合并过程中最坏的情况是两个链表中的元素依次进行比较，比较的次数是m 和n 中的最大值。

9． 主机甲向主机乙发送一个的TCP 段，期望与主机乙建立TCP 连接，若主机乙接受该连接请求，则主机乙向主机甲发送的正确的TCP 段可能是（ ）。

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 相同，也可以不相同，从而主机乙所

发出的TCP 段应该是SYN=1，ACK=1, seq=y , ack=x+l ，即 SYN=1，

ACK=1, seq=y ，ack=11221，

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