337 C++ (25-26)

Question 1

What is the basic form of a node?

Answer 1

struct Node {
int data; // Data of the node
Node* next; // Pointer to the next node
};

Question 2

What are the steps for inserting a new item into the linked list.

Answer 2

1. Allocate a new node
2. Fill the node’s data fields
3. Find the insertion position in the current list
4. Splice the new node into the list, adjusting pointers as necessary.

Question 3

Consider the following function. For this example assume that display is already defined. Fill in the blanks 

int main() {
    int i;
//setting values for head
    Node *head = NULL, *temp_ptr; 
    head = new Node;
    \_\_\_\_\_\_\_\_\_\_ = 0;
    \_\_\_\_\_\_\_\_\_\_ = NULL;
    
    for(i = 1; i < 3; i++){
        temp_ptr = \_\_\_\_\_\_\_\_;
        \_\_\_\_\_\_\_\_\_\_\_\_ = i;
        temp_ptr->next = \_\_\_\_\_\_;
        head = \_\_\_\_\_\_\_\_\_;
    }
    display(head);
    return 0;
}

Answer 3

int main() {
    int i;
//setting values for head
    Node *head = NULL, *temp_ptr;
    head = new Node;
    head ->data = 0;
    head ->next = NULL;
    
    for(i = 1; i < 3; i++){
        temp_ptr = New Node;
        temp_ptr->data = i;
        temp_ptr->next = head;
        head = temp_ptr;
    }
    display(head);
    return 0;
}

Question 4

For the following, complete the display function.
#include <iostream>

int main() {
    int i;
    Node *head = NULL, *temp_ptr;
    head = new Node;
    head ->data = 0;
    head ->next = NULL;
    
    for(i = 1; i < 3; i++){
        temp_ptr = New Node;
        temp_ptr->data = 1;
        temp_ptr->next = head;
        head = temp_ptr;
    }
    display(head);
    return 0;
}

void display (Node *ptr)
{
    while(ptr != \_\_\_\_\_\_\_){
        cout<<"data is:"<< \_\_\_\_\_\_\_\_);
        ptr = \_\_\_\_\_\_\_\_\_;
    }
}

Answer 4

#include <iostream>

int main() {
    int i;
    Node *head = NULL, *temp_ptr;
    head = new Node;
    head ->data = 0;
    head ->next = NULL;
    
    for(i = 1; i < 3; i++){
        temp_ptr = New Node;
        temp_ptr->data = 1;
        temp_ptr->next = head;
        head = temp_ptr;
    }
    display(head);
    return 0;
}

void display (Node *ptr)
{
    while(ptr != nullptr){
        cout<<"data is:"<< ptr->data);
        ptr = ptr -> next;
    }
}

Question 5

Complete the recursive function for factorial:
int factorial (int n)
{
    if(\_\_ == \_\_\_)
        return 1;
    else
        return(n* \_\_\_\_\_\_\_\_\_);
    
}

Answer 5

int factorial (int n)
{
    if(n==0)
        return 1;
    else
        return(n* factorial(n-1));
    
}

Question 6

Consider the following function. Complete the recursive function for destroy().

struct Node {
    int item;
    Node *next;
};
class List {
    public:
        List():headM(nullptr){}; // PROMISES: Creates empty list.
        ~List();
        List(const List &rhs);
        void insert(const int& the_item);
        void display();
    private:
        Node *headM;
        Node* copy(const Node* src);
        void destroy();
};

void List::destroy(){
    Node *temp = \_\_\_\_\_\_;
    if(headM != \_\_\_\_\_\_){
        headM = \_\_\_\_\_\_\_\_\_\_\_;
        destroy();
    }
    if(temp != \_\_\_\_\_\_\_)
        delete \_\_\_\_;
}

List::~List(){
    destroy();
}

Answer 6

struct Node {
    int item;
    Node *next;
};
class List {
    public:
        List():headM(nullptr){}; // PROMISES: Creates empty list.
        ~List();
        List(const List &rhs);
        void insert(const int& the_item);
        void display();
    private:
        Node *headM;
        Node* copy(const Node* src);
        void destroy();
};

void List::destroy(){
    Node *temp = headM;
    if(headM != nullptr){
        headM = headM->next;
        destroy();
    }
    if(temp != nullptr)
        delete temp;
}

List::~List(){
    destroy();
}

Question 7

Consider the following function. Write the recursive function for copy().

struct Node {
    int item;
    Node *next;
};
class List {
    public:
        List():headM(nullptr){}; // PROMISES: Creates empty list.
        ~List();
        List(const List &rhs);
        void insert(const int& the_item);
        void display();
    private:
        Node *headM;
        Node* copy(const Node* src);
        void destroy();
};

//code for copy
Node *List::copy(const Node* src){
    Node* result;
    
    if(src == nullptr)
        result = \_\_\_\_\_\_\_;
    else{
        result = \_\_\_\_\_\_\_\_;
        \_\_\_\_\_\_\_\_\_ = src->item;
        result->next = copy(\_\_\_\_\_\_\_\_);
    }
    return result;
}

Answer 7

struct Node {
    int item;
    Node *next;
};
class List {
    public:
        List():headM(nullptr){}; // PROMISES: Creates empty list.
        ~List();
        List(const List &rhs);
        void insert(const int& the_item);
        void display();
    private:
        Node *headM;
        Node* copy(const Node* src);
        void destroy();
};

//code for copy
Node *List::copy(const Node* src){
    Node* result;
    
    if(src == nullptr)
        result = nullptr;
    else{
        result = new Node;
        result->item = src->item;
        result->next = copy(src->next);
    }
    return result;
}

Question 8

Complete the function such that
int Search(int key, const int *array, int low, int high);
/* REQUIRES:
* - low refers to the index of the first and high refers to the
index of the last element in array.
* - high > low and low >= 0.
* PROMISES:
* returns the position of an element in array that
* its value matches the value of key. Otherwise if no match
* was found, returns -1
*/

Answer 8

int Search(int key, const int *array, int low, int high){
    if(low == high){
        if(array[low]==key)
            return low;
        else
            return -1;
    }
    int result, mid;
    mid = (high+low)/2;
    
    if(array[mid]<key)
        result = Search(key, array, mid+1, high);
    else
        result = Search(key, array, low, mid);
    return result;
}