linear structures

Question 1

what us an adt

Answer 1

is an abstract data type (ADT) is a mathematical model of a data structure that specifies

• the type of data stored
• the operations supported on them and the types of parameters of the operations
• realized by a concrete data structure

Question 2

what are some linear structures

Answer 2

• stack, queues, lists, and their variants such as double ended queues, priority queues
• maps and sets, there variants, and hash tables ( a data structure to implement them)

Question 3

what are some non linear structures

Answer 3

trees, search trees binary trees, binary search trees, balanced trees and heaps, graphs, important graph problems and algorithms

Question 4

how does a stack work ( like adding and taking off elements)

Answer 4

last in first out scheme ( like plates stacked)

Question 5

what are the main stack operations

Answer 5

• push(object)
• object pop() // removes and returns the last inserted element
• object top() returns the last inserted element( do not remove it tho)
• int size() // returns the number of elements
• boolean isEmpty- is there elements

Question 6

what is the spaced used on a array based stack

Answer 6

O(N)

Question 7

what is the run time of a array based stack

Answer 7

each operation is O(1)

Question 8

what are the limitations of a array based stack

Answer 8

• the maximum size of the stack must be defined and cannot be changed
• trying to push a new element into a full stack caused an error

Question 9

stack implemented with a singly linked list running time is

Answer 9

constant time

Question 10

how does a queue work ( like adding and taking off elements)

Answer 10

first in first out ( like lining up for food)

Question 11

what are the main queue opperations

Answer 11

• enqueue(object)
• object dequeue() // removes and returns the last inserted element
• object first() returns the last inserted element( do not remove it tho)
• int size() // returns the number of elements
• boolean isEmpty- is there elements

Question 12

what is the run time of a array based queue

Answer 12

each operation runs at O(1)

Question 13

what is the spaced used on a array based queue

Answer 13

O(N) //N is the size of the array

Question 14

queue implemented with a singly linked list running time is

Answer 14

delete and add in constant time

Question 15

what are the main deque opperations

Answer 15

• addFirst(object) // adds to front of list
• addLast(object) // adds to end of list
• object removeFirst() // removes and returns the first inserted element
• object removeLast() // removes and returns the last element
• object first() returns the first element( do not remove it tho)
• object last() returns the last element( do not remove it tho)
• int size() // returns the number of elements
• boolean isEmpty- is there elements

Question 16

what is the run time of a array based deque

Answer 16

constant time O(1) even with doubly linked list

Question 17

what is the spaced used on a array based deque

Answer 17

O(N)

Question 18

what is a list

Answer 18

list is an ADT in a linear squenece of elements and support of operations for adding or removifn elements at arbatrary positions

Question 19

what are the main list opperations

Answer 19

• get (i) // returns the elements of the list having index i.
• set(i,e) - replaces the element at index i with e and returns the old element that was replaced
  add(i,e) - inserts a new element e into the list so that it has index i
  remove (i) removes and returns the element at index i
• int size() // returns the number of elements
• boolean isEmpty- is there elements

Question 20

what is the run time of a array based list

Answer 20

O(n)

Question 21

what is the run time of a array based list

Answer 21

O(1)