下载文档原格式
数据结构与算法上机作业第五章查找一、选择题1、若构造一棵具有n个结点的二叉排序树，在最坏情况下，其高度不超过 B 。
A. n/2B. nC. (n+1)/2D. n+12、分别以下列序列构造二叉排序数（二叉查找树），与用其他3个序列所构造的结果不同的是 C ：A. (100, 80, 90, 60, 120, 110, 130)B. (100, 120, 110, 130, 80, 60, 90)C. (100, 60, 80, 90, 120, 110, 130)D. (100, 80, 60, 90, 120, 130, 110)3、不可能生成下图所示的二叉排序树的关键字的序列是 A 。
A. 4 5 3 1 2B. 4 2 5 3 1C. 4 5 2 1 3D. 4 2 3 1 54、在二叉平衡树中插入一个结点造成了不平衡，设最低的不平衡点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作 C 型调整使其平衡。
A. LLB. LRC. RLD. RR5、一棵高度为k的二叉平衡树，其每个非叶结点的平衡因子均为0，则该树共有 C 个结点。
A. 2k-1-1B. 2k-1+1C. 2k-1D. 2k+16、具有5层结点的平衡二叉树至少有 A 个结点。
A. 12B. 11C. 10D. 97、下面关于B-和B+树的叙述中，不正确的是 C 。
A. B-树和B+树都是平衡的多叉树B. B-树和B+树都可用于文件的索引结构C. B-树和B+树都能有效地支持顺序检索D. B-树和B+树都能有效地支持随机检索8、下列关于m阶B-树的说法错误的是 D 。
A. 根结点至多有m棵子树B. 所有叶子结点都在同一层次C. 非叶结点至少有m/2（m为偶数）或m/2+1(m为奇数)棵子树D. 根结点中的数据是有序的9、下面关于哈希查找的说法正确的是 C 。
A. 哈希函数构造得越复杂越好，因为这样随机性好，冲突小B. 除留余数法是所有哈希函数中最好的C. 不存在特别好与坏的哈希函数，要视情况而定D. 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单地将该元素删去即可10、与其他查找方法相比，散列查找法的特点是 C 。
数据结构作业系统_第九章答案9.26②试将折半查找算法改写成递归算法。
实现下列函数：int BinSearch(SSTable s, int low, int high, KeyType k);/* Index the element which key is k *//* in StaticSearchT able s. *//* Return 0 if x is not found. */静态查找表的类型SSTable定义如下：typedef struct {KeyType key;... ... // 其他数据域} ElemType;typedef struct {ElemType *elem;int length;} SSTable;int BinSearch(SSTable s, int low, int high, KeyType k)/* Index the element which key is k *//* in StaticSearchT able s. *//* Return 0 if x is not found. */{int mid=(low+high)/2;if(low>high)return 0;if(s.elem[mid].key==k)return mid;else if(s.elem[mid].key>k)return BinSearch(s,low,mid-1,k); else return BinSearch(s,mid+1,high,k);}9.31④试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。
且树中结点的关键字均不同。
实现下列函数：Status IsBSTree(BiTree t);/* 判别给定二叉树t是否为二叉排序树。
*//* 若是，则返回TRUE，否则FALSE */二叉树的类型BiTree定义如下：typedef struct {KeyType key;... ... // 其他数据域} ElemType;typedef struct BiTNode {ElemType data;BiTNode *lchild,*rchild;}BiTNode, *BiTree;Status IsBSTree(BiTree t)/* 判别给定二叉树t是否为二叉排序树。
#include<stdio.h>#include<stdlib.h>#define max 10typedef struct node{int data;node *lchild,*rchild;}Bitree;Bitree *B[max];int temp=0;int Btree[max];Bitree *Creatree(){ //建立二叉树Bitree *T,*S;int ch;int front,rear,sign;sign=0;front=0;rear=-1;T=NULL;printf("建立二叉树(1表示虚结点,0表示输入结束):\n");scanf("%d",&ch);while(ch!=0){if(ch!=1){ //输入结点不是虚结点S=(Bitree*)malloc(sizeof(Bitree));S->data=ch;S->lchild=S->rchild=NULL;rear++;B[rear]=S;if(rear==front){T=S;sign++;}else{if(sign%2==1) //寻找父结点B[front]->lchild=S;if(sign%2==0){B[front]->rchild=S;front++;}sign++;}}else{ //输入结点为虚结点if(sign%2==0)front++;sign++;}scanf("%d",&ch);}return T;}void Inorder(Bitree *T){ //中序遍历二叉树，并将每个结点数据存入数组中if(T!=NULL){Inorder(T->lchild);printf("%d\t",T->data);Btree[temp]=T->data;temp++;Inorder(T->rchild);}}int Judgesort_bitree(int Btree[]){ //判断是否是二叉树int i,sign=1;for(i=0;i<temp-1;i++){if(Btree[i]>Btree[i+1]){sign=0;break;}}return sign;}void Judgeout(int a){ //判断输出if(a==1)printf("给定二叉树是二叉排序树!\n");if(a==0)printf("给定二叉树不是二叉排序树!\n");}void main(){Bitree *T;T=Creatree();printf("中序遍历:\n");Inorder(T);printf("\n");}Judgeout(Judgesort_bitree(Btree));题目：试写一算法判别给定的二叉树是否为二叉排序树，设此二叉树以二叉链表存储，且树中结点的关键字均不相同。
2022年河南工程学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（）方法是哈希文件的关键。
A.哈希函数B.除余法中的质数C.冲突处理D.哈希函数和冲突处理2、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。
A.快速排序B.堆排序C.归并排序D.直接插入排序3、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表4、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>， <V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>｝，G的拓扑序列是（）。
A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V75、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。
A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)6、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。
下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。
Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ7、下列关于无向连通图特性的叙述中，正确的是（）。
Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。
第9章 查找答案一、填空题1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。
2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 9 次。
设有100个结点，用二分法查找时，最大比较次数是 7 。
3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。
解：显然，平均查找长度＝O （log 2n ）<5次（25）。
但具体是多少次，则不应当按照公式)1(log 12++=n nn ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。
因为这是在假设n ＝2m-1的情况下推导出来的公式。
应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.7 ！！！4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。
5. 在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是 散列查找 。
6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。
7. 有一个表长为m 的散列表，初始状态为空，现将n （n<m ）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。
如果这n 个关键码的散列地址都相同，则探测的总次数是 n(n-1)/2=（ 1＋2＋…＋n-1） 。
(而任一元素查找次数 ≤n-1)二、单项选择题（ B ）1．在表长为ｎ的链表中进行线性查找，它的平均查找长度为Ａ. ＡＳＬ＝ｎ; Ｂ. ＡＳＬ＝（ｎ＋１）／２;Ｃ. ＡＳＬ＝n ＋１; Ｄ. ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１（ A ）2. 折半查找有序表（4，6，10，12，20，30，50，70，88，100）。
第6章树和二叉树习题解答一、下面是有关二叉树的叙述，请判断正误（每小题1分，共10分）（√）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。
（×）2.二叉树中每个结点的两棵子树的高度差等于1。
（√）3.二叉树中每个结点的两棵子树是有序的。
（×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。
（×）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。
（应当是二叉排序树的特点）（×）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。
（应2i-1）（×）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
（×）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。
（应2i-1）（√）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。
（正确。
用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。
由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。
）即有后继链接的指针仅n-1个。
（√）10. 〖01年考研题〗具有12个结点的完全二叉树有5个度为2的结点。
最快方法：用叶子数＝[n/2]＝6，再求n2=n0-1=5二、填空（每空1分，共15分）1．由３个结点所构成的二叉树有5种形态。
2. 【计算机研2000】一棵深度为6的满二叉树有n1+n2=0+ n2= n0-1=31 个分支结点和26-1 =32个叶子。
注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。
3．一棵具有２５７个结点的完全二叉树，它的深度为9。
（注：用⎣ log2(n) ⎦+1= ⎣ 8.xx ⎦+1=94.【全国专升本统考题】设一棵完全二叉树有700个结点，则共有350个叶子结点。
一、算法设计题（每题15分，共60分）答题要求：①用自然语言说明所采用算法的思想；②给出每个算法所需的数据结构定义，并做必要说明；③写出对应的算法程序，并做必要的注释。
1、有一个带头结点的单链表，每个结点包括两个域，一个是整型域info，另一个是指向下一个结点的指针域next。
假设单链表已建立，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保留一个。
3、约瑟夫环问题（Josephus问题）是指编号为1、2、…，n的n（n>0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，…，如此重复直到所有的人全部出列为止。
现要求采用循环链表结构设计一个算法，模拟此过程。
4、编程实现单链表的就地逆置。
23．在数组 A[1..n]中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个.5、设计一个尽可能的高效算法输出单链表的倒数第K个元素。
3、假设以I和O分别表示入栈和出栈操作。
栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。
（15分）（1）下面所示的序列中哪些是合法的？A. IOIIOIOOB. IOOIOIIOC. IIIOIOIOD. IIIOOIOO（2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。
若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。
5、设从键盘输入一整数的序列：a1, a2, a3，…，an,试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。
算法应对异常情况（入栈满等）给出相应的信息。
设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为W1，W2，...，W n。
树和二叉树习题（39）1．请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink-rlink 法存储。
2．假设K1，…，Kn 是n 个关键词，试解答：(1) 试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2，…，Kn 时，用算法建立一棵以LLINK / RLINK 链接表示的二叉查找树。
(2) 设计一个算法，打印出该二叉查找树的嵌套括号表示结构。
例如，K1=B，K2=A，K3=D，K4=C，K5=E，则用二叉查找树的插入算法建立的二叉查找树为：该二叉查找树的嵌套括号表示结构为：B（A，D（C，E））3．写出在二叉排序树中删除一个结点的算法，使删除后仍为二叉排序树。
设删除结点由指针p 所指，其双亲结点由指针 f 所指，并假设被删除结点是其双亲结点的右孩子。
用类PASCAL（或C）语言将上述算法写为过程形式。
4. 已知二叉树排序树中某结点指针p,其双亲结点指针为fp,p 为fp 的左孩子，试编写算法，删除p 所指结点。
5．二叉排序树采用二叉链表存储。
写一个算法，删除结点值是X 的结点。
要求删除该结点后,此树仍然是一棵二叉排序树，并且高度没有增长（注：可不考虑被删除的结点是根的情况）。
6. 设记录R1,R2,…,Rn 按关键字值从小到大顺序存储在数组r[1..n]中,在r[n+1]处设立一个监督哨,其关键字值为+∞; 试写一查找给定关键字k 的算法;并画出此查找过程的判定树,求出在等概率情况下查找成功时的平均查找长度。
7．设计算法以求解编号为i和j的两个结点的最近的公共祖先结点的编号。
8．元素集合已存入整型数组A[1..n]中，试写出依次取A 中各值A[i](1<=i<=n)构造一棵二叉排序树T 的非递归算法：CSBT(T,A)9．写出折半查找的算法，并要求它返回整型值i，当查找成功时，返回查找位置，查找不成功时返回0。
10．请编写算法：键树，又称数字查找树。
作业11．数据结构和数据类型两个概念之间有区别吗答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。
数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。
2．阅读下列C程序段，写出相应的执行结果（每小题4分，共8分）（1）。
printf(“Input x”);scanf(“%d”,&x);if (x<=30)if(x>20) y=x;else if (x>10) y=2*x;if (x>0&&x<30)printf(“x=%d,y=%d”,x,y);else printf(“输入数据错！”);试写出当x分别为18，8时的执行结果。
答：运行结果为：x=18，y=36x=8，y=运行前的值，且从x＝30开始为数据错3．分析下面各程序段的时间复杂度作业2（2）。
long int fact(n)int n;{long f;if(n>1)f=n*fact(n-1);else f=1;return(f);}main(){int n;long y;n=5;y=fact(n);printf(“%d,%ld\n”,n,y);}答：运行结果为：5，120 此题为递归运算2. s=0;for i=0; i<n; i++)for(j=0; j<n; j++)s+=B[i][j];sum=s;答：O（n2）1. for (i=0; i<n; i++)for (j=0; j<m; j++)A[i][j]=0;答：O（m*n）3. x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;解：因为x++共执行了n-1+n-2+ (1)n(n-1)/2，所以执行时间为O（n2）4. i=1;while(i<=n)i=i*3;答：O（log3n）1. 【严题集②】试比较顺序存储结构和链式存储结构的优缺点。
计算机专业基础综合（查找）-试卷1(总分：94.00，做题时间：90分钟)一、单项选择题(总题数：25，分数：50.00)1.单项选择题1-40小题。
下列每题给出的四个选项中，只有一个选项是最符合题目要求的。
__________________________________________________________________________________________ 2.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。
A.(n—1)／2B.n／2C.(n+1)／2 √D.n此题考查的知识点是顺序查找长度ASL的计算。
假设表长度为n，那么查找第i个数据元素需进行n一i+1次比较，即C i =n一i+l。
又假设查找每个数据元素的概率相等，即P i =1／n，则顺序查找算法的平均查找长度为：所以应选C。
3.顺序查找法适用于查找顺序存储或链式存储的线性表二分法查找只适用于查找顺序存储的有序表，平均比较次数为( )。
在此假定N为线性表中结点数，且每次查拔都是成功的。
A.N+1B.2log 2 NC.log 2 N √D.N／2此题考查的知识点是各类查找算法的比较次数计算。
顺序查找法用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败，其ASL=(n+1)／2，即查找成功时的平均比较次数约为表长的一半。
应选C。
4.顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为( )在此假定N为线性表中结点数，且每次查拔都是成功的。
A.N+1B.2log 2 NC.log 2 ND.N／2 √二分法查找过程可用一个称为判定树的二叉树描述，由于判定树的叶子结点所在层次之差最多为1，故n个结点的判定树的深度与n个结点的完全二叉树的深度相等，均为[log 2 n]+1。
这样，折半查找成功时，关键字比较次数最多不超过[log 2 n]+1。
课程设计任务书目录1 需求分析 (3)2 概要设计 (4)2.1存储结构设计说明 (4)2.2程序功能图 (4)2.3算法流程图 (5)3 详细设计 (7)3.1程序分析 (7)3.2程序源代码 (7)4 调试分析 (9)5 课程总结 (11)6参考文献 (12)1 需求分析图1-1 二叉树以图1-1所示的二叉树为例设计，建立一个以二叉链表方式存储的二叉树，输入结点信息时按照完全二叉树的结点顺序输入（1为虚结点，0为输入结束）。
由于一棵二叉排序树中序遍历后的序列是递增有序的，因此可利用中序遍历一棵二叉树后的序列是否递增有序来判断是否为二叉排序树。
如图，二叉树的结点输入顺序为77 80 90 50 1 68 88 1 1 34 56 0 （1为虚结点，0为输入结束），中序遍历之后的顺序为50 80 77 34 68 56 90 88 ，由于中序遍历之后的序列不是递增有序的，因此可判断出此二叉树不是二叉排序树。
2 概要设计2.1 存储结构设计说明typedef struct node{int data; //数据域node *lchild,*rchild; //左孩子指针，右孩子指针}Bitree; //结点的结构体定义2.2程序功能图图2-1 程序功能图2.3算法流程图选取部分核心流程图如下：图2-2 主要流程图图2-3 建立二叉树3 详细设计3.1程序分析建立一个以二叉链表方式存储的二叉树，建立二叉树时，按照完全二叉树的结点顺序输入，1表示虚结点，0表示输入结束。
若不是虚结点时，则建立一个新结点，并且将其作为左孩子或右孩子结点连接到它的父结点上（第一个结点无父结点）；若是虚结点，则将空结点（NULL）作为左孩子或右孩子结点连接到它的父节点上。
判定二叉树时，中序遍历整棵二叉树，访问根结点时将根结点信息存入一个数组中，以用来比较中序遍历后序列是否为空。
比较数组元素时，从下标为0的数组元素开始比较，先将下标为i=0的a[i]与下标为1的a[i+1]比较，如果a[i]>a[i+1]，则结束比较，即该二叉树不是二叉排序树，否则继续比较，直至比较完整个数组元素。
3.2程序源代码#include "stdafx.h" //编写的任何.cpp文件都必须首先包含stdafx.h#include<stdio.h>#include<stdlib.h>#define max 10typedef struct node{int data; //数据域node *lchild,*rchild; //左孩子指针，右孩子指针}Bitree; //结点的结构体定义Bitree *B[max];int temp=0;int Btree[max];Bitree *Creatree(){ //建立二叉树Bitree *T,*S;int ch;int front,rear,sign;sign=0; //结点的序号从0开始编号（按照完全二叉树的顺序标记）front=0; //双亲结点下标初值rear=-1; //自身结点下标初值T=NULL; //初始化树Tprintf("建立二叉树(1表示虚结点,0表示输入结束):\n");scanf("%d",&ch); //按完全二叉树的顺序输入结点while(ch!=0){if(ch!=1) //输入结点不是虚结点{S=(Bitree *)malloc(sizeof(Bitree)); //创建新结点SS->data=ch; //将输入的数据保存到S中S->lchild=S->rchild=NULL; //将S的左右子树为空rear++; //结点下标加1B[rear]=S; //将S保存到数组B中，即从下标为0开始存储if(rear==front) //双亲结点下标与本身下标相同时，即无双亲结点（只有第一个结点会产生这种情况）{T=S;sign++; //结点的序号加1}else //寻找双亲结点{if(sign%2==1)B[front]->lchild=S; //S作为左孩子if(sign%2==0){B[front]->rchild=S;//S作为右孩子front++; //下标加1，即寻找下一个双亲结点}sign++;//结点序号加1}}else{ //输入结点为虚结点if(sign%2==0) //为右子树时{front++;} //双亲结点加1 即下一个双亲结点sign++; //结点序号加1}scanf("%d",&ch);}return T;}void Inorder(Bitree *T) //中序遍历二叉树T，并将每个结点数据存入数组中{if(T!=NULL) //如果树不为空{Inorder(T->lchild);printf("%d\t",T->data);Btree[temp]=T->data;temp++;Inorder(T->rchild);}}int Judgesort_bitree(int Btree[]) //判断中序遍历后的二叉树是否是二叉排序树{int i,sign=1;for(i=0;i<temp-1;i++) //用for循环语句看二叉树是否有序递增{if(Btree[i]>Btree[i+1]) //不是有序递增的{sign=0;break;}}return sign;}void Judgeout(int a)//判断输出将sign赋给a{if(a==1)printf("给定二叉树是二叉排序树!\n");if(a==0)printf("给定二叉树不是二叉排序树!\n");}void main(){Bitree *T;T=Creatree(); //建立二叉树printf("中序遍历:\n");Inorder(T); //中序遍历二叉树printf("\n");Judgeout(Judgesort_bitree(Btree)); //判断是否为排序二叉树}4 调试分析实现了设计的所有要求，选取部分运行示意图。
图4-1 给定二叉树是二叉排序树图4-2 给定二叉树不是二叉排序树结果分析：成功的编译了代码，实验结果令人满意。
先说下判断二叉树数否为排序二叉树的时间复杂度。
二叉树以二叉链表存储，在建立二叉树，中序遍历二叉树和判别时的时间复杂度都为O(n)。
再说下编程遇到的问题，编程的关键是要建立一棵二叉树和判别是否为排序二叉树。
其中判断时，用到了递归的思想。
调试时也遇到了一些问题，由于对一些头文件的不熟悉，缺少，导致程序无法运行等小错误通过查阅一些资料得到了解决。
再有就是由于程序涉及到指针，因此有时指针随机访问到系统隐藏空间时会出现异常终端，通过改进，异常出现的几率大大降低，可认为程序能近似完美运行。
最后说下算法的优缺点，优点是：由于使用二叉链表存储，结构简单，可以方便的构造任何形状的二叉树，并可以方便的实现二叉树的大多数操作。
缺点是：查找当前结点的双亲结点操作实现起来比较麻烦。
而且存储效率不高，进一步优化的话，可以逐条归类存储。
算法改进的话，可以调整下操作界面，使人机交流更简单，方便用户操作。
5 课程总结数据结构的课程设计终于结束，真的很开心。
经过一个学期的学习，我觉得课设是对于我们数据结构掌握程度的测验与评估。
这两周的课设，从开始的确定命题，到搜集资料，到初步编程，到修改代码，到最终完成代码，这是一个学习的过程，一个升华的过程。
我想课设的意义也是在于此吧。
这个程序由于使用二叉链表存储，结构简单，可以方便的构造任何形状的二叉树，并可以方便的实现二叉树的大多数操作。
但是他也存在不足，查找当前结点的双亲结点操作实现起来比较麻烦。
而且存储效率不高，进一步优化的话，可以逐条归类存储。
调试时也遇到了一些问题，由于对一些头文件的不熟悉，缺少，导致程序无法运行等小错误通过查阅一些资料得到了解决。
再有就是由于程序涉及到指针，因此有时指针随机访问到系统隐藏空间时会出现异常终端，通过改进，异常出现的几率大大降低，可认为程序能近似完美运行。
虽然刚开始很困难，但是只要你愿意做，就一定能做到。
当然课设也有很多的不足，由于刚学完数据结构没多久，因此没有建立一个系统的知识框架，在编程时大体上还是延续C的思路，并没有过多的采用数据结构在算法和效率上进行优化，这是此次最大的不足，最大的遗憾，也将会是今后学习的重点，我会吸取教训，好好地再巩固自己的理论知识。
当然，我能够成功编译出来也不是自己一个人的功劳，离不开同学，老师的帮助和点播。
在此，我要感谢给于过我帮助的指导老师和热心的同学们，谢谢大家，我会继续努力的。
6参考文献[1]严蔚敏，吴伟民著. 数据结构：C语言版. 清华大学出版社，2007[2]谭浩强著. C++面向对象程序设计. 北京:清华大学出版社，2006。
