《【2017年整理】数据结构非线性部分1(树与二叉树)自测题及解答》由会员分享，可在线阅读，更多相关《【2017年整理】数据结构非线性部分1(树与二叉树)自测题及解答（7页珍藏版）》请在金锄头文库上搜索。
1、数据结构非线性部分内容 1(树与二叉树、优先级队列)自测题(时间：2:30 小时)注：本自测题仅供自测用，不代表期末考试观点，如无雷同，敬请谅解！ 第 1 页 共 7 页一、概念题（每空 1 分，共 55 分）1树（及一切树形结构）是一种“_”结构。在树上，_结点没有直接前趋。对树上任一结点 X 来说，X 是它的任一子树的根结点惟一的 _。2由个结点所构成的二叉树有 种形态。3一棵深度为 6 的满二叉树有 个分支结点和 个叶子。4一棵具有个结点的完全二叉树，它的深度为 。5二叉树第 i(i=1)层上至多有 _个结点；深度为 k(k=1)的二叉树至多有_个结点。6对任何二叉树，若度为 2 的节点
2、数为 n2，则叶子数 n0=_。7满二叉树上各层的节点数已达到了二叉树可以容纳的_。满二叉树也是_二叉树，但反之不然。8设一棵完全二叉树有 700 个结点，则共有 个叶子结点。9.设一棵完全二叉树具有1000个结点，则此完全二叉树有 个叶子结点，有 个度为2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。10.一棵含有 n 个结点的 k 叉树，可能达到的最大深度为 ，最小深度为 。11.二叉树的基本组成部分是：根（N ）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按N L R次序），后序法（即按 次序）和中序法（也称对称序法，即按L N R次
3、序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是 。12.中序遍历的递归算法平均空间复杂度为 。13.二叉树通常有_存储结构和_存储结构两类存储结构。14.如果将一棵有 n 个结点的完全二叉树按层编号，则对任一编号为 i(1n，则结点 X 无_且无_；否则，X 的左孩子 LCHILD(X)的编号为_。（ 3） 若 2i+1n，则结点 X 无_；否则，X 的右孩子 RCHILD(X)的编号为_。15. 每个二叉链表的访问只能从_结点的指针，该指针具有标识二叉链表的作用。16.二叉链表中每个存储结点的每个指针域必须有一个值，这
4、个值或者是_的指针，或者是_。17.具有n个结点的二叉树中,一共有_个指针域,其中只有_个用来指向结点的左右孩子，其余的_个指针域为NULL。18.二叉树有不同的链式存储结构，其中最常用的是_与_。19.若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根遍历序列中的_个结点。20.树与二叉树之间最主要的差别是：二叉树中各结点的子树要区分为_和_，即使在结点只有一棵子树的情况下，也要明确指出该子树是_还是_。21.树的结点数目至少为_，二叉树的结点数目至少为_。22. 下面是中序线索树的遍历算法，树有头结点且由指针thr指向。树的结点有五个域，分别为：数据域 data，
5、左、右孩子域 lchild、rchild 和左、右标志域 ltag,rtag。规定，标志域为1是线索，O是指向孩子的指针。 inordethread(thr)p=thr-lchild;while (pdata);数据结构非线性部分内容 1(树与二叉树、优先级队列)自测题(时间：2:30 小时)注：本自测题仅供自测用，不代表期末考试观点，如无雷同，敬请谅解！ 第 2 页 共 7 页while(3) ) p=(4) ；printf(p-data);p= (5) ; 23.由_转换成二叉树时，其根结点的右子树总是空的。24.哈夫曼（Huffman）树是带权路径长度 _的树，通常权值较大的结点离根_。
6、25.用5个权值3, 2, 4, 5, 1构造的哈夫曼（Huffman ）树的带权路径长度是 。二、选择题（每空1分，共10分）（ ）1 不含任何结点的空树 。（）是一棵树; （）是一棵二叉树; （）是一棵树也是一棵二叉树; （）既不是树也不是二叉树（ ）2二叉树是非线性数据结构，所以 。（）它不能用顺序存储结构存储; （）它不能用链式存储结构存储; （）顺序存储结构和链式存储结构都能存储; （）顺序存储结构和链式存储结构都不能使用 （ ）3. 具有 n(n0)个结点的完全二叉树的深度为 。() log 2(n) () log 2(n) () log 2(n) +1 () log 2(n)+1
7、（ ）4把一棵树转换为二叉树后，这棵二叉树的形态是 。（）唯一的 （）有多种（）有多种，但根结点都没有左孩子 （）有多种，但根结点都没有右孩子5. 树是结点的有限集合，它 A 根结点，记为 T。其余的结点分成为 m（m0）个 B 的集合 T1，T2，Tm，每个集合又都是树，此时结点 T 称为 Ti的父结点，T i称为 T 的子结点（1im） 。一个结点的子结点个数为该结点的 C 。供选择的答案A： 有 0 个或 1 个 有 0 个或多个 有且只有 1 个 有 1 个或 1 个以上 B: 互不相交 允许相交 允许叶结点相交 允许树枝结点相交C： 权 维数 次数 序答案：A= B= C= 6. 二
8、叉树 A 。在完全的二叉树中，若一个结点没有 B ，则它必定是叶结点。每棵树都能惟一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点 N 的左子女是 N 在原树里对应结点的 C 。供选择的答案A： 是特殊的树 不是树的特殊形式 是两棵树的总称 有是只有二个根结点的树形结构 B: 左子结点 右子结点 左子结点或者没有右子结点 兄弟C： 最左子结点 最右子结点 最邻近的右兄弟 最邻近的左兄弟 最左的兄弟 最右的兄弟答案：A= B= C= 数据结构非线性部分内容 1(树与二叉树、优先级队列)自测题(时间：2:30 小时)注：本自测题仅供自测用，不代表期末考试观点，如无雷同，敬请谅解！ 第 3
9、 页 共 7 页三、综合题（1-7每题3分，8-10每题4分,共33分）1给定二叉树的两种遍历序列，分别是：前序遍历序列：D，A，C，E，B，H，F，G，I； 中序遍历序列：D，C，B，E，H，A，G，I，F，试画出二叉树B。2. 给定如图所示二叉树 T，请画出与其对应的中序线索二叉树。3将算术表达式（a+b）+c*(d+e)+f）*(g+h) 转化为二叉树。4. 试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。5. 编写递归算法，计算二叉树中叶子结点的数目。6. 写出求二叉树深度的算法。 7. 编写递归算法，求二叉树中以元素值为x的结点为根的子树的深度。 8设度为 m 的树
10、采用多重链表存储。每个结点有 m+1 个域，其中有一个数据域， m 个指向孩子的指针。则空指针的数目是多少？说明这种存储方式的利弊。9. 假设用于通信的电文仅由 8 个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这 8 个字母设计哈夫曼编码。使用07 的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。10. 试编写最大堆的向上调整算法函数。要求：写成内联函数的形式，程序头已给出，已通过数组 heap 建堆，建堆区间由遍历器 first 、mid 和 last 指向，即mid, last-1）是一个
11、堆，现自底向上将mid,last)调整为一个堆。template inline void _fixup(Raniter first, Raniter mid, Raniter last, T t)2825 3340 60 08 54 55数据结构非线性部分内容 1(树与二叉树、优先级队列)自测题(时间：2:30 小时)注：本自测题仅供自测用，不代表期末考试观点，如无雷同，敬请谅解！ 第 4 页 共 7 页参考答案一、概念题（每空 1 分，共 55 分）1、 分支层次、根、直接前趋2、 53、 31 324、 95、 2i-1 2 k-16、 n2+17、 最大值、完全8、 350 （n/235
12、0）9、 500 499 1 010、 n 211、 L R N F E G H D C B12、 O(n)13、 顺序、链式14、 根、 、左孩子、右孩子、2i 、右孩子、2i+1/i15、 根16、 指向该结点的一个孩子、空指针 NULL17、 2n、n-1、n+118、 二叉链表、三叉链表19、 第一20、 左子树、右子树、左子树、右子树21、 1、022、 （1）p-ltag=0 (2)p-lchild (3)p-rtag=1 & p-rchild!=thr (4) p=p-rchild (5)p=p-rchild22、 树23、 最短、较近24、 33二、选择题（每空 1 分，共 1
13、0 分）1. C 2. C 3. C 4. A 5. A= B= C= 6. A= B= C= 三、综合题（1-9 每题 3 分， 10-11 每题 4 分,共 35 分）1解：方法是：由前序先确定 root，由中序可确定 root 的左、右子树。然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定 root 的左右孩子。将他们分别作为新的 root，不断递归，则所有元素都将被唯一确定，问题得解。DAC FE GB H I数据结构非线性部分内容 1(树与二叉树、优先级队列)自测题(时间：2:30 小时)注：本自测题仅供自测用，不代表期末考试观点，如无雷同，敬请谅解！ 第 5 页 共 7 页2. 解：要遵循中序遍历的轨迹来画出每个前驱和后继。中序遍历序列：55 40 25 60 28 08
