|
|
发表于 2016-7-9 13:55:02
|
显示全部楼层
一、选择题
1. 一个栈的入栈元素序列是1，2，3，4，5若允许出栈操作可在任意可能的时刻进行，则下面的序列中。不可能出现的出栈序列是()。
A.3，4，2，5，1 B.2，5，4，1，3 C.2，3，1，5，4 D.3，5，4，2，1
考点：栈的基本操作 答案：B
2. 一棵二叉树的前序遍历序列为ABCDEFG，它的中序序列可能是()
A. CABDEFG B. ABCDEFG C. DACEFBG D. BADCFEG 考点：二叉树的遍历 答案：B
3. 用有向无环图描述表达式(A+B)*((A+B)/A),至少需要顶点的数目为()
A. 5 B. 6 C. 8 D. 9 考点：无向图的概念 答案：A
4. 若具有n个顶点的无向连通图采用邻接矩阵表示，则邻接矩阵中至少有( )个非零元素.
A. 2(n-1) B. n/2 C. n+1 D. n-1 考点：图的邻接矩阵存储法答案：A
5. 含4个度为2的结点的二叉树，有()个叶子结点。
A. 1 B. 3 C. 5 D. 7 考点：二叉树的度 答案：C
6.下列内部排序算法中，其比较次数与序列初态无关的是( )
A.快速排序 B. 直接插入排序 C. 二路归并排序 D. 简单选择排序
考点：内排序算法 答案：D
7.通过拓扑排序能够得到拓扑序列的图一定是( )
A.连通图 B.带权连通图 C.无回路的有向图 D.无回路的图
考点：拓扑排序 答案：C
8.下面关于B树和B+树的叙述中，不正确的是_________
A)B树和B+树都是平衡的多分树。 B)B树和B+树都可用于文件的索引结构。
C)B树和B+树都能有效地支持随机检索。 D)B树和B+树都能有效地支持顺序检索。
考点：B树、B+树定义与特点答案：D
8.若有18个元素的有序表存放在一维数组A[18]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为( )
A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3
考点：二分查找算法 答案：D
10. 对于线性表(7，34，55，25，64，48，20，10)进行散列存储时，若选用H(K)= K % 7作为散列函数，则散列地址为6的元素有( )个
A.1 B.2 C.3 D.4
考点：散列函数 答案：D
11. 在原码一位乘中，当乘数Yi为1 时，()
A.被乘数连同符号位与原部分积相加后，右移一位
B.被乘数绝对值与原部分积相加后，右移一位
C.被乘数连同符号位右移一位后，再与原部分积相加
D.被乘数绝对值右移一位后，再与原部分积相加
考点：原码一位乘法 答案：B
12. 如果X 为负数，由[X]补求[-X]补是将()。
A.[X]补各值保持不变 B.[X]补符号位变反，其它各位不变
C.[X]补除符号位外，各位变反，未位加1 D.[X]补连同符号位一起各位变反，未位加1
考点：补码 答案：D
13. 在堆栈寻址中，设A 为累加器，SP为堆栈指示器，Msp为SP 指示的栈顶单元。如果
进栈操作顺序是：(SP)-1→SP，(A)→Msp;那么出栈操作的顺序应是()。
A.(Msp)→A,(SP)+1→SP B.(SP)+1→SP，(Msp)→A
C.(SP)-1→SP，(Msp)→A D.(Msp)→A，(SP)-1→SP
考点：堆栈工作原理 答案：A
14. 在取指周期中，是按照( )的内容访问主存，以读取指令。( )
A.指令寄存器IR B.程序状态寄存器PS
C.存储器数据寄存器MDR D.程序计数器PC
考点：指令的执行 答案：D
15.( )不是常用三级时序系统中的一级
A)指令周期 B)工作周期 C)时钟周期 D)定时脉冲
考点：时序系统 答案：B
16. 动态半导体存储器的特点是( )
A.在工作中存储器内容会产生变化 B.每次读出后，需要根据原存内容重新写入一遍
C.每隔一定时间，需要根据原存内容重新写入一遍 D.在工作中需要动态地改变访存地址
考点：DRAM 答案：B
17. 设置中断排队判优逻辑的目的是( )
A.产生中断源编码 B.使同时提出的请求中的优先级别最高者，得到及时响应
C.使CPU 能方便地转入中断服务子程序 D.提高中断响应速度
考点：中断判优 答案：B
18.“总线忙”信号由( )建立。
A.获得总线控制权的设备 B.发出“总线请求”的设备
C.总线控制器 D.CPU
考点：总线控制 答案：A
19.在大多数磁盘中( )。
A.各磁道的位密度相同 B.最外圈磁道的位密度最大 C.最内圈磁道的位密度最大
D.写入时选择较高的位密度，以增加记录信息;读出时选择低的位密度，以提高可靠性
考点：磁盘数据存储 答案：C
20.在调频制记录方式中，是利用( )来写0或1。
A.电平高低的变化 B.电流幅值的变化
C.电流相位的变化 D.电流频率的变化
考点：调频制记录方式原理 答案：D
21.计算机操作系统是一个( )。
A. 应用软件 B. 硬件的扩充 C. 用户软件 D.系统软件
考点：操作系统概念 答案：D
22.对于给定的信号量s，等待操作wait(s)(又称P操作)定义为：
if s>0 then s:=s-1 else 挂起调用的进程。
唤醒操作signal(s)(又称V操作)定义为：
if 存在等待的进程 then 唤醒这个进程 else( )。
A)s=0 B)s=s+1 C)s=s-1 D)s=1
考点：信号量的定义 答案：B
23.单一处理机上，将执行时间有重叠的几个程序称为( )。
A)顺序程序 B) 多道程序 C)并发程序 D) 并行程序
考点：并发程序的定义 答案：C
24. 单一连续存储管理时，若作业地址空间大于用户空间，可用( )把不同时工作的段轮流装入主存区执行。
A)对换技术 B)移动技术 C)虚拟存储技术 D)覆盖技术 考点：对换的作用 答案：A
25.下面的()与文件的存储结构无关。
A) 索引文件 B) 记录式文件 C) 串联文件 D) 连续文件
考点：文件的存储结构 答案：B
答案：C
26. 下列说法中，错误的是：( )
A.页式存储管理中，进程地址空间是一维的;
B.段式存储管理中，进程地址空间是二维的;
C.段页式存储管理中，进程地址空间是二维的;
D.段页式存储管理中，进程地址空间是三维的;
考点：存储管理方式，地址空间 答案：D
27. 下列作业调度算法中，最短的作业平均周转时间是( )。
A)先来先服务法 B) 短作业优先法 C)优先数法 D) 时间片轮转法
考点：作业调度算法比较 答案：B
28.操作系统提供给程序员的接口是( )。
A.进程 B.系统调用 C.库函数 D.B和C 考点：操作系统接口答案：B
29. 有一磁盘，共有10个柱面，每个柱面20个磁道，每个盘面分成16个扇区。采用位示图对其存储空间进行管理。如果字长是16个二进制位，那么位示图共需( )字。
A.200 B.128 C.256 D.100 考点：空闲块管理，位示图法 答案A
30.一下关于文件目录组织结构的说法，错误的是( )
A.单级目录只能支持一个用户 B.二级目录可以支持多个用户
C.多级目录能够实现不同用户之间文件共享 D.多级目录可以使用单级目录模拟实现
考点：文件目录的结构 答案A
31.在 OSI/RM 中，提供流量控制的层是 ________ 。
A . 1、2、3层 B .2、3、4层 C . 3、4、5层 D . 4、5、6层
考点：OSI/RM模型各层功能 答案：B
32.在 OSI 的网络体系结构中，对等实体之间传输的信息组成是 _____ 。
A 。接口控制信息 B .协议控制信息 C .接口数据单元 D .协议数据单元
考点：OSI 的网络体系结构 答案：D
33.在以下传输介质中，带宽最宽，抗干扰能力最强的是()
A) 双绞线 B)无线信道 C)同轴电缆 D)光纤
考点：物理层线路的特性 答案：D
34 .一信道的带宽为 10KHZ ，如果使用4个不同的物理状态来表示数据，根据奈奎斯特定理，其限定的最高数据率是 _____ 。
A .5Kb/s B . 10 Kb/s C . 20 Kb/s D . 40 Kb/s
考点：奈奎斯特定理 答案：D
35. 下面那个设备不可以隔离冲突域
A)中继器 B)网桥 C)交换机 D)路由器 考点：网络互连设备的功能 答案：A
36 .下面给出的 IEEE802 LAN 标准中，采用预约方式的媒体访问控制技术的是 _____ 。 A . CSMA/CD (IEEE802.3 ) B .令牌总线(IEEE802.4)
C .令牌环(IEEE802 . 5 ) D .分布式队列双总线(IEEE802.6)
考点：常见局域网协议 答案：C
37. 对网际控制报文协议(ICMP)描述不正确的有
A)ICMP封装在IP数据报的数据部分 B)ICMP是属于应用层的协议
C)ICMP 是IP协议的必需的一个部分 D)ICMP可用来进行拥塞控制
考点：ICMP协议 答案：B
38.有一个中学获得了C类网段的一组IP 192.168.1.0/24，要求你划分7个以上的子网，每个子网主机数不得少于25台，请问子网掩码该怎么写?____
A.255.255.255.128 B.255.255.255.224
C.255.255.255.240 D.255.255.240.0
考点：IP地址、子网掩码 答案：B
39. 关于TCP和UDP，下列哪种说法是错误的?______
A. TCP和UDP的端口是相互独立的
B. TCP和UDP的端口是完全相同的，没有本质区别
C. 在利用TCP发送数据前，需要与对方建立一条TCP连接
D. 在利用UDP发送数据时，不需要与对方建立连接。
考点：传输层协议 答案：B
40.下面的协议中， ____ 是属于 TCP/IP 协议簇中的高层协议，并且主要用途为完成传输电子邮件作用的。
A . MHS B . HTML C . SMTP D . SNMP
考点：常见应用层协议 答案：C
二、综合题
1.已知一个无符号十进制整数num，写一算法，依次输出其对应的八进制数的各位数字。
答： void CHANGE( int num )
{
STLink p, top=NULL;
do {
p=(STlink)malloc(sizeof(STNode));
p->data=num % 8 ;
p->link=top; // 进栈 //
top=p;
num=num / 8 ;
}
while( num!=0);
while( top!=NULL )
{
printf( “%d”,top->data );
p=top;
top=top->link;
free(p);
}
}
2.已知二叉树的前序遍历序列与中序遍历序列分别存放于数组PREOD[0:n-1]与INOD[0:n-1]中，并且各结点的数据信息均不相同，请写一算法，生成该二叉树的二叉链表存储结构。
答： BTREE BUILDTREE( datatype PREOD[ ], n )
{
BTREE T=NULL;
int i;
for ( i=0; i
INSERTITEM( T, PREOD );
return T;
}
void INSERTITEM( BTREE &T, datatype item )
{
BTREE p, q;
int ord;
p=(BTNode)malloc(sizeof(BTREE));
p->data=item;
p->lchild=p->rchild=NULL;
if ( T==NULL ) T=p;
else { ord=SEARCHPOS( INOD, n, item );
q=T;
while(1)
if ( orddata )
if ( q->lchild!=NULL ) q=q->lchild;
else{ q->lchild=p;
break;
}
else if ( q->rchild!=NULL )
q=q->rchild;
else{ q->rchild=p; break;
}
}
int SEARCHPOS( datatype INOD[ ], int n, datatype item )
{
int i;
for ( i=0; i
if ( INOD==item )
return i+1;
}
3. 流水线中有三类数据相关冲突：写后读(RAW)相关，读后写(WAR)相关;写后写(WAW)相关。判断以下三组指令各存在哪种类型的数据相关。
(1)I1：ADD R1，R2，R3; (R2+R3)->R1
I2：SUB R4，R1，R5; (R1-R5) ->R4
(2)I3: STA M(X),R3; (R3)->M(X),M(X)是存储器单元
I4: ADD R3，R4，R5; (R4+R5) ->R3
(3)I5: MUL R3，R1，R2; (R1)*(R2) ->R3
I6: ADD R3，R4，R5; (R4+R5) ->R3
答：第(1)组指令中，I1 指令运算结果应先写入R1然后在I2指令中读出R1内容。由于I2指令进入流水线，变成I2指令在I1 指令写入R1之前就读出R1内容，发生RAW相关。
第(2)组指令中，I3指令应先读出R3内容并存入存储单元M(X)，然后在I4 指令中将运算结果写入R3，但由于I4 指令进入流水线，变成I4指令在I3 指令读出R3内容前就写入R3 ，发生WAR相关。
第(3)组指令中，如果I6指令的加法运算完成时间早于I5指令的乘法运算时间，变成指令I6 在指令I5 写入R3 之前就写入R3 ，导致R3的内容错误， 发生WAW相关。
4.计算机系统包含32K字的主存，Cache容量4K字，每组4 Blocks，每Block 64个字。假设Cache开始是空的，CPU顺序从存储单元0，1，2到4351中读取字，然后再重复这样的取数9次，Cache比主存快10倍，采用LRU替换算法， 假定块替换的时间忽略不计，计算采用Cache后的加速比。
答：块尺寸=64字
组内块数=4块
组数=4K/(64*4)=16
主存块数=32K/64=512
主存块/组=512/16=32
第1次循环(单位：块)
主存块0~63：失效
主存块64~67：失效&&替换
因“块替换的时间忽略不计”等价于仅存在失效
块失效次数：68
第2次循环～第10次循环(单位：块)
映射到组0~3的20个
主存块：失效&&替换
主存块：0~3，16~19，32~35，48~51，64~67
其余48个主存块：全部命中
块失效次数：20×9
块命中次数：48×9
块失效vs. 块命中(单位：块)
块失效次数：68+20×9=248
块命中次数：48×9=432
块失效 1次字失效，63次字命中 块命中 64次字命中 CPU读存储器总计
Cache失效次数：248
Cache命中次数：63×248+64×432=43272
设Cache一次访问时间为S 则主存一次访问时间为11S
“Cache比主存快10倍”
加速比=全部主存访问时间/(Cache失效访问时间+Cache命中访问时间)
=11s*43520/(s+11s)*248+s*43272
=10.35
5.试述分页式存储管理系统和分段式存储管理系统的主要区别。 答：分页和分段有许多相似之处，比如两者都不要求作业连续存放。但在概念上两者完全不同，主要表现在以下几个方式：
(1)页是信息的物理单位，分页是为了实现非连续分配，以便解决内存碎片问题，或者说分页是由于系统管理的需要。段是信息的逻辑单位，它含有一组意义相对完整的信息，分段的目的是为了更好地实现共享，满足用户的需要。
(2)页的大小固定，由系统确定，将逻辑地址划分为页号和页内地址是由机器硬件实现的。而段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时根据信息的性质来划分。
(3)分页的作业地址空间是一维的。分段的地址空间是二维的。
6. 设在批处理系统中有四道作业，它们进入系统的时刻及运行时间如下：
作业号 进入时刻(h) 运行时间(h)
1 10.00 2
2 10.00 1
3 10.50 1
4 10.70 0.5
设系统每次只选择一个作业装入主机。分别给出在下列算法中这组作业的运行顺序、平均周转时间和平均带权周转时间。
FCFS算法 SJF算法
答：如下： FCFS算法
| 进程名 | 到达时间 | 服务时间 | 开始执行时间 | 完成时间 | 周转时间 | 带权周转时间 | | 1 | 10.00 | 2 | 10.00 | 12.00 | 2 | 2 | | 2 | 10.00 | 1 | 12 | 13 | 3 | 3 | | 3 | 10.50 | 1 | 13 | 14 | 3.5 | 13 | | 4 | 10.70 | 0.5 | 14 | 14.5 | 3.8 | 28 |
SJF算法
| 进程名 | 到达时间 | 服务时间 | 开始执行时间 | 完成时间 | 周转时间 | 带权周转时间 | | 1 | 10.00 | 2 | 12.5 | 14 | 4 | 2 | | 2 | 10.00 | 1 | 10.00 | 11 | 1 | 1 | | 3 | 10.50 | 1 | 11.5 | 12.5 | 2 | 1 | | 4 | 10.70 | 0.5 | 11 | 11.5 | 0.8 | 1.6 |
7. 假定TCP载荷是1500字节，最大分组存活时间是120秒，那么要使TCP报文段的序列号不会循环回来而重叠，允许的最快线路速度是多大?
答：目标是120秒内最多发送2^32个字节，即每秒35791394个字节的载荷。
TCP报文段的载荷是1500字节，那么可以发送23861个报文段。
TCP开销是20个字节，IP开销是20个字节，以太网开销是26个字节。
这就意味着对于1500字节的载荷，必须发送1566个字节。
1566*8*23861 = 299Mbps。 |
|
