数据结构题

《数据结构题》由会员分享，可在线阅读，更多相关《数据结构题（9页珍藏版）》请在金锄头文库上搜索。

1、0 第六章树和二叉树 简答题 1、有一棵树的括号表示为 A(B,C(E,F(G),D),回答下面的问题： 这棵树的根结点是谁？ 这棵树的叶子结点是什么？ 结点 C 的度是多少？ 这棵树的度是多少？ 这棵树的深度是多少？ 结点 C 的孩子结点是哪些？ 结点 C 的双亲结点是谁？ 2、若一棵度为 4 的树中度为 1,2,3,4 的结点个数分别是 4,3,2,2，则该树中叶子结点的 个数是多少？总结点个数是多少？ 3、一棵高度为 h 的完全 k 次数，如果按照层次自上向下、自左向右的顺序从 1 开始对全 部结点编号，试问： 最多有多少个结点？最少有多少个结点？ 编号为 q 的结点的第 i 个孩子结点

2、的编号是多少？ 4、若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点个数为 结点的总个数为 5、一棵完全二叉树有 1001 个结点，其中叶子结点的个数为 6、一棵高度为 h 的完全二叉树至少有 个结点。 7、一棵高度为 5 的完全二叉树至多有 个结点。 8、设高度为 h 的二叉树上只有度为 0 和度为 2 的结点，则此类二叉树至少包含 个 结点。 9、一个具有 1025 个结点的二叉树的高度 h 为 10、在一棵完全二叉树中，结点个数为 n，则编号最大的分支结点的编号为 11、一棵二叉树的先序遍历为 ABCDEF，中序遍历为 CBAEDF，则后序遍历为 1

3、2、一棵二叉树的先序遍历为 ABCDEFG，它的中序遍历可能为 A.CABDEFG B. ABCDEFG C.DACEFBG D.ADCFEGB 思考：二叉树的先序和中序遍历相同的条件是？ 二叉树的后序和中序遍历相同的条件是？ 13、一棵二叉树的后序遍历为 DABEC，中序遍历为 DEBAC，则先序遍历为 14、一棵二叉树的先序遍历为 EFHIGJK，中序遍历为 HFIEJKG，则该二叉树根结点的右孩 子为 16、根据使用频率为 5 个字符设计的赫夫曼编码不可能的是 A.111,110,10,01,00 B.000,001,010,011,1 C.100,11,10,1,0 D.001,000

4、,01,11,10 17、根据使用频率为 5 个字符设计的赫夫曼编码不可能的是 A. 000,001,010,011,1 B.0000,0001,001,01,1 C. 000,001,01,10,11 D.00,100,101,110,111 18、设有 13 个值，用它们组成一棵赫夫曼树，则该赫夫曼树共有 个结点。 19、若以4,5,6,7,8作为叶子结点的权值构造赫夫曼树，则其带权路径长度是 ，各结点对应的赫夫曼编码为 1 20、以数据集2,5,7,9,13为权值构造一棵赫夫曼树，并计算其带权路径长度。 21、一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来，试求出 空格

5、部分的内容，并画出二叉树。 先序遍历 B F ICEH G 中序遍历 D KFIA EJC 后序遍历 K FBHJ G A 15、如图所示的二叉树 T2 是由森林 T1 转换而来的二叉树，那么森林 T1 有 叶子 结点。 GJI H F D C EB A 第七章 图 1.在一个无向图中,所有顶点的度数之和等于所有边数的 倍。 A.1/2 B.1 C.2 D.4 2.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和 的 倍。 A1/2 B.1 C.2 D.4 3.一个有 n 个顶点的无向图最多有 条边。 A.n B.n(n-1) C.n(n-1）/2 D.2n 4.具有 4 个顶点的无向

6、完全图有 条边。 A.6 B.12 C.16 D.20 5.具有 6 个顶点的无向图至少应有 条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 6.在一个具有 n 个顶点的无向图中,要连通全部顶点至少需要 条边。 A.n B.n+1 C.n-1 D.n/2 7.在有 n 个顶点的有向图中，每个顶点的度最大可达 8.对于一个具有 n 个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小 A.n B.(n-1)2 C.n-1 D.n2 9.对于一个具有 n 个顶点和 e 条边的无向图,若采用邻接表表示,则表头向量的大小为 ，所有邻接表中的结点总数是 。 10. 采用邻接表存储的图的深度优先

7、遍历算法类似于二叉树的 。 2 A.先序遍历 B.中序遍历 C.后序遍历 D.按层遍历 11. 采用邻接表存储的图的宽度优先遍历算法类似于二叉树的 A.先序遍历 B.中序遍历 C.后序遍历 D.按层遍历 12.一个有向图 G 的邻接表存储如图，现按深度优先遍历，从顶点 v1 出发，所得到的顶点 序列是 v1 v3 v4 v2 4 5 2 v5 3 5 3 4 13. 一个如图的无向图，从顶点 1 出发进行深度优先遍历， ，可得到的顶点序列是 14. 一个如图的无向图，从顶点 1 出发进行广度优先遍历， ，可得到的顶点序列是 1 3 2 6 5 74 15. 已知图 G 的邻接表存储如图，从顶点

8、 v1 出发，现按深度优先遍历所得到的顶点序列是 ；从顶点 v1 出发，现按广度优先遍历所得到的顶点序列是 3 v1 v3 v4 v2 4 6 2 v5 5 5 3 4 v6 6 3 16.图 G 是一个非连通无向图，共有 28 条边，则该图至少有 个顶点。 17.一个无向连通图的生成树是含有该连通图的全部顶点的 A.极小连通子图 B.极大连通子图 C.极小子图 D.极大子图 18.已知世界 6 大城市：北京 B，纽约 N，巴黎 P，伦敦 L，东京 T，墨西哥 M。试在由表中 给出的交通网确定最小生成树。 BNPLTM B109828121124 N109585510832 P82583979

9、2 L815539589 T211089795113 M124329289113 19.普利姆算法适用于求 的网的最小生成树，克鲁斯卡尔算法适用于求 的网的最小生成树。 20.若一个有向图中顶点不能排列成一个拓扑序列，则可断定该有向图 A.是个有根有向图 B.是个强连通图 C.含有多个入度为 0 的顶点 D.含有顶点数目大于 1 的强连通分量 21.在 AOV 网中，顶点表示 ，有向边表示 22.关键路径是事件结点网络中 A.从源点到汇点的最长路径 B. 从源点到汇点的最短路径 C.最长的回路 D.最短的回路 23. 从源点到汇点的最长路径称关键路径，该路径上的活动称为 24.判定一个有向图是

10、否存在回路除了可以利用拓扑排序方法外,还可以利用 . A求关键路径的方法 B.求最短路径的 Dijkstra 方法 C.宽度优先遍历算法 D.深度优先遍历算法 4 附加上课讲的五个大题。 一、给出邻接表，画图，遍历并分别用普利姆和克鲁斯卡尔算法求最小生成树。 二、给出有向带权图，用 Dijkstra 算法求从某一顶点出发到其他顶点的最短路径，要 求给出求解过程。 三、给出工程的 AOE 网，求完成工程的最短时间，并计算工期。 第九章 查找 1.顺序查找法适合于存储结构为 的线性表。 A.散列存储 B.顺序存储或链式存储 C.压缩存储 D.索引存储 2.顺序查找法的平均查找长度为 ，二分查找法的

11、平均查找长度为 ，分 块查找法(以顺序查找确定块)的平均查找长度为 ，分块查找法(以二分查找确 定块的平均查找长度为 。 3.顺序查找法查找长度为 n 的线性表时，平均比较次数为 4.对线性表进行二分查找时,要求线性表必须 。 A.以顺序方式存储 B.以链接方式存储 C.以顺序方式存储,且结点按关键字有序排序 D.以链接方式存储,且结点按关键字有序排序 5.己知一个有序表为(12,18,20,25,29,32,40,62,83,90,95,98),当二分查找值为 29 和 90 的元素时,分别需要 次和 次比较才能查找成功；若采用顺序查找时,分别需要 次和 次比较才能查找成功。 6.有一个有序

12、表为1,3,9,12,32,41,45,62,75,77,82,95,100,当二分查找值为 82 的结点 时, 次比较后查找成功。 A.1 B.2 C.4 D.8 7.假设在有序线性表 A120上进行二分查找,则比较一次查找成功的结点数为 , 则比较二次查找成功的结点数为 ,则比较三次查找成功的结点数为 ,则 比较四次查找成功的结点数为 ,则比较五次查找成功的结点数为 ,平均 查找长度为 。 8.有一个长度为 12 的有序表,按二分查找法对该表进行查找,在表内各元素等概率情况下查 找成功所需的平均比较次数为 A.35/12 B.37/12 C.39/12 D.43/12 9.设有一个长度为

13、100 的已排好序的表，用二分查找进行查找，若查找不成功，至少比较 次。 A.9 B.8 C.7 D.6 10.在分块查找方法中,首先查找 ,然后再查找相应的 。 11.长度为 225 的表,采用分块查找法,每块的最佳长度是 。 12.在分块查找中，若索引表各块内均用顺序查找，则有 900 个元素线性表分成 块 最好；若分成 25 块，其平均查找长度为 13.在含有 27 个结点的二叉排序树上，查找关键字为 35 的结点，则依次比较的关键字有可 能是 A.28,36,18,46,35 B.18,36,28,46,35 C.46,28,18,36,35 D.46,36,18,28,35 14.如

14、图所示的一棵二叉排序树其查找成功的平均查找长度是 ；其不成 功的平均查找长度是 。 5 62 7430 5615 48 15.在一棵平衡二叉树中，每个结点的平衡因子的取值范围是 。 16.如图所示的 4 棵二叉树， 是平衡二叉树。 62 7430 5615 48 6 17.具有 5 层结点的 AVL 树至少有 个结点。 18.在含有 12 个结点的平衡二叉树上，查找关键字为 35 的结点，则依次比较的关键字有可 能是 A.46,36,18,20,28,35 B.47,37,18,27,36 C.27,48,39,43,37 D.15,45,35 19.在含有 15 个结点的平衡二叉树上，查找关键字为 28 的结点，则依次比较的关键字有可 能是 A.30,36 B.38,48,28 C.48,18,38,28 D.60,30,50,40,38,36 20.一棵深度为 k 的平衡二叉树，其每个非叶子结点的平衡因子均为 0，则该树共有 个结点。 21.查找效率最高的二叉排序树是 。 A.所有结点的左子树都为空的二叉排序树 B.所有结点的右子树都为空的二叉排序树 C.平衡二叉树 D.没有左子树的二叉排序树 22.用二叉排序树查找，在最坏情况下，平均查找长度数量级为 ；当二叉 排序树是一棵平衡二叉树时，ASL 平均查找长度数量级