51Testing软件测试论坛

标题: 数据结构之栈、队列、字符串——软件测试工程师面试秘籍（06） [打印本页]

作者: lsekfe 时间: 2021-11-19 14:29
标题: 数据结构之栈、队列、字符串——软件测试工程师面试秘籍（06）
考点：
　　·栈、队列的概念及特点
　　·函数如何压栈
　　·字符串复制、反转等操作

　　1．栈
　　栈又称后进先出（Last In First Out，LIFO）线性表。限制在栈的一端进行插入或者删除的操作，每次出栈的元素都是栈顶的元素，即最后入栈的元素，如图2.5所示。
　　按照存储方式，栈分为顺序栈和链式栈。顺序栈一般由一维数组和栈顶变量组成。链式栈不会出现栈溢出的情况。
　　函数通过栈来辅助完成调用过程。例如，Z()函数调用A()函数时，首先，将传给A的参数压栈，将现在这条指令（A(…)）的下一条指令的地址压入栈中，以便A()函数执行完后返回Z()函数中继续执行。然后，进入A()函数的内存空间，调用PUSH EBP，即将Z()函数的EPB的内容（地址0x000F）压入栈中。接着，调用MOV EBP ESP，让EBP有一个新的栈顶。最后，将A()函数的局部变量压入栈中，开始执行A()函数的代码。这时，栈和EBP的情况如图2.6所示。
[attach]135388[/attach]
图2.5  栈
[attach]135389[/attach]
图2.6  栈和EBP的情况
　函数参数入栈时，按照从右到左的顺序，并要注意高地址和低地址。入栈时以机器字长为单位且所有参数按字对齐。

　　2．队列
　　队列又称先进先出（First In First Out，FIFO）线性表，它的所有插入操作（又称入队）在队列的一端，而删除操作（又称出队）在队列的另一端，如图2.7所示。
[attach]135390[/attach]
图2.7  队列
队列同样也有顺序队列和链式队列，需要两个变量或指针来指示队头和队尾。在顺序队列中，由于队列的队头和队尾位置是时刻变化的，因此可能会到达队头了，而队尾空出来很多新的空闲区域。而循环队列利用假溢出解决了该问题。到达队头之后，重新回到队尾，当队头指针连接到队尾指针时，视为满队。
　　循环队列次数=(队尾-队头+数组长度)mod(数组长度)
　　3．字符串
　　字符串是面试中常考的内容，也是实际工作中最实用的技术之一。下面列出关于字符串的面试题。
　　试题1．不调用库函数实现字符串复制函数strCpy()。
　　分析：函数声明为strCpy (char * src , const char * des)，其中有如下几点需要注意。
　　（1）src长度为0。
　　（2）src和des地址相同（src==des）。
　　答案：代码如下。

char *strcpy(char *strDest,const char *strSrc)
{
if(strDest==NULL||strSrc==NULL)
return NULL
if(strDest==strSrc)
return strDest
char*tempptr
=
strDest
while((*strDest++=*strSrc++)!
=
'∕0'
)
retum tempptr
}
int strlen(const char*str)
{
assert(strt!=NULL);//断言字符串地址非0
int len;
while((*str++)!='\0')
{ len++; }
return len;
}

复制代码

试题2．编写函数实现整数与字符串之间的相互转化。
　　分析：整数转化成字符串，可以采用加0、然后逆序的方法，整数加0后会隐性转化为字符串；字符串转化成整数，可以采用减0、然后乘以10累加的方法，字符串减0后会隐性转化为整数。

　　试题3．不调用库函数实现字符串反转。
　　答案：代码如下。

package com.others;
publicclassrevertStr {
publicstaticvoid main(String[] args) {
System.out.println(inverse("liuling"));
}
publicstatic String inverse(String str){
char[] chars=str.toCharArray(); //得到字符数组
for (int i=0;i<chars.length/2;i++) {
char temp=chars[i];
chars[i]=chars[chars.length-i-1];
chars[chars.length-i-1]=temp;
}
return String.copyValueOf(chars);
}
}

复制代码

欢迎光临 51Testing软件测试论坛 (http://bbs.51testing.com/)