CISC220 Midterm 1 Study Guide

IN C++ which of the following allows for direct modification of an argument’s value when passed to a function?

Call by reference

Nick is writing an implementation of the queue ADT. which of the following implementations would have the fastes time complexity for the enqueue and dequeue operations? Select all the apply

SLL and DLL

For insertion at the end of a list, which of the following list implementations is the most efficient

• array

• sll without last pointer

• sll with last pointer

• dll

• sll with last pointer

• dll

Which of the following datatypes are passed by pointer by default?

• strings

• objects

• arrays

• doubles

• nothing is passed by pointer by default

arrays

Which of the followintg describes a memory leak?

• when memory is allocated on the stack and not cleaned up afterward

• when memory is allocated on he heap and not cleaned up afterward

• when an excessive ammount of memory is allocated to a program and not used

• when memory is allocated on the heap and the address is lost of overwritten before it can be deallocated

• when pointers are mismanages such that the program tries to access memory that is not allocated to it

• when memory is allocated on he heap and not cleaned up afterward

• when memory is allocated on the heap and the address is lost of overwritten before it can be deallocated

For insertion at the beginning of a list, which of the following list implementations is the least efficient

• array

• sll w/o last pointer

• sll with last pointer

• dll

arrat

Removing an element from an array implementation of a list requires approximately 2n space

true

Pop can be done in O(1) time for linked list implementations

False

Provide the appropriate line of code to accomplish the task:
Create a string variable name on the stack with a value of Jake

string name = “Jake”;

Provide the appropriate line of code to accomplish the task:

create a double variable a on the heap

a = new double;

Provide the appropriate line of code to accomplish the task:

Set the address in a to hold a value of 8.3

*a = 8.3

Provide the appropriate line of code to accomplish the task:
Create a boolean arr of length 6 on the heap

bool *arr = new bool [6];

Provide the appropriate line of code to accomplish the task:
Create a pointer sPtr that points at name

String sPtr* = &name;

Provide the appropriate line of code to accomplish the task:
create a pointer sPtr2 that points at sPtr

string **sPtr2 = &sPtr;

Provide the appropriate line of code to accomplish the task:
create a pointer arrPtr that points at the inital index in arr

bool *arrPtr = arr;

Provide the appropriate line of code to accomplish the task:
move arrPtr to point at the next index in arr

arrPtr++;

Provide the appropriate line of code to accomplish the task:
print out the value of name using sPtr2

cout « **sptr2«endl;

Provide the appropriate line of code to accomplish the task:
deallocate a

delete a

Provide the appropriate line of code to accomplish the task:
Deallocate arr

delete [] arr;

Which list implementation is most efficient for the following operations (array, SLL without last pointer, SLL with last pointer, DLL)

Find kth element

array

Which list implementation is most efficient for the following operations (array, SLL without last pointer, SLL with last pointer, DLL)
Remove kth element

all???

Which list implementation is most efficient for the following operations (array, SLL without last pointer, SLL with last pointer, DLL)
Find x in the list

all

Which list implementation is most efficient for the following operations (array, SLL without last pointer, SLL with last pointer, DLL)
Insert at the beginning of the list

SLL and DLL

Which list implementation is most efficient for the following operations (array, SLL without last pointer, SLL with last pointer, DLL)
Insert at the end of the list

SLL wit last pointer, DLL

What is the time complexity to:
Remove last in a SLL without the last pointer

O(n)

What is the time complexity to:
Remove last in an array

O(n)

What is the time complexity to:
Insert at the beginning of a SLL

O(1)

What is the time complexity to:
Concatenate with two DLLs

O(1)

For insertion at the beginning of a list, which of the following list implementations is the least efficient?

• array

• sll without last pointer

• sll with last pointer

• dll

array

In a singly linked list, which of the following statements is true?

• each node contains a reference to the previous node

• each node contains a reference to the next node

• each node contains a reference to the first node

• it allows for constant-time random access to elements

• it has a fixed size determines at initialization

• each node contains a reference to the next node

Inserting an element into an array implementation of a list requires approximately 2n total space

True

According to list ADT, lists must have indices

True

Which of the following datatypes are passed by pointer by default?
- strings

• objects

• arrays

• doubles

• nothing is passed by pointer by default

arrays

According to the List ADT, implementations must support insertion at the kth position

True

In C++, which of the following allows for direct modification of an argument’s value when passed to a function?

• call by value

• call by pointer

• call by reference

• none of the above

call by reference

In a doubly linked list, which of the following operations has the highest time complexity (big ) notation?
- insertion at the beginning

• deletion from the end

• searchin for an element

• reversing the list

Searching for an element

Reversing the list

What is the worst-case time complexity of Selection Sort?

a) O(log n)
b) O(n)
c) O(n log n)
d) O(n²)

O(n^2)

Which sorting algorithm inserts elements into an already sorted sublist?
a) Quick Sort
b) Bubble Sort
c) Selection Sort
d) Insertion Sort

d) Insertion Sort

True or False: In C++, arrays are passed into functions by value.

False

Which of the following correctly declares a pointer to an integer?
a) int x;
b) int x;
c) int x;
d) int &x;

int *x;

What does the '&' symbol represent in C++?
a) Value
b) Address
c) Dereference
d) Multiplication

Address

Which function call modifies the original variable in main?
a) void f(int x, int y)
b) void f(int x)
c) void f(int x*)
d) void f(int &x)

void f(int &x)

What is printed by this code?
int x = 3; void doublefn(int x) { x = x * 2; } doublefn(x); cout << x;
a) 3
b) Compilation error
c) 0
d) 6

3

Which of the following is NOT true about the heap?
a) Memory is manually managed
b) Variables persist beyond scope
c) Compiler controls allocation
d) Used with 'new' keyword

Compiler controls allocation

What does the delete keyword do in C++?
a) Removes a variable from scope
b) Deletes a file
c) Frees memory on the heap
d) Frees memory on the stack

Frees memory on the heap

True or False: A destructor is automatically called when an object goes out of scope.

True

Which of the following is a valid reason to use the heap?
a) To manage global constants
b) To speed up execution
c) To create objects that persist beyond function scope
d) To store temporary loop variables

To create objects that persist beyond function scope

Output?
ZooCreature *animal = new ZooCreature;

animal->firstname = "Gerald";

func1(animal);

cout << animal->firstname;

void func1(ZooCreature *pet) { pet->firstname = "April"; }

a) Compilation error
b) Undefined
c) April
d) Gerald

April

Which of the following is NOT a characteristic of a linked list?
a) Sequential access
b) Fixed size
c) Dynamic memory allocation
d) Allows duplicates

Fixed size

Which operation adds a node to the end of a linked list?
a) insert()
b) addFirst()
c) pop()
d) push()

push()

What does the next pointer in a linked list node do?
a) Points to next node
b) Stores data
c) Points to head of list
d) Points to previous node

Points to next node

True or False: Arrays allow random access while linked lists allow sequential access.
a) Only for doubly linked lists
b) False
c) True
d) Only for sorted arrays

True

Which sorting algorithm performs better on nearly sorted data?
a) Merge Sort
b) Bubble Sort
c) Insertion Sort
d) Selection Sort

Insertion Sort

What is the role of a destructor in a class with heap-allocated fields?
a) Print debug info
b) Initialize variables
c) Free heap memory
d) Allocate stack memory

Free heap memory

Which of the following correctly inserts a node at the kth position in a linked list?
a) kthNode->next = node;
b) node->next = kthNode->next; kthNode->next = node;
c) node = kthNode->next;
d) node->next = kthNode;

node->next = kthNode->next; kthNode->next = node;

Output?
MyClass t(2,"a");

for (int i = 0; i < 2; i++) { MyClass t2(3,"l"); }

MyClass t3(2,"m");

a) lalm
b) alm
c) mll
d) llam

alm