Pert3 Flashcards Preview

Data Structures > Pert3 > Flashcards

Flashcards in Pert3 Deck (22):
1

What is binary tree?

a data structure which is defined as a collection of elements called the nodes

2

Prefix notation dikenal juga?

Reverse polish notation

3

postfix notation dikenal juga?

polish notation

4

Depth first search?

sebuah algoritma untuk traversing atau searching dalam sebuah tree atau graph. Dimulai dari root dari sebuah tree dan melakukan explore sedalam mungkin pada setiap cabang sebelum ke cabang yang sebelahnya.

5

Depth first search (DFS) menggunakan data structure?

Stack

6

Breadth first search (BFS) menggunakan data structure?

Queue

7

Several applications using queue?

1. Deques
2. Priority Queue
3. Breadth First Search

8

Deque?

dapat di delete / insert dari head atau tail

9

2 jenis Deque

1. Input restricted deque
insertion can be done only at one of the dequeue, deletions both the end

2. Output restricted deque
deletions can be done only at one of the dequeue, insertions both the end

10

Priority Queue?

sebuah ADT dimana setiap element diberikan sebuah prioritas

11

Breadth First Search (BFS)

sebuah algoritma untuk traversing atau searching dalam sebuah tree. dimulai dari root dan melakukan explore ke semua node yang bersebelahan dari level per level sampai menemukan hasil yang diinginkan

12

Breadth First Search (BFS)

sebuah algoritma untuk traversing atau searching dalam sebuah tree. dimulai dari root dan melakukan explore ke semua node yang bersebelahan dari level per level sampai menemukan hasil yang diinginkan

13

3 arithmetic notations?

1. Prefix, operator duluan sebelum operands
2. Infix, operator diantara operands
3. Postfix, operator setelah operands

14

if TOP = MAX - 1

stack is full

15

why do we need prefix/postfix notation?

1. prefix and postfix notation don't need brackets to prioritze operator precedence
2. prefix and postfix is much easier for computer to evaluate

16

complexity dari infix expression?

O(N^2), N adalah panjang string

17

Complexity dari Postfix expression?

O(N)

18

algoritma postfix notation?

1. jika operand push ke stack
2. jika operator, pop twice (store ke var A dan B) dan push(B operator A)

19

Prefix notation pake stack scan dari mana ke mana?

kanan ke kiri

20

algoritma convertion prefix ke postfix

1. cari operator dengan precedence paling tinggi
2. put operator behind the operand
3. repeat until finish

21

conversion infix to postfix notation complexity?

O(N)

22

algoritma infix ke prefix

1. cari operator dengan highest precedence
2. put that operator before operand
3. repeat until finish