数据结构题库(7)

第四章数组和串

1．二维数组和多维数组均不是特殊的线性结构。（√）

2．稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（√） 3．数组元素的引用与队列结构有关联（×）

4．字符串，是一串文字和符号的序列（√） 5．字符串简称为串，是Ｎ个字符的一个有限序列（√） 6．分空串和空格串是相同的。（×）

7． 数组元素的下角标越大，存取时间越长。（×）

8． 对一些特殊矩阵采用压缩存储的目的主要是为了去掉矩阵中的多余元素。（×） 9．数组的存储结构是一组连续的内存单元。（√） 10．一维数组中的数组元素都是线性结构（×）

11．对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的行下标、列下标、和非零元素值三项信息。（√）

12．子串是主串中任意个连续字符组成的序列。（√） 13.数组的基本运算有读、写、插入、删除等。（错误）

第五章树

1．若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。（√）

2．二叉树中每个结点的两棵子树的高度差等于1。（×） 3．二叉树中每个结点的两棵子树是有序的。（√） 4．二叉树中每个结点有两棵非空子树或有两棵空子树。（×）

5．二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。（×） 6．二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2i-1）（×） 7．二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。（×） 8．对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。（×）

9．用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。（√）

10．具有12个结点的完全二叉树有5个度为2的结点。（√）

输入到此处

11．向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（×）

12．若一棵二叉树中的结点均无右孩子，则该二叉树的中序遍历和后序遍历序列正好相反。（×）

13．对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(n)。（√）

14．存在这样的二叉树，对它采用任何次序的遍历，结果相同。（√）

15．在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和中序遍历时具有相同的结果。（×） 16．若已知一棵二叉树的前序遍历序列和后序遍历序列，则可以恢复该二叉树。(×) 17．二叉树的后序遍历序列中，任意一个结点均处在其孩子结点的后面。（√) 18．无序树中结点的各子树之间的次序是很重要的，不能相互交换位置。（×） 19．二叉树只能用二叉链表表示（×）

20．树中每对结点至少存在一个共同的祖先.（×） 21．二叉树的存储表示只有顺序存储表示一种。（×） 22．利用后序遍历销毁一颗二叉树时，算法首先销毁根的左子树和右子树，然后再释放根结点。（√）

23．二叉链表和三叉链表可以是静态链表结构。（√）

24．二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。（√） 25．在二叉树中至少有一个结点的度是2。（×）

26．一个二叉树，前序遍历为ABDEF,则它的中序遍历为DEBAFC。（×) 27．用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（×） 28．堆排序是一种插入排序（×） 29．二叉树就是结点的度为均2的树。（╳） 30．赫夫曼树一定是满二叉树。（╳） 31．赫夫曼树一定是完全二叉叉树。（╳）

32．二叉树中每个结点的两颗子树是有序的。（√）

33．完全二叉树的某结点若无左孩子，则它必是叶结点。(√） 34．满二叉树一定是完全二叉树。（√）

35．把树转换成二叉树，其根结点的右子树总是空的。（√） 36．后序遍历和中序遍历与该树对应的二叉树，其结果不同。（√） 37．在哈夫曼树中，权值最小的结点离根结点最近。（×）

38．二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。（×）

39．删除一个二叉树中的一个结点，再重新插入上去，一定能得到原来的二叉排序树。（×） 40．在一个非空二叉树的中序序列中，根结点的右边只有左子树上的所有结点。（×） 41．由二叉树的前序遍历序列和中序遍历序列?可以推导出该二叉树的后序遍历的序列。(√)

42．具有n个叶子结点的哈夫曼树共有2n-1个结点。(√)

43．设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（×） 44．满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（√） 45．完全二叉树中的叶子结点只可能在最后两层中出现。（√） 46．树的遍历方式有两种：深度优先遍历和广度优先遍历（√）

47．设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有13个结点。（根所在结点为第1层（×）

48．高度为K的满二叉树是有2^k-1个结点的二叉树。（√）

49．二叉树的特点是每个结点最多有两个子女，分别称为该结点的左子女和右子女。（√） 50．在二叉排序树中删除一个节点时，必须将因删除结点而断开的二叉链表从新链接起来，同时确保二叉排序树的性质不会失去。（√）

51．深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。（√）套题五 52．任意一个非空树中有且仅有一个结点没有双亲结点。（√）

53．假设有一棵结点为112个的树，那么这棵树一定有112条边。 （ × ） 54．根据二叉树的定义，二叉树的每一个节点必须有两个分支。（×） 55．堆肯定是一棵平衡二叉树。（ 错 ） 56．堆是满二叉树（×）

57．（101，88，46，70，34，39，45，58，66，10）是堆。（对）

第六章图

1．如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（√）

2．图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。（√）

3．具有n个结点的连通图至少有n条边。（×）

4．对于任意一个图，从它的某个结点进行一次深度或广度优先遍历可以访问到该图的每个顶点。（×）

5．在n条边的无向图，在邻接表中有n个结点。（×） 6．强连接图的每个顶点间均可达。(√）

7．不同的求最小生成树的方法最后得到的最小生生成树是相同的。（×） 8．如果有向图中各个顶点的度都大于2，则该图中必有回路。（×） 9．对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是完全图。（×）

10．图的深度优先搜索和广度优先搜索序列不一定是唯一的。（√） 11．用邻接矩阵法存储一个图时在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关（√）

12．图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。(√ ) 13．边数很少的稀疏图，适宜用邻接矩阵表示。（× ） 14．边数很少的稀疏图，适宜用邻接表表示。（ √ ） 15．强连通图的各顶点间均可达。（ √ ）

16．强连通分量是有向图中的极大强连通子图。(√ ) 17．一个无向连通图的生成树是图的极小的连通子图。（√ ）

18．如果无向图中每个顶点的度都大于等于2，则该图中必有回路。(√) 19．存储无向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下（上）三角部分。( √) 20．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。（ √ ） 21．邻接多重表是无向图的一种链式存储方法。（对） 22．任何有向网络（AOV网络）拓扑排序的结果是唯一的。（错） 23．有回路的图不能进行拓扑排序。（对） 24．AOE网中一定只有一条关键路径。（错） 25．连通分量是无向图中极小连通子图。（错）

26．对任何图，执行一次深度优先或广度优先遍历后，就可访问到图中所有节点。（错误）

27．设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m 有m=2e关系 ( 对 )

28．设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素 之和等于顶点i的出度，第i列上所有元素之和等于顶点i的入度。( 对 )

29．设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的 关系为e=d ( 对 )

30．在n个结点的无向图中，若边数大于n-1，则该图必是连通图。（）× 套题三 31．有e条边的无向图，在邻接表中有e个结点。（）×

32．有向图中顶点V的度等于邻接矩阵中第V行中的1的个数。（）× 33．强连通分量是无向图的极大强连通子图。（）√ 34．连通分量指的是有向图中的极大连通子图。（）×

35．临接多重表是无向图和有向图的链式存储结构。（）× 36．无向图的邻接矩阵可用一维数组存储。（）×

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构题库(7)在线全文阅读。