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

一、填空题

1． 高度为4的3阶B-树中，最多有_____个关键字。

【答案】26

【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。

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

【答案】

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

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

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

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

【答案】23；100CH

5． 抽象数据类型的定义仅取决于它的一组_____，而与_____无关，即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。

【答案】逻辑特性；在计算机内部如何表示和实现；数学特性

6． 已知链队列的头尾指针分别是f 和r ，则将值x 入队的操作序列是_____。

【答案】S ＝(LinkedList*)malloc(sizeof (LNode))；s ﹣＞data ＝x ；s ﹣＞next ＝r ﹣＞next ；r ﹣＞next ＝s ；r ＝s ；

【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。

7． 在单链表中设置头结点的作用是_____。

【答案】方便运算

8． 二进制地址为011011110000, 大小为【答案】011011110100；011011100000

【解析】011011110000是块的起始地址，大小分别为算公式如下:

当大小为4时，起始地址为011011110000+0100。当大小为16时，起始地址为:011011110000-010000。

9． 无用单元是指_____，例_____

【答案】用户不再使用而系统没有回收的结构和变量；

10．检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有 检索和_____检索。

【答案】关键字；记录号；记录号；顺序；直接

11．设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长(也称增

量序列) 依次是4， 2， 1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。

【答案】3; (10，7，-9，0，47，23，1，8，98，36)

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

【答案】n －1

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

和块的伙伴地址分别为:_____ 和其伙伴块的起始地址计

13．G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。

【答案】9

【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。

14．文件由_____组成；记录由_____组成。

【答案】记录；数据项

15．对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。

【答案】4；2

二、判断题

16．两个长度不相同的串有可能相等。（ ）

【答案】 ×

【解析】两个字符串相等，只有当两个字符串的长度相等，并且各个对应位置的字符相等才相等。

17．数据的逻辑结构是指数据的各数据项之间的逻辑关系。（ ）

【答案】X

【解析】数据的逻辑结构是指数据元素之间的逻辑关系。

18． 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（ ）

【答案】 ×

【解析】数组在维数和界偶确定后，其元素个数已经确定，不能进行插入和删除运算。

19．有向图中顶点V 度等于其邻接矩阵中第V 行中的1的个数。（ ）

【答案】×

【解析】有向图顶点V 的出度等于其邻接矩阵第V 行中的1的个数，而有向图中V 的度等于其邻接矩阵中边表出现的V 的个数。

20．队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（ ）

【答案】 ×

【解析】栈只能在一端进行操作，队列可以在表的两端进行运算。

21．在待排数据基本有序的情况下，快速排序效果好。（ ）

【答案】×

【解析】在待排数据基本有序的情况下，插入排序效果好。