1、计算机专业（基础综合）模拟试卷 14 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 下列有关数据存储结构的叙述中，正确的是( )。（A）顺序存储方式只能用于存储线性结构（B）顺序存储方式的优点是占用存储空间小，插入、删除等操作效率高（C）链表的每个结点中都恰好含有一个指针（D）Hash 存储的基本思想是由关键词的值决定数据的存储地址2 若用一个大小为 6 的一维数组来实现循环队列，且当前 front 和 rear 的值分别为3，0，当从队列中删除一个元素，再加入两个元素后，front 和 rear 的值分别
2、为( )。（A）5，1（B） 4，2（C） 2，4（D）153 （A）LRN（B） NRL（C） RLN（D）RNL4 完全二叉树高度为 h，则最左边的叶子结点序号为( )。（A）2h h-1+1（B） 2hh-1（C） 2h+1-1（D）2 h+15 下列的叙述不正确的个数是( )。(1)9 阶 B-树，除根以外的任一结点的关键字个数不少于 4(2)理想情况下，在散列表中查找一个元素的时间复杂度为 O(1)(3)在采用线性探测法处理冲突的散列表中，所有同义词在表中相邻(4)在索引顺序表的查找中，对索引表既可以采用顺序查找方法，也可采用二分查找方法（A）1（B） 2（C） 3（D）46 关于
3、B-树，下列说法不正确的是( )。（A）B-树是一种查找树（B）所有的叶结点具有相同的高度（C） 2-3 树中，所有非叶子结点有 1 或者 3 个孩子结点（D）通常情况下，B-树不是二叉树7 在 AOE 网络中关键路径叙述正确的是( )。（A）从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最短时间（B）从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最短时间（C）从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最长时间（D）从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最长时间8 已知关
4、键序列 5，8，12，19，28，20，15，22 是小根堆(最小堆)，插入关键字3，调整后得到的小根堆是( )。（A）3，5，12，8，28，20，15，22，19（B） 3，5，12，19，20，15，22，8，28（C） 3，8，12，5，20，15，22，28，19（D）3，12，5，8，28，20，15，22，199 设用数组 A1，n 作为两个栈 S1、S2 的共用存储空间，对任一个栈，只有当数组 A1，n 全满时才不作人栈操作，则分配这两个栈空间的最佳方案是( )。（A）S1 的栈底位置设为 1，S2 的栈底位置设为 n（B） S1 的栈底位置设为 n2，S2 的栈底位置设为 n
5、2+1（C） S1 的栈底位置设为 1，S2 的栈底位置设为 n2（D）S1 的栈底位置设为 n2，S2 的栈底位置设为 110 在一棵高度为 h 的理想平衡二叉树中，最少含有( )个结点，最多含有( )个结点。（A）2 h 2h-1（B） 2h-1 2h（C） 2h+1 2h-1（D）2 h-1 2h-111 一个十进制数真值为-100，按补码形式存放在一个 16 位寄存器中，该寄存器的内容用十六进制表示为( )。（A）FF9CH（B） 009CH（C） 9C00H（D）0064H12 某浮点机字长 8 位，尾数和阶码都采用补码形式，且运算过程中数符和阶符都采用双符号位，基数为 2。则浮点加
6、减运算过程中，当出现下列哪种情况时，需要左规?( )（A）尾数相加后，数符为“01”（B）尾数相加后，数符为“10”（C）尾数相加结果为“001xxxxxx”（D）尾数相加结果为“111xxxxxx”13 补码除法中，根据( ) 上商 0。（A）余数为负（B）余数的符号与被除数的符号相同（C）余数的符号与被除数的符号不同（D）余数的符号与除数的符号不同14 以下说法中错误的是( )。（A）与 DRAM 相比，SRAM 的集成度低，存取速度快（B） PC 机的主存储器常由 DRAM 构成（C） RAM 需要刷新，且断电后信息会丢失（D）ROM 是一种非易失性存储器，断电后仍可保持记忆15 某 D
7、RAM 芯片内部存储元排列成 1 0241 024 的矩阵，且已知其存取周期为01s，最大刷新间隔为 2 ms。当采用异步刷新方式时，死时间( )。（A）=2 ms（B） 01 ms（C） =02s（D）=01s16 某计算机的指令系统中有“先基址后间址” 的寻址方式，基址寄存器为 BR，形式地址为 A，则有效地址为( )。（A）(BR)+A（B） (BR+A)（C） (BR)+A)（D）(BR)+A17 在基址寻址方式中，若基址寄存器 BR 的内容为 2D3C16 形式地址 A 的内容为5316 则有效地址 EA 为( )。（A）53 16（B） 2D3C16（C） 2D8F16（D）803
8、C 1618 某计算机的指令流水线由四个功能段组成，指令流经各功能段的时间(忽略各功能段之间的缓存时间)分别是 90 ns、80 ns、70 ns 和 60 ns，则该计算机的 CPU 时钟周期至少是( ) 。（A）90 ns（B） 80 ns（C） 70 ns（D）60 ns19 系统总线中地址线的功能是用于选择( )。（A）主存单元（B） IO 端口（C）磁盘数据块（D）A 或 B20 假设某系统总线在一个总线周期中并行传输 4 字节信息，一个总线周期占用 2个时钟周期，总线时钟频率为 10 MHz，则总线带宽是( )。（A）10 MBs（B） 20 MBs（C） 40 MBs（D）80
9、MBs21 微型计算机中，主机和高速磁盘交换数据适合采用( )方式。（A）程序查询控制（B）程序中断控制（C）直接存储器存取(DMA)（D）通道控制22 某图像显示器的分辨率为 1 024768，共可显示 256 种灰度，则显示存储器的容量为( ) 。（A）256 KB（B） 768KB（C） 1 MB（D）2 MB23 多道程序设计是指( ) 。（A）在实时系统中并发运行多个程序（B）在分布式系统中同一时刻运行多个程序（C）在一台处理机上同一时刻运行多个程序（D）在一台处理机上并发运行多个程序24 下列算法中用于磁盘移臂调度的是( )。（A）时间片轮转法（B） LRU 算法（C）最短寻找时间
10、优先法（D）优先级高者优先法25 当( ) 时，进程从执行状态转变为就绪状态。（A）进程被调度程序选中（B）时间片到（C）等待某一事件（D）等待的事件发生26 在下列文件中，不便于文件增、删操作的是( )。（A）索引文件（B）连续文件（C） Hash 文件（D）串联文件27 设有五个进程共享一个互斥段，如果最多允许两个进程同时进入互斥段，则所采用的互斥信号量初值应该是( )。（A）5（B） 2（C） 1（D）028 银行家算法在解决死锁问题中是用于( )的。（A）预防死锁（B）避免死锁（C）检测死锁（D）解除死锁29 通道又称 IO 处理机，它用于实现( )之间的信息传输。（A）主存和外设（B
11、） CPU 与外设（C）主存与 Cache（D）CPU 与外存30 执行一次磁盘输入输出操作所花费的时间包括( )。（A）寻道时间、延迟时间、传送时间和等待时间（B）寻道时间、等待时间、传送时间（C）等待时间、寻道时间、延迟时间、读写时间（D）寻道时间、延迟时间、传送时间31 （A）5F6AH（B） AF6AH（C） BF6AH（D）10F6AH32 从下面关于虚拟设备的论述中，选择一条正确的论述( )。（A）虚拟设备是指允许用户使用比系统中具有的物理设备更多的设备（B）虚拟设备是指允许用户以标准化方式来使用物理设备（C）虚拟设备是把一个物理设备变换成多个对应的逻辑设备（D）虚拟设备是指允许用
12、户程序不必全部装入内存便可使用系统中的设备33 在 OSI 参考模型中，自下而上第一个提供端到端服务的层次是( )。（A）数据链路层（B）传输层（C）会话层（D）应用层34 用 PCM 寸语音进行数字量化，如果将声音分为 128 个量化级，采样频率为 8 000 次秒，那么一路话音需要的数据传输率为( )。（A）56 Kbps（B） 64 Kbps（C） 128 Kbps（D）1 024 Kbps35 假设有一个信道的带宽是 3 000 Hz，其信噪比为 20 dB，那么这个信道可以获得的理论最大传输速率是( )。（A）1 Kbps（B） 32 Kbps（C） 20 Kbps（D）64 Kbp
13、s36 一个使用 CSMACA 的网络上，计算机 A 的帧际间隔是 2 时槽，计算机 B 的帧际间隔是 6 时槽，如果计算机 C 使用( )帧际间隔可以获得最高优先级。（A）8 时槽（B） 5 时槽（C） 3 时槽（D）1 时槽37 长度为 10 km、数据传输率为 10 Mbps 的 CSMACS 以太网，信号传播速度为200 ms。那么该网络的最小帧长为( ) 。（A）20 bit（B） 200 bit（C） 100 bit（D）1 000 bit38 以下动态路由算法中，使用距离一矢量路由算法的是( )。（A）RIP 协议（B） OSPF 协议（C） BGP 协议（D）ICMP 协议39
14、 物理层、数据链路层和网络层的 PDU 分别是( )。（A）报文、帧、比特（B）报文、分组、比特（C）比特、分组、帧（D）比特、帧、分组二、综合应用题41-47 小题，共 70 分。40 已知下列各种初始状态(长度为 n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从小到大顺序排列)?(1)关键字自小到大有序 (key1key2keyn)。(2)关键字自大到小逆序 (key1key2keyn)。(3)奇数关键字顺序有序，偶数关键字顺序有序(key1key3 ，key2key4)。(4)前半部分元素按关键字顺序有序，后半部分元素按关键字顺序逆序(key1
15、key2 keym，keym+1keym+2)keyn，m 为中间位置)。41 请利用队列的基本操作写出判定一棵二叉树是否为完全二叉树的算法。要求以二叉链表作为二叉树的存储结构。函数原型为：int IsFull_Bitree(Bitree T) 。42 计算机系统中存储器为何采用分级结构?43 指令字长为 12 位，每个地址码为 3 位，采用扩展操作码的方式，设计 4 条三地址指令、16 条二地址指令、64 条一地址指令和 16 条零地址指令。(1)给出一种操作码的扩展方案。(2)计算该方案操作码的平均长度。44 在银行家算法中，若出现下面的资源分配情况：请问： (1)状态是否安全 ? (2)
16、若进程 P2 提出请求 Request(1，2，2，2) 后，系统能否将资源分配给它?45 三类线程 search、insert、delete 共享(访问) 单链表，利用 P、V 原语操作实现这三类线程。限定如下：(1)search 可以与同类线程同时执行；(2)insert 类线程之间互斥，但是可以与任意多 search 同时执行；(3)delete 不但同类之间互斥，而且与其他类线程互斥。46 将要相互通信双方怎样进行建立 TCP 连接?在 TCP 报文段的首部中只有端口号而没有 IP 地址，当 TCP 将其报文段交给 IP 层时， IP 协议怎样知道目的 IP 地址呢?为什么把 IP 地
17、址又称为“虚拟地址”，把 TCP 连接说成是 “虚连接”?假设在建立连接时使用 2 次握手而非 3 次握手的方案，即：不再需要第 3 条报文，这时会发生什么情况?举例说明。计算机专业（基础综合）模拟试卷 14 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 D【试题解析】 顺序存储方式除了用于存储线性结构外，还能存储数组或完全二叉树等非线性结构。插入、删除操作时，由于要移动大量的数据，执行效率低，链表的形式有单链表、双链表和多重链表，除了单链表外，其他链表中的结点需要两个以上的指针。2 【正确答案
18、】 B3 【正确答案】 D4 【正确答案】 B【试题解析】 可知前 h-1 层为满二叉树，共有结点 2h-1-1，因此最左边叶子结点的序号为 B。5 【正确答案】 A【试题解析】 (1)(2)(4) 正确， (3)错误。因为如果发生多次冲突，则同义词在表中就不会相邻。6 【正确答案】 C7 【正确答案】 A8 【正确答案】 A9 【正确答案】 A【试题解析】 由于栈中元素个数不固定，因此如果将栈底设在中间位置时，固定了栈中元素的个数，不能满足只有当数组全满时才不作入栈操作的要求。10 【正确答案】 D【试题解析】 由平衡二叉树的特性可知，一棵高度为 h 的理想平衡二叉树中，含有结点数最少的情形
19、是：前 h-1 层为满二叉树，第 h 层只有一个结点，因而结点总数为(2 h-1-1)+1=2h-1；含有结点数最多的情形是：该树是一棵高度为 h 的满二叉树，因而结点总数为 2h-1。11 【正确答案】 A【试题解析】 100 的 16 位二进制形式为 0000 0000 0110 0100，将其连符号位在内取反加 1，即可得-100 的 16 位二进制形式为 1111 1111 1001 1100，写为十六进制为 FF9CH。12 【正确答案】 D【试题解析】 当尾数运算结果为非规格化形式时，需要左规；基数为 2 的补码的规格化形式下最高数值位应与符号位相反，故当尾数相加结果为“111xx
20、xxxx”时，尾数需要左规。13 【正确答案】 D【试题解析】 补码除法中，当余数的符号与除数的符号相同时，上商 1；当余数的符号与除数的符号不同时，上商 0。14 【正确答案】 C【试题解析】 RAM 又可分为 SRAM 和 DRAM，其中，DRAM 需要刷新，而SRAM 不用，故选 C。15 【正确答案】 D【试题解析】 当采用异步刷新方式时，将对 DRAM 芯片内 1 024 行的刷新均匀分布在 2 ms 内的不同时间，每次刷新一行；这样每次刷新只需停止一个存取周期，即“死时间”为一个存取周期01s ，故选 D。16 【正确答案】 C【试题解析】 先基址，即基址寄存器内容加形式地址，(B
21、R)+A ；再问址，即EA=(BR) +A)，选 C。17 【正确答案】 C【试题解析】 基址寻址方式下，EA=(BR)+A 结合题中条件，EA=(BR)+A=2D3C16+5316=2D8F16，选 C。18 【正确答案】 A【试题解析】 CPU 时钟周期必须保证能够在一个周期内完成最复杂的操作，故本题中 CPU 时钟周期至少应为 90 ns，选 A。19 【正确答案】 D【试题解析】 地址线既可用于选择主存单元，也可用于选择 IO 端口；磁盘通过磁盘控制器与主机相连，故系统总线中的地址线只能用来选择磁盘控制器中的端口，而不能用来选择磁盘数据块。20 【正确答案】 B【试题解析】 总线时钟频
22、率为 10 MHz，一个总线周期占用 2 个时钟周期，故 1 s 内共有 5 M 个总线周期；每个周期并行传输 4 字节信息，故总线带宽为 5 Ms4 B=20 MBs 。21 【正确答案】 C【试题解析】 由于磁盘是高速设备，而程序控制方式(程序查询方式和程序中断方式)下，数据传送需要 CPU 的干预，这样会占用大量的 CPU 时间，甚至可能CPU 时问全部用于数据传送都不能满足磁盘数据交换的要求；而通道控制方式一般见于大中型计算机中，微型机中基本不采用，故 C 为正确选项。22 【正确答案】 B【试题解析】 256 级灰度需要 log2256=8 个二进制位，即 1 B 来表示，故显示存储
23、器的容量为 1 024768 B=768 KB。23 【正确答案】 D24 【正确答案】 C25 【正确答案】 B【试题解析】 A：从就绪态到执行状态；C：从执行状态到阻塞状态；D：从阻塞状态到就绪状态。26 【正确答案】 B【试题解析】 因为连续文件是线性存储，每次增、删都要移动元素，代价较大。27 【正确答案】 B【试题解析】 因为最多允许两个进程同时进入互斥段，所以信号量为 2。28 【正确答案】 B29 【正确答案】 A30 【正确答案】 B31 【正确答案】 C【试题解析】 逻辑地址的最高四位为 2，即页号为 2，根据页表映射，块号为11，即 B(H)，加上页内偏移 F6AH 为 B
24、F6AH。32 【正确答案】 C33 【正确答案】 B【试题解析】 传输层是第一个提供端到端服务的层次，它使用端口来区分不同的应用程序。34 【正确答案】 A【试题解析】 声音信号需要 128 个量化级别，那么每采样一次需要 7 bit 来表示，每秒采样 8 000 次，那么一路话音需要的数据传输率为 56 Kbps。35 【正确答案】 C【试题解析】 SNR=10log 10(SN) ，题目中 SNR=20 dB，因此 SN=100。再使用香农定理可以得到信道的理论速率上限 C=Wlog2(1+SN)=3 000log 2(1+100)20(Kbps)。36 【正确答案】 D【试题解析】 在
25、 CSMACA 中，帧际间隔值可以用来分配发送方的优先级，如果一个设备被分配一个较小的帧际优先级，那么它就会有更多的机会得到对传输介质访问的机会。37 【正确答案】 D【试题解析】 来回路程=10 0002 m，RTT=10 0002(200106)=10-4。那么最小帧长度=WRTT=1 000 bit。38 【正确答案】 A【试题解析】 RIP 协议使用了距离一矢量路由算法。39 【正确答案】 D【试题解析】 物理层的 PDU 是比特，数据链路层的 PDU 是帧，网络层的 PDU是分组。二、综合应用题41-47 小题，共 70 分。40 【正确答案】 依题意，取各种情况下的比较次数即为最少
26、比较次数。(1)在这种情况下，插入第 i 个(2in)元素的比较次数为 1，因此，总的比较次数为 1+1+1+1=n-1。(2)在这种情况下，插入第 i 个(2in)元素的比较次数为 i，因此，总的比较次数为 2+3+4+n=(n-1)(n+2)2。(3)在这种情况下，比较次数最少的情况是所有纪录关键字均按升序排列，这时，总的比较次数为 n-1。(4)在这种情况下，后半部分元素的关键字均大于前半部分元素的关键字时需要比较次数最少，此时前半部分的比较次数=m-1 ，后半部分的比较次数 =(n-m-1)*(n-m+2)2，因此，总的比较次数为 m-1+(n-m-1)(n-m+2)2=(n-2)(n
27、+8)8(假设 n偶数，m=n 2)。41 【正确答案】 int IsFull Bittee(Bitree T)InitQueue(Q)；flag=0；EnQueue(Q，T) ；while(!QueueEmpty(Q)DeQueue(Q，p)；if(! p)flag=1；else if(flag)return 0；elseEnQueue(Q，p-lchild)；EnQueue(Q，p-lchild)；return 1：42 【正确答案】 对存储器要求：容量大、速度快、成本低；为了解决对存储器要求三者之间的矛盾，目前通常采用多级存储器体系结构；使用高速缓冲存储器：使存取速度和 CPU 运算速度
28、相匹配；外存储器：满足计算机对大容量存储要求；主存储器：介于高速缓冲存储器和外存储器之间，容纳核心软件和较多的用户程序。43 【正确答案】 (1)操作码的扩展方案：000XXXYYYZZZ-011XXXYYYZZZ 4 条三地址指令100000XXXYY-101111XXXYYY 16 条二地址指令110000000XXX-110111111XXX 64 条一地址指令111000000000-111000001111 16 条零地址指令(2)操作码的平均长度= 全部指令的操作码长度 指令总数=(43+166+649+1612)(4+16+64+16)=87。44 【正确答案】 45 【正确答案
29、】 int searcher_num=0，inserter_num=0；semaphore search_switch=1；semaphore insert_switch=1；semaphore insert_mutex=1；semaphore delete_mutex=1；semaphore no_searcher=1；semaphore no_inserter=1；search_thread：P(search_switch)；if(+searcher_hum=1)P(no_searcher)；V(search_switch)；search_node_code()； critical sec
30、tionP(search_switch)；if(-searcher_num=0)V(no_searcher)；V(search_switch)；insert_thread：P(insert_switch)；if(+inserter_num=1)P(no_inserter)；V(insert_switch)；P(insert_mutex)；insert_node_code()； critical sectionV(insert_mutex)；P(insert_switch)；if(-inserter_num=0)V(no inserter)；V(insert_switch)；delete_thr
31、ead：P(no_searcher)；P(no_inserter)；delete_node_code()； critical sectionV(no_inserter)；V(no_searcher)；46 【正确答案】 (1)使用三次握手建立连接过程：源主机发送一个同步标志位(SYN)置 1 的 TCP 数据段。此段中同时标明初始序号(Initial Sequence Number，ISN)。ISN 是一个随时间变化的随机值。目标主机发回确认数据段，此段中的同步标志位(SYN)同样被置 1，且确认标志位(ACK)也置 1，同时在确认序号字段表明目标主机期待收到源主机下一个数据段的序号(即表明前
32、一个数据段已收到并且没有错误)。此外，此段中还包含目标主机的段初始序号。?源主机再回送一个数据段，同样带有递增的发送序号和确认序号。(2)仅从 TCP 报文段的首部无法得知目的 IP 地址， TCP 必须告诉 IP 层此报文段要发送给哪一个目的主机(给出其 IP 地址)。(3)因为 IP 地址是靠软件来维持的而不是硬件地址。互联网络也是虚拟的网络系统，它的通信系统是抽象的。虽然许多硬件和软件的组合看起来好像构成了一个很大的网络，但这样的大网络实际上并不存在。这种虚拟网络的地址也是虚拟的，因此 IP 地址又称为“虚拟地址”。同样，因为在两个主机之间建立的 TCP 连接并非真正的物理连接。传输层并
33、不知道所传送的报文段都经过哪些中间结点。实际上，IP数据报都各自独立地选择路由，而所经过的中间结点(路由器)并不记录各 IP 数据报通过的情况。TCP 连接只是从传输层看来，好像在两个传输实体之间有一条连接。因此这条连接可以称之为“虚连接” 。(4)现在把三次握手改成仅需要两次握手，可能发生死锁。假定 B 给 A 发送一个连接请求分组，A 收到了这个组，并发送了确认应答分组。按照两次握手的协定，A 认为连接已经成功的建立了，可以开始发送数据分组。可是， B 在 A 的应答分组在传输中被丢失的情况下，不知道 A 是否已经准备好，不知道 A 建议 B 使用什么样的序列号，也不知道 A 是否同意 B 所建议的 B 到 A 的初始序列号等等，这时B 认为连接还未建立成功，将忽略 A 发来的任何数据分组，只等待接收连接确认应答分组。而 A 在发出的分组超时以后，重复发送同样的分绢。
