简答题1. 怎么用JSON对象执行深拷贝?
用JSON对象执行深拷贝需要几个前置条件,首先属性值不能是undefined、NaN或Infinity;其次属性值不能是函数、变量、对象实例或正则表达式。所以用JSON对象实现深拷贝时,只能使用一些简单的数据类型。满足以上所列的限制后,就能使用下面代码中的深拷贝函数了。
function deepCopy(obj) {
return JSON.parse(JSON.stringify(obj));
}
[考点] 对象
2. 给定一个数组,数组中含有重复元素,给定两个数字num1和num2,求这两个数字在数组中出现位置的最小距离。
可以采用动态规划的方法把每次遍历的结果都记录下来从而减少遍历次数。具体实现思路如下。当遍历数组时,会遇到以下两种情况:
(1)当遇到num1时,记录下num1对应的数组下标lastPos1,通过求lastPos1与上次遍历到的num2下标lastPos2的差可以求出最近一次遍历到的num1与num2的距离。
(2)当遇到num2时,同样记录下它所对应的数组下标lastPos2,然后通过求lastPos2与上次遍历到的num1下标lastPos1,求出最近一次遍历到的num1与num2的距离。
假设给定数组为:[4,5,6,4,7,4,6,4,7,8,5,6,4,3,10,8],num1=4,num2=8。根据以上方法,执行过程如下:
(1)在遍历的时候首先会遍历到4,下标为lastPos1=0,由于此时还没有遍历到num2,因此,没必要计算num1与num2的最小距离。
(2)然后往下遍历,又遍历到num1=4,更新lastPos1=3。
(3)继续往下遍历,又遍历到num1=4,更新lastPos1=7。
(4)接着往下遍历,又遍历到num2=8,更新lastPos2=9;此时,由于前面已经遍历到num1,就可以求出当前num1与num2的最小距离为|lastPos2-lastPos1|=2。
(5)再往下遍历,又遍历到num2=8,更新lastPos2=15;此时,由于前面已经遍历到num1,就可以求出当前num1与num2的最小距离为|lastPos2-lastPos1|=8;由于8>2,所以,num1与num2的最小距离为2。
实现代码如下所示。
function minNum(x,y){
return(x<y)?x:y;
}
function minDistance(arr, num1, num2){
var len=arr.length;
if(!arr||len<=0){
return;
}
var lastPos1=-1, //上次遍历到num1的位置
lastPos2=-1, //上次遍历到num2的位置
minDis=Math.max.apply(null, arr); //num1与num2的最小距离
for(var i=0;i<len;++i){
if(arr[i]=num1){
lastPos1=i;
if(lastPos2>=0)
minDis=minNum(minDis, lastPos1-lastPos2);
}
if(arr[i]==num2){
lastPos2=i;
if(lastPos1>=0)
minDis=minNum(minDis,lastPos2-lastPos1);
}
}
return minDis;
}
[考点] 数组
3. 如果根的层次为1,具有61个结点的完全二叉树的深度为多少?
根据二叉树的性质,具有n个结点的完全二叉树深度为[log2n]+1,因此,含有61个结点的完全二叉树深度为6层。所以,答案为6。
[考点] 二叉树
4. 设计一个函数来补全整数的前置0,例如为3补全两个前置0,得到的结果为“003”。
设计的函数有两个参数,第一个参数是待补全的整数,第二个参数是指定的位数,例如补全4位的整数,如果传入1,那么返回“0001”;如果传入123,那么返回“0123”。在函数中,首先创建一个指定长度的空数组,然后将空数组用“0”合并,接着和传入的整数拼接,最后调用String对象的slice()方法,并传入一个负数,用于去除多余的零,具体代码如下所示。
function prefixZero(integer, digit) {
return (new Array(digit).join("0")+integer),slice(-digit);
}
[考点] 数组
5. 如何用O(l)的时间复杂度求栈中最小元素?
由于栈具有后进先出的特点,因此,push和pop只能对栈顶元素进行操作。可以用另外一个变量来记录栈底的位置,通过遍历栈中所有的元素找出最小值,但是这种方法的时间复杂度为O(N)。那么如何才能用O(l)的时间复杂度求出栈中最小的元素呢?
在算法设计中,经常会采用空间换取时间的方式来降低时间复杂度,也就是说采用额外的存储空间来降低操作的时间复杂度。具体而言,在实现的时候使用两个栈结构,一个栈用来存储数据,另外一个栈用来存储栈的最小元素。实现思路如下:如果当前入栈的元素比原来栈中的最小值还小,则把这个值压入保存最小元素的栈中;在出栈的时候,如果当前出栈的元素恰好为当前栈中的最小值,保存最小值的栈顶元素也出栈,使得当前最小值变为当前最小值入栈之前的那个最小值。为了简单化,可以在栈中保存整数类型。代码实现如下所示。
function Node(){
this.data=null;
this.min=null;
}
function Min_Stack(a){
var_this=this;
this.data=[];
this.top=0;
a.forEach(function (value, key){
_this.push(value);
});
}
Min_Stack.prototype={
push: function(i){
var node=new Node();
node.data=i;
/**
*此处设置每个节点的min值,设置方法为,若栈为空,
*当前元素data则为当前节点的min,
*若栈非空,则当前元素data与前一个节点的min值比较,
*取其小者作为当前节点的min。
*/
if(this.top==0){
min=node.data;
}else{
min=this.data[this.top-1].min<node.data?
this.data[this.top-1].min:
node.data;
}
node.min=min;
this.data.push(node);
this.top++;
return node;
},
pop: function(){
var r=this.data[--this.top];
this.data.splice(this.top,1);
return r;
},
get_min: function(){
return this.data[this.top-1].min;
}
};
var a=[5],
min_stack=new Min_Stack(a);
console.log("栈中最小值为:",min_stack.get_min()); //5
min_stack.push(6);
console.log("栈中最小值为:",min_stack.get_min()); //5
min_stack.push(2);
console.log("栈中最小值为:",min_stack.get_min()); //2
min_stack.pop();
console.log("栈中最小值为:",min_stack.get_min()); //5
[考点] 栈和队列
6. 假设在桌上有三个密封盒,一个盒中有2枚银币(1银币=10便士),一个盒中有2枚镍币(1镍币-5便士),还有一个盒中有1枚银币和1枚镍币。这些盒子被标上10便士、15便士和20便士,但每个标签都是错误的。允许你从一个盒中拿出1枚硬币放在盒前,看到这枚硬币,你能否说出每个盒内装的东西呢?
取出标着15便士的盒中的1枚硬币,如果是银的说明这个盒是20便士的,如果是镍的说明这个盒是10便士的,再由“每标签都是错误的”可以推断出其他两个盒里的东西。
因为每个标签对应的盒子是错误的,所以知道15便士的盒子里面不会是一银一镍,要么是10便士,要么是20便士。如果从15便士的盒子中取出的硬币是银的则说明该盒子有两枚银币,标签是20便士。如果从15便士的盒子中取出的硬币是镍的则说明该盒子有两枚镍币,标签是10便士。确定了15便士盒对应的硬币和标签后,通过标签和便士值不对应的条件,可以推断出10便士盒和20便士盒的硬币和标签。
[考点] 逻辑题 经典逻辑题
7. 为span元素定义下面的CSS样式后,元素的宽和高是如何计算的?
span {
border: 1px solid #000;
margin: 10px 0;
padding: 10px 0;
width: 300px;
height: 100px;
}
span是一个行内元素,它的盒类型默认是inline。行内元素不能定义width和height属性,它的宽度和高度都由其内容和边框决定。行内元素也不能定义上下外边距(margin)和上下内边距(padding)。虽然定义上下padding后,能使得元素变高,但元素占据的空间并没有改变。下面用代码解释行内元素的这个特点,效果如下图所示,在设置上下内边距(padding)后,行内元素与相邻的块级元素重叠在了一起。
<div>块级元素</div>
<span>行内元素</span>
块级元素和行内元素 [考点] 视觉格式模型
8. input元素中的form属性有什么作用?
form属性是HTML5的新增属性,用于关联某个form元素。以往input元素需要放在form元素之内,定义了form属性后,就可以放在文档的任何位置了,代码如下所示。
<!--form元素内-->
<form id="info" method="post">
<input type="text"/>
</form>
<!--关联id为info的form元素-->
<input type="text" form="info"/>
[考点] HTML元素 表单和表格
9. 什么是CSS Sprite,它有何利弊?
CSS Sprite是一种图像处理技术,将零散的小图标整合在一起,形成一张大图(如下图所示),这张图可称为雪碧图或精灵图。当用这张大图作背景图像时,可以利用background-position属性进行背景定位,找到想要的小图标。这么处理图像,不仅可以解决命名困扰,还能减少HTTP请求数和图像字节数,提升网页性能。但制作和维护这张雪碧图比较烦琐,当需要添加一个小图标的时候,必须修改原图,还不能破坏原有图标的位置。
雪碧图 [考点] CSS属性 边框和背景
10. 请列举出你所知的排序算法的平均时间复杂度、最好情况、最坏情况、空间复杂度和稳定性。
排序算法的参数对比如下表所列。
九种排序算法对比
|
排序算法
|
平均时间复杂度
|
最好情况
|
最坏情况
|
空间复杂度
|
排序方法
|
稳定性
|
冒泡排序
|
O(n2)
|
O(n)
|
O(n2)
|
O(l)
|
In-place
|
稳定
|
插入排序
|
O(n2)
|
O(n)
|
O(n2)
|
O(l)
|
In-place
|
稳定
|
归并排序
|
O(nlogn)
|
O(nlogn)
|
O(nlogn)
|
O(n)
|
Out-pace
|
稳定
|
快速排序
|
O(nlogn)
|
O(nlogn)
|
O(n2)
|
O(logn)
|
In-place
|
不稳定
|
选择排序
|
O(n2)
|
O(n2)
|
O(n2)
|
O(l)
|
In-place
|
不稳定
|
希尔排序
|
O(nlogn)
|
O(nlog2n)
|
O(nlog2n)
|
O(l)
|
In-place
|
不稳定
|
堆排序
|
O(nlogn)
|
O(nlogn)
|
O(nlogn)
|
O(l)
|
In-place
|
不稳定
|
计数排序
|
O(n+k)
|
O(n+k)
|
O(n+k)
|
O(k)
|
Out-place
|
稳定
|
桶排序
|
O(n+k)
|
O(n+k)
|
O(n2)
|
O(n+k)
|
Out-place
|
稳定
|
注释:n表示数据规模;k表示“桶”的个数;In-place表示占用常数内存,不占用额外内存;Out-place表示占用额外内存。
[考点] 排序算法
11. TCP中的队首阻塞是怎么回事?
TCP是一种可靠的通信协议,中途如果出现丢包,那么发送方就会根据重发机制再发一次丢失的包,由于通信两端都是串行处理请求的,因此接收端在这个包到达之前,不会再处理后面的请求,这种现象称为队首阻塞。
[考点] 网络协议
12. 在下面的代码中,子元素div的宽度设为了百分数,如何用JavaScript获得经过计算后的真正宽度?
<style>
.container {
width: 100px;
height: 100px;
}
#info {
width: 10%;
}
</style>
<section class="container">
<div id="info"></div>
</section>
Window对象提供了一个getComputedStyle()方法,能读取经过浏览器计算后实际使用的属性值。此方法的第一个参数是元素对象,第二个参数是一个可选的CSS伪元素(如::after、::before等),它的返回值是一个只读的CSSStyleDeclaration对象。有一点要注意,IE8及以下版本并不支持该方法,但可以用一个非标准的元素属性currentStyle来读取实际值。读取实际值的具体实现如下所示。
var div=document.getElementById("info"),
style=window.getComputedStyle(div);
style.width; //"10px"
//IE8及以下版本
div.currentStyle["width"];
[考点] 控制元素
13. 有没有想过制作一套自己的UI库?如果要制作UI库需要考虑哪些方面?
想过。一套经历过沉淀的UI库,有助于快速搭建页面,并且在兼容性、功能性等各方面都有保障。虽然现在市面上有很多精心雕琢的开源UI库,但可能某些方面不符合实际需求,而且要熟练驾驭第三方UI库,肯定需要一个过程,在这过程中必然会花费一定的时间与精力。如果是自己开发的UI库,那么就能以最小的代价调整成符合实际需求的UI库。开发UI库的过程也是学习和实践的过程,UI库要做到小而全,自然会涉及很多平时不常用或不知道如何使用的概念,将这些概念纳入到UI库中,然后在应用UI库的时候,肯定会遇到各种问题,解决这些问题,不但有助于提升自己对概念的理解,还能激发创造力。
用Sass可以写出短小精悍的UI库,并且Sass有个导入功能(使用@import关键字),非常适合模块化开发,其用法如下所示。
@import "../grid",
"../button";
UI库可以简单地分为基础组件和UI组件两部分,其中,基础组件相当于通用零件,它放在任何地方都能用,例如网格系统、字体排版等;UI组件相当于专用零件,它应用于特定领域,完成特定功能,例如表单控件、表格等。UI库的组件根据实际情况,可多可少,Sass的导入功能使得组件可以按需加载,不但能提高代码重用率,还能降低耦合度。
[考点] 预处理器和框架
14. 给定以非递减顺序排序的三个数组,找出这三个数组中的所有公共元素。例如,给出下面三个数组:ar1=[2,5,12,20,45,85],ar2=[16,19,20,85,200],ar3=[3,4,15,20,39,72,85,190]。那么这三个数组的公共元素为{20,85}。
最容易想到的方法是首先找出两个数组的交集,然后再把这个交集存储在一个临时数组中,最后再找出这个临时数组与第三个数组的交集。这个算法的时间复杂度为O(N1+N2+N3),其中N1、N2和N3分别为三个数组的长度。这种方法不仅需要额外的存储空间,而且还需要额外的两次循环遍历。下面介绍另外一种只需要一次循环遍历、而且不需要额外存储空间的方法,主要思路如下。
假设当前遍历的三个数组元素分别为ar1[i]、ar2[j]和ar3[k],则存在以下几种可能性:
(1)如果ar1[i]、ar2[j]和ar3[k]相等,那么说明当前遍历的元素是三个数组的公有元素,可以直接打印出来,然后通过执行i++,j++,k++,使三个数组同时向后移动,此时继续遍历各数组后面的元素。
(2)如果ar1[i]<ar2[j],则执行i++来继续遍历ar1后面的元素,因为ar1[i]不可能是三个数组公有的元素。
(3)如果ar2[j]<ar3[k],同理可以通过j++来继续遍历ar2后面的元素。
(4)如果前面的条件都不满足,说明ar1[i]>ar2[j]且ar2[j]>ar3[k],此时可以通过k++来继续遍历ar3后面的元素。
实现代码如下所示。
function findCommon(ar1, ar2, ar3) {
var i=0,j=0,k=0,
n1=ar1.length,
n2=ar2.length,
n3=ar3.length,
share="";
//遍历三个数组
while(i<n1 && j<n2 && k<n3){
if(arl[i]==ar2[j]&& ar2[j]==ar3[k]){ //找到公有元素就保存
share+=ar1[i]+"";
i++;
j++;
k++;
}
else if(ar1[i]<ar2[j]) //ar1[i]不可能是共有的元素
i++;
else if(ar2[j]<ar3[k]) //ar2[j]不可能是共有的元素
j++;
else //ar3 [k]不可能是共有的元素
k++;
}
console.log(share);
}
[考点] 数组
15. 假设有一个池塘,里面有无穷多的水。现有两个空水壶,容积分别为5升和6升。如何只用这2个水壶从池塘里取得3升的水?
具体实现如下所列:
(1)先把5升的水壶灌满,倒在6升水壶里,这时6升的水壶里有5升水。
(2)再把5升的水壶灌满,用5升的壶把6升的灌满,这时5升的壶里剩4升水。
(3)接着把6升的水倒掉,然后把5升壶里剩余的水倒入6升的壶里,这时6升的壶里有4升水。
(4)最后把5升的水壶灌满,倒满6升的壶,这时5升的壶剩下的水就是3升(5-2=3)。
[考点] 逻辑题 经典逻辑题
16. 一个三角形3个顶点有3只老鼠,一声枪响,3只老鼠开始沿三角形的边匀速运动,请问它们相遇的概率是多少?
75%。
每只老鼠都有顺时针、逆时钟两种运动方向。3只老鼠共有8种运动情况,只有当3只老鼠都为顺时针或者逆时针时,它们才不会相遇,剩余的6种情况都会相遇,故相遇的概率为6/8=75%。
[考点] 逻辑题 经典逻辑题
17. 设置了元素的过渡后,不能立刻看到效果,需要有触发条件。请列举可用的触发条件。
有3种操作能够触发过渡,分别是CSS伪类、媒体查询和JavaScript,具体如下所列:
(1)CSS伪类触发。CSS有众多伪类(例如:hover、:checked等),如果用:hover,那么只有当鼠标悬停在元素上时,才能执行过渡。
(2)媒体查询触发。当改变窗口的尺寸时,就会触发媒体查询,然后执行过渡。
(3)JavaScript触发。用脚本更改元素样式,也能触发过渡效果。
[考点] CSS3属性 变形、过度和动画
18. 动态链接库和静态链接库的优缺点是什么?
所谓库指的是把一些常用函数的目标文件打包在一起,提供相应函数的接口,便于程序员使用。具体而言,它是别人写好的、现有的、成熟的、可以复用的代码,只需要知道其接口如何定义,便可以简单方便地使用。而静态链接库(Static Link Library,LIB)与动态链接库(Dynamic Link Library,DLL)都是共享代码的方式。以下将对这两种方式进行介绍与对比分析。
动态链接库:在Windows操作系统中动态链接库的后缀为.dll,其中有3个最重要的DLL,分别是Keme132.dll、User32.dll和GDI32.dll。Linux操作系统中动态链接库的后缀为.so。动态链接库的代码是在可执行程序运行时才载入内存的,在编译过程中仅简单地引用,因此,它的代码体积较小。动态链接库的使用方式分为两种:一种是静态加载,即在应用程序启动时加载;一种是动态加载,即该动态链接库在被使用时才被应用程序加载。
动态链接库的优点很多,主要有以下几点:
(1)更加节省内存,并减少页面交换。多个应用程序可以使用同一个动态链接库,启动多个应用程序的时候,只需要将动态链接库加载到内存一次即可。
(2)开发模块好,可以更为容易地将更新应用于各个模块,而不会影响该程序的其他部分,从而具有很强的可维护性和可扩展性。例如,有一个大型网络游戏,如果把整个数百MB甚至数GB的游戏代码都放在一个应用程序里,未来的修改工作将会非常费时,而如果把不同功能的代码分别放在数个动态链接库中,则无须重新生成或安装整个程序就可以应用更新,但前提是要求设计者对功能划分得比较好。
(3)不同编程语言编写的程序只要按照函数调用约定设计就可以调用同一个DLL函数。
动态链接库的缺点如下:
(1)不能解决引用计数。
(2)使用动态链接库的应用程序不是自完备的,它依赖的DLL模块也要存在,如果使用载入时进行动态链接,程序启动时发现DLL不存在,系统将终止程序并给出错误信息,而使用运行时进行动态链接,系统不会终止,但由于DLL中的导出函数不可用,程序会加载失败。
(3)可能造成DLL地狱。DLL地狱(DLL Hell)指的是在微软的Windows系统中,因为动态链接库的版本或兼容性的问题而造成程序无法正常运行的情况。
静态链接库:函数和数据被编译进一个二进制文件(通常扩展名为.lib)。静态链接库的代码在编译过程中已经被载入可执行程序,因此,它的体积较大。在使用静态链接库的情况下,编译链接可执行文件时,链接器从库中复制这些函数和数据并把它们和应用程序的其他模块组合起来创建最终的可执行文件(.exe文件)。静态链接库作为代码的一部分,在编译时被链接。
静态链接库的优点有以下两点:①代码的装载速度快,因为编译时它只会把需要的那部分内容链接进去,所以,其执行速度比动态链接库略快;②只需保证在开发者的计算机中有正确的.lib文件即可,在以二进制形式发布程序时不需考虑在用户的计算机上.lib文件是否存在及其版本问题,可避免DLL地狱等问题。
当然,静态链接库的缺点也是很明显的,如果一个静态链接库被多个应用程序使用,则会被装载多次,浪费内存。
[考点] 操作系统 基本概念
19. 函数声明和函数表达式有哪些区别?
函数通常有2种创建方式:函数声明和函数表达式。它们的区别如下所列:
(1)函数声明必须包含名称,而函数表达式可省略名称。
(2)函数声明有位置限制,不能出现在条件语句、循环语句或其他语句中,而函数表达式没有位置限制,可以出现在语句中实现动态编程。
(3)函数声明会先于函数表达式被提升至作用域的顶部,因此用函数声明创建的函数可以在声明之前被调用,而函数表达式必须在表达式之后才能被调用。
[考点] 函数
20. HTML和HTML5的区别有哪些?
HTML和HTML5主要有以下5个区别:
(1)旧版本的HTML比较依赖浏览器的插件,例如播放视频需要安装Flash插件。
(2)因为HTML5不再基于SGML,所以文档声明类型(DOCTYPE)只有一种。
(3)HTML5消除了过时或冗余的元素,例如font、center等。
(4)HTML5新增了许多语义化的元素(如article、header等)和新功能(如video、canvas等),并提供了更好的跨平台支持。
(5)HTML5规定了新的全局属性和元素属性,全局属性有draggable、contenteditable等,元素属性有accept、placeholder等。
[考点] HTML5