2026年自考數(shù)據(jù)結(jié)構(gòu)樹與二叉樹知識(shí)練習(xí)與考點(diǎn)分析含答案一、單選題（共10題，每題2分，計(jì)20分）1.在二叉樹中，若某節(jié)點(diǎn)的度為2，則該節(jié)點(diǎn)稱為（）。A.葉子節(jié)點(diǎn)B.內(nèi)部節(jié)點(diǎn)C.根節(jié)點(diǎn)D.線索節(jié)點(diǎn)2.深度為4的滿二叉樹共有（）個(gè)節(jié)點(diǎn)。A.15B.16C.31D.323.對(duì)于一棵完全二叉樹，其第i層（i從1開(kāi)始）最多有（）個(gè)節(jié)點(diǎn)。A.2^(i-1)B.2^i-1C.2^(i-1)-1D.2^i4.在二叉樹的遍歷中，先訪問(wèn)根節(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹的遍歷方式稱為（）。A.先序遍歷B.中序遍歷C.后序遍歷D.層序遍歷5.一棵二叉樹的前序遍歷序列為ABCD，中序遍歷序列為BADC，則該二叉樹的后序遍歷序列為（）。A.DCBAB.CBADC.ADCBD.DCAB6.在二叉樹的線索化過(guò)程中，對(duì)于某個(gè)節(jié)點(diǎn)，若其左指針為空，則將其左指針設(shè)置為（）。A.父節(jié)點(diǎn)指針B.左孩子指針C.線索指針D.右孩子指針7.在二叉樹中，某個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)是指（）。A.該節(jié)點(diǎn)的左孩子B.該節(jié)點(diǎn)的右孩子C.該節(jié)點(diǎn)的父節(jié)點(diǎn)D.以上都不對(duì)8.完全二叉樹的性質(zhì)之一是：對(duì)于任意節(jié)點(diǎn)u，若其右子節(jié)點(diǎn)存在，則其左子節(jié)點(diǎn)一定存在，該性質(zhì)描述的是（）。A.節(jié)點(diǎn)度的唯一性B.節(jié)點(diǎn)層次的唯一性C.節(jié)點(diǎn)父指針的唯一性D.節(jié)點(diǎn)子樹結(jié)構(gòu)的唯一性9.在二叉樹的層次遍歷中，第3層的節(jié)點(diǎn)數(shù)最多為（）個(gè)。A.8B.7C.6D.510.對(duì)于一棵二叉搜索樹，若插入一個(gè)新節(jié)點(diǎn)后，該樹不再滿足二叉搜索樹的性質(zhì)，則可能的原因是（）。A.插入節(jié)點(diǎn)的值與父節(jié)點(diǎn)值相同B.插入節(jié)點(diǎn)的值與左孩子值相同C.插入節(jié)點(diǎn)的值與右孩子值相同D.插入節(jié)點(diǎn)的值與根節(jié)點(diǎn)值相同二、多選題（共5題，每題3分，計(jì)15分）1.下列關(guān)于二叉樹的說(shuō)法中，正確的有（）。A.二叉樹的度為至多為2B.二叉樹的深度為根節(jié)點(diǎn)到葉節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)C.二叉樹的節(jié)點(diǎn)數(shù)至少為1D.二叉樹的葉子節(jié)點(diǎn)數(shù)等于度為2的節(jié)點(diǎn)數(shù)加1E.二叉樹的每個(gè)節(jié)點(diǎn)至多有兩個(gè)子節(jié)點(diǎn)2.在二叉樹的遍歷中，中序遍歷的特點(diǎn)是（）。A.先訪問(wèn)根節(jié)點(diǎn)B.再訪問(wèn)左子樹C.最后訪問(wèn)右子樹D.遍歷順序與節(jié)點(diǎn)的存儲(chǔ)順序無(wú)關(guān)E.遍歷順序與節(jié)點(diǎn)的存儲(chǔ)順序有關(guān)3.線索二叉樹的作用是（）。A.提高二叉樹的遍歷效率B.增加二叉樹的存儲(chǔ)空間C.實(shí)現(xiàn)二叉樹的快速查找D.保存二叉樹的結(jié)構(gòu)信息E.優(yōu)化二叉樹的插入和刪除操作4.完全二叉樹的性質(zhì)包括（）。A.葉子節(jié)點(diǎn)都集中在最底層B.每個(gè)非葉子節(jié)點(diǎn)的度為2C.若某個(gè)節(jié)點(diǎn)的右子節(jié)點(diǎn)存在，則其左子節(jié)點(diǎn)一定存在D.假設(shè)二叉樹的節(jié)點(diǎn)數(shù)為n，則其第i層（i從1開(kāi)始）的節(jié)點(diǎn)數(shù)為2^(i-1)E.完全二叉樹的深度為log2(n+1)向上取整5.二叉搜索樹的性質(zhì)包括（）。A.左子樹的所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值B.右子樹的所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值C.左子樹和右子樹都是二叉搜索樹D.左子樹和右子樹可以不是二叉搜索樹E.二叉搜索樹中任意節(jié)點(diǎn)的左子樹和右子樹的節(jié)點(diǎn)數(shù)相等三、填空題（共10題，每題2分，計(jì)20分）1.在二叉樹中，節(jié)點(diǎn)的度為該節(jié)點(diǎn)擁有的__________的個(gè)數(shù)。2.一棵深度為5的滿二叉樹共有__________個(gè)節(jié)點(diǎn)。3.在二叉樹的先序遍歷中，根節(jié)點(diǎn)總是__________。4.在二叉樹的線索化過(guò)程中，若某個(gè)節(jié)點(diǎn)的右指針為空，則將其右指針設(shè)置為_(kāi)_________。5.在二叉樹的中序遍歷中，左子樹總是先于__________遍歷。6.完全二叉樹的性質(zhì)之一是：對(duì)于任意節(jié)點(diǎn)u，若其左子節(jié)點(diǎn)存在，則其右子節(jié)點(diǎn)__________。7.在二叉樹的層次遍歷中，第i層的節(jié)點(diǎn)數(shù)最多為_(kāi)_________個(gè)。8.對(duì)于一棵二叉搜索樹，若插入一個(gè)新節(jié)點(diǎn)后，該樹不再滿足二叉搜索樹的性質(zhì)，則可能的原因是__________。9.線索二叉樹中，線索是指__________。10.二叉搜索樹的性質(zhì)之一是：對(duì)于任意節(jié)點(diǎn)，其左子樹的所有節(jié)點(diǎn)的值都__________。四、判斷題（共5題，每題2分，計(jì)10分）1.在二叉樹中，每個(gè)節(jié)點(diǎn)至多有兩個(gè)子節(jié)點(diǎn)。（）2.深度為4的滿二叉樹共有31個(gè)節(jié)點(diǎn)。（）3.在二叉樹的先序遍歷中，左子樹總是先于右子樹遍歷。（）4.完全二叉樹的性質(zhì)之一是：對(duì)于任意節(jié)點(diǎn)，若其右子節(jié)點(diǎn)存在，則其左子節(jié)點(diǎn)一定存在。（）5.二叉搜索樹的性質(zhì)之一是：對(duì)于任意節(jié)點(diǎn)，其左子樹的所有節(jié)點(diǎn)的值都小于該節(jié)點(diǎn)的值。（）五、簡(jiǎn)答題（共5題，每題5分，計(jì)25分）1.簡(jiǎn)述二叉樹的定義及其基本性質(zhì)。2.解釋二叉樹的先序遍歷、中序遍歷和后序遍歷，并舉例說(shuō)明。3.什么是線索二叉樹？線索二叉樹的作用是什么？4.簡(jiǎn)述完全二叉樹的定義及其性質(zhì)。5.什么是二叉搜索樹？二叉搜索樹有哪些性質(zhì)？六、應(yīng)用題（共5題，每題10分，計(jì)50分）1.已知一棵二叉樹的前序遍歷序列為ABCD，中序遍歷序列為BADC，請(qǐng)畫出該二叉樹。2.請(qǐng)編寫一個(gè)算法，實(shí)現(xiàn)二叉樹的先序遍歷。3.請(qǐng)編寫一個(gè)算法，實(shí)現(xiàn)二叉樹的層次遍歷。4.請(qǐng)編寫一個(gè)算法，實(shí)現(xiàn)二叉搜索樹的插入操作。5.請(qǐng)編寫一個(gè)算法，實(shí)現(xiàn)二叉樹的線索化操作。答案與解析單選題1.B解析：二叉樹的節(jié)點(diǎn)度是指該節(jié)點(diǎn)擁有的子樹的個(gè)數(shù)。度為2的節(jié)點(diǎn)即有兩個(gè)子節(jié)點(diǎn)，稱為內(nèi)部節(jié)點(diǎn)。2.C解析：滿二叉樹的定義是除最底層外，每一層都是滿的。深度為4的滿二叉樹共有1+2+4+8+16=31個(gè)節(jié)點(diǎn)。3.A解析：第i層的節(jié)點(diǎn)數(shù)最多為2^(i-1)，因?yàn)槊恳粚佣际菨M的。4.A解析：先序遍歷的順序是先訪問(wèn)根節(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。5.A解析：根據(jù)前序遍歷序列和中序遍歷序列，可以確定二叉樹的結(jié)構(gòu)，進(jìn)而得到后序遍歷序列為DCBA。6.C解析：在二叉樹的線索化過(guò)程中，對(duì)于某個(gè)節(jié)點(diǎn)，若其左指針為空，則將其左指針設(shè)置為線索指針。7.B解析：后繼節(jié)點(diǎn)是指在該節(jié)點(diǎn)中序遍歷順序中的下一個(gè)節(jié)點(diǎn)，即該節(jié)點(diǎn)的右孩子。8.C解析：完全二叉樹的性質(zhì)之一是：對(duì)于任意節(jié)點(diǎn)u，若其右子節(jié)點(diǎn)存在，則其左子節(jié)點(diǎn)一定存在。9.A解析：在二叉樹的層次遍歷中，第3層的節(jié)點(diǎn)數(shù)最多為2^(3-1)=8個(gè)。10.A解析：插入節(jié)點(diǎn)的值與父節(jié)點(diǎn)值相同會(huì)破壞二叉搜索樹的性質(zhì)。多選題1.A,B,E解析：二叉樹的度至多為2，深度為根節(jié)點(diǎn)到葉節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)，每個(gè)節(jié)點(diǎn)至多有兩個(gè)子節(jié)點(diǎn)。2.B,C,D解析：中序遍歷的順序是先訪問(wèn)左子樹，再訪問(wèn)根節(jié)點(diǎn)，最后訪問(wèn)右子樹。遍歷順序與節(jié)點(diǎn)的存儲(chǔ)順序無(wú)關(guān)。3.A,C,D解析：線索二叉樹可以提高二叉樹的遍歷效率，保存二叉樹的結(jié)構(gòu)信息，實(shí)現(xiàn)二叉樹的快速查找。4.A,C,D,E解析：完全二叉樹的葉子節(jié)點(diǎn)都集中在最底層，若某個(gè)節(jié)點(diǎn)的右子節(jié)點(diǎn)存在，則其左子節(jié)點(diǎn)一定存在，深度為log2(n+1)向上取整。5.A,B,C解析：二叉搜索樹的性質(zhì)包括左子樹的所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值，右子樹的所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值，左子樹和右子樹都是二叉搜索樹。填空題1.子樹2.313.第一個(gè)4.線索指針5.右子樹6.存在7.2^(i-1)8.插入節(jié)點(diǎn)的值與父節(jié)點(diǎn)值相同9.空指針的指針10.小于判斷題1.√2.×3.√4.×5.√簡(jiǎn)答題1.二叉樹的定義及其基本性質(zhì)二叉樹是由n（n≥0）個(gè)節(jié)點(diǎn)組成的有限集合，該集合或者為空，或者由一個(gè)根節(jié)點(diǎn)和兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成。二叉樹的基本性質(zhì)包括：（1）度數(shù)性質(zhì)：二叉樹的任意節(jié)點(diǎn)的度至多為2；（2）深度性質(zhì)：二叉樹的深度為根節(jié)點(diǎn)到葉節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)；（3）節(jié)點(diǎn)數(shù)性質(zhì)：深度為h的二叉樹，最多有2^h-1個(gè)節(jié)點(diǎn)。2.二叉樹的先序遍歷、中序遍歷和后序遍歷（1）先序遍歷：先訪問(wèn)根節(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹；（2）中序遍歷：先遍歷左子樹，然后訪問(wèn)根節(jié)點(diǎn)，最后遍歷右子樹；（3）后序遍歷：先遍歷左子樹，然后遍歷右子樹，最后訪問(wèn)根節(jié)點(diǎn)。舉例：對(duì)于二叉樹ABCD，其中A為根節(jié)點(diǎn)，B為左子樹，C為右子樹，D為B的右子樹。先序遍歷：ABCD中序遍歷：BADC后序遍歷：DCBA3.線索二叉樹及其作用線索二叉樹是指通過(guò)修改二叉樹的空指針，將某個(gè)節(jié)點(diǎn)的空指針指向其前驅(qū)節(jié)點(diǎn)或后繼節(jié)點(diǎn)的二叉樹。線索二叉樹的作用是提高二叉樹的遍歷效率，保存二叉樹的結(jié)構(gòu)信息，實(shí)現(xiàn)二叉樹的快速查找。4.完全二叉樹的定義及其性質(zhì)完全二叉樹是由n（n≥0）個(gè)節(jié)點(diǎn)組成的有限集合，該集合或者為空，或者由一個(gè)根節(jié)點(diǎn)和兩棵互不相交的、分別稱為左子樹和右子樹的完全二叉樹組成。完全二叉樹的性質(zhì)包括：（1）葉子節(jié)點(diǎn)都集中在最底層；（2）若某個(gè)節(jié)點(diǎn)的右子節(jié)點(diǎn)存在，則其左子節(jié)點(diǎn)一定存在；（3）假設(shè)二叉樹的節(jié)點(diǎn)數(shù)為n，則其第i層（i從1開(kāi)始）的節(jié)點(diǎn)數(shù)為2^(i-1)；（4）完全二叉樹的深度為log2(n+1)向上取整。5.二叉搜索樹及其性質(zhì)二叉搜索樹（又稱二叉排序樹）是由n（n≥0）個(gè)節(jié)點(diǎn)組成的有限集合，該集合或者為空，或者由一個(gè)根節(jié)點(diǎn)和兩棵互不相交的、分別稱為左子樹和右子樹的二叉搜索樹組成。二叉搜索樹的性質(zhì)包括：（1）左子樹的所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值；（2）右子樹的所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值；（3）左子樹和右子樹都是二叉搜索樹。應(yīng)用題1.已知一棵二叉樹的前序遍歷序列為ABCD，中序遍歷序列為BADC，請(qǐng)畫出該二叉樹根據(jù)前序遍歷序列和中序遍歷序列，可以確定二叉樹的結(jié)構(gòu)如下：前序遍歷：A（根節(jié)點(diǎn)）→B（左子樹）→C（右子樹）→D（右子樹的右子樹）中序遍歷：B（左子樹）→A（根節(jié)點(diǎn)）→C（右子樹）→D（右子樹的右子樹）二叉樹結(jié)構(gòu)如下：A/\BC\/D2.請(qǐng)編寫一個(gè)算法，實(shí)現(xiàn)二叉樹的先序遍歷pythondefpreorder_traversal(root):ifrootisNone:return[]result=[]stack=[root]whilestack:node=stack.pop()result.append(node.val)ifnode.right:stack.append(node.right)ifnode.left:stack.append(node.left)returnresult3.請(qǐng)編寫一個(gè)算法，實(shí)現(xiàn)二叉樹的層次遍歷pythondeflevel_order_traversal(root):ifrootisNone:return[]result=[]queue=[root]whilequeue:node=queue.pop(0)result.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)returnresult4.請(qǐng)編寫一個(gè)算法，實(shí)現(xiàn)二叉搜索樹的插入操作pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefinsert_into_bst(root,val):ifrootisNone:returnTreeNode(val)ifval<root.val:root.left=insert_into_bst(root.left,val)else:root.right=insert_into_bst(root.right,val)returnroot5.請(qǐng)編寫一個(gè)算法，實(shí)現(xiàn)二叉樹的線索化操作pythonclassThreadNode:def__init__(self,val=0,left=None,right=None,ltag=False,rtag=False):self.val=valself.left=leftself.right=rightself.ltag=ltagself.rtag=rtagdefthread_node(root):ifrootisNone:returnNonestack=