Pwuhenp
a=22，3，30，4，60，11，58，18，40，16;low=0;high=9;a=11，3，16，4，18，22，58，60，40，30;low=0;high=4;a=4，3，11，16，18，22，58，60，40，30;low=3;high=4;a=4，3，11，16，18，22，58，60，40，30;low=4;high=4;a=3，4，11，16，18，22，58，60，40，30;low=0;high=0;a=3，4，11，16，18，22，40，30，58，60;low=6;high=7;a=3，4，11，16，18，22，30，40，58，60;low=6;high=6;fails 
/*以下是用c++ 实现的二叉排序树的源代码*/ #include typedef struct TreeNode { 二叉排序树****************/ BiSortTree::BiSortTree() { cout<<"建立一棵二叉排序树，请输入你要建
本文出自数据结构十套笔试题之第一套，本站为原创作品，转载请注明出处，谢谢！一、选择题1、栈和队列的共同特点是( )。A只允许在端点处插入和删除元素 B都是先进后出 C都是先进先出 D没有共同点参考答案是：A2、用链接方式存储的队列，在进行插入运算时( )A 仅修改头指针 B 头、尾指针都要修改 C 仅修改尾指针 D头、尾指针可能都要修改参考答案是：D3、以下数据结构中哪一个是非线性结构？( )A 队列 B 栈 C 线性表 D 二叉树参考答案是：D4、设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。A．688 B．678 C．692 D．696参考答案是：C5、树最适合用来表示( )。A有序数据元素 B无序数据元素C元素之间具有分支层次关系的数据 D元素之间无联系的数据参考答案是：C6、二叉树的第k层的结点数最多为( )A 2k-1 B2K+1 C2K-1 D 2k-1参考答案是：D7、若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A 1，2，3 B 9，5，2，3C 9，5，3 D 9，4，2，3参考答案是：D8、对n个记录的文件进行快速排序，所需要的辅助存储空间大致为（ ）A O（1） B O（n） C O（1og2n） D O（n2）参考答案是：C9、对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）= K %9作为散列函数，则散列地址为1的元素有（ ）个。A．1 B．2 C．3 D．4参考答案是：D10、设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。A5 B6 C7 D8参考答案是：A二、填空题1、通常从四个方面评价算法的质量：_________、_________、_________和_________。参考答案是：正确性 易读性 强壮性 高效率2、一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。参考答案是：O(n)3、假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为_______个，树的深度为_______，树的度为_________。参考答案是：9 3 34、后缀算式9 2 3 + - 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式为_________________。参考答案是：-1 3 4 X * + 2 Y * 3 / -5、若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有 ________个指针域， 其中有________个指针域是存放了地址，有________________个指针是空指针。参考答案是：2n n-1 n+16、对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_______个和________个。参考答案是：e 2e7、AOV网是一种_____________的图。参考答案是：有向无回路8、在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。参考答案是：n(n-1)/2 n(n-1)9、假定一个线性表为(12，23，74，55，63，40)，若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为__________________、 ___________________、_______________________和__________________________。参考答案是：（12，40） （ ） （74） （23，55，63）10、向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度___________。参考答案是：增加111、在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序过程的时间复杂度为________。参考答案是：O(log2n) O(nlog2n)12、在快速排序、堆排序、归并排序中，_________排序是稳定的。参考答案是：归并
#includetypedef struct TreeNode{int key;struct TreeNode *left;struct TreeNode *right;}treeNode;class BiSortTree{public: BiSortTree(void);void desplayTree(void);//显示这个树void insertTree(int key);//在树中插入一个值 deleteTree(int key);//在树中删除一个值 treeNode* searchTree(int key);//在树中查找一个值 ~BiSortTree();private:treeNode* buildTree(treeNode* head，int number);//建立一个树treeNode* search(treeNode* head ，int key);//查找treeNode* BiSortTree::searchParent(treeNode* head，treeNode* p);//查找出p的父亲节点的指针treeNode* BiSortTree::searchMinRight(treeNode* head);//找到右子树中最小的节点void showTree(treeNode* head);//显示 void destroyTree(treeNode* head);//删除treeNode *Head;};/**************以下是建立一个二叉排序树****************/BiSortTree::BiSortTree(){ cout<<"建立一棵二叉排序树，请输入你要建树的所有数(以-1 作为结束标志!): "<>number; while(number!=-1) { Head=buildTree(Head，number); cin>>number; }}treeNode* BiSortTree::buildTree(treeNode* head，int number){treeNode *p; p=new treeNode; p->key=number;p->left =p->right=NULL;if(head==NULL){ return p;}else{ if(p->key key)head->left=buildTree(head->left，number); else head->right=buildTree(head->right，number); return head;}}/*****************以下是在一棵二叉排序树插入一个数***********************************/void BiSortTree::insertTree(int key){Head=buildTree(Head，key);}/*****************以下是在一个二叉排序树查找一个数是否存在*************************/treeNode* BiSortTree::searchTree(int key){return search(Head，key);}treeNode* BiSortTree::search(treeNode* head ，int key){ if(head==NULL)return NULL;if(head->key==key)return head;else{if(keykey )return search( head->left，key); elsereturn search(head->right，key);}}/************以下是在一个二叉排序树删除一个给定的值*********************************/BiSortTree::deleteTree(int key){treeNode *p;p=NULL; p=search(Head，key);if(p==NULL){cout<<"Don't find the key";} if(p==Head){Head=NULL;}else{treeNode* parent;parent=searchParent(Head，p);if(p->left==NULL&&p->right==NULL)//叶子节点{ if(parent->left==p){parent->left=NULL;} else{parent->right=NULL;}} else//非叶子节点{ if(p->right==NULL)//该节点没有右孩子 { if(parent->left==p) { parent->left=p->left ; } else { parent->right=p->left; } } else//该点有左右孩子 { treeNode * rightMinSon，* secondParent;//secondParent为右子树中的最小节点的父亲 rightMinSon=searchMinRight(p->right); secondParent=searchParent(p->right ，rightMinSon); secondParent->left=rightMinSon->right; if(p->right==rightMinSon)//右子树中的最小节点的父亲为p { p->right=rightMinSon->right ; } p->key=rightMinSon->key ; }}}}treeNode* BiSortTree::searchParent(treeNode* head，treeNode* p){if(head->left==p||head->right==p||head==p||head==NULL)return head; else{if(p->keykey)return searchParent(head->left ，p);elsereturn searchParent(head->right ，p);}}treeNode* BiSortTree::searchMinRight(treeNode* head)//找到右子树中最小的节点{if(head->left ==NULL||head==NULL){return head;}else{return searchMinRight(head->left);}}/*****************以下是显示一个二叉排序树****************************************/void BiSortTree::desplayTree(void){showTree(Head);cout<left ) ; cout<key<<' ' ;showTree(Head->right) ;}}/*****************以下是删除一棵整二叉排序树************************************/BiSortTree::~BiSortTree(){cout<<"已经消除了一棵树!!!!"<left );destroyTree(head->right );delete head;}}/*********************/void print(){ cout<>choiceNumber; switch(choiceNumber) { case 1: desplayTree();break; case 2: cout<<"请插入一个数: "<>number; insertTree(number); desplayTree(); break; case 3: cout<<"请插入你要找数: "<>number; if(searchTree(number)==NULL) { cout<<"没有发现"<>number; deleteTree(number); desplayTree(); break; default: break; } cout<<"你是否要继续(Y/N)?"<>flag; if(flag=='N'||flag=='n')break;}}
