Question

1. An array has an index of [5] at the starting address of 200. It has 3 words per memory cell, determine loc[3],loc[4] and NE. (3 Marks: 1 mark for each)

2. A 2-D array defined as A[10 , 5] requires 4 words of storage space for each element. Calculate the address of A[4,3] given the base address as 250 • If the array is stored in Row-major form • If the array is stored in Column-major form

3. Write a method for the following using the data structure Linked List. void append(Node list1, Node list2) If the list1 is {22, 33, 44, 55} and list2 is {66, 77, 88, 99} then append(list1, list2) will change list1 to {22, 33, 44, 55, 66, 77, 88, 99}. (5 Marks: 1mark for each correct step)

4. Write a method for the following using the data structure Linked List. int sum(Node list) If the list is {25, 45, 65, 85} then sum(list) will return 220. (5 Marks: 1mark for each correct step)

5. Trace the following code showing the contents of the Linked List L after each call L.add(50); L.add(60); L.addFirst(10); L.addLast(100); L.set(1, 20); L.remove(1); L.remove(2); L.removeFirst(); L.removeLast(); (10 Marks: 1 mark for each correct answer) L.addFirst(10);

6. Compare and contrast the following data structures. • Array and Linked List

Answer 1

#include <iostream>

using namespace std;

struct Node {
int data;
Node* next;
};

// only for the 1st Node
void initNode(struct Node *head,int n){
head->data = n;
head->next =NULL;
}

// apending
void addNode(struct Node *head, int n) {
Node *newNode = new Node;
newNode->data = n;
newNode->next = NULL;

Node *cur = head;
while(cur) {
if(cur->next == NULL) {
cur->next = newNode;
return;
}
cur = cur->next;
}
}

void insertFront(struct Node **head, int n) {
Node *newNode = new Node;
newNode->data = n;
newNode->next = *head;
*head = newNode;
}

struct Node *searchNode(struct Node *head, int n) {
Node *cur = head;
while(cur) {
if(cur->data == n) return cur;
cur = cur->next;
}
cout << "No Node " << n << " in list.\n";
}

bool deleteNode(struct Node **head, Node *ptrDel) {
Node *cur = *head;
if(ptrDel == *head) {
*head = cur->next;
delete ptrDel;
return true;
}
  
while(cur) {
if(cur->next == ptrDel) {
cur->next = ptrDel->next;
delete ptrDel;
return true;
}
cur = cur->next;
}
return false;
}

/* reverse the list */
struct Node* reverse(struct Node** head)
{
Node *parent = *head;
Node *me = parent->next;
Node *child = me->next;

/* make parent as tail */
parent->next = NULL;
while(child) {
me->next = parent;
parent = me;
me = child;
child = child->next;
}
me->next = parent;
*head = me;
return *head;
}

/* Creating a copy of a linked list */
void copyLinkedList(struct Node *node, struct Node **pNew)
{
if(node != NULL) {
*pNew = new Node;
(*pNew)->data = node->data;
(*pNew)->next = NULL;
copyLinkedList(node->next, &((*pNew)->next));
}
}

/* Compare two linked list */
/* return value: same(1), different(0) */
int compareLinkedList(struct Node *node1, struct Node *node2)
{
static int flag;

/* both lists are NULL */
if(node1 == NULL && node2 == NULL) {
flag = 1;
}
else {
if(node1 == NULL || node2 == NULL)
flag = 0;
else if(node1->data != node2->data)
flag = 0;
else
compareLinkedList(node1->next, node2->next);
}

return flag;
}

void deleteLinkedList(struct Node **node)
{
struct Node *tmpNode;
while(*node) {
tmpNode = *node;
*node = tmpNode->next;
delete tmpNode;
}
}

void display(struct Node *head) {
Node *list = head;
while(list) {
cout << list->data << " ";
list = list->next;
}
cout << endl;
cout << endl;
}

int main()
{
struct Node *newHead;
struct Node *head = new Node;
  
initNode(head,10);
display(head);

addNode(head,20);
display(head);

addNode(head,30);
display(head);

addNode(head,35);
display(head);

addNode(head,40);
display(head);

insertFront(&head;,5);
display(head);

int numDel = 5;
Node *ptrDelete = searchNode(head,numDel);
if(deleteNode(&head;,ptrDelete))
cout << "Node "<< numDel << " deleted!\n";
display(head);

cout << "The list is reversed\n";
reverse(&head;);
display(head);

cout << "The list is copied\n";
copyLinkedList(head,&newHead;);
display(newHead);

cout << "Comparing the two lists...\n";
cout << "Are the two lists same?\n";
if(compareLinkedList(head,newHead))
cout << "Yes, they are same!\n";
else
cout << "No, they are different!\n";
cout << endl;

numDel = 35;
ptrDelete = searchNode(newHead,numDel);
if(deleteNode(&newHead;,ptrDelete)) {
cout << "Node "<< numDel << " deleted!\n";
cout << "The new list after the delete is\n";
display(newHead);
}
cout << "Comparing the two lists again...\n";
cout << "Are the two lists same?\n";
if(compareLinkedList(head,newHead))
cout << "Yes, they are same!\n";
else
cout << "No, they are different!\n";
  
cout << endl;
cout << "Deleting the copied list\n";
deleteLinkedList(&newHead;);
display(newHead);
return 0;
}