데이터 구조 면접 문제 (답안 포함)
1. （ ）
4. （ ）
5. （D）
A. B. C. D.
6. （B）A. B.
C. D.
7. （ ）
8. ， （ ）
9. （ ）
10. L＝（a1,a2,a3,……ai,……an）， （D）
A. B.
C.
D. ，
11. ， （D）
A. B. C. D.
12. （ 、 ）
13. ， （ 1）
14. 5 ， （31）
15. 3 （5 ）
16. 3 ， 8 1 ， （13）
17. dabec， debac， （cedba）
18. ABDEGCFH DBGEACHF， （DGEBHFCA）
19. abdgcefh， dgbaechf， （gdbehfca）
20. ： 、 、 。 1. ， （ ）
2. ， （ ）
： ： 、 、 。
3. （ 、 、 ）
4. （ ）
5. （ ）
6. （ ）
7. （C）
A．
B． （ ）
C．
D．
8. ， 、 ， （ ）
9. ， （C）
A． B． C． D．
10. ， （B）
A．
B．
C．
D．
11. （ ）
12. （ ）
13. ， （ ）
14. （C）A． B． C． D．
15. ， （B）
A． B． C． D．
16. （ ） 。
17. （D）A． B．
C． D．
20. （ ， ）
21. ， ， ， （ ） ， ， 。
22. （C）A． B． C． D． 23. ， （D）A．
B． C． ， D． ，
24. （A）A． B．
C． D．
25. L＝（a1,a2,a3,……ai,……an）， （D）
A． B．
C． D． ，
26. ， （ ）
27. （B）A． B．
C． D．
28. head （ p ）， （p->next=head）
29. ， （ ）
30. （D） ， ， 。A． B． C． D．
31. （C）A． B． C． D．
32. ， （ 1）
33. 3 （5 ）
34. 8 （128） ：2K-1
35. 5 ， （16） ：2n-1
36. 5 ， （31） 。 ：2n－1
37. 699 ， （350）
： N， N ， （N+1）/2； N ， N/2。
38. ， （B）
A．ABCDEF
B．DBEAFC
C．ABDECF
D．DEBFCA
39. dabec， debac， （cedba）
40. ABDEGCFH DBGEACHF， （DGEBHFCA）
41. abdgcefh， dgbaechf， （gdbehfca）42. （ ）
43. p q， q p （ ）
44. N （N-1）
45.N （N）
46. n ， （N）
47. （ ）
48. n， ， （n(n-1)/2）
49. ， （ ）
50. ， （ ）
51. （ ）
52. （ ）
53. ， （ ）
54. A ， ， （ ）
55. 、 、 。1. ： ， 。
1. 。
2. 。
3. ， 、 、 、 ， 。
4. 。
5. ， 。
6. 。
7. 、 。
8. 。
9. 。
10. 、 、 。
11. 。
12. ： 、 。
13. ： 。
14. ， ， 。
15. 。
16. ， 。
17. ： 。 ， 1 。
18. ， ， 。 。
19. ， ， 。
20. 25 ， front=16， rear=9， 18 。 ： rear<front ， ＝ －（front－rear）；
rear>front ， ＝rear－front。1. ： ， ：
N1->N2->N3->N4->N5->N2 ， N5 。 p1，p2。 p1 ，p2 。 p2 NULL 。 。 struct link { int data; link* next;};bool IsLoop(link* head){ link* p1=head, *p2 = head; if (head ==NULL || head->next ==NULL) { return false; } do{ p1= p1->next; p2 = p2->next->next; } while(p2 && p2->next && p1!=p2); if(p1 == p2) return true; else return false;}2, ， 。 ： 1->2->3->4->5 5->4->3->2->1。 ， ， ， ， 。 ： struct linka { int data; linka* next;};void reverse(linka*& head){ if(head ==NULL) return; linka*pre, *cur, *ne; pre=head; cur=head->next; while(cur) { ne = cur->next; cur->next = pre; pre = cur; cur = ne; } head->next = NULL; head = pre;} 。 。 。 ， ， next NULL。 head ， 。 ： linka* reverse(linka* p,linka*& head){ if(p == NULL || p->next == NULL) { head=p; return p; } else { linka* tmp = reverse(p->next,head); tmp->next = p; return p; }}3, ， ？
O(nlogn) 。 ， ， ， binary search。 C++ ： bool findcommon(int a[],int size1,int b[],int size2){ int i; for(i=0;i<size1;i++) { int start=0,end=size2-1,mid; while(start<=end) { mid=(start+end)/2; if(a[i]==b[mid]) return true; else if (a[i]<b[mid]) end=mid-1; else start=mid+1; } } return false;} O(n) 。 。 。 ， ， 。 ， ， ， ， 。 bool findcommon2(int a[], int size1, int b[], int size2){ int i=0,j=0; while(i<size1 && j<size2) { if(a[i]==b[j]) return true; if(a[i]>b[j]) j++; if(a[i]<b[j]) i++; } return false;}4, ：
A1， A2，... An （ ）， A1~An Ai~Aj， Ai Aj
：
-2, 11, -4, 13, -5, 2, -5, -3, 12, -9 21。
， 。 ， 。 O(n^3)。 ， O(n) ， Programming Pearls 。 ， ， O(n^2)。 ： 。 Sum(i, j) A[i] ... A[j] ， Sum(i, j+1) = Sum(i, j) + A[j+1]。 ， ： int max_sub(int a[],int size){ int i,j,v,max=a[0]; for(i=0;i<size;i++) { v=0; for(j=i;j<size;j++) { v=v+a[j];//Sum(i, j+1) = Sum(i, j) + A[j+1] if(v>max) max=v; } } return max;} ？ 。 ： int max_sub2(int a[], int size){ int i,max=0,temp_sum=0; for(i=0;i<size;i++) { temp_sum+=a[i]; if(temp_sum>max) max=temp_sum; else if(temp_sum<0) temp_sum=0; } return max;} 6, ， ， ， 。 ：
Here is www.fishksy.com.cn
：
www.fishksy.com.cn is Here
， ， ， ， 。 ， ， 。 。
char* reverse_word(const char* str)
{
int len = strlen(str);
char* restr = new char[len+1];
strcpy(restr,str);
int i,j;
for(i=0,j=len-1;i<j;i++,j--)
{
char temp=restr[i];
restr[i]=restr[j];
restr[j]=temp;
}
int k=0;
while(k<len)
{
i=j=k;
while(restr[j]!=' ' && restr[j]!='' )
j++;
k=j+1;
j--;
for(;i<j;i++,j--)
{
char temp=restr[i];
restr[i]=restr[j];
restr[j]=temp;
}
}
return restr;
}
， 。
char temp=restr[i];
restr[i]=restr[j];
restr[j]=temp;
restr[i]^=restr[j];
restr[j]^=restr[i];
restr[i]^=restr[j];
7, MSN ， ， 。 ， ， ， ， 。 ：
： : "This is fishsky 's Chinese site: http://www.fishsky.com.cn/cn"
: "fishsky"
： "nc/nc.moc.fishsky.www//:ptth :etis esenihC s'fishsky si sihT"
， stack ， 。 stack 。 。 ， 。
， 。 ：
#include <iostream>
#include <cassert>
#include <stack>
using namespace std;
//reverse the string 's1' except the substring 'token'.
const char* reverse(const char* s1, const char* token)
{
assert(s1 && token);
stack<char> 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 = new char[strlen(s1)+1];
int i=0;
while(!stack1.empty())
{
return_v[i++] = stack1.top();
stack1.pop();
}
return_v[i]='';
return return_v;
}
int main(int argc, char* argv[])
{cout<<"This is fishsky 's Chinese site: http://www.fishsky.com.cn/cn
";
cout<<reverse("This is fishsky's Chinese site: http://www. fishsky.com.cn/cn"," fishsky ");
return 0;
}
8, ： ， 0 ， ， ：
1,1,1,2,2,2,2,2,7,7,1,5,5,5,0 1,2,7,1,5,0 ， 。 STL vector。
#include <iostream>
#include <vector>
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[], vector<int>& _st)
{
_st.push_back(a[0]);
for(int i=1;_st[_st.size()-1]!=0;i++)
{
if(a[i-1]!=a[i])
_st.push_back(a[i]);
}
}
， STL， 。 。
void static remove_duplicated2(int a[])
{
if(a[0]==0 || a==NULL)
return;
int insert=1,current=1;
while(a[current]!=0)
{
if(a[current]!=a[current-1])
{
a[insert]=a[current];
insert++;
current++;
}
else
current++;
}
a[insert]=0;
}
9, ： ：
， 1， 。
， 。
template<typename T>
static int Depth(BSTreeNode<T>* pbs)
{
if (pbs==NULL)
return 0;
else
{
int ld = Depth(pbs->left);
int rd = Depth(pbs->right);
return 1 + (ld >rd ? ld : rd);
}
}
1 ：
template<typename T>
static bool isBalance(BSTreeNode<T>* pbs)
{
if (pbs==NULL)
return true;
int dis = Depth(pbs->left) - Depth(pbs->right);
if (dis>1 || dis<-1 )
return false;
else
return isBalance(pbs->left) && isBalance(pbs->right);4.abstract class Something { private abstract String doSomething ();} 이 단락 코드 가 잘못 되 었 습 니까?답: 땡.abstract methods 는 private 로 수식 할 수 없습니다.abstract methods 는 하위 클래스 implement (실현) 의 구체 적 인 세부 사항 을 어떻게 private 로 abstract method 를 봉쇄 할 수 있 습 니까?(같은 이치 로 abstract method 전에는 final 을 추가 할 수 없습니다).5. 아래 코드 세그먼트 가 어디 에 틀 렸 는 지 보 세 요.public class Something { void doSomething () { private String s = ""; int l = s.length(); } } 답: 틀 렸 습 니 다. 부분 변수 앞 에 접근 수정자 (private, public, proctected) 를 놓 을 수 없습니다. final 은 부분 변 수 를 수식 할 수 있 습 니 다. (final 은 abstract 와 strictfp 와 같 습 니 다. 모두 비 접근 수정자 입 니 다. strictfp 는 variable 이 아 닌 class 와 method 만 수식 할 수 있 습 니 다.) private String name; public abstract boolean isStupidName (String name) {} 답: 틀 렸 습 니 다. abstract method 는 괄호 없 이 분점 으로 끝내 야 합 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
