资源描述
1、若元素a,b,c,d,e,f依次进栈,容许进栈、退栈操作交替进行。但不容许持续三次进行退栈工作,则不也许得到的出栈序列是( D )A:dcebfa B:cbdaef C:dbcaef D:afedcb2、某队列容许在其两端进行入队操作,但仅容许在一端进行出队操作,则不也许得到的顺序是( C )A:bacde B:dbace C:dbcae D:ecbad3、下列线索二叉树中(用虚线表达线索),符合后序线索树定义的是( B )4、在下列所示的平衡二叉树中插入核心字48后得到一棵新平衡二叉树,在新平衡二叉树中,核心字37所在结点的左、右子结点中保存的核心字分别是( C )A:13,48 B:24,48 C:24,53 D:24,905、在一棵度为4的树T中,若有20个度为4的结点,10个度为3的结点,1个度为2的结点,10个度为1的结点,则树T的叶节点个数是(B)A:41 B:82 C:113 D:1226、对n(n不小于等于2)个权值均不相似的字符构成哈夫曼树,有关该树的论述中,错误的是(B)A:该树一定是一棵完全二叉树 B:树中一定没有度为1的结点C:树中两个权值最小的结点一定是兄弟结点 D:树中任一非叶结点的权值一定不不不小于下一任一结点的权值7、若无向图G-(V.E)中含7个顶点,则保证图G在任何状况下都是连通的,则需要的边数至少是(A)A :6 B:15 C:16 D:218、对下图进行拓补排序,可以得到不同的拓补序列的个数是(B )A:4 B:3 C:2 D:19、已知一种长度为16的顺序表L,其元素按核心字有序排列,若采用折半查找法查找一种不存在的元素,则比较次数最多是(A)A:4 B:5 C:6 D:710、采用递归方式对顺序表进行迅速排序,下列有关递归次数的论述中,对的的是(D)A:递归次数与初始数据的排列顺序无关B:每次划分后,先解决较长的分区可以减少递归次数C:每次划分后,先解决较短的分区可以减少递归次数D:递归次数与每次划分后得到的分区解决顺序无关11、对一组数据(2,12,16,88,5,10)进行排序,若前三趟排序成果如下(A)第一趟:2,12,16,5,10,88第二趟:2,12,5,10,16,88第三趟:2,5,10,12,16,88则采用的排序措施也许是:A:起泡排序 B:希尔排序 C:归并排序 D:基数排序12、下列选项中,能缩短程序执行时间的措施是(D)I 提高CPU时钟频率,II优化数据通过构造,III对程序进行编译优化A:仅I和II B:仅I和III C:仅II和III D:I,II,III13、假定有4个整数用8位补码分别表达r1=FEH ,r2=F2H ,r3=90H,r4=F8H,若将运算成果寄存在一种8位的寄存器中,则下列运算会发生溢出的是(C)A: r1*r2 B :r2*r3 C:r1*r4 D:r2*r414、假定变量I,f,d数据类型分别为int,float和double(int用补码表达,float和double分别用IEEE754单精度和双精度浮点数据格式表达),已知i=785,f=1.5678,d=1.5若在32位机器中执行下列关系体现式,则成果为真是(C)(I)f=(int)(float)I (II)f=(float)(int)f (III)f=(float)(double) (IV)=(d+f)-d=fA:仅I和II B:仅I和III C:仅II和III D:仅III和IV15、假定用若干个2k*4位芯片构成一种8*8位存储器,则地址0B1FH所在芯片的最小地址是(D)A:0000H B:0600H C: 0700H D:0800H 16、下列有关RAM和ROM的论述中,对的的是(A)I、 RAM是易失性存储器,ROM是非易失性存储器II、 RAM和ROM都是采用随机存取的方式进行信息访问III、RAM和ROM都可用作CacheIV、RAM和ROM都需要进行刷新A:仅I和II B:仅II和III C:仅I,II,III D:仅II,III,IV17、下列命令组合状况中,一次访存过程中,不也许发生的是(D)A:TLB未命中,Cache未命中,Page未命中B:TLB未命中,Cache命中,Page命中C:TLB命中,Cache未命中,Page命中D:TLB命中,Cache命中,Page未命中18、下列存储器中,汇编语言程序员可见的是(B)A:存储器地址寄存器(MAR) B:程序计数器(PC)C:存储器数据寄存器(MDR) D:指令寄存器(IR)19、下列不会引起指令流水阻塞的是(A)A:数据旁路 B:数据有关 C:条件转移 D:资源冲突20、下列选项中的英文缩写均为总线原则的是(D)A:PCI、CRT、USB、EISA B:ISA、CPI、VESA、EISAC:ISA、SCSI、RAM、MIPS D:ISA、EISA、PCI、PCI-Express21、单级中断系统中,中断服务程序执行顺序是(A)I、保护现场 II、开中断 III、关中断 IV、保存断点V、中断事件解决 VI、恢复现场 VII、中断返回A:I、V、VI、II、VIIB:III、I、V、VIIC:III、IV、V、VI、VIID:IV、I、V、VI、VII22、假定一台计算机的显示存储器用DRAM芯片实现,若规定显示辨别率为1600*1200,颜色深度为24位,帧频为85Hz,显示总带宽的50% 用来刷新屏幕,则需要的显存总带宽至少约为(D)A :245 MbpsB:979 MbpsC:1958 MbpsD:7834Mbps23、下列选项中,操作S提供的给应用程序的接口是(A)A:系统调用B:中断C:库函数D:原语24、下列选项中,导致创进新进程的操作是(C)I顾客成功登陆 II设备分派 III启动程序执行A:仅I和IIB:仅II和IIIC:仅I和IIID:I,II,III25、设与某资源有关联的信号量初值为3,目前值为1,若M表达该资源的可用个数,N表达等待资源的进程数,则M,N分别是(B )A:0,1B:1,0C:1,2D:2,026、下列选项中,减少进程优先权级的合理时机是( A )A:进程的时间片用完B:进程刚完毕Z/O,进入就绪队列C:进程长期处在就绪队列中D:就绪从就绪状态转为运营态27、进行P0和P1的共享变量定义及其初值为( A )boolean flag2;int turn=0;flag0=faulse;flag1=faulse;若进行P0和P1访问临界资源的类C代码实现如下:Void p0()/ 进程p0 Void p1()/ 进程p1while(TURE) while(TURE)Flag0=TURE;ture=1 Flag1=TURE; ture=1While (flag1&(turn=1) While (flag0&(turn=0)临界区:Flag0=FALSE; Flag1=FALSE; 则并发执行进程P0和P1时产生的状况是:A:不能保证进程互斥进入临界区,会浮现“饥饿”现象B:不能保证进程互斥进入临界区,不会浮现“饥饿”现象C:能保证进程互斥进入临界区,会浮现“饥饿”现象D:能保证进程互斥进入临界区,不会浮现“饥饿”现象28、某基于动态分区存储管理的计算机,其主存容量为55mb(初试为空间),采用最佳适配(Best fit)算法,分派和释放的顺序为:分派15mb,分派30mb,释放15mb,分派8mb,此时主存中最大空闲分区的大小是( B )A:7mbB:9mbC:10mbD:15mb29、某计算机采用二级页表的分页存储管理方式,按字节编制,页大小为216字节,页表项大小为2字节,逻辑地址构造为页目编号页号页内偏移量逻辑地址空间大小为216页,则表达整个逻辑地址空间的页目录表中涉及表项的个数至少是( B )A:64B:128C:256D:51230、设文献索引节点中有7个地址项,其中4个地址项为直接地址索引,2个地址项是一级间接地址索引,1个地址项是二级间接地址索引,每个地址项大小为4字节,若磁盘索引块和磁盘数据块大小均为256字节,则可表达的单个文献的最大长度是( C )A:33kbB:519kbC:1057kbD:16513kb 31、设立目前工作目录的重要目的是( C )A:节省外存空间B:节省内容空间C:加快文献的检索速度D:加快文献的读写速度32、本地顾客通过键盘登录系统时,一方面获得键盘输入信息的程序是(B )A:命令解释程序B:中断解决程序C:系统调用程序D:顾客登录程序33、下列选项中,不属于网络体系构造中所描述的内容是( C )A:网络的层次B:每一层使用的合同C:合同的内部实现细节D:每一层必须完毕的功能34、在下图所示的采用“存储-转发”方式分组的互换网络中,所有链路的数据传播速度为100mbps,分组大小为1000B,其中分组头大小20B,若主机H1向主机H2发送一种大小为980000B的文献,则在不考虑分组拆装时间和传播延迟的状况下,从H1发送到H2接受完为止,需要的时间至少是( A )A:80msB:80.08msC:80.16msD:80.24ms35、某自治系统采用RIP合同,若该自治系统内的路由器R1收到其邻居路由器R2的距离矢量中涉及信息net1,16,则也许得出的结论是( A )A:R2可以通过R1达到net1,跳数为17B:R2可以达到net1,跳数为16C:R1可以通过R2达到net1,跳数为17D:R1不能进过R2达到net136、若路由器R由于拥塞丢弃IP分组,则此时R可以向发出该IP分组的源主机发送的ICMP报文献类型是( C )A:路由重定向B:目的不可达C:源克制D:超时37、某网络的IP地址为192.168.5.0/24采用长子网划分,子网掩码为255.255.255.248,则该网络的最大子网个数,每个子网内的最大可分派地址个数为( B )A:32,8B:32,6C:8,32D:8,3038、下列网络设备中,可以克制网络风暴的是( C )中继器 集线器 网桥 路由器A:仅和B:仅C:仅和D:仅39、主机甲和主机乙之间已建立一种TCP连接,TCP最大段长度为1000字节,若主机甲的目前拥塞窗口为4000字节,在主机甲向主机乙连接发送2个最大段后,成功收到主机乙发送的第一段的确认段,确认段中告示的接受窗口大小为字节,则此时主机甲还可以向主机乙发送的最大字节数是( A )A:1000B:C:3000D:400040、如果本地区名服务无缓存,当采用递归措施解析另一网络某主机域名时,顾客主机本地区名服务器发送的域名祈求条数分别为( A )A:1条,1条B:1条,多条C:多条,1条D:多条,多条 二、综合应用题:41-47小题,合计70分41.(10分)将核心字序列(7、8、11、18、9、14)散列存储到散列列表中,散列表的存储空间是一种下标从0开始的一种一维数组散列函数维:H(key)=(key3)MODT,解决冲突采用线性探测再散列法,规定装填(载)因子为0.7问题:(1)请画出所构造的散列表;(2)分别计算等概率状况下,查找成功和查找不成功的平均查找长度。解答:(1)由装载因子0.7,数据总数7个存储空间长度为10P=10因此,构造的散列表为:01234567893071411818.9.H(7)=(73)MOD10=1(2)查找成功的ASL=(1+1+1+1+2+1+1)/7=8/7查找不成功的ASL=(7+6+5+4+3+2+1+2+1+1)/10=3.242.(13分)设将n(n,1)个整数寄存到一维数组R中,试设计一种在时间和空间两方面尽量有效的算法,将R中保有的序列循环左移P(0Pn)个位置,即将R中的数据由(X0 X1 Xn-1)变换为(Xp Xp+1 Xn-1 X0 X1 Xp-1)规定:(1)给出算法的基本设计思想。(2)根据设计思想,采用C或C+或JAVA语言表述算法,核心之处给出注释。(3)阐明你所设计算法的时间复杂度和空间复杂度解答:(1)前P个数依次进队,while(1n-p)Ai-i+p:p个数依次出对,进入数组末尾(2)具体程序略(3)时间复杂度O(N);空间复杂度o(p) 43.(11分)某计算机字长为16q位,主存地址空间大小为128KB,按字编址,采用字长指令格式,指令名字段定义如下:转移指令采用相对寻址方式,相对偏移是用补码表达,寻址方式定义如下:Ms/Md寻址方式助记符含义000B寄存器直接Rn操作数=(Rn)001B寄存器间接(Rn)操作数=((Rn))010B寄存器间接、自增(Rn)+操作数=((Rn)),(Rn)+1Rn011B相对D(Rn)转移目的地址=(PC)+(Rn)注:(X)表达有储蓄地址X或寄存器X的内容,请回答问题:(1)该指令系统最多可有多少条指令?该计算机最多有多少个通用寄存器?存储器地址寄存器(MDR)至少各需多少位?(2)转移指令的目的地址范畴是多少?(3)若操作码0010B表达加法操作(助记符为a d d),寄存器R4和R5的编号分别为100B和101B,R4的内容为1 2 3 4 H,R5的内容为5 6 7 8 H,地址1 2 3 4 H中的内容为5 6 7 8 H中的内容为1 2 3 4 H,则汇编语言为a d d(R4).(R5)+(逗号前原操作数,都号后为目的操作数)相应的机器码是什么(用十六进制表达)?该指令执行后,哪些寄存器和存储单元的内容会变化?变化后的内容是什么?解答:该题的考点是指令系统设计,注意操作位数与指令条数的关系,地址码与寄存器数的关系,指令字长与MOR的关系,存储容量与MAR的关系,注意补码计算的偏移地址。44.(12分)某计算机的主存地址空间为256MB,按字节编址,指令Cache分离均有8个Cache行,每个Cache行的大小为64MB,数据Cache采用直接映射方式,既有两个功能相似的程序A和B,其伪代码如下所示:假定int 类型数据用32位补码表达,程序编译时i,j, sum 均分派在寄存器中,数据a按行优先方式寄存,其地址为320(十进制数),请回答问题,规定阐明理由或给出计算过程。(1)、若不考虑用于cache一致性维护和替代算法的控制位,则数据Cache的总容量是多少?(2)、要组元素a031和a11各自所在的主存块相应的Cache行号分别是多少(Cache行号从0开始)?(3)、程序A和B的数据访问命令中各是多少?那个程序的执行时间更短?简答:考点:Cache容量计算,直接映射方式的地址计算,以及命中率计算(行优先遍历与列优先遍历命中率分别很大) 45、(7分)假设计算机系统采用CSCAN(循环扫描)磁盘调度方略,使用2KB的内存空间记录16384个磁盘块的空间状态(1)、请阐明在上述条件下如何进行磁盘块空闲状态管理。(2)、设某单面磁回旋转速度为每分钟6000转。每个磁道有100个扇区,相临磁道间的平均移动时间为1ms.若在某时刻,磁头位于100号磁道处,并沿着磁道号大的方向移动(如下图所示),磁道号祈求队列为50.90.30.120.对祈求队列中的每个磁道需读取1个随机分布的扇区,则读完这个扇区点共需要多少时间?规定给出计算过程。46.(8分)设某计算机的逻辑地址空间和物理地址空间均为64KB.按字节编址。若某进程最多需要6页(Page)数据存储空间,页的大小为1KB.操作系统采用固定分派局部置换方略为此进程分派4个页框(Page Fame).页号页根号装入时刻访问位071301142301222001391601当该进程执行届时刻260时,要访问逻辑地址为17CAH的数据,请问答下列问题:(1)、该逻辑地址相应的页号是多少?(2)、若采用先进先出(FIFO)置换算法,该逻辑地址相应的物理地址是多少?规定给出计算过程。(3)、若采用时钟(CLOCK)置换算法,该逻辑地址相应的物理地址是多少?规定给出计算过程。(设搜索下一页的指针沿顺时针方向移动,且目前指向2号页框,示意图如下。)解答:17CAH=(0001 0111 1100 1010)2(1)页大小为1K,因此页内偏移地址为10位,于是前6位是页号,因此第一间的解为:5(2)FIFO,则被置换的页面所在页框为7,因此相应的物理地址为(0001 1111 1100 1010)2-IFCAH(3)CLOCK,则被置换的页面所在页框为2,因此相应的物理地址为(0000 1011 1100 1010)2-OBCAH47、(9分)某局域网采用CSMA/CD合同实现介质访问控制,数据传播速率为10MBPS,主机甲和主机乙之间的距离为2KM,信号传播速度是200 000KMS.请回答问题,并给出计算过程。(1)若主机甲和主机乙发送数据时发生冲突,则从开始发送数据时刻起,到两台主机均检测到冲突时刻止,最短需经多长时间?最长需通过多长时间?(假设主机甲和主机乙发送数据过程中,其她主机不发送数据)(2)若网络不存在任何冲突与差错,主机甲总是以原则的最长以大网数据锁(1518字节)向主机乙发送数据,主机乙每成功收到一种数据锁后,立即发送下一种数据锁,此时主机甲的有效数据传播速率是多少?(不考虑以大网锁的前导码)解答:(1)当甲乙同步向对方发送数据时,两台主机均检测到冲突所需时间最短;1KM/00KM/S*2=1*10(-5)S当一方发送的数据立即要达到另一方时,另一方开始发送数据,两台主机均检测到冲突所需时间最长;2KM/000KM/S*2=2*10(-5)S(2)发送一锁所需时间;1518B/10MBPS=1.2144MS数据传播时间;2KM/200 000KM/S=1*10(-5)S=0.01MS有效的数据传播速率=10MBPS*1.2144MS/1.2244MS=9.92MBPS
展开阅读全文