CS201: Elementary Data Structures Certification Answers

Clear My Certification March 15, 2024 Computer Science Leave a comment 161 Views

Elementary data structures are fundamental building blocks used in computer science to store and organize data efficiently. They provide the basic tools for manipulating data and are essential for designing and implementing more complex algorithms and data structures. Here are some commonly used elementary data structures:

Arrays: Arrays are a contiguous collection of elements stored in memory, where each element is accessed by its index. They offer constant-time access to elements but may have limitations when it comes to resizing and inserting elements.
Linked Lists: Linked lists are a collection of nodes where each node contains a data element and a reference (or pointer) to the next node in the sequence. They offer efficient insertion and deletion operations, but accessing elements may require traversal from the beginning of the list.
Stacks: Stacks are a last-in, first-out (LIFO) data structure where elements are added and removed from the same end, called the top. They support two main operations: push (adding an element to the top) and pop (removing the top element).
Queues: Queues are a first-in, first-out (FIFO) data structure where elements are added at the rear (enqueue) and removed from the front (dequeue). They support operations like enqueue, dequeue, and peek (viewing the front element without removing it).
Hash Tables: Hash tables are data structures that store key-value pairs, where each key is hashed to generate an index in an array. They provide fast retrieval, insertion, and deletion of elements, typically with constant-time complexity on average, assuming a good hash function and collision resolution strategy.
Trees: Trees are hierarchical data structures composed of nodes, where each node has a value and a set of children nodes. They include various types such as binary trees, binary search trees, AVL trees, and red-black trees. Trees are commonly used for organizing and searching data efficiently.
Graphs: Graphs consist of a set of vertices (nodes) connected by edges. They can be directed or undirected and may have weighted or unweighted edges. Graphs are used to model relationships between objects and are fundamental in various applications like social networks, transportation networks, and computer networks.

These elementary data structures serve as the foundation for more complex data structures and algorithms used in computer science and software development. Understanding their properties, operations, and trade-offs is essential for designing efficient and scalable software systems.

CS201: Elementary Data Structures Exam Quiz Answers

CS201 Elementary Data StructuresElementary Data Structures

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

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:

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:

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:

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:

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:

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:

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