2020 청화대학 교 912 컴퓨터 기초 종합 추억 (데이터 구조 부분)

2020 청화대학 교 912 컴퓨터 기초 종합
데이터 구조
1. 옳 고 그 름 을 판단 한다 (12 x 2 ')

n l o g n = 오 메 가 (l o g n) (C S D N 은 왜 공식 왼쪽 정렬 을 지원 하지 않 습 니까) nlogn = \ Omega (log ^ n) (CSDN 은 왜 공식 왼쪽 정렬 을 지원 하지 않 습 니까) nlogn = 오 메 가 (CSDN 은 왜 공식 왼쪽 정렬 을 지원 하지 않 습 니까)

quicksort 의 평균 상황 에서 시간 복잡 도 는 O (n l o g n) O (nlogn) O (nlogn) 로 가장 좋 은 상황 에서 도 마찬가지다.

규 모 는 n n n 의 도약 표 이 고 기대 탑 은 l o g n logn logn 이다.

패자 수 delmax() 조작 시간 복잡 도 는 점진 적 의미 에서 승자 수 보다 우수 하 다.

완전 이 진 더미 삭제 작업 의 평균 시간 복잡 도 는 O (1) O (1) O (1) 이 고 최 악의 경 우 는 O (l o g n) O (logn) O (logn) 이다.

Crane 왼쪽 더 미 는 A 와 B 를 합치 면 더 미 를 합 친 오른쪽 노드 가 모두 A 또는 B 의 오른쪽 체인 에서 나 오 는 것 이 아니다.

규모 가 n n 인 AVL 트 리 를 한 번 에 삽입 하면 최 악의 경우 O (l o g n) O (logn) O (logn) 차 부분 재 구성 을 야기 할 수 있다.

n n 개의 요 소 를 완전 이 진 로 를 구성 하려 면 적어도 O (n l o g n) O (nlogn) O (nlogn) 의 시간 이 필요 합 니 다.

붉 은 검 은 나무 중의 모든 노드 의 검 은 깊이 와 검 은 높이 의 합 은 반드시 같다.

은 CBA 알고리즘 을 바탕 으로 O (n) O (n) O (n) 시간 내 에 n n n 개의 무 서수 에서 앞의 10% 을 찾 을 수 있 습 니 다.

은 폐쇄 산열 에 비해 산열 을 개방 하면 시스템 캐 시 를 더욱 잘 이용 할 수 있다.

DAG 은 DFS 이후 k k k 개의 변 이 backward 으로 표시 되 었 는데 그림 에 k k 개의 고리 가 꼭 들 어 있 는 것 은 아니다.

2. 선택 문제 (6 x 3)

DFS 각 노드 방문 순서출력 은 원 그림 의 토폴로지 정렬 시퀀스 입 니 다.

기수 정렬 바 텀 에서 사용 하 는 정렬 알고리즘 이 불안정 하면 기수 정렬 의 정확성 과 안정성 은 어 떻 습 니까?

모드 문자열 텍스트 문자열 은 무 작위 영문 자모 와 숫자 로 구성 되 어 있 으 며, 만력 알고리즘 의 가장 좋 은 상황 은 평균 상황 에 비해 KMP 알고리즘 은 어 떻 습 니까?

RPN 표현 식 값 은 2019 입 니 다. 조작 부호 가 부족 한 것 이 무엇 입 니까?(예년 과 차이 가 많 지 않 지만 구체 적 인 표현 식 이 무엇 인지 기억 이 나 지 않 는 다)

몇 개의 무차별 노드 가 진 이 진 트 리 의 종 류 를 구성 하 는데 2019 쌍 의 괄호 가 구 성 된 합 법 적 인 표현 식 과 똑 같이 많 습 니까?

모드 문자열 HHF...HHFB... (총 15 글자), 개 선 된 next 표를 사용 하면 next[14]-next[0] 은 얼마 입 니까?

3. 증명 여부 (5 ')

주어진 이 진 트 리 의 순서 와 후 순 서 를 옮 겨 다 니 며 유일한 차원 을 얻 을 수 있 습 니까?가능 하 다 면 증명 해 주세요.만약 안 된다 면 반 례 를 들 어 보 세 요.

4. 알고리즘 문제

struct BinNode{
    BinNode *lc;
    BinNode *rc;
    BinNode *parent;

    BinNode *zig(BinNode *t); //        ，              。
    BinNode *zag(BinNode *t); //        ，              。
}

주어진 규모 가 n 인 완전 이 진 트 리 는 뿌리 노드 왼쪽 서브 트 리 의 규 모 를 구하 고 유도 과정 을 작성 합 니 다.

첫 번 째 문 제 를 의사 코드 로 실현 하고 해당 하 는 주석 을 추가 합 니 다.

int lSize(BinNode *t){
    //your code
}

이 완전 이 진 트 리 를 찾 아 중간 에 k 번 째 노드 를 옮 겨 다 니 며 의사 코드 로 이 루어 지고 해당 하 는 설명 을 추가 합 니 다.

BinNode *search(BinNode *t, int k){
    //your code
}

주어진 이 진 트 리 노드 a 과 x, a 은 x 의 조상 으로 zig 과 zag 작업 을 통 해 노드 x 을 a 의 아이 노드 로 조정 하고 a 이 null 이면 x 을 뿌리 노드 로 조정 한다.

BinNode *regulate(BinNode *x, BinNode *a){
    //your code
}

상기 실 현 된 인 터 페 이 스 를 사용 하여 주어진 이 진 트 리 를 완전 이 진 트 리 로 전환 합 니 다.

BinNode *balance(...){
    //your code 
    //        O(nlogn)
    //              
}

은 당신 이 실현 한 balance 이 문제 가 요구 하 는 시간 복잡 도 에 도달 할 수 있다 는 것 을 증명 합 니 다.

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

2020 청화대학 교 912 컴퓨터 기초 종합 추억 (데이터 구조 부분)

좋은 웹페이지 즐겨찾기