最新消息:可做奥鹏等各院校作业论文,答案请联系QQ/微信:18866732

【奥鹏】国家开放大学2022年秋学期《数据结构(本)》形考作业3

形考作业3

试卷总分:100  得分:100

 

一、单项选择题(每小题2分,共38分)

 

1.假定一棵二叉树中,双分支结点数为15,单分支结点数为30,则叶子结点数为( )。

A.15

B.16

C.17

D.47

 

2.二叉树第k层上最多有( )个结点。

A.2k

B.2k-1

C.2k-1

D.2k-1

 

3.将含有150个结点的完全二叉树从根这一层开始,每一层从左到右依次对结点进行编号,根结点的编号为1,则编号为69的结点的双亲结点的编号为( )。

A.33

B.34

C.35

D.36

 

4.如果将给定的一组数据作为叶子数值,所构造出的二叉树的带权路径长度最小,则该树称为( )。

A.哈夫曼树

B.平衡二叉树

C.二叉树

D.完全二叉树

 

5.在一棵度具有5层的满二叉树中结点总数为( )。

A.31

B.32

C.33

D.16

 

6.一棵完全二叉树共有6层,且第6层上有6个结点,该树共有( )个结点。

A.38

B.72

C.31

D.37

 

7.利用3、6、8、12这四个值作为叶子结点的权,生成一棵哈夫曼树,该树中所有叶子结点中的最长带权路径长度为( )。

A.18

B.16

C.12

D.30

 

8.在一棵树中,( )没有前驱结点。

A.分支结点

B.叶结点

C.树根结点

D.空结点

 

9.设一棵采用链式存储的二叉树,除叶结点外每个结点度数都为2,该树结点中共有20个指针域为空,则该树有(  )个叶结点。

A.21

B.22

C.9

D.10

 

10.在一个图G中,所有顶点的度数之和等于所有边数之和的( )倍。

A.1/2

B.1

C.2

D.4

 

11.邻接表是图的一种( )。

A.顺序存储结构

B.链式存储结构

C.索引存储结构

D.散列存储结构

 

12.图的深度优先遍历算法类似于二叉树的( )遍历。

A.先序

B.中序

C.后序

D.层次

 

13.已知下图所示的一个图,若从顶点V1出发,按深度优先搜索法进行遍历,则可能得到的一种顶点序列为( )。

 

{图}

A.V1V2V4V8V3V5V6V7

B.V1V2V4V5V8V3V6V7

C.V1V2V4V8V5V3V6V7

D.V1V3V6V7V2V4V5V8奥鹏作业答案请进open5.net或请联系QQ/微信:18866732

 

14.已知如下图所示的一个图,若从顶点a出发,按广度优先搜索法进行遍历,则可能得到的一种顶点序列为(  )。

 

{图}

 

 

A.abecdf

B.aecbdf

C.aebcfd

D.aedfcb

 

15.图状结构中数据元素的位置之间存在(   )的关系。

A.一对一

B.一对多

C.多对多

D.每一个元素都有一个且只有一个直接前驱和一个直接后继

 

16.在一棵二叉树中,若编号为i的结点存在右孩子,则右孩子的顺序编号为(  )。

A.2i

B.2i-1

C.2i+1

D.2i+2

 

17.一棵具有16个结点的完全二叉树,共有(  )层。(设根结点在第一层)

A.7

B.5

C.6

D.4

 

18.对二叉排序树进行(   )遍历,可以使遍历所得到的序列是有序序列。

A.按层次

B.后序

C.中序

D.前序

 

19.已知一个图的边数为m,则该图的所有顶点的度数之和为(  )。

A.2m

B.m

C.2m+1

D.m/2

 

 

二、判断题 (每小题1分,共10分)

 

20.一棵二叉树的叶结点(终端结点)数为5,单分支结点数为2,该树共有11个结点。

 

21.一棵有14个结点的完全二叉树,则它的最高层上有7个结点。

 

22.一棵二叉树有6个叶结点,则该树总共有11个结点。

 

23.根据搜索方法的不同,图的遍历有.先序;中序;后序三种方法。

 

24.对于一棵具有n个结点的二叉树,其相应的链式存储结构中共有n-1个指针域空。

 

25.  设一棵完全二叉树,其最高层上最右边的叶结点的编号为奇数,该叶结点的双亲结点的编号为10,该完全二叉树一共有21个结点。

 

26.  设一棵完全二叉树,其最高层上最右边的叶结点的编号为偶数,该叶结点的双亲结点的编号为9,该完全二叉树一共有19个结点。

 

27.按照二叉树的递归定义,对二叉树遍历的常用算法有深度优先遍历和深度优先遍两种方法。

 

28.一棵有8个权重值构造的哈夫曼数,共有17个结点。

 

29.一棵有7个叶结点的二叉树,其1度结点数的个数为2,则该树共有15个结点。

 

 

三、程序填空题(每空6分,共12分。请点击正确选项,然后拖拽至相应的方框上)

 

30.  以下程序是后序遍历二叉树的递归算法的程序,完成程序中空格部分(树结构中左、右指针域分别为left和right,数据域data为字符型,BT指向根结点)。完成程序中空格部分。

{图}

void

Inorder (struct BTreeNode *BT)

{

if( BT!=NULL)

{

Inorder(BT->left);

__(1)__

__(2)__

}

利用上述程序对左图进行后序遍历,结果是__(3)__;

 

 

(1).选项1

(2).选项2

(3).选项3

 

31.  以下程序是中序遍历二叉树的递归算法的程序,完成程序中空格部分(树结构中左、右指针域分别为left和right,数据域data为字符型,BT指向根结点)。

 

 

 

void Inorder (struct BTreeNode *BT)

 

{

{图}

 

if(BT!=NULL){

 

Inorder(BT->left);}

 

__(1)__;

 

__(2)__;

 

}

 

利用上述程序对右图进行中序遍历,结果是__(3)__;

 

 

 

 

(1).选项1

(2).选项2

(3).选项3

 

 

四、综合应用题(每小题8分,5题,共40分)

 

32.(1)以3,4,5,8,9,作为叶结点的权,构造一棵哈夫曼树。该树的带权路径长度为   1    .

 

A,64    B.65 C. 62   D. 66

 

(2)权重为3的叶结点的哈夫曼编码为   2    。

 

A.010   B.0101   C.000   D.0111

(1).__1__

A.A

B.B

C.C

D.D

(2).__2__

A.A

B.B

C.C

D.D

 

33.(1)以2,3,4,7,8,9作为叶结点的权,构造一棵哈夫曼树,该树的带权路径长度为   1

 

A,66    B. 80   C. 62D. 87

 

(2)权重值为4的叶结点的哈夫曼编码为   2    。

 

A.0001 B. 1110 C.001 D. 110

(1).__1__

A.A

B.B

C.C

D.D

(2).__2__

A.A

B.B

C.C

D.D

 

34.(1)已知某二叉树的后序遍历序列是debca,中序遍历序列是dbeac,该二叉树的根结点是   1

 

A. e    B. c    C.b    D. a

 

(2)先序遍历序列是   2    。

 

A. e,b,c,d,a     B. c,a,b,,d,e    C.a,b,d,e,c    D. a.c,b,d,e,

(1).__1__

A.A

B.B

C.C

D.D

(2).__2__

A.A

B.B

C.C

D.D

 

35.(1)已知某二叉树的先序遍历序列是aecdb,中序遍历序列是eadcb,该二叉树的根结点是   1    ;

 

A. e     B. c    C.b    D. a

 

(2)后序遍历序列为   2    。

 

A. e,d,b,c,a    B. c,a,b,,d,e   C.a,b,d,e,c   D. a.c,b,d,e,

(1).__1__

A.A

B.B

C.C

D.D

(2).__2__

A.A

B.B

C.C

D.D

 

36.(1)以给定权重值5,6,17,18,25,30,为叶结点,建立一棵哈夫曼树,该树的中序遍历序列为   1

A. 5,11,28,6,17,58,30,101,18,43,25

B.5,11,6,28,17,58,30,101,18,43,25

C.5,11,6,28,101,58,30,17,18,43,25

D.5,11,6,28,17,58,30,101,18,25,43

 

 

 

(2)权重值为6的叶结点的哈夫曼为   2    .

 

A.1001   B.011   C.001   D.0001

(1).__1__

A.A

B.B

C.C

D.D

(2).__2__

A.A

B.B

C.C

D.D

转载请注明:奥鹏作业之家 » 【奥鹏】国家开放大学2022年秋学期《数据结构(本)》形考作业3

发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址