工程2010秋2入学试题答案

1、数据结构试题(60 分)一、 选择题。将下列问题的正确的序号填入方框中（本题共 16 分， 每框 2 分 ）1、一棵前序序列为 1，2，3，4 的二叉树，它的中序序列不可能的是 A 。【供选择的】(A)4,1,2,3(B)4,3,2,1(C)2,4,3,1(D)3,4,2,12、对于一棵具有 n 个结点的二叉树，该二叉树中空的二叉树的总的棵数为 【供选择的】C 。(A)n-1 (B) n(C) n+1(D) 2n3、若某棵树的前序遍历的序列为 A、B、C、D、E、F、G，后序遍历的序列为 B、E、F、D、G、C、A。 则该树的树形能否唯一确定的正确的是B。【供选择的】(A) 无 法 确 定(B

2、) 可 唯 一 确 定(C) 有 多 棵 符 合 条 件 的 树(D)以上都不对4、顺序查找法在平均情况下成功地找到具有给定关键字的结点的时间复杂性的级别为B。注意：被查结点序列共有 n 个结点。【供选择的(A) O(1)】(B) O（n） (C)(D)O（n2） (E)O（nlog2n）O（log2n）5、在含有 n 个结点的树中，若只有两种结点，即度为 0 的结点和度为 K 的其他结点，那么度为 K 的结点的总数为D。【供选择的】(A) K(B) n-1 (C) (K-1)n +1)/K(D)（n-1）/k (E) 以上都不对6、阅读以下程序段：for (i=1;i=n;i+)for (j

3、=1;j100000。 现要从这个结点序列中，挑选出最大、次最大、第三大的结点。学生 A 和 B 分别采用了二种不同的方法。学生 A使用快速排序法将该序列进行快速排序，然后得到最大、次最大、第三大的结点。学生 B 则首先建立一个最大化堆，得到最大结点。调整这个堆之后，得到次最大结点。然后，再调整这个堆，得到第三大的结点。学生 A 和 B 的方法之中，谁的方法更快呢？为什么？答：B 的方法更快，因 A 的快速排序法，在比较好的情况下，时间代价为 O（nlogn）,而 B 建立一个堆花费的时间为 O(n),而堆的调整花费的时间为 2logn。2、将序列 A、B、C、D 中的字符依次进栈，字符进栈之

4、后，可以马上出栈，也可以以后出栈。这样可以得到了若干种输出序列。请问序列 D、C、B、A 是正确的输出序列吗？答：D、C、B、A 是正确的输出序列，因为若要使得 D 作为第一个结点输出，那么在它之前得 A、B、C 应依次进栈，这时 A 在栈底，而 C 在栈顶，故可以得到输出序列 D、C、B、A。3、设某通信电文由 a、b、c、d、e、f，它们出现的频率之比分别为 23，5，14，8，25，7；试问字符 b 的答： 4 位二进制位。编码由几个二进制位？4、一棵二叉排序树初始时为空，现将关键字为 45，24，53，12，26，9 的结点依次插入到二叉排序树之中，请画出答：简单，略。全部完成后的二叉

5、排序树的树形。5、在有向图的邻接矩阵表示法中，如何求出任何一个结点的出度和入度？答：相应结点的行所包含的一的个数为该结点的出度，而相应结点的列所包含的一的个数为该结点的入度。6、在一棵二叉树中，有两个结点 A 和 B。序遍历时，A 在 B 之前；而在后序遍历时，A 在 B 之后。请问 A 一定是 B 的祖先结点吗？为什么？答：A 一定是 B 的祖先结点，因为若满足序遍历时，A 在 B 之前，那么在树或子树中，A 要么是根，而 B 必为左子树或右子树中的结点；或者 A 为左子树中的结点而 B 为右子树中的结点，又因为在后序遍历时，A 在 B 之后，意味着 A 为左子树中的结点而 B 为右子树中的

6、结点是不可能的，所以上述结论成立。三、程序设计题：（本题 20 分，每题 10 分 ）1、已知一棵非空二叉树是以二叉链表（或标准形式）的形式的，其结点结构如下：dataleftright结点结构的说明如下：typedef struct node data;struct node * left; struct node * right; node,* Bitree ；/ 结点的数据场。/ 给出结点的左儿子的地址。/ 给出结点的右儿子的地址。现已知二叉树的根结点的地址为 R。请写一个函数，返回该二叉树中所有结点的数据场之值的总和。count( BitreeR ) 解：Bitree p = R;co

7、unt=0; inistack(s);if ( !p ) return 0; push(s, p );while( !emptystack(s)pop(r,s);count += p-data;if ( p-right )if ( p-left)push(s, p-right );push(s, p-left );return count;2、已知结点的单链表的结点的结构如下：datanext其中：data:next:结点的数据场，其类型为；给出结点的数据值。结点的指针场，存放的是该结点的直接后继结点的地址。现已知该单链表的头结点的地址为 h。现给定一个整数值 key 。请写一个函数，函数返回该单链表的结点的数据场之值大于 key 的结点的个数。图 1 为结点的单链表的实例。设给定的参数 key 为 8，则函数的返回值为 2。注意：头结点的指针场 next 给出单链表的第一个结点的地址。datanextdatanexth图 1、一个结点的单链表的初始情况解：typedef struct node data;struct node * next; Node,* LinkList；/ 结点的数据场。/ 给出后继结点的地址。great ( L