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

一、填空题

1． 克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。 【答案】；边稀疏

2． 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。

【答案】度；出度

3． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。

【答案】O(1)；O(n)

【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。

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

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

5． 设二维数组A 的行和列的下标范围分别为[0:8]和[0:10]，每个元素占2个单元，按行优先顺序存储，第一个元素的存储起始位置为b ，则存储位置为b+50处的元素为_____。

【答案】A[2][3]

【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是(ll*i＋j ＋l ﹣l)*2＋b 。当其值为b ＋50时，则i ＝2，j ＝3。

6． 当两个栈共享一存储区时，栈利用一维数组stack(1，，1) 表示，两栈顶指针为top[l]与top[2]，则当栈1空时，top[l]为_____，栈2空时，top[2]为_____，栈满时为_____。

【答案】0；n+1；top[l]+l＝top[2]

【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。

二、单项选择题

7． 假定编译器将赋值语句“x=x+3; ”转换为指令”add xaddt, 3”, 其中xaddt 是x 对应的存储单元地址, 若执行该指令的计算机采用页式虚拟存储管理方式, 并配有相应的TLB , 且Cache 使用直写(Write Through)方式, 则完成该指令功能需要访问主存的次数至少是（ ）。

A.0

B.1

C.2

D.3

【答案】C

【解析】采用页式虚拟存储管理方式时, 若页表全部放在内存中, 则存取一个数据最少要访问两次内存:第一次是访问页表, 得到所存取的数据或指令的物理地址; 第二次根据该地址存取数据或指令。在配有TLB 的页式虚拟管理方式中, 如果给出的地址在TLB 中, 则直接根据该地址取数据或指令, 仅需要一次访问内存。Cache 使用直写方式时, 计算完需要将数据写回到内存中, 因此完成整个指令功能至少需要访问主存2次。

8． 和顺序栈相比，链栈有一个比较明显的优势是（ ）。

A. 通常不会出现栈满的情况

B. 通常不会出现栈空的情况

C. 插入操作更容易实现

D. 删除操作更容易实现

【答案】A

9． 已知广义表LS ＝((a，b ，c) ，(d，e ，f)) ， 用head 和tail 数取出LS 中原子e 的运算是（ ）。

A.head(tail(LS))

B.tail(head(LS))

C.head(tail(head(tail(LS)))

D.head(tail(tail(head(LS))))

【答案】C

【解析】head 操作就是得到广义表中第一个的原子。tail 操作就是得到除第一个原子外剩下元素构成的表。tail(LS)得到((d，e ，f)) ，head(tail(LS))得到(d，e ，f)tail(head(tail(LS)))得到(e，f) ，head(tail(head(tail(LS))) 得到e 。

10．设有一个10阶的对称矩阵A ，采用压缩存储方式，以行序为主存储，a 11为第一元素，其存储地址为1，每个元素占一个地址空间，则a 85的地址为（ ）。

A.13

B.33

C.18

D.40

【答案】B

【解析】对于对称矩阵，为了节省存储空间，为多个相同的元素只分配一个存储空间。对于对称矩阵，元素下表之间的对应关系为:当i ＞＝j 时，k ＝i(i﹣l)/2＋j ﹣l ；当i ＜＝j 时，k

＝j(j﹣l)/2＋i ﹣l 。其中k 相当于地址空间的标号，i 为行号，j 为列号。因为第一个元素存储地址为1，所以最后计算的k 需要加1。所以a 85的存储位置为8*(8﹣1)/2＋5＝33。

11．某计算机有五级中断, 中断屏蔽字为表示对

屏蔽。若中断响应优先级从高到低的顺序是

的顺序为

A.11110

B.01101

C.00011

D.01010

【答案】D

B

排除掉。【解析】由于L 2的中断处理优先级下降, 屏蔽字中需要3个0, 所以可以将选项A 、

需要对开放, 所以相应位应该为“0”, 即为01010。

12．协议对0111110001111110组帧后对应的比特串为（ ）

A.011111000011111010

B.011111000111110101111110

C.01111100011111010

D.011111000111111001111101

【答案】A

【解析】HDLC 协议对比特串进行组帧时, HDLC 数据帧以位模式标识每一个帧的开始和结束, 因此在帧数据中凡是出现了5个连续的位“1”的时候, 就会在输出的位流中填充一个“0”。所以答案为A 。

13．在虚拟存储管理中, 地址变换机构将逻辑地址变换为物理地址, 形成该逻辑地址的阶段是（ ）。

A. 编辑

B. 编译

C. 链接

D. 装载

【答案】B

【解析】程序的编辑阶段一般都是程序员能够识别的高级语言或低级语言的文本, 不涉及到任何与计算机运行相关的事; 编译是由编译程序将用户源代码编译成若干个目标模块, 源地址编译成目标程序时, 会形成逻辑地址; 链接是由链接程序将编译后形成的一组目标模块, 以及所需库函数链接, 形成完整的装入模块; 装入是由装入程序将装入模块装入内存。

14．下列各类存储器中, 不采用随机存取方式的是（ ）。

A.EPROM

B.CDR0M

C.DRAM

级中断进行

, 且要求中断处理优先级从高到低, 则的中断处理程序中设置的中断屏蔽字是（ ）。