102年 - 102 國立嘉義大學_碩士班招生考試試題_資訊工程學系：資料結構#146343

1. Assume there are n objects and you need to store the distances among them. Let a one-dimensional array be used to store distances. Assume the objects are numbered from 0 to n-1, and the distance between an object to itself is not stored. In other words, the distance between object 1 and object 0 is stored at position 0 in the one-dimensional array, and the distance between object 2 and object 0 is stored at position 1. For example, the following matrix shows the storage for the distances among 5 objects. What is the position for the distance between object 100 and object 10? (10%)

2. The node of a tree is declared as:
typedef struct *treePointer;
typedef struct node {
int data;
treePointer left, right;
};
Please use any programming language to write a level-order traversal function for a binary tree. (15%)

3. When inserting a data object to a hash table, we use a hash function top map a key to a bucket in the hash table. Collision occurs when different keys are assigned to a same bucket. Please briefly describe two methods to handle collision. (15%)

4. Please compare a linked list and an array in terms of time and space. (10%)

5. The purpose of Kruskal’s algorithm is to build a minimum cost spanning tree. Give the minimum cost spanning tree of the graph shown below by using Kruskal’s algorithm. (20%)

6. Write the prefix and postfix form of the following expressions: (15%)

7. We want to create a linked list of integers. The node structure is defined in the following:
We want to set the data field of the first node to 50 and that of the second to 100. Write the function listPointer createTwo() in C/C++ to create a two-node linked list. (15%)