数据结构之栈、队列、字符串——软件测试工程师面试秘籍(06)

发表于:2021-11-19 09:35

字体: | 上一篇 | 下一篇 | 我要投稿

 作者:G. li    来源:51Testing软件测试网原创

#
面试
#
求职
分享:
  2.1.2  栈、队列、字符串
  考点:
  ·栈、队列的概念及特点
  ·函数如何压栈
  ·字符串复制、反转等操作

  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所示。
图2.5  栈

图2.6  栈和EBP的情况

  函数参数入栈时,按照从右到左的顺序,并要注意高地址和低地址。入栈时以机器字长为单位且所有参数按字对齐。

  2.队列
  队列又称先进先出(First In First Out,FIFO)线性表,它的所有插入操作(又称入队)在队列的一端,而删除操作(又称出队)在队列的另一端,如图2.7所示。
图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软件测试网获得人民邮电出版社和作者授权连载本书部分章节。
任何个人或单位未获得明确的书面许可,不得对本文内容复制、转载或进行镜像,否则将追究法律责任。
《2023软件测试行业现状调查报告》独家发布~

关注51Testing

联系我们

快捷面板 站点地图 联系我们 广告服务 关于我们 站长统计 发展历程

法律顾问:上海兰迪律师事务所 项棋律师
版权所有 上海博为峰软件技术股份有限公司 Copyright©51testing.com 2003-2024
投诉及意见反馈:webmaster@51testing.com; 业务联系:service@51testing.com 021-64471599-8017

沪ICP备05003035号

沪公网安备 31010102002173号