Data Structure HW1 Solution

Program Requirement
Programming Language: C
Execution Environment
CPU core: 1
Memory: 2 GB
Execution time limit: 1 second
C Compiler: GCC
Compiled with -O3 -std=c11 -Wall
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 #1
The Fibonacci numbers are defined as:

Write both a recursive and iterative C function to compute .
Input Format
The first line of input contains a number . It represents the amount of questions.
After the first-line, the following will have line of text. Each line contains a string and a number , separate by a whitespace character. The can be recursive or iterative , which stands for which Fibonacci algorithm your program is going to execute. The number will be the subscript of the Fibonacci number .
Output Format
Output line of text. Each line contain the corresponding value.
Technical Specification

Sample Input

Sample Output

Homework #2
There are three towers and disks of different diameters placed on the first tower. The disks are in order of decreasing diameter as one scans up the tower. Monks were reputedly supposed to move the disk from tower 1 to tower 3 obeying the rules:
Only one disk can be moved at any time.
No disk can be placed on top of a disk with a smaller diameter.
Write a recursive function that prints out the sequence of moves needed to accomplish this task.
Input format
A line of input contains a number . It represents the amount of disks which you placed on the first tower.
Output format
Output the sequence of moves needed to accomplish your tower.
First column shows the number of disk.
Second column shows the disk that you determined in first column where it is in which tower.
Third column shows the destination of the disk you moved.
Technical Specification

Sample input

Sample output

Homework #3
Rewrite fastTranspose so that it uses only one array rather than the two arrays required to hold rowTerms and startingPos .
Intput Format
Input consist of line.
First-line contain three number . The matrix size will be is the number of enties in the matrix.
Next lines, each line contains three numbers . Represent the row-index, column-index and element-value.
The input matrix entries are sorted by and in ascending order.
Output Format
Output line.
First-line contains the related to the transposed matrix.
Following line, each contains three number , , .
The output matrix entries are sorted by and in ascending order.
Technical Specification

Sample Input

Sample Output

Homework #4
A (drunken) cockroach is placed on a given square in the middle of a tile floor in a rectangular room of size tiles. The bug wanders (possibly in search of an move from his present tile to any of the eight tiles surrounding him (unless he is against a wall) with equal porbability, how long will it take him to touch every tile on the floor at least once?
An array count is used to represent the number of times our cockroach has reach each tile on the floor. All the cells of this array are initialized to zero. The position of the bug on the floor is represented by the coordinates (ibug, jbug). The eight possible moves of the bug are
represented by the tiles located at , where ,
and

A random walk to any one of the eight neighbor squares is simulated by generating a random value for , lying between and . Of course, the bug cannot move outside the room, so that coordinates that lead up a wall must be ignored, and a square is incremented so that a nonzero entry shows the number of times the bug has landed on that square. When every square has been entered at least once, the experiment is complete.
Write a program to perform the specified simulation experiment. Your program MUST:
(a). handle all values of and ;
(b). perform the experiment for (1) , starting point (10, 10), and (2)
, starting point
For each experiment, print (1) total number of legal moves that the cockroach makes and (2) the final count array. This will show the "density" of the walk, that is, the number of times each tile on the floor was touched during the experiment.
This exercise was contributed by Olson.
Input Format
The input consist of multiple lines. Each line have any one the following format.
A line consists of one character 'a' and two integer numbers , which , . Represent problem (a).
A line consists of one character 'b' and one integer number which is or . Represent problem (b)(1) and (b)(2).
A line consists of one character 'q'. (Quit the program.)
Output Format
For each problem:
A line consists of one integer which is the total number of steps; following with lines, each consist of numbers. Each lines represents the row of cells. They are the numbers of visit of that cell.
Sample Input

Sample Output
The output will vary from run to run. We only test the following conditions.
1. All cells walked.
2. The sum of steps match the sum of all number in the cells.
15
3 1
6 5
11
1 2 1
3 3 1
28
1 1
6 4
9 7
2703
12 24 18 11 3 6 6 7 6 5 2 3 5 7 1
19 25 20 15 17 10 13 15 5 6 6 6 7 8 5
18 19 19 13 13 15 10 10 7 4 7 6 9 9 6
22 31 11 8 8 5 10 8 8 8 4 6 5 9 4
21 29 21 14 13 3 5 12 6 10 5 3 9 5 2
19 37 31 18 11 8 8 3 9 7 6 12 3 4 4
18 21 23 18 15 4 13 9 9 14 9 8 3 4 4
20 23 19 12 5 8 10 11 7 9 9 6 12 6 1
13 17 12 9 4 12 6 9 5 8 7 8 6 6 4
12 19 18 12 8 10 8 3 4 5 6 9 7 12 10
13 19 15 10 10 13 14 8 5 4 4 17 21 22 19
13 28 21 18 14 18 20 11 10 8 10 23 18 27 22
7 14 14 19 18 17 20 17 14 12 27 25 22 17 24
5 7 14 21 22 21 8 13 11 19 42 24 20 24 25
3 9 16 13 10 7 4 3 6 18 26 17 6 14 11
11582
11 27 14 6 1 2 5 4 5 6 2 4 3 3 4 5 4 5 1
19 18 23 16 9 6 7 10 6 6 6 8 11 7 7 5 9 4 2
11 14 13 13 13 5 2 6 8 5 3 6 7 9 6 7 9 11 4
20 18 12 13 7 3 6 5 3 3 3 5 11 9 15 19 9 17 9
16 21 14 6 11 8 9 8 5 3 5 7 8 12 23 22 18 14 8
13 19 11 9 7 6 9 11 5 7 6 7 13 22 27 15 16 13 12
8 16 11 9 9 9 6 13 7 5 4 7 12 21 14 23 23 16 12
11 13 12 15 12 11 5 10 8 8 5 8 7 17 26 14 22 18 18
5 11 14 10 12 11 5 16 8 6 7 10 14 10 16 27 21 19 17
4 14 11 14 13 13 13 12 8 7 14 11 13 18 19 23 21 26 16
11 15 17 18 21 11 13 13 13 7 13 15 18 17 14 19 16 19 14
13 15 12 16 10 12 17 17 12 10 14 18 11 16 14 14 16 23 19
9 13 15 15 17 11 13 15 11 14 15 23 12 12 14 15 20 32 18
3 12 9 13 17 16 9 8 11 15 19 11 14 15 14 16 34 27 17
7 12 11 9 16 14 7 5 6 23 12 10 23 20 18 21 25 31 12
8 13 12 17 13 16 12 8 14 17 14 20 20 17 14 23 20 22 18
8 12 16 9 12 9 10 10 11 16 14 17 12 20 20 22 19 16 13
14 26 15 20 13 10 9 7 16 10 14 15 15 23 21 13 20 20 17
18 24 24 17 10 9 9 10 8 11 10 16 12 14 9 15 22 17 16
15 20 13 7 11 11 7 6 7 10 10 12 9 8 15 20 22 18 8
11 15 17 12 12 8 8 7 3 14 18 9 7 15 21 23 20 17 15
9 11 14 9 17 15 8 11 7 7 9 14 14 12 11 32 30 27 21
8 12 14 17 15 19 13 5 9 7 10 11 12 16 21 38 49 35 21
10 8 17 22 17 18 14 8 12 4 6 5 15 25 29 47 41 35 17
6 14 11 14 14 12 15 18 5 4 8 5 15 24 21 37 27 22 12
7 17 14 11 12 13 18 10 13 6 10 15 7 21 25 19 26 21 9
10 13 21 9 12 12 16 18 18 16 16 17 12 16 26 22 23 16 10
14 25 19 13 18 17 10 10 23 26 23 17 18 25 25 16 20 19 6
14 25 26 18 22 23 15 16 22 17 23 17 18 15 17 16 12 19 11
18 25 27 28 23 20 21 29 21 20 20 20 18 22 13 7 14 18 10
24 29 21 18 17 22 14 22 23 18 27 26 20 16 13 18 13 10 10
30 40 20 16 19 19 15 13 22 32 31 29 23 17 21 15 18 13 9
32 38 28 27 23 19 25 14 20 24 27 37 24 21 20 16 18 17 9
24 36 29 29 20 20 19 17 17 21 19 28 19 15 18 18 21 14 9
20 31 27 31 20 14 19 20 23 20 20 17 18 14 19 19 22 24 14
14 28 35 28 14 13 13 23 29 25 31 23 18 21 17 24 23 30 14
16 29 26 22 15 12 10 13 37 34 30 33 27 26 31 28 35 28 20
10 23 18 13 7 15 18 25 31 24 30 24 21 33 41 37 36 38 14
6 11 9 4 4 5 14 14 12 18 13 11 14 24 37 24 15 25 14
Homework #5
Using the information provided in the text, write a complete program to search a maze. Print out the entrance to exit path if successful.
Input Format
First-line contain two number and . Represent the height and width of the input maze. After first-line there will be lines of input. Each line contain numbers .
All numbers are separated by a whitespace.
The value of number might be or . represent a road in the maze. represent a wall in the maze.
Output Format
The entry point of the maze will be the most northwest point at . Your goal is reach the most southeast point at
Output the path from the entry to the exit, each line contain two number and . Represent the coordinate of current position.
If there is no such path, output no answer .
Technical Specification

You can assume there is only one way or no way to walk from the entry to the exit.
Sample Input

Sample Output

Homework #6
Write two C functions, first one transforms a prefix expression into a postfix one,second one transforms a postfix expression into a prefix.
Input Format
First-line contains one string. It represent the prefix expression
Second-line contains one string. It represent the postfix expression .
Output Format
The output contains two lines.
First-line contains one string. It represents the postfix expression of
Second-line contains one string. It represents the prefix expression of .
Sample Input

Sample Output

Homework #7
Design and build a linked allocation system to represent and manipulate polynomials. You should use circularly linked lists with header nodes. Each term of the polynomial will be represented as a node, using the following structure:
coef expon link
In order to erase polynomials efficiently, use the available space list and associated functions discussed in this seciton.
Write and test the following functions: pread . Read in a polynomial and convert it to its circular representation. Return a pointer to
the header node of this polynomial. pwrite . Output the polynomial using a form that clearly displays it. padd . Compute . Do not change either or . psub . Compute . Do not change either or . pmult . Compute . Do not change either or .
eval . Evaluate a polynomial at some point, where is a floating point constant. Return
the result as a floating point. perase . Return the polynomial represented as a circular list to the available space list.
Input Format
Input consist of line.
First-line contain one number . Represent how many queries in following line.

a string. the name for of a string. Represent the expression name of of a string. Represent the expression name of of
a string. Represent the expression name to evaluate.
a string. Represent the expression name to erase.
Output Format

Technical Specification

Sample Input


Sample Output

Homework #8
Write the following C functions.
[read] accept a tree represented as a parenthesized list as input and create the generalized list representation of the tree.
[copy] make a copy of a tree represented as a generalized list.
[isequal] test for equality between two trees represented as generalized lists.
[clear] delete a tree represented as a generalized list.
[write] output a tree in its parenthesized list notation.
Input Format
First-line of input contain one number . It represent the amount of commands.
After first-line, there will be line, each line consist of one command.
Each command having their own format.
tree id 1 is a number. Represent the first tree to compare with. tree id 2 is a number. Represent the second tree to compare with. write id is a number. Represent the tree to output.
Output Format
For each received command, output the following corresponding info.
read , output readed copy , output copied isequal , output true or false based on comparing result. clear , output cleared write , output the corresponding tree in generalized list notation.
Technical Specification
For each tree id number , we have
For each generalized-list string .
The node data will be an uppercase alphabet, possible value range from to . You can assume there is no operation will lead whole program to illegal state. For example:
copy/write/test equal to/delete a non-exists generalized list, or read a malformed generalized list.
The generalized list describe tree node values in a unordered manner. To define a strict output order result, the output node should be order by their alphabet order.
For example: since in alphabet order, we should output
(A(B,C)) instead of (A(C,B)) . Given (A(C(X),B(Z))) , we should output (A(B(Z),C(X))) .
Sample Input

Sample Output

Homework #9
1. Write a nonrecursive version of funciton preorder
2. Write a nonrecursive version of function postorder
Input Format

The input contains two lines.
1. First-line contains one number . It represents how many number in the next line.
2. Second-line contains numbers , each separated by a whitespace. These numbers describe a binary tree with a special preorder traversals.
Usually, during the preorder traversal of a binary tree, we ignore null child reference. But with this special preorder traversals, we output null child reference as . With this information, you should be able to generate only one kind of binary tree.
Output Format
The output contains two line.
1. First-line contains a series of number. It represents the preorder of input binary tree.
2. Second-line contains a series of number. It represents the postorder of input binary tree.
Technical Specification

Sample Input

Sample Output

Homework #10

Input Format
The input contains two lines.
1. First-line contains one number . It represents how many number in the next line.
2. Second-line contains numbers , each separated by a whitespace. These numbers describe a binary tree with a special preorder traversals.
Usually, during the preorder traversal of a binary tree, we ignore null child reference. But with this special preorder traversals, we output null child reference as . With this information, you should be able to generate only one kind of binary tree.
Output Format
The output contains two line.
1. First-line contains a series of number. It represents the preorder traversal of swapped binary tree.
2. Second-line contains a series of number. It represents the inorder traversal of swapped binary tree.
Technical Specification

Sample Input

Sample Output