17、必须把一般树转换成二叉树后才能进行存储。(X) 18、二叉树的遍历只是为了在应用中找到一种线性次序。(√ ) 19、由一棵二叉树的前序序列和后序序列可以唯一确定它。(X) 20、数据的物理结构是指数据在计算机内的实际存储形式。(√) 21、栈和链表是两种不同的数据结构。（X） 22、数据元素是数据的最小单位。(X)

23、二叉树中每个结点的两棵子树是有序的。（√） 24、集合与线性表的区别在于是否按关键字排序。(X) 25、顺序存储方式只能用于存储线性结构（X）。 26、程序一定是算法。(X)

28、链表中的头结点仅起到标识的作用。(X)

29、健壮的算法不会因非法的输入数据而出现莫名其妙的状态。(√) 30、一个图按广度优先搜索法遍历的结果是惟一的。(X)

四、简答题

1、数据结构是一门研究什么内容的学科？

答：数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象及对象间的关系和施加于对象的操作等的学科。

2、设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元

素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。 答：设数组元素A[i][j]存放在起始地址为Loc ( i, j ) 的存储单元中.

∵ Loc ( 2, 2 ) = Loc ( 0, 0 ) + 2 * n + 2 = 644 + 2 * n + 2 = 676. ∴ n= ( 676 - 2 - 644 ) / 2 = 15

∴ Loc ( 3, 3 ) = Loc ( 0, 0 ) + 3 * 15 + 3 = 644 + 45 + 3 = 692.

3、在结点个数为n (n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分

支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？ 答：结点个数为n时，高度最小的树的高度为2，有2层； 它有n -1个叶结点，1个分支结点；

高度最大的树的高度为n ,有n层；它有1个叶结点，n-1个分支结点。

第 页 6 共 23 页

4、用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？ 答：设图的顶点个数为n(n>1),则邻接矩阵元素的个数为

边数无关。 5、

6、如果一棵树有n1个度为1的结点, 有n2个度为2的结点, ? , nm个度为m的结点, 试问有多少个度为0的结点? 试推导之。

答：总结点数 n = n0 + n1 + n2 + … + nm

总分支数 e = n-1 = n0 + n1 + n2 + … + nm-1 = m*nm + (m-1)*nm-1 + … + 2*n2 + n1 则有 n0=1+0*n1+1*n2+2*n3+...(m-1)*nm

7、有n个顶点的无向连通图至少有多少条边？有n个顶点的有向强连通图至少有多少条边？试举例

说明

答：n个顶点的无向连通图至少有n-1条边,n个顶点的有向强连通图至少有n条边.例如:

特例情况是当n = 1时,此时至少有0条边，一个环也是. 8、简述分块查找算法的思想。

答：（1）首先查找索引表 ，索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。 （2）然后在已确定的块中进行顺序查找 由于块内无序，只能用顺序查找。 9、什么是AOV网的关键路径？

答：用顶点表示活动，用弧表示活动间的优先关系的有向图，叫顶点表示活动的网，简称AOV

网，在AOV-网中路径长度最长的路径叫关键路径。 10、试分别找出满足以下条件的所有二叉树: (1) 二叉树的前序序列与中序序列相同; (2) 二叉树的中序序列与后序序列相同; (3) 二叉树的前序序列与后序序列相同。

答：1) 二叉树的前序序列与中序序列相同：空树或缺左子树的单支树或只有根节点的二叉树；

(2) 二叉树的中序序列与后序序列相同：空树或缺右子树的单支树或只有根节点的二叉树； (3) 二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。 11、数据结构与数据类型有什么区别？

答：“数据结构”这一术语有两种含义，一是作为一门课程的名称；二是作为一个科学的概念。

作为科学概念，目前尚无公认定义，一般认为，讨论数据结构要包括三个方面，一是数据的逻辑结构，二是数据的存储结构，三是对数据进行的操作（运算）。而数据类型是值的集合和操作的

第 页 7 共 23 页

n2，即顶点个数的平方，与图的

已知某图的邻接表，如何建立该图的邻接矩阵？

集合，可以看作是已实现了的数据结构，后者是前者的一种简化情况。 12、一棵度为2的树与一棵二叉树有何区别？

答：一棵度为二的有序树与一棵二叉树的区别在于:有序树的结点次序是相对于另一结点而言

的，如果有序树中的子树只有一个孩子时，这个孩子结点就无须区分其左右次序，而二叉树无论其孩子数是否为2，均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结点而言而是确定的。

13、对于有n个顶点的无向图，采用邻接矩阵表示，如何判断以下问题： 图中有多少条边？任意两

个顶点i和j之间是否有边相连？任意一个顶点的度是多少？ 答：1）邻接矩阵中非零元素个数除2。

（2）设邻接矩阵为A，若aij=1，则i,j有边直接相连；若aik=1，akj=1则经过k有边直接相连。 （3）统计以该点为行的非零元素个数。

14、求网的最小生成树有哪些算法？各适用于哪些情况？为什么？ 答：有普里姆算法和克鲁斯卡尔算法。

1）普里姆算法的时间复杂度为O(n),与网中的边无关，因此适用于求边稠密的网的生成树。 2）克鲁斯卡尔算法恰恰相反，他的时间复杂度为O(eloge)(e为网中的边数)，因此它相对于普里姆算法而言，适合于求边稀疏的网的最小生成树。

15、简述顺序查找法，折半（二分）查找法和分块查找法对被查找表中元素中的要求。

答：1）顺序查找法：表中元素可以任意次序存入。

2）二分查找法：表中元素必须以关键字的大小递增或递减的次序有序列且顺序表存储。

3）分块查找法：表中元素块内的元素可以任意次序存放，但块与块之间必须以关键字的大小递增（或递减）存放，即前一块内所有元素的关键字都不能大（或小）于后一块内任何元素的关键字。

2

16、 一棵高度为h的满k叉树有如下性质: 第h层上的结点都是叶结点, 其余各层上每个结点都有

k棵非空子树, 如果按层次自顶向下, 同一层自左向右, 顺序从1开始对全部结点进行编号, 试

问:

(1) 各层的结点个数是多少?

(2) 编号为i的结点的父结点(若存在)的编号是多少? (3) 编号为i的结点的第m个孩子结点(若存在)的编号是多少?

(4) 编号为i的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少?

答：(1) ki ( i = 0, 1, ??, h ) (2) ?i?k?2? (3) ( i-1)*k + m + 1

?k???第 页 8 共 23 页

i?k?2?(4) ( i-1 ) % k ? 0 或 i?? 时有右兄弟，右兄弟为i + 1。 ?k?*k??17、在单链表中设置头结点的作用是什么？

【答案】主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必

另作判断。另外，不论链表是否为空，链表头指针不变。

18、一个有序表是采用链式存储的，那么你能采用什么样的查找技术从该表中查找某个给定的关键

字？ 【答案】顺序查找法进行查找。

19、 给定一组权值: 23, 15, 66, 07, 11, 45, 33, 52, 39, 26, 58, 试构造一棵具有最小带权外

部路径长度的扩充4叉树, 要求该4叉树中所有内部结点的度都是4, 所有外部结点的度都是0。这棵扩充4叉树的带权外部路径长度是多少?

20、 设有序顺序表中的元素依次为017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765,

897, 908。试画出对其进行折半搜索时的二叉搜索树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。

145(1?2*2?3*4?4*7)?14 ASLsucc = 14159(3?4*14)?15 ASLunsucc = 15

第 页 9 共 23 页

21、有一份电文中共使用5个字符：a、b、c、d、e，它们的出现频率依次为4、7、5、2、4，试画

出对应的哈夫曼树，并求出每个字符的哈夫曼编码

五、写出下列各题的构造过程：

1、已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则构造出此二叉树并写其后序

遍历的结果。

2、请画出下图所示的树所对应的二叉树 。 3

1 2 4 6 8 5 7 第 页 10 共 23 页