1、下图所示的4棵二叉树中，不是完全二叉树的是（ ）
2、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法（ ）。 A 、正确 B 、错误
C 、不一定
3、已知某二叉树的后序遍历序列是dabec ，中序遍历序列是debac ，它的前序遍历序列是（ ）。 A 、acbed B 、decab
C 、deabc
D 、cedba
4、如果T2是由有序树T 转换而来的二叉树，那么T 中结点的后序就是T2中结点的（ ）。 A 、前序 B 、中序
C 、后序
D 、层次序
5、深度为5的二叉树至多有（ ）个结点。 A 、16 B 、32
C 、31
D 、10
6、在一个非空二叉树的中序遍历序列中，根结点的右边（ ）。
A
B
C D
A、只有右子树上的所有结点
B、只有右子树上的部分结点
C、只有左子树上的部分结点
D、只有左子树上的所有结点
7、树最适合用来表示（）。
A、有序数据元素
B、无序数据元素
C、元素之间具有分支层次关系的数据
D、元素之间无联系的数据。
8、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。
A、不发生改变
B、发生改变
C、不能确定
D、以上都不对
9、实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用（）存储结构。
A、二叉链表
B、广义表存储结构
C、三叉链表
D、顺序存储结构
10、对一个满二叉树，m个树叶，n个结点，深度为h，则（）。
A、n=m+h
B、h+m=2n
C、m=h-1
D、n=2h-1
11、设n，m为二叉树上的两个结点，在中序遍历时，n在m前的条件是（）。
A、n在m右方
B、n是m祖先
C、n在m左方
D、n是m子孙12．已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，
其前缀形式为( )
A ．-A+B*C/DE B. -A+B*CD/E C ．-+*ABC/DE D. -+A*BC/DE
13. 设有一表示算术表达式的二叉树（见右图）， 它所表示的算术表达式是（ ）
A. A*B+C/(D*E)+(F-G)
B. (A*B+C)/(D*E)+(F-G)
C. (A*B+C)/(D*E+（F-G ）)
D. A*B+C/D*E+F-G
14. 在下述结论中，正确的是（ ）
①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换; ④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A ．①②③
B ．②③④
C ．②④
D ．①④
15. 设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n,森林F 中第一棵树的结点个数是（ ）
A ．m-n
B ．m-n-1
C ．n+1
D ．条件不足，无法确定
16．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）
A ．9
B ．11
C ．15
D ．不确定
17．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A．250 B．500 C．254 D．505 E．以上答案都不对
18. 一个具有1025个结点的二叉树的高h为（）
A．11 B．10 C．11至1025之间D．10至1024之间
19．深度为h的满m叉树的第k层有（）个结点。(1= 20.利用二叉链表存储树，则根结点的右指针是（）。 A．指向最左孩子B．指向最右孩子C．空D．非空 21．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。 A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历22．若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。 A．前序B．中序C．后序D．按层次 23．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树 一定满足（） A．所有的结点均无左孩子B．所有的结点均无右孩子 C．只有一个叶子结点D．是任意一棵二叉树 24. 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( ) A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右结点 D.X的左子树中最右叶结点 25.线索二叉树是一种（）结构。 A．逻辑B．逻辑和存储C．物理D．线性 26．n个结点的线索二叉树上含有的线索数为（） A．2n B．n－l C．n＋l D．n 27．下面几个符号串编码集合中，不是前缀编码的是（）。 A．{0,10,110,1111} B．{11,10,001,101,0001} C．{00,010,0110,1000} D．{b,c,aa,ac,aba,abb,abc} 28.当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组A[l..n]中时，数组中第i个结点的左孩子为（）A．A[2i](2i= 法确定 29、高度为h的完全二叉树至少有多少个结点?至多有多少个结点? 解：高度为h的完全二叉树至少有2h-1个结点，至多有2h-1个结点(也就是满二叉树)。 30、在什么样的情况下，等长编码是最优的前缀码? 答：在每个字符的使用概率相同的情况下，也即在哈夫曼树中每片叶子的权重相等的时候，等长编码是最优的前缀码。 31.假设在树中，结点x是结点y的双亲时,用(x,y)来表示树边。已知一棵树边的集合为{(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}用图表示出此树，并回答下列问题： (1)哪个是根结点? (2)哪些是叶结点? (3)哪个是g的双亲? (4)哪些是g的祖先? (5)哪些是g的孩子? (6)哪些是e的子孙? (7)哪些是e的兄弟?哪些是f的兄弟? (8)结点b和n的层次各是多少? (9)树的深度是多少? (10)以结点c为根的子树的深度是多少? (11) 树的度数是多少? 答：这是测试我们对树的基本概念的掌握情况。 a是根结点；mndfjkl是叶结点；c是g的双亲；c,a是g的祖先； j,k是g的孩子；imn是e的子孙；d是e的兄弟，g,h是f的兄弟； b的层次是2，n的层次是5；树的深度是5；以c为根的子树深度是3； 树的度数是3。 32、试找出分别满足下面条件的所有二叉树： (1)前序序列和中序序列相同；(2)中序序列和后序序列相同； (3)前序序列和后序序列相同；(4)前序、中序、后序序列均相同。 答： (1) 前序序列和中序序列相同的二叉树是：没有左子树的二叉树(右单支树)。 (2) 中序序列和后序序列相同的二叉树是：没有右子树的二叉树(左单支树)。 (3) 前序序列和后序序列相同的二叉树是：只有根结点的二叉树。 (4) 前序、中序、后序序列均相同的二叉树：只有根结点的二叉树。 33、对二叉树中的结点进行按层次顺序(每一层自左至右)的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树层次序列。现已知一棵二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF，请画出此二叉树。解：A / \ B C / \ \ D E F / \ / G H I \ J 34、对下图所示的森林： (1)求各树的前序序列和后序序列； (2)求森林的前序序列和后序序列； (3)将此森林转换为相应的二叉树； (4)给出(a)所示树的以双亲链表表示、孩子链表表示、双亲孩子链表表示及孩子兄弟链表表示等四种存储结构，并指出哪些存储结构易于求指定结点的祖先，哪些易于求指定结点的后代? 解： (1) (a)的前序序列：ABCDEF 后序序列：BDEFCA (b)的前序序列：GHIJK 后序序列：IJKHG (c)的前序序列：LMPQRNO 后序序列：QRPMNOL (2) 此森林的前序序列：ABCDEFGHIJKLMPQRNO 此森林的后序序列：BDEFCAIJKHGQRPMNOL (3)略 (4)略 35．完全二叉树中，结点个数为n，则编号最大的分支结点的编号为。答：?n/2? 36．二叉树结点的对称序序列为A,B,C,D,E,F,G,后序序列为B,D,C,A,F,G,E,则该二叉树结点的前序序列为(1) ,则该二叉树对应的树林包括(2) 棵树。答：(1)EACBDGF （2）2 37．具有n个结点的满二叉树，其叶结点的个数是______。 答：(n+1)/2 设内部节点数为a，叶节点数为b，明显有a+b=n (1)，非空满二叉树中所有节点的出度正好等于入度，每个内部节点出度为2，叶节点出度为0，所有节点的出度和为2a；根节点入度为0，其他节点的入度为1，所有节点的入度和为a+b-1;因此有2a=a+b-1 (2)。由(1)(2)得b=(n+1)/2，a=(n-1)/2。另外可得b=a+1，也就是说，非空满二叉树的叶节点数正好比内部节点数多1。 38．设一棵后序线索树的高是50，结点x是树中的一个结点，其双亲是结点y,y 的右子树高度是31，x是y的左孩子。则确定x的后继最多需经过______中间结点（不含后继及x本身） 答：31（x的后继是经x的双亲y的右子树中最左下的叶结点） 39．有一份电文中共使用6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试构造一棵哈夫曼树，则其加权路径长度WPL为(1)，字符c的编码是(2)。 答：(1)80 (2)001（不唯一） 40．下面是求二叉树高度的类C写的递归算法，试补充完整。 [说明]二叉树的两指针域为lchild与rchild, 算法中p为二叉树的根，lh和rh 分别为以p为根的二叉树的左子树和右子树的高，hi为以p为根的二叉树的高，hi最后返回。 height(p) {if ((1)) {if(p->lchild==null) lh=(2) ; else lh=(3); if(p->rchild==null) rh=(4); else rh=(5); if (lh>rh) hi=(6)；else hi=(7); } else hi=(8); return hi; }// 答：(1)p (2)0 (3)height(p->lchild) (4)0 (5)height(p->rchild) (6)lh+1 (7)rh+1 (8)0 41．已知一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子结点有多少个？ 答：结点个数在20到40的满二叉树且结点数是素数的数是31，其叶子数是16。 42．用一维数组存放的一棵完全二叉树；ABCDEFGHIJKL。请写出后序遍历该二叉树的访问结点序列。 答：HIDJKEBLFGCA 43．一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为多少？答：左右子树均不空的二叉树先序线索化后，空指针域为1个（最后访问结点的右链为空）。 44．设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码，使得上述正文的编码最短。 45．编程求以孩子—兄弟表示法存储的森林的叶子结点数。要求描述结构。 [题目分析]当森林（树）以孩子兄弟表示法存储时，若结点没有孩子（firstchild=null）,则它必是叶子，总的叶子结点个数是孩子子树（firstchild）上的叶子数和兄弟（nextsibling）子树上叶结点个数之和。 typedef struct node {ElemType data; //数据域 struct node * firstchild, * nextsibling;//孩子与兄弟域}*Tree; int Leaves (Tree t) //计算以孩子-兄弟表示法存储的森林的叶子数 { if(t) if(t->firstchild ==null) //若结点无孩子，则该结点必是叶子 return(1+Leaves(t->nextsibling)); //返回叶子结点和其兄弟子树中的叶子结点数 else return (Leaves(t->firstchild)+Leaves(t->nextsibling)); //孩子子树和兄弟子树中叶子数之和 }//结束Leaves 46．有n个结点的完全二叉树存放在一维数组A[1..n]中，试据此建立一棵用二叉链表表示的二叉树，根由tree指向。 BiTree Creat(ElemType A[],int i) //n个结点的完全二叉树存于一维数组A中，本算法据此建立以二叉链表表示的完全二叉树 { BiTree tree; if (i<=n){ tree=(BiTree)malloc(sizeof(BiNode)); tree->data=A[i]; if(2*i>n) tree->lchild=null；else tree->lchild=Creat(A,2*i)； if(2*i+1>n) tree->rchild=null；else tree->rchild=Creat(A,2*i+1)； } return (tree)； }//Creat [算法讨论]初始调用时,i=1。 47. 以孩子兄弟链表为存储结构，请设计算法求树/森林的深度。 [题目分析]由孩子兄弟链表表示的树，求高度的递归模型是：若树为空，高度为零；若第一子女为空，高度为1和兄弟子树的高度的大者；否则，高度为第一子女树高度加1和兄弟子树高度的大者。其非递归算法使用队列，逐层遍历树，取得树的高度。 int TreeDepth(CSTree T) {if (!T) return 0; else { h1= TreeDepth(T->firstchild); h2= TreeDepth(T->nextsibling); return (max(h1+1,h2)); } }// TreeDepth 48. 设计算法返回二叉树T的先序序列的最后一个结点的指针，要求采用非递归形式，且不许用栈。 [题目分析]二叉树先序序列的最后一个结点，若二叉树有右子树，则是右子树中最右下的叶子结点；若无右子树，仅有左子树，则是左子树最右下的叶子结 点；若二叉树无左右子树，则返回根结点。 BiTree LastNode(BiTree bt) //返回二叉树bt先序序列的最后一个结点的指针 {BiTree p=bt; if(bt==null) return(null); else while(p) if (p->rchild) p=p->rchild; //若右子树不空，沿右子树向下 else if (p->lchild) p=p->lchild; //右子树空，左子树不空，沿左子树向下 else return(p); //左右子树均为空，p即为所求}//lastnode 49.设一棵二叉树的根结点指针为T，C为计数变量，初值为0，试写出对此二叉树中结点计数的算法：BTLC（T，C）。 int BTLC(BiTree T,int *c) //对二叉树T的结点计数 {if(T) {*c++; //调用时*c=0 BTLC(T->lchild,&c); //统计左子树结点 BTLC(T->rchild,&c); //统计右子树结点 } }// 50．设计算法：统计一棵二叉树中所有叶结点的数目及非叶结点的数目。 void Count(BiTree bt,int *n0,*n) //统计二叉树bt上叶子结点数n0和非叶子结点数n {if(bt) {if (bt->lchild==null && bt->rchild==null) *n0++；//叶子结点 else *n++; //非叶结点 Count(bt->lchild,&n0,&n); Count(bt->rchild,&n0,&n); } }//Count 51、编写算法完成下列操作：无重复地输出以孩子兄弟链表存储的树T中的所有的边。输出形式为（k1,k2）……（ki,kj）……，其中ki和kj为树结点中的结点标识。 Void OutEdger(CSTree T) //先根遍历输出树中各条边 { if (T) { p=T->firstchild; while(p) { printf(T->data,p->data); OutEdger(p); p=p->nextsibling; } } }// 52、已知L[i]和R[i]（i=1,2，……，n）分别指示二叉树中第i个结点的左孩子和右孩子结点，0表示空，试写出判别结点u是否是结点v的子孙的算法。status descendent(int L[],int R[],int u,int v) { if (u&&v) { if(L[v]==u||R[v]==u) return TRUE; else if(descendent(L,R,u,L[v])) return TRUE; else return(descendent(L,R,u,R[v])); } el se return FALSE; }// 53.设一棵二叉树以二叉链表为存贮结构，结点结构为(lchild, data,rchild)，设计一个算法将二叉树中所有结点的左，右子树相互交换。 类似本题的另外叙述有： （1）设t为一棵二叉树的根结点地址指针，试设计一个非递归的算法完成把二叉树中每个结点的左右孩子位置交换。 （2）写一个将二叉树中每个结点的左右孩子交换的算法。 void exchange(BiTree bt) //将二叉树bt所有结点的左右子树交换 { if(bt) {BiTree s； s=bt->lchild; bt->lchild=bt->rchild; bt->rchild=s; //左右子女交换 exchange(bt->lchild); //交换左子树上所有结点的左右子树 exchange(bt->rchild); //交换右子树上所有结点的左右子树 } } [算法讨论]将上述算法中两个递归调用语句放在前面，将交换语句放在最后，则是以后序遍历方式交换所有结点的左右子树。中序遍历不适合本题。 下面是本题（1）要求的非递归算法 void exchange(BiTree t) //交换二叉树中各结点的左右孩子的非递归算法{int top=0; BiTree s[],p; //s是二叉树的结点指针的栈，容量足够大if(bt) {s[++top]=t; while(top>0) {t=s[top--]; if(t->lchild||t->rchild){p=t->lchild;t->lchild=t->rchild;t->rch ild=p;}//交换左右 if(t->lchild) s[++top]=t->lchild; //左子女入栈 if(t->rchild) s[++top]=t->rchild; //右子女入栈 }//while(top>0) }//if(bt) }//exchange 54．要求二叉树按二叉链表形式存储， （1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。 完全二叉树定义为：深度为K，具有N个结点的二叉树的每个结点都与深度为K的满二叉树中编号从1至N的结点一一对应。此题以此定义为准。[题目分析]二叉树是递归定义的，以递归方式建立最简单。判定是否是完全二叉树，可以使用队列，在遍历中利用完全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。 BiTree Creat() //建立二叉树的二叉链表形式的存储结构 {ElemType x；BiTree bt; scanf(“%d”,&x); //本题假定结点数据域为整型 if(x==0) bt=null; else if(x>0) {bt=(BiNode *)malloc(sizeof(BiNode)); bt->data=x; bt->lchild=creat(); bt->rchild=creat(); } else error(“输入错误”)； return(bt); }// Creat int JudgeComplete(BiTree bt) //判断二叉树是否是完全二叉树,如是，返回1，否则，返回0 { int tag=0; BiTree p=bt, Q[]; // Q是队列，元素是二叉树结点指针，容量足够大 if(p==null) return (1); QueueInit(Q); QueueIn(Q,p); //初始化队列，根结点指针入队 while (!QueueEmpty(Q)) {p=QueueOut(Q); //出队 if (p->lchild && !tag) QueueIn(Q,p->lchild); //左子女入队 else {if (p->lchild) return 0; //前边已有结点为空，本结点不空 else tag=1; //首次出现结点为空 if (p->rchild && !tag) QueueIn(Q,p->rchild); //右子女入队 else if (p->rchild) return 0; else tag=1; } //while return 1; } //JudgeComplete [算法讨论]完全二叉树证明还有其它方法。判断时易犯的错误是证明其左子树和右子数都是完全二叉树，由此推出整棵二叉树必是完全二叉树的错误结论。 数据结构1800例题与答案 第一章绪论 一、选择题（每小题2分） 1．算法的计算量的大小称为计算的（ B ）。【北京邮电大学2000 二、3 （20/8分）】 A．效率B．复杂性C．现实性D．难度 2．算法的时间复杂度取决于（C）。【中科院计算所1998 二、1 （2分）】 A．问题的规模B．待处理数据的初态C．A和B D．都不是 3．计算机算法指的是（①C ），它必须具备（② B ）这三个特性。 ①A．计算方法B．排序方法 C．解决问题的步骤序列D．调度方法 ②A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性 C．确定性、有穷性、稳定性D．易读性、稳定性、安全性【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（B ）。【中山大学1998 二、1（2分）】 A．程序B．问题求解步骤的描述 C．要满足五个基本特性D．A和C. 5．下面关于算法说法错误的是（ D ）【南京理工大学2000 一、1（1.5分）】A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（C ）【南京理工大学2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（ C ）两大类。【武汉交通科技大学1996 一、4（2分）】 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（ D ）。【北方交通大学2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（ D ）？【北方交通大学2001 一、1（2分）】 A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（Ａ）【北方交通大学2001 一、2（2分）】 A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（Ｃ）【北京工商大学2001 一、10（3分）】 FOR i:=1 TO n DO 《数据结构》必须掌握的知识点与算法 第一章绪论 1、算法的五个重要特性（有穷性、确定性、可行性、输入、输出） 2、算法设计的要求（正确性、可读性、健壮性、效率与低存储量需求） 3、算法与程序的关系： （1）一个程序不一定满足有穷性。例操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。 （2）程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。 （3）一个算法若用程序设计语言来描述，则它就是一个程序。 4、算法的时间复杂度的表示与计算（这个比较复杂，具体看算法本身，一般关心其循环的次数与N的关系、函数递归的计算） 第二章线性表 1、线性表的特点： （1）存在唯一的第一个元素；（这一点决定了图不是线性表） （2）存在唯一的最后一个元素； （3）除第一个元素外，其它均只有一个前驱（这一点决定了树不是线性表） （4）除最后一个元素外，其它均只有一个后继。 2、线性表有两种表示：顺序表示（数组）、链式表示（链表），栈、队列都是线性表，他们都可以用数组、链表来实现。 3、顺序表示的线性表（数组）地址计算方法： （1）一维数组，设DataType a[N]的首地址为A0，每一个数据（DataType类型）占m个字节，则a[k]的地址为：A a[k]＝A0+m*k（其直接意义就是求在数据a[k]的前面有多少个元素，每个元素占m个字节） （2）多维数组，以三维数组为例，设DataType a[M][N][P]的首地址为A000，每一个数据（DataType 类型）占m个字节，则在元素a[i][j][k]的前面共有元素个数为：M*N*i+N*j+k，其其地址为： A a[i][j][k]＝A000+m*(M*N*i+N*j+k)； 4、线性表的归并排序： 设两个线性表均已经按非递减顺序排好序，现要将两者合并为一个线性表，并仍然接非递减顺序。可见算法2.2 5、掌握线性表的顺序表示法定义代码，各元素的含义； 6、顺序线性表的初始化过程，可见算法2.3 7、顺序线性表的元素的查找。 8、顺序线性表的元素的插入算法，注意其对于当原来的存储空间满了后，追加存储空间（就是每次增加若干个空间，一般为10个）的处理过程，可见算法2.4 9、顺序线性表的删除元素过程，可见算法2.5 10、顺序线性表的归并算法，可见算法2.7 11、链表的定义代码，各元素的含义，并能用图形象地表示出来，以利分析； 12、链表中元素的查找 13、链表的元素插入，算法与图解，可见算法2.9 14、链表的元素的删除，算法与图解，可见算法2.10 15、链表的创建过程，算法与图解，注意，链表有两种（向表头生长、向表尾生长，分别用在栈、队列中），但他们的区别就是在创建时就产生了，可见算法2.11 16、链表的归并算法，可见算法2.12 17、建议了解所谓的静态单链表（即用数组的形式来实现链表的操作），可见算法2.13 18、循环链表的定义，意义 19、循环链表的构造算法（其与单链表的区别是在创建时确定的）、图解 第3章栈和队列 一选择题 1. 对于栈操作数据的原则是（）。【青岛大学 2001 五、2（2分）】 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 2. 在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否( ② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。 为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产生上溢。①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶 D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点. B. 其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 【上海海运学院 1997 二、1（5分）】【上海海运学院 1999 二、1（5分）】 3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。 A. 不确定 B. n-i+1 C. i D. n-i 【中山大学 1999 一、9(1分)】 4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 【武汉大学 2000 二、3】 5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，p N,若p N是n，则p i是( )。 A. i B. n-i C. n-i+1 D. 不确定 【南京理工大学 2001 一、1（1.5分）】 6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 【北方交通大学 2001 一、3（2分）】 7. 设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。【中科院计算所2000一、10(2分)】 A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， E. 3，2，1，4， 8. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 【南开大学 2000 一、1】【山东大学 2001 二、4 (1分)】【北京理工大学 2000 一、2（2分）】 9. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（）。 A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4 【合肥工业大学 2001 一、1（2分）】 10. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是 数据结构知识点概括 第一章概论 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。 数据结构的定义： ·逻辑结构：从逻辑结构上描述数据，独立于计算机。·线性结构：一对一关系。 ·线性结构：多对多关系。 ·存储结构：是逻辑结构用计算机语言的实现。·顺序存储结构：如数组。 ·链式存储结构：如链表。 ·索引存储结构：·稠密索引：每个结点都有索引项。 ·稀疏索引：每组结点都有索引项。 ·散列存储结构：如散列表。 ·数据运算。 ·对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。 ·常用的有：检索、插入、删除、更新、排序。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 ·结构类型：由用户借助于描述机制定义，是导出类型。 抽象数据类型ADT：·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。 ·优点是将数据和操作封装在一起实现了信息隐藏。 程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于数据结构。 算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。 评价算法的好坏的因素：·算法是正确的； ·执行算法的时间； ·执行算法的存储空间（主要是辅助存储空间）； ·算法易于理解、编码、调试。 时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。 渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。 时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O （n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。 第6章树和二叉树 部分答案解释如下。 12. 由二叉树结点的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1，因为n=1001,所以1002=2n0+n1,在完全二叉树树中，n1只能取0或1,在本题中只能取0，故n=501，因此选E。 42.前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，所以本题的A和B均对，单支树的特点是只有一个叶子结点，故C是最合适的，选C。A或B 都不全。由本题可解答44题。 47. 左子树为空的二叉树的根结点的左线索为空（无前驱），先序序列的最后结点的右线索为空（无后继），共2个空链域。 52．线索二叉树是利用二叉树的空链域加上线索，n个结点的二叉树有n+1个空链域。 部分答案解释如下。 6．只有在确定何序（前序、中序、后序或层次）遍历后，遍历结果才唯一。 19．任何结点至多只有左子树的二叉树的遍历就不需要栈。 24. 只对完全二叉树适用，编号为i的结点的左儿子的编号为2i(2i<=n)，右儿子是2i+1（2i+1<=n） 37. 其中序前驱是其左子树上按中序遍历的最右边的结点（叶子或无右子女），该结点无右孩子。 38 . 新插入的结点都是叶子结点。 42. 在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结点（该结点的后继指针指向祖先），中序后继是其右子树上按中序遍历的最左边的结点（该结点的前驱指针指向祖先）。 44．非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。 三.填空题 1.(1)根结点(2)左子树(3)右子树 2.(1)双亲链表表示法(2)孩子链表表示法(3)孩 子兄弟表示法 3．p->lchild==null && p->rchlid==null 4.(1) ++a*b3*4-cd (2)18 5.平衡 因子 6. 9 7. 12 8.(1)2k-1 (2)2k-1 9.(1)2H-1 (2)2H-1 (3)H=?log2N?+1 10. 用顺序存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结 点”。设编号为i和j的结点在顺序存储中的下标为s 和t ,则结点i和j在同一层上的条 件是?log2s?=?log2t?。 11. ?log2i?=?log2j?12.(1)0 (2)(n-1)/2 (3)(n+1)/2 (4) ?log2n?+1 13.n 14. N2+1 15.(1) 2K+1-1 (2) k+1 16. ?N/2? 17. 2k-2 18. 64 19. 99 20. 11 21.(1) n1-1 (2)n2+n3 22.(1)2k-2+1（第k层1个结点，总结点个数是2H-1，其双亲是2H-1/2=2k-2）(2) ?log2i?+1 23.69 24. 4 25.3h-1 26. ?n/2? 27. ?log2k?+1 28.(1)完全二叉树 (2)单枝树，树中任一结点（除最后一个结点是叶子外）,只有左子女或 只有右子女。 29.N+1 30.(1) 128(第七层满，加第八层１个) (2) 7 31. 0至多个。任意二叉树，度为１的结点个数没限制。只有完全二叉树，度为１的结点个 数才至多为1。 32．21 33.(1)2 (2) n-1 (3) 1 (4) n (5) 1 (6) n-1 34.(1) FEGHDCB (2)BEF（该二叉树转换成森林，含三棵树，其第一棵树的先根次序是 BEF） 35.(1)先序（2）中序 36. (1)EACBDGF （2）2 37.任何结点至多只有右子女 的二叉树。 38.(1)a (2) dbe (3) hfcg 39.(1) . (2) ...GD.B...HE..FCA 40.DGEBFCA 41．(1)5 （2）略 42.二叉排序树 43.二叉树 44. 前序 45.(1)先根次序（2）中根次序46.双亲的右子树中最左下的叶子结点47.2 48.(n+1)/2 49.31（x的后继是经x的双亲y的右子树中最左下的叶结点） 50.(1)前驱 (2)后 继 51.(1)1 (2)y^.lchild (3)0 (4)x (5)1 (6) y (7)x(编者注：本题按 中序线索化) 52.带权路径长度最小的二叉树，又称最优二叉树 53.69 54.(1)6 (2)261 55.(1)80 (2)001（不唯一）56.2n0-1 57.本题①是表达式求值，②是在二叉排序树中删除值为x的结点。首先查找x，若没有x， 则结束。否则分成四种情况讨论：x结点有左右子树；只有左子树；只有右子树和本身是叶 子。 (1)Postoder_eval(t^.Lchild) (2) Postorder_eval(t^.Rchild) (3)ERROR(无此运 算符)(4)A (5)tempA^.Lchild (6)tempA=NULL(7)q^.Rchild (8)q (9)tempA^.Rchild (10)tempA^.Item 第一章数据结构概述 基本概念与术语 1．数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。 2. 数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。 (补充：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 ) 3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。(有时候也 叫做属性。) 4．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 (1)数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。 数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。 依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种： 1. 集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。 2. 线性结构：结构中的数据元素之间存在“一对一“的关系。若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。 3. 树形结构：结构中的数据元素之间存在“一对多“的关系。若数据为非空集，则除了第一个元素 (根)之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。 4. 图状结构：结构中的数据元素存在“多对多”的关系。若结构为非空集，折每个数据可有多个(或零个)直接后继。 (2)数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为以下两种存储结构： 1. 顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。 2. 链式存储结构：借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物理位置上也相邻。 5. 时间复杂度分析：1.常量阶：算法的时间复杂度与问题规模n 无关系T(n)=O(1) 2. 线性阶：算法的时间复杂度与问题规模 n 成线性关系T(n)=O(n) 3. 平方阶和立方阶：一般为循环的嵌套，循环体最后条件为i++ 时间复杂度的大小比较： O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n ) 第 5 章数组和广义表 一、选择题 1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其 存储地址为1，每个元素占一个地址空间，则a85的地址为（）。【燕山大学 2001 一、2 （2分）】 A. 13 B. 33 C. 18 D. 40 2. 有一个二维数组A[1:6，0:7] 每个数组元素用相邻的6个字节存储，存储器按字节编址， 那么这个数组的体积是（①）个字节。假设存储数组元素A[1，0]的第一个字节的地址是0， 则存储数组A的最后一个元素的第一个字节的地址是（②）。若按行存储，则A[2，4]的第 一个字节的地址是（③）。若按列存储，则A[5，7]的第一个字节的地址是（④）。就一般情 况而言，当（⑤）时，按行存储的A[I，J]地址与按列存储的A[J，I]地址相等。供选择的 答案：【上海海运学院 1998 二、2 （5分）】 ①-④： A．12 B. 66 C. 72 D. 96 E. 114 F. 120 G. 156 H. 234 I. 276 J. 282 K. 283 L. 288 ⑤： A．行与列的上界相同 B. 行与列的下界相同 C. 行与列的上、下界都相同 D. 行的元素个数与列的元素个数相同 3. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10， 数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( )。 A. BA+141 B. BA+180 C. BA+222 D. BA+225 【南京理工大学 1997 一、8 （2分）】 4. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存 储单元，基地址为10，则LOC[5，5]=（）。【福州大学 1998 一、10 (2分)】 A. 808 B. 818 C. 1010 D. 1020 5. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000 的内存单元中，则元素A[5，5]的地址是( )。【南京理工大学 2001 一、13 （1.5分）】 A. 1175 B. 1180 C. 1205 D. 1210 6. 有一个二维数组A[0:8,1:5],每个数组元素用相邻的4个字节存储，存储器按字节编址， 假设存储数组元素A[0,1]的第一个字节的地址是0，存储数组A的最后一个元素的第一个字 节的地址是（①）。若按行存储，则A[3,5]和 A[5,3]的第一个字节的地址是（②） 和（③）。若按列存储，则A[7,1]和A[2,4]的第一个字节的地址是（④）和（⑤）。【上海海运学院 1996 二、1 （5分）】 ①-⑤:A.28 B.44 C.76 D.92 E.108 F.116 G.132 H.176 I.184 J.188 7. 将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元 素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（）。供选择的答案： A. 198 B. 195 C. 197 【北京邮电大学 1998 二、5 （2分）】 8. 二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈 从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中（）内的正确答案。（1）存放A至少需要（）个字节； （2）A的第8列和第5行共占（）个字节； （3）若A按行存放，元素A[8，5]的起始地址与A按列存放时的元素（）的起始地 复习提纲 第一章数据结构概述 基本概念与术语（P3） 1．数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科. 2．数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合 2．数据元素是数据的基本单位 3．数据对象相同性质的数据元素的集合 4．数据结构包括三方面内容:数据的逻辑结构.数据的存储结构.数据的操作. （1）数据的逻辑结构指数据元素之间固有的逻辑关系. （2）数据的存储结构指数据元素及其关系在计算机内的表示 ( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等. 5.时间复杂度分析 -------------------------------------------------------------------------------------------------------------------- 1、名词解释：数据结构、二元组 2、根据数据元素之间关系的不同，数据的逻辑结构可以分为 集合、线性结构、树形结构和图状结构四种类型。 3、常见的数据存储结构一般有四种类型，它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。 4、以下程序段的时间复杂度为___O(N2)_____。 int i,j,x; for(i=0;i 自考02331数据构造重点总结(最后修订) 第一章概论 1.瑞士计算机科学家沃思提出：算法+数据构造=程序。算法是对数据运算描述，而数据构造涉及逻辑构造和存储构造。由此可见，程序设计实质是针对实际问题选取一种好数据构造和设计一种好算法，而好算法在很大限度上取决于描述实际问题数据构造。 2.数据是信息载体。数据元素是数据基本单位。一种数据元素可以由若干个数据项构成，数据项是具备独立含义最小标记单位。数据对象是具备相似性质数据元素集合。 3.数据构造指是数据元素之间互有关系，即数据组织形式。 数据构造普通涉及如下三方面内容：数据逻辑构造、数据存储构造、数据运算 ①数据逻辑构造是从逻辑关系上描述数据，与数据元素存储构造无关，是独立于计算机。 数据逻辑构造分类：线性构造和非线性构造。 线性表是一种典型线性构造。栈、队列、串等都是线性构造。数组、广义表、树和图等数据构造都是非线性构造。 ②数据元素及其关系在计算机内存储方式，称为数据存储构造（物理构造）。 数据存储构造是逻辑构造用计算机语言实现，它依赖于计算机语言。 ③数据运算。最惯用检索、插入、删除、更新、排序等。 4.数据四种基本存储办法：顺序存储、链接存储、索引存储、散列存储 （1）顺序存储：普通借助程序设计语言数组描述。 （2）链接存储：普通借助于程序语言指针来描述。 （3）索引存储：索引表由若干索引项构成。核心字是能唯一标记一种元素一种或各种数据项组合。 （4）散列存储：该办法基本思想是：依照元素核心字直接计算出该元素存储地址。 5.算法必要满足5个准则：输入，0个或各种数据作为输入；输出，产生一种或各种输出；有穷性，算法执行有限步后结束；拟定性，每一条指令含义都明确；可行性，算法是可行。 算法与程序区别：程序必要依赖于计算机程序语言，而一种算法可用自然语言、计算机程序语言、数学语言或商定符号语言来描述。当前惯用描述算法语言有两类：类Pascal和类C。 6.评价算法优劣：算法"对的性"是一方面要考虑。此外，重要考虑如下三点： ①执行算法所耗费时间，即时间复杂性； ②执行算法所耗费存储空间，重要是辅助空间，即空间复杂性； ③算法应易于理解、易于编程，易于调试等，即可读性和可操作性。 第一章概论 1.数据结构描述的是按照一定逻辑关系组织起来的待处理数据元素的表示及相关操作，涉及数据的逻辑结构、存储结构和运算 2.数据的逻辑结构是从具体问题抽象出来的数学模型，反映了事物的组成结构及事物之间的逻辑关系 可以用一组数据（结点集合K）以及这些数据之间的一组二元关系（关系集合R）来表示：(K, R) 结点集K是由有限个结点组成的集合，每一个结点代表一个数据或一组有明确结构的数据 关系集R是定义在集合K上的一组关系，其中每个关系r（r∈R）都是K×K上的二元关系 3.数据类型 a.基本数据类型 整数类型(integer)、实数类型(real)、布尔类型(boolean)、字符类型（char）、指针类型（pointer）b.复合数据类型 复合类型是由基本数据类型组合而成的数据类型；复合数据类型本身，又可参与定义结构更为复杂的结点类型 4.数据结构的分类：线性结构（一对一）、树型结构（一对多）、图结构（多对多） 5.四种基本存储映射方法：顺序、链接、索引、散列 6.算法的特性：通用性、有效性、确定性、有穷性 7.算法分析：目的是从解决同一个问题的不同算法中选择比较适合的一种，或者对原始算法进行改造、加工、使其优化 8.渐进算法分析 a．大Ο分析法：上限，表明最坏情况 b．Ω分析法：下限，表明最好情况 c．Θ分析法：当上限和下限相同时，表明平均情况 第二章线性表 1.线性结构的基本特征 a.集合中必存在唯一的一个“第一元素” b.集合中必存在唯一的一个“最后元素” c.除最后元素之外，均有唯一的后继 d.除第一元素之外，均有唯一的前驱 2.线性结构的基本特点:均匀性、有序性 3.顺序表 a.主要特性：元素的类型相同；元素顺序地存储在连续存储空间中，每一个元素唯一的索引值；使用常数作为向量长度 b. 线性表中任意元素的存储位置：Loc(ki) = Loc(k0) + i * L（设每个元素需占用L个存储单元） c. 线性表的优缺点： 优点：逻辑结构与存储结构一致；属于随机存取方式，即查找每个元素所花时间基本一样 缺点：空间难以扩充 d.检索：ASL=【Ο（1）】 e.插入：插入前检查是否满了，插入时插入处后的表需要复制【Ο（n）】 f.删除：删除前检查是否是空的，删除时直接覆盖就行了【Ο（n）】 4.链表 4.1单链表 a.特点：逻辑顺序与物理顺序有可能不一致；属于顺序存取的存储结构，即存取每个数据元素所花费的时间不相等 b.带头结点的怎么判定空表：head和tail指向单链表的头结点 c.链表的插入（q->next=p->next; p->next=q;）【Ο（n）】 d.链表的删除（q=p->next; p->next = q->next; delete q;）【Ο（n）】 e.不足：next仅指向后继，不能有效找到前驱 4.2双链表 a.增加前驱指针，弥补单链表的不足 b.带头结点的怎么判定空表:head和tail指向单链表的头结点 c.插入：（q->next = p->next; q->prev = p; p->next = q; q->next->prev = q;） d.删除：（p->prev->next = p->next; p->next->prev = p->prev; p->prev = p->next = NULL; delete p;） 4.3顺序表和链表的比较 4.3.1主要优点 a.顺序表的主要优点 没用使用指针，不用花费附加开销；线性表元素的读访问非常简洁便利 b.链表的主要优点 无需事先了解线性表的长度；允许线性表的长度有很大变化；能够适应经常插入删除内部元素的情况 4.3.2应用场合的选择 a.不宜使用顺序表的场合 经常插入删除时，不宜使用顺序表；线性表的最大长度也是一个重要因素 b.不宜使用链表的场合 当不经常插入删除时，不应选择链表；当指针的存储开销与整个结点内容所占空间相比其比例较大时，应该慎重选择 第三章栈与队列 1.栈 a.栈是一种限定仅在一端进行插入和删除操作的线性表；其特点后进先出；插入：入栈（压栈）；删除：出栈（退栈）；插入、删除一端被称为栈顶（浮动），另一端称为栈底（固定）；实现分为顺序栈和链式栈两种 b.应用： 1）数制转换 while (N) { N%8入栈； N=N/8;} while (栈非空){ 出栈； 输出；} 2）括号匹配检验 不匹配情况：各类括号数量不同；嵌套关系不正确 算法： 逐一处理表达式中的每个字符ch： ch=非括号：不做任何处理 ch=左括号：入栈 ch=右括号：if (栈空) return false else { 出栈，检查匹配情况， if (不匹配) return false } 如果结束后，栈非空，返回false 3）表达式求值 3.1中缀表达式： 计算规则：先括号内，再括号外；同层按照优先级，即先乘*、除/,后加+、减-；相同优先级依据结合律，左结合律即为先左后右 3.2后缀表达式： <表达式> ::= <项><项> + | <项><项>－|<项> <项> ::= <因子><因子> * |<因子><因子>/|<因子> <因子> ::= <常数> ?<常数> ::= <数字>|<数字><常数> <数字> ∷= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 3.3中缀表达式转换为后缀表达式 InfixExp为中缀表达式，PostfixExp为后缀表 达式 初始化操作数栈OP，运算符栈OPND； OPND.push('#'); 读取InfixExp表达式的一项 操作数：直接输出到PostfixExp中； 操作符： 当‘（’：入OPND; 当‘）’：OPND此时若空，则出错；OPND若 非空，栈中元素依次弹出，输入PostfixExpz 中，直到遇到‘（’为止；若为‘（’，弹出即 可 当‘四则运算符’：循环（当栈非空且栈顶不是 ‘（’&& 当前运算符优先级>栈顶运算符优先 级），反复弹出栈顶运算符并输入到 PostfixExp中，再将当前运算符压入栈 3.4后缀表达式求值 初始化操作数栈OP； while （表达式没有处理完) { item = 读取表达式一项; 操作数：入栈OP； 运算符：退出两个操作数， 计算，并将结果入栈} c.递归使用的场合：定义是递归的；数据结构是 递归的；解决问题的方法是递归的 2.队列 a.若线性表的插入操作在一端进行，删除操作 在另一端进行，则称此线性表为队列 b.循环队列判断队满对空： 队空：front==rear；队满： (rear+1)%n==front 第五章二叉树 1.概念 a. 一个结点的子树的个数称为度数 b.二叉树的高度定义为二叉树中层数最大的叶 结点的层数加1 c.二叉树的深度定义为二叉树中层数最大的叶 结点的层数 d.如果一棵二叉树的任何结点，或者是树叶， 或者恰有两棵非空子树，则此二叉树称作满二 叉树 e.如果一颗二叉树最多只有最下面的两层结点 度数可以小于2；最下面一层的结点都集中在 该层最左边的位置上，则称此二叉树为完全二 叉树 f.当二叉树里出现空的子树时，就增加新的、特 殊的结点——空树叶组成扩充二叉树，扩充二 叉树是满二叉树 外部路径长度E：从扩充的二叉树的根到每个 外部结点（新增的空树叶）的路径长度之和 内部路径长度I：扩充的二叉树中从根到每个内 部结点（原来二叉树结点）的路径长度之和 2.性质 a. 二叉树的第i层（根为第0层，i≥0）最多有 2^i个结点 b. 深度为k的二叉树至多有2k+1-1个结点 c. 任何一颗二叉树，度为0的结点比度为2的 结点多一个。n0 = n2 + 1 d. 满二叉树定理：非空满二叉树树叶数等于其 分支结点数加1 e. 满二叉树定理推论：一个非空二叉树的空子 树(指针)数目等于其结点数加1 f. 有n个结点（n>0）的完全二叉树的高度为 ?log2(n+1)?，深度为?log2(n+1)?? g. 对于具有n个结点的完全二叉树，结点按层 次由左到右编号，则有： 1) 如果i = 0为根结点；如果i>0，其父结点 编号是(i-1)/2 2) 当2i+1最新版数据结构1800题含完整答案详解
考研数据结构必须掌握的知识点与算法-打印版
目前最完整的数据结构1800题包括完整答案-第三章-栈和队列范文(汇编)
(完整版)非常实用的数据结构知识点总结
目前最完整的数据结构1800题包括完整答案树和二叉树答案
数据结构复习要点(整理版).docx
目前最完整的数据结构1800题包括完整答案 第五章 数组和广义表
数据结构复习提纲(整理)
2021年自考02331数据结构重点总结最终修订
大学数据结构期末知识点重点总结
相关主题
文本预览