Question 1

Which of the following loops correctly uses iter as an iterator to move through the nodes of the linked list?
NodePtr iter; //a pointer to a node
A) whileiter != NULL) iter++;
B) whileiter != NULL) iter=iter->link;
C) foriter=NULL; iter != NULL; iter=iter->link)
D) for iter=head; iter != NULL; iter=iter->link)

Accepted Answer

Option D correctly initializes iter to the head of the linked list and then moves it through the nodes using iter->link. Options A and C incorrectly try to move iter itself to the next node, while option B moves iter through the links of the nodes without starting at the head.

Question 2

A stack exhibits ______________ behavior
A) last-in/ first-out
B) last-in/last-out
C) first-in/first-out
D) none of the above

Accepted Answer

A stack follows the concept of last-in/first-out (LIFO), where the last element to be added is the first one to be removed.

Question 3

If NodeTypePtr is defined to be a pointer type to a node in a linked list, then the declaration
NodeTypePtr head;
A) allocates memory for the node that head will point to
B) automatically makes head->link point to NULL
C) allocates only the memory for a pointer variable
D) allocates a linked list

Accepted Answer

The declaration "NodeTypePtr head;" only allocates memory for a pointer variable, not for a node or a linked list. It simply creates a pointer variable named "head" that can point to a node in a linked list. The memory for the actual node(s) in the list must be allocated separately, either by dynamically creating new nodes with malloc() or by using a pre-existing node(s) as the head of the list.

Question 4

Given the following declarations, which statement would allocate memory for the first item in the list?
Struct Node
{
Int item;
Node* link;
};
Typedef Node* NodePtr;
NodePtr head;
A) head = new Node;
B) head = new int;
C) head->link=NULL;
D) head = new NodePtr;

Accepted Answer

Option A allocates memory for a new Node and assigns the memory address to head. This creates a new Node instance with both the item and link fields initialized to garbage values (unless a constructor is explicitly defined). The other options do not allocate memory for a new Node instance. Option B allocates memory for a single integer and assigns the memory address to head, which would not work since head is of type NodePtr (a pointer to a Node). Option C sets the link field of head to NULL, but does not allocate any memory for a new Node instance. Option D allocates memory for a new NodePtr and assigns the address of that memory to head (which would again be useless, as head is already a NodePtr).

Question 5

The actual value of NULL is
A) -1
B) 0
C) 99999
D) -99

Accepted Answer

The actual value of NULL in programming is 0. It represents a lack of a value, or a pointer that does not point to any memory location.

Question 6

As defined in the text, the pointer variable head
A) is the first node in the list
B) points to the first node in the list
C) is always NULL
D) is undefined

Accepted Answer

The pointer variable head points to the first node in the list, which is different from being the first node itself.

Question 7

If you need to access the last element of a linked list with N nodes in it, how many comparisons do you need to make to find the last element?
A) 0
B) 1
C) N-1
D) N

Accepted Answer

To access the last element of a singly linked list, you need to traverse from the head to the last node, making N comparisons to reach the end.

Question 8

What is wrong with the following definition of headInsert?
Struct Node
{
Int item;
Node* link;
};
Typedef Node* NodePtr;
Void headInsertNodePtr& head, int data)
{
NodePtr tmp = new Node;
Tmp->item = data;
Head->next = tmp;
Tmp->next = head->next;
}
NodePtr head;
HeadInserthead, 4);
A) head->next is pointing to NULL
B) if there were any nodes following head they are now lost.
C) nothing is wrong.
D) tmp should be declared to be a Node not a NodePtr

Accepted Answer

The headInsert function is supposed to insert a new node at the beginning of the linked list, but the implementation is incorrect. Setting `head->next = tmp;` effectively deletes any nodes that were previously linked after `head`, because `head->next` is not preserved before the assignment. Therefore, option B is the correct choice.

Question 9

Given the following stack declaration, which of the following function definitions would correctly implement the destructor?
Struct StackFrame
{
Char data;
StackFrame *link;
};
Typedef StackFrame* StackFramePtr;
Class Stack
{
Public:
Stack );
Stackconst Stack& a_stack);
~Stack );
Void pushchar the_symbol);
Char pop );
Bool empty ) const;
Private:
StackFramePtr top;
};
A) top=NULL;
B) char next;
While ! empty ))
Next = pop );//pop calls delete.
C) char next;
While!empty ))
Next = push);
D) none of the above

Accepted Answer

Option B correctly implements the destructor by using a loop to pop all elements from the stack until it's empty. The `pop` function is assumed to deallocate memory for each `StackFrame`, effectively destroying the stack.

Question 10

What happens if you have two lists list1, list2), no assignment operator in your class, and attempt to execute the following statement?
List1 = list2;
A) you have a syntax error
B) you get a complete and identical copy of list2 into list1
C) list1 and lsit2 now name the same list
D) no problem

Accepted Answer

Without a custom assignment operator, assigning one list to another (List1 = list2;) in many programming languages (like Python) simply makes both variables point to the same list object in memory. This means any modification to the list through one of the variables will be reflected when accessing it through the other variable.

Question 11

In the following search function for a linked list using the Node and NodePtr as defined in the text), why is there code to check if here is NULL?
NodePtr searchNodePtr head, int target)
{
NodePtr here = head;
Ifhere == NULL)
{
Return NULL;
}
Else
{
While here->data != target && here->link != NULL)
{
Here = here->link;
}
Ifhere->data == target)
{
Return here;
}
Else
{
Return NULL;
}
}
}
A) the list may be empty
B) the list may be full
C) there is no reason for that code to be there
D) A and B

Accepted Answer

The check for `here == NULL` is necessary to handle the case where the linked list is empty, meaning `head` is `NULL`. This prevents the function from attempting to access members of a `NULL` pointer, which would result in undefined behavior.

Question 12

To add an item to a stack, we call the ______ function
A) pop
B) top
C) push
D) empty

Accepted Answer

To add an item to a stack, we use the push function.

Question 13

Given a linked list using the code from the book), which of the following sets of statements would implement a function to return the last item in the list?
A) NodePtr here;
Here=head;
Whilehere->link != NULL)
{
Here = here ->link;
}
Return here->data;
B) NodePtr here;
Here=head->link;
Whilehere != NULL)
{
Here = here ->link;
}
Return here->data;
C) NodePtr here;
Whilehere->link != NULL)
{
Here = here ->link;
}
Return here->data;
D) NodePtr here;
Here=head;
Whilehere->link != NULL)
{
Here = here ->link;
}

Accepted Answer

Option A starts at the head of the linked list and iterates through each node using the link field until it reaches the end of the list (where the link is NULL). It then returns the data of the last node. This correctly implements a function to return the last item in the linked list. Option B and C start at the second node of the linked list (head->link), which will not necessarily be the last node. Option D is identical to option A but does not return anything, so it is not a valid solution to the problem presented.

Question 14

Given the following function declaration
Void insert NodePtr afterMe, int num);
//PRE: afterMe points to some node in the non-empty list
//POST: A new node containing num is inserted after afterMe.
Void insertNodePtr afterMe, int num)
{
// which of the following function definitions correctly implement this //function?
}
A) afterMe->link = new Node; afterMe->link->data = num;
AfterMe -> link ->link=afterMe->link;
B) NodePtr tmp=new Node; tmp-> data = num;
AfterMe -> link = tmp;
Tmp->link = afterMe -> link;
C) NodePtr tmp=new Node; tmp-> data = num;
Tmp->link = afterMe -> link;
AfterMe -> link = tmp;
D) NodePtr tmp=new Node; tmp-> data = num;
AfterMe -> link = tmp;
Tmp->link = NULL;

Accepted Answer

Choice C correctly creates a new node (tmp) with the given integer value, links tmp to the node after afterMe, and links afterMe to tmp. Therefore, a new node containing num is inserted after afterMe. Choice A incorrectly links tmp to afterMe instead of afterMe's next node, and also creates an unnecessary circular loop. Choice B correctly creates a new node with the given integer value, but links tmp to afterMe instead of afterMe's next node. Choice D correctly creates a new node with the given integer value, but links tmp to NULL instead of afterMe's next node.

Question 15

To remove an item from the stack, we call the ____ function
A) pop
B) top
C) push
D) empty

Accepted Answer

The pop function removes and returns the top element of the stack.

Question 16

Given a linked list using the code from the book) and assuming there are at least two nodes in the list, which of the following sets of statements would implement a function to return and remove the last item in the list?
A) NodePtr here;
Here=head;
Whilehere->link != NULL)
{
Here = here ->link;
}
Return here->data;
Delete here;
B) NodePtr here;
Here=head;
Whilehere->link != NULL)
{
Here = here ->link;
}
Delete here;
Return here->data;
C) int tmp;
NodePtr here, there;
Here=head;
Whilehere->link != NULL)
{
There = here;
Here = here ->link;
}
There->link = NULL;
Tmp=here->data;
Delete here;
Return tmp;
D) int tmp;
NodePtr here, there;
Here=head;
Whilehere->link != NULL)
{
There = here;
Here = here ->link;
}
There->link = NULL;
Tmp=here->data;
Return tmp;
Delete here;

Accepted Answer

Option A and B correctly identify the last node and remove it, but they do not update the link of the second-to-last node to properly remove the last node from the list. Option D incorrectly places the `delete here;` statement after the return statement. Option C correctly identifies the last node, updates the link of the second-to-last node, removes the last node from the list, and returns its data. Thus, option C is the best choice.

Question 17

Given the following declarations, which statement would put the value of 3 in the item part of the first node in the linked list?
Struct Node
{
Int item;
Node* link;
};
Typedef Node* NodePtr;
NodePtr head;
Head = new Node;
A) head=3;
B) head.item=3;
C) *head.item=3;
D) head->item=3;

Accepted Answer

Option A is incorrect because we cannot assign an integer value directly to a Node pointer.
Option B is incorrect because we need to use the arrow operator (->) to access the item field of the Node pointer.
Option C is incorrect because we cannot use the dereference (*) operator on an integer value.
Option D is correct because it correctly accesses the item field of the Node pointer and assigns a value of 3 to it using the assignment operator (=).

Question 18

The arrow operator ->) specifies
A) a member of a struct or class that is pointed to by a pointer variable
B) the pointer member only of a struct or a class that is pointed to by a pointer variable
C) less than or equal
D) is known as NULL

Accepted Answer

The arrow operator -> is used to access a member of a struct or class that is pointed to by a pointer variable. It is often used in combination with the * operator to dereference the pointer and access the member.

Question 19

Given the following stack declaration, which of the following function definitions would correctly push an item onto the stack?
Struct StackFrame
{
Char data;
StackFrame *link;
};
Typedef StackFrame* StackFramePtr;
Class Stack
{
Public:
Stack );
Stackconst Stack& a_stack);
~Stack );
Void pushchar the_symbol);
Char pop );
Bool empty ) const;
Private:
StackFramePtr top;
};
A) void Stack::pushchar the_symbol)
{
StackFrame temp_ptr;
Temp_ptr = new StackFrame;
Temp_ptr->data = the_symbol;
Temp_ptr->link = top;
Top = temp_ptr;
}
B) void Stack::pushchar the_symbol)
{
StackFramePtr temp_ptr;
Temp_ptr->data = the_symbol;
Temp_ptr->link = top;
Top = temp_ptr;
}
C) void Stack::pushchar the_symbol)
{
StackFramePtr temp_ptr;
Temp_ptr = new StackFrame;
Temp_ptr->data = the_symbol;
Temp_ptr->link = top;
}
D) void Stack::pushchar the_symbol)
{
StackFramePtr temp_ptr;
Temp_ptr = new StackFrame;
Temp_ptr->data = the_symbol;
Temp_ptr->link = top;
Top = temp_ptr;
}

Accepted Answer

Option D correctly creates a new StackFrame pointer, assigns the symbol to its data member, assigns the top to its link member, and then assigns the new pointer as the top of the stack. Option A also creates a new StackFrame pointer and assigns both the symbol and the top to its members, but fails to assign the new pointer as the top of the stack. Option B attempts to assign the symbol to a StackFramePtr without first creating the pointer, which will result in a segmentation fault. Option C correctly creates a new StackFrame pointer, assigns the symbol to its data member and assigns the top to its link member, but it fails to assign the new pointer as the top of the stack.

Question 20

If you push the following numbers onto an integer stack, what item is on the top of the stack? 1,4,8,16)
A) 1
B) 4
C) 8
D) 16

Accepted Answer

Since the problem only states that we are pushing the numbers onto an integer stack without specifying any operations, the last number pushed would be on top of the stack. Therefore, the top of the stack is 16.

Quiz 13: Pointers and Linked Lists

Which of the following loops correctly uses iter as an iterator to move through the nodes of the linked list? NodePtr iter; //a pointer to a node

A stack exhibits ______________ behavior

If NodeTypePtr is defined to be a pointer type to a node in a linked list, then the declaration NodeTypePtr head;

Given the following declarations, which statement would allocate memory for the first item in the list? Struct Node { Int item; Node* link; }; Typedef Node* NodePtr; NodePtr head;

The actual value of NULL is

As defined in the text, the pointer variable head

If you need to access the last element of a linked list with N nodes in it, how many comparisons do you need to make to find the last element?

What is wrong with the following definition of headInsert? Struct Node { Int item; Node* link; }; Typedef Node* NodePtr; Void headInsertNodePtr& head, int data) { NodePtr tmp = new Node; Tmp->item = data; Head->next = tmp; Tmp->next = head->next; } NodePtr head; HeadInserthead, 4) ;

What happens if you have two lists list1, list2) , no assignment operator in your class, and attempt to execute the following statement? List1 = list2;

To add an item to a stack, we call the ______ function

Given a linked list using the code from the book) , which of the following sets of statements would implement a function to return the last item in the list?

To remove an item from the stack, we call the ____ function

Given a linked list using the code from the book) and assuming there are at least two nodes in the list, which of the following sets of statements would implement a function to return and remove the last item in the list?

Given the following declarations, which statement would put the value of 3 in the item part of the first node in the linked list? Struct Node { Int item; Node* link; }; Typedef Node* NodePtr; NodePtr head; Head = new Node;

The arrow operator ->) specifies

If you push the following numbers onto an integer stack, what item is on the top of the stack? 1,4,8,16)