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

一、填空题

1． 在二叉树中，指针p 所指结点为叶结点的条件是_____。

【答案】

【解析】叶子节点的左右孩子都不存在。

2． 顺序栈用存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。

【答案】

【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。

3． 克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。

【答案】O （eloge ）; 边稀疏

4． 对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。

【答案】集合；线性结构；树形结构；图状结构（网状结构）

5． 实现字符串拷贝的函数strcpy 为：

【答案】

6． 当广义表中的每个元素都是原子时，广义表便成了_____。

【答案】线性表

【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。

7． 设有一个空找，栈顶指针为1000H （十六进制），现有输入序列为1，2，3, 4, 5，经过PUSH ，PUSH , POP , PUSH , POP ，PUSH ，PUSH 之后，输出序列是_____，而栈顶指针值是_____。设栈为顺序栈，每个元素占4个字节。

【答案】23; 100CH

8． 设有一个10阶对称矩阵A 采用压缩存储方式（以行为主序存储：

【答案】33

【解析】设存储的元素的行标为i ，列标为j 。若

则的地址为

若

第 2 页，共 35 页

，）则 的地址为_____。

的地址为将代入得33。 9． 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____则

算法，最费时间的是_____算法。

【答案】起泡；快速

，【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为〇（n ） 而快速排序算法需要比较的次数达到最大，时间复杂度为

10．线性表用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____。

【答案】（n －1）/2

【解析】删除第一个元素需要移动n －i 次，以此类推，删除最后一个元素需要移动0次。平 均次数为

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

【答案】

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

12．用循环链表表示的队列长度为n ，若只设头指针，则出队和入队的时间复杂度分别是_____和_____；若只设尾指针，则出队和入队的时间复杂度分别是_____和_____。

【答案】

【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一个结点或者下下个结点删除即可，入队时，只要在尾指针的后面插入新的结点，并更新尾结点即可。

13．以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。

【答案】（1）（2）

第 3 页，共 35 页

链表未到尾就一直进行

将当前结点作为头结点后的第一元素结点插入

14．设有两个算法在同一机器上运行，其执行时闻分别为_____。

【答案】15

【解析】当时，而，时，

15．设有个结点的完全二叉树顺序存放在向量

【答案】

要使前者快于后者，n 至少为

中，其下标值最大的分支结点为_____。

【解析】最大的分支结点是最后一个叶子结点的父结点。

二、选择题

16．下列关于SMTP 协议的叙述中，正确的是（ ）

I. 只支持传输7比特ASCII 码内容 II. 支持在邮件服务器之间发送邮件 III. 支持从用户代理向邮件服务器发送邮件 IV. 支持从邮件服务器向用户代理发送邮件 A. 仅 I 、II 和 III B. 仅 I 、II 和 IV C. 仅 I 、III 和 IV D. 仅 II 、III 和 IV 【答案】A

【解析】根据下图可知，SMTP 协议支持在邮件服务器之间发送邮件，也支持从用户代理向邮件服务器发送信息。SMTP 协议只支持传输7比特的ASCII 码内容

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

A.0 B.1 C.2 D.3

【答案】C

【解析】采用页式虚拟存储管理方式时，若页表全部放在内存中，则存取一个数据最少要访

第 4 页，共 35 页