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

一、填空题

1． 在哈希函数

中，p 值最好取_____。

【答案】小于等于表长的最大素数或不包含小于20的质因子的合数

【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。

2． 对n 个元素的序列进行起泡排序时，最少的比较次数是_____。

【答案】n －1

【解析】如果序列是正序，冒泡排序第一次只要进行n －1次比较，发现没有移动元素，说明序列有序。

3． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。

【答案】物理上相邻；指针

【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。

4． 以下是用类C 语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild 域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack , 栈顶指针为top ，P ，t 为辅助指针，head 为双向循环链表的头指针。试填充算法中的空格，使算法完整。

【答案】

5． n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。

注:(1)图的顶点号从0开始计；

(2)indegree是有n 个分量的一维数组，放顶点的入度， (3)函数crein 用于记算顶点入度； (4)有三个函数回1，否则0) 。

("图有回路") ;

【答案】

其含义为数据data 入栈，出栈和测试栈是否空(不空返

【解析】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的所有元素之和。拓扑排序过程:首先将入度为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度 减一，然后判断这些顶点的入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。

6． 已知一循环队列的存储空间为，其中n ＞m ，队头和队尾指针分别为front 和rear ，则此循环队列判满的条件是_____

【答案】

7． 在下面的程序段中，对X 的赋值语句的时间复杂度为_____ (表示为n 的函数) 。

【答案】1＋(1＋2) ＋(1＋2＋3) ＋…＋(l＋2＋…＋n) ＝n(n＋1)(n＋2)/6，即O(n)

【解析】当i ＝l 时，赋值语句就被执行了一次。当i ＝2时，赋值语句被执行了1＋2次。当i

＝3时，赋值语句被执行了1＋2＋3次。...... 可以推出赋值语句总共被执行了1＋(1＋2) ＋(1＋2＋3) ＋…＋(l＋2＋... ＋n) ＝n(n＋1)(n＋2)/6次。

8． 在一个具有n 个单元的顺序栈中，假定以地址高端(即下标为n 的单元) 作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top ＝_____。

【答案】top ﹣1

【解析】由于栈底在地址高端，栈中压入一个元素时，栈顶向地址底端移动一个单位，所以top ﹣1。

9． 串是一种特殊的线性表，_____；其特殊性表现在_____；串的两种最基本的存储方式是_____、两个串相等的充分必要条件是_____。

【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等 10．假定查找有序表

【答案】

表

平均查找次数为

。

中每个元素的概率相等，则进行折半查找时的平均查找长度为_____。

【解析】折半查找时每个的次数如表所示:

二、单项选择题

11．某机器字长16位，主存按字节编址，转移指令采用相对寻址，由两个字节组成，第1字节为操作码字段，第2字节为相对位移量字段. 假定取指令时，每取一个字节PC 自动加1. 若某转移指令所在主存地址为2000H ，相对位移量字段的内容为06H ，则该转移指令成功转移后的目标地址是（ ）.

A.2006H B.2007H C.2008H D.2009H 【答案】C

【解析】相对寻址方式的有效地址EA ＝(PC)＋D ，其中PC 为程序计数器，D 为相对偏移量. 主存按字节编址，取指令时，每取一个字节PC 值自动加1. 由于转移指令由两个字节组成，取出这条转移指令之后的PC 值自动加2，为2002H ，故转移的目标地址为2002H ＋06H ＝2008H.