Dotcpp  /  试卷列表  /  考研真题题库 - 第20页

考研真题

第381题

(10分)在进行外部排序时，可使用置换-选择排序生成初始归并段。内存工作区可存储n个记录，某文件含 n 个记录。

(1)若n=19，m=4。文件记录关键字为：51,94,37,92,14,63,15,99.48,56,23,60,31,17,43,8,90,166,100。使用置换-选择排序，可生成几个初始归并段?每个归并段各是什么?

(2)对于任意 m(n>>m>0)，使用置换-选择排序生成第一个初始归并段的最大可能长度、最小可能长度分别是?

[

第382题

(14分)某机器字长为32位的计算机M，采用请求调页存储管理。虚拟地址32位，页面大小4KB。Cache采用4路组相联映射，内存块大小为32B，Cache数据区大小为8KB。二维数组int a[24][64]按行优先存储，数组的起始虚拟地址为0042 2000H。数组a的数据初始时未调入内存，按如下方式访问数组a:

for (int i=0;i<24; i++)
for (int j=0;j<64; j++)
a[i][j]=10;

(1)数组a分为几个页面存储?访问数组a 缺页几次?页故障地址各是什么?

(2)不考虑对变量i，j的访问，访问数组 a 的过程是否具有时间局部性?为什么?

(3)在计算机M的32位地址中，块内地址是哪几位? Cache组号是哪几位?数组元素a[1][0]的虚拟地址是什么?对应的Cache组号是什么?

(4)数组a总共占多少块?访问a的Cache 命中率是多少?若采用如下方式访问数组a，则命中率又是多少?

for (int j=0;j<64;j++)
for (int i=0; i<24; i++)
a[i][j]=10;

[

第383题

(9分)43题的C语言代码，对应的机器级代码如下,请回答问题。

for(int i=0;i<24;i++)
1   00401070     C7...     mov[ebp-8],0
2   00401079     EB 09   jmp 00401084h
3   0040107B     8B 55 F8   mov eax,[ebp-8]
...  ...                    ...              ...
7   00401088     7D32    jpe 004010bch
for(int j=0;j<64;j++)
8   0040108A     C7 45...      mov[ebp-4],0
...   ...                   ...               ...
a[i][j]=10;
...   ...                   ...               ...
19  004010AE     C7 84 82 00 20 42 00 0A 00 00 00 mov[ecx+edx*4+00422000h],0Ah
20  ...                   ...

(1)第20条指令的虚拟地址是什么?

(2)第2条指令jmp的操作码是 EBH，它的转移目标地址是00401084h。第7条指令jge的操作码是7DH，它的转移目标地址是 004010bch。这两条指令分别采用什么寻址方式?请给出jmp 指今的转移目标地址计算过程

(3)第19条指令，实现了adll-10该指今的源操作数采用什么寻址方式?已知edx 存放的值，ecx存放的是什么?该系统采用大端还是小端存储?

(4)第一次取第19条指令时，是否发生缺页?为什么?

[

第384题

(7分)采用swap 指今实现进程互斥。lock为TRUE时，不可进入临界区; lock 为FALSE 时，可以进入临界区。某学生写的代码如下:

bool lock = FAlSE;//共享变量
......
// 进入区
bool key = TRUE;
if (key == TRUE)
     swap (key，lock);
// 临界区
......
// 退出区
lock=TRUE;
......
newSwap (boola， bool *b){
       bool temp =*a;
       *a=*b;
       *b=temp;
}

(1)请修改代码，正确实现互斥(不增加语句条数)

(2)是否可以用函数newSwap(&a&b)代替swap 指令?为什么?

[

第385题

(8分)进程P通过系统调用请求从键盘读入一个字符。题目乱序给出6个处理步骤:1.将进程P插入就绪队列，2.将进程插入阻塞队列，3.将字符从键盘控制器读入系统缓冲区，4.启动中断处理程序，5.系统调用返回，6.用户通过键盘输入字符。

（1）1.的前、后分别是哪个步骤? 6.的后面是什么步聚?

（2）哪个步骤一定会使CPU从P进程切换到其他进程?哪个步骤之后调度器可以调度进程p？（3）哪个步骤是由键键盘驱动程序完成的?

（4）中断处理时，进程P是什么状态? CPU处于内核态还是用户态?

[参考管案]

（1）1的前面是3(1分)

1的后面是5(1分)

6的后面是4(1分)

（2）2使得CPU从进程P切换为其他进程 (1分)

1之后调度器可以调廉进程P (1分)

（3）3由键盘驱动程序完成(1分)

（4）中断处理时，进程P处于阻塞态(1分)

CPU处于内核态(1分)

[解析]6个步骤的处理序是: 2 6 4 3 1 5

第386题

计算机网络:

(9分)主机H登录FTP服务器后自服务器上估一个大小为18000B的文件F，假设H传输F建立数据连接时，选择的初始序号为100，MTU=1000B，拥塞控制初始闻值为4MSS，RTT=10ms，忽略TCP的传输时延，在F的传榆过程中，H以MSS段向服务器发送散据，且未发生差错、丢包和乱序。

(1)FTP的控制连接是持久的还是非持久的?FTP的数据连接是持久的还是非持久的?H登录FTP服务器时，建立的TCP连接是控制连持还是数据连接?

(2)H通过数据连接发送F时，F的第一个字节序号是多少?在断开数据连接的过程中，FTP发达的第二次挥手的ACK序号是?

(3)F发送过程中,当H收到确认序号为2101的确认段时，H的拥塞窗口调整为多少?收到确认序号为7101的确认段时，H的拥塞窗口调整为多少?

(4)H从请求建立数据连接开始，到确认F已被服务器全部接收为止，至少需要多长时间期间应用层数据平均发送速率是多少?

[

第387题

(13 分)已知非空二叉树 T 的结点值均为正整数，采用顺序存储方式保存，数据结构定义如下：

typedef struct { //MAX_SIZE 为已定义常量 
 int SqBiTNode[MAX_SIZE]; //保存二叉树结点值的数组 
 int ElemNum; //实际占用的数组元素个数 
} SqBiTree;

T 中不存在的结点在数组 SqBiTNode 中用-1 表示。例如，对于下图所示的两棵非空二叉树 T1 和 T2，


二叉树

T1 的储存结果如下：

T1.SqBiTNode

402560-130-1-127

T2.ElemNum=10

T2 的储存结果如下：

T2.SqBiTNode

405060-130-1-1-1-1-135

T2.ElemNum=11

请设计一个尽可能高效的算法，判定一棵采用这种方式存储的二叉树是否为二叉搜索树，若 是，则返回 true，否则，返回 false。要求： 

（1）给出算法的基本设计思想。 

（2）根据设计思想，采用 C 或 C++语言描述算法，关键之处给出注释。

【答案解析】 

【答案一】 

（1）算法的基本设计思想 

对于采用顺序存储方式保存的二叉树，根结点保存在 SqBiTNode[0]中；当某结点保存在 SqBiTNode[i]中时，若有左孩子，则其值保存在 SqBiTNode[2i+1]；若有右孩子，则其值保 存在 SqBiTNode[2i+2]中；若有双亲结点，则其值保存在 SqBiTNode[(i-1)/2]中。 

二叉搜索树需要满足的条件是：任一结点值大于其左子树中的全部结点值，小于其右子 树中的全部结点值。中序遍历二叉搜索树得到一个升序序列。 

使用整型变量 val 记录中序遍历过程中已遍历结点的最大值，初值为一个负整数。若当 前遍历的结点值小于等于 val，则算法返回 false，否则，将 val 的值更新为当前结点的值。 （2）算法实现 


#define false 0 
#define ture 1 
typedef int bool ; 
bool judgeInOrderBST( SqBiTree bt , int k , int * val )
 //初始调用时 k 的值是 0 
{ if ( k < bt.ElemNum && bt.SqBiTNode [k] ! = -1 )
{ 
 if ( !judgeInOrderBST ( bt , 2 * k+1 , val ) ) return false; 
 if ( bt.SqBiTNode [k] <= * val ) return false; 
 * val = bt.SqBiTNode [k] ; 
 if ( !judgeInOrderBST ( bt , 2 * k+1 , val ) ) return false;
 } 
 return ture; 
}


【答案二】 

（1）算法的基本设计思想 

对于采用顺序存储方式保存的二叉树，根结点保存在 SqBiTNode[0]中；当某结点保存在 SqBiTNode[i]中时，若有左孩子，则其值保存在 SqBiTNode[2i+1]中；若有右孩子，则其值 保存在 SqBiTNode[2i+2]中；若有双亲结点，则其值保存在 SqBiTNode[(i-1)/2]中。 

二叉搜索树需要满足的条件是：任一结点值大于其左子树中的全部结点值，小于其右子 树中的全部结点值。设置两个数组 pmax 和 pmin。根据二叉搜索树的定义，SqBiTNode[i]中 的值应该大于以 SqBiTNode[2i+1]为根的子树中的最大值（保存在 pmax[2i+1]中），小于以 SqBiTNode[2i+2]为根的子树中的最小值（保存在 pmin[2i+1] 中）。初 始 时， 用数 组 SqBiTNode 中前 ElemNum 个元素的值对数组 pmax 和 pmin 初始化。 

在数组 SqBiTNode 中从后向前扫描，扫描过程中逐一验证结点与子树之间是否满足上述 的大小关系。 

（2）算法实现

#define false 0 
#define ture 1 
typedef int bool ; 
bool judgeBST( SqBiTree bt ) 
{ int k , m , * pmin , * pmax ; 
 pmin = ( int * ) malloc ( sizeof ( int ) * ( bt.ElemNum ) ) ; 
 pmax = ( int * ) malloc ( sizeof ( int ) * ( bt.ElemNum ) ) ; 
 for ( k = 0 ; k < bt.ElemNum ; k++ ) //辅助数组初始化 
 pmin [k] = pmax [k] = bt.SqBiTNode [k] ; 
 for ( k = bt.ElemNum - 1 ; k > 0 ; k - - )
 //从最后一个叶结点向根遍历 
 { if ( bt.SqBiTNode [k] ! = -1 ) 
 { m = ( k - 1 ) / 2 ; //双亲 
 if ( k % 2 = = 1 && bt.SqBiTNode [m] > pmax [k] )
 //其为左孩子 
 pmin [m] = pmin [k] ; 
 else if ( k % 2 = = 0 && bt.SqBiTNode [m] < pmin
 [k] ) //其为右孩子
pmax [m] = pmax [k] ; 
 else return false ; 
} 
 } 
 return ture ;
}
第388题

（10 分）现有 n(n>100000)个数保存在一维数组 M 中，需要在查找 M 中最小的 10 个数。 请回答下列问题。 

（1）设计一个完成上述查找任务的算法，要求平均情况下的比较次数尽可能少，简述其算法 思想（不要程序实现）。

（2）说明你所设计的算法平均情况下的时间复杂度和空间复杂度。

【答案解析】

（1）算法思想

【答案一】

定义含 10 个元素的数组 A，元素值均为该数组类型能表示的最大数 MAX。

for M 中的每个元素 s

if（s

当数据全部扫描完毕，数组 A 中保存的就是最小的 10 个数。

【答案二】

定义含 10 个元素的大根堆 H，元素值均为该堆元素类型能表示的最大数 MAX。

for M 中的每个元素 s

if（s

当数据全部扫描完毕，堆 H 中保存的就是最小的 10 个数。

（2）算法平均情况下的时间复杂度是 O（n），空间复杂度是 O(1)

第389题

（15 分）某 CPU 中部分数据通路如题 43 图所示，其中，GPRs 为通用寄存器组；FR 为标 志寄存器，用于存放 ALU 产生的标志信息；带箭头虚线表示控制信号，如控制信号 Read、 Write 分别表示主存读、主存写，MDRin 表示内部总线上数据写入 MDR，MDRout 表示 MDR 的内容送内部总线。 

请回答下列问题。 

（1）设 ALU 的输入端 A、B 及输出端 F 的最高位分别为 A15、B15 及 F15，FR 中的符号标志 和溢出标志分别为 SF 和 OF，则 SF 的逻辑表达式是什么？A 加 B、A 减 B 时 OF 的逻辑表达 式分别是什么？要求逻辑表达式的输入变量为 A15、B15及 F15。

题43图

（2）为什么要设置暂存器 Y 和 Z？ 

（3）若 GPRs 的输入端 rs、rd 分别为所读、写的通用寄存器的编号，则 GPRs 中最多有多少 个通用寄存器？rs 和 rd 来自图中的哪个寄存器？已知 GPRs 内部有一个地址译码器和一个多 路选择器，rd 应连接地址译码器还是多路选择器？ 

（4)取指令阶段（不考虑 PC 增量操作）的控制信号序列是什么？若从发出主存读命令到主存 读出数据并传送到 MDR 共需 5 个时钟周期，则取指令阶段至少需要几个时钟周期？

（5）图中控制信号由什么部件产生？图中哪些寄存器的输出信号会连到该部件的输入端？

【答案解析】 

（1)SF =F15；加运算时，43题图 

减运算时，43题图

（2）因为单总线结构中每一时刻总线上只有一个数据有效，而 ALU 有两个输入端和一个输 出端，因而需要设置 Y 和 Z 两个暂存器，以缓存 ALU 的一个输入端和输出端数据。 

（3）GPRs 中最多有 24=16 个通用寄存器；rs 和 rd 来自指令寄存器 IR；rd 应连接地址译码 器。 

（4）取指阶段的控制信号序列为：①PCout，MARin ②Read ③MDRout，IRin。取指令阶段 至少需要 7 个时钟周期。 

（5）图中控制信号由控制部件（CU）产生。指令寄存器 IR 和标志寄存器 FR 的输出信号会 连到控制部件的输入端。

第390题

（8 分）假设某磁盘驱动器中有 4 个双面盘片，每个盘面有 20000 个磁道，每个磁道有 500 个扇区，每个扇区可记录 512 字节的数据，盘片转速为 7200r/m（转/分），平均寻道时间为 5ms。 请回答下列问题。 

（1）每个扇区包含数据及其地址信息，地址信息分为 3 个字段。这 3 个字段的名称各是什么？ 对于该磁盘，各字段至少占多少位？ 

（2）一个扇区的平均访问时间约为多少？ 

（3）若采用周期挪用 DMA 方式进行磁盘与主机之间的数据传送，磁盘控制器中的数据缓冲 区大小为 64 位，则在一个扇区读写过程中，DMA 控制器向 CPU 发送了多少次总线请求？若 CPU 检测到 DMA 控制器的总线请求信号时也需要访问主存，则 DMA 控制器是否可以获得 总线使用权？为什么？

【答案解析】 

（1）3 个字段的名称为柱面号（或磁道号）、磁头号（或盘面号）、扇区号；该磁盘的柱面号、 磁头号、扇区号字段至少分别占⌈log220000⌉=15 位、⌈log2（4×2）⌉=3 位、⌈log2500⌉=9 位。 

（2）该磁盘转一圈的时间为 60×103/7 200≈8.33ms，一个扇区的平均访问时间约为 5+8.33/2+8.33/500≈9.18ms。

（3）在一个扇区读写过程中，DMA 控制器向 CPU 发送了 512B/64b=64 次总线请求。DMA 控制器可以获得总线使用权。因为一旦磁盘开始读写就必须按时完成数据传送，否则会发生 数据丢失。

第391题

（7 分)某文件系统的磁盘大小为 4KB，目录项由文件名和索引节点号构成，每个索引节点 占 256 字节，其中包含直接地址项 10 个，一级、二级和三级间接地址项各 1 个，每个地址项 占 4 字节。该文件系统中子目录 stu 的结构如题 45（a）图所示，stu 包含子目录 course 和文 件 doc，course 子目录包含文件 course1 和 course2。各文件的文件名、索引节点号、占用磁盘 块的块号如题 45（b）图所示。

45题图a  45题图b

请回答下列问题。 

（1）目录文件 stu 中每个目录项的内容是什么？

（2）文件 doc 占用的磁盘块的块号 x 的值是多少？ 

（3）若目录文件 course 的内容已在内存，则打开文件 coursel 并将其读入内存，需要读几个 磁盘块？说明理由。 

（4）若文件 course2 的大小增长到 6MB，则为了存取 course2 需要使用该文件索引节点的哪 几级间接地址项？说明理由。

【答案解析】

（1）目录文件 stu 中两个目录项的内容是： 

                         文件名                       索引节点号
                         course                              2
                           doc                             10

（2）文件 doc 占用的磁盘块的块号 x 的值为 30。 

（3）需要读 2 个磁盘块。先读 course1 的索引节点所在的磁盘块，再读 course1 的内容所在 的磁盘块。 

（4）存取 course2 需要使用索引节点的一级和二级间接地址项。6MB 大小的文件需占用 6MB/4KB=1536 个磁盘块。直接地址项可记录 10 个磁盘块号，一级间接地址块可记录 4KB/4B=1024 个磁盘块号，二级间接地址块可记录 1024 × 1024 个磁盘块号，而 10+1024<1536<10+1024+1024×1024。

第392题

（8 分）某进程的两个线程 T1 和 T2 并发执行 A、B、C、D、E 和 F 共 6 个操作，其中 T1 执行 A、E 和 F，T2 执行 B、C 和 D。题 46 图表示上述 6 个操作的执行顺序所必须满足的约 束：C 在 A 和 B 完成后执行，D 和 E 在 C 完成后执行，F 在 E 完成后执行。请使用信号量的 wait( )、signal( )操作描述 T1 和 T2 之间的同步关系，并说明所用信号量的作用及其初值。

46题图

【答案解析】

Semaphore ?AC = 0 ;                               //描述 A、C 之间的同步关系 

Semaphore ?CE = 0 ;                                //描述 C、E 之间的同步关系

T1: 

      A ; 

      signal ( SAC ) ; 

      wait ( SCE ) ; 

      E ; 

      F ;

T2: 

      B ; 

      wait ( SAC ) ; 

      C ; 

      signal ( SCE ) ; 

      D ;


第393题

（9 分）某网络拓扑如题 47 图所示，R 为路由器，S 为以太网交换机，AP 是 802.11 接入 点，路由器的 E0 接口和 DHCP 服务器的 IP 地址配置如图中所示；H1 与 H2 属于同一个广播 域，但不属于同一个冲突域；H2 和 H3 属于同一个冲突域；H4 和 H5 已经接入网络，并通过 DHCP 动态获取了 IP 地址。现有路由器、100BaseT 以太网交换机和 100BaseT 集线器（Hub） 三类设备各若干台。 

请回答下列问题。 

（1）设备 1 和设备 2 应该分别选择哪类设备？ 

（2）若信号传播速度为 2×108m/s，以太网最小帧长为 64B。信号通过设备 2 时会产生额外 的 1.51μs 的时间延迟，则 H2 与 H3 之间可以相距的最远距离是多少？

47题图

（3）在 H4 通 DHCP 动态获取 IP 地址过程中，H4 首先发送了 DHCP 报文 M，M 是哪种 DHCP 报文？路由器 E0 接口能否收到封装 M 的以太网帧？S 向 DHCP 服务器转发的封装 M 的以太 网帧的目的 MAC 地址是什么？ 

（4)若 H4 向 H5 发送一个 IP 分组 P，则 H5 收到的封装 P 的 802.11 帧的地址 1、地址 2 和地 址 3 分别是什么？

【答案解析】 

（1）设备 1 选择 100BaseT 以太网交换机，设备 2 选择 100BaseT 集线器。 

（2）设 H2 与 H3 之间的最远距离是 D，根据 CSMA/CD 协议的工作原理有：

47题图

解得：D=210m。 

（3）M 是 DHCP 发现报文（DISCOVER 报文）；路由器 E0 接口能收到封装 M 的以太网帧； 目的 MAC 地址是 FF-FF-FF-FF-FF-FF。 

（4）H5 收到的帧中，地址 1、地址 2 和地址 3 分别是：00-11-11-11-11-E1、00-11-11-11-11- C1 和 00-11-11-11-11-D1。

第394题

软件生存周期一般可分为        、可行性研究、        、设计编码、        、运行与维护阶段。

第395题

按软件的功能进行划分，软件可以划分为        、        、和应用软件。

第396题

可行性研究主要集中在以下四个方面        、         、         和抉择。

第397题

用户界面的        是用户界面设计最重要的也是最基本的目标。

第398题

常见的软件概要设计方法有 3 大类：以数据流图为基础构造模块结构的        方法，以数据结构为基础构造模块的        方法，以对象、类、继承和通信为基础的        方法。

第399题

        和        共同构成系统的逻辑模型。

第400题

软件测试的方法有        和        (即黑盒法)。

知识点标签

全部 高校题库 Python试卷 NOIP真题 计算机网络 Mysql数据库 Linux 考研真题 Java试卷 计算机二级 数据结构与算法 CSP考试 C++试卷 C语言试卷