| 题号 | 题目 | 答案 |
|---|---|---|
| 1 | 对二叉搜索树进行什么遍历可以得到从小到大的排序序列？ | 中序遍历 |
| 2 | 在有N个结点且为完全二叉树的二叉搜索树中查找一个键值，其平均比较次数的数量级为： | O(logN) |
| 3 | 若二叉搜索树是有N个结点的完全二叉树，则不正确的说法是： | 最大值一定在最后一层 |
| 4 | 已知8个数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉搜索树后，最后两层上的结点总数为： | 2 |
| 5 | 若一棵二叉树的前序遍历序列是{ 4, 2, 1, 3, 6, 5, 7 }，中序遍历序列是{ 1, 2, 3, 4, 5, 6, 7 }，则下列哪句是错的？ | 6是3的父结点 |
| 6 | 将{ 3, 8, 9, 1, 2, 6 }依次插入初始为空的二叉搜索树。则该树的后序遍历结果是： | 2, 1, 6, 9, 8, 3 |
| 7 | 若二叉搜索树是有N个结点的完全二叉树，则不正确的说法是： | 最大值一定在叶结点上 |
| 8 | 对二叉搜索树进行中序遍历，得到的结点序列是（）。 | 按关键字递增有序 |
| 9 | 在含有27个结点的二叉搜索树上，查找关键字为35的结点，则被依次比较的关键字有可能是。 | A |
| 10 | 以下列序列构造二叉搜索树，与用其他3个序列所构造的结果不同的是（）。 | A |
1、二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。
7、 如下图8 是根节点，6 是左子节点
本题要求实现函数，判断给定二叉树是否二叉搜索树。
函数接口定义：
bool IsBST ( BinTree T );
其中BinTree结构定义如下：
typedef struct TNode *Position;typedef Position BinTree;struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;}; 函数IsBST须判断给定的T是否二叉搜索树，即满足如下定义的二叉树：
定义：一个二叉搜索树是一棵二叉树，它可以为空。如果不为空，它将满足以下性质：
非空左子树的所有键值小于其根结点的键值。
非空右子树的所有键值大于其根结点的键值。
左、右子树都是二叉搜索树。
如果T是二叉搜索树，则函数返回true，否则返回false。
Yes
No
#include <stdio.h>#include <stdlib.h>typedef enum { false, true } bool;typedef int ElementType;typedef struct TNode *Position;typedef Position BinTree;struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;};BinTree BuildTree(); /* 由裁判实现，细节不表 */bool IsBST ( BinTree T );int main(){
BinTree T;
T = BuildTree();
if ( IsBST(T) ) printf("Yes\n");
else printf("No\n");
return 0;}/* 你的代码将被嵌在这里 */bool IsBST(BinTree T){BinTree p;if (!T)// 树为空return true;if (!T->Left && !T->Right)// 只有根节点return true;p = T->Left;// 先向左查if (p){while (p->Right)//左子树的最大值在右下角p = p->Right;if (p->Data > T->Data)return false;}p = T->Right;// 再向左查if (p){while (p->Left)//右子树的最小值在左下角p = p->Left;if (p->Data < T->Data)return false;}return IsBST(T->Left) && IsBST(T->Right);// 运用递归再查每个左右子树} 给定一个插入序列就可以唯一确定一棵二叉搜索树。然而，一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树，都得到一样的结果。于是对于输入的各种插入序列，你需要判断它们是否能生成一样的二叉搜索树。
输入包含若干组测试数据。每组数据的第1行给出两个正整数N (≤10)和L，分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出N个以空格分隔的正整数，作为初始插入序列。最后L行，每行给出N个插入的元素，属于L个需要检查的序列。
简单起见，我们保证每个插入序列都是1到N的一个排列。当读到N为0时，标志输入结束，这组数据不要处理。
对每一组需要检查的序列，如果其生成的二叉搜索树跟对应的初始序列生成的一样，输出“Yes”，否则输出“No”。
4 23 1 4 23 4 1 23 2 4 12 12 11 20
Yes No No
#include<iostream>#include<queue>using namespace std;struct BSTNode {//数据域int val;//指针域BSTNode *left,*right;//节点的构造BSTNode(int v){val = v;left = NULL;right = NULL;}};//BST的数据结构class BST {private:BSTNode *root;public:BST() { root = NULL; }//通过插入函数构造BSTvoid insert(int n);//比较另一棵BST与本树是否相同bool jugde(BST t);};void BST::insert(int n){BSTNode *p = root,
*pp = NULL;while (p != NULL){pp = p;if (p->val>n) p = p->left;else p = p->right;
}BSTNode *t = new BSTNode(n);if (root != NULL)if (pp->val > n) pp->left = t;else pp->right = t;else root = t;}//通过层序遍历，对比bool BST::jugde(BST t){BSTNode*t1 = root,*t2 = t.root;queue<BSTNode*>q1,q2;while (t1 != NULL && t2 != NULL){if (t1->val != t2->val) return false;if ((t1->left != NULL && t2->left == NULL) || (t1->left == NULL && t2->left != NULL)|| (t1->right != NULL && t2->right == NULL) || (t1->right == NULL && t2->right != NULL)) return false;if ((t1->left != NULL && t2->left != NULL)) { q1.push(t1->left); q2.push(t2->left); }if ((t1->right != NULL && t2->right != NULL)) { q1.push(t1->right); q2.push(t2->right); }if (q1.size() != 0 && q2.size() != 0){t1 = q1.front(); t2=q2.front();q1.pop(); q2.pop();}else t1 = NULL;}return true;}int main(){int n, m;while (cin>>n,cin>>m){BST bst;for (int i = 0; i < n; i++){int num; cin >> num;bst.insert(num);}for (int i = 0; i < m; i++){BST t;for(int j=0;j<n;j++){int num; cin >> num;t.insert(num);}if (bst.jugde(t)) cout << "Yes" << endl;else cout << "No" << endl;}}return 0;}
联系客服
