数据结构 C 语言版复习资料 2数据结构 C 语言版复习资料 2一、选择题1.以下数据结构中哪一个是非线性结构？(B)A. 队列B. 二叉树C. 栈D. 线性表2.设输入序列为 1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为(B)。A. 5，6，3，4，1，2C. 3，1，2，6，5，4B. 3，2，5，6，4，1D. 1，5，4，6，2，33.设某二叉树中度数为 0 的结点数为 N0，度数为 1 的结点数为 Nl，度数为 2 的结点数为 N2，则下列等式成立的是(C) 。A. N0=N1+1B. N0=Nl+N2C. N0=N2+1D. N0=2N1+l4.设某棵二叉树中有 1000 个结点，则该二叉树的最小高度为(B)。A．9B. 10C. 11D. 125、在一棵具有 4 层的满二叉树中结点总数为（ A）。A. 15B. 16C.17D. 326、设一棵二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树先序遍历序列为（ D）。A. adbceB. decabC. debacD. abcde7.设有 8 个结点的无向图，该图至少应有(C)条边才能确保是一个连通图。A. 5B. 6C. 7D. 88.设无向图 G 中有 n 个顶点 e 条边，则其对应的邻接表中的表头结点和表结点的个数分别为(C)。A. n，eB. 2n，eC. n，2eD. e，n9.设无向图 G 中的边的集合 E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点 b 出发进行深度优先遍历可以得到的一种顶点序列为(A) 。A. bacfdeB. becfadC. bacedfD. beafdc二、填空题1.数据元素之间的逻辑结构有四种基本类型，分别是集合、线性、树形结构和网状结构。1 / 6数据结构 C 语言版复习资料 22.数据元素之间的存储结构有两种基本类型，分别是顺序存储结构和链式存储结构。3.设输入序列是 1、2、3、……、n，经过栈的作用后输出序列的第一个元素是 n，则输出序列中第 i 个输出元素是n-i+1。4.设入栈序列为 7、3、4、8，则通过栈的作用后可以得到的出栈序列为 8、4、3、7。5.深度为 k 的二叉树中最少有k个结点，最多有2k-1个结点。6.二叉树的第 i 层最多有2i-1个结点。7.树中的一个节点拥有的子树数称为该节点的度。一棵树的度是指该树中节点的度的最大值，度为零的节点称为叶结点，度不为零的节点称为分支结点。8.设有 n 个结点的完全二叉树，如果按照从自上到下、从左到右从 1 开始顺序编号，则第i 个结点的双亲结点编号为i/2，左孩子结点的编号为2i。9、哈夫曼树是其树的带权路径长度最短的二叉树。10、树内各结点度的度的最大值称为树的度。11....
