Data Structure HW2 Solution

Program Requirement
Programming Language: C
Execution Environment
CPU core: 1
Memory: 2 GB
Execution time limit: 1 second
C Compiler: GCC
C Standard: C 11
Read input from stdin and write your output to stdout.
Use header file only from C Standard Library.
Submit your answer as a C source code file, no executable file.
Your program will be compiled by us.
Homework #11 *
Write a function, insertLeft and insertRight , that inserts a new node, child , as the left child of node parent in a threaded binary tree. The left child pointer of parent becomes the left child pointer of child .
Input Format
Input consist line.
First line contains two numbers and , each separated by whitespace.
represents the number of threaded binary tree insertion operation.
represents the node id of the root node.
Following input consist of line. Each line declares a threaded binary tree child node insertion.
Each line contains three elements , each element is separeated by whitespace.
is the id number of the parent node during insertion.
is a string . It represent the insertion direction (insert as left child or
insert as right child). is the id number of the newly inserted node.
Output Format
Output a series of numbers, each number separated by whitespace.
These numbers describe the inorder traversal of the threaded binary tree.
Technical Specification
are unique.
Describe how your thread binary tree insertion works in the homework report.
Sample Input

Sample Output

Homework #12 *
[Programming Project]
Write a user-friendly, menu-driven program that allows the user to perform the following operations on min heaps.
1. Create a min heap.
2. Remove the key with the lowest value.
3. Change the priority of an arbitrary element.
4. Insert an element into the heap.
Technical Specification
Complete this programming project.
No strict input/output or operation defined in this homework. Just write a user-friendly, menu-driven program that supports those 4 functional requirements.
Demonstrate how to use your program in the homework report. Must cover all those 4 requirements.
Describe how your min heap works in the homework report.
Homework #13
Write a function heightUnion that uses the hight rule for union operations instead of the weighting rule. This rule is defined below:
Definition[Height Rule]:
If the height of tree is less than that of tree , then make the parent of . Your function must run in time and should maintain the hight of each tree as a negative number in the parent filed of the root.
Input Format
A line consists of a number . There will be testcases to be run.
In each testcase, a line with 2 integers , are given. is the number of elements of the whole set. Elements are labeled from to . is the number of operations you need to do.
operations will be given. There 3 operations as follows.
union a1 b1 find a2
same a3 b3
(Note: If two sets with same height perform unioning, the first set a1 be the parent)
Output Format
Each time you gets the operation find , output the root of the set.
Each time you gets the operation same , output true if they are in the same set. Output false if they are not in the same set.
Technical Specification

Sample Input

Sample Output

Homework #14 *
Experiment with function weightedUnion (Program 5.20) and heightUnion to determine which one produces better results when used in conjunction with function collapsingFind (Program
5.21).
Technical Specification
Perform the experiment.
Write down your thought in the homework report.
Remember to provide material(experiment result) to support your thought.
Homework #15
Write an algorithm to construct the binary tree with given
Preorder sequence and inorder sequence
Postorder sequence and inorder sequence
Input Format
Input consists of line.
First line contains one number , represent how many test dataset in the following input.
Following input contains lines describe test dataset, each test dataset composed of lines.
First line of the test dataset contains one string , it will be or
.
Second-line of the test dataset contains one number , represent how many nodes in the binary tree.
Third-line of the test dataset contains a series of numbers. . It represent the preorder or postorder sequence of specific binary tree, The decision is based on what is. If is , then it is preorder sequence. If
, then it is postorder sequence.
Forth-line of the test dataset contains a series of numbres. . It represent the inorder sequence of specific binary tree.
Output Format
The output should consist of lines.
For each test dataset, output one line contains a series of numbers. Each is separated by one whitespace.
If the in test dataset is , then output the postorder sequence of the reconstructed binary tree.
If the in test dataset is , then output the preorder sequence of the reconstructed binary tree.
Technical Specification

Sample Input

Sample Output

Homework #16
Rewrite dfs so that it uses an adjacency matrix representation of graphs.
Input Format
First line of the input consist of one number , represent how many datasets in the following input.
Each dataset consists of line.
First line of the dataset contains two numbers , .
represents the number of vertices in the given graph.
is a vertex index, it represents the entrypoint of the dfs traversal.
The rest of the lines in the dataset describe a matrix which describes an undirected graph in the adjacency matrix.
Output Format
For each dataset, output one line.
Each line consist of numbers. It represent the dfs visit order of the given graph.
Technical Specification
The given graph will be undirected.
When there are multiple vertices available, always start from the vertex with the smallest index.
Sample Input


Sample Output

Homework #17
Rewrite bfs so that it uses an adjacency matrix representation of graphs.
When there are multiple vertices available, always start from the vertex with smallest index.
Input Format
First line of the input consists of one number . It represents how many datasets are in the following input.
Each dataset consists of line.
First line of the dataset contains two numbers , .
represents the number of vertices in the given graph.
is a vertex index, it represents the entry point of the bfs traversal.
The rest of the lines in the dataset describe a matrix which describes an undirected graph in adjacency matrix.
Output Format
For each dataset, output one line.
Each line consists of numbers. It represents the dfs visit order of the given graph.
Technical Specification
The given graph will be undirected.
When there are multiple vertices available, always start from the vertex with the smallest index.
Sample Input


Sample Output

Homework #18
Write a C function that finds a minimum cost spanning tree using Kruskal's algorithm.
Input Format
First line of input consists of two numbers and . represents the vertices count. represents the number of edges in this undirected graph.
The rest of the input contains lines. Each line contains three numbers , and . It declares an undirected edge from vertex to vertex with a cost along with this path.
Output Format
The output consists of one number, . It represents the sum of all edge cost in the minimum spanning tree in terms of the given graph.
Technical Specification

Sample Input

Sample Output

Homework #19
Let be a tree with root . The edges of are undirected. Edge in has a nonnegative length. Write a C function to determine the length of the shortest paths from to the remaining vertices of . Your function should have complexity , where is the number of vertices in . Show that this is the case.
Input Format
The input describes a tree topology in a graph way.
The first line of the input is a number . It represents the vertices count. Each vertex has one id, it ranges from to .
The rest of the input contains lines.
For the first lines, ecah line consists of three numbers , and . It describes a edge between vertex and vertex in this undirected graph.
The last line of input consists of one number , which represents the root of the tree. You are going to calculate the shortest path to each tree child node from here.
Output Format
The output consists of lines.
Each line consists of two numbers and .
represnet the index of vertex . represents the cost to walk from vertex to this vertex .
Technical Specification
, there is only one path to connect and .
Sample Input

Sample Output

Homework #20 *
Compare the performance of leftist trees and min heaps under the assumption that the only operations to be performed are insert and delete min. For this, do the following:
Create a random list of elements and a random sequence of insert and delete-min operations of length . The latter sequence is created such that the probability of an insert or delete-min operation is approximately 0.5. Initialize a min leftist tree and a min heap to contain the elements in the first random list. Now, measure the time to perform the operations using the min leftist tree as well as the min heap. Divide this time by to get the average time per operation. Do this for = 100, 500, 1000, 2000, ...,5000. Let be 5000.
Tabulate your computing times.
Based on your experiments, make some statements about the relative merits of the two priority-queue schemes.
Technical Specification
Perform this experiment, tabulate the result in the homework report.
Based on your experiments, make some statements about the relative merits of the two priority-queue schemes in the homework report.