7.16 written examination of Duoyi network

Written examination on the battle alliance client

1. What linked lists don't have is （）

A Random access to any element    B There is no need to estimate storage space in advance

C There is no need to move data elements when inserting data elements   D There is no need to move data elements when deleting data elements

A For the characteristics of the sequence table

2. The characteristics of the stack

Last in, first out

3. What are the linear data structures （）

Linear data structures are ： The linear table 、 Stack 、 queue 、 deque 、 Arrays and strings

4. In the following sorting algorithm , The time complexity is independent of the initial arrangement of records ( ) 

A． Insertion sort   B． Heap sort   C． Quick sort   D． Bubble sort

5. Which sort is right 1234576 The fastest （）

The basic order

6. Select the smallest data element from the data elements to be sorted for the first time （ Or maximum ） An element of , Store at the beginning of the sequence , And then find the smallest of the remaining unsorted elements （ Big ） Elements , Then put it at the end of the sorted sequence . And so on , Until the number of all data elements to be sorted is zero . This is how the sorting method works

Selection sort

7. How many structures can a three node binary tree have

5 Kind of

8. A database has several patterns

The recognized standard structure in the field of database is the three-level schema structure , It includes external modes 、 Conceptual model 、 Internal mode

9. Existing in a database A、B、C、D、E、F Six sentences , But the current database is uncoordinated . Some statements must be dropped to restore database consistency . It is known that ： (1) If you keep the statement A, Then you must keep the statement B And statement C. (2) If you keep the statement E, You must also delete the statement D And statement C. (3) Only reserved statements E, To keep the statement F. (4) sentence A Is important information , Can't delete . If the above items are true , Which of the following must be true （）

A． Retention statement E And delete the statement C

B． Keep the statement at the same time C And statement D

C． Retention statement E And delete the statement D

D． Delete the statement at the same time E And statement F

10. The incorrect description of sliding windows is ()

A. It can improve the transmission efficiency
B. It can improve channel utilization
C. Capable of flow control
D. It can prevent the error of message segment sequence

11. In a 3 In the system of level page table structure , Memory is shared 8192 page , each page 2048 byte . How many bits does the physical address of memory need ？（）

24 position .

Memory has 8192*2048=2^24Byte, Need 24 Bit address

12. Go to a stack order push The following elements ：ABCDE, Its pop Possible order , The following incorrect is （）

A. BACDE
B. ACDBE
C. AEBCD
D. AEDCB

13. For keywords {25,15,30,10,50,3,5,60} Sequence for quick sorting , The result of the first trip from small to large is （ ）
A. {3,5,10,15} 25{50,30,60}

B. {5,15,3,10} 25 {50,30,60}

C. {3,15,10,5} 25 {50,30,60}

D. {5,15,3,10} 25 {30,50,60}

title ：

This problem adopts the pivot exchange method ：

From right to left , The first one is better than 25 Small number , and 25 Swap places .

From left to right , The first one is better than 25 Large number , and 25 Swap places .

......

until 25 There is no larger number on the left , There is no smaller number on the right .

14. Stable sorting algorithm and time complexity

Stable sorting algorithm ： Bubble sort 、 Insertion sort 、 Merge sort 、 Radix sorting

Unstable sorting algorithm ： Selection sort 、 Quick sort 、 Shell Sort 、 Heap sort

Bubble sort 、 Direct insert sort 、 Selection sort ：O（n*n）

Quick sort 、 Merge sort 、 Heap sort ：log2(n)*n

Shell Sort ：n Of 1.2 The next power

15. A binary tree has 10 The individual degree is 1 The node of ,7 The individual degree is 2 The node of , Then the total number of nodes of the binary tree is （）

25 individual

 16. One has n Digraphs with vertices , The sum of the outgoings of all its vertices is Dout, Then the sum of the penetration of all vertices is ( )

 A．Dout  B．Dout-1  C．Dout+1  D．n

17. One has n A binary tree of nodes , If he has m Leaf node , Then the binary tree is 1 What is the number of nodes （）

n-2m+1

18. Let the array be defined as a[60][70], Each element accounts for 2 Storage unit , Arrays are stored first by column , Elements a[0][0] The address for 1024, So the element a[32][58] The address for （）

8048

19.（） Is limited to insert operations only at one end of the table , A linear table that performs a deletion operation at the other end of the table .

queue

20. The difference between processes and threads in owning resources

21.tcp The protocol is a network protocol for byte stream , It means （）

  It means that the data is transmitted to the receiver in the form of byte stream , There is no fixed “ message ” or “ Message boundary ” The concept of .

22. How does the application layer solve the problem of no message boundary

1. Send a fixed length message

2. Send the message length with the message

3. Separate messages with special tags

23. Data table fields char and varchar The difference between

24. In the array a+b+c=0 All triples that meet the conditions and are not repeated

Title Description
Give a n Array of elements S,S Is there an element in a,b,c Satisfy a+b+c=0？ Find the array S All triples that meet the conditions in .

Their thinking ：
The sum of three equals 0,
1、 Then you need to sort the given array from small to large .
2、 If the first number after sorting is greater than 0, Then their sum cannot be used for 0, return null;
3、 Take the first number as the benchmark , Define the other two pointers （ Double pointer ）, Move the second and last bits in turn to make traversal judgment

 public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();
         //1、 The array is less than three numbers , Go straight back to 
        if(num==null || num.length<3){
            return res;
        }
        //  Sort from small to large 
        Arrays.sort(num);
        for(int i=0;i<num.length-2;i++){
            if(num[i]>0){
                break;//  If the current number is greater than 0, Then the sum of three numbers must be greater than 0, So end the cycle 
            }
            // The repeated three numbers do not count 
            if(i>0 && num[i]==num[i-1]){
                continue;//  duplicate removal 
            }
            // Define two pointers , Before and after   and   From back to front  
            int L=i+1;
            int R=num.length-1;

            while(L<R){
                int sum=num[i]+num[L]+num[R];
                if(sum==0){
                    ArrayList<Integer> list=new ArrayList<>();
                    list.add(num[i]);
                    list.add(num[L]);
                    list.add(num[R]);
                    res.add(list);
                     // duplicate removal 
                    while(L<R && num[L]==num[L+1]){
                        L++;
                    }
                     // duplicate removal 
                    while(L<R && num[R]==num[R-1]){
                        R--;
                    }
                    L++;
                    R--;
                }
                else if(sum>0){
                    R--;
                }
                else if(sum<0){
                    L++;
                }
            }
        }
        return res;
    }