30道选择题,三道编程题。
若干选择题
一、以下说法正确的是( )。
A. 由先序序列、中序序列可以还原出树的原貌
B. 200,190,150,170,180,140,155,160,165,120是一个最大堆
C. 排序之前必须把所有待排数据加载到内存
D. 给定一组输入,可以输出一颗唯一的哈夫曼树
二、请选择正确的描述。( )
A. 静态变量和全局变量是在程序一开始时分配内存的,这部分内存无法回收,直至程序结束
B. 通常常来说,在堆上分配内存比在栈上分配内存效率更高
C. 当我预先知道待分配内存大小时,我就可以直接在栈上分配内存,只要不超过当前操作系统的可用内存大小,就永远会成功
D. 内存泄漏就是指当A程序申请一块内存时,有可能操作系统把B程序的一块内存先交给A程序使用,等A程序结束后再返回给B程序,在内存借用的这段时间内,B程序就产生了内存泄漏
【解析】栈上分配内存效率更高;栈上申请内存并不总是成功;内存泄露是使用完成之后未回收。
三、在公司局域网上ping www.bilibili.com 一定不涉及的网络协议是( )。
A. UDP
B. DNS
C. ICMP
D. RAAP
【解析】。
四、有Area和City两个表,两表的数据如下所示:
Area: | City | ||||
---|---|---|---|---|---|
ID | Name | ID | Name | AreaID | |
1 | North | 1 | 北京 | 1 | |
2 | South | 2 | 上海 | 2 | |
3 | East | 3 | 广州 | 3 | |
4 | West | 4 | 深圳 | 4 | |
null | null | 5 | null | null |
关于下面的sql语句,描述正确的是( )。
select * form City left join Area on City_AreaID = Area.ID where AreaID>0 group by AreaID having count(Region)>0 order by count(Region) desc limit 1;
A.该SQL执行会形成City和Area两表的笛卡尔积
B.该语句执行顺序上,会先执行where再执行having再执行order by最后执行limit
C.该语句执行顺序上,会先执行from,再执行join,再执行where
D.select form City left join Area on City_AreaID = Area.ID 和select form City inner join Area on City_AreaID = Area.ID这两条SQL语句执行的结果是不同的
五、客户端C和服务器S之间建立了一个TCP连接,TCP最大段长度为2KB,客户端C当前的拥塞窗口是16KB,向服务器S连续发送2个最大段之后,成功接收到服务器S发送的第一段确认段,确认段中通告的接收窗口大小是8KB,那么此时客户端C还可以向服务器S发送最大字节数是( )。
A. 16KB
B. 14KB
C. 8KB
D. 6KB
【解析】 min(16, 8) - 2 = 8-2=6。
六、下列关于linux中kernel space和user space描述错误的是()
A.user space不能直接对文件进行写操作
B.程序代码能手动指定在哪个space中运行
C.user space不能直接创建进程
D.user space和kernel space的运行空间是相互隔离的
七、采用递归方式对顺序表进行快速排序,下列关于递归次数的叙述中,正确的是()
- 递归次数与初始数据的排列次序无关
- 每次划分后,先处理较长的分区可以减少递归次数
- 每次划分后,先处理较短的分区可以减少递归次数
- 递归次数与每次划分后得到的分区处理顺序无关
【解析】递归次数与各元素的初始排列有关,认为是固定的。如果每一次划分后分区比较平衡,则递归次数少;如果划分后分区不平衡,则递归次数多。递归次数与处理顺序无关。
每次划分后,先处理较短的分区可以减少递归深度。
1. 24点游戏
给出4个1-10的数字,通过加减乘除,得到数字为24就算胜利。
1 | Input: |
暴力法求解,使用三层循环。
1 | class Solution{ |
2. 括号匹配
给定一个只包括 ‘(‘,’)’,’{‘,’}’,’[‘,’]’ 的字符串,判断字符串是否有效。
1 | Input: |
1 | public boolean isValid(String s) { |
3. 一个找零问题
某国的货币系统包含面值1元、4元、16元、64元共计4种硬币,以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为N的商品,请问最少他会收到多少硬币?
1 | Input: |
动态规划求解
- 利用背包问题进行参考,购买的物品价值为N,给定的面值选择的硬币种类选择,其额度是V = {1,4,16,64},剩余金额为M = 1024 - N;问应该如何选择硬币,使得到的硬币数量为最少??
- 将其转化为:令 dp[j] 表示在前 j 个硬币中能够等于在 i 的额度中的M的价值,则可以得到如下的动态规划函数:
得到状态转移方程:
(1) dp[0] = 0
(2) dp[j] = min( dp[j], dp[ j - coins[i] ] + 1 ) j <= M
1 | public static int GetCoinCount (int N) { |
直接求解
1 | int cnum1,cnum2,cnum3,cnum4; |