March 9, 2010

IF 246 DATA STRUCTURES AND ALGORITHMS Question paper


2007 Anna University B.Tech Information Technology
IF 246 DATA STRUCTURES AND ALGORITHMS Question paper

IF 246 DATA STRUCTURES AND ALGORITHMS

Time: 3 Hours Max Marks: 100
Answer all questions

PART – A
(10 x 2 = 20 Marks)
1. Take a linear search algorithms and discuss best-case time analysis.
2. Explain the basic of the Markov algorithm and discuss two ways in which such an algorithm terminates.
3. What is the purpose of a stack in implementing a recursive procedure? Explain.
4. What is the need for using circular array to implement queues?
5. Give the tree T, find the inorder and postorder traversals.
6. Discuss the basis of the Buddy system of allocation. What type of fragmentation still exists?
7. Discuss the timing analysis of the heap-sort algorithm.
8. What are the two broad classes of collision resolution techniques? Explain.
9. With an example explain the Huffman encoding scheme.
10. Explain how the size of a hashing table could be decreased when using (a) linear
hashing, (b) dynamic hashing.

PART – B
(5 x 16 = 80 Marks)
11. i) Implement typical stack operation when stacks are represented using (1) arrays and (ii) using singly linked lists. (8 Marks)
ii) Define a binary tree. (2 Marks)
iii) Give the iterative algorithm for the inorder traversal of a binary tree. (6 Marks)



12a. i) Design a string manipulation algorithm for duplicating a given character string N times. (6 Marks)

ii) Design an algorithm which trims off all the trailing blanks of a character string. (5 Marks)

iii) Give a procedure that uses a stack in order to reverse the elements of a circular queue which is stored in an array. (5 Marks)

(OR)

12b. i) Given as input a word form assigned to the variable WORD, derive function ORD-SEARCH which searches the ordered array of words looking for the word form. If the word form is present, its index location is returned, else zero is
returned. Any search procedure can be used. (6 Marks)

ii) Assume we have a priority queue split into several queues. To access these queues we have vectors of pointers to the front and rear of each queue and one to indicate the length of each.



Thus to access the front of the queue representing priority 2, one merely starts at PRIORITY_F[2]. This representation allows each queue to be of different length. Given this representation, devise algorithms to insert and delete from a priority
queue. (10 Marks)

13a. i) Give an algorithm to reverse the elements of a single linked lists without using a
temporary list. (6 Marks)

ii) Write algorithms to insert into and delete elements from a doubly linked list.
(6 Marks)

iii) Write an algorithms to count the number of nodes in a given singly linked list.
(4 Marks)

(OR)

13b. i) Write algorithms to allocate and free nodes in a body system of memory
allocation. (10 Marks)

ii) Write an algorithm to add two polynomials when the polynomials are represented
using singly linked lists. (6 Marks)

14a. i) Give the best case and worst case analysis of the binary search. (8 Marks)

ii) Write any one external sorting algorithm in detail. (8 Marks)
(OR)

14b. i) Write an algorithm to delete a node from a binary search tree. (8 Marks)

ii) Give the radix sort algorithm in detail. (8 Marks)

15a. i) Give in detail the structure of a typical Indexed Sequential file. (8 Marks)

ii) Describe the direct file organization and give the procedure to retrieve a record
from a direct file given the key. (8 Marks)

(OR)

15b. Write notes on:-
i. Garbage compaction (6 Marks)
ii. VASM Files (5 Marks)
iii. Virtual Hashing (5 Marks)


FEEL USEFUL PLEASE GIVE +1

0 comments :

Post a Comment

Get Syllabus in your Mail

Labels

Accenture Admission Notice - 2010 Admission Notification Anna University Anna University Chennai Anna University Question Papers Anna University Trichy Apparel Technology and Management Aptitude Questions Arts and Science Colleges Biomedical Engineering C and CPP Ebooks Calicut University CBSE Question papers Civil Engineering Civil Service Exams Colleges in India Colleges Result Computer Science Engineering Core Jobs CS R2008 CSE CSIR NET EBooks Download ECE EEE EIE Electives Electrical and Electronics Engineering Electronics and communication Electronics and Instrumentation Engineering Engineering Engineering Colleges in Maharashtra Engineering Colleges in TamilNadu Engineering Admissions Engineering Colleges Engineering Colleges in Karnataka Engineering Jobs Engineering Syllabus Entrance Exam Dates Entrance Exam Results Entrance Examination Exam Time Table Experiencer First Year Syllabus Freshers Full Time Jobs Government jobs in india Hardware and Networking Jobs Hotel Management and Catering Technology IGNOU Information Technology INTEVIEW QUESTIONS IT Jobs JNTU Question Papers Jobs in Bangalore Jobs in Chennai Jobs in Coimbatore Jobs in Delhi Jobs in Hyderabad Jobs in India Jobs in Kerala Jobs in Noida Jobs in Tamilnadu Jobs in TATA Karnataka Educations Lab Manuals Mechanical Engineering Medical Colleges Placement Papers Plus 2 Preparation for exams Private Jobs in India Question Papers Question Papers Download Results Announcement Semester 1 Semester 2 Semester 3 Semester 4 Semester 5 Semester 6 Semester 7 Semester 8 Syllabus Syllabus Download Tamil Movie TCS Placement Papers Teaching Jobs TECH MAHINDRA Textile Technology Top colleges University Results UPSC VICEVESVARAYA TECHNOLOGICAL UNIVERSITY waec Walk-in Interview Web Designers

Followers

Archive

 

Privacy Policy
http://topengineeringcollegesintamilnadu.blogspot.com use third-party advertising companies to serve ads when you visit our website. These companies may use information (not including your name, address, email address, or telephone number) about your visits to this and other websites in order to provide advertisements about goods and services of interest to you. If you would like more information about this practice and to know your choices about not having this information used by these companies, click here.