一、单项选择题下列每题给出的四个选项中,只有一个选项最符合试题要求。1. 设n是描述问题规模的非负整数,下面程序片段的时间复杂度是______。
order(int j,int m)
{
int i,temp;
if(j<m)
{
for(i=j;i<=n;i++)
if(a[i]<a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
j++;
order(j,m); //递归调用
}
}
- A.O(n)
- B.O(nlog2n)
- C.O(n2)
- D.O(n3)
A B C D
C
[解析] order()函数是一个递归排序过程,设T(n)是排序n个元素所需要的时间。当排序n个元素时,算法的计算时间主要花费在递归调用order()上。第一次调用时,处理的元素序列个数为n-1,也就是对余下的n-1个元素进行排序,所需要的计算时间应为T(n-1)。又因为在其中的循环中,需要进行n-1次比较,所以排序n个元素所需要的时间为:
T(n)=T(n-1)+n-1,n>1
因此得到如下方程:
T(1)=0
T(n)=T(n-1)+n-2 n>1
求解过程为:
12. 下列关于二叉排序树的说法正确的是______。
Ⅰ.向二叉排序树中插入一个结点,所需要比较的次数可能大于此二叉排序树的高度
Ⅱ.二叉排序树一定是平衡二叉树
Ⅲ.删除二叉排序树中的一个结点,再重新插入,一定能得到原来的二叉排序树
Ⅳ.平衡二叉树是指左、右子树的高度差的绝对值不大于1的二叉树
A B C D
D
[解析] 在排序二叉树上进行比较,走的是从跟到叶子结点的路径,有可能中途结束比较,所以比较次数小于或等于树的高度,因此Ⅰ错。
平衡二叉树是指任意结点的左、右子树高度差小于等于1的排序二叉树,因此平衡二叉树属于并不等于排序二叉树,Ⅱ错。
如图所示展示了删除结点4后又重新插入的过程,显然没有得到原来的树,因此Ⅲ错。
根据Ⅱ的讲解可知,Ⅳ错。
26. 如下程序在页式虚存系统中执行,程序代码位于虚空间0页,A为128*128的数组,在虚空间以行为主序存放,每页存放128个数组元素。工作集大小为2个页框(开始时程序代码已在内存,占1个页框),用LRU算法,下面两种对A初始化的程序引起的页故障数分别为______。
程序1:
for(j=1; j<=128; j++)
for(i=1; i<=128; i++)
A[i][j]=0;
程序2:
for(i=1; i<=128; i++)
for(j=1; j<=128; j++)
A[i][j]=0;
- A.128*128,128
- B.128,128*128
- C.64,64*64
- D.64*64,64
A B C D
A
[解析] 本题考查缺页中断的计算。进程的工作集是2个页框,其中一个页框始终被程序代码占用,所以可供数据使用的内存空间只有一个页框。在虚空间以行为主序存放,每页存放128个数组元素,所以每一行占一页。程序1访问数组的方式为先行后列,每一次访问都是针对不同的行,所以每一次都会产生缺页中断,一共128×128次。程序2访问数组的方式是先列后行,每次访问不同行时会产生缺页中断,一共128次。
29. 下列说法正确的是______。
Ⅰ.当各边的权值相等时,广度优先遍历算法可用来解决单源最短路径问题
Ⅱ.广度优先遍历算法可用来求无向图的所有连通分量
Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
A B C D
A
[解析] Ⅰ:对于无权图,广度优先搜索总是按照距离源点由近到远来遍历图中每个顶点(这里的距离是指当前顶点到源点路径上顶点的个数),如图所示。图中各顶点分布在3个层上,同一层上的顶点距离源点的距离是相同的。广度优先搜索就是沿着从1~3的层次顺序来遍历各个顶点,并在遍历的过程中形成了一棵树,称之为广度优先搜索生成树,树的分支总是连接不同层上的顶点,如图中粗线所连。由源点沿生成树分支到达其余顶点的距离都是最近的(可以用层号来描述其远近)。因此对于无权图,可用广度优先搜索遍历的方法来求最短路径。而对于有权图,当图中各个边的权值相同的时候,就可以类比为无权图(无权图可理解为各边权值为1),因为各边没有了权的大小之分,则同样可以用广度优先搜索遍历的方式来求最短路径,所以Ⅰ正确。
Ⅱ:从图中的一个顶点进行广度优先搜索可以将与这个顶点连通的顶点全部遍历到,也就找到了该顶点所在的连通分量,因此广度优先遍历可以求出无向图的所有连通分量,所以Ⅱ正确。
Ⅲ:广度优先遍历算法应该是类似于树中的层次遍历算法,所以Ⅲ错误。
综上所述,Ⅰ、Ⅱ正确。
31. 在双链表中p所指的结点之前插入一个结点q的操作为______。
- A.p→prior==q;q→next=p;p→prior→next=q;q→prior=p→prior;
- B.q→prior=p→prior;p→prior→next=q;q→next=p;p→prior=q→next;
- C.q→next=p;p→next=q;q→prior→next=q;q→next=p;
- D.p→prior→next=q;q→next=p;q→prior=p→prior;p→prior=q;
A B C D
D
[解析] 其实这种题目大部分考生都见过,解题步骤都是固定的。先画图,将选项给出的代码逐个进行检查,看看是否存在断链或者赋值错误的情况。但是这种题型有一种万能的解法,可以应对算法题。如果此题是算法题,考生可将此题的答案按照下面所给的解题技巧轻松地写出,完全不必担心步骤是否会发生错误。
解题技巧:这种题目的目的仅仅是需要把一个结点插进两个结点之间即可,答案肯定是不唯一的。但是我们应该从一些正确的答案中挑选出一个万能的插入公式,只要遇到这种题目,就能迎刃而解了。
例题:假设在双链表中p所指的结点之后插入一个结点s,其操作语句描述为
s->next=p->next; s->prior=p; p->next=s; s->next->prior=s;
指针的变化过程如图所示。
双链表结点的插入过程
说明:不知道大家有没有注意到,在插入时,如果按照上面的顺序来插入,可以看成是一个万能的插入方式。不管怎样,先将要插入的结点两边链接好,这样可以保证不会发生链断之后找不到结点的情况。所以考生们一定要记住这种万能插入结点的方式。
二、综合应用题本大题共70分。一台路由器的路由表中有以下的(CIDR)表项(见下表)。1. 如果到达分组的目标IP地址分别为161.40.63.10、161.40.52.2和192.53.56.7,路由器会执行什么操作。
对于目标地址为161.40.63.10的分组:
(60)10=(111100)2
(63)10=(111111)2
因此会被发送至端口1。
对于目标地址为161.40.52.2的分组:
(56)10=(111000)2
(52)10=(110100)2
因此会被发送至路由器2。
对于目标地址为192.53.56.7的分组:
(40)10=(101000)2
(56)10=(111000)2
因此会被发送至路由器2。
2. 若该路由器去往网络191.7.96.0/21、191.7.104.0/21、191.7.112.0/21用同一输出线路,都往路由器3送,则该如何增加路由表项,能否汇聚成一条?
路由表 |
地址/掩码 | 下一跳 |
161.40.60.0/22 | 端口1 |
161.40.56.0/22 | 端口2 |
192.53.40.0/23 | 路由器1 |
0.0.0.0/0 | 路由器2 |
对于题目给出的三个地址:191.7.96.0/21、191.7.104.0/21、191.7.112.0/21,分析其中的96、104和112段,则有:
(96)10=(01100000)2
(104)10=(01101000)2
(112)10=(01110000)2
即转化为二进制后,前三位均为011;之后两位分别为00、01、10,数据相邻,因此可以合并为011XX。所以答案为能合并。并且可知需要增加的表项为[191.7.96.0/19,下一跳路由器3]。
使用散列函数hashf(x)=xmod11,把一个整数值转换成散列表下标,现要把数据:1,13,12,34,38,33,27,22插入到散列表中。3. 使用链地址的冲突处理方法来构造散列表。
采用链地址法构造散列表时,在直接计算出关键字对应的哈希地址后,将关键字结点插入到此哈希地址所在的链表中。由hashf(x)=xmod11可知,散列地址空间是0到10。链地址法构造的表如下:
4. 分别计算等概率情况下,查找成功和查找不成功所需的平均探查长度。(假设探查到空结点也算一次探查)
在链地址表中查找成功时,查找关键字为33的记录需进行1次探测,查找关键字为22的记录需进行2次探测,依此类推。因此:
ASL成功=(1×4+2×3+3)/8=13/8
查找失败时,假设对空结点的查找长度为1,则对于地址0,查找失败的探测次数为3;对于地址1,查找失败的探测次数为4,则平均探查长度为:
ASL失败=(3+4+2+1+3+1+1+1+1+1+1)/11=19/11
5. 若查找关键字34,则需要依次与哪些关键字比较。
由第一小题可知,查找关键字34,需要依次与关键字1,12,34进行比较。
对同样一组关键字,设定相同的散列函数,则不同处理冲突方法将得到不同的散列表,它们的平均查找长度也不同,本题若采用线性探查法处理冲突,题目应如何解答?
根据图1描述的目录结构,结合以下叙述继续回答问题。根目录常驻内存,目录文件组织成链接文件,不设文件控制块,普通文件组织成索引文件。目录表目指示下一级文件名及其磁盘地址(各占2个字节,共4个字节)。若下级文件是目录文件,指示其第一个磁盘块地址。若下级文件是普通文件,指示其文件控制块的磁盘地址。每个目录文件磁盘块的最后4个字节供拉链使用。下级文件在上级目录文件中的次序在图中为从左至右。每个磁盘块有512字节,与普通文件的一页等长。
普通文件的文件控制块组织如图2所示,其中,每个磁盘地址占2个字节,前10个地址直接指示该文件前10页的地址。第11个地址指示一级索引表地址,一级索引表中每个磁盘地址指示一个文件页地址;第12个地址指示二级索引表地址,二级索引表中每个地址指示一个一级索引表地址;第13个地址指示三级索引表地址,三级索引表中每个地址指示一个二级索引表地址。请问:
6. 一个普通文件最多可有多少个文件页?
因为磁盘块大小为512B,所以索引块大小也为512B,每个磁盘地址大小为2B。因此,一个一级索引表可容纳256个磁盘地址。同样,一个二级索引表可容纳256个一级索引表地址,一个三级索引表可容纳256个二级索引表地址。这样,一个普通文件最多可有文件页数为10+256+256×256+256×256×256=16843018页。
7. 若要读文件J中的某一页,最多启动磁盘多少次?
由图可知,目录文件A和D中的目录项都只有两个,因此这两个目录文件都只占用一个物理块。要读文件J中的某一页,先从内存的根目录中找到目录文件A的磁盘地址,将其读入内存(已访盘1次)。然后从目录A中找出目录文件D的磁盘地址并将其读入内存(已访盘2次)。再从目录D中找出文件J的文件控制块地址并将其读入内存(已访盘3次)。在最坏情况下,该访问页存放在三级索引下,此时需要一级一级地读三级索引块才能得到文件J的地址(已访盘6次)。最后读入文件J中的相应页(共访盘7次)。所以,若要读文件J中的某一页,最多启动磁盘7次。
8. 若要读文件W中的某一页,最少启动磁盘多少次?
由图可知,目录文件C和U的目录项较多,可能存放在多个链接在一起的磁盘块中。在最好情况下,所需的目录项都在目录文件的第一个磁盘块中。先从内存的根目录中找到目录文件C的磁盘地址读入内存(已访盘1次)。在C中找出目录文件I的磁盘地址读入内存(已访盘2次)。在I中找出目录文件P的磁盘地址读入内存(已访盘3次)。从P中找到目录文件U的磁盘地址读入内存(已访盘4次)。从U的第一个磁盘块中找出文件W的文件控制块地址读入内存(已访盘5次)。在最好情况下,要访问的页在文件控制块的前10个直接块中,按照直接块指示的地址读文件W的相应页(已访盘6次)。所以,若要读文件W中的某一页,最少启动磁盘6次。
9. 就上一小题而言,为最大限度减少启动磁盘的次数,可采用什么方法?此时,磁盘最多启动多少次?
为了减少启动磁盘的次数,可以将需要访问的W文件挂在根目录最前面的目录项中。此时,只需读内存中的根目录就可以找到W的文件控制块,将文件控制块读入内存(已访盘1次),最差情况下,需要的W文件的那个页挂在文件控制块的三级索引下,那么读3个索引块需要访问磁盘3次(已访盘4次)得到该页的物理地址,再去读这个页即可(已访盘5次)。此时,磁盘最多启动5次。
[解析] 本题考查文件目录的结构。
10. 假定磁盘传输数据以32位的字为单位,传输速率为1MB/s。CPU的时钟频率为50MHz。
(1)使用程序查询的输入输出方式,一个查询操作需要100个时钟周期,求CPU为I/O查询所花费的时间比率,假定进行足够的查询以避免数据丢失。
(2)用中断方式进行控制,每次传输的开销(包括中断处理)为100个时钟周期,求CPU为传输磁盘数据花费的时间比率。
(3)采用DMA控制进行输入输出操作,假定DMA的启动操作需要1000个时钟周期。 DMA完成时处理中断需要500个时钟周期,如果平均传输的数据长度为4KB,问在磁盘工作时处理器将用多少时间比率进行输入输出操作,忽略DMA申请使用总线的影响。
根据题意可知,每传送一个字需要4μs,CPU的时钟周期为0.02μs。
(1)程序查询的输入输出方式,一个查询操作需要100个时钟周期,而时钟周期=0.02μs,所以每个查询操作需要2μs,CPU为I/O查询所花费的时间比率为0.02×100/4=1/2=0.5。
(2)用中断方式法进行控制,每次传输的开销(包括中断处理)为100个时钟周期,而时钟周期=0.02μs,所以每次传输的开销时间=100×0.02=2μs,传送一个字的时间为4μs,CPU为传输磁盘数据花费的时间比率为0.02×100/4=1/2=0.5。
(3)采用DMA控制进行输入输出操作,平均传输的数据长度为4KB,根据数据传输率,传送时间4KB÷1 MB/s=4ms。又由于DMA的启动操作需要1000个时钟周期,即1000×0.02=20μs;DMA完成时处理中断需要500个时钟周期,即500×0.02=10μs。所以在磁盘工作时CPU为进行输入输出操作花费的时间比率为0.02×1500/4000=30/4000=0.0075。
一个磁盘机有19,456个柱面,16个读写磁头,并且每个磁道有63个扇区。磁盘以5400rpm的速度旋转。试问:11. 如果磁盘的平均寻道时间是10ms,那么读一个扇区的平均时间是多少?
读一个扇区的平均等待时间为旋转半周的时间,即为(60/5400)/2=5.55ms,传输时间为(60/5400)/63=0.18ms,因此读一个扇区的平均时间为5.55+0.18+10=15.73ms。
12. 在一个请求分页系统中,若将该磁盘用作交换设备,而且页面大小和扇区的大小相同。读入一个换出页的平均时间和上面计算的相同。假设如果一个页必须被换出,则寻找换入页的平均寻道时间将只有1ms,那么传输这两个页的平均时间是多少?
换出页时间为15.73ms,换入页时间1+5.55+0.18=6.73,传输这两个页的平均时间为6.73+15.73=22.46ms。
13. 如果在该系统中打开的文件数目远远多于驱动器的数目时,对磁盘机有什么影响?
可能会产生两个后果,第一个后果是“饥饿”,这是由于请求磁盘I/O操作的应用程序得不到满足而长时间在阻塞队列等待,从而导致“饥饿”;第二个后果是“抖动”,由于每次磁盘I/O操作完成后,都要进行磁盘的换入换出,从而导致“抖动”。
[解析] 本题考查磁道的性能指标和特点。
14. 给出将一个正整数字符串转化为对应的整数值的递归描述。
递归出口:
(1)若给出的字符串是空串,则返回一个标记指明无法转换。
(2)若给出的字符串长度为1,则直接转换为对应的整数。
递归:
若给出的字符串长度大于1,则:
1)先将串尾的字符转化为对应的整数。
2)递归的转化除串尾字符的子串,并将转化结果乘以10后与串尾字符的转化结果相加得到最终结果。
一个公司有两个部门:研发部和市场部,研发部有29台计算机,市场部有11台计算机。公司申请了一个C类地址212.112.32.0,规划的网络拓扑如图所示。试问:
规划的网络拓扑
15. 请给出合理的子网规划,并说明理由,然后将规划填入下表。
子网规划表 |
子网号 | 子网掩码 | 子网网络地址 | 子网广播地址 | 子网网络地址范围 |
NO.A | | | | |
NO.B | | | | |
NO.C | | | | |
其他 | | | | |
子网规划表
|
子网号
|
子网掩码
|
子网网络地址
|
子网广播地址
|
子网网络地址范围
|
NO.A
|
255.255.255.224
|
212.112.32.32
|
212.112.32.63
|
212.112.32.33~212.112.32.62
|
NO.B
|
255.255.255.224
|
212.112.32.64
|
212.112.32.95
|
212.112.32.65~212.112.32.94
|
NO.C
|
255.255.255.224
|
212.112.32.96
|
212.112.32.127
|
212.112.132.97~212.112.32.126
|
16. 根据第一小题的规划,为两个路由器的接口和各台计算机分配IP地址。
下面对第一小题中划分好的3个子网进行规划。将网络212.1 12.32.32分给研发部,记为子网A;网络212.112.32.64分给两个路由器之间的那条链路,记为子网B;网络212.112.32.96分给市场部,记为子网C下面为路由器的端口及其各主机分配IP地址。
路由器R1的E0端口:该端口属于子网A,给其分配的IP地址为:212.112.32.33。
路由器R1的S0端口:该端口属于子网B,给其分配的IP地址为:212.112.32.65。
路由器R2的E0端口:该端口属于子网B,给其分配的IP地址为:212.112.32.66。
路由器R2的S0端口:该端口属于子网C,给其分配的IP地址为:212.112.32.97。
研发部的29台主机:212.112.32.34~212.112.34.62,恰好29个IP地址。
市场部的11台主机:212.112.32.98~212.112.32.126,随机选11个IP地址。
17. 如果路由器R1和R2都采用了路由信息协议(Routing Information Protocol,RIP)作为路由选择协议,当稳定运行之后,R1的路由表是怎样的?请填写下表。
R1的路由表 |
目的网络地址 | 接口 | 下一跳 | 度量 |
| | | |
| | | |
| | | |
注:度量是一个通用的词语,如果采用RIP,度量即表示跳数:如果采用其他协议,度量就可能是其他含义。 |
R1的路由表
|
目的网络地址
|
接口
|
下一跳
|
度量
|
212.112.32.32
|
E0
|
-
|
0
|
212.112.32.64
|
S0
|
-
|
0
|
212.112.32.96
|
S0
|
212.112.32.66
|
1
|
18. 当路由器R1的接口E0断掉了,经过一次信息交互之后,R1的路由表发生了怎样的变化?请填写下表。
交互后R1的路由表 |
目的网络地址 | 接口 | 下一跳 | 度量 |
| | | |
| | | |
| | | |
交互后R1的路由表
|
目的网络地址
|
接口
|
下一跳
|
度量
|
212.112.32.32
|
S0
|
212.112.32.66
|
2
|
212.112.32.64
|
S0
|
—
|
0
|
212.112.32.96
|
S0
|
212.112.32.66
|
1
|