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

一、填空题

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

【答案】由空格字符（

值32）所组成的字符串；空格个数

2． 文件可按其记录的类型不同而分成两类，即_____和_____文件。

【答案】操作系统文件；数据库

3． 顺序栈用

【答案】

存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。

【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。

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

【答案】

5． 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。

【答案】度；出度

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

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

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

7． 遍历图的过程实质上是_____，广度优先遍历图的时间复杂度_____; 深度优先遍历图的时间复杂度_____, 两者不同之处在于_____, 反映在数据结构上的差别是_____。

【答案】查找顶点的邻接点的过程；0（n+e）; 0（n+e）; 访问顶点的顺序不同；队列和栈 【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。

8． 已知如下程序段：

语句1执行的时间复杂度为_____；语句2执行的时间复杂度为_____；语句3执行的时间复杂度为_____；语句4执行的时间复杂度为_____。

【答案】（1）n ＋1 （2）n

（3）n （n ＋3）/2 （4）n （n ＋l ）/2

【解析】语s 句1执行到不符合条件情况下，执行了n ＋1次。当语句1不符合条件了是不会执行语句2的，所以语句2被执行了n 次。语句3每次都要执行到不符合条件，故为2＋3＋4...... ＋（n ＋l ）加起来就是n （n ＋3）/2。语句3不符合条件了是不会执行语句4的。所以语句4被执行了1＋2＋3...... ＋n 即n （n ＋l ）/2。

9． 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。

【答案】

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

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

【答案】69

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

二、判断题

11．—个树形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（ ）

【答案】√

【解析】树的前序遍历和后序遍历叶子节点的相对次序是不变的，都遵循左右的次序。

12．对磁带机而言，ISAM 是一种方便的文件组织方法。（ ）

【答案】×

【解析】ISAM 是一种专为磁盘存取设计的文件组织方式。

13．二维以上的数组其实是一种特殊的广义表。（ ）

【答案】√

【解析】广义表是线性表的推广。广义表中的元素还有可能是广义表。对于维数大于二的数组，它在某一维上的元素还是数组。符合广义表的定义，因此二维以上的数组其实是一种特殊的广义表。

14．静态链表就是一直不发生变化的链表。（ ）

【答案】

【解析】用数组描述的链表，即称为静态链表。仍具有链式存储结构的主要优点。不是指不发生变化的的链表。

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

【答案】

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

16．抽象数据类型与计算机内部表示和实现无关。（ ）

【答案】

【解析】抽象数据类型只表示数据的逻辑结构，与计算机内部表示和实现无关。