快速查题-408计算机专业基础综合试题

10.B树不同于B树的特点之一是
A.能支持顺序查找
B.结点中含有关键字
C.根结点至少有两个分支
D.所有叶结点都在同一层上

45.（16分）已知f（n）=n!=n×（n-1）×（n-2）×…×2×1，计算f(n)的C语言函数f1的源程序（阴影部分）及其在32位计算机 M上的部分机器级代码如下：
int f1(int n){
1 00401000 55 push edp
... ... ...
if (n>1)
1100401018 83 7D 08 01 cmp dword ptr [ebp+8],1
120040101C 7E 17 jle f1+35h(00401035)
return n*f1(n-1);
130040101E 8B 45 08 mov eax,dword ptr [ebp+8]
1400401021 83 E8 01 sub eax,1
1500401024 50 push eax
1600401025 E8 D6 FF FF EF call f1( 00401000)
... ... ...
1900401030 0F AF C1 imul eax,ecx
2000401033 EB 05 jmp f1+3Ah(0040103a)
else return 1;
2100401035 B8 01 00 00 00 mov eax, 1
}
... ... ...
2600401040 3B EC cmp ebp,esp
... ... ...
300040104A C3 ret
其中，机器级代码行包括行号、虚拟地址、机器指令和汇编指令，计算机 M按字节编址，int 型数据占32位。请回答下列问题：
（1）计算 f(10)需要调用函数 f1多少次?执行哪条指令会递归调用 f1?
（2）上述代码中，哪条指令是条件转移指令?哪几条指令一定会使程序跳转执行?（3）根据第16行的 call指令，第 17行指令的虚拟地址应是多少?已知第16行的 call指令采用相对寻址方式，该指令中的偏移量应是多少（给出计算过程）? 已知第 16行的 call指令的后4字节为偏移量，M是采用大端方式还是采用小端方式?
（4）f（13）=6227020800，但 f1（13）的返回值为1932053504，为什么两者不相等?要使f1（13）能返回正确的结果，应如何修改 f1的源程序?
（5）第19行的imul指令（带符号整数乘）的功能是R[eax]←R[eax]×R[ecx]，当乘法器输出的高、低32位乘积之间满足什么条件时，溢出标志OF=1?要使CPU在发生溢出时转异常处理，编译器应在 imul 指令后应加一条什么指令?

11.对10TB的数据文件进行排序，应使用的方法是
A.希尔排序
B.堆排序
C.快速排序
D.归并排序

46.（7分）对于题45，若计算机M的主存地址为32位，来用分页存储管理方式，页大小为4KB，则第1行的 push指令和第30行的 ret 指令是否在同一页中（说明理由）?若指令Cache 有64行，采用4路组相联映射方式，主存块大小为64B，则32位主存地址中，哪几位表示块内地址?哪几位表示Cache 组号?哪几位表示标记（tag）信息? 读取第 16行的 call指令时，只可能在指令 Cache 的哪一组中命中（说明理由）?

12.将高级语言源程序转换为机器级目标代码文件的程序是
A.汇编程序
B.链接程序
C.编译程序
D.解释程序

47.（9分）某网络拓扑如题47图所示，其中R为路由器，主机 H1~H4的IP 地址配置以及 R的各接口 IP 地址配置如图中所示。现有若干以太网交换机（无VLAN 功能）和路由器两类网络互连设备可供选择。
请回答下列问题：
（1）设备1、设备2和设备3分别应选择什么类型的网络设备?
（2）设备1、设备2和设备3中，哪几个设备的接口需要配置IP地址?为对应的接口配置正确的IP 地址。
（3）为确保主机 H1～H4能够访问Internet，R需要提供什么服务?
（4）若主机H3发送一个目的地址为192.168.1.127的IP数据报，网络中哪几个主机会接收该数据报?

13.有如下C语言程序段：
short si=-32767;
unsigned short usi=si;
执行上述两条语句后，usi的值为
A.-32767
B.32767
C. 32768
D.32769

41.（13分）定义三元组（a，b，c）（a，b，c 均为正数）的距离D=la-b|+|b-c+|c-al。给定3个非空整数集合 S1、S2和S3，按升序分别存储在3个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组（a，b，c）（a三S1，b三S2，c三S3）r中的最小距离。例如S1={-1，0，9}，S2={-25，-10，10，11}，S3={2，9，17，30，41}，则最小距离为2，相应的三元组为（9，10，9）。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采C或 C++语言描述算法，关键之处给出注释。
（3）说明你所设计算法的I间复杂度和空间复杂度。

14.某计算机字长为32位，按字节编址，采用小端（Little Endian）方式存放数据。假定有一个double型变量，其机器数表示为1122 3344 5566 7788H，存放在0000 8040H开始的连续存储单元中，则存储单元0000 8046H中存放的是
A.22H
B.33H
C.66H
D.77H

42.（10 分）若任一个字符的编码都不是其他字符编码的前缀，则称这种编码具有前缀特性。现有果气符集（字符个数≥2）的不等长编间，每个字农润编达头二进制的0、1 厅列最长为L位，且具有前缀特性。请回答下列问题：
（1）哪种数据结构适宜保存上述具有前缀特性的不等长编码?
（2）基于你所设计的数据结构，简述从0/1 串到字符串的译码过程。
（3）简述判定某字符集的不等长编码是否具有前缀特性的过程。