2022年数据结构笔试面试题 .pdf
《2022年数据结构笔试面试题 .pdf》由会员分享,可在线阅读,更多相关《2022年数据结构笔试面试题 .pdf(7页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、数据结构笔试面试题5,找出单向链表的中间结点这道题和解判断链表是否存在环,我用的是非常类似的方法,只不过结束循环的条件和函数返回值不一样罢了。设置两个指针 p1,p2。每次循环 p1 向前走一步,p2 向前走两步。当p2 到达链表的末尾时,p1 指向的时链表的中间。link*mid(link*head)link*p1,*p2;p1=p2=head;if(head=NULL|head-next=NULL)return head;do p1=p1-next;p2=p2-next-next;while(p2&p2-next);return p1;6,按单词反转字符串并不是简单的字符串反转,而是按给定
2、字符串里的单词将字符串倒转过来,就是说字符串里面的单词还是保持原来的顺序,这里的每个单词用空格分开。例如:Here is 经过反转后变为: is Here 如果只是简单的将所有字符串翻转的话,可以遍历字符串,将第一个字符和最后一个交换,第二个和倒数第二个交换,依次循环。其实按照单词反转的话可以在第一遍遍历的基础上,再遍历一遍字符串,对每一个单词再反转一次。这样每个单词又恢复了原来的顺序。char*reverse_word(const char*str)int len=strlen(str);char*restr=new charlen+1;strcpy(restr,str);int i,j;f
3、or(i=0,j=len-1;ij;i+,j-)char temp=restri;restri=restrj;restrj=temp;int k=0;while(klen)名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页,共 7 页 -i=j=k;while(restrj!=&restrj!=)j+;k=j+1;j-;for(;ij;i+,j-)char temp=restri;restri=restrj;restrj=temp;return restr;如果考虑空间和时间的优化的话,当然可以将上面代码里两个字符串交换部分改为异或实现。例如将 char temp=restri;rest
4、ri=restrj;restrj=temp;改为 restri=restrj;restrj=restri;restri=restrj;7,字符串反转我没有记错的话是一道MSN 的笔试题,网上无意中看到的,拿来做了一下。题目是这样的,给定一个字符串,一个这个字符串的子串,将第一个字符串反转,但保留子串的顺序不变。例如:输入:第一个字符串:This is fishsky s Chinese site:http:/ 子串:fishsky 输出:nc/nc.moc.fishsky.www/:ptth:etis esenihC sfishsky si sihT 一般的方法是先扫描一边第一个字符串,然后用
5、stack 把它反转,同时记录下子串出现的位置。然后再扫描一遍把记录下来的子串再用stack 反转。我用的方法是用一遍扫描数组的方法。扫描中如果发现子串,就将子串倒过来压入堆栈。最后再将堆栈里的字符弹出,这样子串又恢复了原来的顺序。源代码如下:#include#include#include using namespace std;/reverse the string s1 except the substring token.const char*reverse(const char*s1,const char*token)assert(s1&token);名师资料总结-精品资料欢迎下载-
6、名师精心整理-第 2 页,共 7 页 -stack stack1;const char*ptoken=token,*head=s1,*rear=s1;while(*head!=)while(*head!=&*ptoken=*head)ptoken+;head+;if(*ptoken=)/contain the token const char*p;for(p=head-1;p=rear;p-)stack1.push(*p);ptoken=token;rear=head;else stack1.push(*rear);head=+rear;ptoken=token;char*return_v=n
7、ew charstrlen(s1)+1;int i=0;while(!stack1.empty()return_vi+=stack1.top();stack1.pop();return_vi=;return return_v;int main(int argc,char*argv)coutThis is fishsky s Chinese site:http:/ is fishskys Chinese site:http:/ 0;8,删除数组中重复的数字名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页,共 7 页 -问题:一个动态长度可变的数字序列,以数字 0 为结束标志,要求将重复的
8、数字用一个数字代替,例如:将数组 1,1,1,2,2,2,2,2,7,7,1,5,5,5,0 转变成 1,2,7,1,5,0 问题比较简单,要注意的是这个数组是动态的。所以避免麻烦我还是用了STL的 vector。#include#include using namespace std;/remove the duplicated numbers in an intger array,the array was end with 0;/e.g.1,1,1,2,2,5,4,4,4,4,1,0-1,2,5,4,1,0 void static remove_duplicated(int a,vect
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年数据结构笔试面试题 2022 数据结构 笔试 试题
限制150内