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

一、填空题

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

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

2． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：

【答案】

【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。

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

【答案】方便运算

4． 如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。

【答案】69

【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。

5． 在哈希函数中，P 值最好取_____。

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

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

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

【答案】

7． 模式串

的next 函数值序列为_____。

【答案】01122312

8． 数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____，设计出相应的_____。

；算法 【答案】逻辑结构；物理结构；操作（运算）

9． 设有一个10阶对称矩阵A 采用压缩存储方式（以行为主序存储：

【答案】33

【解析】设存储的元素的行标为i ，列标为j 。若

则

则的地址为

若

的地址为将代入得33。

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

【答案】9

【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。 11．深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。

【答案】

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

【答案】

13．对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。

置空链表，然后将原链表结点逐个插入到有序表中

当链表尚未到尾，p 为工作指针

查P 结点在链表中的插入位置，这时q 是工作指针

，）则 的地址为_____。

【答案】（1）（2）（3）

（4）（5）

将P 结点链入链表中

是q 的前驱，u 是下个待插入结点的指针

14．有向图G=（V ，E ）, 其中V （G ）=[0, 1，2，3，4, 5}, 用三元组表示弧及弧上的权d 。 E （G ）为 E （G= {<0，5, 100>, <0，2，10>, <1，2，5>，<0，4, 30>，<4, 5, 60>，<3，5, 10>，<2. 3，50>， <4, 3, 20>}，则从源点0到顶点3的最短路径长度是_____，经过的中间顶点是_____。

【答案】50; 4

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

【答案】23; 100CH

二、选择题

16．若一棵二叉树的前序遍历序列和后序遍历序列分别为1，2, 3, 4和4, 3, 2, 1，则该二叉树的中序遍历序列不会是（ ）。

A.1, 2.3.4 B.2，3, 4.1 C.3, 2, 4, 1 D.4, 3, 2, 1

【答案】C

【解析】题目中的二叉树的先序序列和后序序列正好相反，这样的二叉树每层只有一个结点。该二叉树的形态如下图所示。

从左至右，这8棵二叉树的中序序列分别为： （1）4. 3. 2. 1， （2）3, 4, 2, 1 （3）2, 4, 3, 1 （4）2, 3, 4，1 （5）1，4，3, 2 （6）1, 3, 4, 2