|
|
Posted on 11/25/2014 12:46:30 PM
|
|
|
Data Structure Paper (1)
1. Multiple choice questions (2 points per question, 20 points in total)
1. The common characteristics of stacks and queues are ( ).
A. Only allow insertion and deletion of elements at the endpoint
B. All first-in, last-out
C. It's all first-in, first-out
D. There is no common ground
2. The queue stored in a linked manner is inserted when performing the insertion operation ( ).
A. Only the head pointer is modified B. The head and tail pointers must be modified
C. Modify only the tail pointer D. The head and tail pointers may need to be modified
3. Which of the following data structures is a nonlinear structure? ( )
A. Queue B. Stack C. Linear table D. Binary tree
4. If there is a two-dimensional array A[m][n], assuming that A[0][0] is stored at 644 (10), and A[2][2] is stored at 676 (10), each element occupies a space, where is A[3][3][3](10) stored? Footnote (10) indicates that it is expressed in decimal.
A．688 B．678 C．692 D．696
5. Trees are best used to represent ( ).
A. Ordered data elements B. Unordered data elements
C. Data with branching hierarchical relationships between elements D. Data without connection between elements
6. The maximum number of nodes in the kth layer of the binary tree is ( ).
A．2k-1 B.2K+1 C.2K-1 D. 2k-1
7. If there is an ordered table of 18 elements stored in a one-dimensional array A[19], the first element is placed in A[1], and now a binary search is performed, then the subscript of the comparison sequence to find A[3] is ( )
A. 1，2，3 B. 9，5，2，3
C. 9，5，3 D. 9，4，2，3
8. Quickly sort the files of n records, and the auxiliary storage space required is roughly the same
A. O（1） B. O（n） C. O（1og2n） D. O（n2）
9. For linear tables (7, 34, 55, 25, 64, 46, 20, 10) for hash storage, if H(K)=K %9 is selected as the hash function, there are ( ) elements with a hash address of 1.
A．1 B．2 C．3 D．4
10. An undirected graph with 6 nodes, and the graph should have at least ( ) edges to ensure a connected graph.
A.5 B.6 C.7 D.8
2. Fill in the blanks (1 point per blank, 26 points in total)
1. The quality of the algorithm is usually evaluated from four aspects: _________, _________, _________, and _________.
2. The time complexity of an algorithm is (n3+n2log2n+14n)/n2, and its order of magnitude is expressed as ________.
3. Assuming that the generalized table of a tree is represented as A(C,D(E,F,G),H(I,J)), then the number of nodes contained in the tree is __________, the depth of the tree is ___________, and the degree of the tree is _________.
4. The value of the suffix formula 9 2 3 +- 10 2 / - is __________. The suffix formula corresponding to the middle formula (3+4X)-2Y/3 is _______________________________.
5. If a binary tree is stored with a linked list, each node has two pointers to the left child and the right child in addition to the data field. In this storage structure, the binary tree with n nodes has a total of ________ pointer fields, of which ________ pointer fields store addresses and ________________ pointers are empty pointers.
6. For a directed graph and an undirected graph with n vertices and E-bar edges, there are _______ and ________ edge nodes in its corresponding adjacency table, respectively.
7. AOV network is a ___________________ graph.
8. In an undirected complete graph with n vertices, there are ________ edges, and in a directed complete graph with n vertices, there are ________ edges.
9. Assuming that a linear table is (12,23,74,55,63,40), if the elements of the same remainder become a subtable according to the Key % 4 condition, the four subtables obtained are ____________________________, ___________________, _______________________ and __________________________.
10. In the process of inserting elements into a B_ tree, if the root node of the tree is finally split, the height of the new tree is ___________ than that of the original tree.
11. In the process of heap sorting, the time complexity of sieving any branch node is ________, and the time complexity of the whole heap sorting process is ________.
12. In quick sorting, heap sorting, and merge sorting, _________ sorting is stable.
Data Structure Paper (2)
1. Multiple-choice questions (24 points)
1. The following description of linear tables is incorrect ().
(A) Linear tables are stored sequentially and must occupy a contiguous piece of storage space
(B) Linear tables are chained and do not take up a continuous piece of storage space
(C) Linear tables are implemented with chained storage to facilitate insertion and deletion operations
(d) Linear tables are implemented with sequential storage to facilitate insertion and deletion operations
2. Suppose the total number of leaf nodes in the Huffman tree is m, and if a binary linked list is used as the storage structure, there are a total of ( ) empty pointer fields in the Huffman tree.
(A) 2m-1 (B)2m (C)2m+1 (D)4m
3. If the head and tail pointers of the sequential loop queue Q[0:M-1] are F and R respectively, the head pointer F always points to the previous position of the head element, and the tail pointer R always points to the current position of the tail element, then the number of elements in the loop queue is ( ).
(A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M
4. If the middle order traversal sequence of a binary tree is ABCD and the previous sequence traversal sequence is CABD, then the sequence obtained by traversing the binary tree in the subsequent order is ().
(A) BADC (B)BCDA (C) CDAB (D) CBDA
5. Suppose there are n vertices in a completely undirected graph, then there are ( ) edges in the completely undirected graph.
(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1
6. Suppose there are 2000 nodes in a binary tree, then the minimum height of the binary tree is ( ).
(A) 9 (B) 10 (C) 11 (D) 12
7. Suppose there are n vertices in a directed graph, then there are ( ) header nodes in the adjacency table corresponding to the directed graph.
(A) n-1 (B) n (C) n+1 (D) 2n-1
8. Set a set of initial record keyword sequences (5, 2, 6, 3, 8), and the result of a quick sort based on the first record keyword 5 is ( ).
(A) 2，3，5，8，6 (B) 3，2，5，8，6
(C) 3，2，5，6，8 (D) 2，3，6，5，8
2. Fill in the blanks (24 points)
1. In order to effectively apply HASH lookup technology, two problems that must be solved are ____________________ and __________________________.
2. The function of the following program segment realizes the data x into the stack, and requires the correct statement to be filled in the underline.
typedefstruct {int s[100]; int top; } sqstack;
void push(sqstack&stack,int x)
{
if (stack.top==m-1) printf(“overflow”);
else {____________________; _________________; }
}
3. The sequence obtained by traversing the binary sorting tree in the middle order is a ___________ sequence (filled in ordered or unordered).
4. The worst time complexity of quick sorting is ___________, and the average time complexity is __________.
5. If the number of nodes with a degree of 0 in a binary tree is N0 and the node number with a degree of 1 is N1, then the number of nodes with a degree of 2 in the binary tree is _________; If a binary linked list is used as the storage structure of the binary tree, there are _______ empty pointer fields in the binary tree.
6. Suppose the number of vertices and edges in a certain undirected graph are n and e, respectively, and the sum of the degrees of all vertices is d, then e = _______.
7. If the initial record keyword sequence is (55, 63, 44, 38, 75, 80, 31, 56), then the initial heap established by the screening method is ___________________________.
8. It is known that the adjacency table storage structure of a directed graph is as follows: From vertex 1, the output sequence of DFS traversal is:
, the output sequence of BFS traversal is
Data Structure Paper (3)
1. Multiple-choice questions (1 point per question, 20 points in total)
1. If the binary form of a data structure is expressed as A=(D,R),D={01,02,03,04,05,06,07,08,09}, R={r},r={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,<03,08>,<03,09>}, then the data structure A is ( ).
(A) Linear structure (B) Tree structure (C) Physical structure (D) Graphical structure
2. The time complex of the following program is ()
for（i=1，s=0； i<=n； i++） {t=1；for(j=1；j<=i； j++) t=t*j； s=s+t； }
(A) O(n) (B) O(n2) (C) O(n3) (D) O(n4)
3. Set the pointer variable p to point to node A in a single linked list, if you delete node A in a single linked list, you need to change the operation sequence of the pointer to ().
(A) q=p->next； p->data=q->data； p->next=q->next； free(q)；
(B) q=p->next； q->data=p->data； p->next=q->next； free(q)；
(C) q=p->next； p->next=q->next； free(q)；
(D) q=p->next； p->data=q->data； free(q)；
4. If there are n record keywords to be sorted, ( ) auxiliary record units are required in the heap sorting.
(A) 1 (B) n (C) nlog2n (D) n2
5. If the initial keyword record keywords are (20, 15, 14, 18, 21, 36, 40, 10), then the result after the end of a quick sort recorded with 20 as the benchmark is ( ).
(A) 10，15，14，18，20，36，40，21
(B) 10，15，14，18，20，40，36，21
(C) 10，15，14，20，18，40，36，2l
(D) 15，10，14，18，20，36，40，21
6. Suppose there are n nodes in the binary sort tree, then the average lookup length in the binary sort tree is ( ).
(A) O(1) (B) O(log2n) (C) (D) O(n2)
7. Suppose there are n vertex e edges in the undirected graph G, then the number of header nodes and table nodes in the corresponding adjacency table is ( ).
(A) n，e (B) e，n (C) 2n，e (D) n，2e
8. Suppose there are n vertices in a strong connection graph, then there are at least ( ) edges in the strong connection graph.
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)
9. There are 5000 record keywords to be sorted, if you need to use the fastest method to select the smallest 10 record keywords, you can use the following ( ) method to achieve this purpose.
(A) Quick sort (B) Heap sort (C) Merge sort (D) Insert sort
10. The following four sorts of ( ) have the greatest spatial complexity.
(A) Insertion sorting (B) Bubbling sorting (C) Heap sorting (D) Merge sorting
2. Fill in the blanks (1 point per blank, 20 points in total)
1. The physical structure of data mainly includes two situations: _____________ and ______________.
2. If there are 500 nodes in a complete binary tree, the depth of the binary tree is __________; If you use a binary linked list as the storage structure for the fully binary tree, there are ___________ empty pointer fields.
3. If the input sequence is 1, 2, 3, then ___________ different output sequences can be obtained after the action of the stack.
4. If the adjacency matrix A[n][n] is used as the storage structure for graph G, then the sum of all elements on row i in the adjacency matrix is equal to the ________ of vertex i, and the sum of all elements on column i is equal to the ________ of vertex i.
5. If there are n nodes in the Huffman tree, there are ________ nodes with a degree of 1 in the Huffman tree.
6. If there are n vertices e in the directional graph G with directional edges, and the sum of all vertices entering degrees is d, then the relationship between e and d is _________.
7. __________ traversing the nodes in the binary sorting tree can obtain an incremental sequence of keywords (filled, middle, or posterior).
8. If there are 100 elements in the lookup table, if you use the dichotomous search method to find data element X, you need to compare it up to ________ times to determine whether data element X is in the lookup table.
9. Whether it is a stack with a sequential storage structure or a stack with a chain storage structure, the time complexity of in-stack and out-stack operations is ____________.
10. A complete binary tree with n nodes, if numbered in order from top to bottom and from left to right starting from 1, the parent node of the ith node is numbered ____________, and the number of the right child node is ___________.
11. If the initial set of recorded keywords is (72, 73, 71, 23, 94, 16, 5), then the result of a quick sort based on the record keyword 72 is ___________________________.
12. If there is a set of directed edges in the directional graph G E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>}, then a topological sequence of the graph is ____________________.
13. The following algorithm implements the keyword with the value of x in the sequential hash list, please fill in the correct statement in the underscore.
struct record{int key; int others; };
inthashsqsearch(struct record hashtable[ ],int k)
{
inti,j; j=i=k % p;
while (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; if (i==j) return(-1); }
if (_______________________ ) return(j); else return(-1);
}
14. The following algorithm implements the key value k in the binary sort tree, please fill in the correct statement in the underscore.
typedefstruct node{int key; struct node *lchild; struct node *rchild; }bitree;
bitree *bstsearch(bitree *t, int k)
{
if (t==0 ) return(0); else while (t!=0)
if (t->key==k)_____________; else if (t->key>k) t=t->lchild; else_____________;
}
Data structure test paper (1) Refer to the answer
1. Multiple-choice questions (2 points per question, 20 points in total)
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A
2. Fill in the blanks (1 point per blank, 26 points in total)
1. Correctness, legibility, strength, and high efficiency
2.O(n)
3.9 3 3
4.-1 3 4 X * + 2 Y * 3 / -
5.2n n-1 n+1
6.e 2e
7. Directional and non-circuit
8.n(n-1)/2 n(n-1)
9.（12，40） （ ） （74） （23,55，63）
10. Add 1
11.O(log2n) O(nlog2n)
12. Consolidation
The answers to other test questions can be seen:
Tourists, if you want to see the hidden content of this post, please Reply
|
Previous:Cisco helps develop the world's innovative talent, today and in the futureNext:November 25, 2014 ESET NOD32 Username & Password [30 days]
|
Posted on 12/30/2014 12:10:55 AM
|
