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函数将告诉你，堆栈被破坏