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

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

2022年齐鲁工业高校理学院872数据结构考研导师圈点必考题汇编〔一〕(2)

2022年齐鲁工业高校理学院872数据结构考研导师圈点必考题汇编〔二〕(12)

2022年齐鲁工业高校理学院872数据结构考研导师圈点必考题汇编〔三〕(23)

2022年齐鲁工业高校理学院872数据结构考研导师圈点必考题汇编〔四〕(33)

2022年齐鲁工业高校理学院872数据结构考研导师圈点必考题汇编〔五〕(43)

第1页，共53页

第2页，共53页2022年齐鲁工业高校理学院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-E*press

【答案】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=*给服务器，即客户的TCP向服务器发出连接恳求报文段，其首部中的同步位SYN=1，并选择序号seq=*，说明传送数据时的第一个数据字节的序号是*。第二次握手：服务器发送SYN=1,ACK=1,Seq=y,ack=*+l给客户，即服务器的TCP收到连接恳求报文段后，犹如意那么发回确认。服务器在确认报文段中应使SYN=1，使ACK=1，其确认号ack=*+l,自己选择的序号seq=y。第三次握手：客户发送ACK=1,seq=*+l,ack=y+l给服务器，即客户收到此报文段后向服务器给出确认，其ACK=1,确认号aCk=y+l。客户的TCP通知上层应用进程，连接已经建立。服务器的TCP收到主机客户的确认后，也通知其上层应用进程：TCP连接已经建立。因此，此题中*=11220,y是主机乙自动选取的序号，可以与*相同，也可以不相同，从而主机乙所

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

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

目次

2022年齐鲁工业高校理学院872数据结构考研导师圈点必考题汇编〔一〕(2)

2022年齐鲁工业高校理学院872数据结构考研导师圈点必考题汇编〔二〕(12)

2022年齐鲁工业高校理学院872数据结构考研导师圈点必考题汇编〔三〕(23)

2022年齐鲁工业高校理学院872数据结构考研导师圈点必考题汇编〔四〕(33)

2022年齐鲁工业高校理学院872数据结构考研导师圈点必考题汇编〔五〕(43)

第1页，共53页

第2页，共53页2022年齐鲁工业高校理学院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-E*press

【答案】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=