Java common data structure interview questions (with answers)

1. The common characteristics of stack and queue are (only elements can be inserted and deleted at the endpoint) 4. The two storage structures commonly used by stack are (linear storage structure and linked list storage structure) 5. The following description about stack is correct (D) A. the stack is a non-linear structure B. the stack is a tree structure C. the stack has the feature of first in first out D. the stack has the feature of last in first out 6. The characteristics that the linked list does not have are (b) A. It is not necessary to estimate the storage space in advance B. any element can be accessed randomly C. It is not necessary to move the element for insertion and deletion D. the required space is proportional to the length of the linear list 7. The advantages of using the linked list to represent the linear list are (easy to insert and delete) 8. In a single linked list, the purpose of adding a header node is to facilitate the implementation of operation. 9. The main advantage of a circular linked list is that (the whole linked list can be accessed from any node in the list) 10. Linear list L = (A1, A2, A3,... AI,... An). The following statement is correct (D) A. each element has a direct antecedent and a direct antecedent. B. there must be at least one element in the linear table. C. The arrangement order of the elements in the table must be from small to large or from large to small. D. except for the first and last element, each other element has one and only one direct antecedent and direct antecedent. 11. If the linear table adopts the chain storage structure, it is required to be available in memory The address of the storage unit (d) A. must be continuous B. the partial address must be continuous C. must be discontinuous D. continuous and discontinuous can be 12. The sequential storage structure of the linear table and the chain storage structure of the linear table are (random access storage structure and sequential access storage structure) respectively 13. The tree is a collection of nodes, and the number of its root nodes is (yes and only 1) 14. In a full binary tree with a depth of 5, the number of leaf nodes is (31) 15. A binary tree with 3 nodes has (5 forms) 16. If there are 3 leaf nodes and 8 nodes with a degree of 1 in a binary tree, the total number of nodes in the binary tree is (13) 17. It is known that the post order traversal sequence of a binary tree is dabec, the middle order traversal sequence is debac, and its pre order traversal sequence is (cedba) 18. If it is known that the pre order traversal and middle order traversal of a binary tree are abdegcfh and dbgeachf respectively, the post order traversal of the binary tree is (dgebhfca) 19. If the pre order traversal access order of a binary tree is abdgcefh and the middle order traversal access order is dgbaechf, the node access order of post order traversal is (gdbehfca) 20. Database protection is divided into security control, integrity control, concurrency control and data recovery.

1. In the computer, Algorithm refers to (accurate and complete description of problem-solving scheme) 2. Among the following options, which is not the basic feature (infinity) that an algorithm should generally have? Description: the four basic features of the algorithm are: feasibility, certainty, finiteness and sufficient intelligence. 3. What kinds of control structures can the algorithm be combined with (sequence, selection, cycle) 4. The time complexity of the algorithm refers to (the number of basic operations required during the execution of the algorithm) 5. The space complexity of the algorithm refers to (the storage space required during the execution) 6. The purpose of algorithm analysis is (to analyze the efficiency of the algorithm for improvement) 7. The following statements are correct (C) A. the execution efficiency of the algorithm is independent of the data storage structure. B. the spatial complexity of the algorithm refers to the instructions in the algorithm program C. the finiteness of the algorithm means that the algorithm must be able to terminate after executing a limited number of steps D. the time complexity of the algorithm means the time required to execute the algorithm program 8. Data structure, as a discipline of computer, mainly studies the logical structure of data, the operation of various data structures, and (data storage structure) 9. In the data structure, what is irrelevant to the computer used is the data (c) A. storage structure B. physical structure C. logical structure D. physical and storage structure 10. In the following description, what is wrong is (B) A. the storage structure of data is closely related to the efficiency of data processing B. the storage structure of data has nothing to do with the efficiency of data processing C. the space occupied by the storage structure of data in the computer is not necessarily continuous D. a logical structure of data can have a variety of storage structures 11. The storage structure of data refers to (the representation of the logical structure of data in the computer) 12. The logical structure of data refers to (the data structure reflecting the logical relationship between data elements) 13. According to the complexity of the antecedent and antecedent relationship between data elements in the data structure, the data structure is generally divided into (linear structure and nonlinear structure) 14. The following data structures have memory function (C) A. queue B. cyclic queue C. stack D. sequence table 15. Among the following data structures, the data is organized according to the principle of first in and last out (b) A. linear linked list B. stack C. cyclic linked list D. sequence table 16. Recursive algorithm generally needs to be implemented by (queue). 17. What is correct in the following description of stack (D) A. only data can be inserted in the stack B. only data can be deleted in the stack C. the stack is a first in first out linear table D. the stack is a first in last out linear table 20. The advantages of sharing one storage space by two stacks are (saving storage space and reducing the probability of overflow)

21. When an application program needs to output data through a printer during execution, it usually forms a print job first, It is stored in a designated (queue) in the hard disk. When the printer is idle, it will take out the job to be printed in a first come first serve manner for printing. 22. The following description about the queue is correct (C) A. only data can be inserted into the queue B. only data can be deleted from the queue C. the queue is a first in first out linear table D. the queue is a first in last out linear table 23. In the following description, the correct is (D) A. the position of each element in the linear linked list in the storage space must be continuous. B. the header element in the linear linked list must be stored in front of other elements. C. the position of each element in the linear linked list in the storage space is not necessarily continuous, but the header element must be stored in front of other elements. D. the position of each element in the linear linked list in the storage space It is not necessarily continuous, and the storage order of each element is arbitrary 24 The following statements are correct: (a) A. linear table is linear structure B. stack and queue are nonlinear structure C. linear linked list is nonlinear structure D. binary tree is linear structure 25. Linear table L = (A1,... An). The following statements are correct (D) A. each element has a direct antecedent and a direct consequent. B. there must be at least one element in the linear table. C. The arrangement order of the elements in the table must be from small to large or from large to small. D. except for the first element and the last element, each other element has one and only one direct antecedent and direct consequent. 26. If the linear table adopts the chain storage structure, it is required to The address of the available storage unit in the memory (continuous or discontinuous) 27. The characteristics of the linked list are (b) A. there is no need to estimate the storage space in advance B. any element can be accessed randomly C. There is no need to move the element for insertion and deletion D. the required space is directly proportional to the length of the linear list 28. The tail node of the non empty circular single linked list head (pointed by P) meets the following requirements (P - > next = head) 29. Compared with the one-way linked list, one of the advantages of the two-way linked list is (easier access to adjacent nodes) 30. In (D) A. linear single linked list B. bidirectional linked list C. linear linked list D. circular linked list 31. The following data structures belong to nonlinear data structures (C) A. queue B. linear table C. binary tree D. stack 32. A tree is a collection of nodes, and its number of root nodes is (yes and only 1) 33. A binary tree with three nodes has (5 forms) 34. The maximum number of nodes in the eighth layer of a binary tree is (128) Note: 2k-1 35. In a full binary tree with a depth of 5, the number of leaf nodes is (16) Note: 2N-1 36. There are (31) nodes in a full binary tree with a depth of 5. Note: 2N-1 37. If a complete binary tree has 699 nodes, the number of leaf nodes in the binary tree is (350). Note: the total number of points of a complete binary tree is n. if n is an odd number, the number of leaf nodes is (n + 1) / 2; if n is an even number, the number of leaf nodes is n / 2.38. The following binary tree is set, and the result of the middle order traversal of the binary tree is (b) a.abcdef b.dbeafc c.abdecf d.debfca 39. It is known that the post order traversal sequence of the binary tree is dabec, the middle order traversal sequence debac, and its pre order traversal sequence is (cedba) 40. If it is known that the preorder traversal and inorder traversal of a binary tree are abdegcfh and dbgeachf respectively, the postorder traversal of the binary tree is (dgebhfca)

41. If the pre order traversal access order of a binary tree is abdgcefh and the middle order traversal access order is dgbaechf, Then the node access order traversed in the subsequent order is (gdbehfca) 42. The length of the string is (the number of characters contained in the string) 43. There are two strings P and Q, and the operation of finding the first occurrence position of Q in P is called (pattern matching) 44. The number of edges in a connected graph with n vertices is at least (n-1) 45. The number of edges in a strongly connected graph with n vertices is at least (N) 46. In the worst case, the number of comparisons required for the linear table with length n is (n) 47. The simplest exchange sorting method is (bubble sorting) 48. Assuming that the length of the linear table is n, the number of comparisons required for bubble sorting is (n (n-1) / 2) 49 On the premise that the sequence of elements to be sorted is basically orderly, The most efficient sort method is (bubble sort) 50. In the worst case, the least time complexity of the following sort methods is (heap sort) 51. Hill sort method belongs to (insert sort) 52. Heap sort method belongs to (select sort) 53. Among the following sort methods, the one requiring the largest amount of memory is (merge sort) 54. It is known that each element in data table a is not far from its final position. In order to save time, it should be used (direct insertion sort) 55. The basic characteristics of the algorithm are feasibility, certainty, finiteness and sufficient intelligence.

1. An algorithm usually consists of two basic elements: one is the operation and operation of data objects, and the other is the control structure of the algorithm. 1. The complexity of the algorithm mainly includes time complexity and space complexity. 2. The number of storage units required to implement the algorithm and the workload of the algorithm are called the spatial complexity and time complexity of the algorithm respectively. 3. The so-called data processing refers to the operation of each element in the data set in various ways, including insertion, deletion, search, change and other operations, as well as the analysis of data elements. 4. Data structure refers to the collection of interrelated data elements. 5. The data structure is divided into logical structure and storage structure, and the linear linked list belongs to the storage structure. 6. Data structure includes logical structure of data and storage structure of data. 7. Data structure includes the logical structure of data, the storage structure of data and the operation of data. 8. Any relationship between data elements can be described by antecedent and successor relationships. 9. The logical structure of data includes linear structure and nonlinear structure. 10. Common storage structures include order, link, index and other storage structures. 11. Sequential storage method is to store logically adjacent nodes in storage units adjacent to physical locations. 12. There are three basic operations of stack: entering stack, exiting stack and reading stack top elements. 13. There are two basic operations of queue: queue in operation and queue out operation. 14. In practical application, the stack with chain can be used to collect all free storage nodes in the computer storage space. This stack with chain is called available stack. 15. The storage structures commonly used by stacks and queues are chain storage and sequential storage. 16. When the linear table is stored in sequential storage structure, its main feature is that the adjacent nodes in the logical structure are still adjacent in the storage structure. 17. There are two basic operations of circular queue: queue in operation and queue out operation. For each queue operation, the end of the queue pointer enters 1. 18. When the cyclic queue is not empty and the end of queue pointer is equal to the header pointer, it indicates that the cyclic queue is full and cannot be queued. This condition is called overflow. 19. When the circular queue is empty, the queue withdrawal operation cannot be performed, which is called underflow. 20. In a circular queue with a capacity of 25, if the head pointer front = 16 and the tail pointer rear = 9, there are 18 elements in the circular queue. Note: when rear < front, the number of elements = total capacity - (front-rear); when rear > front, the number of elements = rear-front.

1. Judge whether there is a ring linked list: judge whether there is a ring in a linked list. For example, there is a ring in the following linked list: for example, N1 - > N2 - > N3 - > N4 - > N5 - > N2 is a linked list with a ring. The starting node of the ring is N5. Here is a relatively simple solution. Set two pointers P1, P2. Each cycle P1 moves forward one step and P2 moves forward two steps. End the loop until P2 encounters a null pointer or two pointers are equal. If the two pointers are equal, there is a ring.

2. Linked list inversion the inversion of one-way linked list is not only a frequently asked interview question, but also a very basic question. For example, a linked list is like this: 1 - > 2 - > 3 - > 4 - > 5 becomes 5 - > 4 - > 3 - > 2 - > 1 after inversion. The easiest way to think of is to traverse the linked list, use an auxiliary pointer to store the next element pointed to by the current pointer in the traversal process, then reverse the pointer of the current node element, and continue traversal later with the stored pointer. The source code is as follows:

There is another way to use recursion. The basic idea of this method is to call recursive functions to invert subsequent nodes before inverting the current node. The source code is as follows. However, this method has a disadvantage that the last node after inversion will form a ring, so the next field of the node returned by the function must be set to null. Because I want to change the head pointer, I use a reference. The source code of the algorithm is as follows:

3. Judge whether there are the same numbers in two arrays. Given two ordered arrays, how can we efficiently judge whether there are the same numbers in the two arrays? The first thought of this problem is an O (nlogn) algorithm. It is to randomly select an array and traverse all elements of the array. During the traversal process, binary search is performed on each element in the first array in another array. The code implemented in C + + is as follows:

Later, it was found that there was an O (n) algorithm. Because both arrays are ordered. So just one traversal. First, set two subscripts, initialize them to the starting addresses of the two arrays, and move forward in turn. The advance rule is to compare the numbers in two arrays. The subscript of the smaller array advances one step until the subscript of any array reaches the end of the array. If the same number has not been encountered at this time, it means that there is no same number in the array.

4. Maximum subsequence problem: given an integer sequence A1, A2 An (there may be negative numbers), find a subsequence AI ~ AJ of A1 ~ an so that the sum of AI to AJ is the largest. For example, the sum of the largest subsequences of the integer sequence - 2,11, - 4,13, - 5,2, - 3,12, - 9 is 21. For this problem, the simplest and easiest way to think of is to enumerate all subsequences. Use the triple loop to find the sum of all subsequences in turn, and then take the largest one. Of course The algorithm complexity will reach o (n ^ 3). Obviously, this method is not optimal. Here is a linear algorithm implementation with algorithm complexity of O (n). The algorithm comes from the book Programming pearls. Before giving the linear algorithm, let's look at an algorithm that optimizes the exhaustive algorithm. Its algorithm complexity is O (n ^ 2). In fact, this algorithm only slightly modifies the exhaustive algorithm: in fact, we don't need to recalculate the sum of subsequences every time. Suppose sum (I, J) is a [i] Sum of a [J], then sum (I, j + 1) = sum (I, J) + a [J + 1]. Using this recursion, we can get the following algorithm:

How can we achieve linear complexity? The idea of dynamic programming is used here. Let's first look at the source code implementation:

6. Reversing the string by word is not a simple string inversion, but reversing the string according to the words in the given string, that is, the words in the string still maintain the original order, and each word here is separated by spaces. If you simply flip all strings, you can traverse the string, exchange the first character with the last, the second and the penultimate, and cycle in turn. In fact, according to word inversion, you can traverse the string again on the basis of the first traversal, and reverse each word again. In this way, each word returns to the original order.

If you consider the optimization of space and time, of course, you can change the two string exchange parts in the above code to XOR.

For example, will

Change to

7. If I remember string inversion correctly, it is a written test question of MSN. I accidentally saw it on the Internet and did it for a while. The problem is, given a string, a substring of this string, reverse the first string, but keep the order of substrings unchanged. For example:

Input: the first string: "this is mianwww's Chinese site: http://www.mianwww.com.cn/cn "

Substring: "mianwww"

Output: "NC / nc.moc.mianwww.www / /: PTTH: ETIS esenihc s'mianwww Si siht"

The general method is to scan the first string on one side, then reverse it with stack, and record the position of the substring at the same time. Then scan again and reverse the recorded substring with stack. The method I use is to scan the array once. If a substring is found during scanning, the substring is inverted and pushed into the stack.

8. The problem of deleting duplicate numbers in the array: a number sequence with variable dynamic length, with the number 0 as the end flag, requires that the duplicate number be replaced by a number, for example:

The problem of transforming the array 1,1,7,5,0 into 1,0 is relatively simple. It should be noted that this array is dynamic. So to avoid trouble, I still use STL Vector.

Of course, if you can change the original array, you can use STL instead of pointer operation. The following program will modify the contents of the original array.

9. How to judge whether a binary tree is a balanced binary tree problem: judge whether a binary sort tree is a balanced binary tree solution: according to the definition of a balanced binary tree, if the depth difference between the left and right subtrees of any node is no more than 1, the tree is a balanced binary tree. Firstly, write a function to calculate the depth of binary tree, which is realized by recursion.

The following is a function of recursively judging whether the depth difference between the left and right subtrees is 1 to judge whether it is a balanced binary tree:

Is there a mistake in this code? Answer: wrong. Abstract methods cannot be decorated with private. Abstract methods allow subclasses to implement specific details. How can we use private to block the abstract method? (similarly, final cannot be added before abstract method). 5. Look at the following code snippet. What's wrong?

Answer: wrong. No access modifiers (private, public, and protected) can be placed before local variables. Final can be used to modify local variables (final, like abstract and strictfp, are non access modifiers, and strictfp can only modify classes and methods rather than variables). 6. Is there any error in the following code? If so, where is the error?

Answer: wrong. Abstract method must end with a semicolon without curly braces.