soru |
cevap |
1. Describe a data structure. Give an example of a Data Structure. öğrenmeye başla
|
|
a collection of data values, the relationships among them, and the functions or operations that can be applied to the data. eg a Stack Queue or List
|
|
|
2. Describe the four different categories of data structures. öğrenmeye başla
|
|
Linear, Hierarchical, set, Graphs
|
|
|
3. Describe an Abstract Data Type (ADT). What is the function of an ADT? öğrenmeye başla
|
|
An ADT is a collection of data and associated methods stored as a single module. What is the function of an ADT?
|
|
|
4. Explain what is meant by O(n). öğrenmeye başla
|
|
Linear time exicution, as the number of elements (n) increases so does operational time
|
|
|
5. Explain what is meant by O(1) öğrenmeye başla
|
|
Constant time exicution, the method will always execute in 1 time unit
|
|
|
6. Describe the technique of recursion. öğrenmeye başla
|
|
solving a large problem by solving the same problem with a smaller scope, repeating the recursive step until the base case is reached. The case being a known answer
|
|
|
7. Explain what is meant by Tail End Recursion öğrenmeye başla
|
|
there is one recursive call in an algorithm and this call is the very last thing the done.
|
|
|
8. In recursion explain what is backtracking öğrenmeye başla
|
|
Backtracking is a systematic trial and error approach to finding the solution to a problem. Backtracking algorithms are useful where initially there appear to be many solutions but few survive further tests.
|
|
|
9. Describe linear search algorithm öğrenmeye başla
|
|
a method for finding a target value within a list. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched.
|
|
|
10. Describe binary search algorithm öğrenmeye başla
|
|
finds the position of a target value within a sorted data structure.
|
|
|
öğrenmeye başla
|
|
A queue is a collection of objects organised such that the object that has been stored in the queue the longest is the next one removed A queue is a linear data structure
|
|
|
öğrenmeye başla
|
|
A stack is a collection of objects where only the most recently inserted object can be removed at any time. A stack is a linear data structure. Last-In First-Out structure – LIFO
|
|
|
13. Describe a Singly Linked List öğrenmeye başla
|
|
Linked list is a collection of objects, called nodes Every node has two components information to be stored (the data) reference to the next node (often called a link).
|
|
|
öğrenmeye başla
|
|
Extension of an ordered SLL with Additional forward links, added in a randomized way. Probabilistic data structure Based on a set of parallel linked lists
|
|
|
15. Describe the process of inserting a new node into a Singly Linked List öğrenmeye başla
|
|
The list is empty. New node inserted as the only node The list is not empty. New node inserted somewhere within the list New node inserted at the front of the list. New node inserted at the end of the list.
|
|
|
16. Describe the process of inserting a new node into a SkipList öğrenmeye başla
|
|
Determine level by using a probabilistic technique a random number generator to determine level of insertion. Find where to insert you will need to build an array to hold references for each level. Insert by adjusting references at each level
|
|
|
öğrenmeye başla
|
|
Hashing involves using an array for the efficient storage and retrieval of information
|
|
|
18. Describe 2 method of handling collisions in a has table öğrenmeye başla
|
|
Collision Resolution with Chaining a linked list at each hash site Collision Resolution with Open Addressing change the hash site for a conflict
|
|
|
19. What is the big-O time complexity of traversing a singly linked list? Explain your answer. öğrenmeye başla
|
|
O(n) for unsorted data using linear search or O(log2n) for sorted data using binary search
|
|
|
20. What are the disadvantages of using a linked list öğrenmeye başla
|
|
They use more memory than arrays because of the storage used by their pointers. Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access.
|
|
|
21. Describe a Binary Tree öğrenmeye başla
|
|
consists of a collection of nodes (elements) where each node has a unique predecessor and many successors. every node is of degree two or less.
|
|
|
22. Describe a Binary Search Tree öğrenmeye başla
|
|
Keys in the left subtree of the root precedes the key in the root Key in the root node precedes the keys in the right subtree Left and right subtrees of the root are also BSTs
|
|
|
23. Define the height of a tree öğrenmeye başla
|
|
The height of a tree is the number of edges on the longest downward path between the root and a leaf
|
|
|
24. Define the level of a node in a tree öğrenmeye başla
|
|
The level of a node is defined by 1 + the number of connections between the node and the root. or level = depth + 1
|
|
|
25. Create/build a Binary Search Tree from a given set of data. öğrenmeye başla
|
|
|
|
|
26. Define the Depth First Traversal of a binary tree. What data structure is used? öğrenmeye başla
|
|
proceeds along a path from the root through one child to the most distant descendant of that first child before processing the second child. Implementation uses a stack
|
|
|
27. Define the Breadth First Traversal of a binary tree. What data structure is used? öğrenmeye başla
|
|
proceeds horizontally from the root to all of its children then to its children’s children and so on... Implementation uses a queue.
|
|
|
28. A full binary tree consists of 2n+1 nodes. How many of these nodes will be leaf leaves? Explain why. öğrenmeye başla
|
|
(n+1)/2. In the simplest case a binary tree with a root node, a left and a right has 3 nodes, two of which are leaf nodes.
|
|
|
29. What is the maximum number of nodes in a binary search tree of height h? Explain your answer. öğrenmeye başla
|
|
2n-1 where n = height, Given thatThe maximum number of nodes: in a BST of height 1 = 1 , in a BST of height 2 = 3 (The tree now has 1 node on level 0 and two nodes on level 1) in a BST of height 3 = 7
|
|
|
30. A binary Search Tree is created by inserting numbers in numerical order. What do you know about the shape of this tree? Explain why. öğrenmeye başla
|
|
You get a simple list as the creation of the BST sorts the data
|
|
|
31. What is postfix notation? öğrenmeye başla
|
|
an alternative way that can be used to represent an expression with the opperators after the opperands There is only one way to represent an expression using Postfix notation. This notation is used in Complier design to generate our unambiguous code
|
|
|
32. What is an expression tree or parse tree? öğrenmeye başla
|
|
is an ordered, rooted tree that represents the syntactic structure of a string according to some context-free grammar.
|
|
|