FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

THE OXFORD COLLEGE OF ENGINEERING

Hosur Road, Bommanahalli, Bengalore-560068

DEPARTMENT OF INFORMATION SCIENCE AND ENGINEERING

LABORATORY MANUAL [2018SCHEME]

[UPDATED 2020-2021]

SUBJECT NAME & CODE : FILE STRUCTURES LABORATORY WITH MINI

PROJECT (18ISL67)

SCHEME – B.E (ISE) : 2018 SCHEME

SEMESTER : VI-B

FACULTY INCHARGES :

1) MS. Madhusmita Mishra, Asst. Professor, ISE

HOD-ISE

The Oxford college of Engineering Page 1

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

DEPARTMENT OF INFORMATION SCIENCE AND

ENGINEERING

Mission
“The department aims to develop the best information science professionals who work
creatively, communicate effectively and become technologically competent, also to mould them
into good citizens by inculcating sense of ethical values in them”

Vision
“To meet the educational, research and service needs of the region through collaboration with academic
and technical institutions, business and government agencies and cultural organizations, thereby
providing a platform that encourages students and staff to continue their intellectual and professional
growth”

The Oxford college of Engineering Page 2

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

FILE STRUCTURES LABORATORY WITH MINI PROJECT

[As per Choice Based Credit System (CBCS) scheme]
(Effective from the academic year 2016 -2017)
SEMESTER – VI
Subject Code 15ISL68 IA Marks 20

Number of Lecture Hours/Week 01I + 02P Exam Marks 80

Total Number of Lecture Hours 40 Exam Hours 03

CREDITS – 02
Course objectives: This course will enable students to
· Apply the concepts of Unix IPC to implement a given function.
· Measure the performance of different file structures
· Write a program to manage operations on given file system.
· Demonstrate hashing and indexing techniques
Description (If any):
Design, develop, and implement the following programs
Lab Experiments:
PART A
1. Write a program to read series of names, one per line, from standard input and
write these names spelled in reverse order to the standard output using I/O
redirection and pipes. Repeat the exercise using an input file specified by the user
instead of the standard input and using an output file specified by the user instead
of the standard output.
2. Write a program to read and write student objects with fixed-length records and
the fields delimited by “|”. Implement pack ( ), unpack ( ), modify ( ) and search ( )
methods.
3. Write a program to read and write student objects with Variable - Length records
using any suitable record structure. Implement pack ( ), unpack ( ), modify ( ) and
search ( ) methods.
4. Write a program to write student objects with Variable - Length records using any

The Oxford college of Engineering Page 3

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

suitable record structure and to read from this file a student record using RRN.
5. Write a program to implement simple index on primary key for a file of student
objects. Implement add ( ), search ( ), delete ( ) using the index.
6. Write a program to implement index on secondary key, the name, for a file of
student objects. Implement add ( ), search ( ), delete ( ) using the secondary index.
7. Write a program to read two lists of names and then match the names in the two
lists using Consequential Match based on a single loop. Output the names
common to both the lists.
8. Write a program to read k Lists of names and merge them using k-way merge
algorithm with k = 8.
Part B --- Mini project:

Student should develop mini project on the topics mentioned below or similar applications
Document processing, transaction management, indexing and hashing, buffer
management, configuration management. Not limited to these.

Course outcomes: The students should be able to:

· Implement operations related to files
· Apply the concepts of file system to produce the given application.
· Evaluate performance of various file systems on given parameters.
Conduction of Practical Examination:
1. All laboratory experiments from part A are to be included for practical
examination.
2. Mini project has to be evaluated for 30 Marks as per 6(b).
3. Report should be prepared in a standard format prescribed for project work.
4. Students are allowed to pick one experiment from the lot.
5. Strictly follow the instructions as printed on the cover page of answer script.
6. Marks distribution:
a) Part A: Procedure + Conduction + Viva:10 + 35 +5 =50 Marks
b) Part B: Demonstration + Report + Viva voce = 15+10+05 = 30 Marks
7. Change of experiment is allowed only once and marks allotted to the procedure
part to be made zero.

The Oxford college of Engineering Page 4

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

TABLE OF CONTENTS
Page
Sl.No Name of the experiment
No

I. PART-A

1 Write a C++ program to read series of names, one per line, from standard input 6
and write these names spelled in reverse order to the standard output using I/O
redirection and pipes. Repeat the exercise using an input file specified by the
user instead of the standard input and using an output file specified by the user
instead of the standard output.

2 Write a C++ program to read and write student objects with fixed-length records 8
and the fields delimited by “|”. Implement pack ( ), unpack ( ), modify ( ) and
search ( ) methods.

3 Write a C++ program to read and write student objects with Variable - Length 14
records using any suitable record structure. Implement pack ( ), unpack ( ),
modify ( ) and search( ) methods

4 Write a C++ program to write student objects with Variable - Length records 18
using any suitable record structure and to read from this file a student record
using RRN

5 Write a C++ program to implement simple index on primary key for a file of 23
student objects. Implement add ( ), search ( ), delete ( ) using the index

6 Write a C++ program to implement index on secondary key, the name, for a 29
file of student objects. Implement add ( ), search ( ), delete ( ) using the
secondary index

7 Write a C++ program to read two lists of names and then match the names in 35
the two lists using Cosequential Match based on a single loop. Output the names
common to both the lists.

8 Write a C++ program to read k Lists of names and merge them using k-way 39
merge algorithm with k = 8.

II.PART-B

1 Mini Project-: Mini project should base on the topics mentioned below or 42
similar applications Document processing, transaction management,
indexing and hashing, buffer management, configuration management.

The Oxford college of Engineering Page 5

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

III.EXTRA PROGRAMS

1. Write a C++ program to implement B-Tree for a given set of integers and its 43
operations insert ( ) and search ( ). Display the tree

2. Write a C++ program to implement B+ tree for a given set of integers and its 46
operations insert ( ), and search ( ). Display the tree

3. Write a C program to implement Hashing with double hashing technique with 56

operations insert ( ) and display ( ) and rehash (). Display the table.

IV. VIVA QUESTIONS AND ANSWERS 65

V. REFERENCES 67

The Oxford college of Engineering Page 6

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

I.PART-A
1. Write a C++ program to read series of names, one per line, from standard input and
write these names spelled in reverse order to the standard output using I/O
redirection and pipes.Repeat the exercise using an input file specified by the user
instead of the standard input and using an output file specified by the user instead
of the standard output.

AIM: The aim of this program is to read some names from standard input device like keyboard
and reverse the names and display them on standard output device like monitor. Repeat the
same by reading the names from a file, reverse them and write the reversed names onto an
new file.
Concepts-
Keywords: I/O redirection, Pipes
I/O redirection: There are always three default files open, stdin (the keyboard), stdout (the
screen), and stderr (error messages output to the screen). These, and any other open files,
can be redirected. Redirection simply means capturing output from a file,
command,program, script, or even code block within a script and sending it as input to
another file,command, program or script.
Pipes: A pipe is nothing but a temporary storage place where the output of one command is
stored and then passed as the input for second command. Pipes are used to run more than
two commands (multiple commands) from same command line.

PROGRAM

#include<iostream>
#include<string>
#include<fstream>
#include<stdlib.h>
using namespace std;
int main()
{
char s1[25];
fstream file1,file2;
int i=0,j=0,x=0,c=0,ch=0,f=0,r=0;
char fname1[25],fname2[25];
for(;;)
{
cout<<"\n1. for standard input and output \n2. input from file and output to file \n3. exit enter ur
choice";
cin>>ch;
switch(ch)
{

The Oxford college of Engineering Page 7

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

case 1: cout<<"enter the number of names\n";

cin>>c;
for(j=1;j<=c;j++)
{
cout<<"enter the name"<<j<<":";
cin>>s1;
x=strlen(s1);
cout<<"the name in reverse is "<<j<<":";
for(i=x-1;i>=0;i--)
cout<<s1[i];
}
break;
case 2:
cout<<"enter the fname to read";
cin>>fname1;
cout<<"enter the reverse data filename";
cin>>fname2;
file1.open(fname1,ios::in);
file2.open(fname2,ios::out);
while(1)
{
file1.getline(s1,25);
if(file1.fail())
break;
x=strlen(s1);
for(i=x;i>=0;i--)
file2<<s1[i];
file2<<endl;
}
file1.close();
file2.close();
break;
default:exit(0);
}
}
return 1;
}

OUTPUT:

press 1. for standard input and output

press 2. input from file and output to file
presss 3. exit enter ur choice1
enter the number of names
3
enter the name1:prathi

The Oxford college of Engineering Page 8

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

the name in reverse is 1:ihtarpenter the name2:pani

the name in reverse is 2:inapenter the name3:this
the name in reverse is 3:siht
press 1. for standard input and output
press 2. input from file and output to file
presss 3. exit enter ur choice2
enter the fname to readfname1.txt
enter the reverse data filenamefname2.txt

press 1. for standard input and output

press 2. input from file and output to file
presss 3. exit enter ur choice3
[root@localhost ~]# cat fname2.txt
ahbihtarp
ilajna
ihtawhsa
[root@localhost ~]# cat 1.txt |wc
4 3 23
[root@localhost ~]# cat 1.txt |sort

Photography
Prash
Sam

2. Write a C++ program to read and write student objects with fixed-length records and
the
fields delimited by “|”. Implement pack( ), unpack ( ), modify ( ) and search ( ) methods.

Aim: The aim of this problem is to create a text file to store student information using fixed
length record where fields of the record is delimited by ‘|’ and to implement the functions
search( ) and modify( ) on these records.
Concepts:
Keywords: Fixed length record, field, delimiter
Fixed length records: A data file that contains data records of equal and constant length. All
records in the file are the same size. Each field will have a predetermined and unchanging
size, set when the record layout is designed, and the sum of the field sizes will add up to the
record size. If the data stored in a given field contains fewer characters than the defined
size,the rest of the field will be filled with spaces, or some other special characters.
Fields and delimiter: Fields are the building blocks of records. These are the sections of a record
where information is stored. A delimiter is a sequence of one or more characters used to
specify the boundary between, independent regions in plain text or other data
streams(i.e.between two fields of a record or between two records of a file).

PROGRAM

#include<iostream>

The Oxford college of Engineering Page 9

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

#include<string>
#include<fstream>
#include<stdlib.h> //stlib is a C library, not a C++ library... thus the ".h"
using namespace std;

class student
{
public:
string usn, name, sem;
void enter_data(); //input name usn sem from the user and stores in object
void display_data(); //displays an object(name,usn, sem) to the user
void pack(); //converts an object to a string and writes the string to the record file
void unpack(); //reads 1 line in the record file to a string and converts this string to an
object
void modify(); //accepts new values for name usn and sem from the user
}s[100],temp;
fstream fp;
void search();
/*unpacks all records and searches for particular record... if it is modified... all the records are
again packed*/
void error(int); //displays suitable error messages

int main()
{
int choice;
system("clear"); // == clrscr();

while(1)
{
cout<<"\n1. Insert a Record\n2. Search and modify a record\n3. Exit\nEnter choice:
"<<endl;
cin>>choice;
switch(choice)
{
case 1:
temp.enter_data();
fp.open("in.txt",ios::out|ios::app);
/*ios::out -> open file for writing, ios::app -> append i.e. write //at the end of the file, (existing
matter is not overwritten)*/
if(!fp) //check if file has opened successfully, else display 1st error
error(1);
temp.pack();
fp.close();
break;
case 2:
search();

The Oxford college of Engineering Page 10

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

break;
default: exit(0);
}
}
}
void student::enter_data()
{
cout<<"\nEnter usn: ";
cin>>usn;
cout<<"\nEnter name: ";
cin>>name;
cout<<"\nEnter sem: ";
cin>>sem;
}

void student::pack()
{
string buf = usn + "|" + name + "|" + sem + "|";
if(buf.length() > 45) //if rec length> 45 then we have to reject the record by displaying
2nde error
{ error(2);
return;
}
while(buf.length()<46) //if rec len < 45.. extra bytes is padded
buf += '_';
fp<<buf<<endl;
}
void search()
{
string usn_srch;
int i=0, srch_flag=-1, modify_flag=-1, count;
cout<<"\nEnter the USN of the student to be found: ";
cin>>usn_srch;
fp.open("in.txt",ios::in);
if(!fp)
error(1);
while(fp) //unpack all the records in the file and store in objects
{
s[i].unpack();
i++;
}
fp.close();
count = i;
for(i=0;i<count;i++) //search each of the objects for required usn

The Oxford college of Engineering Page 11

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

{
if(s[i].usn==usn_srch)
{
srch_flag=i;
break;
}
}
if(srch_flag==-1)
{
cout<<"Record Not found!";
return;
}
cout<<"\nRecord Found!\n";
s[srch_flag].display_data();
cout<<"\nDo you wish to modify the Record??\n Press 1. to modify, 0. to Cancel\n";
cin>>modify_flag;
if(modify_flag)
{ s[srch_flag].modify();
fp.open("in.txt",ios::out);
if(!fp)
error(1);
for(i=0;i<count;i++)
s[i].pack();
fp.close();
}

void student::unpack()
{
string seg;
getline(fp,usn,'|');
getline(fp,name,'|');
getline(fp,sem,'|');
getline(fp,seg);
}

void student::display_data()
{
cout<<"\nName: "<<name<<"\nusn: "<<usn<<"\nsem: "<<sem<<endl;
}
void student::modify()
{
int choice;
while(1)
{

The Oxford college of Engineering Page 12

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

cout<<"\nEnter the field to modify:\n 1. name\n 2.usn \n 3.sem \n 4. to exit modification\

n";
cin>>choice;
switch(choice)
{
case 1: cout<<"\nEnter new name: ";
cin>>name;
break;
case 2: cout<<"\nEnter new usn: ";
cin>>usn;
break;
case 3: cout<<"\nEnter new sem: ";
cin>>sem;
break;
default: return;
}
}
}

void error(int error_type)

{
switch(error_type)
{
case 1: cout<<"\nFATAL ERROR!: Unable to open the record File\n";
exit(0);
case 2: cout<<"\n ERROR!: Data exceeds record length\n";
return;
}
}
OUTPUT:
1. Insert a Record
2. Search and modify a record
3. Exit
Enter choice: 1
Enter usn: 23
Enter name: mahesh
Enter sem: 8
1. Insert a Record
2. Search and modify a record
3. Exit
Enter choice: 1
Enter usn: 3
Enter name: vijay
Enter sem: 8
1. Insert a Record
2. Search and modify a record

The Oxford college of Engineering Page 13

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

3. Exit
Enter choice: 2
Enter the USN of the student to be found: 3
Record Found!
Name: vijay
usn: 3
sem: 8
Do you wish to modify the Record??
Press 1. to modify, 0. to Cancel1
Enter the field to modify:
1. name
2.usn
3.sem
4. to exit modification1
Enter new name: harish
Enter the field to modify:
1. name
2.usn
3.sem
4. to exit modification3
Enter new sem: 7
Enter the field to modify:
1. name
2.usn
3.sem
4. to exit modification4
1. Insert a Record
2. Search and modify a record
3. Exit
Enter choice: 2
Enter the USN of the student to be found: 3
Record Found!
Name: harish
usn: 3
sem: 7
Do you wish to modify the Record??
Press 1. to modify, 0. to Cancel0
1. Insert a Record
2. Search and modify a record
3. Exit
Enter choice: 3

The Oxford college of Engineering Page 14

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

3. Write a C++ program to read and write student objects with Variable - Length records
using any suitable record structure. Implement pack(), unpack(), modify() and
search() methods.

Aim: The aim of this problem is to create a text file to store student information using variable
length record where fields of the record is delimited by ‘|’ and to implement the functions
search( ) and modify( ) on these records.

Keywords: Variable length record, field, delimiter

Variable length records: A data file that contains data records of variable length. All records in
the file are of the different size. Each field will have a predetermined size, set when the
record layout is designed, and the sum of the field sizes will add up to the record size. Each
record will have different size depending on the number of characters entered.

PROGRAM

#include<iostream>
#include<string>
#include<fstream>
#include<stdlib.h>
using namespace std;
class student
{
public:
string usn, name, sem;
void enter_data(); //NOTE: all functions except pack() are exactly the same.
void display_data();
void pack();
void unpack();
void modify();
}s[100];
fstream fp;
void search();
void error(int);
int main()
{
int choice;
system("clear");
while(1)
{
cout<<"\n1. Insert a Record\n2. Search and modify a record\n3. Exit\nEnter choice:
"<<endl;
cin>>choice;
switch(choice)

The Oxford college of Engineering Page 15

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

{
case 1:
s[0].enter_data();
fp.open("in2.txt",ios::out|ios::app);
if(!fp)
error(1);
s[0].pack();
fp.close();
break;
case 2:
search();
break;
default: exit(0);
}
}
}
void student::enter_data()
{
cout<<"\nEnter usn: ";
cin>>usn;
cout<<"\nEnter name: ";
cin>>name;
cout<<"\nEnter sem: ";
cin>>sem;
}
void student::pack()
{
string buf = usn + "|" + name + "|" + sem + "|"; //no need of padding and rejecting
fp<<buf<<endl;
}
void search()
{
string usn_srch;
int i=0, srch_flag=-1, modify_flag=-1, count;
cout<<"\nEnter the USN of the student to be found: ";
cin>>usn_srch;
fp.open("in2.txt",ios::in);
if(!fp)
error(1);
while(fp)
{
s[i].unpack();
i++;
}
fp.close();
count = i-1;

The Oxford college of Engineering Page 16

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

for(i=0;i<=count;i++)
{
if(s[i].usn==usn_srch)
{
srch_flag=i;
break;
}
}
if(srch_flag==-1)
{
cout<<"\nRecord Not found!\n";
return;
}
cout<<"\nRecord Found!\n";
s[srch_flag].display_data();
cout<<"\nDo you wish to modify the Record??\n Press 1. to modify, 0. to Cancel\n";
cin>>modify_flag;
if(modify_flag)
{ s[srch_flag].modify();
fp.open("in2.txt",ios::out);
if(!fp)
error(1);
for(i=0;i<count;i++)
s[i].pack();
fp.close();
}
}
void student::unpack()
{
string seg;
getline(fp,usn,'|');
getline(fp,name,'|');
getline(fp,sem,'|');
getline(fp,seg);
}
void student::display_data()
{
cout<<"\nName: "<<name<<"\nusn: "<<usn<<"\nsem: "<<sem<<endl;
}
void student::modify()
{
int choice;
while(1)
{
cout<<"\nEnter the field to modify:\n 1. name\n 2.usn \n 3.sem \n 4. to exit modification\
n";

The Oxford college of Engineering Page 17

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

cin>>choice;
switch(choice)
{
case 1: cout<<"\nEnter new name: ";
cin>>name;
break;
case 2: cout<<"\nEnter new usn: ";
cin>>usn;
break;
case 3: cout<<"\nEnter new sem: ";
cin>>sem;
break;
default: return;
}
}
}
void error(int error_type)
{
switch(error_type)
{
case 1: cout<<"\nFATAL ERROR!: Unable to open the record File\n";
exit(0);
}
}

OUTPUT:

1. Insert a Record
2. Search and modify a record
3. Exit
Enter choice: 1
Enter usn: 3
Enter name: manisha
Enter sem: 7
1. Insert a Record
2. Search and modify a record
3. Exit
Enter choice: 1
Enter usn: 98
Enter name: prathibha
Enter sem: 8
1. Insert a Record
2. Search and modify a record
3. Exit
Enter choice:
2

The Oxford college of Engineering Page 18

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

Enter the USN of the student to be found: 98

Record Found!
Name: prathibha
usn: 98
sem: 8
Do you wish to modify the Record??
Press 1. to modify, 0. to Cancel 1
Enter the field to modify:
1. name
2.usn
3.sem
4. to exit modification
3
Enter new sem: 5
Enter the field to modify:
1. name
2.usn
3.sem
4. to exit modification
2
Enter new usn: 67
Enter the field to modify:
1. name
2.usn
3.sem
4. to exit modification 4
1. Insert a Record
2. Search and modify a record
3. Exit
Enter choice: 3

4. Write a C++ program to write student objects with Variable - Length fields using any
suitable record structure and to read from this file a student record using RRN.
Aim: The aim of this problem is to create a text file to store student information using fixed
length record where fields of a record is delimited by ‘|’ and each of the records will be
addressed by its RRN. We need to implement a function to access a record using its RRN to
reduce the search time.

Keywords: RRN (relative record number)

Relative Record Number (RRN): It’s an integer that is used to represent a fixed length record.
RRN starts with 0 followed by 1,2,3,.... where RRN 0 represent 1st record, RRN 1 represent
2nd record and so on. If length of a record is N and RRN of that record is R then address of
that record is calculated as R * N.

PROGRAM

The Oxford college of Engineering Page 19

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

#include<iostream>
#include<string>
#include<fstream>
#include<stdlib.h>
using namespace std;

class student
{
string usn, name, sem;
public:
void enter_data();
void display_data();
void pack();
void unpack(int); /* in this prog only the required record is unpacked. the "int" argument
is used to specify the position of the required record in the file.*/
}s1;

int rrn[100], cnt = 0;

fstream fp1;

void find_rrn();
void search();
void error(int);

int main()
{
int choice;

system("clear");
fp1.open("record4.txt",ios::out|ios::app);
fp1.close();
find_rrn();

while(1)
{
cout<<"\n1. Insert a record\n2. Search for record using RRN\n3. Exit\n\nEnter Choice : ";
cin>>choice;
switch(choice)
{
case 1:
s1.enter_data();
fp1.open("record4.txt",ios::out|ios::app);
if(!fp1)
error(1);
s1.pack();

The Oxford college of Engineering Page 20

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

fp1.close();
break;
case 2:
search();
break;
default: exit(0);
}
}
}

void find_rrn()
{
int pos;
string seg;
fp1.open("record4.txt",ios::in);
if(!fp1)
error(1);
while(fp1)
{
pos = fp1.tellg();
getline(fp1,seg);
if(seg.length()==0)
continue;
rrn[++cnt] = pos;
}
fp1.close();
}

void student::enter_data()
{
cout<<"\nEnter usn: ";
cin>>usn;
cout<<"\nEnter name: ";
cin>>name;
cout<<"\nEnter sem: ";
cin>>sem;
}

void student::pack()
{
int pos = fp1.tellg();
string buf = usn + "|" + name + "|" + sem + "|";
fp1<<buf<<endl;
rrn[++cnt] = pos;
}

The Oxford college of Engineering Page 21

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

void search()
{
int rrn_srch, pos;
cout<<"\nEnter the RRN of the record to be found:\n";
cin>>rrn_srch;
if(rrn_srch>cnt||rrn_srch<1)
{ error(2);
return;
}
cout<<"\nRecord Found:\n";
pos = rrn[rrn_srch];
fp1.open("record4.txt", ios::in);
if(!fp1)
error(1);
s1.unpack(pos);
fp1.close();
s1.display_data();
}

void student::unpack(int pos)

{
fp1.seekg(pos, ios::beg);
getline(fp1, usn, '|');
getline(fp1, name, '|');
getline(fp1, sem, '|');
}

void student::display_data()
{
cout<<"\nName: "<<name<<"\nusn: "<<usn<<"\nsem: "<<sem<<endl;
}

void error(int error_type)

{
switch(error_type)
{
case 1: cout<<"\nFATAL ERROR!: Unable to open the record File\n";
exit(0);
case 2: cout<<"\nInvalid RRN\n";
return;
}
}

OUTPUT:
1. Insert a record
2. Search for record using RRN

The Oxford college of Engineering Page 22

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

3. Exit
Enter Choice : 1
Enter usn: 3
Enter name: vijay
Enter sem: 8
1. Insert a record
2. Search for record using RRN
3. Exit
Enter Choice : 1
Enter usn: 7
Enter name: ganga
Enter sem: 9
1. Insert a record
2. Search for record using RRN
3. Exit
Enter Choice : 2
Enter the RRN of the record to be found:
5
Record Found:
Name: kasturi
usn: 2
sem: 4
1. Insert a record
2. Search for record using RRN
3. Exit
Enter Choice : 1
Enter usn: 5
Enter name: kashi
Enter sem: 8
1. Insert a record
2. Search for record using RRN
3. Exit
Enter Choice : 2
Enter the RRN of the record to be found:
8
Record Found:
Name: kashi
usn: 5
sem: 8
1. Insert a record
2. Search for record using RRN
3. Exit
Enter Choice : 3

The Oxford college of Engineering Page 23

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

5. Write a C++ program to implement simple index on primary key for a file of student
objects. Implement add ( ), search ( ), delete ( ) using the index.

Aim: To create a text file with fixed length records or variable length records, an index file with
key(USN) and record address where entire record can be found and to show how indexing is
performed
Key words:
Index table: a table containing key and its address
Primary index: unique key that represents a record in a file
key: an entry in index table which uniquely identifies the record.
Operations performed on index file
1. Create the original empty index and data files
2. Load the index file into memory before using it
3. Rewrite the index file after using it
4. Add data records to the data file
5. Delete records from the data file
6. Update the index file to reflect the changes in the data file

PROGRAM

#include<iostream>
#include<string>
#include<fstream>
#include<stdlib.h>

using namespace std;

class student
{
public:
string usn, name, sem;
void enter_data();
void pack();
}s1;

struct index
{
string usn;
int addr;
}i1[100],temp;

int cnt;
fstream fp;

The Oxford college of Engineering Page 24

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

void create_index();
void sort_index();
void search();
int bin_srch(string);
void del();
void error(int);

int main()
{
int choice;

system("clear");
fp.open("record5.txt",ios::out|ios::app);
fp.close();
create_index();

while(1)
{
cout<<"1. to Add Record\n2. to Search for a record\n3. to delete a record\n4. Exit\n\
nEnter choice : ";
cin>>choice;
switch(choice)
{
case 1:
s1.enter_data();
fp.open("record5.txt",ios::out|ios::app);
if(!fp)
error(1);
s1.pack();
fp.close();
break;
case 2:
search();
break;
case 3:
del();
break;
default:
exit(0);
}
}
}

void create_index()
{

The Oxford college of Engineering Page 25

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

int pos, i;
string seg, usnbuf;
cnt = -1;
fp.open("record5.txt", ios::in);
if(!fp)
error(1);
while(fp)
{
usnbuf.erase();
pos = fp.tellg();
getline(fp, usnbuf, '|');
getline(fp,seg);
if(usnbuf[0] == '*'||usnbuf.length()==0)
continue;
cnt++;
i1[cnt].usn = usnbuf;
i1[cnt].addr = pos;
}
fp.close();
sort_index();
}

void sort_index()
{
for(int i=0; i<=cnt; i++)
{
for(int j=i+1; j<=cnt; j++)
if(i1[i].usn>i1[j].usn)
{
temp.usn = i1[i].usn;
temp.addr = i1[i].addr;

i1[i].usn = i1[j].usn;
i1[i].addr = i1[j].addr;

i1[j].usn = temp.usn;
i1[j].addr = temp.addr;
}
}
}

void student::enter_data()
{
cout<<"\nEnter usn: ";
cin>>usn;
cout<<"\nEnter name: ";

The Oxford college of Engineering Page 26

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

cin>>name;
cout<<"\nEnter sem: ";
cin>>sem;
}
void student::pack()
{
int pos = fp.tellg();
string buf = usn + "|" + name + "|" + sem + "|";
fp<<buf<<endl;
cnt++;
i1[cnt].usn = usn;
i1[cnt].addr = pos;
sort_index();
}
int bin_srch(string usn_srch)
{
int l=0, h = cnt, mid;
while(l<=h)
{
mid = (l+h)/2;
if(i1[mid].usn == usn_srch) {return mid;}
if(i1[mid].usn<usn_srch) l = mid +1;
if(i1[mid].usn>usn_srch) h = mid -1;
}
return -1;
}
void search()
{
string usn_srch, buf;
cout<<"Enter the USN of the student to be found: ";
cin>>usn_srch;
int pos = bin_srch(usn_srch);
if(pos == -1)
{
cout<<"Record Not Found \n";
return;
}
cout<<"Record found\n";
cout<<"Usn|Name|Sem"<<endl;
fp.open("record5.txt",ios::in);
if(!fp)
error(1);
fp.seekg(i1[pos].addr, ios::beg);
getline(fp, buf);
fp.close();
cout<<buf<<endl;

The Oxford college of Engineering Page 27

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

void del()
{
string usn_srch;
cout<<"Enter the USN of the student to be deleted : ";
cin>>usn_srch;
int pos = bin_srch(usn_srch);
if(pos == -1)
{
cout<<"\nRecord Not Found \n";
return;
}
cout<<"\nRecord found and deleted\n";
fp.open("record5.txt",ios::out|ios::in);
fp.seekp(i1[pos].addr, ios::beg);
fp.put('*');
fp.close();

for(int i = pos; i<cnt; i++)

{
i1[i].usn = i1[i+1].usn;
i1[i].addr = i1[i+1].addr;
}
cnt--;
}

void error(int error_type)

{
switch(error_type)
{
case 1: cout<<"\nFATAL ERROR!: Unable to open the record File\n";
exit(0);
}
}

OUTPUT:

1. to Add Record
2. to Search for a record
3. to delete a record
4. Exit

Enter choice : 1
Enter usn: 7

The Oxford college of Engineering Page 28

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

Enter name: iqraa

Enter sem: 6
1. to Add Record
2. to Search for a record
3. to delete a record
4. Exit
Enter choice : 1
Enter usn: 8
Enter name: sanghamesh
Enter sem: 8
1. to Add Record
2. to Search for a record
3. to delete a record
4. Exit
Enter choice : 2
Enter the USN of the student to be found: 8
Record found
Usn|Name|Sem
8|sanghamesh|8|
1. to Add Record
2. to Search for a record
3. to delete a record
4. Exit
Enter choice : 3
Enter the USN of the student to be deleted : 8
Record found and deleted
1. to Add Record
2. to Search for a record
3. to delete a record
4. Exit
Enter choice : 2
Enter the USN of the student to be found: 8
Record Not Found
1. to Add Record
2. to Search for a record
3. to delete a record
4. Exit
Enter choice : 3
Enter the USN of the student to be deleted : 7
Record found and deleted
1. to Add Record
2. to Search for a record
3. to delete a record
4. Exit

Enter choice : 4

The Oxford college of Engineering Page 29

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

6. Write a C++ program to implement index on secondary key, the name, for a file of
student
objects. Implement add ( ), search ( ), delete ( ) using the secondary index.

Aim: To create a text file with fixed length records or variable length records, an index file with
primary key(USN),secondary key(name) and record address where entire student record can
be found and to show how indexing is performed
Key words:
Index: a table containing key and its address
Key: an entry in index table which uniquely identifies the record.
Secondary key: an entry in the index table (not unique, repetition of the key may occur)which
identifies the record.
Operations performed on index file
1. Create the original empty index and data files
2. Load the index file into memory before using it
3. Rewrite the index file after using it
4. Add data records to the data file
5. Delete records from the data file
6. Update the index file to reflect the changes in the data file

PROGRAM

#include<iostream>
#include<string>
#include<fstream>
#include<stdlib.h>

using namespace std;

class student
{
public:
string usn, name, sem;
void enter_data();
void pack();
}s1;
struct sec_index
{
string usn, name;
int addr;
}i2[100], found[20];
int cnt, find_cnt;

fstream fp;
int indexnums[20];

The Oxford college of Engineering Page 30

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

void create_index();
void sort_index();
void search();
void lin_srch(string);
void del();
void error(int);
int main()
{
int choice;
system("clear");
fp.open("record6.txt", ios::out|ios::app);
fp.close();
create_index();
while(1)
{
cout<<"1. to Add Record\n2. to Search for a record\n3. to delete a record\n4. Exit\n\
nEnter choice : ";
cin>>choice;
switch(choice)
{
case 1:
s1.enter_data();
fp.open("record6.txt",ios::out|ios::app);
if(!fp)
error(1);
s1.pack();
fp.close();
break;
case 2:
search();
break;
case 3:
del();
break;
default:
exit(0);
}
}
}
void create_index()
{
int pos, i;
string seg, usnbuf, namebuf;
cnt = -1;
fp.open("record6.txt", ios::in);

The Oxford college of Engineering Page 31

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

if(!fp)
error(1);
while(fp)
{
usnbuf.erase();
namebuf.erase();
pos = fp.tellg();
getline(fp, usnbuf, '|');
getline(fp, namebuf, '|');
getline(fp,seg);
if(usnbuf[0] == '*'||usnbuf.length()==0||namebuf.length()==0)
continue;
cnt++;
i2[cnt].usn = usnbuf;
i2[cnt].name = namebuf;
i2[cnt].addr = pos;
}
fp.close();
sort_index();
}

void sort_index()
{
struct sec_index temp;
for(int i=0; i<=cnt; i++)
{
for(int j=i+1; j<=cnt; j++)
if(i2[i].name>i2[j].name)
{
temp.usn = i2[i].usn;
temp.name = i2[i].name;
temp.addr = i2[i].addr;

i2[i].usn = i2[j].usn;
i2[i].name = i2[j].name;
i2[i].addr = i2[j].addr;

i2[j].usn = temp.usn;
i2[j].name = temp.name;
i2[j].addr = temp.addr;
}
}
}

void student::enter_data()
{

The Oxford college of Engineering Page 32

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

cout<<"\nEnter usn: ";

cin>>usn;
cout<<"\nEnter name: ";
cin>>name;
cout<<"\nEnter sem: ";
cin>>sem;
}

void student::pack()
{
int pos = fp.tellp();
string buf = usn + "|" + name + "|" + sem + "|";
fp<<buf<<endl;
cnt++;
i2[cnt].addr =pos;
i2[cnt].usn = usn;
i2[cnt].name = name;
sort_index();
}

void lin_srch(string name_srch)

{
find_cnt = 0;int j=0;

for(int i = 0; i<=cnt; i++)

{
if(i2[i].name == name_srch)
{
indexnums[j++]=i;
found[find_cnt].usn = i2[i].usn;
found[find_cnt].name = i2[i].name;
found[find_cnt].addr = i2[i].addr;
find_cnt++;
}
}
}
void search()
{
string name_srch, buf;
int ch;
cout<<"\nEnter the Name of The student to be searched : ";
cin>>name_srch;
lin_srch(name_srch);
if(find_cnt == 0)
{
cout<<"\nRecord Not Found!\n";

The Oxford college of Engineering Page 33

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

return;
}
if(find_cnt == 1)
{
cout<<"\n1 Record Found\n";
ch = 0;
}
if(find_cnt>1)
{
cout<<"\nMultiple Records Found!\n";
for(int i = 0; i< find_cnt; i++)
cout<<i<<". Usn = "<<found[i].usn<<endl;
cout<<"\nEnter choice: ";
cin>>ch;if(ch>find_cnt){cout<<"Invalid Range\n\n";return;}
}
cout<<"\nUsn|Name|Sem"<<endl;
fp.open("record6.txt",ios::in);
if(!fp)
error(1);
fp.seekg(found[ch].addr, ios::beg);
getline(fp,buf);
fp.close();
cout<<buf<<endl;
}

void del()
{
string name_srch;
int ch;
cout<<"\nEnter the Name of The student to be deleted : ";
cin>>name_srch;
lin_srch(name_srch);
if(find_cnt == 0)
{
cout<<"\nRecord Not Found!\n";
return;
}
if(find_cnt == 1)
{
cout<<"\n1 Record Found\n";
ch = 0;
}
if(find_cnt>1)
{
cout<<"\nMultiple Records Found!\n";
for(int i = 0; i< find_cnt; i++)

The Oxford college of Engineering Page 34

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

cout<<i<<". "<<found[i].usn<<endl;
cout<<"\nEnter choice: \n";
cin>>ch;if(ch>find_cnt){cout<<"Invalid Range\n\n";return;}
}
cout<<"\nRecord Deleted\n\n";
fp.open("record6.txt",ios::out|ios::in);
if(!fp)
error(1);
fp.seekp(found[ch].addr, ios::beg);
fp.put('*');
fp.close();
for(int i=indexnums[ch]; i<cnt;i++)
{
i2[i].usn = i2[i+1].usn;
i2[i].name = i2[i+1].name;
i2[i].addr = i2[i+1].addr;
}
cnt--;
}

void error(int error_type)

{
switch(error_type)
{
case 1: cout<<"\nFATAL ERROR!: Unable to open the record File\n";
exit(0);
}
}

OUTPUT:
1. to Add Record
2. to Search for a record
3. to delete a record
4. Exit

Enter choice : 1
Enter usn: 2
Enter name: kiran
Enter sem: 8
1. to Add Record
2. to Search for a record
3. to delete a record
4. Exit

Enter choice : 1

The Oxford college of Engineering Page 35

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

Enter usn: 90
Enter name: iqra
Enter sem: 4
1. to Add Record
2. to Search for a record
3. to delete a record
4. Exit
Enter choice : 2
Enter the Name of The student to be searched : iqra
1 Record Found
Usn|Name|Sem
90|iqra|4|
1. to Add Record
2. to Search for a record
3. to delete a record
4. Exit
Enter choice : 3

Enter the Name of The student to be deleted : iqra

1 Record Found

Record Deleted

1. to Add Record
2. to Search for a record
3. to delete a record
4. Exit
Enter choice : 2
Enter the Name of The student to be searched : iqra
Record Not Found!
1. to Add Record
2. to Search for a record
3. to delete a record
4. Exit

7. Write a C++ program to read two lists of names and then match the names in the two
lists using Consequential Match based on a single loop. Output the names common to
both the lists.

AIM: The aim of this program is to read two lists of names from standard input device like
keyboard and using consequential match based on a single loop compare both the list of
names and write the names to a file which are common to both the files and print them on
standard output device like monitor.
Concepts -

The Oxford college of Engineering Page 36

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

Keywords: Co-sequential match

Co-sequential Match: Coordinated processing of two or more sequential lists to produce a single
list.We have at least two lists and they contain names in sorted order. From these two list we
find out the common names and write them to a new file.It contains the match procedure as
given below:
1. Initializing: we need to arrange the things in sorted order such a way that the
procedure gets going properly.
2. Getting and accessing the next list item: we need simple methods that support getting
the next list element and accessing it.
3. Synchronizing: we have to make sure that match will never be missed.
4. Handling end of file conditions: when to get to the end of either of Lists we need to
halt the program.
5. Recognizing errors: when an error occurs in the data, we need to detect it and take
some action.

PROGRAM

#include<iostream>
#include<string>
#include<fstream>
#include<stdlib.h>
using namespace std;
class coseq
{
public:
string list1[100],list2[100];
int count1, count2;
void read_lists();
void sort_lists();
void match_lists();
};
void error(int);

int main()
{
system("clear");
coseq c;
c.read_lists();
c.sort_lists();
cout<<"\n\nCommon Names in Both Lists Are : \n";
c.match_lists();
return 0;
}

void coseq::read_lists()
{

The Oxford college of Engineering Page 37

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

fstream fp;
string name;
count1 = 0; // Initially 0 names in arrays
fp.open("1.txt",ios::in);
if(!fp)
error(1);
while(fp)
{
getline(fp,name); //read from file
list1[count1++]=name; //store in array
}
fp.close();

//Now same thing for the next file.

count2 = 0;
fp.open("2.txt",ios::in);
if(!fp)
error(1);
while(fp)
{
getline(fp,name);
list2[count2++]=name;
}
fp.close();
}

void coseq::sort_lists()
{
int i,j;
string temp;

for(i=0;i<count1;i++)
{
for(j=i+1;j<count1;j++)
{
if(list1[i]>list1[j])
{
temp=list1[i];
list1[i]=list1[j];
list1[j]=temp;
}
}
}

cout<<"\nThe Sorted Contents of List 1 : \n";

for(i=0;i<=count1;i++)

The Oxford college of Engineering Page 38

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

cout<<list1[i]<<"\n";

//Now same thing for the second list.

for(i=0;i<count2;i++)
{
for(j=i+1;j<=count2;j++)
{
if(list2[i]>list2[j])
{
temp=list2[i];
list2[i]=list2[j];
list2[j]=temp;
}
}
}

cout<<"\nThe Sorted Contents of List 2 : \n";

for(i=0;i<=count2;i++)
cout<<list2[i]<<"\n";
}

void coseq::match_lists()
{
int i=0,j=0;
while(i<=count1 && j<=count2)
{
if(list1[i]==list2[j])
{
cout<<list1[i]<<endl;
i++;
j++;
}
if(list1[i]<list2[j])i++;
if(list1[i]>list2[j])j++;
}
}

void error(int error_type)

{
switch(error_type)
{
case 1: cout<<"\nFATAL ERROR!: Unable to open the File(s)\n";
exit(0);
}
}

The Oxford college of Engineering Page 39

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

OUTPUT:

The Sorted Contents of List 1 :

anoop
archana
sam
The Sorted Contents of List 2 :
archana
david
sam
Common Names in Both Lists Are :
archana
sam

8. Write a C++ program to read k Lists of names and merge them using k-way merge
algorithm with k = 8.
Aim: The aim of this program is to read K lists of names from standard input in sorted order in
each list and merge K number of lists in to one sequentially ordered list using K-way Merge
Algorithm and print merged list on standard output device.
Concepts -
Keywords: K-way Merge Algorithm
K-way Merge Algorithm: It is to merge K input lists to create a single sequentially ordered list. It
can be viewed as a process of deciding which two input items has the minimum value,
outputting that item, then moving ahead in the list from which that item is taken. In this we
take all k lists in sorted order.It requires calling a minimum index function to find the index
of item with the minimum collating sequence value and an inner loop that finds all lists that
are using that item. In this we find the minimum and testing to see that in which list the item
occurs and which files therefore need to be read. It works nicely if k value is less than or
equal to 8

PROGRAM

#include<iostream>
#include<string>
#include<fstream>
#include<stdlib.h>
using namespace std;
class coseq
{
public:
string list[8][50];
string outlist[200];
int count1[8],count2[8];
void read_file(int i);
void sort_list(int i);

The Oxford college of Engineering Page 40

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

void kwaymerge();
};
void error(int);
int main()
{
//system("clear");
coseq c;

for(int i=0; i<8; i++) //For each of the k lists read_file and sort_list.

{
c.count1[i] = 0;
c.read_file(i);
c.sort_list(i);

}
c.kwaymerge();
return 0;
}
void coseq::read_file(int i)
{
fstream fp;
string name;
switch(i)
{
case 0:fp.open("n1.txt",ios::in);break;
case 1:fp.open("n2.txt",ios::in);break;
case 2:fp.open("n3.txt",ios::in);break;
case 3:fp.open("n4.txt",ios::in);break;
case 4:fp.open("n5.txt",ios::in);break;
case 5:fp.open("n6.txt",ios::in);break;
case 6:fp.open("n7.txt",ios::in);break;
case 7:fp.open("n8.txt",ios::in);break;
}
if(!fp)
error(1);
while(fp)
{
getline(fp,name);
if(name.length()>0)
list[i][count1[i]++]=name;
}
fp.close();
}
void coseq::sort_list(int k)
{

The Oxford college of Engineering Page 41

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

int i,j;
string temp;
for(i=0;i<count1[k];i++)
{
for(j=i+1;j<count1[k];j++)
{
if(list[k][i]>list[k][j])
{
temp=list[k][i];
list[k][i]=list[k][j];
list[k][j]=temp;
}
}
}
}
void coseq::kwaymerge()
{
string sml;
int s_list,count3=0,strt=0,avail_list=8,avail[8],i;
for(i=0;i<8;i++)
{
avail[i]=1;
count2[i]=0;
}
while(avail_list>1)
{
if(!avail[strt])
{
strt++;
continue;
}
s_list=strt;
sml=list[strt][count2[strt]];
for(i=strt+1;i<8;i++)
{
if(!avail[i])
continue;
if(list[i][count2[i]]<sml)
{
sml=list[i][count2[i]];
s_list=i;
}
}
count2[s_list]++;
if(count2[s_list]==count1[s_list])
{

The Oxford college of Engineering Page 42

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

avail[s_list]=0;
avail_list--;
}
outlist[count3++]=sml;
}
for(i=0;i<8;i++)
if(avail[i])
{
for(int j=count2[i];j<count1[i];j++)
outlist[count3++]=list[i][j];

}
cout<<"\nMerged list:\n";
for(i=0;i<count3;i++)
{
if(outlist[i]==outlist[i+1])continue;
cout<<outlist[i]<<endl;
}
}
void error(int error_type)
{
switch(error_type)
{
case 1: cout<<"\nFATAL ERROR!: Unable to open the File(s)\n";
exit(0);
}
}
OUTPUT:
Merged list:
chitra
jayashree
joyce
prathibha
reeshma
seema
vijay

II.PART-B
MINI PROJECT
The mini project should be developed on the topics mentioned below or similar
applications like Document processing, transaction management, indexing and hashing,
buffer management, configuration management using JAVA or basic programming
languages(C, C++)

The Oxford college of Engineering Page 43

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

APPLICATIONS
DOCUMENT PROCESSING
It involves the conversion of typed and handwritten text on paper-based &
electronic documents (e.g., scanned image of a document) into electronic information
utilizing one of, or a combination of, intelligent character recognition (ICR), optical
character recognition (OCR) and experienced data entry clerks.
TRANSACTION MANAGEMENT
A transaction is a logical unit of work that contains one or more SQL statements. A
transaction is an atomic unit. The effects of all the SQL statements in a transaction can be
either all committed (applied to the database) or all rolled back (undone from the
database).
BUFFER MANAGEMENT
Buffer management is a key component in achieving this efficiency. The buffer
management component consists of two mechanisms: the buffer manager to access and
update database pages, and the buffer cache (also called the buffer pool), to reduce
database file I/O.
CONFIGURATION MANAGEMENT
Configuration management (CM) is a governance and systems engineering process that
ensures the proper accounting of an enterprise's configuration items (CIs) and of the
interrelationship between them in an operational environment. CIs consist of enterprise
devices, hardware and software, and capabilities necessary to deliver services for an
organization.
HASHING
Hashing is the transformation of a string of characters into a usually shorter fixed-length
value or key that represents the original string. Hashing is used to index and retrieve
items in a database because it is faster to find the item using the shorter hashed key than
to find it using the original value.
INDEXING
Indexing is a way to optimize performance of a database by minimizing the number of
disk accesses required when a query is processed.An index or database index is a data

The Oxford college of Engineering Page 44

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

structure which is used to quickly locate and access the data in a database table.
Indexes are created using some database columns.
● The first column is the Search key that contains a copy of the primary key or candidate
key of the table. These values are stored in sorted order so that the corresponding data
can be accessed quickly (Note that the data may or may not be stored in sorted order).
● The second column is the Data Reference which contains a set of pointers holding the
address of the disk block where that particular key value can be found.

III.EXTRA PROGRAMS

1. Write a C++ program to implement B-Tree for a given set of integers and its
operations insert ( ) and search ( ). Display the tree.
PROGRAM:

#include <iostream.h>
#include <fstream.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <math.h>

#define order 4
#define min (int)ceil((float)order/2)

struct node
{ int level;
int usage;
int numbers[order+1];
struct node* children[order+1];
struct node* parent;
};
typedef struct node* NODE;
NODE head=NULL,cur,temp,up,prev,newup;

The Oxford college of Engineering Page 45

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

NODE getnode()
{
NODE temp;
int i;
temp=(NODE)malloc(sizeof(struct node));
if (temp==NULL)
{
cout<< "insuffcient memory\n";
getch(); exit(0);
}
temp->level=0; temp->usage=0;
for(i=0;i<=order;i++)
{
temp->children[i]=NULL;
temp->numbers[i]=999;
}
temp->parent=NULL;
return temp;
}

void display(NODE head)

{
NODE a[100],cur;
int i=0,j=0,k,level;
cur=head;
a[i]=cur;i++;
while(cur->children[0]!=NULL)
{
for(k=0;k<=cur->usage-1;k++)
{
a[i]=cur->children[k];
i++;
}
j++;
cur=a[j];
}
i--;
level=head->level;
for(k=0;k<=i;k++)

The Oxford college of Engineering Page 46

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

{
cur=a[k];
if(level!=cur->level)
{
cout<<"\n";
level=cur->level;
}
for(j=0;j<=cur->usage-1;j++)
{
cout<<cur->numbers[j]<<" ";
}
cout<<"\t";
}
}

void insertnode()
{
int num,i,j,k,poi;
cout << "Enter number to insert into btree..\n";
cin >> num;
if (head == NULL)
{
head=getnode();
head->usage=1;
head->numbers[0]=num;
return;
}
else
{
cur=head;
while (cur != NULL)
{
for(i=0,j=0;i<=(cur->usage)-1;i++)
if (num > cur->numbers[i]) j++;
prev=cur;
if (j == cur->usage) cur=cur->children[j-1];
else cur=cur->children[j];
}
cur=prev;
poi=j;

The Oxford college of Engineering Page 47

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

if (cur->numbers[poi] == num)
{
cout << "Element already present..\n";
return;
}
if (poi != cur->usage)
{
for(i=cur->usage;i>=poi+1;i--)
{
cur->numbers[i]=cur->numbers[i-1];
cur->children[i]=cur->children[i-1];
}
}
cur->numbers[poi]=num;
cur->children[poi]=NULL;
cur->usage++;
while(cur!=NULL)
{
if (cur->usage <= order)
{
if (cur->parent == NULL) break;
up=cur->parent; i=0;
while (up->children[i] != cur) i++;
up->numbers[i]=cur->numbers[(cur->usage)-1];
cur=up;
continue;
}
temp=getnode();
for(k=min,j=0;k<=order;k++,j++)
{
temp->numbers[j]=cur->numbers[k];
cur->numbers[k]=999;
temp->children[j]=cur->children[k];
cur->children[k]=NULL;
}
cur->usage=min;
temp->usage=order-(cur->usage)+1;
temp->level=cur->level;
if (cur->children[0] != NULL)
{

The Oxford college of Engineering Page 48

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

for(i=0;i<=(cur->usage)-1;i++)(cur->children[i])->parent=cur;
for(i=0;i<=(temp->usage)-1;i++)(temp->children[i])->parent=temp;
}
if (cur->parent == NULL)
{
up=getnode();
up->level=(cur->level)+1;
up->usage=2;
up->numbers[0]=cur->numbers[(cur->usage)-1];
up->numbers[1]=temp->numbers[(temp->usage)-1];
up->children[0]=cur;
up->children[1]=temp;
cur->parent = temp->parent = up;
head=up;
return;
}
else
{
up=cur->parent;
temp->parent=up;
newup=getnode();
i=0;
while (up->numbers[i] < cur->numbers[0])
{
newup->numbers[i] = up->numbers[i];
newup->children[i] = up->children[i];
i++;
}
newup->numbers[i]= cur->numbers[(cur->usage)-1];
newup->children[i] = cur;
i++;
newup->numbers[i]= temp->numbers[(temp->usage)-1];
newup->children[i] = temp;
i++;
j=0;
while (up->numbers[j] <= temp->numbers[(temp->usage)-1]) j++;
while (j <= (up->usage)-1)
{
newup->numbers[i] = up->numbers[j];
newup->children[i] = up->children[j];

The Oxford college of Engineering Page 49

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

i++,j++;
}
up->usage=i;
newup->usage=i;
for(i=0;i<=(newup->usage)-1;i++)
{
up->numbers[i] = newup->numbers[i];
up->children[i] = newup->children[i];
}
free(newup);
cur=up;
continue;
}
}
}
}

void searchnode()
{
int num,i,j,poi;
cout << "Enter number to search : \n";
cin >> num;
cur=head;
while (cur != NULL)
{
for(i=0,j=0;i<=(cur->usage)-1;i++)
if (num > cur->numbers[i]) j++ ;
prev=cur;
if (j == cur->usage) cur=cur->children[j-1];
else cur=cur->children[j];
}
cur=prev;
poi=j;
if (cur->numbers[poi] == num) cout << "Search success..\n";
else cout << "search failure\n";
}

void main()
{
int ch;

The Oxford college of Engineering Page 50

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

for(;;)
{ cout << "1:Insert 2:Search 3:Displaytree 4:Exit\nEnter choice : ";
cin >> ch;
switch(ch)
{
case 1 : insertnode(); break;
case 2 : searchnode(); break;
case 3 : display(head); break;
default: exit(0);
}
}
}
OUTPUT

1. Insert 2. Search 3. Display 4. Exit

Enter the choice : 1
Enter the number : 10
Enter the choice : 1
Enter the number : 20
Enter the choice : 1
Enter the number : 9
1. Insert 2. Search 3. Display 4. Exit
Enter the choice : 2
Enter the number to be searched: 20
Search success.

1. Insert 2. Search 3. Display 4. Exit

Enter the choice : 3
9 10 20

2. Write a C++ program to implement B+ tree for a given set of integers and its operations
insert ( ), and search ( ). Display the tree.

PROGRAM:

#include <iostream.h>
#include <fstream.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

The Oxford college of Engineering Page 51

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

#include <math.h>
#define order 3
#define min (int)ceil((float)order/2)
struct node
{ int level;
int usage;
int numbers[order+1];
struct node* children[order+1];
struct node* parent;
struct node * right;
};
typedef struct node* NODE;
NODE head=NULL,cur,temp,up,prev,newup,first,temp1,temp2;

NODE getnode()
{ NODE temp;
int i;
temp=(NODE)malloc(sizeof(struct node));
if (temp==NULL)
{ cout<< "insuffcient memory\n";
getch(); exit(0);
}
temp->level=0; temp->usage=0;
for(i=0;i<=order;i++)
{ temp->children[i]=NULL;
temp->numbers[i]=999;
}
temp->parent=NULL;
temp->right=NULL;
return temp;
}

void display(NODE head)

{ NODE a[100],cur;
int i=0,j=0,k,level;
cur=head;
a[i]=cur;i++;

while(cur->children[0]!=NULL)

The Oxford college of Engineering Page 52

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

{
for(k=0;k<=cur->usage-1;k++)
{
a[i]=cur->children[k];
i++;
}
j++;
cur=a[j];
}
i--;
level=head->level;
for(k=0;k<=i;k++)
{
cur=a[k];
if(level!=cur->level)
{
cout<<"\n";
level=cur->level;
}
for(j=0;j<=cur->usage-1;j++)
{
cout<<cur->numbers[j]<<" ";
}
cout<<"\t";
}
}
void insertnode()
{

int num,i,j,k,poi;
cout << "enter number to insert into btree\n";
cin >> num;
if (head == NULL)
{ head=getnode();
head->usage=1;
head->numbers[0]=num;
first=head;
return;
}
else

The Oxford college of Engineering Page 53

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

{ cur=head;
while (cur != NULL)
{ for(i=0,j=0;i<=(cur->usage)-1;i++)
if (num > cur->numbers[i]) j++ ;
prev=cur;
if (j == cur->usage) cur=cur->children[j-1];
else cur=cur->children[j];
}
cur=prev;
poi=j;
if (cur->numbers[poi] == num)
{ cout << "element already present\n";
return;
}
if (poi != cur->usage)
{ for(i=cur->usage;i>=poi+1;i--)
{ cur->numbers[i]=cur->numbers[i-1];
cur->children[i]=cur->children[i-1];
}
}
cur->numbers[poi]=num;
cur->children[poi]=NULL;
cur->usage++;

while(cur!=NULL)
{ if (cur->usage <= order)
{ if (cur->parent == NULL) break;

up=cur->parent; i=0;
while (up->children[i] != cur) i++;
up->numbers[i]=cur->numbers[(cur->usage)-1];

cur=up;
continue;
}

temp=getnode();
for(k=min,j=0;k<=order;k++,j++)
{ temp->numbers[j]=cur->numbers[k];
cur->numbers[k]=999;

The Oxford college of Engineering Page 54

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

temp->children[j]=cur->children[k];
cur->children[k]=NULL;
}

cur->usage=min;
temp->usage=order-(cur->usage)+1;
temp->level=cur->level;

if (cur->children[0] != NULL)
{for(i=0;i<=(cur->usage)-1;i++)(cur->children[i])->parent=cur;
for(i=0;i<=(temp->usage)-1;i++)(temp->children[i])->parent=temp;
}
if(cur->level==0)
{
/*temp1=first;
while(temp1->right!=NULL && temp != cur)
{
temp1=temp1->right;
}
temp2=temp1->right;
temp1->right=temp;
temp->right=temp2;
temp1=cur*/;
temp1=cur->right;
cur->right=temp;
temp->right=temp1;
}

if (cur->parent == NULL)
{ up=getnode();
up->level=(cur->level)+1;
up->usage=2;
up->numbers[0]=cur->numbers[(cur->usage)-1];
up->numbers[1]=temp->numbers[(temp->usage)-1];
up->children[0]=cur;
up->children[1]=temp;
cur->parent = temp->parent = up;
head=up;
return;
}

The Oxford college of Engineering Page 55

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

else
{ up=cur->parent;
temp->parent=up;
newup=getnode();

i=0;

while (up->numbers[i] < cur->numbers[0])

{ newup->numbers[i] = up->numbers[i];
newup->children[i] = up->children[i];
i++;
}

newup->numbers[i]= cur->numbers[(cur->usage)-1];
newup->children[i] = cur;
i++;
newup->numbers[i]= temp->numbers[(temp->usage)-1];
newup->children[i] = temp;
i++;

j=0;
while (up->numbers[j] <= temp->numbers[(temp->usage)-1]) j++;
while (j <= (up->usage)-1)
{ newup->numbers[i] = up->numbers[j];
newup->children[i] = up->children[j];
i++,j++;
}

up->usage=i;
newup->usage=i;
for(i=0;i<=(newup->usage)-1;i++)
{ up->numbers[i] = newup->numbers[i];
up->children[i] = newup->children[i];
}

free(newup);
cur=up;
continue;
}
}

The Oxford college of Engineering Page 56

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

}
}

void displaylist()
{
temp=first;
while (temp!=NULL)
{
for(int i=0;i<=(temp->usage-1);i++)
{
cout<<temp->numbers[i]<<" ";
}
cout<<"\t";
temp=temp->right;
}
}
void searchnode()

{
int num,i,j,poi;
cout << "enter number to search\n";
cin >> num;
cur=head;
while (cur != NULL)
{ for(i=0,j=0;i<=(cur->usage)-1;i++)
if (num > cur->numbers[i]) j++ ;
prev=cur;
if (j == cur->usage) cur=cur->children[j-1];
else cur=cur->children[j];
}
cur=prev;
poi=j;
if (cur->numbers[poi] == num) cout << "search success\n";
else cout << "search failure\n";
}

void main()
{
int ch;

The Oxford college of Engineering Page 57

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

// clrscr();
for(;;)
{ cout << "1:insert 2:search 3:displaytree 4: dispaly list\t 5:exit\nenter choice::::";
cin >> ch;
switch(ch)
{ case 1 :insertnode();
break;
case 2 : searchnode();
break;
case 3 : display(head);
break;
case 4:displaylist();
break;
default: exit(0);

}
}
}

OUTPUT

1. Insert 2. Search 3. Display tree 4. Display list 5. Exit

Enter choice: 1

Enter number to insert into B tree – 10

1. Insert 2. Search 3. Display tree 4. Display list 5. Exit

Enter choice: 1

Enter number to insert into B tree – 20

1. Insert 2. Search 3. Display tree 4. Display list 5. Exit

Enter choice: 3

10 20

1. Insert 2. Search 3. Display tree 4. Display list 5. Exit

Enter choice: 2

Enter the number to search: 30

The Oxford college of Engineering Page 58

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

Search Failure.

1. Insert 2. Search 3. Display tree 4. Display list 5. Exit

Enter choice: 2

Enter the number to search: 10

Search Success.

3. Write a C++ program to implement Hashing with double hashing technique with
operations insert ( ) and display ( ) and rehash (). Display the table.

#include <stdio.h>
#include <stdlib.h>
#define MIN_TABLE_SIZE 5
int i;
enum EntryType {
Legitimate, Empty, Deleted
};
struct HashNode {
int element;
enum EntryType info;
};
struct HashTable {
int size;
struct HashNode *table;
};
int HashFunc1(int key, int size) {
return key % size;
}

int HashFunc2(int key, int size) {

return (key * size - 1) % size;
}
struct HashTable *initializeTable(int size) {
struct HashTable * htable;
if (size < MIN_TABLE_SIZE) {
printf("Table Size Too Small\n");
return NULL;
}
htable = malloc(sizeof(struct HashTable));
if (htable == NULL) {
printf("Out of Space\n");
return NULL;

The Oxford college of Engineering Page 59

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

}
htable->size = size;
htable->table = malloc(sizeof(struct HashNode[htable->size]));
if (htable->table == NULL) {
printf("Table Size Too Small\n");
return NULL;
}
for (i = 0; i < htable->size; i++) {
htable->table[i].info = Empty;
htable->table[i].element = NULL;
}
return htable;
}
/*
 * Function to Find Element from the table
 */
int Find(int key, struct HashTable *htable) {
int hashVal = HashFunc1(key, htable->size);
int stepSize = HashFunc2(key, htable->size);
while (htable->table[hashVal].info != Empty
&& htable->table[hashVal].element != key) {
hashVal = hashVal + stepSize;
hashVal = hashVal % htable->size;
}
return hashVal;
}
/*
* Function to Insert Element into the table
 */
void Insert(int key, struct HashTable *htable) {
int pos = Find(key, htable);
if (htable->table[pos].info != Legitimate) {
htable->table[pos].info = Legitimate;
htable->table[pos].element = key;
}
}
/*
 * Function to Rehash the table
 */
struct HashTable *Rehash(struct HashTable *htable) {
int size = htable->size;
struct HashNode *table = htable->table;
htable = initializeTable(2 * size);
for (i = 0; i < size; i++) {
if (table[i].info == Legitimate)
Insert(table[i].element, htable);

The Oxford college of Engineering Page 60

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

}
free(table);
return htable;
}
/*
 * Function to Retrieve the table
 */
void Retrieve(struct HashTable *htable) {
for (i = 0; i < htable->size; i++) {
int value = htable->table[i].element;
if (!value)
printf("Position: %d Element: Null\n", (i + 1));
else
printf("Position: %d Element: %d\n", (i + 1), value);
}
}
/*
 * Main Contains Menu
 */
int main() {
int value, size, pos, i = 1;
int choice;
struct HashTable * htable;
while (1) {
printf("\n----------------------\n");
printf("Operations on Double Hashing\n");
printf("\n----------------------\n");
printf("1.Initialize size of the table\n");
printf("2.Insert element into the table\n");
printf("3.Display Hash Table\n");
printf("4.Rehash The Table\n");
printf("5.Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter size of the Hash Table: ");
scanf("%d", &size);
htable = initializeTable(size);
break;
case 2:
if (i > htable->size) {
printf("Table is Full, Rehash the table\n");
continue;
}
printf("Enter element to be inserted: ");

The Oxford college of Engineering Page 61

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

scanf("%d", &value);
Insert(value, htable);
i++;
break;
case 3:
Retrieve(htable);
break;
case 4:
htable = Rehash(htable);
break;
case 5:
exit(0);
default:
printf("\nEnter correct option\n");
}
}
return 0;
}

Output:

----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 1
Enter size of the Hash Table: 3
Table Size Too Small
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 1
Enter size of the Hash Table: 5
 

The Oxford college of Engineering Page 62

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 3
Position: 1 Element: Null
Position: 2 Element: Null
Position: 3 Element: Null
Position: 4 Element: Null
Position: 5 Element: Null
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 10
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 20
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table

The Oxford college of Engineering Page 63

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

3.Display Hash Table

4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 30
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 40
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 50
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Table is Full, Rehash the table
 
----------------------
Operations on Double Hashing
 
----------------------

The Oxford college of Engineering Page 64

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

1.Initialize size of the table

2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 3
Position: 1 Element: 10
Position: 2 Element: 50
Position: 3 Element: 40
Position: 4 Element: 30
Position: 5 Element: 20
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 4
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 3
Position: 1 Element: 10
Position: 2 Element: Null
Position: 3 Element: Null
Position: 4 Element: Null
Position: 5 Element: Null
Position: 6 Element: Null
Position: 7 Element: 30
Position: 8 Element: 50
Position: 9 Element: 40
Position: 10 Element:20
 
----------------------
Operations on Double Hashing

The Oxford college of Engineering Page 65

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 1000
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 2000
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 3000
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 4000
 

The Oxford college of Engineering Page 66

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 5000
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 3
Position: 1 Element: 10
Position: 2 Element: 2000
Position: 3 Element: 4000
Position: 4 Element: 3000
Position: 5 Element: 5000
Position: 6 Element: 1000
Position: 7 Element: 30
Position: 8 Element: 50
Position: 9 Element: 40
Position: 10 Element:20
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 5

The Oxford college of Engineering Page 67

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

IV.VIVA QUESTIONS AND ANSWERS

1. ______ is a unique tag, usually a number, identifies the file within the file system.
a) File identifier
b) File name
c) File type
d) none of the mentioned
Answer: a
2. To create a file
a) allocate the space in file system
b) make an entry for new file in directory
c) both (a) and (b)
d) none of the mentioned
Answer: c
3. By using the specific system call, we can
a) open the file
b) read the file
c) write into the file
d) all of the mentioned
Answer: d
4. File type can be represented by
a) file name
b) file extension
c) file identifier
d) none of the mentioned
Answer: b
5. Which file is a sequence of bytes organized into blocks understandable by the system’s linker?
a) object file
b) source file
c) executable file
d) text file
Answer: a
6. What is the mounting of file system?
a) crating of a filesystem
b) deleting a filesystem
c) attaching portion of the file system into a directory structure
d) removing portion of the file system into a directory structure
Answer: c
7. Mapping of file is managed by
a) file metadata

The Oxford college of Engineering Page 68

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

b) page table
c) virtual memory
d) file system
Answer: a

8. Mapping of network file system protocol to local file system is done by

a) network file system
b) local file system
c) volume manager
d) remote mirror
Answer: a
9. Which one of the following explains the sequential file access method?
a) Random access according to the given byte number
b) read bytes one at a time, in order
c) read/write sequentially by record
d) read/write randomly by record
Answer: b
10. File system fragmentation occurs when
a) unused space or single file are not contiguous
b) used space is not contiguous
c) unused space is non-contiguous
d) multiple files are non-contiguous
Answer: a
11. An index is clustered, if
(A) it is on a set of fields that form a candidate key.
(B)it is on a set of fields that include the primary key.
(C)the data records of the file are organized in the same order as the data entries of the index.
(D)the data records of the file are organized not in the same order as the data entries of the index.
Answer: (C)
12. Consider a B+-tree in which the maximum number of keys in a node is 5. What is the
minimum number of keys in any non-root node?
(A) 1
(B) 2
(C) 3
(D) 4
Answer:(B)
13.A clustering index is defined on the fields which are of type
(A) non-key and ordering
(B) non-key and non-ordering
(C) key and ordering
(D) key and non-ordering
Answer:(A)

14. In the index allocation scheme of blocks to a file, the maximum possible size of the file
depends on :
(A) the number of blocks used for the index, and the size of the blocks.

The Oxford college of Engineering Page 69

FILE STRUCTURES LABORATORY WITH MINI PROJECT (18ISL67)

(B)the size of the blocks, and the size of the address of the blocks.
(C)the size of the blocks, the number of blocks used for the index, and the size of the address of
the blocks.
(D) None of these

V.REFERENCES:

1. K.R. Venugopal, K.G. Srinivas, P.M. Krishnaraj: File Structures Using C++, Tata McGraw-
Hill, 2008.

2. Scot Robert Ladd: C++ Components and Algorithms, BPBPublications, 1993.

3. Raghu Ramakrishna and Johannes Gehrke: Database Management Systems, 3rd Edition,

McGraw Hill, 2003.

4. The File System, Linux Documentation Project

5. Tuning the Linux file system Ext3, Oliver Diedrich, The H, Heise Media UK Ltd., October 27,
2008.

The Oxford college of Engineering Page 70