Deck 17: Linked Data Structures

Question 1

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

Answer 1

False

Question 2

A tree is a recursive structure.

Answer 2

True

Question 3

Data is removed at the back of the queue.

Answer 3

False

Question 4

To insert a node into a doubly linked list requires references to the node before and after the location we wish to insert the new node.

Question 5

Placing data on a stack is called popping the stack.

Question 6

Data is inserted into a queue at the back.

Question 7

Which of the following are potential problems when we use the delete operator on a pointer variable?

A)inaccessible heap memory
B)dangling pointers
C)uninitialized pointers
D)NULL pointers

Question 8

Given the structure definition:
const int STRING_SIZE = 20;
struct ListNode
{
char item[STRING_SIZE];
int count;
ListNode * link;
};
ListNode *head = new ListNode;
Show two equivalent ways to set the count member in the ListNode variable to which head points.

Question 9

A hash function maps an object to a unique number.

Question 10

A friend class is made to further a sense of community among the students.

Question 11

Removing data from a stack is called popping the stack.

Question 12

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

Question 13

A linked list is

A)fixed in size
B)can vary in size,shrinking or growing as there is need
C)can be set,and then not changed other than destroying the list
D)none of the above

Question 14

Given the type definitions:
const int STRING_SIZE = 20;
struct ListNode
{
char item[STRING_SIZE];
int count;
ListNode * link;
};
What is the output produced by the following code? (As always,you are to assume that the code is embedded in a correct and complete program.
ListNode * head = new ListNode;
strcpy( head->item,"Stop Light");
head->count = 10;
cout << (*head).item << endl;
cout << head->item << endl;
cout << (*head).count << endl;
cout << head->number << endl;

Question 15

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

Question 16

The link field in the last node in a linked list has a special value stored in it.What is it? It has a special name.What is the special name? Why is this done?

Question 17

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

Question 18

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

Question 19

Insertion into a linked list takes the same number of operations no matter where the insertion occurs

Question 20

Given the structure definition:
const int STRING_SIZE = 20;
struct ListNode
{
char item[STRING_SIZE];
int count;
ListNode *link;
};
ListNode *head = new ListNode;
Give code to assign the string "Wilbur's brother Orville" to the member item of the variable to which head points.Hint: you need a function declared in cstring.

Question 21

Here is a diagram of a three node linked list with a head pointer and a node to be inserted.Show all steps necessary to delete the second node,pointed to by discard_me.You may assume the necessary search for the node to be deleted is done and the pointer discard_me is already positioned.
You are to make clear the sequence of steps by either numbering the steps,or by making several copies of this drawing,with one change per drawing,numbered to show the sequence.
You may assume that a search routine taking a head pointer and data arguments has been defined for you.
Give code and the drawing to make clear what you are doing.
NodePtr discard_me;
NodePtr temp_ptr;

Question 22

Given the type definitions:
const int STRING_SIZE = 20;
struct ListNode
{
char item[STRING_SIZE];
int count;
ListNode *link;
};
ListNode *head = new ListNode;
Give a typedef statement that hides the pointer operator *.Call the new type identifier NodePtr.

Question 23

A linked list is normally specified by giving a pointer pointing to the first node of a list.An empty list has no nodes at all.What is the value of a head pointer for an empty list?

Question 24

Here is a diagram of a three node linked list with a head pointer and a node to be inserted.Show all steps necessary to insert the node pointed to by temp between the second and third nodes,including the search for the node prior to insertion.You are to make clear the sequence of steps by either numbering the steps,or by making several copies of this drawing,with one change per drawing,numbered to show the sequence.You may assume a search routine taking a head node and data has been defined for you.
Give code and the drawing to make clear what you are doing.

Question 25

Given the doubly linked list in the diagram below,give the code to delete the second node in the list with the number 31.Assume each entry in the list is a node of class Node with a public next and prev member variable.

Question 26

Describe why a very large hash table will likely increase the performance (i.e.faster additions and lookup)at the expense of wasting memory,and vice versa,why a small hash table will use less memory but result in a decrease in performance.

Question 27

Name the stack operations as implemented in the text.Tell what each does.

Question 28

Suppose you have the following struct definition and typedef statements in your program:
struct N
{
double d;
N *next;
};
typedef N* node_ptr;
node_ptr head,p1,p2;
Now suppose further that p1 points to a node of type N in the middle of a linked list (neither the first nor the last node).Write code that deletes the node after the node p1 points to in the linked list.After the code is executed,the linked list should be the same,excepting the specified node is missing.

Question 29

Why can a raw pointer be used as an iterator for an array,but not for a list?

Question 30

Give pseudocode for inserting a node in front of the head node in a linked list.