2. 2016 텐센트 소프트웨어 개발 면접문제(부정항목 선택문제[1-12])

1. 두 갈래 트리를 알고 있습니다. 만약에 먼저 훑어보는 노드의 순서가 ADCEFGHB이고 중간 훑어보는 것이 CDFEGHAB이면 뒤에 훑어보는 결과는 다음과 같습니다. ()
A. CFHGEBDA B. CDFEGHBA C. FGHCDEBA D. CFHGEDBA
지식
두 갈래 나무의 역행 방식은 일반적으로 세 가지 선서, 중서, 후서 세 가지 방식으로 나뉜다.
두 갈래 나무가 비어 있으면 아무 작업도 하지 않습니다. 그렇지 않으면 1. 루트 결점에 접근합니다.2. 선순 방식으로 왼쪽 나무를 두루 돌아다닌다.3. 먼저 오른쪽 나무를 두루 훑어보다..
중간 순서 반복 (왼쪽 뿌리 오른쪽) 두 갈래 나무가 비어 있으면 아무런 조작도 하지 않습니다. 그렇지 않으면 1. 중간 순서 왼쪽 트리를 반복합니다.2. 루트 결점에 접근한다.3、중서가 우자나무를 두루 돌아다닌다..
뒷차례 반복(왼쪽 오른쪽 뿌리) 두 갈래 나무가 비어 있으면 아무런 조작도 하지 않습니다. 그렇지 않으면 1. 뒷차례 왼쪽 트리를 반복합니다.2. 후서들이 오른쪽 나무를 두루 돌아다닌다.3. 뿌리를 내리고 결점을 묻는다
따라서 제목이 제시한 선차적 역류와 중차적 역류에 따라 두 갈래 나무를 그릴 수 있다.
두 갈래 나무가 두루 다니다.png
최종 결과 선택: D
2. 검색 및 삭제 성능이 높은 두 데이터 구조는 무엇입니까?( )
A. 서열 그룹 B. 서열 체인 테이블 C. AVL 트리 D. Hash 테이블
지식
몇 가지 흔히 볼 수 있는 데이터 구조의 조작 성능.png
균형 트리의 찾기, 삽입과 삭제 성능은 모두 O(logN)인데 그 중에서 찾기와 삭제 성능이 비교적 좋다.해시표의 검색, 삽입, 삭제 성능은 모두 O(1)로 가장 좋다.그래서 마지막 결과 선택: CD
3. 다음 정렬 알고리즘 중 어떤 시간의 복잡도가 nlogn을 초과하지 않습니까?( )
A. 빠른 정렬 B. 더미 정렬 C. 병합 정렬 D. 거품 정렬
지식
몇 가지 흔히 볼 수 있는 정렬 알고리즘의 대비.png
위의 그림에 따르면 평균 상황을 관찰하면 가장 나쁜 상황의 시간 복잡도는 기본적으로 답을 알 수 있다. 마지막 결과 선택: BC
4. 초기 서열은 18625473조로 무더기 정렬을 사용하고 더미(소근더미)가 완성되면 더미에 대응하는 두 갈래 나무의 차례는 다음과 같다. ()
A. 8 3 2 5 1 6 4 7 B. 3 2 8 5 1 4 6 7 C. 3 8 2 5 1 6 7 4 D. 8 2 3 5 1 4 7 6
초기화 서열: 18625473, 작은 뿌리 더미는 결점의 값이 좌우 아이의 결점의 값보다 작고 좌우 아이의 크기는 상관없다. 그러면 작은 뿌리 더미의 순서는 다음과 같다.
중서 반복: 왼쪽 뿌리 오른쪽, 그러므로 반복 결과: 832 51 647
마지막으로 선택한 결과: A
5, n = 5 시 다음 함수의 반환 값은 다음과 같습니다. ()

[cpp] view plaincopy
int foo(int n)  
{  
    if(n<2)return n;  
    return foo(n-1)+foo(n-2);  
}

A．5 B．7 C．8 D．1
이 문제는 몇 세대만 들어가면 결과를 알 수 있기 때문에 마지막 결과는 A로 한다.
차례로 돌아가다.png
6. S시 A, B는 모두 두 개의 구역이 있는데 인구 비율은 3:5이다. 역사 통계에 의하면 A구의 범죄율은 0.01%이고 B구는 0.015%이다. 기존의 새로운 사건이 S시에서 발생한다면 사건이 A구에서 발생할 가능성이 얼마나 됩니까?( )
A．37.5% B．32.5% C．28.6% D．26.1%
이 문제는 우선 범죄율이 무엇인지 알아야 한다.범죄율은 바로 범죄 인원수와 전체 인구수의 비율이다.따라서 (30.01%)/(30.01%+5*0.015%)= 28.6%
물론 이해하기 어렵다면 우리는 실례화할 수 있다. 예를 들어 B구역이 5000명, A구역이 3000명, A구역의 범죄율이 0.01%라고 가정하면 A구역의 범죄율은 30명, B구역의 범죄율은 0.015%이다. 그러면 B구역의 범죄수는 75명으로 A구역에서 발생할 가능성을 구한다. 즉, A구역의 범죄수는 전체 범죄수의 얼마, 즉 30/(30+75)=0.2857이다.
물론 우리 고등학교에서 잊어버린 지식으로 돌아갈 수도 있다.
가령 C는 범죄 속성이 A구역에서 범죄를 저지를 확률을 나타낸다고 가정합니다: P(C|A) = 0.01% B구역에서 범죄를 저지를 확률: P(C|B) = 3/8 B구역에서 확률: P(B) = 5/8 범죄 확률: P(C) = (3/80.01% +5/80.015%) 베일스 공식에 따라 P(A|C) = P(A,C)/P(C)=P(C|A) P(A)]/[P(C|A) P(A) + P(C|B) P(B)]]]도 계산할 수 있습니다 오다
따라서 최종 결과는 다음과 같습니다. C
7. 유닉스 시스템에서 프로세스 간 통신에 사용할 수 있는 것은 무엇입니까?( )
A.Socket B. 공유 메모리 C. 메시지 대기열 D. 신호량
지식
파이프(Pipe) 및 유명 파이프(named pipe): 파이프는 친연관계 프로세스 간의 통신에 사용할 수 있으며, 유명 파이프는 파이프의 이름이 없는 제한을 극복하기 때문에 파이프가 가진 기능을 제외하고 무친연관계 프로세스 간의 통신을 허용한다
신호(시그널): 신호는 비교적 복잡한 통신 방식으로 프로세스에 어떤 사건이 발생했음을 알리는 데 사용되며 프로세스 간의 통신을 제외하고 프로세스는 프로세스 자체에 신호를 보낼 수 있다.linux는 유닉스 초기 신호의 의미 함수인sigal을 지원하는 것 외에 의미가 Posix에 부합되는 것을 지원합니다.1 표준적인 신호 함수sigaction(실제로 이 함수는 BSD를 바탕으로 하고 BSD는 신뢰할 수 있는 신호 메커니즘을 실현하기 위해 대외 인터페이스를 통일하고sigaction 함수로signal 함수를 다시 실현했다)
메시지 대기열 (메시지 대기열): 메시지 대기열은 메시지의 링크 테이블입니다. Posix 메시지 대기열 시스템 V 메시지 대기열을 포함합니다.충분한 권한이 있는 프로세스는 대기열에 메시지를 추가할 수 있고, 읽기 권한이 부여된 프로세스는 대기열의 메시지를 읽을 수 있습니다.메시지 대기열은 신호 적재 정보량이 적고 파이프는 형식이 없는 바이트만 적재할 수 있으며 버퍼 크기가 제한되는 단점을 극복했다
공유 메모리: 여러 프로세스가 같은 메모리 공간에 접근할 수 있도록 하는 것이 가장 빠른 IPC 형식입니다.다른 통신 메커니즘의 운행 효율이 비교적 낮도록 설계된 것이다.왕왕 다른 통신 메커니즘, 예를 들어 신호량과 결합하여 사용하여 프로세스 간의 동기화와 상호 배척에 도달한다.신호량(semaphore): 주로 프로세스 간과 같은 프로세스의 서로 다른 라인 간의 동기화 수단으로..
소켓(Socket): 더욱 일반적인 프로세스 간 통신 메커니즘으로 서로 다른 기계 간의 프로세스 간 통신에 사용할 수 있다.처음에는 유닉스 시스템의 BSD 지점에서 개발되었지만, 지금은 일반적으로 다른 유닉스 시스템에 이식할 수 있다. 리눅스와 시스템 V의 변종은 모두 플러그인을 지원한다
마지막으로 선택한 결과: ABCD
8. 정적 변수는 일반적으로 프로세스의 어느 구역에 저장됩니까?( )
A. 창고 B. 더미 C. 전역 D. 코드 영역
정적 변수의 수식 키워드:static, 정적 전역 변수라고도 부른다.마지막으로 선택한 결과: C
9. 쿼리 성능 ()
A. Name 필드에 키 추가 B. Name 필드에 색인 추가 C. Age 필드에 키 추가 D. Age 필드에 색인 추가
결과 선택: B
10. IP 주소 131.153.12.71은 (B) 클래스 IP 주소입니다.
A．A B．B C．C D．D
지식
IP 주소 분류.png
그러므로 131을 바이너리로 전환: 10000011, 따라서 B 클래스 IP 주소, 결과는 B
11. 자동 인식기의 언어는 다음과 같습니다. (C)
A.0형 언어 B.1형 언어 C.2형 언어 D.3형 언어
지식
이것은 번역 원리에 관한 것이다.
촘스키 체계는 컴퓨터 과학에서 형식적인 문법 표현 능력을 묘사하는 분류 계통으로 짐 촘스키가 1956년에 제기한 것이다.여기에는 다음과 같은 네 가지 계층이 포함됩니다.
0-형 문법(무제한 문법 또는 단어 구조 문법)은 모든 문법을 포함한다.이 유형의 문법은 도영기에 식별될 수 있는 모든 언어를 만들 수 있다.도영기에 식별될 수 있는 언어는 도영기를 정지시킬 수 있는 문자열을 가리키는데 이런 언어는 귀속 가능 매거언어라고도 부른다.귀속 가능 매개 언어와 귀속 언어의 차이를 주의하십시오. 후자는 전자의 진자집합으로 총 정지된 도영기에 의해 판정될 수 있는 언어입니다
1-형 문법(상하문 관련 문법)은 상하문 관련 언어를 생성한다.이런 문법의 발생식 규칙은 다음과 같다.αAβ -> αγβ 같은 형식.여기서 A 는 끝 기호가 아니라α, β 화목하다γ 는 비종결 기호와 종결 기호를 포함하는 문자열입니다.α, β 빈칸일 수도 있지만,γ 빈 문자열일 수 없음;이 문법에도 규칙 S->ε ,그러나 문법의 생성식 규칙은 오른쪽에 S를 포함할 수 없습니다.이런 문법에 규정된 언어는 선형 유계 비확정 도영기에 의해 받아들일 수 있다
2-형 문법(상문무관문법)은 상하문무관언어를 생성한다.이런 문법의 발생식 규칙은 A->와 같다.γ 같은 형식.여기에 있는 A 시비 종결 기호는γ 는 비종결 기호와 종결 기호를 포함하는 문자열입니다.이런 문법에 규정된 언어는 비확정 하추자동기에 의해 받아들일 수 있다.상하문과 무관한 언어는 대다수 프로그램 설계 언어의 문법에 이론적 기초를 제공했다
3-형 문법(정규 문법)은 정규 언어를 생성한다.이런 문법은 생성식의 왼쪽에는 하나의 비종결 기호만 포함할 수 있고 생성식의 오른쪽은 빈 줄, 하나의 종결 기호 또는 하나의 비종결 기호 뒤에 하나의 종결 기호만 포함할 수 있다.생성된 모든 오른쪽에 초기 기호 S가 없는 경우 규칙 S ->ε 나타날 수도 있고.이런 문법에 규정된 언어는 유한 상태 자동기에 받아들여질 수도 있고 정규 표현식을 통해 얻을 수도 있다.정규 언어는 일반적으로 검색 모드나 프로그램 설계 언어의 어법 구조를 정의하는 데 쓰인다
정규 언어 클래스는 상하문과 무관한 언어 클래스, 상하문과 무관한 언어 클래스는 상하문 관련 언어 클래스, 상하문 관련 언어 클래스는 귀속 가능한 매개 언어 클래스에 포함된다.여기에 포함된 것은 모두 집합된 진정한 포함 관계이다. 즉, 귀속 가능한 매개 언어가 존재하는 것은 상하문 관련 언어류에 속하지 않고 상하문 관련 언어가 존재하는 것은 상하문 관련 언어류에 속하지 않으며 상하문 관련 언어가 존재하는 것은 정규 언어류에 속하지 않는다.
네 가지 유형의 문법의 주요 특징:
네 가지 유형의 문법의 주요 특징.png
그래서 정답 선택: B
12. 다음 프로그램의 출력은 다음과 같습니다. ()

[cpp] view plaincopy
#define add(a+b) a+b  
int main()  
{  
    printf(“%d
”，5*add(3+4));  
    return ;  
}

A．23 B．35 C．16 D．19