数据结构试题

1．算法的计算量的大小称为计算的（ ）。

A．可行性 B. 区分度 C. 现实性 D. 复杂性 2. 以下数据结构中，哪一个不是线性结构（ ）

A．队列 B. 二叉树 C. 栈 D. 串 3. 链表不具有的特点是（ ）

A．插入、删除不需要移动元素 B．可完全随机并以最低时间复杂度访问任一元素

C．不必事先估计存储空间 D．所需空间与所含元素个数成正比 4. 一个递归算法必须包括（ ）。

A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件

5. 数组A[0..4, 0..7]中含有元素的个数（ ）。

A. 55 B. 40 C. 36 D. 16

6. 设有一表示算术表达式的二叉树（见下图）， 它所表示的算术表达式是（ ）

A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G）) D. A*B+C/D*E+F-G

7．在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍。

A．1/2 B．1 C．2 D．4 8．堆排序属于（ ）排序

（A）插入 （B）选择 （C）交换 （D）归并

9．关键路径是指AOE(Activity On Edge)网中（ ）。

(A) 最长的回路 (B) 最短的回路 (C) 从源点到汇点(结束顶点)的最长路径 (D) 从源点到汇点(结束顶点)的最短路径

10．输入序列为DCAB，利用一个堆栈不可以得到的输出序列是.( )

(A) DCBA (B) CDAB (C) CDBA (D) ADBC

二、 填空题（5*2=10）

1. 在线性结构中，开始结点有没有前驱结点，其余各个结点有 个前驱结点；终端结点有 个后继结点，其余每个结点有一个后继结点。

2. 向栈中推入元素的操作是 。

3. Prim算法和Kruskal算法是求无向图的______（填最小/最大）生成树算法。

4．在一棵具有n（n>0）个结点的二叉树中，所有结点的空子树个数等于 。

三、 判断题（10*2=20）

1. 算法的优劣与算法描述语言无关，但与所用计算机有关。 ( ) 2. 在散列检索中，“比较”操作一般也是不可避免的。 ( ) 3. Dijkstra算法是按路径长度递增次序，逐步产生最短路径的算法。（ ）

4. 对图的遍历通常有深度优先和宽度优先两种遍历方式。（ ） 5. 哈夫曼树不含有度为一的结点。（ ） 6. AVL树一定是二叉排序树（ ）

7. 散列函数越复杂越好，因为这样随机性好，冲突概率小.（ ） 8. 带权无向图的最小生成树必是唯一的。（ ）

9．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（ ） 10. 无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（ ）

四、 解析题，从下面4道题中任选3道（每题10分。共30分） 1. 简述数据结构的4种基本关系并画出它们的关系图。 2. 已知某通信用电文仅有A、B、C、D、E、F、G、H八个字符构成，字母在电文中出现的频率分别为18、10、6、76、9、43、85、10。试为这8个字母设计哈夫曼编码，给出它们的哈夫曼编码及求解过程。

3. 已知二叉树T的前序遍历序列为I D A C B H E G F，中序遍历序列为A D C B I E H F G。试画出该二叉树并给出相应的后序遍历序列。

4. 给定图1所示网络，试求该网络的一棵最小生成树。

1a2c1b3e4g1f3

图1

五、 算法设计，从下面3题中任选两题（每题10分，共20分）。 1. 单链表的结点的两个数据域分别是Data和next，其中Data为数据域，next为指向其后继的指针。Head为指向单链表L的头结点的指针，试写一算法求单链表L中中间位置的结点地址。 2. 设计一个算法，在以root为根的二叉树中查找关键字为key的结点，找到了返回True，否则返回False。

3. 已知单链线性表La和Lb的元素按值非递减排列，试编写算法，归并La和Lb得到新的单链线性表Lc，要求Lc的元素值仍按非递减排列。