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

一、填空题

1． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度，当它为一棵_____ 时. 具有最大高度

【答案】完全；只有一个叶结点的二叉树

2． 每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是中序序列是前庁序列是_____。

【答案】

【解析】树的抑序序列对应二叉树的前序序列. 该二叉树转换成森林吋含三棵树. 其第一棵树的前序是。

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

【答案】克鲁斯卡尔

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

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

第 2 页，共 63 页

.

，则它的后庁序列是_____。设上述二叉树是由某棵树转换而成，则该树的

【答案】

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

5． 设单链表的结点结构为

为指针域，已知指针px 指向单链表中data 为x 的结

_____；点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，贝懦要执行以下语句：

_____;

【答案】

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

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

7． 线性表

【答案】（n －1）/2

【解析】删除第一个元素需要移动n －i 次，以此类推，删除最后一个元素需要移动0次。平 均次数为

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

【答案】4; 2

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

【答案】33

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

的地址为

将

代入得33。

则

的地址为

若

，）则

的地址为_____。

用数组表示，假定删除表中任一元素的概率相同，则删除一个元素

平均需要移动元素的个数是_____。

第 3 页，共 63 页

10．假定查找有序表

【答案】37/12

中每个元素的概率相等，则进行折半查找时的平均查找长度为_____

【解析】折半查找时每个的次数如表所示：

表

平均查找次数为

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

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

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

【答案】9

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

二、选择题

13．若下图为lOBaseT 网卡接收到的信号波形，则该比特串是（ ）

A.00110110 B.10101101 C.01010010 D.11000101 【答案】A

【解析】以太网采用曼彻斯特编码，其将一个码元分成两个相等的间隔，前一个间隔为高电平而后一个间隔为低电平表示1，反之则表示0。故根据波形图，可得答案为A 。

14．将线性表的数据元素进行扩充，允许带结构的线性表是（ ）。

A. 串 B. 树 C. 广义表 D. 栈 【答案】C

【解析】串、树、栈中的数据元素都是属于非结构的原子类型，元素的值是不可分解的。数组和广义表都是允许带结构的线性表。

第 4 页，共 63 页