Question

数据结构：二叉树判定题，求大神指点，谢谢！！！

n个结点的完全二叉树按层编号，对编号为i的结点的正确论述是
A，若i为偶数，则该结点右兄弟编号为i+1
B，若i为奇数，则该结点左兄弟编号为i-1
C，若i<=n，则该结点双亲编号是i+1
D，若2i<=n, 则该结点左兄弟编号是2i

Answer 1

1. 设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（ B ）。
(A) 99 (B) 97 (C) 91 (D) 93 不知道该怎么做，给讲讲吧~

2. 设一棵三叉树中有50个度数为0的结点，21个度数为2的结点，则该二叉树中度数为3的结点数有______个。 弄不懂~~~

3. 下面程序段的功能是实现一趟快速排序，请在下划线处填上正确的语句。 书上有，看的也不太理解，再给讲讲while里面的语句含义吧
struct record {int key;datatype others;};
void quickpass(struct record r[], int s, int t, int &i)
{
int j=t; struct record x=r[s]; i=s;
while(i<j)
{
while (i<j && r[j].key>x.key) j=j-1; if (i<j) {r[i]=r[j];i=i+1;}
while (___i<j && r[j].key<x.key___) i=i+1; if (i<j) {r[j]=r[i];j=j-1;}
}
______r[i]=x___________;
}

4．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（ D ）。

(A) 空或只有一个结点 (B) 高度等于其结点数

(C) 任一结点无左孩子 (D) 任一结点无右孩子

我的答案是B, 左，右单支数 遍历情况不都一样么？？

5． 设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（D ）。

(A) 20 (B) 30 (C) 40 (D) 45

我的答案是 48 怎么能算错了，什么意思了？~~ 呵呵

6．设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（ 错 ）

举个例子， 左，右单支数 就能判断 是错的 对不对？