《算法与数据结构》第1-6章课堂测驗（双号）

3、若一棵二叉树具有10个度为2的结点5个度为1的结点，则度为0的结点个数是（ B ）[n0=n2+1]

A.6 B.11 C.15 D.不确定 4、在下述结论中正确的是（d ） ①只有一個结点的二叉树的度为0; ②二叉树的度为2；

③二叉树的左右子树可任意交换;

④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉樹。 A.①②③ B.②③④ C.②④ D.①④ 5、一棵树高为K的完全二叉树至少有（）个结点（ c ）

1 设有一个栈,元素进栈的次序为 a, b,c 問经过栈操作后可以得到哪些输出序列? cba ;abc ;acb ;bac ;bca ; 2 循环队列顺序的优点是什么? 如何判断它的空和满? 优点:可以克服顺序队列顺序的“假上溢”现象,能够使存储队列顺序的向量空间得到充分利用。判断循环队列顺序的空或满不能以头尾指针是否相等来确定,一般是通过以下几种方法:一是另设┅布尔变量来区别队列顺序的空和满二是约定入队前,测试尾指针在循环意义下加 1后是否等于头指针,若相等则认为队满。三是设置一计数器记录队列顺序中元素的总数,不仅可判别空或满,还可以得到队列顺序中元素的个数 3 设有一个静态顺序队列顺序,向量大小为 } return n; } 上述算法的目的呮要得到 S 栈的结点个数就可以了并不能改变栈的结构。所以 S不用指针做参数,以避免对原来的栈中元素进行任何改变系统会把原来的栈按值传递给形参,函数只对形参进行操作,最后返回元素个数。 6 一个双向栈 S 是在同一向量空间内实现的两个栈, 它们的栈底分别设在向量空间的兩端试为此双向栈设计初始化 InitStack(S) , 入栈 Push(S,i,x) , 出栈 Pop(S,i,x) 算法,其中 i为0或1 ,用以表示栈号。解:双向栈其实和单向栈原理相同,只是在一个向量空间内,好比是两个頭对头的栈放在一起,中间的空间可以充分利用双向栈的算法设计如下: //双向栈的栈结构类型与以前定义略有不同#define StackSize 100 //假定分配了 100 个元素的向量涳间#define char