Integration of data structure major questions in postgraduate entrance examination
2. TJP group
TJP group one
4. Drawing/calculation/proof/algorithm analysis (30 points)
(1) Proof questions (8 points)
If a tree has n1 nodes with degree 1, n2 nodes with degree 2, ... , nm nodes with degree m, prove that the number of leaf nodes is n0 = 1+ {hint: imitate Binary tree property proof}.
(2) Drawing and calculation questions (8 points)
The AOE network of a certain project is shown in the figure on the right, and the weight on the arc is the period of activity a1~a10 (that is, the number of days required to complete the activity).
beg:
① The earliest occurrence time Ve and the latest allowable occurrence time Vl of each event of the project, the earliest start time e and the latest allowable start time l of each activity (please list the times of Ve, Vl, e, and l),
② How long will it take at least to complete this project, and which activities are key activities?
(3) It is known that only five characters C, A, T, F, and I may appear in a certain message, and their frequencies of occurrence are 35, 15, 25, 7, and 18, respectively. Please illustrate a Huffman tree and give the Huffman encoding of each character. (7 points)
(4) Given the keywords of a set of records {78, 12, 45, 98, 23, 109, 85, 68, 89, 256, 34}, ① Write the result of a quick sort of this set of records, and explain this The number of keyword comparisons in the sorting pass; ② Build this group of record keywords into a large root heap (the value of the top element of the heap is the largest). (7 points)
5. Procedure to fill in the blanks (2 points for each grid, 20 points in total)
1. The definition of ordered linear list class (single linked list structure with header) is as follows:
tmd Mad
2. Quick sort: Sort the elements of a[low]...a[high] in descending order of keywords
void QuickSort(Datatype a[], int low, int high)
{
int i = low, j = high;
Datatype temp = a[low];
while (i < j)
{
while (i < j && ___________)
j--;
if (i < j)
a[i++] = a[j];
while (i < j && a[i].key >= temp.key)
______________;
if (i < j)
a[j--] = a[i];
}
a[i] = temp;
if (low < i)
QuickSort(a, low, i - 1);
if (i < high)
____________________;
}
void QuickSort(Datatype a[], int n)
{
QuickSort(a, 0, n - 1);
}
TJP group two
4. Drawing/calculation/proof/algorithm analysis (30 points)
(1) Knowing that the keywords of a group of records are {18,2,10,6,78,56,45,50,110,8}, draw the balanced binary tree of this group of records in the order of input, and find the equal probability The average lookup length of the next lookup success. (8 points)
(2) Set the filling factor to 0.77, hash function H(Key) = Key MOD 11, and repeatedly use H(Key) +1 to resolve conflicts, try to construct a hash table for the record key in (1), please illustrate the surface. (7 points)
(3) The adjacency matrix of the known directed graph is:
V0 V1 V2 V3 V4 V5 V0 0 ∞ ∞ ∞ ∞ ∞ V1 30 0 ∞ 40 ∞ ∞ V2 ∞ 20 0 ∞ ∞ 10 V3 ∞ ∞ 20 0 50 40 V4 10 ∞ ∞ ∞ 0 ∞ V5 20 10 ∞ ∞ 20 0
Try to give: ① original graph, ② adjacency list, ③ inverse adjacency list, ④ strongly connected components. (8 points)
(4) Known keyword sequence {38, 12, 21, 77, 65, 7, 38, 53}, the diagram shows the process of sorting it in the first pass using the quick sort method (increasing by keyword) (7 Minute)
5. Procedure to fill in the blanks (2 points for each grid, 20 points in total)
1. The ordered linear list class is defined as follows:
typedef char Datatype; // or typedef int Datatype;
const int MaxListSize = 100;
class OrderSeqList
{
private:
Datatype data[MaxListSize];
int size; // The actual number of elements, that is, the valid data is data[0]..data[size-1]
public:
OrderSeqList(void);
~OrderSeqList(void);
int ListSize(void) const; // Return the actual size of the linear table, that is, return size
int ListEmpty(void) const; // Determine whether the linear list is empty
int Find(Datatype &item) const; // Returns the position of the item in the linear list
Datatype GetData(int pos) const; // Take out the element at position pos of the linear table
void Insert(Datatype item); // Insert a new element item into the ordered linear list
Delete(Datatype item); // Delete element item in ordered linear list
void ClearList(void); // clear line table
};
The following is the implementation of some member functions: (the element position here refers to the subscript in data)
int OrderSeqList::Find(Datatype &item) const
{
if (size == 0)
return -1;
int i = 0;
while (________________________)
i++;
if (item == data[i])
return i;
else
return -1;
}
void OrderSeqList::Insert(Datatype item)
{
int i;
if (___________________________)
{
cerr << "The sequence table is full and cannot be inserted!" << endl;
exit(1);
}
for (i = size; (data[i - 1] > item) && (i > 0); i--)
data[i] = ___________;
data[i] = __________________;
size++;
}
OrderSeqList::Delete(Datatype item)
{
if (size == 0)
{
cerr << "The sequence table is empty, no element can be deleted!" << endl;
exit(1);
}
int loc = Find(item);
if (loc != -1)
{
for (int j = loc; j < size - 1; j++)
data[j] = _______________;
_______________;
}
}
2. Write a function that removes substrings:
void deletestr(char *str, int start, int span)
{
int i;
int len = strlen(str);
if ((start < 0) || (start > len - 1))
return;
if ((start + span < -1) || (start + span > len))
return;
if (span > 0)
for (i = start; i <= _______________; i++)
str[i] = ________________;
else
for (i = __________________; i <= len + span + 1; i++)
_______________;
}
TJP group three
4. Drawing/calculation/proof/algorithm analysis (30 points)
(1) Proof questions (8 points)
Try to prove the nature of the binary tree: if the depth of a complete binary tree is K, then for a complete binary tree with n nodes, its K is the smallest positive number not greater than long2n.
(2) Drawing and calculation questions (8 points)
The AOE network of a certain project is shown in the figure on the right, and the weight on the arc is the period of activity a1~a10 (that is, the number of days required to complete the activity).
beg:
① The earliest occurrence time Ve and the latest allowable occurrence time Vl of each event of the project, the earliest start time e and the latest allowable start time l of each activity (please list the times of Ve, Vl, e, and l),
② How long will it take at least to complete this project, and which activities are key activities?
(3) It is known that only five characters a, b, c, d, e may appear in a certain message, and their frequency of occurrence is 32, 15, 24, 8, 19 respectively. Requirements: ①Illustrate a Huffman tree; ②Illustrate a binary tree corresponding to the root sequence traversal clues of the Huffman tree. (7 points)
(4) Given a set of recorded keywords {25, 18, 46, 2, 53, 39, 32, 4, 74, 67, 60, 11}, ① shows a balanced binary sort tree (binary search tree); ② lists the average number of searches for each keyword when the search is successful under the condition of equal probability. (7 points)
// ToDo ## 3. LZH group ### LZH group one ### LZH group two ### LZH group three ### LZH group four ### LZH Group Five ### LZH group six ### LZH group seven ## 4. LB group ### LB group one ### LB group two ### LB group three ### LB Group Four ### LB Group Five ### LB group six ### LB group seven ### LB Group Eight