52《c语言数据结构》第3章
栈和队列 自测卷答案
上亿文档资料，等你来发现
52《c语言数据结构》第3章
栈和队列 自测卷答案
第3章栈和队列自测卷答案姓名班级；一、填空题（每空1分，共15分）；1.【李春葆】向量、栈和队列都是结构，可以在向量；2.栈是一种特殊的线性表，允许插入和删除运算的一；3.性表；4.在一个循环队列中，队首指针指向队首元素的5.；6.向栈中压入元素的操作是先，后；7.从循环队列中删除一个元素时，其操作是先移动队；head；二、判断正误（判断下列概念的正确性，并
栈和队列 自测卷答案
一、填空题（每空1分，共15分）
1. 【李春葆】向量、栈和队列都是结构，可以在向量的删除元素；对于栈只能在
插入和删除元素；对于队列只能在
删除元素。
2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为
。不允许插入和删除运算的一端称为
4. 在一个循环队列中，队首指针指向队首元素的 5. 在具有n个单元的循环队列中，队满时共有个元素。
6. 向栈中压入元素的操作是先 ，后 。
7. 从循环队列中删除一个元素时，其操作是 先
移动队首指针
，后 8. 〖00年统考题〗带表头结点的空循环双向链表的长度等于 解：
二、判断正误（判断下列概念的正确性，并作出简要的说明。）（每小题1分，共10分） （
）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。
）2. 在表结构中最常用的是线性表，栈和队列不太常用。
错，不一定吧？调用子程序或函数常用，CPU中也用队列。
）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。
）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。
正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。
）5. 栈和链表是两种不同的数据结构。
错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。
）6. 栈和队列是一种非线性数据结构。
错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。
）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。
）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把
两个栈的栈底分别设在这片内存空间的两端。
）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
错，后半句不对。
× ）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。
错，有可能。
三、单项选择题（每小题1分，共20分）
）1. 〖00年元月统考题〗栈中元素的进出原则是
Ａ．先进先出
Ｂ．后进先出
Ｃ．栈空则进
Ｄ．栈满则出
）2. 〖李春葆〗若已知一个栈的入栈序列是1，2，3，?，n，其输出序列为p1，p2，p3，?，pn，若p1=n，则pi为
Ｄ．不确定
解释：当p1=n，即n是最先出栈的，根据栈的原理，n必定是最后入栈的，那么输入顺序必定是1，2，3，?，n，则出栈的序列是n，?，3，2，1。
）3. 〖李春葆〗判定一个栈ST（最多元素为m0）为空的条件是
Ａ．ST-&top&&0
Ｂ．ST-&top=0
Ｃ．ST-&top&&m0
Ｄ．ST-&top=m0
）4. 〖李春葆〗判定一个队列QU（最多元素为m0）为满队列的条件是
Ａ．QU-&rear － QU-&front = = m0
Ｂ．QU-&rear － QU-&front －1= =
Ｃ．QU-&front = = QU-&rear
Ｄ．QU-&front = = QU-&rear+1
）5．数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，
ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为
（Ａ）r－f;
（Ｂ）（n＋f－r）%
（Ｃ）n＋r－f;
（Ｄ）（n＋r
6. 【98初程P71】
从供选择的答案中，选出应填入下面叙述内的最确切的解答，把相应编号写在答卷的对应栏内。
设有4个数据元素a1、a2、a3和a4，对他们分别进行栈操作或队操作。在进栈或进队操作时，按a1、a2、a3、a4次序每次进入一个元素。假设栈或队的初始状态都是空。
现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是
，第二次出栈得到的元素是
是；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是
，第二次出队得到的元素是
。经操作后，最后在栈中或队中的元素还有
个。 供选择的答案：
A～D：①a1
④a4 E： ①1
④ 0 答：ABCDE＝2,
7. 【94初程P75】
从供选择的答案中，选出应填入下面叙述内的最确切的解答，
把相应编号写在答卷的对应栏内。
栈是一种线性表，它的特点是
。设用一维数组A[1,…,n]来表示一个栈，A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。往栈中推入（PUSH）一个新元素时，变量T的值
；从栈中弹出（POP）一个元素时，变量T的值
。设栈空时，有输入序列a，b，c，经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素的序列是
，变量T的值是
。 供选择的答案：
A： ① 先进先出
②后进先出
③进优于出
④出优于进 ⑤ 随机进出 B，C： ① 加1
⑥减2 D：① a,b
⑥ a,c E：① n+1
⑤ n-2 答案：ABCDE=2,
注意，向地址的高端生长，称为向上生成堆栈；向地址低端生长叫向下生成堆栈，本题中底部为n，向地址的低端递减生成，称为向下生成堆栈。
8. 【91初程P77】
从供选择的答案中，选出应填入下面叙述
内的最确切的解答，把相应编号写在答卷的对应栏内。
在做进栈运算时，应先判别栈是否
；在做退栈运算时，应先判别栈是否
。当栈中元素为n个，做进栈运算时发生上溢，则说明该栈的最大容量为
。 为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的
分别设在这片内存空间的两端，这样，只有当
时，才产生上溢。 供选择的答案：
A，B：①空
④ 下溢 C：
④ n/2 D：
E：①两个栈的栈顶同时到达栈空间的中心点
②其中一个栈的栈顶到达栈空间的中心点
③两个栈的栈顶在达栈空间的某一位置相遇
④两个栈均不空，且一个栈的栈顶到达另一个栈的栈底
答案：ABCDE＝2,
四、简答题（每小题4分，共20分）
1. 【严题集3.2①和3.11①】说明线性表、栈与队的异同点。
刘答：相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。
不同点：①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。 ② 用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。
2. 【统考书P60 4-11，难于严题集3.1①】设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。
刘答：至少有14种。
① 全进之后再出情况，只有1种：4，3，2，1
② 进3个之后再出的情况，有3种，3,4,2,1
③ 进2个之后再出的情况，有5种，2,4,3,1
2,1,3,4 ④ 进1个之后再出的情况，有5种，1,4,3,2
3. 【刘自编】假设正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’ 和‘ababab’则不是回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列等方式正确输出其回文的可能性？
答：线性表是随机存储，可以实现，靠循环变量（j--）从表尾开始打印输出；
堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可； 队列是先进先出，不易实现。
哪种方式最好，要具体情况具体分析。若正文在机内已是顺序存储，则直接用线性表从后往前读取即可，或将堆栈栈顶开到数组末尾，然后直接用POP动作实现。（但堆栈是先减后压还是??）
若正文是单链表形式存储，则等同于队列，需开辅助空间，可以从链首开始入栈，全部压入后再依次输出。
4. 【统考书P60 4-13】顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？
答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。
采用循环队列是解决假溢出的途径。 另外，解决队满队空的办法有三：
① 设置一个布尔变量以区别队满还是队空； ② 浪费一个元素的空间，用于区别队满还是队空。 ③ 使用一个计数器记录队列中元素个数（即队列长度）。
我们常采用法②，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。 判断循环队列队空标志是： f=rear
队满标志是：f=(r+1)%N
5. 【统考书P60 4-14】设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有
① front=11，rear=19;
② front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？
答：用队列长度计算公式：
(N＋r－f)% N
① L=（40＋19－11）% 40=8
② L=（40＋11－19）% 40=32
五、阅读理解（每小题5分，共20分。至少要写出思路）
1. 【严题集3.7①】按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，并仿
照教材例3-2的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：
A－B×C/D+E↑F
2. 【严题集3.3②】写出下列程序段的输出结果（栈的元素类型SElem Type为char）。 void main( ){ Stack S; Char x,y; InitStack(S); X=’c’;y=’k’;
Push(S,x); Push(S,’a’);
Push(S,y); Pop(S,x); Push(S,’t’); Push(S,x); Pop(S,x); Push(S,’s’);
while(!StackEmpty(S)){ Pop(S,y);printf(y); }; Printf(x); }
答：输出为“stack”。
3. 【严题集3.12②】写出下列程序段的输出结果（队列中的元素类型QElem Type为char）。 void main( ){
Init Queue (Q); Char x=’e’; y=’c’;
EnQueue (Q,’h’); EnQueue (Q,’r’);
EnQueue (Q,’y’);
包含各类专业文献、专业论文、高等教育、外语学习资料、各类资格考试、应用写作文书、52《c语言数据结构》第3章
栈和队列 自测卷答案 等内容。　
　数据结构第3章栈和队列自测题答案第3 章 栈和队列 自测卷答案 题号 题分 ...数据结构(c语言版)题集答... 10页 免费 数据结构栈和队列自测题 7页 免费... 　数据结构(C语言)习题 答案数据结构(C语言)习题 答案隐藏&& 第3章 栈和队列 自测卷 一、填空题 1. 向量(线性表)、栈和队列都是 线性 结构,可以在向量的 任... 　数据结构第3章栈和队列自测题答案_工学_高等教育_教育专区。数据结构第3章栈和...数据结构(c语言版)题集答... 10页 免费 数据结构栈和队列自测题 7页 免费... 　数据结构(c语言版)题集答案――第三章_栈和队列_IT认证_资格考试/认证_教育专区。数据结构题集(c语言版)答案及部分代码第三章 栈与队列 3.15 typedef struct{... 　《C语言数据结构》第1至... 62页 2下载券 数据结构第3章栈和队列自... ...第2 章 自测卷答案 题号 题分 得分 一 13 二 10 三 10 四 10 姓名 五... 　第三章栈和队列习题_数据... 11页 免费 《数据结构》习题集:第... 7页 ...(1)A*B*C (2)(A+B)*C-D (3)A*B+C/(D-E) (4)(A+B)*D+E/... 　第3章 栈和队列 自测卷 一、填空题 1. 2. 3. 4. 5. 6. 7. 8. 向量(线性表)、栈和队列都是 线性 结构,可以在向量的 任何 位置插入和删除元素;对于... 　《c语言数据结构》第9章 排序 自测卷 答案_理学_高等教育_教育专区。第 9 章排序自测卷答案姓名班级题号 题分 得分 一 24 二 18 三 36 四 8 五 14 总分... 　《数据结构》(C语言版)第三... 71页 免费 数据结构(C语言版)第3章 栈... 暂无评价 54页 5财富值 数据结构(c语言版)题集答案... 10页 免费 数据结构... 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
数据结构(C语言版)栈和队列
下载积分：400
内容提示：数据结构(C语言版)栈和队列
文档格式：PPT|
浏览次数：22|
上传日期： 09:49:21|
文档星级：
该用户还上传了这些文档
数据结构(C语言版)栈和队列
官方公共微信C语言/C++栈和队列 - C++技巧 - 大学IT网
当前位置: >
> C语言/C++栈和队列
关键词：&&阅读(1188) 赞(16)
[摘要]本文是对C语言/C++栈和队列的讲解，对学习C++编程技术有所帮助,与大家分享。
①数制转换：
将一个非负的十进制整数N转换为另一个等价的基为B的B进制数的问题，很容易通过"除B取余法"来解决。
【例】将十进制数13转化为二进制数。
解答：按除2取余法，得到的余数依次是1、0、1、1，则十进制数转化为二进制数为1101。
分析：由于最先得到的余数是转化结果的最低位，最后得到的余数是转化结果的最高位，因此很容易用栈来解决。
具体算法如下：
#include &STACK&
//C++中使用栈要包含的头文件
//这个也是要加的
void conversion(int N,int B)
{//假设N是非负的十进制整数，输出等值的B进制数
stack&int& S;
//创建一个元素类型为int型的空栈
S.push(N%B); //将转换后的数值，从底位到高位开始入栈
while(!S.empty())//栈非空时退栈输出
printf("%d",S.top());
//打印栈顶元素
//将栈顶元素出栈
int main()
conversion(10,2);
②表达式求值
表达式求值是程序设计语言编译中的一个最基本的问题。我们讨论一种简单直观的方法“算法优先级法”
算术四则运算的规则：
1、从左到右
2、先乘除后加减
3、先括号内，后括号外
相继出现的两个运算符优先级如下图：
【例】4 + 2*3 -10/5 每一步的计算顺序应该是：
4 + 2*3 -10/5 = 4 + 6 - 10/5 = 10 - 10/5 = 10 - 2 = 8
算法步骤：（我们假设表达式以字符‘#’结尾）
（1）首先，创建空运算符栈OPTR，将表达式起始符‘#’压入栈底，创建空操作数栈OPND
（2）依次读入表达式中的每个字符，若是操作数则进操作数栈，若是运算符则和运算符栈顶的运算符比较优先级后，做如下相应操作：
1.如果栈顶的运算符优先级较低，则把新的运算符压入OPTR；执行（2）
2.如果栈顶的运算符优先级较高，则将其 和 操作数栈的两个栈顶元素 退栈，计算3个元素组成的表达式的值，再压入操作数栈，然后继续判断；
3.如果栈顶的运算符优先级相等（除了#符外，只有‘(’和‘)’是相等的），则将‘（’出栈；执行（2）
（3）直到整个表达式求值完毕（即OPTR栈顶元素和当前读入的字符均为‘#’）
具体算法实现：
#include &iostream&
#include &stack&//C++中使用栈要包含的头文件
//符号数组
char symbol[7] = {'+', '-', '*', '/', '(', ')', '#'};
//栈内元素的优先级
int in[7] = {3, 3, 5, 5, 1, 6, 0};
//栈外元素的优先级
int out[7] = {2, 2, 4, 4, 6, 1, 0};
* 通过符号字符获取它的数组下标
int get(char c)
* 比较栈内运算符c1和栈外运算符c2的优先级
char precede(char c1, char c2)
int i1 = get(c1);
int i2 = get(c2);
if(in[i1] & out[i2])
return '&';
else if(in[i1] & out[i2])
return '&';
return '=';
* 计算基本表达式的值
int figure(int a, int theta, int b)
switch(theta)
return a +
return a -
return a *
return a /
* 计算表达式的值
int EvaluateExpression(const char *exp)
stack&int& OPND; //操作数栈
stack&int& OPTR; //运算符栈
OPTR.push(get('#'));
int flag = 1; //表示正负号 1,表示正 0,表示负
int a, theta,
if(!('+' == *exp || '-' == *exp || '(' == *exp || isdigit(*exp)))
{//如果不是以'+'、'-'、'('或者数字的其中一个开头，则表达式错误
cout && "表达式出错1" &&
return -1;
if('+' == *exp)
exp++;//指向下一个字符
else if('-' == *exp)
exp++;//指向下一个字符
int index = OPTR.top();
//获取运算符栈顶元素在数组的下标号
while(*exp || symbol[index] != '#') //如果栈顶元素是'#'且当前元素为空结束计算
if(isdigit(*exp))
{//如果当前元素是数字，计算整个操作数的值，然后压入操作数栈
int sum = 0;
while(isdigit(*exp))
{//计算操作数的值
sum = sum * 10 + (*exp - '0');
if (!flag)
//如果是负数
OPND.push(sum);
{//如果不是数字
switch(precede(symbol[OPTR.top()], *exp))//比较栈顶运算符和当前运算符的优先级
case '&' :
b = OPND.top();
OPND.pop();
a = OPND.top();
OPND.pop();
theta = OPTR.top();
OPTR.pop();
OPND.push(figure(a, theta, b));
case '&' :
OPTR.push(get(*exp));
case '=' :
OPTR.pop();
index = OPTR.top();
return OPND.top();
int main()
char c[50] = {0};
cout && "请输入一个表达式: ";
cin.getline(c,50);
cout && EvaluateExpression(c) &&
队列的应用
1、问题叙述
假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者，等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。
2、问题分析
先入队的男士或女士亦先出队配成舞伴。因此该问题具体有典型的先进先出特性，可用队列作为算法的数据结构。
在算法中，假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。此时，若某队仍有等待配对者，算法输出此队列中等待者的人数及排在队头的等待者的名字，他（或她）将是下一轮舞曲开始时第一个可获得舞伴的人。
3、具体算法及相关的类型定义
#include &QUEUE&&span style="background-color: font-family: 微软雅黑; "&//C++中使用队列要包含的头文件&/span&
typedef struct
char name[20];
//性别，'F'表示女性，'M'表示男性
void DancePartner(Person dancer[],int num)
{//结构数组dancer中存放跳舞的男女，num是跳舞的人数。
queue&Person& Mdancers,F
for(int i = 0; i & i++)
{//依次将跳舞者依其性别入队
p=dancer[i];
if(p.sex=='F')
Fdancers.push(p); //排入女队
Mdancers.push(p); //排入男队
printf("The dancing partners are: \n \n");
while(!(Fdancers.empty()||Mdancers.empty()))
//依次输入男女舞伴名
p=Fdancers.front();
//获取女队第一人
Fdancers.pop();
printf("%s ",p.name);
//打印出队女士名
p=Mdancers.front();
//获取男队第一人
Mdancers.pop();
printf("%s\n",p.name);
//打印出队男士名
if(!Fdancers.empty())
{//输出女士剩余人数及队头女士的名字
printf("\n There are %d women waitin for the next round.\n",Fdancers.size());
p=Fdancers.front(); //取队头
printf("%s will be the first to get a partner. \n",p.name);
else if(!Mdancers.empty())
{//输出男队剩余人数及队头者名字
printf("\n There are%d men waiting for the next round.\n",Mdancers.size());
p=Mdancers.front();
printf("%s will be the first to get a partner.\n",p.name);
printf("There is not person in the queue!");
}//DancerPartners
int main()
Person p[] = {{"A",'F'},{"B",'F'},{"C",'M'},{"D",'M'}};
DancePartner(p,4);
相关C++技巧推荐面试题1：变量的声明和定义有什么区别&为变量分配地址和存储空间的称为定义，不分配地址的称为声明。一个变量可以在多个地方声明，但是只在一个地方定义。加入extern修饰的是变量的声明，说明此变量将在文件以外或在文件后面部分定义。&说明：很多时候一个变量，只是声明不分配内存空间，直到具体使用时才初始化，分配内存空间，如外部变量。&面试题2：写出bool 、int、 float、指针变量与“零值”比较的if语句&bool型数据：&if( flag ) { &A; } else { &B； }&int型数据：&if( 0 != flag ) { &A; } else { &B； }&指针型数：&if( NULL == flag ) { &A; } else { &B； }&float型数据：&if ( ( flag &= NORM ) && ( flag &= NORM ) ) { &A；&}&注意：应特别注意在int、指针型变量和“零值”比较的时候，把“零值”放在左边，这样当把“==”误写成“=”时，编译器可以报错，否则这种逻辑错误不容易发现，并且可能导致很严重的后果。&面试题3：sizeof和strlen的区别&sizeof和strlen有以下区别：&sizeof是一个操作符，strlen是库函数。&sizeof的参数可以是数据的类型，也可以是变量，而strlen只能以结尾为‘/0‘的字符串作参数。  编译器在编译时就计算出了sizeof的结果。而strlen函数必须在运行时才能计算出来。并且sizeof计算的是数据类型占内存的大小，而strlen计算的是字符串实际的长度。  数组做sizeof的参数不退化，传递给strlen就退化为指针了。&注意：有些是操作符看起来像是函数，而有些函数名看起来又像操作符，这类容易混淆的名称一定要加以区分，否则遇到数组名这类特殊数据类型作参数时就很容易出错。最容易混淆为函数的操作符就是sizeof。&面试题4：C语言的关键字 static 和 C++ 的关键字 static 有什么区别&在C中static用来修饰局部静态变量和外部静态变量、函数。而C++中除了上述功能外，还用来定义类的成员变量和函数。即静态成员和静态成员函数。&注意：编程时static的记忆性，和全局性的特点可以让在不同时期调用的函数进行通信，传递信息，而C++的静态成员则可以在多个对象实例间进行通信，传递信息。&面试题5：Ｃ中的malloc和Ｃ＋＋中的new有什么区别&malloc和new有以下不同：&（1）new、delete 是操作符，可以重载，只能在C++中使用。&（2）malloc、free是函数，可以覆盖，C、C++中都可以使用。&（3）new 可以调用对象的构造函数，对应的delete调用相应的析构函数。&（4）malloc仅仅分配内存，free仅仅回收内存，并不执行构造和析构函数&（5）new、delete返回的是某种数据类型指针，malloc、free返回的是void指针。&注意：malloc申请的内存空间要用free释放，而new申请的内存空间要用delete释放，不要混用。因为两者实现的机理不同。&面试题6：写一个“标准”宏MIN&#define min(a,b)((a)&=(b)?(a):(b))&注意：在调用时一定要注意这个宏定义的副作用，如下调用： &((++*p)&=(x)?(++*p):(x)。&p指针就自加了两次，违背了MIN的本意。&面试题7：一个指针可以是volatile吗&可以，因为指针和普通变量一样，有时也有变化程序的不可控性。常见例：子中断服务子程序修改一个指向一个buffer的指针时，必须用volatile来修饰这个指针。&说明：指针是一种普通的变量，从访问上没有什么不同于其他变量的特性。其保存的数值是个整型数据，和整型变量不同的是，这个整型数据指向的是一段内存地址。&面试题8：a和&a有什么区别&请写出以下代码的打印结果，主要目的是考察a和&a的区别。&#include&stdio.h&&void main( void )&{ &int a[5]={1,2,3,4,5}; &int *ptr=(int *)(&a+1); &&printf(&%d,%d&,*(a+1),*(ptr-1)); &&}&&输出结果：2，5。&注意：数组名a可以作数组的首地址，而&a是数组的指针。思考，将原式的int *ptr=(int *)(&a+1);改为int *ptr=(int *)(a+1);时输出结果将是什么呢？&面试题9：简述C、C++程序编译的内存分配情况&C、C++中内存分配方式可以分为三种：&（1）从静态存储区域分配：&内存在程序编译时就已经分配好，这块内存在程序的整个运行期间都存在。速度快、不容易出错，因为有系统会善后。例如全局变量，static变量等。&（2）在栈上分配：&在执行函数时，函数内局部变量的存储单元都在栈上创建，函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中，效率很高，但是分配的内存容量有限。&（3）从堆上分配：&即动态内存分配。程序在运行的时候用malloc或new申请任意大小的内存，程序员自己负责在何时用free或delete释放内存。动态内存的生存期由程序员决定，使用非常灵活。如果在堆上分配了空间，就有责任回收它，否则运行的程序会出现内存泄漏，另外频繁地分配和释放不同大小的堆空间将会产生堆内碎块。&一个C、C++程序编译时内存分为5大存储区：堆区、栈区、全局区、文字常量区、程序代码区。&&面试题10：简述strcpy、sprintf与memcpy的区别&三者主要有以下不同之处：&（1）操作对象不同，strcpy的两个操作对象均为字符串，sprintf的操作源对象可以是多种数据类型，目的操作对象是字符串，memcpy 的两个对象就是两个任意可操作的内存地址，并不限于何种数据类型。&（2）执行效率不同，memcpy最高，strcpy次之，sprintf的效率最低。&（3）实现功能不同，strcpy主要实现字符串变量间的拷贝，sprintf主要实现其他数据类型格式到字符串的转化，memcpy主要是内存块间的拷贝。&说明：strcpy、sprintf与memcpy都可以实现拷贝的功能，但是针对的对象不同，根据实际需求，来选择合适的函数实现拷贝功能。&面试题11：设置地址为0x67a9的整型变量的值为0xaa66&int * &ptr = (int *)0x67a9; &*ptr = 0xaa66; &说明：这道题就是强制类型转换的典型例子，无论在什么平台地址长度和整型数据的长度是一样的，即一个整型数据可以强制转换成地址指针类型，只要有意义即可。&面试题12：面向对象的三大特征&面向对象的三大特征是封装性、继承性和多态性：&封装性：将客观事物抽象成类，每个类对自身的数据和方法实行protection（private， protected，public）。&继承性：广义的继承有三种实现形式：实现继承（使用基类的属性和方法而无需额外编码的能力)、可& & &视继承(子窗体使用父窗体的外观和实现代码)、接口继承(仅使用属性和方法,实现滞后到子类实现)。&多态性：是将父类对象设置成为和一个或更多它的子对象相等的技术。用子类对象给父类对象赋值& & & & & & &之后，父类对象就可以根据当前赋值给它的子对象的特性以不同的方式运作。&说明：面向对象的三个特征是实现面向对象技术的关键，每一个特征的相关技术都非常的复杂，程序员应该多看、多练。&面试题13：C++的空类有哪些成员函数&缺省构造函数。&缺省拷贝构造函数。&缺省析构函数。&缺省赋值运算符。&缺省取址运算符。&缺省取址运算符 const。&注意：有些书上只是简单的介绍了前四个函数。没有提及后面这两个函数。但后面这两个函数也是空类的默认函数。另外需要注意的是，只有当实际使用这些函数的时候，编译器才会去定义它们。&面试题14：谈谈你对拷贝构造函数和赋值运算符的认识&拷贝构造函数和赋值运算符重载有以下两个不同之处：&（1）拷贝构造函数生成新的类对象，而赋值运算符不能。&（2）由于拷贝构造函数是直接构造一个新的类对象，所以在初始化这个对象之前不用检验源对象是否和新建对象相同。而赋值运算符则需要这个操作，另外赋值运算中如果原来的对象中有内存分配要先把内存释放掉&注意：当有类中有指针类型的成员变量时，一定要重写拷贝构造函数和赋值运算符，不要使用默认的。&面试题15：用C++设计一个不能被继承的类&template &typename T&&class A&{ &friend T;&private: &A() {} &~A() {}&}; &class B : virtual public A&B&&{&public: &B() {} &~B() {}&};&class C : virtual public B&{&public: &C() {} &~C() {}&};&void main( void )&{ &B &//C &&}&注意：构造函数是继承实现的关键，每次子类对象构造时，首先调用的是父类的构造函数，然后才是自己的。&面试题16：访问基类的私有虚函数&写出以下程序的输出结果：&#include &iostream.h&&class A&{ &virtual void g() &{ &&cout && &A::g& && &}&private: &virtual void f() &{ &&cout && &A::f& && &}&};&class B : public A&{ &void g() &{ &&cout && &B::g& && &} &virtual void h() &{ &&cout && &B::h& && &}&};&typedef void( *Fun )( void );&void main()&{ &B &Fun pF &for(int i = 0 &i & 3; i++) &{ &&pFun = ( Fun )*( ( int* ) * ( int* )( &b ) + i ); &&pFun(); &} &}&&输出结果：&B::g A::f B::h&注意：本题主要考察了面试者对虚函数的理解程度。一个对虚函数不了解的人很难正确的做出本题。在学习面向对象的多态性时一定要深刻理解虚函数表的工作原理。&面试题17：简述类成员函数的重写、重载和隐藏的区别&（1）重写和重载主要有以下几点不同。&范围的区别：被重写的和重写的函数在两个类中，而重载和被重载的函数在同一个类中。&参数的区别：被重写函数和重写函数的参数列表一定相同，而被重载函数和重载函数的参数列表一定不同。&virtual的区别：重写的基类中被重写的函数必须要有virtual修饰，而重载函数和被重载函数可以被virtual修饰，也可以没有。&（2）隐藏和重写、重载有以下几点不同。&与重载的范围不同：和重写一样，隐藏函数和被隐藏函数不在同一个类中。&参数的区别：隐藏函数和被隐藏的函数的参数列表可以相同，也可不同，但是函数名肯定要相同。当参数不相同时，无论基类中的参数是否被virtual修饰，基类的函数都是被隐藏，而不是被重写。&说明：虽然重载和覆盖都是实现多态的基础，但是两者实现的技术完全不相同，达到的目的也是完全不同的，覆盖是动态态绑定的多态，而重载是静态绑定的多态。&面试题18：简述多态实现的原理&编译器发现一个类中有虚函数，便会立即为此类生成虚函数表 vtable。虚函数表的各表项为指向对应虚函数的指针。编译器还会在此类中隐含插入一个指针vptr（对vc编译器来说，它插在类的第一个位置上）指向虚函数表。调用此类的构造函数时，在类的构造函数中，编译器会隐含执行vptr与vtable的关联代码，将vptr指向对应的vtable，将类与此类的vtable联系了起来。另外在调用类的构造函数时，指向基础类的指针此时已经变成指向具体的类的this指针，这样依靠此this指针即可得到正确的vtable，。如此才能真正与函数体进行连接，这就是动态联编，实现多态的基本原理。&注意：一定要区分虚函数，纯虚函数、虚拟继承的关系和区别。牢记虚函数实现原理，因为多态C++面试的重要考点之一，而虚函数是实现多态的基础。&面试题19：链表和数组有什么区别&数组和链表有以下几点不同：&（1）存储形式：数组是一块连续的空间，声明时就要确定长度。链表是一块可不连续的动态空间，长度可变，每个结点要保存相邻结点指针。&（2）数据查找：数组的线性查找速度快，查找操作直接使用偏移地址。链表需要按顺序检索结点，效率低。&（3）数据插入或删除：链表可以快速插入和删除结点，而数组则可能需要大量数据移动。&（4）越界问题：链表不存在越界问题，数组有越界问题。&说明：在选择数组或链表数据结构时，一定要根据实际需要进行选择。数组便于查询，链表便于插入删除。数组节省空间但是长度固定，链表虽然变长但是占了更多的存储空间。&面试题20：怎样把一个单链表反序&（1）反转一个链表。循环算法。&List reverse(List & n) &{ &&if(!n) & & & //判断链表是否为空，为空即退出。&& { && &}&& list cur = n. &//保存头结点的下个结点 &&list pre = & & //保存头结点&&& pre.next = & & //头结点的指针指空，转换后变尾结点 &while ( NULL != cur.next ) & //循环直到cur.next为空 &{ &&tmp = &//实现如图10.3—图10.5所示&& tmp.next = pre & &&pre =&& & cur = cur. &}&& &&//f返回头指针&}&（2）反转一个链表。递归算法。&List *reverse( List *oldList, List *newHead = NULL ) &{ &List *next = oldList-& & //记录上次翻转后的链表 &oldList-& next = newH & //将当前结点插入到翻转后链表的开头 &newHead = oldL & & //递归处理剩余的链表 &&return ( next==NULL )? newHead: reverse( t, newHead ); &}&说明：循环算法就是图10.2—图10.5的移动过程，比较好理解和想到。递归算法的设计虽有一点难度，但是理解了循环算法，再设计递归算法就简单多了。&面试题 21：简述队列和栈的异同&队列和栈都是线性存储结构，但是两者的插入和删除数据的操作不同，队列是“先进先出”，栈是“后进先出”。&注意：区别栈区和堆区。堆区的存取是“顺序随意”，而栈区是“后进先出”。栈由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。堆一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收。分配方式类似于链表。&它与本题中的堆和栈是两回事。堆栈只是一种数据结构，而堆区和栈区是程序的不同内存存储区域。&面试题22：能否用两个栈实现一个队列的功能&结点结构体：&typedef struct node&{ & &node *&}node,*LinkS&创建空栈：&LinkStack CreateNULLStack( LinkStack &S)&{ &S = (LinkStack)malloc( sizeof( node ) ); & & //申请新结点&& if( NULL == S)&& { &&printf(&Fail to malloc a new node./n&);&& return NULL;&&}&& S-&data = 0; & & & & //初始化新结点&& S-&next = NULL; &&return S;&}&栈的插入函数：&LinkStack Push( LinkStack &S, int data)&{ &if( NULL == S) & & & //检验栈&& { &&printf(&There no node in stack!&); &&return NULL;&& }&& LinkStack p = NULL;&& p = (LinkStack)malloc( sizeof( node ) );&//申请新结点&& if( NULL == p) &{ &&printf(&Fail to malloc a new node./n&); &&return S;&&}&& if( NULL == S-&next) &{ &&p-&next = NULL; &} &else &{ &&p-&next = S-& &}&& p-&data = & & & //初始化新结点 &S-&next = & & //插入新结点 &&return S;&}&出栈函数：&node Pop( LinkStack &S)&{ & &temp.data = 0; &temp.next = NULL; &&if( NULL == S) & & & //检验栈&& { &&printf(&There no node in stack!&); &&&&}&& temp = *S;&& if( S-&next == NULL )&&{ &&printf(&The stack is NULL,can't pop!/n&); && &&}&& LinkStack p = S -& &//节点出栈&& S-&next = S-&next-& &temp = *p; &&free( p ); &p = NULL; && &&}&双栈实现队列的入队函数：&LinkStack StackToQueuPush( LinkStack &S, int data)&{ & &LinkStack S1 = NULL;&&CreateNULLStack( S1 ); & & &//创建空栈 &&& while( NULL != S-&next ) &&//S出栈入S1&& { &&n = Pop( S ); &&Push( S1, n.data ); &}&& Push( S1, data ); & & & &//新结点入栈&& while( NULL != S1-&next ) &&//S1出栈入S&& { &&n = Pop( S1 ); &&Push( S, n.data );&& }&& return S;&}&说明：用两个栈能够实现一个队列的功能，那用两个队列能否实现一个队列的功能呢？结果是否定的，因为栈是先进后出，将两个栈连在一起，就是先进先出。而队列是现先进先出，无论多少个连在一起都是先进先出，而无法实现先进后出。&面试题23：计算一颗二叉树的深度&深度的计算函数：&int depth(BiTree T)&{ &if(!T)&return 0; & & &//判断当前结点是否为叶子结点&& int d1= depth(T-&lchild); & &//求当前结点的左孩子树的深度 &int d2= depth(T-&rchild); &//求当前结点的右孩子树的深度&& return (d1&d2?d1:d2)+1;&}&注意：根据二叉树的结构特点，很多算法都可以用递归算法来实现。&面试题24：编码实现直接插入排序&直接插入排序编程实现如下：&#include&iostream.h&&void main( void )&{ &int ARRAY[10] = { 0, 6, 3, 2, 7, 5, 4, 9, 1, 8 }; &&int i,j; &for( &i = 0; i & 10; i++) &{ &&cout&&ARRAY[i]&&& &;&&} &&cout&& &&for( i = 2; i &= 10; i++ ) & &//将ARRAY[2],…,ARRAY[n]依次按序插入 &{ & & &if(ARRAY[i] & ARRAY[i-1]) & //如果ARRAY[i]大于一切有序的数值， & & & & &//ARRAY[i]将保持原位不动&& { &&&ARRAY[0] = ARRAY[i]; &//将ARRAY[0]看做是哨兵,是ARRAY[i]的副本&& & j = i - 1;&& & do{ & & &//从右向左在有序区ARRAY[1．．i-1]中 & & & & &//查找ARRAY[i]的插入位置&& & ARRAY[j+1] = ARRAY[j]; &//将数值大于ARRAY[i]记录后移 & &j--; && & }while( ARRAY[0] & ARRAY[j] ); & &&ARRAY[j+1]=ARRAY[0]; &//ARRAY[i]插入到正确的位置上&& }&& }&& for( &i = 0; i & 10; i++)&& { &&cout&&ARRAY[i]&&& &;&&}&&cout&&&}注意：所有为简化边界条件而引入的附加结点（元素）均可称为哨兵。引入哨兵后使得查找循环条件的时间大约减少了一半，对于记录数较大的文件节约的时间就相当可观。类似于排序这样使用频率非常高的算法，要尽可能地减少其运行时间。所以不能把上述算法中的哨兵视为雕虫小技。面试题25：编码实现冒泡排序&冒泡排序编程实现如下：&#include &stdio.h&&#define LEN 10 &&&//数组长度&void main( void )&{ &int ARRAY[10] = { 0, 6, 3, 2, 7, 5, 4, 9, 1, 8 }; //待排序数组 &printf( &/n& );&& for( int a = 0; a & LEN; a++ )&//打印数组内容&& { &&printf( &%d &, ARRAY[a] ); &}&& int i = 0; &int j = 0;&& bool isC & & & //设定交换标志&& for( i = 1; i & LEN; i++ ) &{ & & & & //最多做LEN-1趟排序&& isChange = 0; & & &//本趟排序开始前,交换标志应为假&& for( j = LEN-1; j &= j-- ) &&//对当前无序区ARRAY[i..LEN]自下向上扫描&& { & &if( ARRAY[j+1] & ARRAY[j] ) & &&{ & & & //交换记录&& & ARRAY[0] = ARRAY[j+1]; &//ARRAY[0]不是哨兵,仅做暂存单元&& & ARRAY[j+1] = ARRAY[j]; & &&ARRAY[j] = ARRAY[0]; & &isChange = 1; & &//发生了交换,故将交换标志置为真&& & } &&}&& printf( &/n& );&& for( a = 0; a & LEN; a++) &//打印本次排序后数组内容&& { & &printf( &%d &, ARRAY[a] ); &&}&&&if( !isChange ) & &&//本趟排序未发生交换,提前终止算法&& { & & &&} &} && printf( &/n& ); &&}&面试题26：编码实现直接选择排序&#include&stdio.h&&#define LEN 9&void main( void )&{ &int ARRAY[LEN]={ 5, 6, 8, 2, 4, 1, 9, 3, 7 }; & //待序数组&& printf(&Before sorted:/n&);&& for( int m = 0; m & LEN; m++ ) & & &//打印排序前数组&& { &&printf( &%d &&, ARRAY[m] ); &}&& for (int i = 1; i &= LEN - 1; i++) &//选择排序&& { &&int t = i - 1; & &int temp = 0; & &for (int j = j & LEN; j++) & &{ & &if (ARRAY[j] & ARRAY[t]) &&{ & & &t = & &&} &&&} & &if (t != (i - 1)) &&{ & &&temp = ARRAY[i - 1]; & &ARRAY[i - 1] = ARRAY[t]; & &ARRAY[t] = &&} &}&& printf( &/n& );&& printf(&After sorted:/n&); &for( i = 0; i & LEN; i++ ) & & & //打印排序后数组&& { &&printf( &%d &&, ARRAY[i] ); &}&& printf( &/n& );&}&注意：在直接选择排序中，具有相同关键码的对象可能会颠倒次序，因而直接选择排序算法是一种不稳定的排序方法。在本例中只是例举了简单的整形数组排序，肯定不会有什么问题。但是在复杂的数据元素序列组合中，只是根据单一的某一个关键值排序，直接选择排序则不保证其稳定性，这是直接选择排序的一个弱点面试题27：编程实现堆排序&堆排序编程实现：&#include &stdio.h&&void createHeep(int ARRAY[],int sPoint, int Len) &//生成大根堆&{ &while( ( 2 * sPoint + 1 ) & Len ) &{ &&int mPoint = 2 * sPoint + 1; & &if( ( 2 * sPoint + 2 ) & Len ) &&{ & &&if(ARRAY[ 2 * sPoint + 1 ] & ARRAY[ 2 * sPoint + 2 ] ) & &{ & &&mPoint = 2*sPoint+2; & &} &&} &&if(ARRAY[ sPoint ] & ARRAY[ mPoint ]) & //堆被破坏，需要重新调整 &&{ & &int tmpData= ARRAY[ sPoint ]; &//交换sPoint与mPoint的数据&& & ARRAY[ sPoint ] = ARRAY[ mPoint ]; & &ARRAY[ mPoint ] = tmpD&& & sPoint = mPoint & &&}&& else & &&{ && &&//堆未破坏，不再需要调整 && }&& } &&} &&void heepSort( int ARRAY[], int Len ) & & &//堆排序&{ &int i=0;&& for ( i = ( Len / 2 - 1 ); i &= 0; i-- ) & & //将Hr[0，Lenght-1]建成大根堆&& { &&createHeep(ARRAY, i, Len); &}&& for ( i = Len - 1; i & 0; i-- ) &{ &&int tmpData = ARRAY[0]; & & &//与最后一个记录交换&& ARRAY[0] = ARRAY[i]; &&ARRAY[i] = tmpD &&createHeep( ARRAY, 0, i );&//将H.r[0..i]重新调整为大根堆 &&& } &&&} &int main( void )&{ &int ARRAY[] ={ 5, 4, 7, 3, 9, 1, 6, 8, 2}; &&printf(&Before sorted:/n&); &&//打印排序前数组内容&& for ( int i = 0; i & 9; i++ ) &{ &&printf(&%d &, ARRAY[i]); &}&& printf(&/n&);&& heepSort( ARRAY, 9 ); & & & //堆排序&&&& printf(&After sorted:/n&);&//打印排序后数组内容&& for( i = 0; i & 9; i++ ) &{ &&printf( &%d &, ARRAY[i] ); &&}&& printf( &/n& ); &return 0;&}&说明：堆排序，虽然实现复杂，但是非常的实用。另外读者可是自己设计实现小堆排序的算法。虽然和大堆排序的实现过程相似，但是却可以加深对堆排序的记忆和理解。面试题28：编程实现基数排序&#include &stdio.h&&#include &malloc.h&&#define LEN 8&typedef struct node & & & //队列结点&{ & &struct node *&}node,*QueueN &typedef struct Queue &&//队列&{ &QueueN &QueueN&}Queue,*QueueL &QueueLink CreateNullQueue( QueueLink &Q) &//创建空队列&{ &Q = NULL;&& Q = ( QueueLink )malloc( sizeof( Queue ) ); &if( NULL == Q ) &{ &&printf(&Fail to malloc null queue!/n&); &&return NULL; &}& Q-&front = ( QueueNode )malloc( sizeof( node ) ); &Q-&rear &= ( QueueNode )malloc( sizeof( node ) ); &if( NULL == Q-&front || NULL == Q-&rear ) &{ &&printf(&Fail to malloc a new queue's fornt or rear!/n&); &&return NULL; &} &Q-&rear = NULL; &Q-&front-&next= Q-& & &return Q;&}&int lenData( node data[], int len) & & //计算队列中各结点的数据的最大位数&{ &int m = 0; &int temp = 0; & &for( int i = 0; i & i++) &{ &&d = data[i]. &&while( d & 0) &&{ & &d /= 10; & &temp ++; &&} &&if( temp & m ) &&{ & &m = &&} &&temp = 0; &} &&}&QueueLink Push( QueueLink &Q , node node ) &//将数据压入队列&{ &QueueNode p1,p;&& p =( QueueNode )malloc( sizeof( node ) ); &if( NULL == p ) &{ &&printf(&Fail to malloc a new node!/n&); &&return NULL; &}&& p1 = Q-&&& while(p1-&next != NULL) &{p1 = p1-& &}&& p-&data = node. &p1-&next =&& p-&next = Q-&&& return NULL;&}&node Pop( QueueLink &Q)&//数据出队列&{ & &temp.data = 0; &temp.next = NULL; &QueueN &p = Q-&front-& &if( p != Q-&rear ) &{ &&temp = *p; &&Q-&front-&next = p-& &&free( p ); &&p = NULL; &} &&}&int IsEmpty( QueueLink Q)&{ &if( Q-&front-&next == Q-&rear ) &{ &&return 0; &} &return 1;&}&int main( void )&{ &&int i = 0; &int Max = 0; & & & //记录结点中数据的最大位数&& int d = 10; &int power = 1; &int k = 0;&& node Array[LEN] ={{450, NULL}, {32,NULL}, { 781,NULL}, { 57 ,NULL}, & & && & &&{145,NULL},{ 613,NULL},{ 401,NULL},{ 594,NULL}}; &&//队列结点数组&& QueueLink Queue[10];&& for( i = 0; i & 10; i++) &{CreateNullQueue( Queue[i]); & //初始化队列数组&& }&& for( i = 0; i & LEN; i++) &{ &&printf(&%d &&,Array[i].data); &} &&printf(&/n&); &&Max = lenData( Array, LEN ); & &//计算数组中关键字的最大位数&& printf(&%d/n&,Max);&& for(int j = 0; j & M j++) & & //按位排序&& { &&if(j == 0) power = 1; &&else power = power *d;&& & for(i = 0; i & LEN; i++) &&{ & &k = Array[i].data /power - (Array[i].data/(power * d)) * & &Push( Queue[k], Array[i] ); &&} &&&& for(int l = 0, k = 0; l & l++) & //排序后出队列重入数组 &&{ & &while( IsEmpty( Queue[l] ) ) &&&{ & &&Array[k++] = Pop( Queue[l] ); & &} &&}&& for( int t = 0; t & LEN; t++) &&{ & &printf(&%d &&,Array[t].data); &&}&& printf(&/n&);&}&& return 0;&}&说明：队列为基数排序的实现提供了很大的方便，适当的数据机构可以减少算法的复杂度，让更多的算法实现更容易。面试题29：谈谈你对编程规范的理解或认识&编程规范可总结为：程序的可行性，可读性、可移植性以及可测试性。&说明：这是编程规范的总纲目，面试者不一定要去背诵上面给出的那几个例子，应该去理解这几个例子说明的问题，想一想，自己如何解决可行性、可读性、可移植性以及可测试性这几个问题，结合以上几个例子和自己平时的编程习惯来回答这个问题。&面试题30：short i = 0; i = i + 1L；这两句有错吗&代码一是错的，代码二是正确的。&说明：在数据安全的情况下大类型的数据向小类型的数据转换一定要显示的强制类型转换。&面试题31：&&和&、||和|有什么区别&（1）&和|对操作数进行求值运算，&&和||只是判断逻辑关系。&（2）&&和||在在判断左侧操作数就能确定结果的情况下就不再对右侧操作数求值。&注意：在编程的时候有些时候将&&或||替换成&或|没有出错，但是其逻辑是错误的，可能会导致不可预想的后果（比如当两个操作数一个是1另一个是2时）。&面试题32：C++的引用和C语言的指针有什么区别&指针和引用主要有以下区别：&（1）引用必须被初始化，但是不分配存储空间。指针不声明时初始化，在初始化的时候需要分配存储空间。&（2）引用初始化以后不能被改变，指针可以改变所指的对象。&（3）不存在指向空值的引用，但是存在指向空值的指针。&注意：引用作为函数参数时，会引发一定的问题，因为让引用作参数，目的就是想改变这个引用所指向地址的内容，而函数调用时传入的是实参，看不出函数的参数是正常变量，还是引用，因此可能会引发错误。所以使用时一定要小心谨慎。面试题33：在二元树中找出和为某一值的所有路径&输入一个整数和一棵二元树。从树的根结点开始往下访问，一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。例如，输入整数9和如下二元树：&& & & & & & & & & & &3 & & & & & & & & & &&&&/ & / & & & & & & & & &&& & & & & & & & & 2 & & 6&& & & & & & & & &/ &/ & & & & & & & && & & & & & & &5 & & 4&则打印出两条路径：3，6和3，2，4。&【答案】&typedef struct path&{ &BiTNode* &&//结点数据成员 &struct path* & & &//结点指针成员&}PATH,*pP&初始化树的结点栈：&void init_path( pPath* L )&{ &*L = ( pPath )malloc( sizeof( PATH ) ); &//创建空树&& ( *L )-&next = NULL; &}&树结点入栈函数：&void push_path(pPath H, pBTree T)&{ &pPath p = H-& &pPath q = H; &&while( NULL != p )&& { &&q =&& p = p-&&& }&& p = ( pPath )malloc( sizeof( PATH ) ); &//申请新结点&& p-&next = NULL; & & //初始化新结点&& p-&tree = T; & &q-&next = &&&//新结点入栈&}&树结点打印函数：&void print_path( pPath L )&{ &pPath p = L-& & &while( NULL != p ) & & //打印当前栈中所有数据&& { &&printf(&%d, &, p-&tree-&data); &&p = p-& && } &}&树结点出栈函数：&void pop_path( pPath H )&{ &pPath p = H-& &pPath q = H; &&if( NULL == p ) & & &//检验当前栈是否为空&& { &&printf(&Stack is null!/n&); && &}&& p = p-&&& while( NULL != p ) & & //出栈&& { &&q = q-& &&p = p-& &}&& free( q-&next ); & & &//释放出栈结点空间&& q-&next = NULL; &}&判断结点是否为叶子结点：&int IsLeaf(pBTree T)&{ &return ( T-&lchild == NULL )&&( T-&rchild==NULL );&}&查找符合条件的路径：&int find_path(pBTree T, int sum, pPath L)&{ &push_path( L, T); &record += T-& && if( ( record == sum ) && ( IsLeaf( T ) ) ) &//打印符合条件的当前路径&& { &&print_path( L ); & &printf( &/n& ); && }&& if( T-&lchild != NULL ) & & //递归查找当前节点的左孩子&& { &&find_path( T-&lchild, sum, L); &}&& if( T-&rchild != NULL ) & & &//递归查找当前节点的右孩子&& { &&find_path( T-&rchild, sum, L);&}&& record -= T-& &&pop_path(L); &&return 0;&}&注意：数据结构一定要活学活用，例如本题，把所有的结点都压入栈，而不符合条件的结点弹出栈，很容易实现了有效路径的查找。虽然用链表也可以实现，但是用栈更利于理解这个问题，即适当的数据结构为更好的算法设计提供了有利的条件。&面试题34：写一个“标准”宏MIN&写一个“标准”宏MIN，这个宏输入两个参数并且返回较小的一个。&【答案】&#define min(a,b)((a)&=(b)?(a):(b))&注意：在调用时一定要注意这个宏定义的副作用，如下调用： &((++*p)&=(x)?(++*p):(x)。&p指针就自加了两次，违背了MIN的本意。&面试题35：typedef和define有什么区别&（1）用法不同：typedef用来定义一种数据类型的别名，增强程序的可读性。define主要用来定义常量，以及书写复杂使用频繁的宏。&（2）执行时间不同：typedef是编译过程的一部分，有类型检查的功能。define是宏定义，是预编译的部分，其发生在编译之前，只是简单的进行字符串的替换，不进行类型的检查。&（3）作用域不同：typedef有作用域限定。define不受作用域约束，只要是在define声明后的引用都是正确的。&（4）对指针的操作不同：typedef和define定义的指针时有很大的区别。&注意：typedef定义是语句，因为句尾要加上分号。而define不是语句，千万不能在句尾加分号。面试题36：关键字const是什么&const用来定义一个只读的变量或对象。主要优点：便于类型检查、同宏定义一样可以方便地进行参数的修改和调整、节省空间，避免不必要的内存分配、可为函数重载提供参考。&说明：const修饰函数参数，是一种编程规范的要求，便于阅读，一看即知这个参数不能被改变，实现时不易出错。&面试题37：static有什么作用&static在C中主要用于定义全局静态变量、定义局部静态变量、定义静态函数。在C++中新增了两种作用：定义静态数据成员、静态函数成员。&注意：因为static定义的变量分配在静态区，所以其定义的变量的默认值为0，普通变量的默认值为随机数，在定义指针变量时要特别注意。&面试题38：extern有什么作用&extern标识的变量或者函数声明其定义在别的文件中，提示编译器遇到此变量和函数时在其它模块中寻找其定义。&面试题39：流操作符重载为什么返回引用&在程序中，流操作符&&和&&经常连续使用。因此这两个操作符的返回值应该是一个仍旧支持这两个操作符的流引用。其他的数据类型都无法做到这一点。&注意：除了在赋值操作符和流操作符之外的其他的一些操作符中，如+、-、*、/等却千万不能返回引用。因为这四个操作符的对象都是右值，因此，它们必须构造一个对象作为返回值。&面试题40：简述指针常量与常量指针区别&指针常量是指定义了一个指针，这个指针的值只能在定义时初始化，其他地方不能改变。常量指针是指定义了一个指针，这个指针指向一个只读的对象，不能通过常量指针来改变这个对象的值。&指针常量强调的是指针的不可改变性，而常量指针强调的是指针对其所指对象的不可改变性。&注意：无论是指针常量还是常量指针，其最大的用途就是作为函数的形式参数，保证实参在被调用函数中的不可改变特性。&面试题41：数组名和指针的区别&请写出以下代码的打印结果：&#include &iostream.h&&#include &string.h&&void main(void)&{ &char str[13]=&Hello world!&;&& char *pStr=&Hello world!&; &&&cout&&sizeof(str)&& &cout&&sizeof(pStr)&& &cout&&strlen(str)&& &cout&&strlen(pStr)&& &&&}&【答案】 打印结果：&13 4 12 12&注意：一定要记得数组名并不是真正意义上的指针，它的内涵要比指针丰富的多。但是当数组名当做参数传递给函数后，其失去原来的含义，变作普通的指针。另外要注意sizeof不是函数，只是操作符。&面试题42：如何避免“野指针”&“野指针”产生原因及解决办法如下：&（1）指针变量声明时没有被初始化。解决办法：指针声明时初始化，可以是具体的地址值，也可让它指向NULL。&（2）指针 p 被 free 或者 delete 之后，没有置为 NULL。解决办法：指针指向的内存空间被释放后指针应该指向NULL。&（3）指针操作超越了变量的作用范围。解决办法：在变量的作用域结束前释放掉变量的地址空间并且让指针指向NULL。&注意：“野指针”的解决方法也是编程规范的基本原则，平时使用指针时一定要避免产生“野指针”，在使用指针前一定要检验指针的合法性。&面试题43：常引用有什么作用&常引用的引入主要是为了避免使用变量的引用时，在不知情的情况下改变变量的值。常引用主要用于定义一个普通变量的只读属性的别名、作为函数的传入形参，避免实参在调用函数中被意外的改变。&说明：很多情况下，需要用常引用做形参，被引用对象等效于常对象，不能在函数中改变实参的值，这样的好处是有较高的易读性和较小的出错率。&面试题44：编码实现字符串转化为数字&编码实现函数atoi()，设计一个程序，把一个字符串转化为一个整型数值。例如数字：“5486321”，转化成字符：5486321。&【答案】&int myAtoi(const char * str){&&int num = 0; & & & //保存转换后的数值&& int isNegative = 0; &&//记录字符串中是否有负号&& int n =0;&&char *p = &if(p == NULL) & & & //判断指针的合法性&&{return -1; &}&&while(*p++ != '/0') & & &//计算数字符串度&&{n++; &}&&p =&& if(p[0] == '-') & & & //判断数组是否有负号&&{ &&isNegative = 1;&&}&char temp = '0';&&for(int i = 0 &i & i++) &{char temp = *p++; &&if(temp & '9' ||temp & '0') & &//滤除非数字字符&& {&}&& if(num !=0 || temp != '0') & &//滤除字符串开始的0字符 &&{ &&& temp -= 0x30;&&//将数字字符转换为数值&& & &num += temp *int( pow(10 , n - 1 -i) ); &&}&} &&if(isNegative) & & & &//如果字符串中有负号，将数值取反&{ &&return (0 - num); &} &else&{ && & & & //返回转换后的数值&&}&}&注意：此段代码只是实现了十进制字符串到数字的转化，读者可以自己去实现2进制，8进制，10进制，16进制的转化。&面试题45：简述strcpy、sprintf与memcpy的区别&三者主要有以下不同之处：&（1）操作对象不同，strcpy的两个操作对象均为字符串，sprintf的操作源对象可以是多种数据类型，目的操作对象是字符串，memcpy 的两个对象就是两个任意可操作的内存地址，并不限于何种数据类型。&（2）执行效率不同，memcpy最高，strcpy次之，sprintf的效率最低。&（3）实现功能不同，strcpy主要实现字符串变量间的拷贝，sprintf主要实现其他数据类型格式到字符串的转化，memcpy主要是内存块间的拷贝。&说明：strcpy、sprintf与memcpy都可以实现拷贝的功能，但是针对的对象不同，根据实际需求，来选择合适的函数实现拷贝功能。&面试题46：用C编写一个死循环程序&while(1) { }&说明：很多种途径都可实现同一种功能，但是不同的方法时间和空间占用度不同，特别是对于嵌入式软件，处理器速度比较慢，存储空间较小，所以时间和空间优势是选择各种方法的首要考虑条件。&面试题47：编码实现某一变量某位清0或置1&给定一个整型变量a，写两段代码，第一个设置a的bit 3，第二个清a的bit 3，在以上两个操作中，要保持其他位不变。&【答案】&#define BIT3 (0x1 && 3 ) S&设置a的bit 3:&void set_bit3( void ) { &a |= BIT3; & & &//将a第3位置1&}&清a的bit 3&void set_bit3( void ) { &a &= ~BIT3; & & &//将a第3位清零&}&说明：在置或清变量或寄存器的某一位时，一定要注意不要影响其他位。所以用加减法是很难实现的。&面试题48：评论下面这个中断函数&中断是嵌入式系统中重要的组成部分，这导致了很多编译开发商提供一种扩展——让标准C支持中断。具体代表事实是，产生了一个新的关键字__interrupt。下面的代码就使用了__interrupt关键字去定义一个中断服务子程序(ISR)，请评论以下这段代码。&__interrupt double compute_area (double radius)&&{ &double area = PI * radius * &printf(& Area = %f&, area); & &}&【答案】&这段中断服务程序主要有以下四个问题：&（1）ISR 不能返回一个值。&（2）ISR 不能传递参数。&（3）在ISR 中做浮点运算是不明智的。&（4）printf()经常有重入和性能上的问题。&注意：本题的第三个和第四个问题虽不是考察的重点，但是如果能提到这两点可给面试官留下一个好印象。&面试题49：构造函数能否为虚函数&构造函数不能是虚函数。而且不能在构造函数中调用虚函数，因为那样实际执行的是父类的对应函数，因为自己还没有构造好。析构函数可以是虚函数，而且，在一个复杂类结构中，这往往是必须的。析构函数也可以是纯虚函数，但纯虚析构函数必须有定义体，因为析构函数的调用是在子类中隐含的。&说明：虚函数的动态绑定特性是实现重载的关键技术，动态绑定根据实际的调用情况查询相应类的虚函数表，调用相应的虚函数。&面试题50：谈谈你对面向对象的认识&面向对象可以理解成对待每一个问题，都是首先要确定这个问题由几个部分组成，而每一个部分其实就是一个对象。然后再分别设计这些对象，最后得到整个程序。传统的程序设计多是基于功能的思想来进行考虑和设计的，而面向对象的程序设计则是基于对象的角度来考虑问题。这样做能够使得程序更加的简洁清晰。&说明：编程中接触最多的“面向对象编程技术”仅仅是面向对象技术中的一个组成部分。发挥面向对象技术的优势是一个综合的技术问题，不仅需要面向对象的分析，设计和编程技术，而且需要借助必要的建模和开发工具。}