• ¿Documento equivocado? Cámbialo gratis
  • Escrito por estudiantes que aprobaron
  • Inmediatamente disponible después del pago
  • Leer en línea o como PDF
Vender
¿Dónde estudias?
Tu idioma
Document preview thumbnail
Vista previa 2 fuera de 15 páginas
Examen

Computer Science: Data Structures and Algorithms Questions and Answers

Document preview thumbnail
Vista previa 2 fuera de 15 páginas

Computer Science: Data Structures and Algorithms Doubly Linked List: advantage, disadvantage - Answer- Advantage: quick insert to beginning, quick removal from end Disadvantage: slow search, not great for indexing Data Structures: Discuss characteristics of a Dictionary - Answer- Use when: order is unimportant, frequently adding and removing items, frequently looking up items Why is looking up, adding, and removing elements from a dictionary or hash map an O(1) operation? - Answer- Hash maps are built upon arrays: keys entered into a dictionary/hash map are hashed first to find where the key/value pair should be stored. This position is unique and can be used for fast lookups, as well as insertions and deletions. When searching in a regular list, Python iterates over the list to see if a given value is in the list -- this is an O(n) operation. When looking to see if a value is in a hash table, Python hashes the value that's sought and can go immediately to that position in the array to see if there is a value there. That process of hashing and indexing is an O(1) operation. Similarly, as every item in a hash map has a unique position, adding or inserting items does not require that eery other item shift index position; an items' position is not dependent on other items in the array. Explain why removing elements from or adding elements to an arbitrary location in a Python list are O(n) operations. - Answer- Python lists are contiguous in memory. When an item is removed or added to the middle of a list, all the subsequent items in the list must be shifted either up or down by one position What's the runtime for Bubble Sort? - Answer- O(n^2) (very bad); best case O(n) What's the runtime for Quick Sort? - Answer- O(n log n) (okay); worst case O(n^2) What's the runtime for Merge Sort? - Answer- O(n log n) (okay) particularly good when number of items being sorted increases What's the runtime for Insertion Sort? - Answer- O(n^2) (very bad); best case O(n). Its good when the number of items being sorted is small, but as N grows, runtime slows dramatically. What's the runtime for TimSort? - Answer- O(n) (fair); worst case O(n log n) (okay)

Vista previa del contenido

Computer Science: Data Structures
and Algorithms
Doubly Linked List: advantage, disadvantage - Answer- Advantage: quick insert to
beginning, quick removal from end

Disadvantage: slow search, not great for indexing

Data Structures: Discuss characteristics of a Dictionary - Answer- Use when: order is
unimportant, frequently adding and removing items, frequently looking up items

Why is looking up, adding, and removing elements from a dictionary or hash map an
O(1) operation? - Answer- Hash maps are built upon arrays: keys entered into a
dictionary/hash map are hashed first to find where the key/value pair should be
stored. This position is unique and can be used for fast lookups, as well as insertions
and deletions.

When searching in a regular list, Python iterates over the list to see if a given value
is in the list -- this is an O(n) operation. When looking to see if a value is in a hash
table, Python hashes the value that's sought and can go immediately to that position
in the array to see if there is a value there. That process of hashing and indexing is
an O(1) operation.

Similarly, as every item in a hash map has a unique position, adding or inserting
items does not require that eery other item shift index position; an items' position is
not dependent on other items in the array.

Explain why removing elements from or adding elements to an arbitrary location in a
Python list are O(n) operations. - Answer- Python lists are contiguous in memory.
When an item is removed or added to the middle of a list, all the subsequent items in
the list must be shifted either up or down by one position

What's the runtime for Bubble Sort? - Answer- O(n^2) (very bad);
best case O(n)

What's the runtime for Quick Sort? - Answer- O(n log n) (okay);
worst case O(n^2)

What's the runtime for Merge Sort? - Answer- O(n log n) (okay)
particularly good when number of items being sorted increases

What's the runtime for Insertion Sort? - Answer- O(n^2) (very bad);
best case O(n).
Its good when the number of items being sorted is small, but as N grows, runtime
slows dramatically.

What's the runtime for TimSort? - Answer- O(n) (fair);
worst case O(n log n) (okay)

, What's the runtime for Heap Sort? - Answer- O(n log n) (okay)

What's the runtime for Selection Sort? - Answer- O (n^2) (very bad)

What's the runtime for Tree Sort? - Answer- O(n log n) (okay);

What's the runtime for Shell Sort? - Answer- O(n log n) (okay);

What's the runtime for Bucket Sort? - Answer- Ω(n+k) (very good; close to O(log n)
or O(1)

What's the runtime for Radix Sort? - Answer- Ω(n+k) (very good; close to O(log n) or
O(1)

What's the runtime for Counting Sort? - Answer- Ω(n+k) (very good; close to O(log n)
or O(1)

What's the runtime for Cube Sort? - Answer- O(n)

6. What is the difference between a tree and a graph? - Answer- A tree is a restricted
kind of graph where there are no loops or cycles.

(Might require pen/paper)
Using the Python implementation of Quick Sort from the instructions:

Given the list [8, 4, 1, 6, 5, 2, 7, 3]:
When this function is initially called, what is the value of list? - Answer- [8, 4, 1, 6, 5,
2, 7, 3]

(Might require pen/paper)
Using the Python implementation of Quick Sort from the instructions:

Given the list [8, 4, 1, 6, 5, 2, 7, 3]:
When this function is initially called, what is the value of pivot? - Answer- 5

(Might require pen/paper)
Using the Python implementation of Quick Sort from the instructions:

Given the list [8, 4, 1, 6, 5, 2, 7, 3]:
When this function is initially called, what is the value of low? - Answer- [ 4, 1, 2, 3 ]

(Might require pen/paper)
Using the Python implementation of Quick Sort from the instructions:

Given the list [8, 4, 1, 6, 5, 2, 7, 3]:
When this function is initially called, what is the value of high? - Answer- [8, 6, 7]

Top 3 characteristics of Lists - Answer- Iterable,
Ordered,

Información del documento

Subido en
18 de agosto de 2024
Número de páginas
15
Escrito en
2024/2025
Tipo
Examen
Contiene
Preguntas y respuestas
$12.99

¿Documento equivocado? Cámbialo gratis Dentro de los 14 días posteriores a la compra y antes de descargarlo, puedes elegir otro documento. Puedes gastar el importe de nuevo.
Escrito por estudiantes que aprobaron
Inmediatamente disponible después del pago
Leer en línea o como PDF

Seller avatar
Los indicadores de reputación están sujetos a la cantidad de artículos vendidos por una tarifa y las reseñas que ha recibido por esos documentos. Hay tres niveles: Bronce, Plata y Oro. Cuanto mayor reputación, más podrás confiar en la calidad del trabajo del vendedor.
Freshy
3.6
(11)
Vendido
65
Seguidores
4
Artículos
6964
Última venta
1 semana hace



Por qué los estudiantes eligen Stuvia

Creado por compañeros estudiantes, verificado por reseñas

Calidad en la que puedes confiar: escrito por estudiantes que aprobaron y evaluado por otros que han usado estos resúmenes.

¿No estás satisfecho? Elige otro documento

¡No te preocupes! Puedes elegir directamente otro documento que se ajuste mejor a lo que buscas.

Paga como quieras, empieza a estudiar al instante

Sin suscripción, sin compromisos. Paga como estés acostumbrado con tarjeta de crédito y descarga tu documento PDF inmediatamente.

Student with book image

“Comprado, descargado y aprobado. Así de fácil puede ser.”

Alisha Student

Preguntas frecuentes