An Introduction to Order Notation Top Fillable Arrays Contents

Arrays

Synopsis

An array is a fundamental data structure that supports the getting and setting of values. The size of an array dictates how many values it can hold. An array of size n can hold n values. Arrays are distinguished by the fact that getting or setting any element in the array can be done in constant time, regardless of the size of the array.

Arrays may be homogeneous or heterogeneous, depending on the language. In a homogeneous array, all the stored values must have the same type (e.g. all the elements are integers or all are strings). In a heterogeneous array, the values do not need to be of the same type (e.g. the array can hold both integers and strings).

Structure

Arrays are typically built in to the language.

Vocabulary

The terms used in describing an array are:

element
A value stored in an array. Each element is associated with a unique index. Elements are said to be stored at an index.
first element
The element with the lowest index. Also known as the leftmost element.
last element
The element with the highest index. Also known as the rightmost element.
index
An index is an integer value used to indicate a particular element in an array. An array of size n has n indices and holds n elements. In modern programming languages, a technique known as zero-based counting is used to number the elements. Instead of numbering the elements from leftmost to rightmost as 1, 2, 3, 4 ..., the elements are numbered 0, 1, 2, 3, ... . Thus, the first element in the array has index 0, the second, index 1, the third, index 2, and so on.
length
The number of elements in the array. Also known as the capacity.

Supports

Arrays can be used to implement:

Dependencies

Arrays are usually fundamental data structures provided by the language processor.

Operations

get

Languages that support arrays often provide special syntax for getting an element of an array. For C-based languages, square brackets are used to indicate which element is to be gotten; the index of the desired element is placed between the brackets. The array the element is to be retrieved from is given immediately before the opening square bracket. Here are some examples, with items being the name of the array:

    println(items[0]);                //print the first item
    last = items[length(items) - 1]   //get the last item, assign to last

Functional languages may use function calls to get elements from an array:

    println(array-get(items,0))
    set(last,array-get(items,length(items) - 1));

Getting an element takes Θ(1) time.

set

Setting an element in an array overwrites the previous value. Getting an element at an index always gets the value most recently set at that index. In C-based languages, setting looks like getting, except the array name, brackets, and index appear to the left of an assignment operator. Here are some examples, with items being the name of the array:

    items[0] = items[1];            //set the first element to the second
    items[length(items) - 1] = 0;   //set the last element to zero

Functional languages may use function calls to set elements from an array:

    array-set(items,0,array-get(items,1))
    array-set(items,length(items) - 1,0)

Setting an element takes Θ(1) time.

Traversals

Arrays are usually traversed from left to right:

    for (i = 0; i < length(items); i += 1) //zero-based counting!
        println(items[i])

However, it is not uncommon to traverse them from right to left:

    for (i = length(items) - 1; i >= 0; i -= 1) //zero-based counting!
        println(items[i])

Concept Inventory

Array Concept Inventory (C Language)
     
  1. Consider a small array a and large array b. Accessing the first element of a takes more/less/the same amount of time as accessing the first element of b.
    1. the same amount of time
    2. more time
    3. less time
     
  2. Consider a small array a and large array b. Accessing the last element of a takes more/less/the same amount of time as accessing the first element of b.
    1. the same amount of time
    2. more time
    3. less time
     
  3. C arrays are:
    1. homogeneous
    2. heterogeneous
    3. neither homogeneous nor heterogeneous
    4. both homogeneous and heterogeneous
     
  4. C arrays can be:
    1. dynamically allocated only
    2. statically allocated only
    3. dynamically and statically allocated
    4. neither dynamically nor statically allocated
     
  5. Why is the following array declaration not proper?
        int z1[];
    
    1. it is proper
    2. the square brackets are in the wrong place
    3. the size of the array is missing
    4. z1 is not a legal variable name
     
  6. Why is the following array declaration not proper?
        int _[] = { 1 };
    
    1. it is proper
    2. arrays have to have more than one slot
    3. the size of the array is missing
    4. _ is not a legal variable name
     
  7. Why is the following array declaration not proper?
        int[1] x = { 1 };
    
    1. it is proper
    2. arrays have to have more than one slot
    3. the size of the array is missing
    4. the brackets are in the wrong place
     
  8. Why is the following array declaration improper?
        int y[2] = { 1, 2, 3 };
    
    1. it is proper, the array is expanded to three elements
    2. it is proper, the last initializer is ignored
    3. there are too many initializers
    4. there are too few initializers
     
  9. Why is the following array declaration improper?
        int w = { 1, 2, 3 };
    
    1. it is proper
    2. there are too many initializers
    3. there are too few initializers
    4. the square brackets are missing
     
  10. Why is the following array declaration improper?
        double y[3] = { 1, 2, 3 };
    
    1. it is proper
    2. you cannot have integer initializers
    3. you cannot give a size if you have initializers
    4. there should be a comma after the 3
     
  11. Why is the following array declaration improper?
        double y[1];
    
    1. it is proper
    2. initializers are missing
    3. arrays need more than one slot
    4. there should be an empty initializer list
     
  12. Why is the following array declaration improper?
        double y[2] = {};
    
    1. it is proper
    2. there should be initializer values
    3. the initializer list should be {,}
    4. the initializer list should be {}
     
  13. Why is the following array declaration improper?
        double y[3] = { 1.1 2.2 3.3 };
    
    1. it is proper, commas are not necessary
    2. commas after each initializer are missing
    3. commas between initializers are missing
     
  14. Why is the following array declaration improper?
        double y[3] = { "1", "2", "3" };
    
    1. it is proper
    2. you cannot have string initializers
    3. you cannot give a size if you have initializers
    4. there should be a comma after the 3
     
  15. Why is the following array declaration improper?
        void y[2];
    
    1. it is proper
    2. void is not a valid type for arrays
    3. the initializer is missing
     
  16. Why is the following array declaration improper?
        void *y[2];
    
    1. it is proper
    2. void * is not a valid type for arrays
    3. the initializer is missing
     
  17. T or F: Given the declaration int x[3]; and int y[3];, then y[0] = x[0]; is a logically correct assignment.  
     
     
  18. T or F: Given the declaration int x[3]; and int y[3];, then y[0] = x[1]; is a logically correct assignment.  
     
     
  19. T or F: Given the declaration int x[3]; and int y[3];, then y[0] = x[3]; is a logically correct assignment.  
     
     
  20. T or F: Given the declaration int x[3]; and int y[3];, then y[3] = x[2]; is a logically correct assignment.  
     
     
  21. An array has size n. What is the index of the last element?
    1. n
    2. n - 1
    3. n + 1
    4. n - 2
     
  22. You wish to set change the first element in an array a to the value of the last element. Which of the following accomplishes that task?
    1. a[0] = a[n-1];
    2. a[1] = a[n-1];
    3. a[1] = a[n];
    4. a[0] = a[n];
     
  23. You know that the second element of array a holds a valid index for a. You wish to change the element at that index to zero. Which of the following reliably accomplishes that task?
    1. a[a[1]] = 0;
    2. a = a[a[2]];
    3. a[a[2]] = 0;
    4. a[a[1]] = a[1];
     
  24. Consider the declaration int y[3];. As an rvalue, the expression y[2]:
    1. generates an out-of-bounds error message
    2. references the last element in the array
    3. may cause the program to crash
    4. will always cause the program to crash
     
  25. Consider the declaration int y[3];. As an rvalue, the expression y[3]:
    1. generates an out-of-bounds error message
    2. references the last element in the array
    3. may cause the program to crash
    4. will always cause the program to crash
     
  26. Consider the declaration int y[3];. As an rvalue, the expression y[4]:
    1. generates an out-of-bounds error message
    2. references the last element in the array
    3. may cause the program to crash
    4. will always cause the program to crash
     
  27. Consider the declaration int y[3];. The proper declaraction for a pointer that can point to array y is:
    1. int *z;
    2. int z;
    3. int z(*[3]);
    4. int *z[3];
     
  28. Consider the declaration char *y[3];. The proper declaraction for a pointer that can point to array y is:
    1. char *z;
    2. char **z;
    3. char *z(*[3]);
    4. char *z[3];
     
  29. Suppose z points to array a. To access the first element of a using z, one would use the expression:
    1. z[0]
    2. z[1]
    3. *z[0]
    4. *z[1]
    5. z+0
    6. z+1
     
  30. Consider the declaration int *y[3];. To make the assignment p = y; legal, the declaration of p would have to be:
    1. int ***p;
    2. int **p;
    3. int *p;
    4. int p;
     
  31. Consider the declaration int **y[3];. To make the assignment p = y; legal, the declaration of p would have to be:
    1. int ***p;
    2. int **p;
    3. int *p;
    4. int p;
     
  32. Consider the declaration int y[3];. To make the assignment p = y; legal, the declaration of p would have to be:
    1. int ***p;
    2. int **p;
    3. int *p;
    4. int p;
     
  33. Consider the declaration char *y[3];. To make the assignment p[0] = y; legal, the declaration of p would have to be:
    1. char ***p;
    2. char **p;
    3. char *p;
    4. char p;
     
  34. Consider the declaration char y[3];. To make the assignment p[0] = y; legal, the declaration of p would have to be:
    1. char ***p;
    2. char **p;
    3. char *p;
    4. char p;
     
  35. Consider the declaration char **y[3];. To make the assignment p[0] = y[0]; legal, the declaration of p would have to be:
    1. char ***p;
    2. char **p;
    3. char *p;
    4. char p;
     
  36. Consider the declaration char *y[3];. To make the assignment p[0] = y; legal, the declaration of p would have to be:
    1. char ***p;
    2. char **p;
    3. char *p;
    4. char p;
     
  37. T or F: Given the declaration int x[3]; and int y[3];, then x = y; will cause a compiler error.  
     
     
  38. T or F: Given the declaration int x[3]; and int y[3];, then y = x; will cause a compiler error.  
     
     
  39. T or F: Given the declaration int x[3]; and int y[3];, then y = x[0]; will cause a compiler error.  
     
     
  40. T or F: Given the declaration int x[3]; and int y[3];, then y[0] = x; will cause a compiler error.  
     
     
  41. Consider the declaration int z[3];. The name z is:
    1. a pointer
    2. a pseudopointer
    3. neither a pointer nor a pseudopointer
     
  42. T or F: You can assign a pointer to a pseudopointer.  
     
     
  43. T or F: You can assign a pseudopointer to a pseudopointer.  
     
     
  44. T or F: You can assign a pointer to a pointer.  
     
     
  45. T or F: You can assign a pseudopointer to a pointer.  
     
     
  46. Using the sizeof operator on a pseudopointer to an array gives you:
    1. the number of slots in the array
    2. the number of bytes in the array
    3. the size of the pseudopointer
    4. you are not allowed to use sizeof on a pseudopointer
     
  47. Using the sizeof operator on a pointer to an array gives you:
    1. the number of slots in the array
    2. the number of bytes in the array
    3. the size of the pointer
    4. you are not allowed to use sizeof on a pointer
     
  48. Consider:
        int a[3];
        int *p = a;
    

    The value stored at the memory location associated with p is:

    1. the address of the first slot of the array
    2. the name a
    3. the value of the first element of the array
    4. undefined, since the operation is illegal
     
  49. Consider:
        int a[3];
        int *p = a;
    

    The value stored at the memory address found in p is:

    1. the address of the first slot of the array
    2. the name a
    3. the value of the first element of the array
    4. undefined, since the operation is illegal
     
  50. The array access a[3] can be rewritten as:
    1. *(a + 2)
    2. *(a + 3)
    3. *(a) + 2
    4. *(a) + 3
     
  51. The pointer access *(a+4) can be rewritten as:
    1. a[3]
    2. a[4]
    3. *(a[3])
    4. *(a[4])
     
  52. The array access a[0] cannot be rewritten as:
    1. *(a + 2) - 2
    2. *(a + 2 - 2)
    3. *(a + 0)
    4. *a
     
  53. Consider:
        int a[] = { 10, 100, 100 };
        int *p = a;
    

    The expression p+1:

    1. points to the first slot of a
    2. points to the second slot of a
    3. evaluates to 11
    4. evaluates to 101
     
  54. Consider:
        int a[] = { 10, 100, 100 };
        int *p = a;
    

    The expression p+2:

    1. points to the first memory location beyond a
    2. points to the third slot of a
    3. evaluates to 101
    4. evaluates to 1001
     
  55. Consider:
        int a[] = { 10, 100, 100 };
        int *p = a;
    

    The expression p+3:

    1. points to the first memory location beyond a
    2. points to the third slot of a
    3. evaluates to 1001
    4. would generate an error by the compiler
     
  56. The standard library function that can be used to dynamically allocate an array is called:
    1. malloc
    2. allocate
    3. dallocate
    4. dymalloc
     
  57. The string "dog" is stored as:
    1. an array of three characters
    2. an array of four characters
    3. a single location in memory
    4. three non-contiguous memory locations
     
  58. A pointer to the string "rat" has the type:
    1. char
    2. char *
    3. char [3]
    4. string
    5. string *
     
  59. Consider a pointer p to the string "bat". What is the rvalue of p[1]?
    1. the second memory location in the string
    2. the letter 'b'
    3. the letter 'a'
    4. the first memory location in the string
     
  60. Consider a pointer p to the string "bat". What is the lvalue of p[1]?
    1. the second memory location in the string
    2. the letter 'b'
    3. the letter 'a'
    4. the first memory location in the string
     
  61. Consider a pointer p to the string "bat". What is the rvalue of p[3]?
    1. unknown
    2. the letter 't'
    3. the null character
    4. the last memory location in the string
     
  62. Consider a pointer p to the string "bat". What is the lvalue of p[4]?
    1. the first memory location beyond the string
    2. the second memory location beyond the string
    3. unknown
    4. the null character

lusth@cs.ua.edu


An Introduction to Order Notation Top Fillable Arrays Contents