2015
1. There is an unordered data sequence containing N integers. All data elements are different and stored in integer array R[0, n-1]. requirement:
(1). Design an algorithm as efficient as possible to output the k(1 ≤ k ≤ n) smallest element in the sequence
- Two ideas:
- Create a small top heap with k elements for heap arrangement. The maximum number of K is reserved in the heap, and the top of the heap is the k-th small element;
- The pivot partition strategy similar to fast row is adopted, and one element position can be determined each time. When the pivot is the k-th position, the pivot value is the k-th smallest element;
(2). The solution process is given and the time complexity is analyzed.
- For method 1: the time complexity is \ (n*log_2k \)
- code:
void PrintNumK(int *nums, ，int n, int k) { // Output the smallest number k, n: sequence length // Create a small top heap with k elements, and replace the smallest element at the top of the heap with the next element of the original array each time. After the array is traversed, the top element of the heap is the target element; int Heap[k+1]; //heap int i; for (i = 0; i < k; i++) nums[i] = Heap[i+1]; for (i = k/2; i > 0; i--) AdjustHeap(Heap, i, k); //Heap initialization for (i = k; i < n; i++) { if(Heap[1] < nums[i]) Heap[1] = nums[i]; //When the external element is larger than the top of the heap, replace the top of the heap element else continue; AdjustHeap(Heap, 1, k); } printf("%d",A[1]); } void AdjustHeap(int *Heap, int k, int h) { // k: The position of the element to be adjusted; h: Total length of heap int i = k, j = 2*k; int temp = Heap[i]; while(j<=h) { if (j<h && Heap[j]>Heap[j+1]) j++; if(temp < Heap[j]) { Heap[i] = Heap[j]; i = j; j = 2*j; } else break; } Heap[i] = temp; } - For method 2: the average complexity is O(n)
- code:
int SNum_k(int *nums, int low, int high, int k) { // Output the smallest number k in nums if (low>high) return -1; // >Instead of > == You need to walk again when you get there int L = low, H = high; int temp = nums[L]; while(L<H) { while(L<H && nums[H]>temp) --H; nums[L] = nums[H]; while(L<H && nums[L]<temp) ++L; nums[H] = nums[L]; } nums[L] = temp; if(L==k-1) printf("%d\n ",temp); //The smallest number k should be in the position of k-1 if(L<k-1) SNum_k(nums, L+1, high, k); else SNum_k(nums, low, L-1, k); }
2. Take the binary tree with parent pointer as the storage structure of the binary tree, and the node types are as follows:
typedef struct node
{
int data;
struct node *lchild, *rchild;
struct node *parent;
}BinTNode;
1. Briefly describe the method of finding the successor of middle order according to the different situations of middle order sequence
- Two cases:
- If there is no right child, the successor node is the first node with the subtree of the current node as the left subtree;
- There are right children, and the successor node is the leftmost node in the right subtree.
2. Write an algorithm to find the middle order successor node of the node referred to by px
- code
BinNode *InorderNext(BinNode *px) { if(px == NULL) retuen NULL; BinNode *p = px; if(px->rchild != NULL) //When you have a right child { p = px->rchild; while(p->lchild != NULL) p = p->lchild; return p; } else // When there is no right child { while(p->parent->lchild!=p && p->parent!=NULL) p = p->parent; return p->parent; } }
3. Use only the child pointer and the parent pointer, and write the algorithm to output the path from root to px;
- Idea: in order to traverse, use the stack to save the path
- code:
void PrintPath(BinNode *root, BinNode *px) { static int path[maxsize]; // maxsize is a defined constant that satisfies the length static int top=0; static int flag=1; // Path found flag, if(root && flag) return; // When the flag is 0, you do not need to traverse down and return directly path[top++] = root->data; if(root == px) // Meet the conditions { for(int i = 0; i < top; i++) print("%d ",path[i]); flag = 0; //flag is set to 0 and the traversal is truncated } PrintPath(root->lchild); PrintPath(root->rchild); top--; }
2016
1. A single linked list of the leading node with the structure of [data; next]. Without changing the linked list, find the node at the penultimate k (positive integer) position in the linked list; If the search is successful, the data value of the node is output and 1 is returned; Otherwise, only 0 is returned;
-
1. Idea: set two pointers, The first pointer goes K steps first (if the pointer points to null, it means K is illegal) and points to the k-th node excluding the head node; at this time, the second pointer points to the next node of the head node (excluding the first node of the head node), and then the two pointers traverse synchronously. When the next node of the first pointer is empty, the second pointer points to the penultimate element;
-
2. Code:
int SearchReNum_K(Linklist *head, int k) { //Print the penultimate element of the lin k ed list Linklist *p1=head, *p2=head->next; for(int i=0; i<k ;i++) // Locate p1 to the K-th node { p1 = p1->next; if(p1 == NULL) return 0; // Illegal k value } while(p1->next != NULL) // Traverse until p1 points to the tail node { p1 = p1->next; p2 = p2->next; } print("%d ", p2->data); return 1; }
2. To find the minimum path of a weighted digraph, the time complexity is O((V+E)logK)
- Idea: establish a heap to sort the heap by weight. The nodes in the heap are {node;cost}, and sort according to cost. The problem is that the position of the edge in the heap changes after sorting. How to locate the position of the corresponding edge when updating the weight, and traversing the heap should be the worst case (the result is traversed)
- Time complexity: the problem requirements should still not be met. The total number of traversals is E times. The maximum cost of each traversal should be k when traversing and finding edges in the heap;
- code:
typedef struct { //Heap node int cost; //Weight int vex; //vertex }HeapNode; void SHeapUpAdjust(HeapNode* Heap, int k) { //Floating process of single element in small top heap, k floating element position int i=k, j=k/2; HeapNode temp = Heap[k]; while (j>0) { if (temp.cost < Heap[j].cost) { Heap[i] = Heap[j]; i = j; //Continue to check whether the node needs to float up j = j/2; } else break; } Heap[i] = temp; } void SHeapDownAdjust(HeapNode* Heap, int k, int h) { // The sinking process of a single element in the small top pile, k: the position of the element to be adjusted; h: Total length of heap int i = k, j = 2*k; HeapNode temp = Heap[i]; while(j<=h) { if (j<h && Heap[j].cost > Heap[j+1].cost) j++; if (temp.cost > Heap[j].cost) { Heap[i] = Heap[j]; i = j; j = 2*j; } else break; } Heap[i] = temp; } void HeapDijkstra(AGraph *G, int v) { int dist[maxsize], path[maxsize], isJoin[maxsize]; int num = 0; //Number of valid nodes in the heap int pos; //Position the node in the heap ArcNode *p; HeapNode heap[maxsize+1]; for (int i = 0; i < maxsize+1; i++) //Initialize array { if (i<maxsize) { dist[i] = MAX; path[i] = -1; isJoin[i] = 0; } heap[i].cost=MAX; // The initial cost is MAX heap[i].vex = -1; // Node initialized to - 1 } dist[v] = 0; path[v] = -1; isJoin[v] = 1; for (int i = 0; i < G->v - 1; ++i) { p = G->Adjlist[v].firstarc; while (p!=NULL) // Node heap { if(isJoin[p->vex]) //If edges are added, skip { p=p->nextarc; continue; } pos = 0; for (int k = 1; k < num+1; k++) //Locate the node in the heap { if(heap[k].vex==p->vex) { pos = k; break; } } if(pos && p->cost + dist[v] < heap[pos].cost)//There is already p - > vex in the heap, and the distance from V to p - > vex + dist [v] is less than the existing distance, update the weight { heap[pos].cost = p->cost+dist[v]; path[p->vex] = v; //Record new path } if(!pos) // There is no p - > vex point in the heap. The number of effective nodes is num+1. Fill in the new node in the new position { heap[++num].vex = p->vex; heap[num].cost = p->cost + dist[v]; path[p->vex] = v; } SHeapUpAdjust(heap, num); // Pile bottom floating p=p->nextarc; } dist[heap[1].vex] = heap[1].cost; v = heap[1].vex; // Start the next with the top node isJoin[v] = 1; heap[1] = heap[num--]; //Replace the top node, and the number of effective nodes is - 1 SHeapDownAdjust(heap, 1, num); //Pile top subsidence } }
2017
1. With regard to heap, ask:
- 1. Is the storage method sequential or linked. order
- 2. The maximum element and the minimum element are at the specified position. Maximum: pile top; Minimum: leaf node
- 3. The maximum and minimum number of comparisons in the team building process of n elements;
- Minimum: the heap is original and orderly, and the comparison starts from n/2; If n is an odd number, a total of \ (\ frac{n}{2}*2 = n-1 \) times; If n is an even number, the last node is compared only once, a total of \ (\ frac{n}{2}*2-1 = n-1 \) times.
- At most: assume that the heap is a complete binary tree; Tree height \ (h = log_2n+1 \), compare from the h-1 layer
- In the case of most discussions, each node in the \ (h-1 \) layer only needs to be compared with the next layer twice, with a total of \ (2*2^{h-2}*1 \)
- In addition to comparing with the next layer, the \ (h-2 \) layer needs to continue to compare with the lower layer after falling, with a total of \ (2*2^{h-3}*2 \)
- Then the maximum number of comparisons for the elements of layer K is \ (2*2^{k-1}*(h-k) \)
- The total number of times is \ (\ sum {k = 1} ^ {H-1} (2 * 2 ^ {k-1} * (H-K)) \) = \ (2 ^ {H + 1}-2 (H + 1) \)
2. Find the intersection of the two linked lists and store the results in hc for the increased order single linked list ha, hb of two non empty leading nodes; It is required that the original linked list cannot be destroyed. The node structure is:
typedef struct Node
{
int data;
struct Node *next;
}Node, *LinkList;
- An efficient algorithm is designed and the time complexity is given
Node *Intersection(LinkList ha, LinkList hb) { // Returns the intersection of two linked lists, the linked list of the leading node LinkList hc = (Node *)malloc(sizeof(Node)); Node *pa = ha->next, *pb = hb->next, *p, *pre; hc->next = NULL; while(pa && pb) { if(pa->data == pb->data) { p = (Node *)malloc(sizeof(Node))); p->data = pa->data; p->next = NULL; if(hc->next == NULL) //Special treatment of the first node { hc->next = p; pre = p; } else // Subsequent node tail interpolation { pre->next = p; pre = p; } } else if(pa->data > pb->data) pb = pb->next; // Smaller nodes go backward else pa = pa->next; } return hc; }
3 design an algorithm to judge whether there are rings in undirected graph
- Idea 1: count the number of edges N and the number of nodes m in the graph. If n > M-1, it indicates that there is a loop
- code:
int DetectLoop(AGraph *G, int v) { static int visit[maxsize]; static int edge, vertex; ArcNode *p = G->Adjlist[v].firstarc; visit[v] = 1; vertex++; // Record vertex while(p!=NULL) { edge++; //Edge recording if(visit[p->vex]==0) DetectLoop(G, p->vex); p = p->nextarc; } if(edge/2 >= vertex) { printf("YES"); return 1; } return 0; } - Idea 2: for depth traversal, you need to mark the last node
- code:
int DetectLoop2(AGraph *G, int v, int pre) { //pre: previous node static int visit[maxsize]; static int flag=0; // Ring marking if(flag) return flag; ArcNode *p = G->Adjlist[v].firstarc; visit[v] = 1; while(p!=NULL) { if(p->vex!=pre && visit[p->vex]) flag = 1; //Find loop if(!visit[p->vex]) DetectLoop2(G, p->vex, v); p = p->nextarc; } return flag; }
Expansion Design an algorithm to judge whether there are rings in a directed graph
- Idea: backtrack the depth traversal. If a node returns to itself again before the depth traversal is completed, it indicates that there is a loop;
Difference from ordinary depth traversal: regular depth traversal will mark a node as accessed after accessing it, and will not access it next time;
The backtracking depth traversal adds a flag to mark the nodes of this round of traversal. If a node is visited twice in a round of traversal, it indicates that there is a ring; - code:
- Figure structure
typedef struct ArcNode { //Edge node int vex; //Node information pointed by the current edge int cost; //Edge cost struct ArcNode *nextarc; //Next edge }ArcNode; typedef struct VNode { //Vertex node int vex; //vertex data ArcNode *firstarc; // The first edge of the vertex }VNode; typedef struct AGraph { //Adjacency table VNode Adjlist[maxsize]; //vertex array int v,e; //The number of vertices and edges of the current vertex }AGraph;- code
int DetectCircle(AGraph *G, int v) { // Detect whether there is a loop in the directed graph based on DFS; static int visit[maxsize]; static int finished[maxsize]; static int flag = 0; //Marker bit if (flag) return 1; //flag is used to intercept traversal. If the conditions are met, it will return directly and will not continue traversal ArcNode *p = G->Adjlist[v].firstarc; visit[v] = 1; finished[v] = 1; // finished[i]=1 indicates that it is still in the current round of traversal. If you visit yourself again, it indicates that there is a loop //printf("%d ",v); while(p!=NULL) { if (finished[p->vex]==1) { flag=1; // The same node is accessed again, indicating that there is a loop; return 1; // Direct return of the loop has been detected; } if(visit[p->vex]==0) { DetectCircle(G,p->vex); finished[p->vex]=0; } p = p->nextarc; } return flag; }
2018
1. A directed graph with n vertices is represented by an adjacency table, and an algorithm is written to find the penetration of vertex k
- Traverse the adjacency table, count and sum, and record the adjacency table as Adjlist
- code
int InDegree(AGraph *G, int k) { ArcNode *p; int sum=0; for(int i=0; i< G->n; i++) { p = G->Adjlist[i].firstarc; while(p != NULL) { if(p->data == k) { sum++; break; } p = p->next; } } return sum; }
2. Recursively find the balance factor of each node in a tree
- Depth traversal: the balance factor of a node is equal to the height of the left subtree minus the height of the right subtree;
- Node structure {lchild; rchild; bf; data}
- code:
int BalanceNum(BinNode *root) { if(root==NULL) return 0; int LD, RD; LD = BalanceNum(root->lchlid); RD = BalanceNum(root->rchlid); root->bf = LD - RD; return (LD>RD)?(LD+1):(RD+1); //Returns the larger + 1 as the upper tree height }
2019
1. Depth first traversal to realize the topological sorting of directed graphs
- Idea: when traversing the exit, record the node, you can get an inverse topological sort sequence, and the inverse output can get a topological sort
- code:
TopoSort(Grapg *G, int v) { static int topo[maxsize]; static int top = 0; static int visit[maxsize]; ArcNode *p = G->Adjlist[v].firstarc; visit[v] = 1; while( p!= NULL) { if(!visit[p->vex]) TopoSort(G, p->vex); p = p->nextarc; } topo[top++] = v; //When recursively exiting a node, the node enters the stack, and the stack sequence is an inverse topology sequence if(top == maxsize) //Reverse order output for(int i=top-1; i>=0; i--) print("%d ", topo[i]); }
2. Use a single linked list to represent integers of any length, and each node stores one bit of integer. Realize the subtraction of two positive integers;
- code
Node *Minus(Node *LA, Node *LB) { //LA - LB LA = Reverse(LA); //Invert the array, subtracting from position to high order LB = Reverse(LB); int carry=0; //carry is a debit. If it is not enough, the next debit is required int i; Node *pla = LA; Node *la = LA->next; Node *lb = LB->next; while (la && lb) { if (la->d < lb->d) //If it is not enough, debit will occur { la->d = la->d - lb->d + 10 - carry; carry = 1; } else { la->d = la->d - lb->d - carry; carry = 0; } la = la->next; lb = lb->next; pla = pla->next; } if (la==NULL) //When the number of digits of a is less than that of b, { pla->next = lb; while (lb!=NULL) { lb->d = 0 - lb->d + 10 - carry; carry = 1; lb = lb->next; } } else //When a has more digits than b, { while (la!=NULL && carry) { if(la->d==0) { la->d = la->d + 10 - carry; } else { la->d = la->d - carry; carry=0; } la = la->next; } } la = LA->next; if (carry==1) //Finally, if the carry is 1, it means that the highest bit still has borrow, and the result is negative { /* For example, 123 - 456 = - 333, after inversion, the corresponding bit subtraction result is 321 - 654 = 766; carry=1，Indicates that the final result is negative; The processing method is for all bits 9-x; The last first digit is + 1; 9-7+1=3； 9-6=3； 9-6=3 The result was - 333; */ while (la!=NULL) { la->d = 9 - la->d; //Subtract all digits with 9 la = la->next; } LA->next->d++; //Single digit correction } la = LA; la = Reverse(la); while (la->next->d == 0) // Position the head node in front of the first non-0 element, and the result is 0, which should be specially considered { if(la->next->next!=NULL) la = la->next; else { la->next->d = 0; break; } } if (carry==1) // Mark positive and negative with header node la->d = -1; else la->d = 1; Show(la); //Returns the header node of the result chain. If the header node is - 1, it means the result is negative, and 1 means the result is non negative; return la; }
2020 articles
1. Binary tree, which outputs the nodes of layer k from left to right;
- Idea: traverse the hierarchy, delete from the front, and insert from the rear
- code:
void K_Floor(BinNode *root, int k) { // Output the node of layer k, and record root as the first layer int queue[maxsize]; // Queue structure {node, n}, n marks the layer of node int le; int front=0, rear=0; // When empty, rear==front. When not empty, front points to the first position and rear points to the last position BinNode *p; queue[rear++].node = root; queue[front].n =1; while(front!=rear) { p = queue[front].node; le = queue[front].n; front = (front+1)%maxsize; if(le < k) //Up to layer k-1, layer K can all join the team { if(p->lchild != NULL) // The left child joined the team { queue[rear].node = p->lchild; queue[rear].n = ++le; // Number of layers + 1 rear = (rear+1)%maxsize; } if(p->rchild != NULL) // Right child join the team { queue[rear].node = p->rchild; queue[rear].n = ++le; // Number of layers + 1 rear = (rear+1)%maxsize; } } if(le = k) print("%d ", p->data); } }
2. Sort the heap, delete the elements at position p, and rearrange the small root heap; The so-called deletion should be to move the number of p position to the end of the array
- Small root heap sort
- code
void SheapDownAdjust(int *heap, ,int k, int h) { int i=k, j=2*k; int temp = heap[i] while(j<=h) { if(j< h && heap[j]>heap[j+1]) j++; //Take the smaller one if(temp>heap[j]) { heap[i] = heap[j]; i = j; j = 2*j; } else break; } heap[i] = temp; } void Delet_p(int *heap, int h, int p) { heap[n] = heap[p]; for(int i=n/2; i>0; i++) SheapDownAdjust(heap, i, h-1); }
2021
1. Let the weighted digraph be represented by adjacency matrix, judge whether there is a path from \ (V_i \) to \ (V_j \) in the graph, and calculate the path length. The description of adjacent order matrix is required.
- Idea: start the depth traversal from \ (V_i \). If the \ (V_j \) node is passed in the traversal, it indicates that there is a path.
- code:
// typedef struct Graph { Adjlist[maxsize][maxsize]; // adjacency matrix int v,e; // Number of vertices and edges } Graph;int MDFS1(Graph *G, int v, int j) { // If there is a path, the length is returned. If it does not exist, - 1 is returned static int visit[maxsize]; static int d=0; //Record traversal length static int result=-1; //Record result length if(result!=-1) return result; //Truncate the traversal. If the result is not - 1, the path has been found if(v == j) result = d; d++; visit[v] = 1; for(int k=0; k<maxsize; k++) if(G->Adjlist[v][k] && !visit[k]) MDFS1(G, k, j); d--; return result; }
2. Possible operators of infix expression to suffix expression + - * / ^ ()
- Idea: use two stacks, one to store operators and the other to store suffix expression results
- When a number is encountered, it is directly put into the result stack
- When encountering an operator (, directly enter the operator stack, encounter), all operators before the last bracket will pop up and enter the result stack; when encountering other operators, if the operator stack is empty, directly enter the stack; if it is not empty, it is necessary to compare the priority with the top of the stack, and the top of the stack has a higher priority or the same priority. Pop the top of the stack into and out of the result stack, otherwise push the existing operators onto the stack;
- code
// auxiliary function int isop(char c) { // c is the operator that returns 1, otherwise it returns 0; return (c=='+'||c=='-'||c=='*'||c=='/'||c=='^')?(1):(0); } int comop(char op1, char op2) { //If the op2 operator has higher or equal priority than the op1 operator, return 1; otherwise, return 0; //if (op2=='(' && op1=='(') return 1; if (op2=='(') return 0; //Encountered parentheses in the stack and returned 0. Calculation is not allowed if (op1=='^') return 0; if (op1=='+' || op1=='-') return 1; if (op2=='*' || op2=='/' || op2=='^') return 1; return 0; } // void IntoRear(char *arr, int n) { char opstack[n]; //Operator stack char restack[n]; //Result stack int optop=-1, retop=-1; for(int i=0; i<n-1; i++) //There is an empty character at the end of the string { if(arr[i]== '(' ) opstack[++optop] = arr[i]; else if(arr[i]== ')') { while(opstack[optop]!='(') restack[++retop] = opstack[optop--]; optop--; //Skip the current '(' } else if(!isop(arr[i])) restack[++retop] = arr[i]; //Digital direct stack else // Operator time { if(optop == -1) opstack[++optop] = arr[i]; //Stack empty, directly into the stack else { // comop(op1, op2). When the priority of op2 is higher than op1, it returns 1, otherwise it returns 0; // opstack[optop] the symbol at the top of the stack may be parentheses. In this case, it is directly put into the operator stack if(opstack[optop]=='(' || comop(opstack[optop], arr[i])) opstack[++optop] = arr[i]; else { restack[++retop] = opstack[optop--]; opstack[++optop] = arr[i]; } } } } while(optop!=-1) restack[++retop] = opstack[optop--]; //Pop up remaining for (int i = 0; i <= retop; i++) printf("%c ",restack[i]); }
2022
Random sequence \ (A[a_0...a_{n-1}] \), design an algorithm so that the elements on the left of \ (a_i \) are less than \ (a_i \), and the elements on the right of \ (a_i \) are greater than \ (a_i \).
- Fast row division idea
- code:
void QuickSort(int *nums, int n) { int L = 0, H = n-1; int temp = nums[L]; while(L<H) { while(L<H && nums[H]>temp) --H; nums[L] = nums[H]; //It cannot be written here as num [L + +] = num [H], because if there is no number smaller than temp in this cycle, then there is H==L. after num [L + +] = num [H], l will be 1 larger than h and point to the wrong position, but num [l] = num [H], there will be a repeated judgment of a [l] < temp, but the result is correct. while(L<H && nums[L]<temp) ++L; nums[H] = nums[L]; } nums[L] = temp; }
Calculate the external weighted path length WPl of a tree, that is, the sum of the weights from the root node to all leaves;
- Tree structure bit {lchild; rchild; weight}
- Idea: depth traversal; The weights on the road are recorded casually and accumulated once when leaf nodes are encountered
- code:
int WPL=0; int sum=0; void CalWPL(BTree *root) { if(root==NULL) return; sum += root->weight; //Weighted value if(!root->lchild && !root->rchild) WPL += sum; CalWPL(root->lchild); CalWPL(root->rchild); sum -= root->weight; //Return weight }
Conclusion:
- The above contents are the contents I sorted out during the review of the 2022 postgraduate entrance examination. Due to my limited personal ability, the accuracy needs to be verified; I hope I can give some help to my friends who take the postgraduate entrance examination later.