1、计算机专业（基础综合）模拟试卷 102及答案解析(总分：138.00，做题时间：90 分钟)一、单项选择题(总题数：41，分数：82.00)1.单项选择题 1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_2.假设 n是描述问题规模的非负整数，下面程序片段的时间复杂度为( )。void fun(int n)int i，j，k；for(i=1;i=n;i+)for(j=1;j=n;j+)k=1；while(k=n k=5*k; （分数：2.00）A.O(n 2 log 2 n)B.O(nlog 5 n)C.O(n 2 log 5 n)D.O(n 3 )3
2、.以下说法正确的是( )。带头结点的循环双链表 L为空的条件是：Lprior=Li=n;i+)for(j=1;j=n;j+)k=1；while(k=n k=5*k; （分数：2.00）A.O(n 2 log 2 n)B.O(nlog 5 n)C.O(n 2 log 5 n) D.O(n 3 )解析：解析：首先抓基本运算语句，即 k=5*k；设其执行时间为 T(n)。对于 j每循环一次，该语句的执行次数为 m，有 5 m n，即 mlog 5 n。所以， T(n)= n i=1 n j=1 m=m n i=1 n j=1 =mn 2 =n 2 log 5 n=O(n 2 log 5 n)3.以下
3、说法正确的是( )。带头结点的循环双链表 L为空的条件是：Lprior=L 关键字序列 void heap() int i=n2； 找到最后一个结点的父母结点 if(n2=1) 当 n是右结点时 if(KiKn=1Kn-1Kn)swap(Kn-i，Ki)；swap()实现交换两个元素 if(KiKnKn-1Knswap(K(n，Ki)； else 当 n是左结点 if(KiKn)swap(Kn，Ki)； i=i2； while(i0) 依次向上调整 if(KiKn-1Kn-1Kn)swap(Kn-1，Ki)； if(KiKn&Kn-1Kn)swap(Kn，Ki)；i=i2； )解析：(3).说
4、明你所设计算法的时间复杂度。（分数：2.00）_正确答案：(正确答案：时间复杂度分析：在循环当中，我们可以看出每次都是对结点的父母结点进行调整，因此操作次数正好是树的高度，时间复杂度为 O(log 2 n)。)解析：假设一个主频为 1GHz、CPI 为 5的 CPU需要从某个成块传送的 IO 设备读取 1000B的数据到主存缓冲区中，该 IO 设备一旦启动即按 50KBs 的数据传输率向主机传送 1000B数据，每个字节的读取、处理并存入内存缓冲区需要 1000个时钟周期，则以下 4种方式下，在 1000B的读取过程中，CPU 用在该设备的IO 操作上的时间分别为多少?占整个 CPU时间的百分
5、比分别是多少?（分数：10.00）(1).采用定时查询方式，每次处理一个字节，一次状态查询至少需要 60个时钟周期。（分数：2.00）_正确答案：(正确答案：主频为 1GHz，所以时钟周期为 11GHz=1ns。因为每个字节的读取、处理并存入内存缓冲区需要 1000个时钟周期，所以，对于像程序查询和中断等用软件实现输入输出的方式，CPU为每个字节传送所用的时间至少为 10001ns=1000ns=1s。在 50kBs 的数据传输率下，设备每隔1B50kBs=20s=20000ns 准备好一个字节，因而读取 1000B的时间为 100020s=20ms。 定时查询方式下的 IO 过程如图 7-1
6、2所示。用户可以设置每隔 20000ns查询一次，这样使得查询程序的开销达到最小，即第一次读取状态时就可能会发现就绪，然后用 1000个时钟周期进行相应处理，因此，对于每个字节的传送，CPU 所用时钟周期数为 60+1000=1060。因此，在 1000B的读取过程中，CPU 用在该设备的IO 操作上的时间至少为 100010601ns=1060ms，占整个 CPU时间的百分比至少为106020=53。 )解析：(2).采用独占查询方式，每次处理一个字节，一次状态查询至少需要 60个时钟周期。（分数：2.00）_正确答案：(正确答案：独占查询方式下的 IO 过程如图 7-13所示。启动设备后，
7、CPU 就开始查询，因为 33360+20=20000，所以第一个字节传送在第 334次读取状态查询时检测到就绪，随后用 1000个时钟周期进行相应的处理，然后继续第二个字节的状态查询，因为 40+1000+31660=20 000，所以，第二个字节的传送在第 316次读取状态查询时检测到就绪，第一个和第二个字节的传送过程如图 7-13a所示。每次检测到就绪后，就进行相应的处理，然后周而复始地进行查询，因为(20000-1000)60=3167，所以，第 317次状态查询时发现就绪。因为 1000+60317-20000=20，所以，每 3B可多 60个时钟周期，正好进行一次状态查询，因此，在
8、剩下的 998B的读取过程中，前 996B的传送正好用了 99620000个时钟周期，如图 7-13b所示。最后两个字节的传送过程如图 7-13c所示，因为 2(1000+60317-20000)=40，此外，最后一个字节的处理还有 1000个时钟周期，所以最后两个字节总的时间为 220000+40+1 000=41 040个时钟周期。 综上所述，CPU 用在该设备的 IO 操作上的总时间为100020000ns+10401ns=2000104ms20ms，即在 1000B的整个传输过程中，CPU 一直为该设备服务，所用时间占整个 CPU时间的 100。 )解析：(3).采用中断 IO 方式，
9、外设每准备好一个字节发送一次中断请求。每次中断响应需要 2个时钟周期，中断服务程序的执行需要 1200个时钟周期。（分数：2.00）_正确答案：(正确答案：中断方式下的 IO 过程如图 7-14所示。中断方式下，外设每准备好一个字节请求一次中断，每次中断 CPU所用时钟周期数为 2+1200=1202，因此 CPU用在该设备的 IO 操作上的时间为 100012021ns=1202ms，占整个 CPU时间的百分比至少为 120220=601。 )解析：(4).采用周期挪用 DMA方式，每挪用一次主存周期处理一个字节，一次 DMA传送完成 1000B的传送，DMA初始化和后处理的时间为 2000
10、个时钟周期，CPU 和 DMA之间没有访存冲突。（分数：2.00）_正确答案：(正确答案：DMA 方式下，由于 CPU和 DMA没有访存冲突，所以不需考虑由于 DMA而影响到 CPU执行其他程序。因此，传送 1000B CPU所用的时钟周期数就是 2000，在 1000B的读取过程中，CPU 用在该设备的 IO 操作上的时间为 20001ns=2s，占整个 CPU时间的百分比为 2(100020)=001。)解析：(5).如果设备的速度提高到 5MBs，则上述 4种方式中，哪些是不可行的?为什么?对于可行的方式，计算出 CPU在该设备 IO 操作上所用的时间占整个 CPU时间的百分比。（分数：
11、2.00）_正确答案：(正确答案：若设备数据传输率为 5MBs，则外设传输 1000B所用时间为 1000B(510 6 Bs)=200us。 对于定时查询和独占查询方式，传送 1000B CPU所用时间至少为 1000(60+1000)1ns=1060s；对于中断方式，传送 1000B CPU所用时间为 1000(2+1 200)1ns=1 202s。上述 3种方式下，CPU 所用的时间都比设备所用时间长得多，即设备的传输比 CPU的处理快得多，因而发生数据丢失。因此，这 3种方式都不能用于该设备的 IO 操作。对于 DMA方式，传送 1000B CPU所用时间为20001ns=2s，占整个
12、 CPU时间的百分比为 2200=1。这说明可以使用 DMA方式，不过由于外设传输速度加快，使得 CPU频繁进行 DMA预处理和后处理，因而 CPU的开销从 001上升到了 1。中断方式的计算，可以先求出 1s内该外设请求的中断次数为 1(1B50kB)=50k，然后得到 1s内 CPU用于数据IO 的时钟周期数为 50k(2+1200)=60110 7 ，因此在该设备传输过程中，CPU 用于该设备 IO 操作的时间占整个 CPU时间的百分比为 60110 7 1G=601。)解析：硬磁盘共有 4个记录面，存储区域内半径为 10cm，外半径为 155cm，道密度为 60道cm，外层位密度为 6
13、00bitcm，转速为 6000rmin。问：（分数：10.00）(1).硬磁盘的磁道总数是多少?（分数：2.00）_正确答案：(正确答案：有效存储区域=155cm-10cm=55cm，道密度=60 道cm，因此每个面 60道cm55cm=330 道，即有 330个柱面，磁道总数=4330 道=1320 道。)解析：(2).硬磁盘的容量是多少?磁盘的非格式化容量和格式化容量是一个什么概念，两者之间有什么关系?（分数：2.00）_正确答案：(正确答案：外层磁道的长度为 2R=2314155cm=9734cm 每道信息量=600bitcm9734cm=58404bit=73005B 磁盘总容量=7
14、3005B1320 道=9636660B(非格式化容量) 磁盘在使用之前要对其执行格式化操作，要首先完成划分磁道和扇区，设置文件目录区等。非格式化容量是指一个盘片上可以记录的二进制位的总数量，而格式化容量通常是指用户可用空间的二进制位的总数量，前者比后者要大，因为系统要管理磁盘会占用一定的存储空间，还要使用一个磁道用于同步，扇区之间还有间隔和一些为保存检错纠错信息的空间，磁盘上往往还会留有一些备份磁道。在谈到磁盘容量时，通常指的是格式化之后用户可用的磁盘容量。)解析：(3).将长度超过一个磁道容量的文件记录在同一个柱面上是否合理?（分数：2.00）_正确答案：(正确答案：如果长度超过一个磁道容
15、量的文件，将它记录在同一个柱面上比较合理，因为不需要重新寻找磁道，这样数据读写速度快。)解析：(4).采用定长数据块记录格式，直接寻址的最小单位是什么?寻址命令中磁盘地址如何表示?（分数：2.00）_正确答案：(正确答案：采用定长数据块格式，直接寻址的最小单位是一个扇区，每个扇区记录固定字节数目的信息，在定长记录的数据块中，活动头磁盘组的编址方式可用如下格式： )解析：(5).假定每个扇区的容量 512B，每个磁道有 12个扇区，寻道的平均等待时间为 105ms，试计算读出磁盘一个扇区中数据的平均时间。（分数：2.00）_正确答案：(正确答案：读一个扇区中数据所用的时间为 找磁道的时间+找扇区
16、的时间+磁头扫过一个扇区的时间 找磁道时间是指磁头从当前所处磁道运动到目标磁道的时间，一般选用磁头在磁盘径向方向上移动 12 个半径长度所用时间为平均值来估算，题中给的是 105ms。 找扇区的时间是指磁头从当前所处扇区运动到目标扇区的时间，一般选用磁盘旋转半周的所用时间作为平均值来估算，题中给出的磁盘转速为 6000rmin，即 100ds，即磁盘转一周用时为 10ms，转半周的时间是 5ms。 题中给出每个磁道有 12个扇区，磁头扫过一个扇区用时为 1012ms=083ms，计算结果应该为 105ms+5ms+083ms=1633ms。 为了减少寻找磁道和等待扇区所占时间的比例，磁盘通常应
17、该以多个扇区为单位进行读写，一旦开始具体的读写操作，就对多个连续的扇区进行顺序读写，读写的数据首先保存到系统设置的一个缓存区中，CPU通常要经过操作系统实现与这个缓冲区交换数据，而不是直接与磁盘设备本身交换数据。)解析：在一个段式存储管理系统中，逻辑地址为 32位，其中高 16位为段号，低 16位为段内偏移，以下是段表(其中的数据均为十六进制，见表 7-1)。 以下是代码段的内容： （分数：12.00）(1).x的逻辑地址为 10108，它的物理地址是多少?（分数：2.00）_正确答案：(正确答案：高 16位为段号，低 16位为段内偏移，则 1为段号(对应基址 11900)，0108 为段内偏
18、移，则逻辑地址 1lA08对应的物理地址为基址加段内偏移，即 11900+0108=11A08。)解析：(2).栈指针的当前地址是 70FF0，它的物理地址是多少?（分数：2.00）_正确答案：(正确答案：7 为段号，0FF0 为段内偏移，13000+0FF0=13FF0。)解析：(3).第一条指令的逻辑地址和物理地址各为多少?（分数：2.00）_正确答案：(正确答案：逻辑地址 240，物理地址为基址加段内偏移，即 10000+240=10240。)解析：(4).push x指令的执行过程：将 SP(堆栈寄存器)减 4，然后存储 x的值。试问 x被存储在什么地方(物理地址)?（分数：2.00）
19、_正确答案：(正确答案：在(2)中，知道 SP对应物理地址为 13FF0，减 4之后为 13FEC，即 x存储地址为13FEC。)解析：(5).call sin指令的执行过程：先将当前 PC值入栈，然后在 PC内装入目标 PC值。试问哪个值被压入栈了?新的栈指针的值是多少?新的 PC值是多少?（分数：2.00）_正确答案：(正确答案：PC 在调用 call sin命令之后，自增为 248，所以逻辑地址 248被压入栈。由第(4)问我们知道，每次入栈栈指针是减少 4，那么将当前 PC值入栈后，则栈指针的值为 70FF0-4-4=70EE8。即新的栈指针值为 70FE8，新的 PC值为 360。)
20、解析：(6).语句“mov r2,4+(sp)”的功能是什么?（分数：2.00）_正确答案：(正确答案：70FE8(sp)+4=70FEC，即 x的逻辑地址，所以功能是访问 x的值，即 sin函数的输入参数。)解析：有一个文件系统如图 7-2所示。其中的方框表示目录，椭圆圈表示普通文件。根目录常驻内存，目录文件组织成链接文件，不设文件控制块，普通文件组织成索引文件。目录表目指示下一级文件名及其磁盘地址(各占 2B，共 4B)。若下级文件是目录文件，指示其第一个磁盘块地址。若下级文件是普通文件，指示其文件控制块的磁盘地址。每个目录文件磁盘块最后 4B供链接地址使用。下级文件在上级目录文件中的次序
21、在图 7-2中为左至右。每个磁盘块有 512B，与普通文件的一页等长。 普通文件的文件控制块组织结构如图 7-3所示，其中每个磁盘地址占 2B，前 10个地址直接指示该文件前 10页的地址。第 11个地址指示一级索引表地址，一级索引表中每个磁盘地址指示一个文件页地址；第 12个地址指示二级索引表地址，二级索引表中每个地址指示一个一级索引表地址；第 13个地址指示三级索引表地址，三级索引表中每个地址指示一个二级索引表地址。 （分数：6.00）(1).adat 文件的绝对路径名和相对路径名。（分数：2.00）_正确答案：(正确答案：S 的绝对路径名为usersadmindownloadadat，S
22、 的相对路径名为downloadadat。)解析：(2).若要读取顺序文件 adat 中的某一页，最少启动磁盘多少次，最多启动磁盘多少次?（分数：2.00）_正确答案：(正确答案：因为当前目录为usersadmin。该目录中有目录 download的磁盘地址，将其读入内存(已访问磁盘一次)。然后从目录 download中找出文件 adat 的文件控制块地址并将文件控制块读入内存(已访问磁盘两次)。 在最好情况下，要访问的页在文件控制块的前 10个直接块中，按照直接块指示的地址读文件 adat 的相应页(已访问磁盘 3次)。所以在最好的情况下，只需启动磁盘 3次。 在最坏情况下，要访问的页存放在
23、三级索引下，这时候需要一级一级地读三级索引块才能得到目标页的地址(已访问磁盘 5次)，最后读入目标页(已访问磁盘 6次)。所以在最坏情况下，需启动磁盘 6次。)解析：(3).如果已知顺序文件 adat 的大小。试问如果要读取该文件的最后一个记录，是否能预估出启动磁盘的次数?若能，请详述过程。（分数：2.00）_正确答案：(正确答案：能。因为给出了 adat 文件的大小，且要访问的位置也给出(文件末尾，也就是文件的最后一页)。通过文件大小，可以算出文件最后一页的地址是在直接块中，还是在第 i级索引块中。若在直接块中，访问次数就是最好情况下的 3次。若在第 i级索引块中，访问次数就是 3+i次。)
24、解析：某时刻，一台 PC开始抓取数据报文，其中一个报文展开如下所示。IP：-IP Header-IP：IP：Version=4，header length=20 bytesIP：Type of service=00IP：000=routineIP： 0=normal delayIP： 0=normal throughputIP： 0=normal reliabilityIP： 0=ECT bit-transport protocolIP： 0=CE bit-no congestionIP：Total length =166 bytesIP：Identification =32897IP：Fla
25、gs =0XIP： .0=may fragmentIP： 0=last fragmentIP：Fragment offset=0 bytesIP：Time to 1ire =64 secondhopsIP： Protocol =17IP：Header checksum=7A58(correct)IP：Source address =17216191IP：Destination address=172162076IP：No optionsIP：试回答以下问题：（分数：10.00）(1).这个报文传输层采用了什么协议?（分数：2.00）_正确答案：(正确答案：从报文当中我们可以看到 Protoco
26、l项是 17，故采用的是 UDP协议。)解析：(2).该 IP数据报的头部是否有选项与域?（分数：2.00）_正确答案：(正确答案：由于 header length=20B，而 IP不包括选项的首部长度为 20B，故该 IP数据报的头部是没有选项域。)解析：(3).这个报文最多经过多少个路由器就会被丢弃?（分数：2.00）_正确答案：(正确答案：由于 time to live=64，故这个报文最多经过 64个路由器就会被丢弃。)解析：(4).该 IP报文的源地址和目的地址是什么?（分数：2.00）_正确答案：(正确答案：显然源 IP地址=17216191，目的 IP地址 172162076。)解析：(5).该报文的总长度是多少?是否被分段?（分数：2.00）_正确答案：(正确答案：显然总长度 166B。由于 flags的 MF=0(last fragment)且 fragment offset=0B，故 IP报文没有被分段。)解析：
