Deck 13: Pointers and Linked Lists

Question 1

There is no need for error checking when pushing a stack.

Answer 1

False

Question 2

A stack is a specialized type of list

Answer 2

True

Question 3

The linked list is always the most efficient storage mechanism for storing many pieces of data.

Answer 3

False

Question 4

Most applications that use a stack will store a struct or class object on the stack.

Question 5

Removing data from a stack is called popping the stack.

Question 6

If you write a linked list class, then you should implement the destructor, copy constructor, and the assignment operator

Question 7

Placing data on a stack is called popping the stack.

Question 8

A stack is a first-in-first-out data structure.

Question 9

The stack can be compared to a line of people at a bank, where the first person in line is the first person served.

Question 10

A queue is first-in-first-out data structure.

Question 11

The stack exhibits last-in/first-out behavior

Question 12

You can directly access the nth node of a linked list

Question 13

*head.item is the same as *head).item

Question 14

There is no need for error checking when popping a stack.

Question 15

A _______ is a list constructed using pointers.

Question 16

The last node in a linked list as defined in the text should always point back to the head of the list.

Question 17

Data is inserted into a queue at the back.

Question 18

The constant NULL can be assigned only to pointers that point to numbers

Question 19

A linked list is not fixed in size.

Question 20

Data is removed at the back of the queue.

Question 21

What C++11 keyword can you use instead of NULL to distinguish between the null value and the number 0?

Question 22

Which operator * or .) has higher precedence?

Question 23

When adding a node to a linked list, which pointer variable do you update first?

Question 24

In a linked list as defined in the text, the pointer in the last node in the list should always point to _________.

Question 25

If you want to make your linked list a class, you must also include the _____.

Question 26

A _________ is a struct or class object that has one or more member variables that are pointer variables.

Question 27

If you want to declare a node type struct and typedef a pointer type for that node, in which order must you make these declarations?

A) first the node pointer, then the node, since the node has a pointer in it.
B) first the node, then the typedef.
C) it doesn't matter which order you do them in
D) you cannot do both of them in the same program.

Question 28

You can define a stack that will hold _________-

Question 29

Apart from constructors, the operations for a stack listed in the text are ____________, _____________, and _______________,

Question 30

The pointer in a node points to

A) the data part of a node
B) the count part of a node
C) the pointer part of the node
D) the whole node

Question 31

Dynamically allocated memory that is no longer pointed to by any pointer variable causes a ______________.

Question 32

The function used to put data into a stack is typically called _______.

Question 33

A stack can be implemented using a __________.

Question 34

If head is a NodePtr pointer variable, write the code to make head point to new node of type Node.

Question 35

Apart from constructors, the operations for a queue listed in the text are ____________, _____________, and _______________,

Question 36

The number of possible nodes in a linked list is __________

Question 37

The function used to get the data at the top or front) of the stack is called _______.

Question 38

The arrow operator ->) combines the actions of which two operators?

Question 39

The first node in a linked list is generally named _________

Question 40

In a node type named MyNode, which of the following correctly declares a pointer to a node of that type?

A) MyNode* ptr;
B) MyNode ptr;
C) ptr myNode*;
D) MyNode.data* ptr;

Question 41

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)

Question 42

A stack exhibits ______________ behavior

A) last-in/ first-out
B) last-in/last-out
C) first-in/first-out
D) none of the above

Question 43

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

Question 44

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;

Question 45

The actual value of NULL is

A) -1
B) 0
C) 99999
D) -99

Question 46

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

Question 47

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

Question 48

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

Question 49

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

Question 50

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

Question 51

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

Question 52

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

A) pop
B) top
C) push
D) empty

Question 53

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;
}

Question 54

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;

Question 55

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

A) pop
B) top
C) push
D) empty

Question 56

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;

Question 57

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;

Question 58

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

Question 59

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;
}

Question 60

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

Question 61

When would you use a linked list over an array or a dynamic array?

A) when you know the maximum size at compile time
B) when you know the maximum size at run-time
C) when you do not know the maximum size
D) when you need to access any item quickly

Question 62

Data is removed from a stack in the _____ _______ it was entered.

A) same order
B) reverse order
C) alternating order
D) sorted order

Question 63

If you need to insert an element in the front of a list with N nodes and move the other elements back one place), how many nodes do you have to move?

A) 0
B) 1
C) N-1
D) N

Question 64

The discipline for a stack is:

A) .data first inserted is the data first out.
B) for a misbehaving stack, 30 lashes.
C) data last inserted is the data first out.
D) depends on the application of the stack.