WGU C949 Data Structures and Algorithms I

WGU C949 Data Structures and Algorithms I Leave the first rating Students also studied Terms in this set (80) Save WGU C949 Data Structures and Alg...102 terms bodiewoodPreview C949 - Data Structure and Algorith...37 terms dle50Preview Hardware and Operating Systems E...279 terms rprach2Preview

C949 W

72 terms Ver Practice questions for this set Learn1 / 6Study using Learn A queue is an ADT in which items are inserted at the end of the queue and removed from the front of the queue.FIFO (Linked List, Array) An algorithm with a polynomial runtime is considered efficient?

True: An efficient algorithm is generally one whose runtime increases no more

than polynomially with respective to the input size. In contrast, an algorithm with an exponential runtime is not efficient.An efficient algorithm exists for all computational problems.

False: Many computational problems exist for which an efficient algorithm is

unknown. Such problems are often encountered in real applications.Choose an answer 1Array2Linked List 3Queue4Bag Don't know?

An efficient algorithm to solve an NP-complete may exist.True: Whether or not an efficient algorithm exists for NP-complete problems is an open research question. However, the current consensus is that such an algorithm is unlikely.RecordA record is the data structure that stores subitems, often called fields, with a name associated with each subitem.ArrayAn array is a data structure that stores an ordered list of items, where each item is directly accessible by a positional index.Linked listA linked list is a data structure that stores an ordered list of items in nodes, where each node stores data and has a pointer to the next node.Binary treeA binary tree is a data structure in which each node stores data and has up to two children, known as a left child and a right child.Hash tableA hash table is a data structure that stores unordered items by mapping (or hashing) each item to a location in an array HeapA max-heap is a tree that maintains the simple property that a node's key is greater than or equal to the node's childrens' keys. A min-heap is a tree that maintains the simple property that a node's key is less than or equal to the node's childrens' keys.GraphA graph is a data structure for representing connections among items, and consists of vertices connected by edges. A vertex represents an item in a graph.An edge represents a connection between two vertices in a graph A linked list stores items in an unspecified order. False: A linked list stores an ordered list of items. The links in each node define the order in which items are stored.A node in binary tree can have zero, one, or two children. True: A binary tree node can have no children, a single left or right child, or both a left and right child.A list node's data can store a record with multiple subitems.True: The data stored in a list node can be a record with multiple subitems. Ex: A linked list storing employee data might use a record containing the employee's name, title, and salary. Also, the list node itself can be implemented as a record, having subitems for the data and the pointer to the next node.Items stored in an array can be accessed using a positional index.Array elements are stored in sequential locations, so can be easily accessed using an index.Inserting an item at the end of a 999-item array requires how many items to be shifted?

Zero: Appending an item just places the new item at the end of the array. No

shifting of existing items is necessary.Inserting an item at the end of a 999-item linked list requires how many items to be shifted?

Zero: The new item is simply added to the end.

Inserting an item at the beginning of a 999-item array requires how many items to be shifted?

999: Inserting at the beginning requires making room for the new item. So every

current item must be shifted once.

Inserting an item at the beginning of a 999-item linked list requires how many items to be shifted?Zero: No shifting of other items is required, which is an advantage of using linked lists.Algorithm for appending to array Algorithm for appending to linked-list Abstract data types (ADTs)A data type described by predefined user operations, such as "insert data at rear," without indicating how each operation is implemented. An ADT can be implemented using different underlying data structures. However, a programmer need not have knowledge of the underlying implementation to use an ADT.A list ADT's underlying data structure has no impact on the program's execution.False: Different underlying data structures will require different algorithms to

perform same list ADT operation, which will have different runtimes. Ex: For

prepending an item to a list, a linked list-based implementation is more efficient than an array-based implementation.ListA list is an ADT for holding ordered data. (Array, Linked List) StackA stack is an ADT in which items are only inserted on or removed from the top of a stack. LIFO (Linked List) QueueA queue is an ADT in which items are inserted at the end of the queue and removed from the front of the queue.FIFO (Linked List, Array) DequeA deque (pronounced "deck" and short for double-ended queue) is an ADT in which items can be inserted and removed at both the front and back. (Linked List) BagA bag is an ADT for storing items in which the order does not matter and duplicate items are allowed. (Array, Linked List) SetA set is an ADT for a collection of distinct items. (Binary Search Tree, Hash Table) Priority QueueA priority queue is a queue where each item has a priority, and items with higher priority are closer to the front of the queue than items with lower priority. (Heap) Dictionary (Map)A dictionary is an ADT that associates (or maps) keys with values. (Hash Table, Binary Search Tree) Common operations for "List" ADP

Some common operations for a queue ADT.Abstraction and optimizationAbstraction means to have a user interact with an item at a high-level, with lower- level internal details hidden from the user. ADTs support abstraction by hiding the underlying implementation details and providing a well-defined set of operations for using the ADT.Using abstract data types enables programmers or algorithm designers to focus on higher-level operations and algorithms, thus improving programmer efficiency.However, knowledge of the underlying implementation is needed to analyze or improve the runtime efficiency.Python, C++, and Java all provide built-in support for a deque ADT.True The underlying data structure for a list data structure is the same for all programming languages.False ADTs are only supported in standard libraries. False

Python: DefineValueA value such as "20", "abcdef", or 55.

Python: Define TypeThe type of the object, such as integer or string. (Muttable)

Python: Define IdentityA unique identifier that describes the object.

Which built-in function finds the type of an object? type() Write an expression that gives the identity of the variable num id(num) Is a "Name" considered an Identifier?True Arithmetic Operators Constant Time OperationsIn practice, designing an efficient algorithm aims to lower the amount of time that an algorithm runs. However, a single algorithm can always execute more quickly on a faster processor. Therefore, the theoretical analysis of an algorithm describes runtime in terms of number of constant time operations, not nanoseconds. A constant time operation is an operation that, for a given processor, always operates in the same amount of time, regardless of input values.

ex: X = 2 , Y = 50, Z = 100