Data Structures 6

Question 1

Binary Search tree

Answer 1

all left descendants < =n < all right descendents 8 / \ 4 10/ \ \2 6 20

Question 2

Balanced Trees

Answer 2

AVL trees and red-black trees

Question 3

Complete Binary Trees

Answer 3

“every level of the tree is fully filled, except for the last level. it has to be filled left to right “

Question 4

Full Binary Tree

Answer 4

a binary tree where every node has zero or 2 children. It is the all or nothing binary tree

Question 5

Perfect Binary Tree

Answer 5

It is both full and complete. 2k - 1 nodes where k is the height

Question 6

In-Order Traversal

Answer 6

LDR -> Left, Visit Node, Right.

Question 7

Pre-Order Traversal

Answer 7

DLR -> Visit Node, Left, Right

Question 8

Post-Order Traversal

Answer 8

LRD -> Left, Right, Visit NOde

Question 9

Array advantages

Answer 9

Simple and easy to use and access to elements is O(1)

Question 10

Array disadvantages

Answer 10

fixed size, one block allocation, and complex position-based insertion

Question 11

O(1) complexity for access

Answer 11

Array and dynamic arrays time complexity.

Question 12

O(n) time complexity for accessing elements

Answer 12

lists

Question 13

Main operations of lists

Answer 13

traversing, insert(), pop()

Question 14

Main operations of stack

Answer 14

push(), int pop()

Question 15

Auxiliary operations of stack

Answer 15

int top(), int size(), int empty(), isFull()

Question 16

I want to balance symbols, tags, and fix symbols

Answer 16

stack applications

Question 17

Space complexity of stack

Answer 17

O(n)

Question 18

Time complexity of push, pop, and operation of stack

Answer 18

O(1)

Question 19

Why is the push implementation of a dynamic array and list Average O(1)

Answer 19

Every now and then we have to increase the size of a full array which involves an O(n) operation

Question 20

idempotent

Answer 20

doing the same operation multiple times and getting the same outcome. In terms of Restful services, I should do the same call on data, multiple times, and it will not change.

Question 21

GET request

Answer 21

It is idempotent, therefore, It should never be used to alter data. We would like to be able to do this over and over

Question 22

PUT request

Answer 22

It is idempotent, therefore, it should only be used to update data. If I update with the same information, the result will not change.

Question 23

POST request

Answer 23

It is not idempotent, therefore, it should be used to alter data in some form where if you did the same post request, the resulting set will be different.

Question 24

CRUD

Answer 24

Create, Read, Update, Delete

Question 25

One-Many or Many One ->

Answer 25

In objects, if one object can have many of another object.This can be done with a simple WHERE clause or a simple join if another column data is needed of some sort

Question 26

Many-Many

Answer 26

If Many objects can have many of another. An employee can be a part of many departments, while many departments can have many employees. This is normally done by an intermediate table.