1、计算机专业（基础综合）模拟试卷 1 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 抽象数据类型(ADT)不包括 ( )。（A）逻辑结构（B）存储结构（C）数据关系（D）操作2 利用栈对后缀表达式 12+34+*求值，求值过程所需栈的最大深度是( )。（A）1（B） 2（C） 3（D）43 序列 EAs+Y+QUE* *+st+*+IO*n+*表示对一个双端队列的操作，大写字母表示向队头之前入列，小写字母表示在队尾之后入列，加号+表示从队头出列，乘号*表示从队尾出列。该操作序列得到的出队结果是( )。（A）E
2、 A s Y Q U E s t I O n（B） E s A Y U Q E s t I O n（C） A Y s E E U t O s O I n（D）A E y s E U t Q O I s n4 一个具有 1 025 个结点的二叉树的高 h 为( )。（A）11（B） 10（C） 11 至 1 025 之间（D）10 至 1 025 之间5 （A）4 3 2 1（B） 1 4 3 2（C） 2 1 4 3（D）1 4 2 36 一棵折半查找树(BST)有 7 个结点，存放的数据分别为 A B C D E F G，( )不是查找序列。（A）A B C D E F G（B） G F E
3、 D（C） D B C F（D）D G E F7 在无序数组 aN中作 10 次以上查找，为提高查找效率，先对 aN排序，然后各次查找采用折半查找。问 N 至少为( )时，排序预处理才是合理的 ?（A）512（B） 1 024（C） 2 048（D）4 0968 100 个结点的平衡二叉树(AVL 树)最高为( )层?(根是第 1 层)（A）10（B） 11（C） 12（D）139 对无序的扑克排序，要求先排花色，再排大小，两次排序采用同种排序法，则应选用 ( )。（A）快速排序（B）选择排序（C）插入排序（D）堆排序10 某种排序法对存放在内存中的 aN排序，时间为 60 秒，对存放在内存中
4、的a2N排序的时间超过 240 秒，则该排序法极可能是( )。（A）归并排序（B）快速排序（C）堆排序（D）基数排序11 针对 8 位二进制数，下列说法中正确的是( )。（A）-127 的补码为 10000000（B） -127 的反码等于 0 的移码（C） +1 的移码等于-127 的反码（D）0 的补码等于-1 的反码12 下列说法中正确的是( )。（A）只有定点数运算才有可能溢出，浮点数运算不会产生溢出。（B）只有带符号数的运算才有可能产生溢出。（C）将两个正数相加时有可能产生溢出。（D）采用变形补码进行加减法运算可以避免溢出。13 下列说法中正确的是( )。（A）虚拟存储器技术提高了计
5、算机的速度。（B）若主存由两部分组成，容量分别为 2n 和 2m，则主存地址共需要 n+m 位。（C）闪速存储器是一种高密度、非易失性的读写半导体存储器。（D）存取时间是指连续两次读操作所需间隔的最小时间。14 在多级存储体系中，“Cache-主存”结构的作用是解决 ( )的问题。（A）主存容量不足（B）主存与辅存速度不匹配（C）辅存与 CPU 速度不匹配（D）主存与 CPU 速度不匹配15 下列陈述中不正确的是( )。（A）总线结构传送方式可以提高数据的传输速度。（B）与独立请求方式相比，链式查询方式对电路的故障更敏感。（C） PCI 总线采用同步时序协议和集中式仲裁策略。（D）总线的带宽即
6、总线本身所能达到的最高传输速率。16 已知定点整数 x 的原码为 1xn-1xn-2xn-3x0，且 x-2 n-1，则必有( )。（A）x n-1=0（B） xn-1=1（C） xn-1=0，且 x0x n-2 不全为 0（D）x n-1=1，且 x0xn-2 不全为 017 下列说法中不正确的是( )。（A）机器语言和汇编语言都是面向机器的，它们和具体机器的指令系统密切相关。（B）指令的地址字段指出的不是地址，而是操作数本身，这种寻址方式称为直接寻址。（C）串联堆栈一般不需要堆栈指示器，但串联堆栈的读出是破坏性的。（D）存储器堆栈是主存的一部分，因而也可以按照地址随机进行读写操作。18 下
7、列描述中，属于冯.诺依曼体系结构的特点是( )。采用流水线技术； 指令和数据均以二进制表示；存储程序并且存储时不区别数据和指令。（A）和（B） 和（C） 和（D），和19 下述有关存储器的描述中，正确的是( )。（A）双端口存储器具有分离的读端口和写端口，因而 CPU 可以同时对其进行读、写操作。（B）存储保护的目的是：在多用户环境中，既要防止一个用户程序出错而破坏系统软件或其他用户程序，又要防止一个用户访问不是分配给他的主存区，以达到数据安全与保密的要求。（C）在虚拟存储器中，外存和主存以相同的方式工作，因此允许程序员用比主存空间大得多的外存空间编程。（D）CPU 中通常都设置有若干个寄存器
8、，这些寄存器与 Cache 统一编址，但访问速度更高。20 在计算机系统中，表征系统运行状态的部件是( )。（A）程序计数器（B）累加寄存器（C）中断寄存器（D）程序状态字21 下列陈述中正确的是( )。（A）由于微程序控制器具有设计规整、灵活性强等优点，已经全部取代硬布线控制器（B）由于堆栈按照先入先出的固定顺序访问，故不需直接给出访问地址（C）集中式总线控制中，计数器定时查询方式下，各设备的优先级是固定不变的（D）CPU 在每个指令周期后响应中断请求22 某虚拟存储器采用页式内存管理，使用 LRU 页面替换算法，考虑下面的页面访问地址流(每次访问在一个时间单位中完成)，1，8，1，7，8，
9、2，7，2，1，8，3，8，2，1，3，1，7，1，3，7。假定内存容量为 4 个页面，开始时是空的，则页面失效次数是( )。（A）4（B） 5（C） 6（D）723 支持多道程序的操作系统，区别于其他操作系统的主要特征为( )。（A）多用户、进程的独立性、进程之间的同步与通信（B）进程的独立性、进程之间的同步与通信、动态存储分配（C）进程的独立性、动态存储分配、虚存（D）多内核结构、进程的独立性、动态存储分配24 进程与线程的主要差别体现在( )。（A）不同进程不能共享代码，而不同线程可以共享代码（B）不同进程不能共享内存，而不同线程可以共享内存（C）不同进程有不同的地址空间，而不同线程可以
10、有相同的地址空间（D）不同进程不能并行，而不同线程可并行25 以下给出 UNIX Shell 的两条命令行： I1soutputtxt&wc outputtxt& IILs WC 命令行 I 与命令行 II 的主要差别在于( )。（A）I 的 ls 与 wc 串行执行，而 II 的 ls 与 WC 并发执行（B） I 的 ls 与 WC 并发执行，而 II 的 ls 与 wc 串行执行（C） I 正确，而 II 不正确（D）I 不正确，而 II 正确26 UNIX 对已有文件建立物理链接与建立符号链接，以下叙述正确的是( )。（A）物理链接创建新的目录项，而符号链接不创建新的目录项（B）物理链
11、接创建新的 inode，而符号链接不创建新的 inode（C）物理链接不创建新的目录项，而符号链接创建新的目录项（D）物理链接不创建新的 inode，而符号链接创建新的 inode27 某系统进程 P1 在时刻 t 开始执行，所需执行时间是 5 秒。进程 P2 在时刻 t+2秒开始执行，所需执行时间是 2 秒。随后无其他进程进入系统。如果进程调度算法为时间片轮转(RR)，时间片大小为 1 秒且调度开销忽略不计，那么( )。（A）P1 的结束时间是 t+5 秒，P2 的结束时间是 t+7 秒（B） P1 的结束时间是 t+4 秒，P2 的结束时间是 t+7 秒（C） P1 的结束时间是 t+7
12、秒，P2 的结束时间是 t+5 秒（D）P1 的结束时间是 t+6 秒，P2 的结束时间是 t+7 秒28 进程 P 需要资源 1、2 、3、4，进程 Q 需要资源 2、3、4、5，系统中有资源1、2、3、4、5 各一个，以下序列( )将导致死锁。(+表示请求资源)（A）P+1 ， P+2，Q+5 ，P+4 ，P+3，Q+3，Q+2 ，Q+4（B） Q+5，Q+4，P+1，P+2，P+3 ，P+4，Q+3，Q+2（C） Q+2，Q+3，Q+4，P+1，P+2 ，P+3，Q+5，P+4（D）P+1 ， Q+4，Q+3，Q+2 ，Q+5，P+2，P+3 ，P+429 页面淘汰策略之一的先进先出算法
13、可能导致 Belady 现象，其根本原因是( )。（A）局部性原理（B）工作集太大（C）地址格式设置不当（D）程序错误30 复制文件操作完成之后(无错误)，存放文件的磁盘其空闲块将( )。（A）增加（B）减少（C）不变（D）A、B、C 都有可能31 某激光打印机每分钟打印 20 页，每页 4 000 字符，相应的设备驱动程序一次输出一个字符，采用中断方式，CPU 处理每次中断需 50 微秒，则 CPU 用于打印的开销是( ) 。（A）110（B） 115（C） 120（D）14 00032 磁盘 D1 每道 32 扇区，每扇区：1K，磁盘 D2 每道 8 扇区，每扇区 4K。文件F1 和 F2
14、 内容相同，大小为 100K。F1 均匀分布在 D1，F2 均匀分布在 D2。磁盘D1、D2 的平均寻道时间均为 10 毫秒，旋转延迟 5 毫秒，传输时间忽略不计。顺序读完 F1、F2 的时间分别为 ( )。（A）15 秒和 6 秒（B） 0375 秒和 15 秒（C） 15 秒和 0375 秒（D）6 秒和 15 秒33 网络协议的三要素是( )。（A）数据格式、编码、信号电平（B）数据格式、控制信息、速度匹配（C）语法、语义、时序（D）编码、控制信息、同步34 RS232-C 接口规范所处的层次是 ( )。（A）物理层（B）数据链路层（C）网络层（D）传输层35 一个广域网信道的比特率是
15、4 Kbps，传播延迟为 20 毫秒，若确保停一等协议至少 50的效率，那么帧的大小至少是( )。（A）大于 160 bit（B）大于 150 bit（C）大于 140 bit（D）大于 130 bit36 下列哪项是 SNMP 的正确描述 ( )。（A）SNMP 很少在新安装设备上使用（B） SNMP 是一个 TCPIP 标准（C） SNMP 是一个如 MB 一样的概念（D）SNMP 是大流量网络的最佳选择37 IP 数据报的报文格式如下图所示。在没有选项和填充的情况下，报头长度域的值为( )。（A）3（B） 5（C） 10（D）2038 对地址转换协议(ARP)描述正确的是( )。（A）A
16、RP 封装在 IP 数据报的数据部分（B） ARP 是采用广播方式发送的（C） ARP 是用于 IP 地址到域名的转换（D）发送 ARP 包需要知道对方的 MAC 电址39 下列哪一项控制端到端传送的信息量并保证 TCP 的可靠性( )。（A）广播（B）窗口（C）错误恢复（D）流量控制40 当一台计算机从 FTP 服务器下载文件时，在该 FTP 服务器上对数据进行封装的五个转换步骤是( ) 。（A）比特，数据帧，数据报，数据段，数据（B）数据，数据段，数据报，数据帧，比特（C）数据报，数据段，数据，比特，数据帧（D）数据段，数据报，数据帧，比特，数据二、综合应用题41-47 小题，共 70 分
17、。41 试编写一个建立带表头结点的双向循环链表的算法。42 编写判定给定的二叉树是否是二叉排序树的函数。43 设磁盘的扇区大小为 4 KB，磁盘转速为 15 000 rmin ，磁盘平均寻道时间为 4 ms，最大数据传输速率为 40 MBs ，磁盘控制器开销时问为 1 ms，计算读写一个扇区所需平均时间(不考虑 IO 请求队列中的等待时间 )。44 45 46 47 计算机专业（基础综合）模拟试卷 1 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 B【试题解析】 抽象数据类型的描述包括给出抽象数
18、据类型的名称、数据的集合、数据之间的关系和操作的集合等方面的描述。抽象数据类型(ADT)用于指定逻辑特性而不指定实现细节，是我们现实中讨论的数据结构(逻辑结构)，而不是计算机世界中讨论的数据结构(指存储结构，又称为物理结构)。2 【正确答案】 C【试题解析】 由后缀表达式画出所对应的二叉树，其深度是 3，故求值过程所需栈的最大深度为 3。3 【正确答案】 C【试题解析】 考查双端队列的操作。分析如下：E 入队头，A 入队头，s 入队尾，A 从队头出，Y 入队头，Y 从队头出；故最先出队的两个元素是 AY 比较答案知只有 C 满足，故选 C。4 【正确答案】 C5 【正确答案】 D【试题解析】
19、假设给定图 G 的初态是所有顶点均未曾访问过。在 G 中任选一顶点 v 为初始出发点(源点) ，则深度优先遍历可定义如下：首先访问出发点 v，并将其标记为已访问过；然后依次从 v 出发搜索 v 的每个邻接点 w。若 w 未曾访问过，则以 w 为新的出发点继续进行深度优先遍历，直至图中所有和源点 v 有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。D 选项当访问到顶点 4 时与 4 邻接的顶点还有 3 没访问过，故紧接着应该访问 3，所以 D 错。6 【正确答案】 C【试题解析
20、】 C 中 B、C 都在 D 的左子树上，所以紧接在 C 后面的 F 应该也是D 的左子树上的数据，事实上 F 应该在 D 的右子树上，故 C 错。7 【正确答案】 B【试题解析】 排序是很费时的运算，最快也得花 O(nlogn)的时间；折半查找时间复杂度 O(loga(n)。解 nlogn+10*log 2n=10*n，知选 B。8 【正确答案】 A【试题解析】 在最坏情况下，n 个结点的 AVL 树的高度约为144lgn，1 44lg100 约等于 10。9 【正确答案】 C10 【正确答案】 B11 【正确答案】 B12 【正确答案】 C【试题解析】 A 错，浮点数阶码溢出时浮点数溢出。
21、 B 错，无符号数也可能溢出。D 错，变形补码，即用两个二进制位来表示数字的符号位，用 “00”表示正，用“11”表示负，也称为模 4 的补码，其余与补码相同。符号位左边那一位表示正确的符号，0 为正，1 为负；右边那一位如果和左边的相同，则无溢出。如果右边那一位与左边那一位不一样，则表示有溢出。它并不能避免溢出的发生，只是使判断溢出更方便而已。13 【正确答案】 C【试题解析】 A 错，虚拟存储器技术是为了解决主存容量不足问题的，并不能提高计算机速度。B 错，主存地址只需 log2(2n+2m)位。D 错，存取时间指从启动一次存储器操作到完成该操作所经历的时间。具体来讲，从一次读操作命令发出
22、到该操作的完成，将数据读人数据缓冲寄存器所经历的时间，即为存储器存取时间。存储周期是指连续两次存取操作所需间隔的最短时间。需要指出的是，存取时间和存储周期不一样，而通常，存储周期略大于存取时间。D 所说的是存取周期而非存取时间。14 【正确答案】 D15 【正确答案】 A【试题解析】 总线(Bus)是计算机各种功能部件之间传送信息的公共通信干线，它是由导线组成的传输线束。采用总线结构的主要优点：(1)简化了硬件的设计。便于采用模块化结构设计方法，面向总线的微型计算机设计只要按照这些规定制作 CPU 插件、存储器插件以及 IO 插件等，将它们连人总线就可工作，而不必考虑总线的详细操作。(2)简化
23、了系统结构。整个系统结构清晰。连线少，底板连线可以印制化。(3)系统扩充性好。一是规模扩充，规模扩充仅仅需要多插一些同类型的插件。二是功能扩充，功能扩充仅仅需要按照总线标准设计新插件，插件插入机器的位置往往没有严格的限制。(4)系统更新性能好。因为 CPU 存储器、IO 借口等都是按总线规约挂到总线上的，因而只要总线设计恰当，可以随时随着处理器的芯片以及其他有关芯片的进展设计新的插件，新的插件插到底板上对系统进行更新，其他插件和底板连线一般不需要改。(5)便于故障诊断和维修。用主板测试卡可以很方便找到出现故障的部位，以及总线类型。采用总线结构的缺点：(1)利用总线传送具有分时性。当有多个主设备
24、同时申请总线的使用是必须进行总线的仲裁。(2)总线的带宽有限，如果连接到总线上的个硬件设备没有资源调控机制容易造成信息的延时(这在某些即时性强的地方是致命的)。(3)连到总线上的设备必须有信息的筛选机制，要判断该信息是否是传给自己的。16 【正确答案】 A【试题解析】 x 的符号位为 1 知 x 为负数，又 x-2 n-1 即 x 的绝对值小于 2n-1 所以Xn-1 必须为 0。17 【正确答案】 B18 【正确答案】 C19 【正确答案】 B【试题解析】 双端口存储器是指同一个存储器具有两组相互独立的读写控制线路。当两个端口的地址不相同时，在两个端口上进行读写操作，一定不会发生冲突。当两个
25、端口同时存取存储器同一存储单元时，便发生读写冲突。为解决此问题，特设置了 BUSY 标志。由片上的判断逻辑决定对哪个端口优先进行读写操作，而暂时关闭另一个被延迟的端口。20 【正确答案】 D【试题解析】 A 程序计数器：指示当前指令的地址。 B 累加寄存器：累加。C 中断寄存器：保存中断字。D 程序状态字：保存机器运行状态。21 【正确答案】 D【试题解析】 A 错，微程序控制器和硬布线控制器各有其优点，不可能一方完全取代另一方。B 错，堆栈是按先入后出的方式访问的。C 错，计数器定时查询方式下，通过设定计数初值，设备的优先级是可变的。22 【正确答案】 C23 【正确答案】 B【试题解析】
26、A 是多用户操作系统区别于其他操作系统的特点。24 【正确答案】 D【试题解析】 进程间是独立的，这表现在内存空间，上下文环境；线程运行在进程空间内。一般来讲(不使用特殊技术)进程是无法突破进程边界存取其他进程内的存储空间；而线程由于处于进程空间内，所以同一进程所产生的线程共享同一内存空间。同一进程中的两段代码不能够同时执行，除非引入线程。线程是属于进程的，当进程退出时该进程所产生的线程都会被强制退出并清除。线程占用的资源要少于进程所占用的资源。进程和线程都可以有优先级。进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动，进程是系统进行资源分配和调度的一个独立单位，线程是进程的一个实
27、体，是 CPU 调度和分派的基本单位，它是比进程更小的能独立运行的基本单位；不同进程可并发不可并行，不同线程可并行。25 【正确答案】 D26 【正确答案】 D【试题解析】 软连接(符号链接)有自己的 inode 和数据块，它的数据块当中的内容为所要连接的文件的绝对或者相对路径。而硬连接(物理连接)和它所要连接的文件共有同一个 inode 和数据块。链接是 UNIX 文件系统提供了一种将不同文件链接至同一个文件的机制。它可以使得单个程序对同一文件使用不同的名字。这样的好处是文件系统只存在一个文件的副本。系统简单地通过在目录中建立一个新的登记项来实现这种连接，该登记项具有一个新的文件名和要连接文
28、件的 inode 号。文件的目录登记项就是所谓的文件硬链接。不论一个文件有多少硬链接，在磁盘上只有一个描述它的 inode。只要该文件的链接数不为 0，该文件就保持存在。27 【正确答案】 C【试题解析】 在 t+2 秒时刻，p1 执行了 2 秒，此时 p2 开始执行由于它和 p1 按时间片轮转算法执行，故在 3 秒(此时 p2 执行了 2 秒，p1 执行了 1 秒)后即 t+5 秒时刻 p2 执行结束， p1 还需 2 秒才能结束，此时只有进程 p1 故 p1 执行到时刻 t+7秒结束。故选 C。28 【正确答案】 B【试题解析】 B 选项，进程 P 申请资源 4 时，由于 4 已分配给了进
29、程 Q 故进程P 不能获得足够资源运行始终等待进程 Q 释放 4，而进程 Q 已获得资源 5、4 还需资源 2、3 才能运行结束，而资源 3 已分配给进程 P 故 Q 也始终等待进程执行完毕释放资源，故进程 P 和 Q 相互等待对方释放已占有的资源而发生死锁现象。29 【正确答案】 A【试题解析】 Belady 现象是指：采用 FIFO 算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。其根本原因是程序的局部性原理，导致一段时间内程序中的某条指令被执行，不久之后该指令可能再次被执行，而此时这条需要再执行的指令所在的页面可能刚刚才被换出，此时
30、又得换入。30 【正确答案】 D【试题解析】 复制文件操作完成之后磁盘的还可容纳存储数据的磁盘空闲空间肯定减小，但是磁盘空闲块数可能增加、减小或不变。31 【正确答案】 B【试题解析】 1 分钟内 CPU 用于打印的时间是 ptime=204 0005010-6s，所以 1分钟内 CPU 用于打印的开销是 ptlme60 s=460=115；故选 B。32 【正确答案】 C33 【正确答案】 C【试题解析】 网络协议三要素：语法，用来规定信息格式；语义，用来说明通信双方应当怎么做；时序，详细说明事件的先后顺序。34 【正确答案】 A【试题解析】 物理层协议要解决的是主机、工作站等数据终端设备与
31、通信设备之间的接口问题。ISO 将上两种设备分别称为 DTE(插头)和 DCE(插座)；RS232-C是美国电子工业协会与 1973 年提出的串行通信接口标准，用于 DTE 和 DCE 之间的接口标准。定义在 ISO7 层参考模型中的物理层。35 【正确答案】 A【试题解析】 设帧的大小为 n bit，则题目可表达为 (n(410 3)(n (410 3)+22010-3) =05，解出 n=160；故选 A。36 【正确答案】 B【试题解析】 SNMP 是“简单网络管理协议”，是一系列协议组和规范，它们提供了一种从网络上的设备中收集网络管理信息的方法。SNMP 被设计成与协议无关，所以它可以
32、在 IP、IPX、AppleTalk、OSI 以及其他用到的传输协议上被使用。故选 B。37 【正确答案】 B【试题解析】 报头长度占 4 位，可表示的最大数值是 15 个单位，1 个单位为 4 字节。故 IP 的首部长度最大值是 60 字节。当首部无选项和填充时首部只有固定的部分(20)字节，此时报头长度的数值为 204=5；故选 B。38 【正确答案】 B【试题解析】 以主机 A(19216815)向主机 B(19216811)发送数据为例。当发送数据时，主机 A 会在自己的 ARP 缓存表中寻找是否有目标 IP 地址。如果找到了，也就知道了目标 MAC 地址，直接把目标 MAC 地址写入
33、帧里面发送就可以了；如果在 ARP 缓存表中没有找到目标 IP 地址，主机 A 就会在网络上发送一个广播，A 主机 MAC 地址是“主机 A 的 MAC 地址”，这表示向同一网段内的所有主机发出这样的询问：“我是 19216815，我的硬件地址是主机 A 的 MAC地址。请问 IP 地址为 19216811 的 MAC 地址是什么?”网络上其他主机并不响应 ARP 询问，只有主机 B 接收到这个帧时，才向主机 A 做出这样的回应：“19216811 的 MAC 地址是 00-aa-00-62-c6-09”。这样，主机 A 就知道了主机 B 的 MAC 地址，它就可以向主机 B 发送信息了。同时
34、 A 和 B 都更新了自己的ARP 缓存表 (因为 A 在询问的时候把自己的 IP 和 MAC 地址一起告诉了 B)，下次A 再向主机 B 或者 B 向 A 发送信息时，直接从各自的 ARP 缓存表里查找就可以了。39 【正确答案】 B【试题解析】 窗口是实现端到端传送的主要机制，发送端窗口大小决定了发送的信息量，而且发送的数据如果出错，可以从发送窗口中重传。40 【正确答案】 B【试题解析】 应用层的数据首先加上 TCP 首部构成 TCP 数据段，接着又加上 IP首部构成 IP 数据报，紧接着把 IP 数据报加上帧头和帧尾构成 MAC 帧，最后转化为比特流在物理层上传送。二、综合应用题41-
35、47 小题，共 70 分。41 【正确答案】 用前插入法建立带头结点的双向循环链表。算法描述如下：DCLink*Created(int tag)int x；DCLink* p=NULL；*建立表头*DCLink*head=(DCLink*)malloc(sizeof(DLLink)；head-next=head；head-prior=head；head-data=tag；*插入数据*printf(“input X：n”)；scanf(“d”，&x)；while(x!=tag)p=(DCLink*)malloc(sizeof(DLLink)；申请空间p- data=x；赋值*在表头部插入结点*p
36、- next=head-next ；head-next-prior=p；p-prior=head；head-next=p ；scanf(“d“，&x)；return head；42 【正确答案】 判定二叉树是否为二叉排序树是建立在二叉树中序遍历的基础上，在遍历中附设一指针 pre 指向树中当前访问结点的中序直接前驱，每访问一个结点就比较前驱结点 pre 与该结点是否有序。若遍历结束后各结点和其中序直接前驱结点均满足有序，则此二叉树即为二叉排序树，否则不是二叉排序树。void BisortTree(Bitree*T，Bitree*pre，int&flag)*初始时 pre=NULL，flag=1
37、，若结束时 flag=1，则此二叉树为排序二叉树*if(T!=NULL&flag=-1)BisortTree(T-lchild ， pre，flag) ；遍历左子树if(pre=NULL)访问中序序列的第一个结点时，不需要比较flag=1；pre=T；else比较 T 与中序直接前驱 pre 的大小if(pre-dataT-data)pre 与 T 有序flag=1；pre=T；elsepre 与 T 无序flag=0；BitsortTree(T-rchild，pre，flag) ；遍历右子树43 【正确答案】 磁盘转速为 15 000 转分钟，即 250 转秒，故其平均旋转等待时间为(1 2
38、)(1250)=0002 s=2 ms读写一个扇区时，数据传输率为最大数据传输率，即 40 MBs ，故读写一个扇区所需的数据传输时间为4 KB(40 MBs)=0 000 1 s=01 ms根据题意，读写一个扇区的平均时间为平均旋转等待时间+平均寻道时间+ 数据传输时间+ 磁盘控制器开销=2 ms+4 ms+01 ms+1 ms=7 1 ms44 【正确答案】 45 【正确答案】 46 【正确答案】 (1)页面长度为 1 KB=210B，因此页内偏移地址占 10 位。主存大小为 16 KB=214B，所以物理地址占 14 位。0AC5H=0000101011000101 B，除去后 10位，
39、得到页号为 2，则查找页表可知物理块号为 4，所以物理地址是01001011000101 B。1AC5H=0001101011000101 B，除去后 10 位，得到页号为 6，则查找 TLB 可知物理块号为 2，所以物理地址是 00101011000101 B。 (2)第一次读TLB 没找到所需页表项，然后读了页表，读完页表后再读所需物理块，共需 2 次内存访问；第二次读 TLB 找到了所需的页表项，直接去读页表项指示的物理块，只需 1 次内存访问。两次访问总共耗时=152+15=45(ns)47 【正确答案】 (1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到
40、100 Mbps 的数据传送速率，需要线路达到 200 Mbps 的带宽。(2)以太网的最小帧长度是 64 字节，那么发送一个最小帧需要的时间T1=648(10010 6)，设网络的最大长度为 L，那么信号沿网络传输一个来回的时间 T2=2L(20010 6)，T1=T2，则可以得到 T2 的最大长度为 544 m。 (3)在以太网中发送数据，首先要知道对方的以太网地址。所以主机 A 需要先发送 ARP 帧来获得主机 C 的物理地址。 (4)ARP 采用了以太网的广播功能，使用全1的地址作为目的地址，即： FFFFFFFFFF FF ，源地址为主机 A 的地址：DE24 E4EF C5B2，类型为 ARP 的类型值：0806。
