济南铁道职业技术学院 专升本辅导教材 数据结构

A．〞cdefgh〞 C．〞cdefxy〞 B．〞cdxyzw〞 D．〞cdefef〞

B．数组的元素必须从左到右顺序排列 D．数组是多维结构，内存是一维结构

2．多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为（ ）

A．数组的元素处在行和列两个关系中 C．数组的元素之间存在次序关系 A．tail (head (LS)) C．head (tail (LS)) A．创建和删除

3．从广义表LS＝（(p, q), r, s）中分解出原子q的运算是（ ）

B．head (tail (head (LS))) D．tail (tail (head (LS))) B．索引和修改

4．数组通常具有两种基本运算，即（ ）

C．读和写 D．排序和查找 5．设有一5阶上三角矩阵A［1..5，1..5］，现将其上三角中的元素按列优先顺序存放在一堆数组B［1..15］中。已知B［1］的地址为100，每个元素占用2个存储单元，则A［3，4］的地址为（ ）

A．116 B．118 C．120 D．122

6.为查找某一特定单词在文本中出现的位置，可应用的串运算是( ) A.插入 B.删除 C.串联接 D.子串定位

7.已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到( ) A.P=″SCIENCE″ B.P=″STUDY″ C.S=″SCIENCE″ D.S=″STUDY″

8.三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A［３］[4][5]的存储地址为( ) A.356 B.358 C.360 D.362 9.串S=″I am a worker″的长度是________。

第五章 树 二叉树 补充内容

后序遍历的非递归算法。

在对二叉树进行后序遍历的过程中，当指针p指向某一个结点时，不能马上对它进行 访问，而要先遍历它的左子树，因而要将此结点的地址进栈保存。当其左子树遍历完毕之 后，再次搜索到该结点时(该结点的地址通过退栈得到)，还不能对它进行访问，还需要遍 历它的右子树，所以，再一次将此结点的地址进栈保存。为了区别同一结点的两次进栈， 引入一个标志变量nae，有 0 表示该结点暂不访问 1 表示该结点可以访问

标志flag的值随同进栈结点的地址一起进栈和出栈。因此，算法中设置两个空间足够的堆栈，其中，STACKlCM]存放进栈结点的地址，STACK2[M]存放相应的标志n昭的值，两个堆栈使用同一栈顶指针top，top的初值为—1。 具体算法如下：

#defineH 100 ／●定义二叉树中结点最大数目。／ voidPOSTOiRDER(BTREET) {

／*T为二叉树根结点所在链结点的地址。／

第 31 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

BTREESTACKl[H]，p=T； intSTACK2[M]，flag,top=—1； if(T!=NULL) d0{

while(p!=NULL){

STACK／[++top]=p； ／●当前p所指结点的地址进栈●／ STACK2[top]= 0； ／，标志0进栈●／

p=p->lchild； ／●将p移到其左孩子结点x／ }

p=STACKl[top)； flag=STACK2[top--]； if(flag==0){

STACKl[++top]=p； ／，当前p所指结点的地址进栈。／ STACK2[toP]=1； ／●标志1进栈●／

p=p->rchild； ／x将p移到其右孩子结点o／ } else{

VISIT(p)； ／x访问当前p所指的结点x／ p=NULL； }

}while(p!=NULLtttop!=-1)； }

不难分析，上述算法的时间复杂度同样为O(n) 5．6．3 二叉树的线索化算法

对--X树的线索化，就是把二叉树的二叉链表存储结构中结点的所有空指针域改造成指向某结点在某种遍历序列中的直接前驱或直接后继的过程，因此，二叉树的线索化过程只能在对二叉树的遍历过程中进行。 ·

下面给出二叉树的中序线索化的递归算法。算法中设有指针pre，用来指向中序遍历过程中当前访问的结点的直接前驱结点，pre的初值为头结点的指针；T初始时指向头结点，但在算法执行过程中，T总是指向当前访问的结点。 voldINTHREAD(TBTREET) { TBTREE pre； if(T!=Null){

INTHREAD(T—>lchild)； if(T—>rchild==NULL) T—>rbit=0；

if(T—>lchild==NUll)； T—>lchild=pre； T—>lbit=0； }

if(pre—>rbitc==0) pre—>rchild=T； pre=T；

inthread(T->rchild)； } }

第 32 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

平均查找长度(AverageSearchLength)：确定一个元素在树中的位置所需要进行的比较次数的期望值。 二叉树的内路径长度(InternalPathLength)：从二叉树根结点到某结点所经过的分支数目定义为该结点的路径长度。

二叉树中所有结点的路径长度之和定义为该二叉树的内路径长度IPL。图7。25(h)给出的二叉排序树的内路径长度为

IPL：1X2+2X2+3X1+4X2=17

二叉树的外路径长度(ExternalPathLength)：为了分析查找失败时的查找长度，在二叉树中出现空子树时，增加新的空叶结点来代表这些空子树，从而得到一棵扩充后的二叉树。为了与扩充前的二叉树相区别，这些新增添的空的叶结点用小方块代表，称之为外部结点，树中原有的结点为内部结点。

下图给出了一棵扩充后的二叉树，其外路径长度EPL是二叉树中所有外部结点的路径长度之和，即

EPL=2X2+3X1+4X4+5X3十6X2=50

习 题

5.1 判断题(在你认为正确的题后的括号中打√，否则打X)。

(1)在树型结构中，每一个结点最多只有一个前驱结点，但可以有多个后继结点。 ( ) (2)在树型结构中，每—个结点不能没有前驱结点。 ( ) (3)在度为k的树中，至少有一个度为k的结点。 ( )

(4)在度为k的树中，每个结点最多有k—1个兄弟结点。 ( ) (5)度为2的树是二叉树。 ( ) (6)二叉树的度一定为2。 ( )

(7)在非空完全二叉树中，只有最下面一层的结点为叶结点。 ( ) (8)在完全-y．树中，没有左孩子的结点一定是叶结点。 ( ) (9)在完全二叉树中，没有右孩子的结点一定是叶结点。 ( )

(10)在结点数目一定的前提下，各种形态的二叉树中，完全二叉树具有最小深度。 ( ) (11)满二叉树一定是完全二叉树。 ( )

(12)满二叉树中的每个结点的度不是0就是2。 ( )

(13)在所有深度相同的二叉树中，满二叉树具有最大结点数目。 ( ) (14)具有n个结点的非空二叉树一定有n—1个分支。 ( )

(15)n个结点的二叉树采用二叉链表结构，链表中有n—1个存放NULL的指针域。 ( ) (16)“退化二叉树”不宜采用顺序存储结构的主要原因是空间浪费较大。 ( ) (17)由二叉树的前序序列和中序序列可以惟一地确定一棵二叉树。 ( ) (18)由二叉树的中序序列和后序序列可以惟一地确定一棵二叉树。 ( )

第 33 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

(19)由二叉树的前序序列和后序序列可以惟一地确定一棵二叉树。 ( ) (20)实现二叉树的按层次遍历算法时需要用到队列结构。 ( ) (21)实现二叉树的遍历算法时不需要用到堆栈结构。 ( ) (22)线索二叉树对应的二叉链表中不存在空的指针域。 ( ) (23)二叉排序树中的任何一棵子树也是二叉排序树。 ( ) (24)一个序列对应的二叉排序树是惟一的。 ( )

(25)按照“逐点插入法”建立的二叉排序树的深度与结点的插入顺序无关。 ( ) (26)在二叉排序树中进行查找的效率与二叉排序树的深度有关。 ( )

(27)在二叉排序树中查找一个结点，查找长度不会超过二叉树的深度。 ( ) (28)给定一组权值，构造出来的哈夫曼树是惟一的。 ( ) (29)哈夫曼树中不存在度为1的结点。 ( )

(30)在哈夫曼树中，权值相同的叶结点都在同一层上。 ( ) 5．2单项选择题。

(1)树型结构最适合用来描述——。

A．有序的数据元素 B．无序的数据元素

C．数据元素之间具有层次关系的数据 D．数据元素之间没有关系的数据 (2)对于一棵具有n个结点、度为4的树而言，——。 A．树的深度最多是n-4 B．树的深度最多是n-3

C．第i层上最多有4x(i-1)个结点 D．最少在某一层上正好有4个结点 (3)“二叉树为空”意味着二叉树————。

A．由一些未赋值的空结点组成 B．根结点无子树 巳不存在 D．没有结点

(4)按照二叉树的定义，具有3个结点的二叉树有——种形态(不考虑数据信息的组合情况)。 A．2 B．3 C．4 D．5

(5)若一棵度为7的树有8个度为1的结点，有7个度为2的结点，有6个度为3的结点，有5个度为4的结点，有4个度为5的结点，有3个度为6的结点，有2个度为7的结点，则该树一共有——个叶结点。

A．35 B．28 C．77 D．78

(6)若一棵二叉树有10个度为2的结点，则该二叉树的叶结点的个数是——。 A．9 B．11 C．12 D．不确定

(7)若一棵满二叉树有2047个结点，则该二叉树中叶结点的个数为——。 A．512 B．1024 C．2048 D．4096

(8)深度为h的满二叉树的第i层有——个结点。(i≤h) A．2(i)—1 B．2(i)-1 C．2(h)—1 D．2(h)-1 (9)深度为h的完全二叉树的第i层有——个结点。(i

A．n-1 B．n C．Llog2(n)』 D．Llog2(n)』+1 (11)具有2000个结点的非空二叉树的最小深度为——。 A．9 B．10 C．11 D．12

(12)若某完全二叉树的深度为h，则该完全二叉树中至少有——个结点。 A．2(h) B．2(h)-1 c．2(h)+1 D．2(h—1)

(13)若二叉树的前序序列与后序序列的次序正好相反，则该二叉树一定是——的二叉 树。

第 34 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

A．空或仅有一个结点 B．其分支结点无左子树 C．其分支结点无右子树 D．其分支结点的度都为1

(14)任何一棵非空二叉树中的叶结点在前序遍历、中序遍历与后序遍历中的相对位置——————。 A．都会发生改变 B．不会发生改变

C．有可能会发生改变 D．部分会发生改变

(15)对于一个数据元素序列，按照逐点插入方法建立一棵二叉排序树，该二叉排序树的形状取决于——。

A．该序列的存储结构 B．序列中数据元素的取值范围 C，数据元素的输人次序 D．使用的计算机的软、硬件条件

(16)对一棵二叉排序树进行——遍历，可以得到该二叉树的所有结点按值从小到大排列 的序列。 A．前序 B．中序 C．后序 D．按层次 (17)除了前序遍历(DLR)、中序遍历(LDR)与后序遍历(LRD)外，二叉树的遍历方法还可以有DRL、RDL和RLD三种。对于一棵二叉排序树，采用——遍历方法可以得到该二叉排序树的所有结点按值从大到小排列的序列。·

A．LDR B．LRD C．RLD D．RDL (18)在二叉排序树中进行查找的效率与——有关。

A。二叉排序树的深度 B．二叉排序树的结点的个数 C．被查找结点的度 D．二叉排序树的存储结构

(19)在具有n个结点的二叉排序树中查找一个结点的过程的时间复杂度约为——。 A．O(1) B．O(n) C．O(nz) D．O(10gan)

(20)下列名词术语中，与数据的存储结构有关系的仅是——。

A．完全二叉树 B．满二叉树 C．线索二叉树 D．二叉排序树 (21)平衡二叉树中任意结点的平衡因子只能是——之一。

A．0，1，2 B．0，1 C．-1，+1 D．0，-1，+1 7． 3 填空题。

(1)任何非空树中有且仅有一个结点没有前驱结点，该结点就是树的——。 (2)树的层次定义为——。

(3)度为k的树中第i层最多有——个结点(i≥1)。 (4)深度为h的k叉树最多有——个结点。 (5)非空二叉树一共有——种基本形态。 (6)非空二叉树中第i层最多有——个结点。 (7)深度为h的二叉树最多有————个结点。 (8)具有n个结点的完全二叉树的深度h二——。

(9)若二叉树有N0个叶结点，n2个度为2的结点，则N0与n2的关系是——。

(10)若具有n个结点的非空zX．树有N0个叶结点，则该二叉树有——个度为2的结点，——个度为1的结点。

(11)对具有n个结点的完全二叉树按照层次从上到下，每一层从左到右的次序对所有结点进行编号，编号为i的结点的双亲结点的编号为——，左孩子的编号为——，右孩子的编号为——。

(12)若具有n个结点的二叉树采用二叉链表存储结构，则该链表中有——个指针域，其中有——个指针域用于链接孩子结点，l-个指针域空闲存放着NULL。

(13)二叉树的遍历方式通常有——、——、——和_____四种。

(14)已知二叉树的前序遍历序列为ABDCEFG，中序遍历序列为DBCAFEG，其后序遍历序列为——。 (15)已知某完全二叉树采用顺序存储结构，结点的存放次序为A,B，C,D，E，F，G，H，I，J，该完全二叉树的后序序列为——。

第 35 页 共 63 页