GESP-C++六级 题库
假设字母表 {a,b,c,d,e} 在字符串出现的频率分别为 10%,15%,30%,16%,29%。若使用哈夫曼编码方式对字母进行二进制编码,则字符 abcdef 分别对应的一组哈夫曼编码的长度分别为( )。(2024.9-6)
以下C++代码实现 n nn 位的格雷码,则横线上应填写( )。
格雷码(Gray code)是一种相邻两个代码之间只有单个比特不同的二进制数字系统。要生成n位的格雷码,可以通过迭代的方式生成更长的格雷码序列。在这段代码中,首先生成了1位的格雷码,即"0"和"1"。然后通过迭代,每次都将现有的格雷码列表翻倍,并且在新加入的格雷码前加上不同的前缀来保证相邻格雷码之间的差异性。在每一轮迭代中,首先将现有的格雷码序列反转并加上前缀"1",然后原有的格雷码序列加上前缀"0"。
仔细观察,可以看到第一个循环是从末尾向前遍历,将’1’添加到现有元素的前面。这意味着,对于第二个循环,我们应该从头部开始遍历,同样将’0’添加到现有元素的前面,所以选B而不是选A。
给定一棵二叉树,其前序遍历结果为:ABDECFG,中序遍历结果为:DEBACFG,则这棵树的正确后序遍历结果是( )。(2024.9-6)
在前序遍历中找根,在中序遍历中找根的左右子树,建好树后进行后序遍历。
一棵有 n 个结点的完全二叉树用数组进行存储与表示,已知根结点存储在数组的第 1 个位置。若存储在数组第 9 个位置的结点存在兄弟结点和两个子结点,则它的兄弟结点和右子结点的位置分别是( )。(2024.9-6)
完全二叉树兄弟结点一般是左偶右奇,9号结点的兄弟结点只能是8号,而右子结点即9*2+1 = 19,选C
二叉树的深度定义为从根结点到叶结点的最长路径上的结点数,则以下基于二叉树的深度优先搜索实现的深度计算函数中横线上应填写( )。
代码的思路是计算出当前根结点左子树的深度,右子树的深度,那么以根结点为子树的深度即max(左子树,右子树)+1,+1即将根结点的深度也计算在内,所以选C。
上一题的二叉树深度计算还可以采用二叉树的广度优先搜索来实现。以下基于二叉树的广度优先搜索实现的深度计算函数中横线上应填写( )。
二叉搜索树中的每个结点,其左子树的所有结点值都小于该结点值,右子树的所有结点值都大于该结点值。以下代码对给定的整数数组(假设数组中没有数值相等的元素),构造一个对应的二叉搜索树,横线上应填写():
对上题中的二叉搜素树,当输入数组为[5,3,7,2,4,6,8] 时,构建二叉搜索树,并采用如下代码实现的遍历方式,得到的输出是( )。
根据输入数组建BST,然后根据 “左根右”的遍历规则输出为: 2 3 4 5 6 7 8,选B
动态规划通常用于解决( )。(2024.9-6)
一个问题是否能用DP来解决我们的考虑一般有两点:① 最优子结构,②无后效性
最优子结构即 选项中B的可分解成相互依赖的子问题的问题,因此选B。
阅读以下用动态规划解决的0-1背包问题的函数,假设背包的容量 W 是10kg,假设输入4个物品的重量weights 分别为1,3,4,6(单位为kg),每个物品对应的价值values 分别为20,30,50,60,则函数的输出为( )。
01背包问题,dp[n][w]表示将前n个物品放入容量为w的背包中得到的最大价值,4个物品的重量为1 3 4 6,价值为20 30 50 60,背包容量为10,最大价值是1 3 6 对应的110。
面向对象的编程思想主要包括( )原则。
面向对象的编程思想(OOP)主要包括多态、继承和封装原则。
多态:多态允许程序在运行时根据对象的实际类型来选择执行的方法,增加了代码的灵活性和可扩展性。
继承:通过继承,子类可以扩展父类的功能,而不需要重新编写已有的代码,提高了代码的复用性和维护性。
封装:封装隐藏了对象的内部状态,只提供必要的操作接口,保护对象数据不被外部直接访问,同时确保了数据的安全性和完整性。
这些原则共同构成了面向对象编程的核心,使得代码更加模块化、可重用、可维护和可扩展
运行下列代码,屏幕上输出( )。
构造函数my_class()在对象obj实例化时自动调用,静态局部变量count在程序执行到该对象的声明处时被首次初始化为0,在以后的函数调用不再进行初始化;因此后续调用print_count()方法时,输出count依次自增的结果,程序输出结果为1 2 3,另外析构函数~my_class()会在对象结束调用时做“清理善后” 的工作,即程序结束时,会自动调用三次~my_class()方法,因此最终程序结束时,count的值为0。
运行下列代码,屏幕上输出( )。
主函数实例化两个对象rectangle rec 和triangle tri,pshape调用rec的area()方法,输出了rectangle area:,之后pshape调用tri的area()方法,输出了triangle area:
向一个栈顶为hs的链式栈中插入一个指针为s的结点时,应执行( )。
指针之间的赋值:A=B可以理解为A指向B,栈的结构为先进后出,因此S需要作为栈顶存在,hs需要指向S,即hs=s;但是在此之前,需要将S链接到hs,即S的下一个指针指向S,有S->next=hs;
在栈数据结构中,元素的添加和删除是按照什么原则进行的?
栈的元素添加原则为先进后出(后进先出)。
要实现将一个输入的十进制正整数转化为二进制表示,下面横线上应填入的代码为( )。
如果对十进制X进行拆位:每次用%10取得最低位,同时/10去除最低位,用栈即可得到从个位到高位的各个位,不停弹出即可正常输出十进制的每一位,这个过程可以理解为将十进制转化为二进制,如果将%10 /10 改为%2 /2,那么这就相当于将十进制转化为二进制。
代码中ten2bin()就是拆分各个位并返回栈st,bin接收值后,按照栈的弹出规则依次输出即可,因此答案选B.
下面定义了一个循环队列的类,请补全判断队列是否满的函数,横向上应填写( )。
判断循环队列是否为满可以让队列的rear指针加1之后对capacity取模结果等于front指针,这时表明队列已满,反之则未满。
对“classmycls”使用哈夫曼(Huffman)编码,最少需要( )比特。
按照哈夫曼编码规则进行建树,如图,按照左0右1的二进制格式编码,可以得到每个字符的编码:
length©=length(S)=length(L)=2,length(A)=3,length(Y)=length(M)=4
经过计算可以得到classmycls的总长=2+2+3+2+2+4+4+2+2+2=25。
二叉树的( )第一个访问的节点是根节点。
先序遍历先根再左子树再右子树,中序遍历先左子树再根再右子树,后序遍历先左子树再右子树再根。
一棵5层的满二叉树中节点数为( )。
一个K层的满二叉树的节点个数为1+2+4+……+2k-1=2k-1 (等比数列/二进制)。