中国大学数据结构与算法1（张淼 2021春季学期）章节答案(mooc完整答案)

分类：初级会计习题发布于：2024-06-02 13:01:51ė08025次浏览681条评论

中国大学数据结构与算法1（张淼 2021春季学期）章节答案(mooc完整答案)

第一课

第一课测验

1、中国张淼章节以下与数据的大学答案答案存储结构无关的术语是（）
A、哈希表
B、数据算法链表
C、结构栈
D、春季循环队列

2、学期某算法的完整时间复杂度是O()，表明该算法的中国张淼章节()
A、问题规模与成正比
B、大学答案答案问题规模是数据算法
C、执行时间与正比
D、结构执行时间等于

3、春季以下关于数据结构的学期说法中，正确的完整是（）
A、数据的中国张淼章节存储结构独立于其逻辑结构
B、数据结构仅由其逻辑结构和存储结构决定
C、数据的逻辑结构独立于其存储结构
D、数据的逻辑结构唯一决定了其存储结构

4、以下算法的时间复杂度为（）
A、
B、
C、
D、

5、求整数n（n≥0）阶乘的算法如下，其时间复杂度是()
A、
B、
C、
D、

6、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（）
A、数据的操作方法
B、数据元素的类型
C、数据元素之间的关系
D、数据的存取方法

7、The characteristic of an algorithm that can be handled when an illegal operation occurs is called （）
A、readability
B、robustness
C、reliability
D、correctness

8、In data structures，logically，data structures can be divided into（）
A、dynamic structure and static structure
B、internal structure and external structure
C、compact structure and non-compact structure
D、linear structure and nonlinear structure

9、For?the?following?program?fragment?the?running?time(Big-O)?is（）
A、
B、
C、
D、

10、The running time of an algorithm can be expressed as the following equation，So the?running?time(Big-O)?is()
A、
B、
C、
D、

11、以下数据结构中，（）是非线性数据结构。
A、字符串
B、树
C、栈
D、队列

12、在线性表中，处理开始元素外，每个元素（）
A、有多个后继元素
B、有多个前驱元素
C、只有唯一的后继元素
D、只有唯一的前驱元素

13、若线性表最常用的操作是存取第i个元素及其前驱后继元素的值，为了提高效率，应采取（）的存储方式
A、顺序表
B、单链表
C、单循环链表
D、双向链表

14、在一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动（）个元素
A、i-1
B、n-i
C、n-i-1
D、n

15、设线性表中有2n个元素，（）在单链表上的实现比在顺序表上的效率高
A、在最后一个元素的后面插入一个新元素
B、删除所有值为x的元素
C、交换第i个素和第2n-i-1个元素的值（i=0,…,n-1）
D、顺序输出前k个元素

16、单链表中，增加一个头结点的目的是()
A、说明单链表是线性表的链式存储
B、标识表结点中首结点的位置
C、方便运算实现
D、是单链表中至少有一个结点

17、The Linked List is designed for conveniently（）data item
A、inserting
B、getting
C、locating
D、finding

18、The main advantage of a circular list is that()
A、can traverse the entire list from any point in the table
B、no longer requires head pointers
C、when knows the location of a node，it can easily find its direct predecessor
D、in the delete operation，to ensure that the list continues to open

19、The condition that the double-loop linked list L with a head is empty is()
A、L->prior==L&&L->next==NULL
B、L->prior==L&&L->next==L
C、L->prior==NULL&&L->next=L
D、L->prior==NULL&&L->next==NULL

20、以下（）是一个线性表
A、邻接表
B、由n个实数组成的集合
C、由100个字符组成的序列
D、所有整数组成的序列

21、一个线性表最常用的操作是存取任意指定序号的元素和最后进行插入删除操作，则利用（）存储方式可以节省时间
A、顺序表
B、带头结点的双循环链表
C、双向链表
D、单循环链表

22、对于顺序表，访问第i个位置的元素和第i个位置插入一个元素的时间复杂度为()
A、O（1），O（n）
B、O（n），O（1）
C、O（n），O（n）
D、O（1），O（1）

23、Combine two ordered tables with n elements into an ordered table，with the least number of comparisons()
A、n-1
B、2n-1
C、2n
D、n

24、The element in pointer P refers to the bidirectional cyclic list（P is header），and the tail element of List（L） is()
A、NULL
B、P->Right
C、L
D、P->Left

25、在一个单链表中，已知q所指向结点是p所指结点的前驱节点，若在q和p之间插入结点s，则执行()
A、q->next=s; s->next=p;
B、p->next=s->next; s->next=p;
C、p->next=s; s->next=q;
D、s->next=p->next; p->next=s;

26、The characteristic of an algorithm that can be handled when an illegal operation occurs is called （）
A、robustness
B、correctness
C、readability
D、reliability

27、下列关于线性表说法正确的是()
A、顺序存储方式只能用于存储线性结构
B、在一个长度为n的有序单链表中插入一个新结点并仍保持有序的时间复杂度是O（n）
C、取线性表第i个元素的时间与i的大小无关
D、静态链表需要分配较大的连续空间，插入和删除不需要移动元素

28、数据元素是数据的最小单位。

29、一个数据结构是由一个逻辑结构、物理结构和这个逻辑结构上的一个基本运算集构成的整体。

30、算法是对特定问题求解步骤的一种描述，是（）的指令序列

第一课作业

1、简述逻辑结构与存储结构的关系。

2、度量一个算法的执行时间通常有几种方法？各有何优缺点？

3、分析下面函数的时间复杂度。 void func(int n) { int i = 1, k = 100; while(i < n) { k++; i+=2; } }

4、

5、线性表可以用于顺序表或链表存储，试问：两种存储表示各有哪些主要优缺点？如果有n个表同时并存，并且在处理过程中各表的长度会动态变化，表的总数也可能自动改变，在此情况下，应选用哪种存储表示？为什么？若表的总数基本固定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，应采用哪种存储表示？为什么？

第二课

第二课测验

1、假定利用数据a[n]顺序存储一个栈，用top表示栈顶指针，top==-1表示栈空，并已知栈未满，当元素x进栈时执行的操作是()
A、a[top++]=x
B、a[++top]=x
C、a[top--]=x
D、a[--top]=x

2、用S表示进栈操作，用X表示出栈操作，若元素的进栈顺序是1234，为了得到1342的出栈顺序，相应的操作序列是()
A、SXSSXSXX
B、SXSXSSXX
C、SSSXXSXX
D、SXSSXXSX

3、用链式存储方式的队列进行删除操作时()
A、头尾指针都要修改
B、头尾指针可能都要修改
C、仅修改头指针
D、仅修改尾指针

4、一个队列的入队顺序是1，2，3，4，则出队的顺序是（）
A、3，2，4，1
B、1，2，3，4
C、4，3，2，1
D、1，4，3，2

5、假设循环单链表表示的队列长度为n，队头固定在链表尾部，若只设置头指针，则进队操作的时间复杂度是()
A、
B、
C、
D、

6、()不是栈的基本操作
A、判断栈是否为空
B、删除栈底元素
C、将栈置为空栈
D、删除栈顶元素

7、设链表不带头结点且所有操作均在表头进行，则下列最不适合链栈的是()
A、只有表尾结点指针，没有表头指针的双向循环链表
B、只有表头结点指针，没有表尾指针的单向循环链表
C、只有表头结点指针，没有表尾指针的双向循环链表
D、只有表尾结点指针，没有表头指针的单向循环链表

8、3个不同元素依次进栈，能得到（）种不同的出栈序列
A、4
B、5
C、6
D、7

9、栈和队列的主要区别在于()
A、它们的存储结构不一样
B、它们的逻辑结构不一样
C、所包含的元素不一样
D、插入、删除操作的限定不一样

10、在一个链队列中，假设队头指针是front，队尾指针是rear，x所指向的元素需入队，则执行的操作是()
A、rear->next=x, rear=x
B、front=x, front=front->next
C、rear->next=x, x->next=null, rear=x
D、x->next=front->next, front=x

11、In general，the recursive algorithm is converted into an equivalent non-recursive algorithm that should be set()
A、set
B、stack
C、array
D、queue

12、The input sequence of the stack is 1，2，3，4，and （）cannot be its output sequence.
A、1，4，3，2
B、1，2，4，3
C、2，1，3，4
D、4，3，1，2

13、The circular queue A[0…M-1] stores its elements and uses front and rear to represent the header and queue end respectively，while the condition of the full loop queue is （）
A、Q.rear==Q.front
B、(Q.rear+1)%m==Q.front
C、Q.rear+1==Q.front
D、Q.rear==Q.front+1

14、Both the stack and queue are linear structures that restrict the fetch.

15、Stacks，FIFO queues，double ended queues can be considered as derived classes of a container class. The container represents a sequential access structure that restricts access locations.

第二课作业

1、简述线性表、栈和队列的异同。

2、

3、内存中一片连续空间（不妨假设地址从1到m），提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。

第三课

第三课测验

1、串是任意有限个。
A、符号构成的集合
B、符号构成的序列
C、字符构成的集合
D、字符构成的序列

2、串是一种特殊的线性表，其特殊性体现在。
A、可以顺序存储
B、数据元素是一个字符
C、可以链式存储
D、数据元素可以是多个字符

3、两个串相等必有串长度相等且。
A、串的各位置字符任意
B、串中各位置字符均对应相等
C、两个串含有相同的字符
D、两个串所含字符任意

4、设有数组定义：char array[] = "China"；则数组array所占的存储空间为。
A、4个字节
B、6个字节
C、5个字节
D、7个字节

5、设有数组定义：char array[10] = "China"；则数组array所占的存储空间为。
A、4个字节
B、5个字节
C、6个字节
D、10个字节

6、数组在存储字符串常量时通常需要在其末尾带一个结束标记来表示串的结束。
A、'\0'
B、'#'
C、'0'
D、'\#'

7、已知字符串S为"abaabaabacacaabaabcc", 模式串t为"abaabc"。采用KMP算法进行匹配，笫一次出现匹配失败时，i=j=5, 则下次开始匹配时，i和j的值分别是。
A、i=1，j=0
B、i=5，j=0
C、i=5，j=2
D、i=6，j=2

8、已知串S="abababc"，其特征向量为。
A、0012340
B、0112340
C、0012341
D、0123400

9、KMP算法的特点是在模式匹配时指示主串的指针。
A、不会变大
B、不会变小
C、都有可能
D、无法判断

10、Which of the following is the incorrect way to assign a string value?
A、char *str； str = "string"
B、char str[7]={ 's','t','r','i','n','g'}
C、char str1[10]； str1 = "string"
D、char str1[]="string", str2[] = "1234567"

11、Assume that strings s="abcd",s1="123", then executing s2=InsStr(s,2,s1)，s2= 。
A、"123abcd"
B、"a123bcd"
C、"ab123cd"
D、"abc123d"

12、Assume that string s="abcd", then executing s2=DelStr(s,2,2)，s2=
A、"abcd"
B、"abc"
C、"ad"
D、"a"

13、If the length of the main string is n and the length of the substring is m, then the time complexity of the Naive string matching algorithm is 。
A、O(m)
B、O(n)
C、O(m*n)
D、O(m+n)

14、If the length of the main string is n and the length of the substring is m, then the time complexity of the KMP algorithm is 。
A、O(m+n)
B、O(m)
C、O(n)
D、O(m*n)

15、设有两个串S1和S2, 求S2在S1中首次出现的位置的运算称作。
A、求子串
B、判断是否相等
C、模式匹配
D、连接

第三课作业

1、

第四课

第四课测验

1、具有10个叶结点的二叉树中有个度为2的结点。
A、9
B、8
C、10
D、11

2、一棵完全二叉树上有1001个结点，其中叶子结点的个数是。
A、501
B、250
C、505
D、254

3、一个具有1025个结点的二叉树的高h（只有根结点时的高度为1）为。
A、11
B、11到1025之间
C、10
D、10到1024之间

4、一棵二叉树高度为h（只有根结点时的高度为1）,所有结点的度或为0，或为2，则这棵二叉树最少有个结点。
A、2h+1
B、2h-1
C、2h
D、h+1

5、高度为 K（只有根结点时的高度为1）的二叉树最大的结点数为。
A、
B、
C、
D、

6、A complete binary tree of height “k”(the height is 1 when only the root in the tree) contains nodes at least.
A、
B、
C、
D、

7、A full binary tree with 2n+1 nodes contains .
A、n-1 leaf nodes
B、n leaf nodes
C、n-1 non-leaf nodes
D、n non-leaf nodes

8、A full binary tree with n leaves contains nodes.
A、
B、
C、n
D、2n-1

9、A binary tree of depth “d” is an almost complete binary tree if .
A、None of them
B、(i) Each leaf in the tree is either at level “d” or at level “d–1”
C、Both (i) & (ii)
D、(ii) For any node “n” in the tree with a right descendent at level “d” all the left descendents of “n” that are leaves, are also at level “d”

10、二叉树的第k（只有根结点时的层数为1）层上最多含有结点数为。
A、
B、
C、
D、

11、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是。
A、9
B、不确定
C、11
D、15

12、The number of leaf nodes in a full binary tree of depth d is .
A、
B、
C、
D、

13、) 由3个结点所构成的二叉树有种形态。

14、一棵深度为6的满二叉树有个分支结点

15、设一棵完全二叉树具有1000个结点则此完全二叉树有个度为2的结点。

第四课作业

1、具有33个结点的完全二叉树的深度是多少？有多少叶结点？有多少个度为1的结点？

2、某二叉树有20个叶结点，有30个结点仅有一个孩子，求该二叉树的总结点数是多少？

3、

4、

第五课

第五课测验

1、一棵二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为。
A、DEBCFA
B、DEBAFC
C、DEBFCA
D、DEFBCA

2、在任何一棵二叉树中，如果结点a有左孩子b, 右孩子c, 则在结点的先序序列、中序序列、后序序列中，。
A、结点a一定在结点c的前面
B、结点b一定在结点a的前面
C、结点a一定在结点b的前面
D、结点b一定在结点c的前面

3、在二叉树的前序序列、中序序列和后序序列中，所有叶子结点的先后顺序。
A、前序和中序相同，而后序不同
B、中序和后序相同，而前序不同
C、都不相同
D、完全相同

4、下列序列中，不能唯一地确定一棵二叉树的是。
A、层次序列和中序序列
B、后序序列和中序序列
C、先序序列和中序序列
D、先序序列和后序序列

5、设结点X和Y是二叉树中任意的两个结点，在该二叉树的先序遍历序列中X在Y之前，而在其后序遍历序列中X在Y之后，则X和Y的关系是。
A、X 是Y 的右兄弟
B、X 是Y 的后代
C、X 是Y 的祖先
D、X 是Y 的左兄弟

6、已知一棵二叉树的后序序列为DABEC,中序序列为DEBAC,则先序序列为。
A、DEABC
B、DECAB
C、CEDBA
D、ACBED

7、已知一棵二叉树的层次序列为ABCDEF,中序序列为BADCFE,则先序序列为。
A、ABCDEF
B、ACBEDF
C、FCEDBA
D、BDFECA

8、对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用次序的遍历实现编号。
A、中序遍历
B、层次遍历
C、先序遍历
D、后序遍历

9、The pre-order and post-order traversal of a Binary Tree is 1234 and 4321, respectively. Then the In-order traversal of this tree will not be .
A、1234
B、4321
C、2341
D、3241

10、The pre-order and post-order traversal of a Binary Tree generates the same output. The tree can have maximum .
A、Any number of nodes
B、One node
C、Two nodes
D、Three nodes

11、二叉树的先序遍历的递归实现如下： template<class T> void BinaryTree<T>::PreOrder (BinaryTreeNode<T> *root) { if (root != NULL) { ; } } 则横线部分应为。
A、Visit(root->value()); PreOrder(root->leftchild()); PreOrder(root->rightchild());
B、PreOrder(root->leftchild()); PreOrder(root->rightchild()); Visit(root->value());
C、PreOrder(root->leftchild()); Visit(root->value()); PreOrder(root->rightchild());
D、PreOrder(root->rightchild()); Visit(root->value()); PreOrder(root->leftchild());

12、设n、m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是。
A、n 是m祖先
B、n 在m 左方
C、n 在m 右方
D、n 是m 子孙

13、一棵二叉树的前序遍历序列为1234567, 它的中序遍历序列可能是。
A、1463572
B、4135627
C、3124567
D、1234567

14、The pre-order and post-order traversal of a Binary Tree is A 、B 、C and C 、B 、A, respectively. The number of trees that satisfy the conditions is .
A、4
B、1
C、2
D、3

15、若一棵二叉树的前序遍历序列为a, e, b, d, c，后序遍历序列为b, c, d, e, a，则根结点的孩子结点。
A、有e、b
B、无法确定
C、只有e
D、有e、c

第五课作业

1、

2、

第六课

第六课测验

1、按照遍历二叉搜索树得到的序列是一个有序序列。
A、层次
B、先序
C、中序
D、后序

2、在二叉搜索树中查找的效率与有关
A、二叉排序树的结点个数
B、被查找结点的度
C、二叉搜索树的深度
D、二叉搜索树的存储结构

3、在二叉搜索树的存储结构中，关键字值最大的结点。
A、左右指针均不为空
B、左指针一定为空
C、右指针一定为空
D、左右指针均为空

4、对于下列关键字序列，不可能构成某二叉搜索树中的一条查找路径的序列是。
A、12，25，71，68，33，34
B、21，89，77，29，36，38
C、95，22，91，24，94，71
D、92，20，91，34，88，35

5、从空树开始一次插入元素52，26，14，32，71，60，93，58，24，41后构成一个二叉搜索树。在该树中查找60要进行比较的次数是。
A、3
B、4
C、5
D、6

6、构造含有n个结点的二叉搜索树时，最理想的情况下的高度为（只含有根节点时，高度为1）。
A、
B、取下界
C、取上界
D、

7、不可能生成如下图二叉搜索树的关键字序列是。
A、4，5，1，2，3
B、4，2，1，3，5
C、4，5，2，1，3
D、4，2，5，3，1

8、对于二叉搜索树，下面说法正确的是。
A、二叉搜索树是动态树表，查找失败时或插入新结点时，会引起树的重新分裂组合
B、用逐点插入法构造二叉搜索树，若先后插入的关键字有序，二叉搜索树的深度最大
C、对二叉搜索树进行层次遍历可得到有序序列
D、在二叉搜索树中进行查找，关键字比较的次数不超过结点数的1/2

9、分别用以下序列构造二叉搜索树，与其他三个序列构造结果不同的是。
A、100，60，80，90，120，110，130
B、100，80，60，90，120，130，110
C、100，120，110，130，80，60，90
D、100，80，90，60，120，110，130

10、在含有n个结点的二叉搜索树中查找某个关键字，最多进行次比较
A、
B、
C、
D、

11、A binary search tree has a preorder sequence of { 50，38，30，45，40，48，70，60，75，80}，its inorder sequence is .
A、50，38，70，30，45，60，75，40，48，80
B、30，40，48，45，38，60，80，75，70，50
C、50，38，30，45，48，40，70，60，75，80
D、30，38，40，45，48，50，60，70，75，80

12、Build a binary search tree with the sequence of { 40，72，38，35，67，51，90，8，55，21}，and its average search length ASL = .
A、3.5
B、3.2
C、4
D、3.6

13、The value of the node in the binary search tree is between 1 and 1000. When searching for 363, which search sequence is impossible .
A、2，252，401，398，330，344，397，363
B、924，220，911，244，898，258，362，363
C、925，202，911，240，912，245，363
D、2，399，387，219，266，382，381，278，363

14、The largest value in the binary search tree belongs to the rightmost node.

15、The nodes in the binary search tree may have the same values.

第六课测验

1、在平衡二叉树中（）
A、任意结点的左、右子树高度之差的绝对值不大于1
B、不存在度为1的结点
C、任意结点的左、右子树结点数目相同
D、任意结点的左、右子树高度相同

2、有12个结点的平衡二叉树的最大深度是 ()
A、3
B、4
C、5
D、6

3、由元素序列27，16，75，38，51构造平衡二叉树，则首次出现的最小不平衡子树的根（即离插入节点最近且平衡因子的绝对值为2的节点）为（）
A、27
B、75
C、51
D、38

4、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点在A，并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则应进行( )型调整以使其平衡
A、RL
B、LL
C、RR
D、LR

5、下列二叉树中，不满足平衡二叉树定义的是（??）
A、
B、
C、
D、

6、一棵深度为k的平衡二叉树，其每个非叶子结点的平衡因子均为0，则该树的结点数是( )。
A、2k-1
B、2k-1+1
C、2k-1-1
D、2k-1

7、一个高度为4的平衡二叉树，最小结点数是
A、14
B、7
C、15
D、8

8、在AVL树中，由于在Ａ结点的右孩子的右子树上插入结点，使Ａ结点的平衡因子由-1变为-2，使其失去平衡，应采用（）型平衡旋转
A、LL
B、RL
C、RR
D、LR

9、如图所示平衡二叉树,插入元素78后,应作什么处理,使其仍为一棵平衡二叉树
A、RL型平衡调整
B、LL型平衡调整
C、RR型平衡调整
D、LR型平衡调整

10、在一棵AVL树中，每个结点的平衡因子的取值范围是
A、-2至2
B、-1至1
C、1至2
D、0至1

11、All leaf nodes of the AVL tree are not necessarily at the same level. Similarly, the leaf nodes of a balanced m-way search tree are not necessarily at the same level.

12、AVL tree refers to a binary tree whose absolute value of the height difference between the left and right subtrees is not greater than 1

13、AVL is a binary tree whose absolute value of the balance factor of any node on the tree is not greater than 1.

14、In the AVL tree, inserting a new node into the tree of a node whose balance factor is not zero will cause a balance rotation

第六课作业

1、

2、

3、

第七课

第七课测试

1、建堆时，最坏情况下需要挪动元素次数是等于树中各结点的高度和。问：对于元素个数为12的堆，其各结点的高度之和是多少？
A、12
B、11
C、10
D、15

2、堆是一种有用的数据结构。下列关键码序列（）是一个堆。
A、94,53,31,72,16,23
B、16,31,23,94,53,72
C、16,53,23,94,31,72
D、94,31,53,23,16,72

3、设计一个判别表达式中左，右括号是否配对出现的算法，采用（?）数据结构最佳。
A、队列
B、线性表的链式存储结构
C、线性表的顺序存储结构
D、栈

4、下列关键字序列中，构成大根堆的是()
A、9，8，6，3，5，l，2，7
B、9，8，6，7，5，1，2，3
C、9，8，1，7，5，6，2，33
D、5，8，1，3，9，6，2，7

5、将一个递归算法改为对应的非递归算法时，通常需要使用____。
A、优先队列
B、循环队列
C、栈
D、队列

6、The enqueuing sequence of a queue is 1, 2, 3, 4, and the output sequence of the queue is（）
A、3，2，4，1
B、1，4，3，2
C、1，2，3，4
D、4，3，2，1

7、The following physical storage of various structures must occupy continuous storage space:（）
A、Stack
B、Array
C、Binary tree
D、Linked list

8、在下列的数据结构中哪一种更适合用来实现优先队列。
A、栈
B、单链表
C、堆
D、队列

9、The two storage structures commonly used in the stack structure are the sequential storage structure and the linked list storage structure.

10、Stacks and queues are non-linear data structures

11、优先队列的主要特点是支持从一个集合中快速地查找并移出有最大值或最小值的元素。

12、Heap is not necessarily a complete binary tree

第七课作业

1、

2、

第八课

第八课测验

1、关于哈夫曼树，下列说法正确的是( )。
A、在哈夫曼树中，权值较大的叶子结点一般离根结点较远
B、哈夫曼树是带权路径长度最短的二叉树，路径上权值较大的结点离根较近
C、在哈夫曼编码中，当两个字符出现频率相同时，其编码也相同，对于这种情况应作特殊外理
D、在哈夫曼树中，权值相同的叶子结点都在同一层上

2、设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。
A、2m+1
B、2m-1
C、2m
D、4m

3、有n个叶子的哈夫曼树的结点总数为（??）。
A、2n
B、2n+1?
C、不确定
D、2n-1

4、由带树为9,2,5,7的四个叶子结点树造一棵哈夫曼树，该树的带权路径长度为()
A、46
B、44
C、29
D、37

5、设T是哈夫曼树，具有5个叶子结点，树T的高度最高可以是（）
A、5
B、6
C、3
D、4

6、用整数1,2,3,4,5作为五个树叶的权值，可构造一棵带树路径长度值为__的哈夫曼树。
A、15
B、54
C、33
D、34

7、根据使用频率为五个字符设计的哈夫曼编码不可能是__。
A、000，001，010，011，1?
B、100，11，10，1，0
C、001，000，01，11，10
D、111，110，10，01，00

8、设某哈夫曼树中有199个结点，则该哈夫曼树中有( )个叶子结点。
A、99
B、100
C、102
D、101

9、Huffman树的带权路径长度WPL等于（）
A、所有结点权值之和
B、各叶子结点的带权路径长度之和
C、根结点的值
D、除根结点之外的所有结点权值之和

10、设森林F对应的二叉树为B，它有m个结点，B的根为P，P的右子树结点个数为n，森林F中的第一棵树的结点个数是__。
A、m-n
B、条件不充分，无法确定
C、m-n-1
D、n+1

11、度为4、高度为h的树，__。（高度从1开始）
A、至少有h+3个结点
B、至多有4h-1个结点
C、至多有4h个结点
D、至少有h+4个结点

12、设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（????）个。
A、n
B、n-1
C、n+1
D、n+2

13、树的后序遍历序列等同于该树对应的二叉树的(????).?
A、先序序列
B、后序序列
C、中序序列
D、以上都不是

14、在下列存储形式中，哪一个不是树的存储形式？（????）
A、顺序存储表示法
B、双亲表示法
C、孩子兄弟表示法
D、孩子链表表示法

15、如图所示的T2是由森林T1转换而来的二叉树，那么森林T1有__个叶子结点
A、4
B、5
C、6
D、7

16、设树T的高度为4，其中度为1、2、3和4的结点个数分别为4、2、1、1，则T中的叶子数为__。
A、5
B、6
C、7
D、8

17、讨论树、森林和二叉树的关系，目的是为了（????）
A、将树、森林按二叉树的存储方式进行存储
B、借助二叉树上的运算方法去实现对树的一些运算
C、将树、森林转换成二叉树
D、体现一种技巧，没有什么实际意义

18、Converting a forest F into a binary tree T represented by a child sibling linked list,What is the posterior traversal of F？
A、neither
B、Inorder Traversall of T
C、postorder traversal of T
D、preorder traversal of T

19、A tree with n nodes, in which the degree of all branch nodes is k, then the number of leaf nodes in the tree is ()
A、(nk-n+1)／k?
B、n／k
C、(n+1)／k
D、n(k-1)

20、Huffman tree must be completely binary

21、The all nodes（more than 1）in a Huffman tree cannot be even

22、Huffman tree is the tree with the shortest weighted path. The nodes with larger weights on the path are closer to the root.

23、Given a tree, you can find the only binary tree corresponding to it

24、Turn a tree into a binary tree with no left subtree at the root node

第八课作业

1、假定用于通信的电文仅由8个字母ABCDEFGH组成，各字母在电文中出现的频率分别是0.05，0.25，0.03，0.06，0.1，0.11，0.36，0.04。试为这8个字母设计不等长Huffman编码，并给出该电文的总码数。

2、

3、

4、

5、