哈夫曼树的带权路径长度表示什么_哈夫曼树的带权路径长度表示什么

真题笔试解题报告 　　第一行的使得对齐的补齐字节为2。 　　因此union的大小为13+1=14. 　　void foo(){} 不占   ——函数不占用sizeof的内存。 　　typedef char*(*f)(void*); 不占——声明不占用内存 　　 enum{hdd,ssd,blueray}disk; 4个字节—— — 实质上就是整型，所以 size 是 4 　　  　　在动态分区分配方案中,系统回收主存,合并空闲空间时需修改空闲区表,以下哪种情况空闲区会减1?   　　A.只要回收主存,空闲区数就会减一 　　B.空闲区数和主存回收无关 　　C.无上邻空闲区,也无下邻空闲区 　　D.有上邻空闲区,但无下邻空闲区 　　E.有下邻空闲区,但无上邻空闲区 　　F.有上邻空闲区,也有下邻空闲区 　　A：错误，因为回收主存时，要根据相邻分区空闲情况决定空闲分区个数，如果不考虑合并的话，空闲分区个数增加一个，因为可能发生合并情况，所以可能- ，可能不变； B：由上知，错误； C：无上邻空闲区,也无下邻空闲区，不需要合并空闲分区，空闲分区个数加1； D：有上邻空闲区,但无下邻空闲区，需要将刚刚的空闲分区表的起始地址修改为上邻空闲区的起始地址和空闲分区大小，但是空闲分区个数不变； E：有下邻空闲区,但无上邻空闲区，刚刚的空闲分区表起始位置不用改变，空闲分区大小改变，空闲分区个数不变； F：有上邻空闲区,也有下邻空闲区，假设原来是2个空闲分区，新回收一个，发现前后都是空闲的，将三个合并为1个，最后结果为1个空闲分区，空闲分数个数减1 　　int* pint = 0; pint += 6; cout << pint << endl; 　　  　　以上程序的运行结果是： 24 　　首先如果直接cout一个指针，打印的是其所村春的变量的地址。 　　这个指针+6，一个指针的大小是4，加4*6就是24. 　　下面哪种协议在数据链路层？ 　　ARP 　　ICMP 　　FTP 　　UDP 　　HTTP 　　VPN 　　ICMP是网络层，UDP是传输层，FTP和HTTP是应用层 　　目前VPN隧道协议主要有4种：点到点隧道协议PPTP、第二层隧道协议L2TP、网络层隧道协议IPSec以及SOCKS v5协议。其中，PPTP和L2TP工作在数据链路层，IPSec工作在网络层，SOCK v5工作在会话层。 　　TCP/IP模型中，ARP协议属于网络层，在OSI参考模型中，ARP属于数据链路层 　　  　　  　　以下哪种方式，在读取磁盘上多个顺序数据块时的效率最高？ 　　中断控制方式 　　DMA方式 　　通道方式 　　程序直接访问方式 　　循环检查I/O方式 　　以上访问方式都一样 　　答案选C，通道方式。 （1）程序直接访问方式跟循环检测IO方式：CPU和IO串行，每读一个字节（或字），CPU都需要不断检测状态寄存 器的busy标志，当busy=1时，表示IO还没完成；当busy=0时，表示IO完成。此时读取一个字的过程才结束，接着读取下一个字。 （2）中断控制方式：循环检测先进些，IO设备和CPU可以并行工作，只有在开始IO和结束IO时，才需要CPU。但每次只能读取一个字。 （3）DMA方式：Direct Memory Access，直接存储器访问，比中断先进的地方是每次可以读取一个块，而不是一个字。在中断驱动方式中，I/O设备与内存之间的数据交换必须经过CPU中的寄存器，所以速度还是受限，而DMA方式的基本思想是在I/O设备和内存之间开辟直接的数据交换通路。 （4）通道方式：I/O通道控制方式是DMA控制方式的发展，是以一组数据块为单位的，即可以连续读取多个数据块（每次可以处理多个块，而不只是一个块） C/C++工程师能力评估 　　以下prim函数的功能是分解质因数。括号内的内容应该为？ 　　void prim(int m, int n) { if (m >= n) { while ( ) n++; ( ); prim(m, n); cout << n << endl; } } 　　m/=n m%=n 　　分解质因数：从n=2开始，找到第一个m的质因子，因此需要m&n==0，然后继续找剩下的质因子，此时m=m/n。也可以用循环法做，此处不再赘述。 　　补充一下判断是否为质数的代码： 　　int isPrime(int n) { int flag = 1; for(int i = 2; i*i <= n; i++) if(n%i == 0) flag = 0; return flag; } 　　补充一下最大公约数的代码：（辗转相除法） 　　  　　int gcd(int x,int y) //用辗转相除法，求两数的最大公约数 { int r; while(y>0) { r=x%y; x=y; y=r; } return x; } 　　求两数的最大公约数，可采用欧几里得方法：只要两数不相等，就反复用大数减小数，直到相等为止，此相等的数就是两数的最大公约数。 　　int gcd(int x,int y) { while(x!=y) { if(x>y) x=x-y; else y=y-x; } return x; } 　　补充一下最小公倍数的代码：先求出最大公约数，用x*y/gcd（x,y）就可以得到最小公倍数。 　　  　　  　　enum string{ x1, x2, x3=10, x4, x5, } x; 　　函数外部问x等于什么？0 如果是函数外定义那么是0 如果是函数内定义，那么是随机值，因为没有初始化； 数组在当做参数传给函数的时候，会被退化为普通指针，因此，sizeof还是4字节。 指针在做加减的时候，是根据其所指的类型进行加减的，因此加减sizeof(type)。 静态局部变量要比全局变量先销毁。 　　  重载和重写的一些要求： 方法重载（overload）： 1.必须是同一个类 2方法名（也可以叫函数）一样 3参数类型不一样或参数数量不一样 　　方法的重写（override）两同两小一大原则： 方法名相同，参数类型相同 子类返回类型小于等于父类方法返回类型， 子类抛出异常小于等于父类方法抛出异常， 子类访问权限大于等于父类方法访问权限。   类的大小注意点： 　　1 先找有没有virtual 有的话就要建立虚函数表，+4 　　2 static的成员变量属于类域，不算入对象中，成员函数也不占空间      +0 　　3 神马成员都没有的类，或者只有成员函数        +1 　　4 对齐法则，对大家都没有问题，看看有没有被#pragma pack(n)设置大小 　　int main() { MyClass obj1(1), obj2(2); MyClass obj3 = obj1; return 0; } 　　关于拷贝构造和赋值的问题：以上例子中obj3调用的是拷贝构造函数，因为obj3还未存在，需要调用拷贝构造函数。 　　假如obj3已经存在，才会调用赋值函数。 　　  　　 数组全排列： 　　  算法思路： 　　  (1)n个素的全排列=（n-1个素的全排列）+（另一个素作为前缀）； 　　  (2)出口：如果只有一个素的全排列，则说明已经排完，则输出数组； 　　  (3)不断将每个素放作第一个素，然后将这个素作为前缀，并将其余素继续全排列，等到出口，出口出去后还需要还原数组； 　　  　　void perm(int list[], int k, int m) { if (k==m) { copy(list,list+m,ostream_iterator<int>(cout,” “)); cout<<endl; return; } for (int i=k; i<=m; i++) { swap(&list[k],&list[i]); perm（list，k+1，m）; swap(&list[k],&list[i]); } } 　　腾讯2016研发工程师在线模拟笔试题  　　1、 32位系统中，定义a[3][4],则变量占用内存空间为()。 　　解析：＊＊a[3][4]表示a存储的地址，指向一个大小为3＊4的数组，这个数组里存储的是指针。指针大小为4，4＊3＊4＝48。 　　2、有36辆自动赛车和6条跑道，没有计时器的前提下，最少用几次比赛可以筛选出最快的三辆赛车？ 　　解析：6次得到小组第一，a1 b1 c1 d1 e1 f1，def所在的小组的二三名舍弃。 　　第七次，a1，b1，c1，d1，e1，f1进行比赛。得到前三，假设为b1，d1，e1。则a1，c1，f1被舍弃。 　　第八次，在b2，b3，d1，d2，e1种得到第二名和第三名。 　　3、下列哪些http方法对于服务端和用户端一定是安全的？（） 　　解析： 　　Get：通过请求URI得到资源。 　　Post：不仅可以查询也可以添加新的内容，请求放在Body里。 　　Head：类似于Get，但是不返回body，获得请求uri的响应报头，用于检查对象是否存在。 　　Trace：用于远程诊断服务器。 　　Options：列出请求的资源支持的所有方法。 　　Head、Get、Options和Trace视为安全的方法，因为它们只是从服务器获得资源，而不对服务器做任何修改，但对于用户端未必安全。例如get容易将敏感信息暴露在uri中。 　　4、一个系统，提供多个http协议的接口，返回的结果Y有json格式和jsonp格式。Json的格式为 {“code”:100,”msg”:”aaa”},为了保证该协议变更之后更好的应用到多个接口，为了保证修改协议不影响到原先逻辑的代码，以下哪些设 计模式是需要的?协议的变更指的是日后可能返回xml格式，或者是根据需求统一对返回的消息进行过滤。() 　　解析：装饰者模式：动态添加功能，例如过滤功能，并不修改原来的逻辑。 　　proxy模式：为类提供代理，使得代理类可以控制对 对象的访问，例如实现延迟实例化，控制访问等。 　　composite模式：组合模式，将对象组合成树形结构以表示”部分－整体”的层次结构。使得用户对单个对象和组合对象的使用具有一致性。 　　5、对于定义”int *p”,下列哪些说明可能是正确的?() 　　int （＊p）「10」才表示一个指向一位数组的指针。 　　int ＊ （＊p）「10」表示一个指向二位数组的指针。 　　int arr「10」； 　　int ＊p＝arr；此时p保存的是第一个素的地址。 　　6、十字链表是无向图的一种存储结构()是 　　解析： 　　图的存储结构： 　　邻接矩阵，也成为数组表示法。用一个一维数组存储图中顶点的信息，用一个二维数组存储边的信息。 　　
　　邻接表：是一种顺序存储和链式存储结合的存储方法。 　　十字链表：即把每一条边的边结点分别组织到以弧尾顶点为头结点的链表和以弧头顶点为头顶点的链表中。在十字链表表示中，顶点表和边表的结点结构分别如图8.13 的(a)和(b)所示。 　　
　　
　　7、在一个素个数为N的数组里，找到升序排在N/5位置的素的最优算法时间复杂度是 O(n) 　　解析：算法课上讲过的，线性复杂度的找第K大的素的算法。 　　BFPRT算法解决的问题十分经典，即从某n个素的序列中选出第k大（第k小）的素，通过巧妙的分 析，BFPRT可以保证在最坏情况下仍为线性时间复杂度。 　　该算法的思想与快速排序思想相似，当然，为使得算法在最坏情况下，依然能达到o(n)的时间复杂 度，五位算法作者做了精妙的处理。 　　算法步骤： 　　1. 将n个素每5个一组，分成n/5(上界)组。 　　2. 取出每一组的中位数，任意排序方法，比如插入排序。 　　3. 递归的调用selection算法查找上一步中所有中位数的中位数，设为x，偶数个中位数的情况下设定为选取中间小的一个。 　　4. 用x来分割数组，设小于等于x的个数为k，大于x的个数即为n-k。 　　5. 　若i==k，返回x；(i就是中位数) 　　若i<k，在小于x的素中递归查找第i小的素； 　　若i>k，在大于x的素中递归查找第i-k小的素。 　　终止条件：n=1时，返回的即是i小素。 　　8、下面的程序输出可能是什么?一直是“ab” 　　class Printer{ public: Printer(std::string name) {std::cout << name;} }; class Container{ public: Container() : b(“b”), a(“a”) {} Printer a; Printer b; }; int main(){ Container c; return 0; } 　　  　　 初始化列表的初始化顺序  与在列表中的顺序无关，由变量在类中定义的先后顺序决定. 　　因此先初始化a，然后再初始化b。 　　还有一种题目： 　　class A { private: int n1; int n2; public: A():n2(0),n1(n2+2){} void Print(){ cout << “n1:” << n1 << “, n2: ” << n2 <<endl; } }; int main() { A a; a.Print(); return 1; } 　　  　　 这个题目，因为先初始化n1，此时n2还未初始化，所以是未定义值。后来n2才被初始化为0.因此结果是下图： 　　
　　9、下面程序段包含4个函数,其中具有隐含this指针的是() f4 　　int f1(); class T { public:static int f2(); private:friend int f3(); protect:int f4(); }; 　　解析： 静态成员函数属于整个类所拥有，没有this指针 友员函数不是这个类的成员，没有 类的非静态成员函数  有 补充：之前有个问题，能不能同时用const和static修饰类的成员函数。答案是不能，为什么？因为const函数（成员函数）会隐含const this*以保证不修改类的成员。而static不能有this指针。因此不能同时修饰。 　　 10、如果在一个排序算法的执行过程中，没有一对素被比较过两次或以上，则称该排序算法为节俭排序算法，以下算法中是节俭排序算法的有________。插入排序，归并排序 　　解析： 　　A。插入排序的思想是对第i+1位置上的数，将其插入前i个有序数组中。插入以后形成新的有序数组，根据排序数组不会在比较的原则，该素不可能再次比较了。 B。选择排序的思想是对当前第i个位置上的数，那么在后续数组中，选最小的与i对换。说明肯定比较过第二小和第三的数。那么在i+1位置上，上次第二小和第三小的数还需要比较一次选出最小的与i+1交换。那么至少比较了两次。 C。堆排序。堆排序分两步。初始建堆和堆重建。当最大素与最末尾素交换后。面临堆重建的问题。那么堆顶素下层过程中，必然与第二小的素比较一次。再一次堆重建，假设第二小素被替换的时候，他们会在比较一次。 D。归并排序思路是对两个已经排好序的数组，同时向后移动。那么每个素只会与其他数组中的素比较一次。然后合并在一起。根据同组素不会比较的原则的，以后两个素不可能在比较到。 11、一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和()错 解析：哈弗曼树又称最优树,   路径长：第L层的路经长为L-1 带权路径长度(Weighted Path Length of Tree)：定义为树中所有叶结点的带权路径长度之和。 　　结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。 ———————————————————————————————— 　　哈夫曼编码：（左1右0/左0右1）。得到码表，根据出现的概率乘以码长可以得到平均码长。平均码长/等长编码=压缩率。 　　哈夫曼编码步骤：（找最小权值的节点拿出来构成一颗二叉树，生成一个中间节点，再重复） 　　一、对给定的n个权值{W1,W2,W3,…,Wi,…,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,…,Ti,…,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算 法，一般还要求以Ti的权值Wi的升序排列。） 　　二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。 　　三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。 　　四、重复二和三两步，直到集合F中只有一棵二叉树为止。 　　12、若以下程序 　　#include <stdio.h> main() { FILE *fp; int i,a[ 6]={1,2,3,4,5,6},k; fp = fopen (“data.dat”, “w+b”); for (i=0;i<6;i+ +) { fseek(fp,0L,0); fwrite(&a[5—i],sizeof(int),1,fp); } rewind(fp); fread(&k,sizeof(int),1,fp); fclose(fp); printf(“%d”,k); } 　　  　　解析： C的关于文件I/O的函数库，首先定义了一个文件流fp。然后以w+b的方式打开data文件。下图是open的mode选项：r读w写a追加  加b表示binary二进制模式 　　然后fseek 用于二进制方式打开的文件,移动文件读写指针位置。最后开头只有1。将文件内部的位置指针重新指向一个流(数据流/文件)的开头。，每次都写开头，都覆盖模式。