CS201: Elementary Data Structures Certification Answers

Related Articles

CS406: Information Security Certification Exam Answers

April 24, 2024

CS403: Introduction to Modern Database Systems Certification Exam Answers

April 24, 2024

CS402: Computer Communications and Networks Certification Exam Answers

April 24, 2024

Elementary data structures are fundamental building blocks used in computer science and programming to organize and manage data efficiently. These structures are the basic components that form more complex data structures and algorithms. Some common elementary data structures include:

1. Arrays: Arrays are a collection of elements, each identified by at least one array index or key. They store elements of the same type and allow random access to elements using their indices.
2. Linked Lists: Linked lists are collections of nodes where each node contains data and a reference (link) to the next node in the sequence. They are dynamic in size and provide efficient insertion and deletion operations, but accessing elements requires traversing the list from the beginning.
3. Stacks: Stacks are abstract data types that follow the Last-In-First-Out (LIFO) principle. Elements are added and removed from only one end, called the top. Common operations include push (add element) and pop (remove element).
4. Queues: Queues are abstract data types that follow the First-In-First-Out (FIFO) principle. Elements are added at the rear (enqueue) and removed from the front (dequeue). Common implementations include arrays and linked lists.
5. Trees: Trees are hierarchical data structures composed of nodes, where each node has a value and a list of references to its child nodes. They are commonly used for organizing hierarchical data, such as file systems, and implementing various algorithms, such as binary search trees and AVL trees.
6. Graphs: Graphs are collections of nodes (vertices) and edges that connect pairs of nodes. They can be directed or undirected and may contain cycles. Graphs are used to model relationships between objects and solve various real-world problems, such as network routing and social network analysis.

These elementary data structures are essential for understanding more complex data structures and algorithms used in software development and computer science. Understanding their properties, operations, and performance characteristics is crucial for designing efficient and scalable solutions.

CS201: Elementary Data Structures Exam Quiz Answers

Question 1: What is the index of the last element of an array of size 50? Select one:

• 0
• 49
• 50
• 51

Question 2: What is the correct way of declaring a two-dimensional array of integers with three rows and four columns? Select one:

• int my_array [3][4];
• int my_array [4][3];
• integer my_array [3][4];
• int my_array [3], my_array [4];

Question 3: What is the difference between an abstract data type definition and an instance? Select one:

• Each abstract data type can have many definitions. Each is a definition instance.
• An instance is the time taken to allocate memory for a defined abstract data type.
• An abstract data type has a description or definition that is used to create instances.
• Abstract data type definitions give instructions on each instance of memory allocation.

Question 4: A pointer is which of the following? Select one:

• Another name for a variable that holds the address of a block of memory
• A floating-point number that specifies the address of an array’s first data value
• The address of the first byte of a contiguous block of memory allocated by a program
• The important information embedded in the assembler code generated by the compiler

Question 5: Which of the following C++ code fragments uses a combination of vectors, or one-dimensional arrays, in non-contiguous memory to build two-dimensional arrays? Select one:

• int data [5][6];
• std: array<std: array<int,5>,6> data;
• int * data = (int*) malloc (5 * 6 * size of(int));
• int * data [5]; for (int i = 0; i < 5; i++) data [i] = new int [6];

Question 6: What are the operations associated with a stack? Select one:

• Push, Pop, Empty
• Push, Sort, Retrieve
• Add, Remove, Access
• Insert, Access, Delete

Question 7: How do stacks allow their elements to be accessed? Select one:

• Any entry is directly accessible.
• Only the earliest entry is directly accessible.
• Only the most recent entry is directly accessible.
• Only the entry with the lowest value is accessible.

Question 8: If characters A, B, C, and D are inserted in that order in a queue and then removed one at a time, what will be the correct removal order? Select one:

• ABCD
• ABDC
• DBCA
• DCBA

Question 9: What is specific to the circular array implementation of the queue? Select one:

• Only one pointer is used to keep track of the “front.”
• Only one pointer is used to keep track of the “rear.”
• Two pointers are used, one to track the “front” and the other to track the “rear.”
• Two pointers are used, one for the next and the other for the previous queue elements.

Question 10: What does the term “enqueue” mean? Select one:

• Adding a new element to the rear of a queue.
• Adding a new element to the front of a queue.
• Removing an element from the front of a queue.
• Computing the hash value of the element and inserting it in the queue.

Question 11: What will be printed after the execution of the following code?

int x;

int *a;

a = &x;

*a =5;

cout<< *a;

Select one:

• 5
• The memory address of the variable a
• The memory address of the variable x
• 0 or NULL (depending on the compiler), since the variable a contains a null pointer

Question 12: In the third line of the following code, which operator takes precedence?

int num [10];

int *ptr1 = &num [0];

*ptr1++;

Select one:

• *
• ++
• Both operators have the same precedence.
• The syntax is incorrect, since pointer variables cannot be incremented.

Question 13: Is it possible for a scalar type to have a different numeric range from one compiler to another on the same machine? Why or why not? Select one:

• Yes. Some compilers produce code for lesser bit lengths than the target computer.
• Yes. The compiler makes decisions on variable numeric ranges based on memory availability.
• No. Compilers for a given bit length do not produce executable code for different bit lengths.
• No. The same code syntax is guaranteed to produce the same results regardless of compiler.

Question 14: We can create a dereference operator by adding a(n) ____ in front of the variable name. Select one:

• *
• &
• #
• _

Question 15: What value does variable a hold in the following code?

int x=10;

int *a;

a = &x;

Select one:

• The variable a is equal to x.
• The variable a is equal to 10.
• The variable a points to the memory location of x.
• This operation would corrupt the variable a, and should be avoided.

Question 16: What value does the variable galaxy hold in the following line of code?

char *galaxy = “galaxy”;

Select one:

• The character string g
• The memory address of g
• The character string galaxy
• Nothing; the code will not compile since the syntax is incorrect

Question 17: In the following code, which variable is a scalar, which is a vector, and which is an array?

int C = 6;

int R = 5;

int *data[R];

for (int i = 0; i < R; i++) data[i] = new int[C];

Select one:

• Scalar: C, Vector: R, Array: data[i]
• Scalar: int[C], Vector: R, Array: data
• Scalar: R, Vector: data, Array: int[C]
• Scalar: R, Vector: data[i], Array: data

Question 18: Which of the following statements about constructors in C++ is true? Select one:

• A constructor is required to contain input arguments.
• A constructor automatically initializes all data members of a class.
• A constructor is automatically invoked when a class is instantiated.
• The name of the constructor is never the same as the name of the class.

Question 19: During a memory leak, which of the following statements about memory is true? Select one:

• It is wasted by the compiler.
• It is available but not usable.
• It is being used by another program.
• It is allocated but never deallocated.

Question 20: Which of the following statements about the memory heap is true? Select one:

• It is allocated at design time.
• It is allocated at compile time.
• It is allocated when an object is deleted.
• It is used to dynamically allocate memory.

Question 21: Memory leaks can best be minimized during program execution by doing which of the following? Select one:

• Foregoing the use of dynamically-allocated memory
• Recasting memory pointers for use by other abstract data types
• Ensuring there is a “delete” for every “new”, and a “free” for every “malloc” or “calloc”
• Ensuring there is a “free” for every “new”, and a “delete” for every “malloc” or “calloc”

Question 22: Which of the following statements about C++ classes and structures is true? Select one:

• Struct declarations are the same in C and C++.
• A compiler error results when public or private is not specified.
• Class members are private and structure members are public by default.
• Class members are public and structure members are private by default.

Question 23: Which list application allows deletion at one end and insertion at the other end? Select one:

• Hash Access
• First-In/First-Out
• Last-In/First-Out
• Random Access

Question 24: How many pointers does a node in a doubly linked list have? Select one:

• 1
• 2
• 3
• 4

Question 25: What operation cannot be performed on a linked list? Select one:

• Adding a node
• Deleting a node
• Traversing a node
• Direct random access to nodes

Question 26: Which of the following types of linked list has one or two links between nodes? Select one:

• Singly linked list
• Doubly linked list
• Circular linked list
• Hash-extension linked list

Question 27: The runtime efficiency of merge sort using Big-O notation is which of the following? Select one:

• O (n)
• O (log n)
• O (n 2)
• O (n log n)

Question 28: The runtime efficiency of linear search using Big-O notation is which of the following? Select one:

• O (n)
• O (log n)
• O (n 2)
• O (n log n)

Question 29: In terms of Big-O notation, the efficiency of selection sort can be represented by which of the following? Select one:

• O (n)
• O (log n)
• O (n 2)
• O (n log n)

Question 30: In terms of Big-O notation, the efficiency of merge sort can be represented by which of the following? Select one:

• O (n)
• O (log n)
• O (n 2)
• O (n log n)

Question 31: Which of the following sort algorithms uses the divide-and-conquer principle? Select one:

• Bubble sort
• Insertion sort
• Merge sort
• Selection Sort

Question 32: What is the worst-case runtime efficiency for linear search of an array? Select one:

• O (1)
• O (n)
• O (log n)
• O (n log n)

Question 33: The worst-case number of comparisons required to perform an insertion in an unbalanced binary search tree with n nodes is which of the following? Select one:

• O (1)
• O (n)
• O (log n)
• O (n log n)

Question 34: Is linear or binary search algorithm more efficient when searching an array? Select one:

• Linear search is more efficient.
• Binary search is more efficient.
• Linear and binary search are equally efficient.
• Either can be more efficient, depending on the type of data involved.

Question 35: Which of the following sorts is most suitable for large amounts of data? Select one:

• Bubble sort
• Insertion sort
• Merge sort
• Selection sort

Question 36: How many comparisons does bubble sort have to make while sorting an array? Select one:

• n2
• n
• n^2
• log(n)+1

Question 37: Which of the following statements about a complete binary search tree with a depth d and n number of nodes is true? Select one:

• n=2(d+1)–1
• Space efficiency is < n
• The deepest node has depth < log n
• Runtime efficiency is log n for all operations

Question 38: Where is an item stored in a hash table? Select one:

• At the end of the table
• At the beginning of the table
• At the key calculated by the function
• Relative to the lowest-valued existing item

Question 39: Assume that you have a hash table with 9 slots. Let the hash function be h(k)=k mod 9, where k is the key. The list of keys to be added to the hash table is: 5, 6, 8, 39, 15, 23, 44, 33, and 17. How many entries does Slot 5 of the hash table have? Select one:

• 0
• 1
• 2
• 3

Question 40: In a hash table, “chaining” means using which of the following? Select one:

• Arrays in contiguous memory
• Linked lists in non-contiguous memory
• A list to implement the hash table itself
• A list to store entries with the same keys

Question 41: Which of the following statements is true? Select one:

• Graphs are a special case of trees.
• A graph must have at least one edge.
• A graph must have at least one vertex.
• Vertices are each connected via at least two edges.

Question 42: A good hash function should do which of the following? Select one:

• Use real numbers
• Allow table overflows
• Use some random function
• Map any key into one of the slots

Question 43: What can the maximum height of a binary search tree with n nodes be? Select one:

• n
• n−1
• 2n
• log(n+1)/2

Question 44: The ____ tree-traversal method arrives fastest at a leaf. Select one:

• pre-order
• post-order
• depth-first
• breadth-first

Question 45: When do hash tables have collisions? Select one:

• When two entries are identical except their keys
• When two entries with different data have the same key
• When two entries with the same key have different hash values
• When two entries with different keys have the same hash value

Question 46: Which of the following statements is true? Select one:

• Trails are a subset of walks.
• Walks are a subset of circuits.
• Paths are a super-set of walks.
• Cycles are a super-set of walks.

Question 47: Assume that you have a hash table with 5 slots. Let the hash function be h(k)=k mod 5, where k is the key. Which slot will number 23 map to? Select one:

• 0
• 1
• 2
• 3

Question 48: Compared to hashing, which of the following statements about linear probing is true? Select one:

• Collisions never occur.
• Sequential search looks for the key or its absence when a collision occurs.
• Fibonacci steps are used to search for the key or its absence when a collision occurs.
• A hash-function parameter is adjusted and the function is recalculated when a collision occurs.

Question 49: A hashing technique is called “perfect” if the worst-case number of memory accesses required to perform a search is which of the following? Select one:

• O (1)
• O (n)
• O (log n)
• O (n log n)

Question 50: How can structures and classes be treated as abstract data types? Select one:

• Any process having a pointer to the object can call any method within the object.
• The memory occupied by the object itself and its internal data is entirely contiguous.
• Structures contained within classes are not necessarily accessible outside the class object.
• Their data is entirely public and can be changed by any process having a pointer to the object.

Question 51: Why may an array not always occupy contiguous memory? Select one:

• Garbage cleanup includes memory defragmentation.
• The allocation method may employ blocks that point to sub-blocks.
• Memory may be rearranged automatically by the operating system.
• There may be insufficient memory to allocate the required block size.

Question 52: Which of the following terms describes adding an item to a stack? Select one:

• Inserting
• Popping
• Pushing
• Updating

Question 53: Which of the following terms describes the removal of an element from a stack? Select one:

• Deleting
• Popping
• Pushing
• Reallocating

Question 54: What are terms for adding and removing elements from a queue? Select one:

• Push, Pop
• Insert, Delete
• Inject, Extract
• Enqueue, Dequeue

Question 55: A pointer is which of the following? Select one:

• The memory address of the program’s main () function
• A variable that stores the memory address of another variable
• The memory address of the program’s last executable statement
• The memory address of the program’s first executable statement

Question 56: We can create a reference operator by adding a(n) ____ in front of the variable name. Select one:

• *
• &
• #
• _

Question 57: In C++, how would you extend the numeric range of a normal integer? Select one:

• long int i;
• double int i;
• unsigned int i;
• int i [<number of words desired>];

Question 58: What is true about the following code?

int num [10];

int *ptr1 = & (num [0]);

*(ptr1 + 2) = 8;

Select one:

• The value of the third element of the array is 8.
• The value of the third element of the array is 10.
• The pointer ptr1 contains the memory address of the first element of the array.
• The pointer ptr1 contains the memory address of the third element of the array.

Question 59: A NULL pointer does which of the following? Select one:

• Does not point to any memory address
• Holds the memory address of the main method
• Points to a memory address that holds no value
• Holds the memory address to the end of the program

Question 60: When is memory allocated while using dynamic memory allocation? Select one:

• At run time
• At design time
• At compile time
• Only when a class constructor is invoked

Question 61: What is the main purpose of a destructor? Select one:

• To end a program
• To release resources used by an object
• To destroy viruses or malicious programs
• To pass resources on to a replacement object

Question 62: A linked list is which of the following? Select one:

• A data structure to store values in an array
• A data structure that facilitates random access to stored values
• A fixed-length data structure that expands and contracts as needed
• A data structure where one value points to a subsequent and/or previous value

Question 63: The stack data structure can be implemented as which of the following? Select one:

• Hash Table
• FIFO Queue
• LIFO Queue
• LILO Queue

Question 64: The runtime efficiency of binary search using Big-O notation is which of the following? Select one:

• O (n)
• O (log n)
• O (n2)
• O (n log n)

Question 65: Which of the following sets of Big-O notations is arranged from most to least efficient? Select one:

• O(n), O (log n), O (n2)
• O (log n), O(n), O (n2)
• O (n2), O(n), O (log n)
• O (n2), O (log n), O(n)

Question 66: The expected height of a balanced binary search tree with n nodes is which of the following? Select one:

• O (1)
• O (n)
• O (log n)
• O (n log n)

Question 67: The worst runtime case occurs in a linear search algorithm when the item is which of the following? Select one:

• The first element in the array
• The last element in the array
• In the second half of the array
• Somewhere in the middle of the array

Question 68: The worst-case scenario for the binary search of an array requires how many comparisons? Select one:

• 1
• n
• n+1/2
• log(n)+1

Question 69: In terms of Big-O notation, the efficiency of bubble sort can be represented by which of the following? Select one:

• O (n)
• O (n2)
• O (log n)
• O (n log n)

Question 70: The worst-case number of comparisons required to perform a deletion in an unbalanced binary search tree with n nodes is which of the following? Select one:

• O (1)
• O (n)
• O (log n)
• O (n log n)

Question 71: A ____ may have a repeated edge. Select one:

• trail
• critical path
• spanning tree
• multi-branch tree

Question 72: What can the minimum height of a binary-search tree with n nodes be? Select one:

• n
• n−1
• n2
• log(n+1)/2

Question 73: For integer-valued keys, which of the following hash functions is bound to generate collisions but no errors, given any range of positive-value keys, an array-table of size t = 1000, and a computer with b = 64-bit words? Select one:

• h(i)=i
• h(i)=i mod t
• h(i)= (i
• h(i)= (i mod(b/2)) −b

Question 74: Which of the following statements is true? Select one:

• Paths are equivalent to trails.
• Walks are a superset of trails.
• Cycles are a subset of circuits.
• Circuits are a superset of trails.

Question 75: Compared to undirected graphs, directed graphs have which of the following? Select one:

• No cycles
• Fewer edges
• No spanning trees
• Edges for traversal in one direction

Question 76: Suppose you have to insert the values 5, 28, 29, 15, 20, 33, 12, 17, 10 into a hash table. Let the hash function h(k)=k mod 9. How many collisions will there be? Select one:

• 0
• 1
• 2
• 3

Question 77: The simplest way to solve the problem of “collision” in a hash table is to do which of the following? Select one:

• Use chaining
• Rebalance the table
• Use a random hash function
• Increase the size of the hash table

Question 78: “Contiguous memory” is which of the following? Select one:

• Memory blocks whose words all have consecutive addresses
• Memory blocks that are allocated entirely from active memory
• A collection of memory blocks where each block points to the next
• A memory block that is allocated using standard language methods

Question 79: In what way are abstract data types (ADTs) related to the C++ Standard Template Library (STL)? Select one:

• The STL is a superset from which abstract data types are derived.
• An ADT has a description or “definition”. STL members are not so constrained.
• The STL is a collection of ADTs that offer definitions of commonly-required objects.
• The STL is a library of ADTs created by the programmer over time to promote reusable code.

Question 80: What will the result of compiling this C++ code be?

int x = sum_array [0];

int i = 0;

while (i < sum_array. length)

{x = sum_array[i]; i++;}

Select one:

• An infinite loop will occur.
• The code will not compile.
• At the end of the loop, the sum will be stored in the variable i.
• At the end of the loop, the sum will be stored in the variable x.

Question 81: Is it possible for a scalar type to have a different numeric range using the same compiler on different machines? Select one:

• Yes. Compilers have options that can be set for the bit-size of the computer in question.
• Yes. The loader will always allocate appropriate memory and word lengths for the code in question.
• No. The loader is not capable of allocating program space for code built for shorter word lengths.
• No. Compilers for one bit-length will not produce executable code for computers of other bit-lengths.

Question 82: Which of the following statements is true? Select one:

• A class cannot have more than one constructor.
• A constructor without input arguments is not allowed.
• A constructor with no arguments is called a default constructor.
• A class without a default constructor will cause a compiler error.

Question 83: Which of the following statements about the linked list data structure is true? Select one:

• Linked lists occupy contiguous memory.
• Memory is allocated at the beginning of the program.
• Memory is allocated dynamically as the program runs.
• There are no nodes without programmer-assigned data values.

Question 84: In which of the following kinds of linked list does the last node point to the first node? Select one:

• Singly linked lists
• Doubly linked lists
• Multiply linked lists
• Circular linked lists

Question 85: What is the essential difference between arrays and linked lists? Select one:

• Array elements can be directly accessed, whereas linked list elements can only be accessed via an indexing vector.
• Array elements always occupy contiguous memory, whereas linked lists always occupy non-contiguous memory.
• Arrays use scalar index values to directly reference an element of the array. linked list elements do not have direct reference.
• linked lists always include arrays as linked elements. These arrays provide pointers to subsequent and previous list elements.

Question 86: Which of the following statements about a simple graph is true? Select one:

• It may contain loops.
• It may have weighted edges.
• It contains only undirected edges.
• It has nodes that connect via multiple edges.

Question 87: Assume that you have a hash table with 9 slots. Let the hash function be h(k)=k mod 9, where k is the key. The list of keys to be added to the hash table is: 5, 6, 8, 39, 15, 23, 44, 33, and 17. How many entries does Slot 0 of the hash table have? Select one:

• 0
• 1
• 2
• 3

Question 88: Suppose you have to insert the values 5, 28, 29, 15, 20, 33, 12, 17, 10 into a hash table. Let the hash function h(k)=k mod 9. At which slot will 33 be inserted? (There are 9 slots in the table.) Select one:

• Slot 5
• Slot 6
• Slot 7
• Slot 9

Question 89: Which of the following statements about trees is true? Select one:

• Trees can have cycles.
• Trees are special cases of graphs.
• Trees cannot be implemented using arrays.
• Trees must be implemented using objects that point to each other.

Question 90: Assume that you have a hash table with 9 slots. Let the hash function be h(k)=k mod 9, where k is the key. The list of keys to be added to the hash table is: 5, 6, 8, 39, 15, 23, 44, 33, and 17. How many entries does Slot 1 of the hash table have? Select one:

• 0
• 1
• 2
• 3

Question 91: A perfect hash function does which of the following? Select one:

• Minimizes collisions
• Minimizes insertion/deletion time
• Produces a unique hash value for each different key
• Produces a unique hash value in the least amount of time