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

一、填空题

1． 在哈希函数中，p 值最好取_____。

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

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

2． 关键码序列(Q，H ，C ，Y ，Q ，A ，M ，S ，R ，D ，F ，X) ，要按照关键码值递增的次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是_____; 若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是_____。

【答案】(Q，A ，C ，S ，Q ，D ，F ，X ，R ，H ，M ，Y) ; (F，H ，C ，D ，a ，A ，M ，Q ，R ，S ，Y ，X)

【解析】希尔排序的基本思想是:先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

快速排序(quick sort) 的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

3． 二叉树由_____，_____，_____三个基本单元组成。

【答案】根结点；左子树；右子树

4． 起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32, 则其伙伴块的起始地址为_____; 。

【答案】480+8=488，480－32=448

【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下:

根据上述公式起始地址就为488。

5． 一棵有11个结点的满二叉树有_____个度为1的结点、有_____个分支(非终端) 结点和_____个叶子，该满二叉树的深度为_____。 【答案】或

【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。

6． 实现字符串拷贝的函数strcpv 为:

(_____)

【答案】s++＝*t++或(*s++＝*t++)!＝'\0’

7． 空格串是指_____，其长度等于_____。

【答案】由空格字符(ASCII值32) 所组成的字符串；空格个数

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

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

9． 已知有序表为(12，18，24，35，47，50，62，83，90，115，134) 当用二分法查找90时，需次查找成功，查找47时_____成功，查找100时，需_____次才能确定不成功。

【答案】2; 4; 3

【解析】二分法查找元素次数列表

查找100是找到115就停止了。

10．已知二叉排序树的左右子树均不为空，则_____上所有结点的值均小于它的根结点值，_____上所有结点的值均大于它的根结点的值。

【答案】左子树；右子树

【解析】二叉排序树(binary sort tree)或者是一棵空树，或者是具有下列性质的二叉树:①若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左、右子树也分别为二叉排序树。

二、判断题

11．当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。（ ）

【答案】×

【解析】当改变任意关键路径上的关键话动之后，这个活动可能还是关键活动，因此不会产生不同的关键路径。

12．强连通分量是无向图的极大强连通子图。（ ）

【答案】×

【解析】强连通分量是对有向图而言的，一般在无向图中讨论连通性。

13．取线性表的第i 个元素的时间同i 的大小有关。（ ）

【答案】 ×

【解析】不一定，如果是顺序存储结构，它访问数据元素时的时间效率都是O(1)。

14．设尾指针的循环链表表示队列，则入队和出队算法的时间复杂度均为O(1)（ ）。

【答案】 √

【解析】入队和出队操作分别在队尾和队头进行，设有尾指针的循环链表对头和尾元素的操作的时间复杂度是O(1)。

15．数据元素是数据的最小单位。（ ）

【答案】 ×

【解析】数据项是数据的不可分割的最小单位，而数据元素是数据的基本单位。

16．在外部排序过程中，对长度为n 的初始序列进行“置换-选择”排序时，可以得到的最大初始有序段的长度不超过n/2。（ ）

【答案】×

【解析】当输入文件以关键字的升序排序时，只能得到一个长度为文件长度的初始归并段

17．为了很方便的插入和删除数据，可以使用双向链表存放数据。（ ）

【答案】 √

【解析】链式存储结构便于数据的插入和删除，但只能顺序访问表中的元素。

18．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。（ ）

【答案】×

【解析】单链表不能使用折半查找方法。折半查找主要用于数据元素有序且存储方式为顺序存储的表。

19．对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。（ ）

【答案】 √

【解析】可以有长度无穷大的广义表，只是在计算机中不能实现。