2011华为笔试题
华为2011第一次笔试题目总结:
单选20,多选10,改错3,编程2 有数据结构、网络、操作系统、数据库 一、 单项选择题(4选1)
1. 如果有N个节点用二叉树结构来存储,那么二叉树的最小深度是: 解析:深度为k的二叉树,最多有2^k-1个节点,这时的二叉树成为满二叉树。 Log2(N+1)
2. 形结构的一种重要运算。若已知一棵二叉树的前序序列是BEFCGDH,中序序列是
FEBGCHD,则后序序列是:FEGHDCB 3. 下列算法的功能是: /*L是无头节点单链表*/ LinkList Demo(LinkList L){
ListNode *Q,*P; If(L&&L->next){
Q=L;
L=L->next; P=L;
While(p->next) P=p->next; p->next=Q; Q->next=NULL;
}
return L;
}
解析:将单链表转变为循环链表头结点转变为尾节点 4、循环单向链表指:最后一个节点的指针总是指向链表头。 5、折半查找算法的算法复杂度:O(log2N) 6、void example(char acWelcome[]){ Printf(“%d”,sizeof(acWelcome)); return; }
Void main(){ }
Char acWelcome[]=”Welcome to Huawei Test”; Example(acWelcome); return;
的输出是—— A 4 B 5 解析:4
C 22
D 23
7、设有如下定义:
Unsigned long pulArray[]={6,7,8,9,10}; Unsigned long *pulPtr;
则下列程序段的输出结果为—— pulPtr=pulArray;
*(pulPtr+2)+=2;
printf(“%d,%d\n”,*pulPtr,*(pulPtr+2)); 6,10
pulPtr+2只是一个临时的指针 相当于 int *p,*q; q = PulPtr + 2;
return pulPtr;
而ptr++相当于ptr = ptr +1;return ptr;
7,8
指针的问题!!!
8、#define M(x,y,z) x*y+z
void main(){
int a=1,b=2,c=3; cout
A 12 B 13 C 19 D 8
9、如下:
int func(int a){ int b;
switch(a){ case 1:b=100; case 2:b=200; case 3:b=250; default:b=0; } return b; }
问f(1)等于多少? 0 10、给出以下定义:
Char acX[]=”abcdefg”;
Char acX[]={‘a’,’b’,’c’,’d’,’e’,’f’,’g’}; 则正确的叙述为()
A、 数组acX和数组acY等价
B、 数组acX和数组acY的长度相同
C、 数组acX的长度大于数组acY的长度 D、 数组acX的长度小于数组acY的长度
11、有下面一段代码:
Char szMsisdn[MAX_LEN_MSISDN-1]; szMsisdn[sizeof(szMsidn)]=’\0’; 则对执行以上代码后,正确的叙述为: 程序执行后有问题,内存被踩。
解析:给szMsisdn[MAX_LEN_MSISDN-1]赋值是越界行为。 12、对下列常见的各种网络术语,描述错误的是——
A、DNS(域名系统)是一种用于TCP/IP应用程序的分布式数据库,因此它在TCP/IP体系结构中处于应用层。
B、TFTP是一种文件传递应用程序,它使用的传输层协议是TCP
C、Telnet是标准的提供远程登录功能的应用,可以在不同OS系统的主机之间运行; D、Ping是对两个TCP/IP系统连通性进行测试的基本工具,它利用ICMP进行基本的请求和应答。
13、由国际化组织(ISO)和国际电信联盟(ITU-T)共同提出的开放系统互连(OSI)参考模型中共有—7—层。
14、下列关于进程的叙述中,哪一个是正确的:
A、进程获得处理机而运行是通过调度而得到的。
B、优先级是进行进程调度的重要依据,一旦确定不能改变 C、在单CPU系统中,任意时刻有1个进程处于运行状态 D、进程申请CPU
资源得不到满足时,其状态变为等待状态
上图分别是进程3/5/7状态模型
15、考虑在一个计算机系统里,进程可以申请和释放一个或多个资源。资源一旦分配给一个进程,则该进程独占此资源,直到资源被主动释放。如果一个进程申请的资源,正在被其他进程占有,那么该进程进入等待该资源的一个队列,直到该资源能够得到满足。下列方法中,哪一个不能很好解决死锁问题:
A、给每一个进程不同的优先级,并按照优先级的大小决定在资源队列中的顺序。 B、让进程开始运行时获得全部的资源,在不能获得全部资源时重新启动。 C、给资源编号,并要求进程按照编号的顺序申请资源。??
D、提供超时机制,在进程进入资源等待后一段随机时间内重启进程。 E、系统监控等待队列发生死锁时,重启相关进程。 16.下面的各种RAID类别中,没有任何数据冗余保护的是: A.RAID0 B、RAID1 C、RAID5 D、RAID10 解析:见后面截图资料。
17、在概念设计阶段,最常使用的数据模型是:
A、对象模型 B、物理模型 C、逻辑模型 D、实体联系模型 解析:数据库概念设计阶段用实体联系模型 逻辑设计阶段需要将E-R图转换为关系模型
18、——是DBMS的基本单位,它是构成单一逻辑工作单元的操作集合: A、进程 B、SQL C、事务 D、文件 19、事务的持续性是指:——
A、事务中包括的所有操作要么都做,要么不做 B、事务一旦提交,对数据库的改变时永久的
C、一个事务内部的操作及使用的数据对并发的其他事务是隔离的 D、事务必须是使数据库从一个一致性状态变到另一个一致性状态 20、解决并发操作带来的数据不一致行问题,一般采用方法: A、恢复 B、封锁 C、存取控制 D、协商 多选题:
1、 完全二叉树的概念
满二叉树
a) 深度为k且有2k-1个结点的二叉树。 b) 特点
i. ii.
每一层上的结点数都是最大结点数; 所有的分支结点的度数都为2;
iii. 叶子结点都在同一层次上。 完全二叉树
c) 若对满二叉树的结点从上到下从左至右进行编号,则深度为k且有n个结点的二
叉树称为完全二叉树,当且仅当其每一个结点都与深度为k的满二叉树的编号从1
到n一一对应时。
d) 特点 i. 叶子结点只可能在层次最大的两层上出现;
ii. 前k-1层中的结点都是“满”的,且第 k 层的结点都集中在左边。
2、 栈在——中应用。
A、 递归 B、快速排序(非递归程序用栈实现) C、表达式求值 D、树的遍历 3、 队列是一种运算受限的线性表,以下说法准确的是:
A、 单向队列在允许删除的一端叫队头,在允许插入的一端叫队尾。
B、 单向队列在允许删除的一端叫队尾,在允许插入的一端叫队头。 C、 队列可以用数组实现,也可以用链表实现 D、 队列是先进先出的,栈是后进先出的 4、 下列关于线性表描述正确的是: A、 适用于数据项数量不能预知的情况
B、 逻辑相邻的2元素的存储空间可以是不连续的 C、 链表节点一般有数据元素和指针域两部分组成
D、 存储空间需要动态分配
解析:线性表存储空间分配的静态、动态性是由其实现方式决定的,线性表可以通过顺序表和链表实现,顺序表是静态分配的,链表又分为静态和动态,静态链表静态分配,动态链表动态分配。
5、 下面说法正确的是:
A、 归并排序的平均复杂性为O(N*log(N)); B、 快速排序最坏情况下时间复杂度是O(N2)
C、 堆排序在最好最坏情况下时间复杂度都是O(N*log(N)) D、 快速排序会比归并排序消耗更多的交换空间
解析:归并排序时间复杂度O(n),消耗空间最多。 6、 下面网络知识的阐述中,存在错误的是:
A、 ARP协议根据MAC地址查询其对应的IP地址,便于IP通信; B、 TCP协议是面向连接的,UDP协议时面向无连接的
C、 127.0.0.1属于私有地址 D、 IPV6协议是下一代IP协议 解析:
回送地址:127.0.0.1。一般用于测试使用。例如:ping 127.0.0.1 来测试本机TCP/IP是否正常。 广播地址:是专门用于同时向网络中所有工作站进行发送的一个地址。在使用TCP/IP 协议的网络中,主机标识段host ID 为全1 的IP 地址为广播地址,广播的分组传送给host ID段所涉及的所有计算机。例如,对于10.1.1.0 (255.255.255.0 )网段,其广播地址为10.1.1.255 (255 即为2 进制的11111111 ),当发出一个目的地址为10.1.1.255 的分组(封包)时,它将被分发给该网段上的所有计算机。 广播地址应用于网络内的所有主机 1)有限广播
它不被路由但会被送到相同物理网络段上的所有主机
IP地址的网络字段和主机字段全为1就是地址255.255.255.255 2)直接广播
网络广播会被路由,并会发送到专门网络上的每台主机
IP地址的网络字段定义这个网络,主机字段通常全为1,如 192.168.10.255
私有地址(Private address)属于非注册地址,专门为组织机构内部使用。私有地址就是在互联网上不可用,被用在局域网中的地址。如果你的IP地址是自动获取IP地址,而你在网络上又没有找到可用的DHCP服务器,这时你将会从以下私有地址中临得获得一个IP地址。 以下表列出留用的内部寻址地址
A类 10.0.0.0 --10.255.255.255 B类 172.16.0.0--172.31.255.255 C类 192.168.0.0--192.168.255.255 7、 关于死锁的说法正确的有: A、 竞争可剥夺资源会产生死锁
B、 竞争临时资源会产生死锁??
C、
在发生死锁时,必然存在一个进程—资源的环形链
D、 如果进程在一次性申请其所需的全部资源成功后才运行,就不会发生死锁。
临时性资源又叫可消费资源:
死锁的例子:
1) 进程推进顺序不当产生死锁 2) PV操作使用不当产生死锁
3)
资源分配不当引起死锁
4) 对临时性资源使用不加限制引起死锁
死锁预防:
通过破坏产生死锁的四个条件中的一个或多个条件,保证不会发生死锁。
1、 破坏互斥条件
2、 破坏占有及等待条件
3、 破坏不可剥夺条件
4、 破坏环路等待条件
可剥夺资源:可以被其他进程抢占的资源,如CPU、内存等
不可剥夺资源:一旦进入便不可被抢占,只能完成后自己释放,如打印机、磁带机等。
8、 目标模块装入内存有几种方式:
A、 绝对装入 B、可重定位装入 C、动态运行时装入
4. 类似图片中的题目,数组做函数参数
7,4,4,7
二、 找错、改错
1、 请指出以下程序的两处错误,并给出错误原因:
#include
#include
#include
void GetMemory(char **p, int num)
{
}
void main(void){
char *str=NULL;
GetMemory(&str,100);
if(NULL!=str){
strcpy(&str,
printf(str);
}
return true; }
错误1:main 函数返回值类型为void 不可以有return true.
错误2:strcpy(&str,”hello”); 修改为strcpy(str,”hello”); if(NULL==p && num>0) return; *p=(char *)malloc(num); return;
}
题目结果: hello
strcpy(s1,s2);strcpy函数的意思是:把字符串s2中的内容copy到s1中,连字符串结束标志也一起copy.
char * s2=”ch”这样s1在内存中的存放为:ch\0;
在cout
sizeof是个运算符,它的结果是字符串在内存中的所占字节大小,它要把\0算进去的。
2、如下程序用于输出“Welcome to Huawei Test”,请指出其中的两处错误,并给出错误原因。
char * GetWelcome(void){
char * pcWelcome;
char * pcNewWelcome;
}
pcWelcome=
测试程序如下:
#include
#include
#include
char * GetWelcome(void){
char * pcWelcome;
char * pcNewWelcome;
pcWelcome=
pcNewWelcome=(char *)malloc(strlen(pcWelcome)); if(NULL==pcNewWelcome){ } return NULL; free(pcNewWelcome); strcpy(pcNewWelcome, pcWelcome); return pcNewWelcome;
}
void main(){
char * str; str=GetWelcome(); printf(str);
}
3、请指出下面程序的两处错误,并给出错误原因:
unsigned long FUNC_B(unsigned char str)
{
unsigned long sum; while(0
sum+=str;
str--;
}
return sum; }
错误1:sum赋初值=0;
错误2:0
测试程序:
#include
#include
#include
unsigned long FUNC_B(unsigned char str)
{
}
unsigned long sum = 0; while(0
} sum+=str; str--; return sum;
//see it clearly!
//this button;右键添加断点或者
//this menu; (F9) 或者菜单栏中组件—>开始调试(F5)
//shift+F9—quick watch
//找到原因了吧?嗯,sum 初始化问题,
int main()
{
//now,initial this sum;let us get the issue; //declare a num first; //add a breakpoint here //clearly? unsigned long summer; summer = FUNC_B(5); return 0;
}
应用题
注意:p是数组的首地址,相当于指针常量,是不能赋值。p++ 相当于 p = p + 1; 隐含的要改变p的值,这肯定不成, 也就是说p不能做左值(l-value) ,应该换个指针变量来指向p。 1、对于一个任意输入的少于200字节的字符串,把它按‘-’分成若干子串(子串最多20个),输出原始字符串和每个子串,要求能依次处理用户输入的多个字符串,直到用户输入字符串“0”时程序退出。
#include
using namespace std;
#include
void main(){
char str_s[200];
char *ptr=str_s;
char *pt=str_s;
int lenth;
cout
}
}
小笨解析:
#include
#include
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
char getword[200]; cout
while (true)
{
}
return 0;
}
这么写就能处理多个了
小笨的程序:引入临时数组
#include
using namespace std;
int main()
{
cout
//char outdata[20][200];//用于保存输出的二维数组。
while (true)
{
char getword[200]={'\0'};//保存用户输入的数组 cin>>getword; //用户输入,碰到回车键的时候进行判断 cout>getword; if (getword[0] == '0') {break;}
//而临时数组归零,为下一个数组。
}
return 0;
}
小笨讲解:
指向字符串的指针就不用重新申请空间. char a[111]; char *b = a; 申请,比如malloc(sizeof(int) * num);是指向一片内存区域。 } cout
2、将parabuf[]中的字符串,如“123”,“-301”等转化成数字123,-301并输出,不能用atoi等函数。
#include
using namespace std;
int change(char* str)
{
int base = 0;
while (*str) {
base = base * 10 + (*str) - '0';
} str++;
return base;
}
void main()
{ char str[100];
cin>>str;
int value1;
if (*str == '-')
{
value1 = -1 * change(str + 1);
}
else{
value1 = change(str);
}
cout
整数转换为字符串:
可以采用+‘0’、逆序法。
+‘0’将数转换为相应的ASCII码,‘0’的ASCII码为48 数字5转为字符 5+‘0’=5+58=53即为数字5的ASCII码 #include
using namespace std;
char * itoa(int value,char *string){
char tmp[33];
char *tp=tmp;
int i;
unsigned v;
char *sp;
if(value
v=-value;
else
v=(unsigned)value;
while(v){
i=v%10;
} v=v/10; *tp++=i+'0';
sp=string;
if(value
*sp++='-';
while(tp>tmp){
} *sp++=*--tp;
*sp='\0';
return string;
}
void main(){
int value=-123;
char string[200];
char *x;
x=itoa(value,string); while(*x!='\0'){ cout
堆栈增长的方式:
基础解析:堆栈是内存中指定的一段特殊存储区,存储区起始单元的地址叫栈底,当前存储单元叫栈顶。堆栈存储区一旦指定,栈底就固定不变了,而栈顶是随入栈、出栈操作呈动态。而不同机型的堆栈设计,有两种情况:一是每入栈一个数,栈顶地址加1,每出栈一个数,栈顶地址减1,即堆栈区是由内存的低地址向高地址。另一种是每入栈一个数,栈顶地址减1,每出栈一个数,栈顶地址加1,即堆栈区是由内存的高地址向低地址。高地址、低地址的概念是计算机领域里通用的,并非汇编知识特有。高地址、低地址是相对而言,即相对地址编码的大小而言。
如何判断堆栈的增长放向?i386的机器,栈就是从高地址向低地址增长。堆栈如何增长和编译器有关系,编译器有时候不按照常规办事儿。函数中参数和局部变量的入栈方式不确定——这和编译器有关系;
函数中的两个局部变量,不一定先定义的就先入栈,这些都和编译器有关系。
到底什么不依赖于堆栈呢? 不妨回想一下,函数如何调用。执行一个函数时,这个函数的相关信息都会出现栈之中,比如参数、返回地址和局部变量。当它调用另一个函数时,在它栈信息保持不变的情况下,会把它调用那个函数的信息放到栈中。两个函数的相关信息位置是固定的,肯定是先调用的函数其信息先入栈,后调用的函数其信息后入栈。
设计两个函数,一个作为调用方,另一个作为被调用方。被调用方以一个地址(也就是指针)作为自己的入口参数,调用方传入的地址是自己的一个局部变量的地址,然后,被调用方比较这个地址和自己的一个局部变量地址,由此确定栈的增长方向。
函数的相关信息会一起送入栈,这些信息就包括了参数、返回地址和局部变量等等,在计算机的术语里,有个说法叫栈帧,指的就是这些与一次函数调用相关的东西,而在一个栈帧内的这些东西其相对顺序是由编译器决定的,所以,仅仅在一个栈帧内做比较,都会有对编译器的依赖。就这个问题而言,参数和局部变量,甚至包括返回地址,都是相同的,因为它们在同一个栈帧内,它们之间的比较是不能解决这个问题的,而它们就是一个函数的所有相关信息,所以,一个函数很难解决这个问题。 stdcall调用约定声明的语法为(以前文的那个函数为例):
int __stdcall function(int a,int b)
stdcall的调用约定意味着:1)参数从右向左压入堆栈,2)函数自身修改堆栈 3)函数名自动加前导的下划线,后面紧跟一个@符号,其后紧跟着参数的尺寸
以上述这个函数为例,参数b首先被压栈,然后是参数a,函数调用function(1,2)调用处翻译成汇编语言将变成:
push 2 第二个参数入栈 push 1 第一个参数入栈
call function 调用参数,注意此时自动把cs:eip入栈
cdecl调用约定
cdecl调用约定又称为C调用约定,是C语言缺省的调用约定,它的定义语法是: int function (int a ,int b) //不加修饰就是C调用约定
int __cdecl function(int a,int b)//明确指出C调用约定
在写本文时,出乎我的意料,发现cdecl调用约定的参数压栈顺序是和stdcall是一样的,参数首先由右向左压入堆栈。所不同的是,函数本身不清理堆栈,调用者负责清理堆栈。由于这种变化,C调用约定允许函数的参数的个数是不固定的,这也是C语言的一大特色。
fastcall调用约定和stdcall类似,它意味着:
函数的第一个和第二个DWORD参数(或者尺寸更小的)通过ecx和edx传递,其他参数通过
从右向左的顺序压栈 ,被调用函数清理堆栈 。函数名修改规则同stdcall 其声明语法为:int fastcall function(int a, int b)
thiscall是唯一一个不能明确指明的函数修饰,因为thiscall不是关键字。它是C++类成员函数缺省的调用约定。由于成员函数调用还有一个this指针,因此必须特殊处理thiscall意味着: 参数从右向左入栈 如果参数个数确定,this指针通过ecx传递给被调用者;如果参数个数不确定,this指针在所有参数压栈后被压入堆栈。对参数个数不定的,调用者清理堆栈,否则函数自己清理堆栈为了说明这个调用约定,定义如下类和使用代码: class A
{public:
int function1(int a,int b);
int function2(int a,...);};
int A::function1 (int a,int b){return a+b;}
#include
int A::function2(int a,...)
{va_list ap;
va_start(ap,a);
int i;
int result = 0;
for(i = 0 ; i
{result += va_arg(ap,int);}
return result;}
void callee()
{A a;
a.function1(1, 2);
a.function2(3, 1, 2, 3);}
callee函数被翻译成汇编后就变成:
//函数function1调用
00401C1D push 2
00401C1F push 1
00401C21 lea ecx,[ebp-8]
00401C24 call function1 注意,这里this没有被入栈
//函数function2调用
00401C29 push 3
00401C2B push 2
00401C2D push 1
00401C2F push 3
00401C31 lea eax, [ebp-8] 这里引入this指针
00401C34 push eax
00401C35 call function2
00401C3A add esp, 14h
可见,对于参数个数固定情况下,它类似于stdcall,不定时则类似cdecl
naked call
这是一个很少见的调用约定,一般程序设计者建议不要使用。编译器不会给这种函数增加初始化和清理代码,更特殊的是,你不能用return返回返回值,只能用插入汇编返回结果。这一般用于实模式驱动程序设计,假设定义一个求和的加法程序,可以定义为: __declspec(naked) int add(int a,int b)
{__asm mov eax,a
__asm add eax,b
__asm ret
}
注意,这个函数没有显式的return返回值,返回通过修改eax寄存器实现,而且连退出函数的ret指令都必须显式插入。上面代码被翻译成汇编以后变成:
mov eax,[ebp+8]
add eax,[ebp+12]
ret 8
注意这个修饰是和__stdcall及cdecl结合使用的,前面是它和cdecl结合使用的代码,对于和stdcall结合的代码,则变成:
__declspec(naked) int __stdcall function(int a,int b)
{
__asm mov eax,a
__asm add eax,b
__asm ret 8 //注意后面的8
}
至于这种函数被调用,则和普通的cdecl及stdcall调用函数一致。
函数调用约定导致的常见问题
如果定义的约定和使用的约定不一致,则将导致堆栈被破坏,导致严重问题,下面是两种常见的问题: 函数原型声明和函数体定义不一致
DLL导入函数时声明了不同的函数约定,以后者为例,假设我们在dll种声明了一种函数为: __declspec(dllexport) int func(int a,int b);//注意,这里没有stdcall,使用的是cdecl
使用时代码为:
typedef int (*WINAPI DLLFUNC)func(int a,int b);
hLib = LoadLibrary(...);
DLLFUNC func = (DLLFUNC)GetProcAddress(...)//这里修改了调用约定
result = func(1,2);//导致错误
由于调用者没有理解WINAPI的含义错误的增加了这个修饰,上述代码必然导致堆栈被破坏,MFC在编译时插入的checkesp函数将告诉你,堆栈被破坏