Data Structure and Algorithm - Updated Exam Questions with Answers

Data Structure and Algorithm - Updated Exam Questions with Answers Algorithm - Correct Answers: A computable set of steps to achieve a desired result. Array - Correct Answers: In programming, a list of data values, all of the same type, any element of which can be referenced by an expression consisting of the array name followed by an indexing expression. Arrays are part of the fundamentals of data structures, which, in turn, are a major fundamental of computer programming Data Structure - Correct Answers: The term data structure refers to the way data is organized for use within a program. Correct organization of data can lead to simpler and more efficient algorithms. Common data structures are linked-lists, stacks, queues and trees. FIFO - Correct Answers: First in first out is a policy that items are processed in order of arrival. A QUEUE implements this. Insertion Sort - Correct Answers: Sort by repeatedly taking the next item and inserting it into the final data structure in its proper order with respect to items already inserted. LIFO - Correct Answers: Last in first out is a policy that the most recently arrived item is processed first. A STACK implements this. Linked List - Correct Answers: A data structure in which a list of nodes or elements of a data structure connected by pointers. A singly linked list has one pointer in each node pointing to the next node in the list; a doubly linked list has two pointers in each node pointing to the next and previous nodes. In a circular list, the first and last nodes of the list are linked together. Linear Search - Correct Answers: A simple, though inefficient, search algorithm that operates by sequentially examining each element in a list until the target element is found or the last has been completely processed. Linear searches are primarily used only with very short lists. Also called sequential search. merge sort - Correct Answers: A sort algorithm that splits the items to be sorted into two groups, recursively sorts each group, and merges them into a final, sorted sequence. Node - Correct Answers: A unit of reference in a data structure. Also called a vertex in graphs and trees. (2) A collection of information which must be kept at a single memory location. Infix Notation - Correct Answers: Notation in which the operator separates its operands. E.g. (a + b) * c. Infix notation requires the use of brackets to specify the order of evaluation, unlike either prefix or postfix notations. Postfix Notation - Correct Answers: Reverse Polish Notation or Suffix Notation Notation in which the operator follows its operands. E.g. a + b * c represented as abc*+. Prefix Notation - Correct Answers: Polish Notation Notation in which the operator comes before its operands. E.g. a + b represented as +ab. Queue - Correct Answers: A data structure with first-in first-out behavior, supporting the operations enqueue (to insert) and dequeue (to remove) Selection Sort - Correct Answers: A sort algorithm that repeatedly looks through remaining items to find the least one and moving it to its final location. The run time is (n2), where n is the number of comparisons. The number of swaps is O(n). Sort - Correct Answers: Arrange items in a predetermined order. There are dozens of algorithms, the choice of which depends on factors such as the number of items relative to working memory, knowledge of the orderliness of the items or the range of the keys, the cost of comparing keys vs. the cost of moving items, etc. Quicksort - Correct Answers: An in-place sort algorithm that uses the divide and conquer paradigm. It picks an element from the array (the pivot), partitions the remaining elements into those greater than and less than this pivot, and recursively sorts the partitions Stack - Correct Answers: A data structure with last-in first-out behavior, supporting the operations push (to insert) and pop (to remove) Singly Linked List - Correct Answers: A data structure in which a list of nodes or elements of a data structure connected by pointers. A singly linked list has one pointer in each node pointing to the next node in the list. Start symbol - Correct Answers: The nonterminal symbol that stands for a complete valid utterance in the language being parsed. The start symbol is usually listed as the first nonterminal symbol in a language specification. Symbol table - Correct Answers: A data structure where symbol names and associated data are stored during parsing to allow for recognition and use of existing information in repeated uses of a symbol. Heap - Correct Answers: A complete tree where every node has a key more extreme (greater or less) than or equal to the key of its parent. Usually understood to be a binary heap. Good for: priority queues Binary Tree - Correct Answers: A specific type of tree data structure in which each node has at most two subtrees, one left and one right. Binary trees are often used for sorting information; each node of the binary search tree contains a key, with values less than that key added to left subtree and values greater than that key added to the right subtree. Binary Search Tree - Correct Answers: A data structure with in which every node refers to a left subtree and a right subtree such that all values in the left subtree are smaller than the value in the node and all elements in the right subtree are greater than (or equal to) the value in the node. The top node is called the root. The nodes with no children (left and right subtrees empty) are called leaves. Hash Table - Correct Answers: A dictionary in which keys are mapped to array positions by a hash function. Having more than one key map to the same position is called a collision. There are many ways to resolve collisions, but they may be divided into open addressing, in which all elements are kept within the table, and chaining, in which additional data structures are used. In-order Traversal - Correct Answers: Process all nodes of a tree by recursively processing the left subtree, then processing the root, and finally the right subtree. Level-order Traversal - Correct Answers: Process all nodes of a tree by depth: first the root, then the children of the root, etc. Postorder Traversal - Correct Answers: Process all nodes of a tree by recursively processing the left subtree, then processing the right subtree, and finally the root. Recursion - Correct Answers: An algorithmic technique where a function, in order to accomplish a task, calls itself with some part of the task. Tree Traversal - Correct Answers: A technique for processing the nodes Network - Correct Answers: A set of computers that can intercommunicate. *Think of network as a house with a bunch of doors to different applications.