Abstract Data Structures

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Thinking recursively[edit]

5.1.1 Identify a situation that requires the use of recursive thinking.

5.1.2 Identify recursive thinking in a specified problem.

Subprogram statements[edit]

Recursive binary search[edit]

Quicksort[edit]

5.1.3 Trace a recursive algorithm to express a solution to a problem.

Abstract data structures[edit]

5.1.4 Describe the characteristics of a two-dimensional array.

One-dimensional array is an liner array, but two-dimensional array is more like a plane. If we want to explain how long of an line is, we can said,"it has 6 meters long". If we want to explain how large of an plane is, we can said,"it has 6*6 meters large", or "36 meters square". So one-dimensional array has one parameter to represent (x), but two-dimensional array has 2 parameters to represent (x,y). Another, two-dimensional array can be considered as numbers of one dimensional array combine each other.
Two-dimensional array can be considered as an table, one parameter representing row and another parameter representing column. Using that two parameters to determine the location of an specific data. The notation is array[x][y] (x,y can be any integer number but should be within the range of parameter). The parameter (x,y) started with "0", data type is integer. Generally, one two-dimensional array only contain one type of data (int, char, long int) or one type of object (often defined by class), and the type is declared before.

5.1.5 Construct algorithms using two-dimensional arrays.

5.1.6 Describe the characteristics and applications of a stack.

5.1.7 Construct algorithms using the access methods of a stack.

5.1.8 Describe the characteristics and applications of a queue.

5.1.9 Construct algorithms using the access methods of a queue.

5.1.10 Explain the use of arrays as static stacks and queues.

Linked lists[edit]

5.1.11 Describe the features and characteristics of a dunamic data structure.

5.1.12 Describe how linked lists operate logically.

5.1.13 Sketch linked lists (single, double and circular).

Trees[edit]

5.1.14 Describe how trees operate logically (both binary and non-binary).

5.1.15 Define the terms: parent, left-child, right-child, subtree, root, and leaf.

5.1.16 State the result of inorder, postorder, and preorder tree traversal.

5.1.17 Sketch binary trees.

Applications[edit]

5.1.18 Define the term dynamic data structure.

5.1.19 Compare the use of static and dynamic data structures.

5.1.20 Suggest a suitable structure for a given situation.