复试准备了很多，但问的很少。至少80%是用不到的，但也不能不准备啊。。

平凡的自我介绍，其实建议自己写，背的更快更轻松。可以以我的为框架自己填充东西。 缺点：没有说明自己的科研、竞赛和项目

Dear teachers, Good afternoon. I’m very glad to be here for this interview.

First, please allow me to introduce myself. My name is XXX, I’m XX years old and come from a small county in Anhui province. There’s nothing special in my hometown, but people in there are very kindly and friendly.

[基本信息] I major in computer science and I will graduate from XXX university this year. During my years in collage, I’ve learned a lot of knowledge in terms of computers, but also forget a lot. [考研动机] In the third year of my college, I realize that what I have grasped is not enough for me to be a qualified job-seeker in today’s competitive market, that’s why I made up my mind to take part in the postgraduate entrance exam.[自我评价和兴趣爱好] I’m open to different things and have broad interests including reading, ping-pong listening to music and so on. In my spare time ,I like to play high-quality games, and my favorite game is Genshin impact .//I also program a lot, they make my brains more active.//[优点长处] And I know that I am not that talented, but I never give up easily, I’ll give it a try and put all my heart on one thing to the last minute.

[表达渴望]If I could have the chance to be enrolled, I would try my best to improve my ability and take advantage of the great platform the school provides us.

That’s the end of my self-introduction, thanks for listening.

栈、队列、优先队列、哈希表、二叉树、B-数、堆

APPLICATION: 1. Bracket matching. 2.Backtracking: finding the correct path in a maze.

APPLICATION: Breath first search;

priority queue: each element additionally has a “priority” associated with it. An element with high priority is served before the element with low priority.

hash table is a structure that can map keys to values. Hash table uses hash function to transform keys to indexes of an array, from which we can find the desired value.

···Bad hash function may result in ‘hash collisions’, where the hash function generates the same index for more than one keys. Two common resolutions for the collision are separate chaining and open addressing.

In separate chaining, the collided items are chained together through a single linked list. In open addressing, we start from the hashed-to index and proceed in some probe sequence(linear probing,double hashing), until an unoccupied slot is found.

Binary search tree: BST is a rooted binary tree data structure whose internal nodes stores a key greater than all the keys in its left subtree and less than the keys in its right subtree. The time complexity is O(log n) ~ O(n).

B-tree is a self-balancing tree data structure that maintains sorted data. The B-tree generalizes binary search tree. A B-tree of order m’ allows at most m-1 keys and m children, and at least m/2 - 1 keys and m/2 children. (internal nodes may be joined or split.)

Heap is a complete tree-based data structure. There are two kind of heap: max heap and min heap. In max heap, the parent node is greater than or equal to the key of its children. It is a useful structure when we need repeatedly operate the maximum or minimum value, cause it’s always in the root node.

快速排序、基数排序、桶排序、希尔排序

Quicksort: is a divide-and-conquer algorithm. It works by selecting a pivot element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. Quicksort is not a stable sort, it cannot preserve the relative order of equal items.

​ On average it takes O(n log n), worst O(n^2)

Radix sort: is a kind of linear sort algorithm. We sort the array from least significant digit to most significant digit using counting sort. Note that the radix sort uses counting sort as a subroutine.

​ Time complexity: O(d(n+r)),* d is the length,n is the number of the elements, r is the radix.

​ Counting sort: is based on keys between a specific range. we traverse the array and get the count of every element, then we traverse the range and ouput the sorted array. Time: O(n+r)

Bucket sort: We need several buckets at first. Every bucket corresponds to a certain range . Then we insert every element into corresponding bucket, then we sort individual buckets using insertion sort. At last, we concatenate all sorted buckets.

shell sort：希尔排序是把元素序列按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的元素越来越多，当增量减至 1 时，整个序列恰被分成一组，算法便终止。

An Operating System (OS) is a software that acts as an interface between computer hardware components and the user. The main functions of OS includes Memory /Processor/ File/ I/O Management.

少年派的奇幻漂流吧，这个既有书又拍了电影。

My favorite book/movie: Life of Pi, which is a fictional movie/book, tells us a story about a young man who survives a disaster at sea and is hurtled into an epic journey of adventure and discovery. During his journey, he forms an unexpected connection with a fearsome tiger. The protagonist is very brave and tough, he manages to live with a tiger, and fights against the bad condition on the sea. At last, he arrives at the shore and is saved by the fisherman.

一些问题回答的不是很好，可以自行google 对应英文单词，去英文网站上看介绍。

在这里推荐一个网址：

https://www.geeksforgeeks.org/array-data-structure/?ref=shm