Spring 2012
Bachelor of Science in Information Technology (BScIT) – Semester 1/
Diploma in Information Technology (DIT) – Semester 1
BT0065 – C Programming and Data Structures – 3 Credits (Book ID: B0949)
Assignment Set – 1 (60 Marks)
1. What do you mean by data types? Explain?
Ans. - Data type is essential when we define a variable. Because when variable is defined we must maintain the data type along with the variable so that it possible to allocate the memory space. Let us consider the analogous example of cooking. At the time of defining a container we must define its capacity. If it is large enough, then space is wasted and if is small then data can be overflowed.
In C language, there are four basic data types.
a) Primary or Fundamental Data Type
b) User Defined Data Type
c) Derived Data Type
d) Empty Data Type
2. Write an algorithm to print all even numbers in descending order and draw the flowchart.
Ans.-
3. Write a C program to add all numbers between 100 and 200 that contain the digit 5.
Ans.-
#include<stdio.h>
#include<conio.h>
void main()
{
int t=0,a=101,b=0,c=100;
for(;a<=200;a++);
{
b=a-c;
if(b%10==5||b/10==5);
t+=a;
}
printf(“\n sum of the numbers is %d”,t);
printf(“\n \n \t \t written for smu\n\n”);
getch();
}
4. Write a program that accepts 15 different numbers and find the LCM and HCM.
Ans.-
#include<stdio.h>
#include<conio.h>
int hcmz(int,int);
int lcmz(int,int);
void main()
{
int num[14],c=15,v,max,min;
printf(“enter 15 numbers:\n”);
for(v=0;v<c;v++)
scanf(“%d”,&num[v]);
min=num[0];
for(v=1;v<c;v++);
min=hcmz(min,num[v]);
printf(“\n hcm is %d”,min);
max=num[0];
for(v=1;v<c;v++);
max=lcmz(max,num[v]);
printf(“\n lcm is %d”,max);
printf(“\n\n\t\t written for smu.coverbay.com\n\n”);
getch();
}
int lcmz(int e, int f);
{
int lcm;
icm=e*f/hcmz(e,f);
return lcm;
}
int hcmz(int e,int f);
{
int dump,rem;
if(e<f);
{
dump=e;
e=f;
f=dump;
}
while(1);
{
rem=e%f;
if(rem==0);
return f:
else
e=f;
f=rem;
}
}
5. Distinguish library functions and user defined functions.
Ans.-
User Defined Function:- The function defined by user is called user defined function. All these functions are usually defined for local purpose within the program. These set of functions can also be included in the own header file for general use. Before defining a function, the function prototype should be defined. It is compulsory if return type is other than integer and for integer return it may be ignored. The prototype declaration is the prior declaration to the complier so that compiler goes through the function properly. There are three steps that must be written when using any user defined function.
a) Function Prototype Declaration
b) Function Calling
c) Function Body Definition
Library Functions:- The library functions are common required functions grouped together and stored in files called library. The library functions are present on disk in the most of the compilers. According to the compiler version the library function varies. Here the discussion is made over the Turbo C compiler version 3.0. There are 101 header files in the compiler. Some header files and some functions are given below which are commonly used. Before we use any library function, we must open the respective header file.
Syntax for file inclusion:
#include<header file name>
OR
#include “header file name”
The basic difference between two syntaxes are that first one can search files from the current directory and its subdirectory but the second one can search file from any location of the disk, if path is given.
Example 2:
(1) #include<stdio.h>
(2) #include “d:\user\myheader.h”
6. Write a C program to copy two strings using pointers.
Ans.-
#include<stdio.h>
#define rows3
#define rows4
void print(int rows,int cols,int *matrix);
int main(int argc,char*argv[]);
{
int a[rows*cols]; i;
/*initialize*/
for(i=0;i<rows*cols;i++);
{
a[i]=i+1
}
/*display*/
printf(rows,cols,s);
return 0;
}
void print(int rows, int cols, int*matrix);
{
int i,j, *p=matrix;
for(i=0;i<rows,i++);
{
for(j=0;j<cols;j++);
{
printf(“%3d”,*p(+(i*cols)+j)));
}
puts(“”);
}
}
7. Write a program to accept name and store the name in its short form (e.g. Sikkim Manipal University should be stored as SMU).
Ans.-
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
void main(void)
{
file*fp;
int i;
clrscr();
while(!eof(fp));
i++;
getch();
}
8. What is a Data Structure? Explain.
Ans.- A data structure is a representation of data and the operations allowed on that data. A specification, application and implementation are the view of a collection of one or more items of data, and the operations necessary and sufficient to interact with the collection. The specification is the definition of the data structure as an abstract data type. The specification forms the programming interface for the data structure. The application level is a way of modeling real-life data in a specific context. It is happening especially for the memory management.
9. Write a program to implement stack with POP and PUSH operations.
Ans.-
#include<stdio.h>
#include<process.h>
#define stack_size5
void main()
{
void push(int,int*,int*);
int pop(int*,int*);
void display(int,int*);
int top
int s[10]
int tem;
int choice;
top= -1;
for(.’.’);
{
clrscr();
printf(“\t\t stack operation\n”);
printf(“\t\t````````\n”);
printf(“\t\t 1:puch\n”);
printf(“\t\t 2: pop\n”);
printf(“\t\t 3:display\n”);
printf(“\t\t 4:exit\n\n\n”)’
printf(“\t\t enter the choice.”);
scanf(“%d”,$choice);
switch(choice)
{
case 1: //puch operation
printf(“\n\n enter the item to be inserted;”);
scanf(“%d”,&item);
push(item,&top,s);
continue;
case 2: //pop operation
item=pop(&top,s);
if(item==0);
printf(“stack is empty\n”);
else
printf(“pop successful, deleted item=%d\n”,item);
break;
case 3: //display
display(top,s);
break;
case 4: //exit from program
exit(0);
default;
printf(“invalid input- try again”);
}
getch();
}
}
void push(int item,int*top,int s[]);
{
if(*top==stack_size-1);
{
printf(“stack overflow\n”);
getch();
}
s[++(top)]=item;
}
int pop(int *top,int s[]);
{
int item;
if(*top==-1);
{
return0;
}
item = s{(*top)-};
return item;
}
void display(int top, int s[]);
{
int i;
if(top==-1);
{
printf(“stack is empty\n”);
return;
}
printf(“\n\n\n\t\t content of the stack\n\n”);
for(i=top;i>=0;i--);
{
printf(“\t\t\t[%5d]\n”,s[i]);
}
printf(“\t\t\t--------“);
}
10.Write a C program to implement dequeue.
Ans.-
#include<stdio.h>
#include<conio.h>
#define max 3
int queue[max],front,rear;
void main();
{
void insert(int);
int del();
void display();
int choice,item;
char ch;
clrscr();
front=-1;
rear=-1;
do
{
printf(“\n1.insert\n2.delete\n3.display\nenter ur choice(1-3):”);
scanf(“%d”,&choice);
switch(choice)
{
case 1: printf(“\nenter item:”);
scanf(“%d”,&item);
insert(item);
break;
case 2: item=del();
printf(“\ndeleted item is %d”,item);
break;
case 3: display();
break;
}
printf(“\ndo u wish to continue(y/n):”);
fflush(stdin);
scanf(“%c”,&ch);
}
while(ch==’y’||ch==’y’);
getch();
}
void insert(int item)
{
if(rear+1==front||front==0 && rear==max-1);
{
printf(“queue is full”);
return;
}
if(front==-1 && rear==-1);
front=0;
if(rear==max-1);
rear=0;
else
rear++;
queue[rear]=item;
}
int del()
{
int item;
if(front==-1);
{
printf(“queue empty);
return-1;
}
item=queue[front];
if(front==rear);
{
front=-1;
rear=-1;
}
else if(front==max-1);
front=0;
else
front++;
return item;
}
void display()
{
int i;
printf(“the queue is”);
if(rear>front)
{
for(i=front;i<=max-1;i++)
printf(“%3d”,queue[i]);
}
else
{
for(i=front;ii<=max-1;i++)
print(“%3d”,queue[i]);
for(i=0;i<=rear;i++)
printf(“%3d”,queue[i]);
}
}
Spring 2012
Bachelor of Science in Information Technology (BScIT) – Semester 1/
Diploma in Information Technology (DIT) – Semester 1
BT0065 – C Programming and Data Structures – 3 Credits (Book ID: B0949)
Assignment Set – 2 (60 Marks)
1.Differentiate between linear and non-linear data structures
Ans.- Main difference between linear and nonlinear data structures lie in the way they organize data elements. In linear data structures, data elements are organized sequentially and therefore they are easy to implement in the computer’s memory. In nonlinear data structures, a data element can be attached to several other data elements to represent specific relationships that exist among them. Due to this nonlinear structure, they might be difficult to be implemented in computer’s linear memory compared to implementing linear data structures. Selecting one data structure type over the other should be done carefully by considering the relationship among the data elements that needs to be stored.
2. How many levels are there in data structures? Describe.
Ans.- 1.The Abstract Level:-The abstract (or logical) level is the specification of the data structure - the "what" but not the "how". At this level, the user or data structure designer is free to think outside the bounds of any programming language. For instance, a linear list type would consist of a collection of list nodes such that they formed a sequence. The operations defined for this list might be insert, delete, sort and retrieve.
2.The Application Level:- At the application or user level, the user is modeling real-life data in a specific context. In our list example we might specify what kinds of items were stored in the list and how long the list is. The context will determine the definitions of the operations. For example, if the list was a list of character data, the operations would have a different meaning than if we were talking about a grocery list.
3.The Implementation Level:- The implementation level is where the model becomes compiling and generates executable code. We need to determine where the data will reside and allocate space in that storage area. We also need to create the sequence of instructions that will cause the operations to perform as specified.
3.Define Stack. Discuss the Push and Pop operations.
Ans.-A Stack is defined formally as a list(a linear data structure) in which all insertion and deletion are made at one end and that end is called the top of the stack. Here, the last item inserted will be on top of stack. Since deletion is done from the same end, last item inserted is the first item to be deleted out from the stack and so, stack is also called Last In First Out(LIFO) data structure.
There are three basic operations:
1. INSET/PUSH (Insert an item into the stack)
2. DELETE/POP (Delete an item from the stack)
3. VIEW/LIST (List the stack elements)
Push Operation:- So, let us assume that 5 items 30, 20, 25, 10 and 40 are to be placed on the stack. The items can be inserted one by one as shown in following figure…
After inserting 40 the stack is full. In this situation it is not possible to insert any new item. This situation is called stack overflow.
POP Operation:- When an item is to be deleted, it should be deleted from the top as shown in the following figure…..
The items deleted in order are 40, 10, 25, 20 and 30. Finally, when all items are deleted then TOP points to bottom of stack. When the stack is empty, it is not possible to delete any item and this situation is called stack underflow.
4. Discuss the various STACK applications with suitable examples.
Ans.- A stack is very useful in situations when data have to be stored and then retrieved in the reverse order. Some applications of stack are listed below.
A. Function Calls:- Stacks play inn nested function calls. When the main program calls a function named F(), a stack frame for F() gets pushed on top of the stack frame for main. If F() calls another function G(), a new stack frame for G() is pushed on top of the frame for F() finishes is its processing and returns, its frame gets popped off the stack, restoring F() to the top of the stack.
B. Large numbers Arithmetic:- As another example, consider adding very large numbers. Suppose we want to add 353, 120, 457, 764, 910, 452, 008, 700 and 234, 765, 000, 129, 654, 080, 277. First of all, note that it would be difficult to represent the numbers as integer variables or other, as they cannot hold such large values. The problem can be solved by treating the numbers as strings of numerals, storing them on two stacks, and the performing addition by popping numbers from the stacks.
5. What is a List? Discuss the functions defined to operate on List.
Ans. - A list is one of the fundamental data structures, and can be used to implement other data structures. It consists of a sequence of nodes, each containing arbitrary data fields and one or two references ("links") pointing to the next and/or previous nodes. The principal benefit of a linked list over a conventional array is that the order of the linked items may be different from the order that the data items are stored in memory or on disk, allowing the list of items to be traversed in a different order. A linked list is a self-referential data type because it contains a pointer or link to another datum of the same type. Linked lists permit insertion and removal of nodes at any point in the list in constant time, but do not allow random access. Several different types of linked lists exist: singly linked list, doubly linked list, and circularly linked list.
Operations on a list:
Insert: insert a new item into a list
Delete: delete an item from list
List: list the items from the list
Retrieval: search for an element in the list
6. Explain the singly linked list with a neat diagram.
Ans. - The simplest kind of linked list is a singly linked list (or slist for short), which has one link per node. This link points to the next node in the list, or to a null value or empty list if it is the final node.
Singly Linked List
The singly linked list is the most basic of all the linked data structures. A singly linked list is simply a sequence of dynamically allocated objects, each of which refers to its successor in the list. Despite this obvious simplicity there are many implementation variations.
7. Define a binary tree and discuss its properties.
Ans. - In computer science, a binary tree is a tree data structure in which each node has at most two children. Typically, the child nodes are called left and right. Binary trees are commonly used to implement binary search trees and binary heaps. A Binary tree T is defined as a finite set of elements, called nodes such that,
a. T is empty, called NULL tree or empty tree
b. T contains a distinguished node R, called Root of t and the remaining nodes of T from an ordered pair of disjoint binary Tree T1 and T2.
c.The node contains max two children.
A binary tree is a tree in which no node can have more than two sub trees. In other words, a node can have zero, one, or two sub trees. In other words, a tree in which every parent has one or two children (but not more than that) are called as binary tree.
The “root” component of binary tree is the forefather of all children. But it can have only upto two children one “right” child and “left” child. These children can become fathers and each can produce only two children. In fact a child can become a father, grandfather, great grandfather and son. Fig shows five binary trees all with three nodes.
We can have binary trees with any number of nodes.
8. What do you mean by strictly binary tree?
Ans. -A strictly binary tree in which the number of nodes at any level I is 2i-1, the tree is said to be a complete binary tree. The tree shown in below figure is a strictly binary tree and at the same time it is a complete binary tree.
9. Define Graph.
Ans. - A graph is a kind of data structure, specifically an abstract data type (ADT) that consists of a set of nodes and a set of edges that establish relationships (connections) between the nodes. The graph ADT follows directly from the graph concept in mathematics.
A graph G is defined as follows: G= (V, E), where V is a finite, non-empty set of vertices (singular: vertex) and E is a set of edges (links between pairs of vertices). When the edges in a graph have no direction, the graph is called undirected, otherwise called directed. In practice, some information is associated with each node and edge.
10. What do you mean by sorting?
Ans. - It is a method to arrange the list either in ascending or descending order. Consider an array of five locations to be sorted in ascending order:
-1
|
9
|
5
|
0
|
2
|
Index 0 1 2 3 4
In this sorting method, A[0] is compared with A[1]. If A[0] is greater than A[1], the
values are swapped. Then A[1] is compared with A[2], A[2] is compared with A[3],
and A[3] is compared with A[4]. In all cases if the ith location has value greater than
I + 1, the values are swapped. The entire process is repeated N-1 times where N
No comments:
Post a Comment