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

一、填空题

1． 在循环队列中，队列长度为n ，存储位置从0到，n ﹣1编号，以rear 指示实际的队尾元素，现要在此队列中插入一个新元素，新元素的位置是_____。

【答案】

2． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。 【答案】

的次数最小。总次数为

3．

线性表

【答案】(n﹣1)/2

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

4． 设广义表L ＝(（ ），（ ）) ，则head(L)是_____tail(L)是_____L的长度是_____；深度是_____。

【答案】（ ）；(（ ）) ；2；2

【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。

5． 求图的最小生成树有两种算法，_____算法适合于求稀疏图的最小生成树e

【答案】克鲁斯卡尔

【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。

6． 在拓扑分类中，拓扑序列的最后一个顶点必定是_____的顶点。

【答案】出度为0

【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点

。 用数组表示，假定删除表中任一元素的概率相同，则删除一个元【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测素平均需要移动元素的个数是_____。

矛盾，所有最后一个顶点的出度必定为零。

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

【答案】23；100CH

8． 循环队列的引入，目的是为了克服_____。

【答案】假溢出时大量移动数据元素

【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。

9． 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。

【答案】起泡；快速

【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为O(n)，

2而快速排序算 法需要比较的次数达到最大，时间复杂度为O (n) 。

10．

给定一组数据以它构造一棵哈夫曼树，则树高为_____，带权路径长度WPL 的值为_____。

【答案】5；96

【解析】每次找两个最小的权值构建哈夫曼树:

二、判断题

11．—个排序算法是否稳定，是指该算法在各种情况下的时间效率是否相差不大。（ ）

【答案】×

【解析】排序的稳定性指:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序， 这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri 在rj 之前，而在排序后的序列中，ri 仍在ij 之前，则 称这种排序算法是稳定的；否则称为不稳定的。

12．二叉树中除叶结点外，任一结点X ，其左子树根结点的值小于该结点(X)的值；其右子树根结点的值大于等于该结点(X)的值，则此二叉树一定是二叉排序树。（ ）

【答案】×

【解析】二叉排序树按中序遍历的结点序列是从小到大的因为某结点的左子树根结点不一定是它的中序前驱，可能会出现某结点的左子树根结点的右子树上的值大于这个结点; 其右子树根结点也不一定是它的中序后继。可能会出现右子树根结点的左子树的值小于这个结点。

13．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ ）

【答案】×

【解析】排序的稳定性指:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri 在rj 之前，而在排序后的序列中，ri 仍在ij 之前，则称这种排序算法是稳定的；否则称为不稳定的。

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

【答案】 √

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

15．用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（ ）

【答案】 ×

【解析】后序遍历、中序遍历也可以遍历一维数组存储的二叉树。

16．负载因子(装填因子) 是哈希表的一个重要参数，它反映哈希表的装满程度。（ ）

【答案】√

【解析】查找过程中需和给定值进行比较的关键字的个数取决于三个因素:哈希函数，处理冲突的方法和哈希表的装填因子。其中装填因子标志哈希表的装满程度。

17．通常使用队列来处理函数或过程的调用。（ ）

【答案】 ×

【解析】经常使用栈来处理函数或过程的调用。

18．设模式串的长度为m ，目标串的长度为n ，当n ≈m 且处理只匹配一次的模式时，朴素的匹配(即子串定位函数) 算法所花的时间代价可能会更为节省。（ ）

【答案】 √

【解析】因为两个字符串的长度几乎相等，因此，在进行相应的匹配时，只需要定位父串的前几位即可。