#### hi, Hello, today is November 4. Maybe this time is really over. But the road of learning will not stop.

(1) If the sorting code of a group of records is (46, 79, 56, 38, 40, 84), use

The quick sorting method is based on the first record, and the first division result is

( ).

A．38，40，46，56，79，84 B．40，38，46，79，

56，84

C．40，38，46，56，79，84 D．40，38，46，84，

56，79

Answer: C

Analysis: this question mainly focuses on the method of quick sorting. Remember to place the central point at the monitoring post, find the number smaller than the central point from the back, and remember to find the number larger than the central point from the front after leaving the position in the back.

(11) If the sorting code of a group of records is (46, 79, 56, 38, 40, 84), use

The initial heap created by the heap sorting method is ().

A．79，46，56，38，40，84 B．84，79，56，38，

40，46

C．84，79，56，46，40，38 D．84，56，79，40，

46，38

Answer: B

Analysis: create a tree according to the sorting code, and then create a large root heap or a small root heap for sorting

(1) Set the keyword sequence to be sorted as {12, 2, 16, 30, 28, 10, 16 *, 20,

6, 18}, try to write out the following sorting methods respectively, and the keyword order after each sorting

Status of the column.

① Direct insert sort

② Split insertion sort [mid=(low+high)/2]

③ Hill sort (incremental selection 5, 3, 1)

④ Bubble sorting

⑤ Quick sorting (focus on mastering methods)

⑥ Simple selection sort

⑦ Heap sort

⑧ Two way merge sort

(3) Input files (101, 51, 19, 61, 3, 71, 31, 17, 19100,

55，20，9，30，50，6，90)； When k=6, use the permutation selection algorithm to write

Establish the initial loser tree and generate the initial merging segment

Initial merging section: r1:3,19,31,51,61,71100101

R2:9,17,19,20,30,50,55,90

R3:6

## algorithm

(1) Try to use the single linked list as the storage structure to realize the simple selection sorting algorithm.

`[Algorithm description]: void LinkedListSelectSort(LinkedList head) //The algorithm finds a node with the smallest keyword at a time, and its data is exchanged with the current node; To exchange pointers, you must record / / the precursor pointers of the current node and the smallest node p=head->next; while(p!=null) {q=p->next; r=p; //Let r be a pointer to the node with the smallest keyword while (q!=null) {if(q->data<r->data) r=q; q:=q->next; } if(r!=p) r->data<-->p->data; p=p->next;}`

(2) There are n records stored in the two-way linked list of the leading node, which is now sorted by two-way bubbling

Method to sort them in ascending order. Please write out the algorithm of this sort. (Note: bidirectional bubbling)

Sorting (i.e. two adjacent sorts bubble in the opposite direction).

`typedef struct node { ElemType data; struct node *prior,*next; }node，*DLinkedList; void TwoWayBubbleSort(DLinkedList la) //The elements stored in the two-way linked list la of the leading node are subject to two-way bubbling Preface. {int exchange=1; // Set mark DLinkedList p,temp,tail; head=la //Bidirectional chain header, which bubbles downward during the algorithm Start node tail=null; //The tail of the two-way linked list is bubbling upward in the process of the algorithm Start node while (exchange) {p=head->next; //p is the working pointer, pointing to the current node exchange=0; //It is assumed that there is no exchange in this trip while (p->next!=tail) // Bubbling down (right), there is a maximum in one trip Element bottom if (p->data>p->next->data) //Exchange two node pointers, involving 6 chain {temp=p->next; exchange=1;//There is exchange p->next=temp->next;temp->next->prior=p //First remove the node from the linked list Take it off temp->next=p; p->prior->next=temp; //Insert temp into p Before node temp->prior=p->prior; p->prior=temp; } else p=p->next; //No exchange, pointer moves back tail=p; //Ready to blister up p=tail->prior; while (exchange && p->prior!=head) //Bubble up (left) and a minimum element comes out at a time if (p->data<p->prior->data) //Exchange two node fingers Needle, involving 6 chains {temp=p->prior; exchange=1; //There is exchange p->prior=temp->prior;temp->prior->next=p； //First, remove the temp node from the linked list temp->prior=p; p->next->prior=temp; //Insert temp into the p node Rear (right) temp->next=p->next; p->next=temp; } else p=p->prior; //No exchange, pointer forward head=p; //Ready to bubble down }// while (exchange) } //End of algorithm`

(5) With the help of the idea of quick sorting algorithm, a given relation is found in a group of unordered records

Records with key word value equal to key. Set this group of records to be stored in the array r[l..n]. Ruocha

If the search is successful, the position of the record in the r array and its value will be output; otherwise, "not" will be displayed

"find" information. Please briefly explain the idea of the algorithm and write the algorithm.

Analysis: take the records to be checked as the pivot, and compare them successively from back to front. If it is smaller than the pivot

Axis, from the front to the back, until the search successfully returns its position or fails to return 0

`int index (RecType R[],int l,h,datatype key) {int i=l,j=h; while (i<j) { while (i<=j && R[j].key>key) j--; if (R[j].key==key) return j; while (i<=j && R[i].key<key) i++; if (R[i].key==key) return i; } cout<<"Not find"; return 0; }//index `