当前位置：问答库＞考研试题

一、填空题

1． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度, 当它为一棵_____时，具有最大高度。

【答案】完全；只有一个叶结点的二叉树

2． 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_____和_____；而又根据指针的连接方式，链表又可分成_____和_____。

【答案】单链表；双链表；(动态) 链表；静态链表

【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根据指针的连接方式，链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号，动态链表的指针指向下一个元素的物理位置。

3． 在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出。

【答案】满；空；n ；栈底；两栈顶指针相邻(即值之差的绝对值为1)

4．

线性表

【答案】(n﹣1)/2

【解析】删除第一个元素需要移动n ﹣1次，以此类推，删除最后一个元素需要移动0次。平均次数为(n﹣l)*n/n/2＝(n﹣l)/2。

5． —棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_____个结点。

【答案】

树。故结点个数为

。 【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____。

二、单项选择题

6． 假设5个进程P0、P1、P2、P3、P4共享三类资源R1、R2、R3, 这些资源总数分别为18、6、22。时刻的资源分配情况如下表所示, 此时存在的一个安全序列是（ ）。

表 资源分配情况表

A.P0, P2, P4, P1, P3

B.P1, P0, P3, P4, P2

C.P2, P1, P0, P3, P4

D.P3, P4, P2, P1, P0P0

【答案】D 。

【解析】典型的死锁避免算法、银行家算法的应用。分析一下下表, 可以看到, P3, P4, P2, P1, P0运行是可以的。

表

本题也可以排除法, 时刻可用资源是R1, R2, R3分别为2, 3, 3, 此时刻, P0需要R1, R2, R3分别为2, 3, 7, 故排除A , P1需要R1, R2, R3分别为1, 3, 3, P2还需要资源R1, R2, R3分别为0, 0, 6, 故C 排除, P3需要R1, R2, R3分别为2, 2, 1。所以正确答案在B , D 之间。

看B 选项, P1之后的可用资源R1, R2, R3分别变为6, 3, 6, 而P0尚需资源2, 3, 7, 故B 方案行不通。因而最终答案只有D 项。

7． 某以太网拓扑及交换机当前转发表如下图所示, 主机后, 向主机

A.

C.

D. 和和 B.{2, 3}和{1} 和{1}

向主机发送1个数据帧, 主机收到该帧发送一个确认帧, 交换机对这两个帧的转发端口分别是（ ）

【答案】B

【解析】

第一次交换机没有

这个数据报源MAC 地址的信息的信息, 只能选择从其他端口全部发送, 同时记录, 确认帧发送时已经有的信息了所以只用从1端口转发。

8． 某计算机存储器按字节编址, 主存地址空间大小为64MB ,

现用

32MB 的主存储器, 则存储器地址寄存器MAR 的位数至少是（ ）。

A.22位

B.23位

C.25位

D.26位

【答案】D 位的RAM 芯片组成

【解析】虽然实际的主存储器(RAM区) 只有32MB , 但不排除还有ROM 区, 考虑到存储器扩展的需要, MAR 应保证能访问到整个主存地址空间。因为主存的地址空间大小为64MB , 所以MAR 的位数至少需要26位。

9． 下列关于进程和线程的叙述中, 正确的是（ ）。

A. 不管系统是否支持线程, 进程都是资源分配的基本单位

B. 线程是资源分配的基本单位, 进程是调度的基本单位

C. 系统级线程和用户级线程的切换都需要内核的支持

D. 同一进程中的各个线程拥有各自不同的地址空间

【答案】A 。

【解析】利用排除法来确定正确答案:“线程是资源分配的基本单位, 进程是调度的基本单位”这句话说反了, 明显错误。“系统级线程和用户级线程的切换都需要内核的支持”也不正确, 因为用户级线程的切换由用户编写的RimtimeSystem 执行的, 内核并不感知。“同一进程中的各个线程拥有各自不同的地址空间”明显错误, 引入线程的目的就是为了同一进程的所有线程能共享进程的地址空间, 故“不管系统是否支持线程, 进程都是资源分配的基本单位”是正确的。