第三章测试1.
以下关于红黑树的说法，错误的是（ ）。
A:其他选项均不正确 B:红黑树是一棵二叉查找树 C:红黑树是一棵平衡树 D:红黑树表示的是一棵2-3查找树
答案:A
2.以下关于散列表的说法，错误的是（ ）。
A:散列表需要采用散列函数进行散列值的计算 B:散列表又叫做哈希表 C:散列表解决的碰撞的方法有拉链法和线性探测法 D:如果采用双向散列函数，散列表可以被可以攻击
答案:ABCD
A:错 B:对
答案:A
给定二叉查找树的数据结构，进行插入操作。
public class BST<Key extends Comparable<Key>, Value> {
private Node root; // root of BST
private class Node {
private Key key; // sorted by key
private Value val; // associated data
private Node left, right; // left and right subtrees
private int size; // number of nodes in subtree
public Node(Key key, Value val, int size) {
this.key = key;
this.val = val;
this.size = size;
}
}
public BST() {
}
private Node put(Node x, Key key, Value val) {
if (x == null) return new Node(key, val, 1);
int cmp = key.compareTo(x.key);
if (cmp < 0) x.left = put(x.left, key, val);
else if (cmp > 0) x.right = put(x.right, key, val;
else x.val = val;
return ( ？ );
}
}
A:
x.val
B:val C:x D:key答案:C
给定如下的红黑树的数据结构，请完成红黑树的插入（put方法）操作。
public class RedBlackBST<Key extends Comparable<Key>, Value> {
private static final boolean RED = true;
private static final boolean BLACK = false;
private Node root; // root of the BST
// BST helper node data type
private class Node {
private Key key; // key
private Value val; // associated data
private Node left, right; // links to left and right subtrees
private boolean color; // color of parent link
private int size; // subtree count
public Node(Key key, Value val, boolean color, int size) {
this.key = key;
this.val = val;
this.color = color;
this.size = size;
}
}
public RedBlackBST() {
}
// is node x red; false if x is null ?
private boolean isRed(Node x) {
if (x == null) return false;
return x.color == RED;
}
private Node rotateRight(Node h) {
assert (h != null) && isRed(h.left);
// assert (h != null) && isRed(h.left) && !isRed(h.right); // for insertion only
Node x = h.left;
h.left = x.right;
x.right = h;
x.color = h.color;
h.color = RED;
x.size = h.size;
h.size = size(h.left) + size(h.right) + 1;
return x;
}
// make a right-leaning link lean to the left
private Node rotateLeft(Node h) {
assert (h != null) && isRed(h.right);
// assert (h != null) && isRed(h.right) && !isRed(h.left); // for insertion only
Node x = h.right;
h.right = x.left;
x.left = h;
x.color = h.color;
h.color = RED;
return x;
}
// flip the colors of a node and its two children
private void flipColors(Node h) {
h.color = !h.color;
h.left.color = !h.left.color;
h.right.color = !h.right.color;
}
// insert the key-value pair in the subtree rooted at h
private Node put(Node h, Key key, Value val) {
if (h == null) return new Node(key, val, RED, 1);
int cmp = key.compareTo(h.key);
if (cmp < 0) h.left = put(h.left, key, val);
else if (cmp > 0) h.right = put(h.right, key, val);
else h.val = val;
// fix-up any right-leaning links
if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
if (isRed(h.left) && isRed(h.right)) flipColors(h);
return ( ？ );
}
}
}
A:
h.right
B:null C:h D:h.left
答案:C
