Question

Data Structure:

1. Write a program for f(n) = 1^2+2^3+…+n^2. (i^2 = i*i)

2. If you have the following polynomial function

f(n)=a0 +a1 x + a2x2+…+an xn ,

then you are asked to write a program for that, how do you do?

3. Write a function in C++ to sort array A[]. (You can assume that you have 10 elements in the array.)

4. Analyze the following program, tell us what does it do for each location of “???” ( i.e. add your comments for the code ) . boolean func(int Start, int End) ///??? What does the function do

{

int k = (Start + End)/2;

if (Start==End){ // ending state

if(N == A[k-1]) // ??? return true; // ???

else return false; // ??? }

if (N <= A[k-1]) return func(Start, k); // ???

else return func(k+1, End); // ???

return false; } // func

5. Write a program that implements Linked-Lists with function append() and removeHeadNode(). Can you use it for Queues? How?

Answer 1

Sol.

Part 1.

This fuction will compute F(n) where n is the user input value and it is also nth term in series.

#include <bits/stdc++.h>
using namespace std;

void series(int a, int r, int n)
{
int curr_term;
for (int i = 0; i < n; i++) {
curr_term = a * pow(r, i);
cout << curr_term << " ";
}
}
int main()
{
int a = 1; // First number of series
int r = 2; // Common ratio
int n; // N th term
cout<<"Enter Nth term that you want: "<<endl;
cin>>n;
series(a, r, n);
return 0;
}

Part 2.

GIven series is the binomial expension. so to compute the binomial expenesion

nCr = (n!) / ((n-r)! * (r)!) and general term is 

Tr+1 = nCn-rAn-rXr

and binomial coffient is ⁿC_i+1 = ⁿC_i*(n-i)/(i+1)

suppose a = 1 , x = 1 and n = 5

then serires will be 1 5 10 10 5 1

so lets make program for this.

#include <bits/stdc++.h>
using namespace std;

void bio(int A, int X, int n)
{
int nthterm = pow(A, n);
cout << nthterm << " ";
for (int i = 1; i <= n; i++) {
nthterm = nthterm * X * (n - i + 1)/(i * A);
cout << nthterm << " ";
}
}

int main()
{
int a; // Value of constant a
cout<<"Enter value of a: "<<endl;
cin>>a;
int x; // value of x
cout<<"Enter value of x: "<<endl;
cin>>x;
int n = 5; // Power
cout<<"Enter value of n"<<endl;
cin>>n;
bio(a,x,n);
return 0;
}

Part 3.

There are many various algorithm exist to sort the array. here is bubble sort implemetation.

#include<bits/stdc++.h>
using namespace std;

void Sort(int* ar, int n)
{
int i,j;
for (i = 0; i < n-1; i++)
for (j = 0; j < n-i-1; j++)
if (ar[j] > ar[j+1])
swap(ar[j], ar[j+1]);
}
int main()
{
int ar[10] = {0,3,2,5,3,7,4,8,6,8};
int n = sizeof(ar)/sizeof(ar[0]);
Sort(ar, n);
for(int i=0;i<10;i++)
cout<<ar[i]<<" ";
return 0;
}
part 4.

Here is boolean func is the implemetation of binary search to find the target element in the array.

boolean func(int Start, int End){

int k = (Start + End)/2; // finding the middle element of array.

if (Start==End){ // if start reaches at the end of array then enetr to the condition

if(N == A[k-1]) return true;// here N is the target variable and we are comparing it with middle's previous element if match we will return 1 or true to the boolean func
else return false; // if does not match then return false or 0.

if (N <= A[k-1]) return func(Start, k); // if target element N is less then midlle's previous element then we got that target will find in between 0 to k-1 so we call start to k in fuction

else return func(k+1, End); // if target is greater then call k+1 to end in array

return false; } // func
}

part 5 implentation of append and removalheadnode.

class Node

{

    public:

    int data;

    Node *next;

};

void append(Node* head, int new_data)
{
Node* new_node = new Node();
Node *last = *head;
new_node->data = new_data;
new_node->next = NULL;

if (head == NULL)
{
head = new_node;
return;
}
while (last->next != NULL)
last = last->next;
last->next = new_node;
return;
}

part 5. delete head node in list

Node* removeHeadNode(struct Node* head)
{
if (head == NULL)
return NULL;
Node* temp = head;
head = head->next;
  
delete temp;
  
return head;
}