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

一、填空题

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

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

2． VSAM(虚拟存储存取方法) 文件的优点是:动态地_____，不需要文件进行_____，并能较快地_____进行查找。

【答案】分配和释放存储空间；重组；对插入的记录

3． 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n 个顶点

用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。

(1)若

是边，则

的值等于_____，若

不是边，则A(i, j) 的值是一个比任何

置

边的权_____，矩阵的对角线元素全为0。

(2)构造最小生成树过程中，若顶点已包括进生成树，就把相邻矩阵的对角线元素成_____，若

【答案】(1)

已包括进生成树，就把矩阵元素

置成_____。

(3)算法结束时，相邻矩阵中_____的元素指出最小生成树的_____。

边上的权值；都大的数；(2)1; 负值；(3)为负；边

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

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

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

5． 二叉树的前序序列和中序序列相同的条件是_____。

【答案】空树或任何结点至多只有右子树的二叉树

【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。

6． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。

【答案】模式匹配；模式串

7． 阅读下列程序，指出其功能，并写出空格处应填上的语句。

【答案】

【解析】本题是在哈希表中插入值为item 的元素，如该元素已在哈希表中，报告出错。

8．

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

【答案】(n﹣1)/2

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

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

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

10．属于不稳定排序的有_____。

【答案】希尔排序、简单选择排序、快速排序、堆排序等

11．文件可按其记录的类型不同而分成两类，即 _____和_____文件。

【答案】操作系统文件；数据库

12．设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。

【答案】O(m＋n)

二、单项选择题

13．对于一个线性表既要求能够进行较快速地的插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（ ）。

A. 顺序存储方式 B. 链式存储方式

C. 散列存储方式 D. 以上均可以 【答案】B

14．已知序列25, 13, 10, 12, 9是大根堆, 在序列尾部插入新元素18, 将其再调整为大根堆, 调整过程中元素之间进行的比较次数是（ ）。

A.1 B.2 C.4 D.5

【答案】B

【解析】对堆插入或删除一个元素, 有可能不满足堆的性质, 堆被破坏, 需要调整为新堆。 (1)为原堆, (2)为插入18后, (3)比较10与18, 交换后,

(4)比较25与18, 不交换, 即为调整后的新的大根堆。 因此调整过程中元素之间进行的比较次数为2。

15．b ，c) ，(d，e ，f)) ， 已知广义表LS ＝((a，用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 。

16．响应外部中断的过程中, 中断隐指令完成的操作, 除保护断点外, 还包括（ ）。

Ⅰ. 开关中断