资源描述：
《数据结构(树与图部分)练习题.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构(树与图部分)练习题一、填空题1.不考虑顺序的3个结点可构成种不同形态的树，种不同形态的二叉树。2.已知某棵完全二叉树的第4层有5个结点，则该完全二叉树叶子结点的总数为：。3.已知一棵完全二叉树的第5层有3个结点，其叶子结点数是。4.一棵具有110个结点的完全二叉树，若i＝54，则结点i的双亲编号是；结点i的左孩子结点的编号是，结点i的右孩子结点的编号是。5.一棵具有48个结点的完全二叉树，若i＝20，则结点i的双亲编号是______；结点i的左孩子结点编号是______，右孩子结点编号是______。6.在有n个叶子结点的
2、Huffman树中，总的结点数是：______。7.图是一种非线性数据结构，它由两个集合V(G)和E(G)组成，V(G)是______的非空有限集合，E(G)是______的有限集合。8.遍历图的基本方法有优先搜索和优先搜索两种方法。9.图的遍历基本方法中是一个递归过程。10.n个顶点的有向图最多有条弧；n个顶点的无向图最多有条边。11.在二叉树的二叉链表中，判断某指针p所指结点是叶子结点的条件是。12.在无向图G的邻接矩阵A中，若A[i,j]等于1，则A[j,i]等于。二、单项选择题1.树型结构的特点是：任意一个结点：（）A、可以
3、有多个直接前趋B、可以有多个直接后继C、至少有1个前趋D、只有一个后继2.如下图所示的4棵二叉树中，（）不是完全二叉树。ABCD3.深度为5的二叉树至多有（）个结点。A、16B、32C、31D、104.64个结点的完全二叉树的深度为：（）。A、8B、7C、6D、55.将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为：（）。A、98B、99C、50D、486.在一个无向图中，所有顶点的度之和等于边数的（）倍。A、1/2B、1C、2D、47.设有13个值
4、，用它们组成一棵Huffman树，则该Huffman树中共有()个结点。A、13B、12C、26D、251.若对一棵有16个结点的完全二叉树按层编号，则对于编号为7的结点x，它的双亲结点及右孩子结点的编号分别为()。A、2,14B、2,15C、3,14D、3,152.若对一棵有20个结点的完全二叉树按层编号，则对于编号为5的结点x，它的双亲结点及左孩子结点的编号分别为()。A、2,11B、2,10C、3,9D、3,103.将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非
5、叶结点的编号为：A、48B、49C、50D、514.无向图的邻接矩阵是一个()。A、对称矩阵B、零矩阵C、上三角矩阵D、对角矩阵5.由64个结点构成的完全二叉树，其深度为：()。A、8B、7C、6D、56.若对一棵有16个结点的完全二叉树按层编号，则对于编号为7的结点x，它的双亲结点及右孩子结点的编号分别为()。A、2,14B、2,15C、3,14D、3,157.图示二叉树的中序遍历序列是：（）abcdgefA、abcdgefB、dfebagcC、dbaefcgD、defbagc8.图示二叉树的后序遍历序列是：（）ABDCEFGHA
6、、ABCDEFGHB、BDAFEHGCC、DBFHGECAD、HGFEDCBA1.邻接表是图的一种（）。A、顺序存储结构B、链式存储结构C、索引存储结构D、散列存储结构2.给定有向图如右图所示，则该图的一个强连通分量是：（）。A、{A,B,C,F}B、{B,C,F}C、{B,C,D,F}D、{C,D,E,F}3.已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该：A、将邻接矩阵的第i行删除B、将邻接矩阵的第i行元素全部置为0C、将邻接矩阵的第i列删除D、将邻接矩阵的第i列元素全部置为0三、判断题1.（）非线性数据结构
7、可以顺序存储，也可以链接存储。2.（）非线性数据结构只能用链接方式才能表示其中数据元素的相互关系。3.（）完全二叉树一定是满二叉树。4.（）在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。5.（）若一棵二叉树的任意一个非叶子结点的度为2，则该二叉树为满二叉树。6.（）度为1的有序树与度为1的二叉树是等价的。7.（）二叉树的先序遍历序列中，任意一个结点均排列在其孩子结点的前面。8.（）已知一棵二叉树的先序序列和后序序列，就一定能构造出该二叉树。9.（）在霍夫曼树中，权值最小的结点离根结点最近。10.()对任意一个图，从它的
8、某个顶点出发进行一次深度优先或广度优先遍历可访问到该图的每个顶点。11.（）线性数据结构可以采用顺序存储结构或链式存储结构，而非线性数据结构只能采用链式存储结构。12.（）二叉树中的叶子结点就是二叉树没有左、右子树的结点。13.（）如
