数据结构选择题答案及相关知识点

1、1、在一棵具有 5 层的满二叉树中结点总数为（A ）。A) 31B）32C） 33D）16(2n) - 1,N = 2 k-1(N 总结点数， k 层数 )2、串的逻辑结构与（A ）的逻辑结构不相同。A）线性表B）栈C）队列D）集合串的逻辑结构和线性表极为相似， 区别仅在于串的数据对象约束为字符集。P713、下列序列中，执行第一趟快速排序后得到的序列是（A）。A） d,a,e,d,bfh,gB) c,e,a,dfh,g,bC) g,a,e,c,bfd,hD) a,b,c,d,fe,g,h左大右小4、n 个顶点的强连通图至少有（C ）条边。A） nB）n+1C）n-1D）n(n-1)单节点除外，

2、 so,-15、设单链表中指针 p 指着结点 A，若要删除 A 之后的结点（若存在），则需要修改指针的操作为（ A ）。A） p-next=p-next-next B） p=p-nextC） p=p-nexe-nextD） p-next=p无限删除6、对下图 V4 的度为（C ）。A）1B ）2C ）3D ）4v1v2v3v47、在一棵度为 3 的树中，度为 3 的结点个数为 2，度为 2 的结点个数为 1，则度为 0 的结点个数为（ C ）。A）4B）5C）6D）7图 1-7设度为 0 的结点 个数为 n0 ，度为 1 的结点 个数为 n1 ，度为 2 的结点 个数为 n2，度为 3 的个数

3、 n3树中结点总数n0+ n1 + n2 + n3 ，所有边的数量为0 * n0 + 1 * n1 + 2 * n2 +3 * n3树中结点比边多1 个，合并这两个式子就可以得到：n0 = 1 + n2 + 2 * n38、在数据结构中，从逻辑上可以把数据结构分为（C ）。A）动态结构和静态结构B）紧凑结构和非紧凑结构C）线性结构和非线性结构D）内部结构和外部结构数据的逻辑结构 分两大类：线性结构和 非线性结构数据的存储方法 有四种： 顺序存储方法、 链接存储方法、 索引存储方法 和散列存储方法 ( hash 存储 )9、用一维数组 A 进行顺序存储时，若起始地址为loc(A1) ，元素长度为

4、c，则 A 的第 i个数组单元在存放地址loc(Ai)，等于（B）。A）loc(A1)+i*cB）loc(A1)+(i-1)*cC）loc(A1)+i*c+1D）loc(A1)+(i+1)*c10、（ C ）在进行插入操作时，常产生假溢出现象。A）顺序栈B）循环队列C）顺序队列D）链队列循环队列产生是为了解决顺序队列的假溢出11、下列各种数据结构中属于线性结构的有（A ）。A）栈B)二叉树C) 广义表D)图数据元素之间的关系称为结构 ：1. 集合； 2. 线性结构； 3.树形结构； 4. 图 / 网状结构12、倘若在对串的插入、删除运算中，期望运算速度最快，则应采用（B ）。A）顺序表示法B）

5、单字符为结点的单链表表示法C）等量分块表示法D）不等量分块表示法13、广义表 head(a,b),(c,d)的运算结果为（D）。A） (a,b)B）(c,d)C）空表D）（ a,b ）,(c,d)）14、n 个顶点的图的最小生成树必定 （D），是不正确的描述。A）不唯一B）权的总和唯一C）不含回路D）有 n 条边15、采用链结构存储线性表时，其地址（B）。A）必须是连续的B）连续不连续都可以C）部分地址必须是连续D）必须是不连续的16、队列的操作的原则是（A）。A）先进先出B)后进先出C) 只能进行插入D)只能进行删除U字走法，不是 Y17、设给定问题的规模为变量n，解决该问题的算法所需时间为

6、Tn=O(f(n),Tn 表示式中记号O表示（A）。A）一个数量级别B）一个平均值C）一个最大值D）一个均方值18、线性表的链接实现有利于（A）运算。A）插入B）读元素C）查找D）定位20、下面程序段的时间复杂度是(A ) 。s =0;for( i =0; in; i+)for(j=0;jLchild=NullB) D-ltag=1C) D-Rchild=NullD) D-ltag=0L Tag0 lchild域指示节点的左孩子 ;1 lchild域指示节点的前驱 R tag0 rchild域指示节点的左孩子 ;1 rchild域指示节点的前驱 没有前趋结点并没有左子树就没有左孩子，通常没有头

7、结点的情况下，中序遍历的第一个结点就满足条件。29、栈进行插入和删除操作的特点是（A）。A） LIFOB） FIFOC） FCFSD） HPFLIFO = “last in first out”30、与无向图相关的术语有（C）。A）强连通图B ）入度C）路径D ）弧32、若采用邻接矩阵法存储一个 n 个顶点的无向图，则该邻接矩阵是一个（ D ）。A）上三角矩阵B)稀疏矩阵C) 对角矩阵D)对称矩阵34、栈进行插入和删除操作的特点是（A）。A） LIFOB） FIFOC） FCFSD） HPF39、在循环队列中，若 front 与 rear 分别表示对头元素和队尾元素的位置，则判断循环队列空的条

8、件是 ( C ) 。A）front=rear+1B）rear=front+1C）front=rearD）front=0此时我们约定：少用一个元素，“队列头指针在队列尾指针的下一位置”作为队列呈“满”状态的标志。43、在有 n 个叶结点的哈夫曼树中其结点总数为： （D）。（ A ）不确定（ B ）2 n（ C） 2 n + 1（ D） 2 n 1无论哈夫曼树是几叉，其特点是一致的（假设为m 叉），即树中只存在度为 0 的结点（即叶结点） 和度为 m 的结点。不妨设度为 0 的结点个数为 x，度为 m 的结点个数为 y，则存在一个等式 x+y=my+1 ，即 x=(m-1)y+1 ，x+y是树的总

9、结点个数。就这道题来说，假设哈夫曼树是二叉的话，则度为0 的结点个数为N，度为 2 的结点个数为N-1 ，则结点总数为2N-1 。44、（C）在进行插入操作时，常产生假溢出现象。A）顺序栈B）循环队列C）顺序队列D）链队列1-10 这个要记一下 , 重复就重复48、某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为： (C )A）3B）2C）4D） 5后序最后一个为根节点49、在数据结构中假定在一棵二叉树中， 度为 2 的结点数为 15 个，度为 1 的结点数为 32 个，则叶子结点数为（B）个。A）15B）16C）17D）47每个分枝下面都有一个结点，所

10、以总结点数N=2*15+1*32+0*叶子数 +1( 根节点） =63二叉树中除了双分支结点，单分支结点就是叶子结点。所以叶子数 =63-15-32=16.50、树最适合用来表示 (C )。A）有序数据元素B）无序数据元素C）元素之间具有分支层次关系的数据D）元素之间无联系的数据51、在顺序存储结构的线性表中第 i 个元素 (1=inext =NULLC）head-next =headD）head!=NULL61、二维数组 A33 按行优先顺序存储， 若数组元素 A11 的存储地址为 1087，A22 的存储地址为1095，则数组元素A00的存储地址为（A）。A ）1079B）1080C）10

11、78D）1060（1095-1087）/4 =2； A00 = A11 -8 = 107962、在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（A）A）队列B）栈C）线性表D）有序表63、对线性表进行折半查找时，要求线性表必须（B）。A ）以顺序方式存储B）以顺序方式存储，且结点按关键字有序排列C）以链式方式存储D）以链式方式存储，且结点按关键字有序排列64、节点的带权路径是指从根节点到该节点的路径长度乘以该节点的权值，树的带权路径长度是指树中所有叶子节点的带权路径长度之和，已知叶子节点a,b,c 的权分别是 2,5,7左边给出的树的带权路径长度为（A ）A）21B） 14cC）22D）

12、28(2+5)*2+7=21ab65、对一棵有 n 个节点的二叉树按上述方法对节点进行编号，如果编号为 i(inext = NULLB）p = NULLC）p-next =headD）p = headAB68、设无向图的邻接链表如图所示， 则该图的边的数目是（）ABCD(1) 完全二叉树 只有最下面的两层结点度小于 2 ，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树；(2) 满二叉树 除了叶结点外每一个结点都有左右子叶且叶结点都处在最底层的二叉树 ,。(3) 平衡二叉树 一棵空树或左右两个子树的高度差的绝对值不超过 1 ，并且左右两个子树都是一棵平衡二叉树。66、若用邻接矩阵表示一

13、个有向图，则其中每一列包含的 1的个数为（ B ）。A ）图中每个顶点的入度B）图中每个顶点的出度A） 4B）5C） 10D）20VV69、下面的算法中（A）是用来构造最小生成树的算法。A ）普里姆（ Prim）算法B ） 迪 杰 斯 特 拉（ Dijkstra ）算法VVC）弗洛伊德（Floyd ）算法D）拓扑排序B:是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。C: 是一种用于寻找给定的加权图中多源点之间最短路径的算法。D: 对一个有向无环图G 进行拓扑排序，是将G 中所有顶点排成一个线性序列，使得图中任意一对顶点u 和 v，若边 +-(u,v) E(G) ，则 u 在线性序列中出现在v 之前。70、设有一个栈，元素依次进栈的顺序为A 、B、 C、D、E。下列 (C)是不可能的出栈序列。A ）A,B,C,D,EB）B,C,D,E,AC）E,A,B,C,DD）E,D,C,B,A71、若有序表的关键字