数据结构(c)第一章复习题.pdf_在线真题试卷与模拟练习_数据结构(c)第一章复习题.pdf_考试宝

更新时间：试题数量：购买人数：提供作者：

有效期：个月

章节介绍：共有个章节

收藏

我的练习

我的错题
(0道)

我的收藏
(0道)

我的斩题
(0道)

我的笔记
(0道)

专项练习

顺序练习 0 / 0

随机练习 自定义设置练习量

题型乱序 按导入顺序练习

模拟考试 仿真模拟

题型练习 按题型分类练习

易错题 精选高频易错题

学习资料 考试学习相关信息

搜索

题库预览

给定权值集合 {15, 03, 14, 02, 06, 09, 16, 17}, 构造相应的赫夫曼树 , 1 2

3 6 5 C3 C8 C5 C6 C1 C4 C2 C7 1 11 1 1 1 1 对两个字符编码为 0 和 10 外，还可以最多对__4 __个字符编码。 (8) 设二叉树有 n个结点且根结点处于第 1层，则其高度为（不确定）。 (9) 设高度为 h二叉树只有度为 2和度为0的结点，则该二叉树中所含结点至少有（ 2h -1 ）个。 (除第一层之外，每层都有 2个结点) (10) 设森林F中有4棵树，第 1、2、3、4棵树的结点个数分别为n1、n2、n3、n4，当把森林 F转换成一棵二叉树后，其根结点的右子树中有（ n2+n3+n4 ）个结点。 (11) 设森林F中有4棵树，第 1、2、3、4棵树的结点个数分别为n1、n2、n3、n4，当把森林 F转换成一棵二叉树后，其根结点的左子树中有（ n1-1 ）个结点。 (12) 将含有 82 个结点的完全二叉树从根结点开始顺序编号，根结点为第 0 号，其他结点自上向下，同一层自左向右连续编号。则第40号结点的双亲结点的编号为（ 19 ）。（编号为 i 的结点，左孩子编号 2i+1，右孩子 2i+2）（13）高度为 h的完全二叉树最少有 2 h-1 个结点。（第h层只有一个结点）（14）某二叉树结点的中序序列为 A、B、C、D、E、F、G，后序序列为B、D、C、A、F、G、E，则其左子树中结点数目为： (　　)

下面是一个使用栈 stack实现对二叉树进行非递归先根遍历的函数 , 请在标号处填写合适的语句。程序: Void preorder(bitree *T) {bitree *stack[m]; int top; if(T!=NULL) {top=1; stack[top]=(1); while( (2) ) {p=stack[top]; top--; printf(“%d”,p->data); if(p->rchild!=NULL){ (3) ; stack[top]=p->rchild;} if( (4) ) { top++; (5) ;} } } } (1) T (2) top>0 (3) top++ (4) p->lchild!=NULL (5) stack[top]=p->lchild 第六章习题⼀、选择题（1）在⼀个⽆向图中，所有顶点的度数之和等于图的边数的（）倍。（2）在⼀个有向图中，所有顶点的⼊度之和等于所有顶点的出度之和的（）倍。（3）具有 n 个顶点的有向图最多有（）条边。（4）n 个顶点的连通图⽤邻接矩阵表示时，该矩阵⾄少有（）个⾮零元素。（5）G 是⼀个⾮连通⽆向图，共有 28 条边，则该图⾄少有（）个顶点。（6）若从⽆向图的任意⼀个顶点出发进⾏⼀次深度优先搜索可以访问图中所有的顶点，则（7）下⾯（）适合构造⼀个稠密图(　　)的最⼩⽣成树。（8）⽤邻接表表示图进⾏⼴度优先遍历时，通常可借助（）来实现算法。（9）⽤邻接表表示图进⾏深度优先遍历时，通常可借助（）来实现算法。（10）图的深度优先遍历类似于⼆叉树的（）。（11）图的⼴度优先遍历类似于⼆叉树的（）。（12）图的 BFS ⽣成树的树⾼⽐ DFS ⽣成树的树⾼（）。（13）已知图的邻接矩阵如图 6.30 所示，则从顶点 v0出发按深度优先遍历的结果是（）。（14）已知图的邻接表如图 6.31 所示，则从顶点 v0出发按⼴度优先遍历的结果是（（15）下⾯的（）⽅法可以判断出⼀个有向图是否有环。（1）已知图 6.32 所示的有向图，请给出：（2）已知如图 6.33 所示的⽆向⽹，请给出：（3）已知图的邻接矩阵如图 6.34 所示。试分别画出⾃顶点 1 出发进⾏遍历所得的深度优先（5）试对图 6.36 所示的 AOE-⽹：① 求这个⼯程最早可能在什么时间结束；② 求每个活

设散列表为 HT[13], 散列函数为(　　)(key) = key %13。用下列方法解决冲突 , 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。 (1) 采用线性探测再散列法寻找下一个空位 , 画出相应的散列表 , (2) 采用再哈希法寻找下一个空位 ,再哈希函数为 RH (key) = (7*key) % 10 + 1, 寻找下一个空位的公式为 Hi = (Hi-1 + RH (key)) %

D12. D13. B14. C15.(　　)数据结构（ Python 版）习题第五章习题⼀、选择题（1）把⼀棵树转换为⼆叉树后，这棵⼆叉树的形态是（）。（2）由 3 个结点可以构造出多少种不同的⼆叉树？ ( ) （3）⼀棵完全⼆叉树上有 1001 个结点，其中叶⼦结点的个数是（）。（4）⼀个具有 1025 个结点的⼆叉树的⾼(　　)为（）。（5）深度为(　　)的满 m 叉树的第 k 层有（）个结点(1≤k≤h)。（6）利⽤⼆叉链表存储树，则根结点的右指针（）。（7）对⼆叉树的结点从 1 开始进⾏连续编号，要求每个结点的编号⼤于其左、右孩⼦的编号，同⼀结点的左右孩（8）在⼀棵度为 4 的树 T 中，若有 20 个度为 4 的结点，10 个度为 3 的结点，1 个度为 2 的结点， 10 个度为

解答（1）每个顶点的⼊度和出度如图 6.28(　　)所示；（2）邻接矩阵如图 6.28(　　)所示；（3）邻接表如图 6.28(　　)所示；（4）逆邻接表如图 6.28(　　)所示。顶点 123456 ⼊度 321122 出度022313 1 2● 3● 4● 5● 6● 1● 2● 3● 4● 5● 6●

01 68 27 192084 23 第七章习题⼀、选择题（1）对 n 个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找⻓度为（）。（2）适⽤于折半查找的表的存储⽅式，以及元素排列要求为（）。（3）如果要求⼀个线性表既能较快的查找，⼜能适应动态变化的要求，最好采⽤ ( )查找法。（4）折半查找有序表（ 4, 6, 10, 12, 20, 30, 50, 70, 88, 100）。若查找表中元素 58，则它将依次与表中（5）对 22 个记录的有序表作折半查找，当查找失败时，⾄少需要⽐较（）次关键字。（6）折半查找与⼆叉排序树的时间性能（）。（7）分别以下列序列构造⼆叉排序树，与⽤其他三个序列所构造的结果不同的是（）。（8）在平衡⼆叉树中插⼊⼀个结点后造成了不平衡，设最低的不平衡结点为 A，并已知(　　)的左孩⼦（9）下列关于 m 阶 B-树的说法错误的是（）。（10）下⾯关于 B-和(　　)+ 树的叙述中，不正确的是（）。（11）m 阶 B-树是⼀棵（）。（12）下⾯关于散列查找的说法，正确的是（）。（13）下⾯关于散列查找的说法，不正确的是（）。（14）设散列表⻓为 14，散列函数是 H(key) = key%11，表中已有数据的关键字为 15, 38, 61, 84 共四个（15）采⽤线性探测法处理冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上（1）假定对有序表：（3, 4, 5, 7, 24, 30, 42, 54, 63, 72, 87, 95）进⾏折半查找，试回答下列问题。

3 14 02 06 09 16 17

在哈夫曼树中，权值最小的结点离根结点最近。（5）将一棵树转换为二叉树表示后 ,该二叉树的根结点一定没有右

通常是以算法执行所耗费的（时间）和所占用的（空间）来判断

算法具有输入、输出、（确定性）、有穷性和可执行性等特性。