Array

Question 1

What is an array?

Answer 1

In computer science, an array data structure, or simply an array, is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key.

Question 2

What is the memory address of the first address called?

Answer 2

The memory address of the first element of an array is called first address or foundation address.

Question 3

How does an array effectively exploit addressing logic of computers?

Answer 3

In most modern computers and many external storage devices, the memory is a one-dimensional array of words, whose indices are their addresses.

Question 4

How are arrays useful.?

Answer 4

element indices can be computed at run time which allows a single iterative statement to process arbitrarily many elements of an array.

Question 5

Requirements?

Answer 5

the elements of an array data structure are required to have the same size and should use the same data representation.

Question 6

History?

Answer 6

The first digital computers used machine-language programming to set up and access array structures for data tables, vector and matrix computations, and for many other purposes.

Question 7

Applications?

Answer 7

Arrays are used to implement other data structures, such as lists, heaps, hash tables, deques, queues, stacks, strings, and VLists.

Question 8

How else can Arrays be used?

Answer 8

Arrays can be used to determine partial or complete control flow in programs, as a compact alternative to (otherwise repetitive) multiple IF statements.

Question 9

Accessing elements?

Answer 9

When data objects are stored in an array, individual objects are selected by an index that is usually a non-negative scalar integer.

Question 10

What are the 3 ways in which an element can be indexed?

Answer 10

0 (zero-based indexing): The first element of the array is indexed by subscript of 0.[8]

1 (one-based indexing): The first element of the array is indexed by subscript of 1.[9]

n (n-based indexing): The base index of an array can be freely chosen. Usually programming languages allowing n-based indexing also allow negative index values and other scalar data types like enumerations, or characters may be used as an array index

Question 11

What is the dimension?

Answer 11

The number of indices needed to specify an element is called the dimension, dimensionality, or rank of the array.

Question 12

How to find the element index of a linear vector in a one-dimensional array?

Answer 12

For a vector with linear addressing, the element with index i is located at the address B + c × i, where B is a fixed base address and c a fixed constant, sometimes called the address increment or stride.

Question 13

How about multidimensional arrays?

Answer 13

For a multidimensional array, the element with indices i,j would have address B + c · i + d · j, where the coefficients c and d are the row and column address increments, respectively.

Question 14

What is a dope vector?

Answer 14

The addressing formula is completely defined by the dimension d, the base address B, and the increments c1, c2, …, ck. It is often useful to pack these parameters into a record called the array’s descriptor or stride vector or dope vector.[2][3]

Question 15

What kinds of operations can be handled by the dope vector?

Answer 15

Many useful array slicing operations (such as selecting a sub-array, swapping indices, or reversing the direction of the indices) can be performed very efficiently by manipulating the dope vector.[2]

Question 16

Static arrays?

Answer 16

Static arrays have a size that is fixed when they are created and consequently do not allow elements to be inserted or removed.

Question 17

Dynamic arrays?

Answer 17

by allocating a new array and copying the contents of the old array to it, it is possible to effectively implement a dynamic version of an array

Question 18

Worst case O(1)?

Answer 18

Both store and select take (deterministic worst case) constant time.

Question 19

Locality of Reference?

Answer 19

This is roughly a factor of B/k better than the number of cache misses needed to access n elements at random memory locations. As a consequence, sequential iteration over an array is noticeably faster in practice than iteration over many other data structures, a property called locality of reference

Question 20

Memory-wise?

Answer 20

Memory-wise, arrays are compact data structures with no per-element overhead.

Question 21

Packed arrays?

Answer 21

It can also happen that elements stored in an array require less memory than the same elements stored in individual variables, because several array elements can be stored in a single word; such arrays are often called packed arrays.

Question 22

Efficiency?

Answer 22

Indexing = O(1)

Wasted space = 0

Question 23

What are dynamic arrays?

Answer 23

growable arrays are similar to arrays but add the ability to insert and delete elements; adding and deleting at the end is particularly efficient. However, they reserve linear (Θ(n)) additional storage, whereas arrays do not reserve additional storage.

Question 24

Efficiency for Dynamic arrays?

Answer 24

Indexing = O(1)
Insertion/Deletion at beginning  =  O(n)
Insertion/Deletion at end = O(1) amortized
Insertion/Deletion at middle = O(n)
Wasted Space = O(n)

Question 25

What are Associative Arrays?

Answer 25

provide a mechanism for array-like functionality without huge storage overheads when the index values are sparse. For example, an array that contains values only at indexes 1 and 2 billion may benefit from using such a structure.

Question 26

What is 32-bit unsigned integer?

Answer 26

2,147,483,647…the largest integer from 2**32

Question 27

What is the item size for 32bits?

Answer 27

4 bytes, so an array holding n items has a total size of 4 * n bytes.

Question 28

How is the memory address of the first index of an array assigned?

Answer 28

Arbitrarily…

Question 29

How are preceding memory address of indices computed?

Answer 29

Start with the memory address of the first index i.e. 0xBA03 and add the number of bytes it will hold multiplied by the index it will occupy: 0xB3A0 + 4 * 3 = 0xB3A3

Question 30

How do arrays work in higher level languages?

Answer 30

To store heterogeneously sized items in an array in C, pointers to those items, instead of the items themselves, would have to be explicitly stored.

Question 31

Why are arrays among the fastest data structures?

Answer 31

among the fastest data structures since the index lookup process is simply an integer multiplication operation followed by an integer addition operation

Question 32

What is a jagged array?

Answer 32

This can be avoided by using a one-dimensional array which stores references to other one-dimensional arrays of heterogeneous length.

Question 33

What are the types of ways to manipulate data?

Answer 33

Adding
Searching
Sorting
Deleting
Rearranging
Traversing