公众号:offer多多
2021/08/04阅读:82主题:橙心
笔试题整理
第一题:前缀tree
假设某段通信电文仅由 6 个字母 ABCDEF 组成,
字母在电文中出现的频率分别为2,3,7,15,4,6。
根据这些频率作为权值构造哈夫曼编码,
最终构造出的哈夫曼树带权路径长度与字母 B 的哈夫曼编码分别为______。(这里假定左节点的值小于右节点的值)
-
答案
长度:37+22+9+5+3=86
编码:1011
-
分析:

step1. 创建一个优先级队列(小)
-
【2 3】 4 6 7 15 step2. 重复 pop 2个最小的,然后累计和添加进去
-
[4 5 6 7 15
-
[6 7] 9 15
-
9 13 15
-
15 22
step3 左节点的值小于右节点的值
进程的关系
并发进程执行的相对速度是______。 -与进程调度策略有关
-
分析:抢占 协作
抢占式多任务处理(Preemption)是计算机操作系统中,一种实现多任务处理(multi task)的方式,
相对于协作式多任务处理而言。
协作式环境下,下一个进程被调度的前提是当前进程主动放弃时间片;
抢占式环境下,操作系统完全决定进程调度方案,操作系统可以剥夺耗时长的进程的时间片,提供给其它进程。
只要有一个优先级更高的任务就绪,它就可以中断当前优先级较低的任务的执行
new

-
答案 a
大小段

举例来说,数值0x2211使用两个字节储存:高位字节是0x22,低位字节是0x11。
大端字节序:高位字节在前,低位字节在后,这是人类读写数值的方法。
小端字节序:低位字节在前,高位字节在后,即以0x1122形式储存。
https://www.ruanyifeng.com/blog/2016/11/byte-order.html
算法
-
写一个函数,输入一个二叉树,树中每个节点存放了一个整数值,函数返回这棵二叉树中相差最大的两个节点间的差值绝对值。
虚拟内存
有一个虚拟存储系统,若进程在内存中占3页(开始时内存为空), 若采用先进先出(FIFO)页面淘汰算法,
当执行如下访问页号序列后1,2,3,4,5, 1,2,5,1,2,3,4,5,会发生多少缺页?
-
分析
D,10。 FIFO,发生缺页时的调入顺序即为淘汰顺序
1、访问1,缺页,调入1,内存中为 1, ,;
2、访问2,缺页,调入2,内存中为 1,2,;
3、 访问3,缺页,调入3,内存中为 1,2,3;
4、 访问4,缺页,调入4,淘汰1,内存中为 4,2,3;
5、 访问5,缺页,调入5,淘汰2,内存中为 4,5,3;
6、 访问1,缺页,调入1,淘汰3,内存中为 4,5,1;
7、 访问2,缺页,调入2,淘汰4,内存中为 2,5,1;
8、 访问5,不缺页,内存中为 2,5,1;
9、 访问1,不缺页,内存中为 2,5,1;
10、 访问2,不缺页,内存中为 2,5,1;
11、访问3,缺页,调入3,淘汰5,内存中为 2,3,1;
12、访问4,缺页,调入4,淘汰1,内存中为 2,3,4;
13、访问5,缺页,调入5,淘汰2,内存中为 5,3,4;
顺序栈

-
B,每次出栈操作前栈内元素依次是 s1,s2 ; s1,s3 ; s1,s4 ; s1,s5,s6 ; s1,s5 ; s1
文件系统
下列关于文件索引结构的叙述中,哪一个是错误的?
正确答案: A
-
采用索引结构,逻辑上连续的文件存放在连续的物理块中[错误]
-
系统为每个文件建立一张索引表
-
索引结构的优点是访问速度快,文件长度可以动态变化
-
索引结构的缺点是存储开销大
分析: 索引,就意味着 不连续物理块
堆
【0、2、1、4、3、9、5、8、6、7】是以数组形式存储的最小堆,删除堆顶元素0后的结果是()


排序


数据结构
当很频繁地对序列中部进行插入和删除操作时,应该选择使用的容器是()

c语言

1.如果const位于*号的左侧,则const就是用来修饰指针所指向的变量,即指针指向为常量。
2.如果const位于*号的右侧,const就是修饰指针本身,即指针本身是常量。
作者介绍