My Profile
Active Members
TodayLast 7 Days
more...
Awards & Gifts
Online Exams
Fresher Jobs
Our fresher job section is exclusively for fresh graduates! Find jobs for freshers in major Indian
cities including Bangalore, Chennai, Hyderabad, Pune or Kochi
Resources
Find educational articles, blogs, discussion threads and other resources.
Colleges
Find details about any college in India or search for courses.
|
Download Model question papers & previous years question papers
|
Posted By: B.Rajashree Member Level: Silver Posted Date: 18 Nov 2007
|
2007 Anna University B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2007. Question paper
|
|
|
B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2007.
THIRD SEMESTER
Electronics and Communication Engineering
CS 1151 – DATA STRUCTURES
(common to computer Science Engineering and Information Technology branches of Annual Pattern Candidates admitted in 2006)
(Regulation 2004)
Time: Three hours Maximum : 100 marks
Answer all questions.
PART A - 10 * 2 = 20
1. When will you say an algorithm efficient? Give the notation for time complexity.
2. What is ‘top-down’? Is ‘C’ language a top-down design? Justify your answer.
3. Why is linked list used for polynomial arithmetic?
4. Write the role of stack in function call.
5. What is the minimum number of nodes in an AVL tree of height 5?
6. What is the use of sentinel value in binary heap?
7. Which is the best way of choosing the pivot element in quick sort?
8. Merge sort is better than insertion sort. Why?
9. Define a graph. How it differs from tree?
10.What is minimum spanning tree? Name any two algorithms used to find MST.
PART B – 5 * 16 = 80
11. (a) (1) Given two lists L1 and L2, write the routine to compute L1 intersection with L2 using basic operations. (Hint : for efficient performance, sort the lists). (10)
(2) Write the routines for inserting and deleting elements from a queue.Check for the conditions Q-empty and Q-full. (6)
OR
(b) (1) How you implement a stack of queues? Write routines for creation and inserting of elements into it. (8)
(2) Write routines to insert heterogeneous data into the list. (8)
12. (a) (1) Write the routines to insert and remove a node from Binary Search Tree. (10)
(2) A full node is a node with two children. P rove that the number of full nodes plus one is equal to the number of leaves in a binary tree. (6)
OR
(b) (1) Show the result of inserting 2,1,4,5,9,3,6,7 into an empty AVL tree. (6)
(2) Write the procedures to implement single and double rotations while inserting nodes in an AVL tree. (10)
13. (a) Explain with suitable examples the basic heap operations and write algorithms for the same. (16)
(b) How will you resolve the collisions, while inserting elements into the hash table using separate chaining and linear probing? Write the routines for inserting, searching and removing elements from the hash table using the above mentioned techniques. (16)
14. (a) (1) Write the routine for sorting n elements in increasing order using heap sort. (12)
(2) Sort 3,1,4,1,5,9,2,6 in decreasing order using heap sort. (4)
OR
(b) (1) Explain with example, about the insertion sort. (6)
(2) What is external sorting? Discuss the algorithms with proper examples. (10)
15. (a) (1) Discuss and write the program to perform topological sorting. (6)
(2) What is single source shortest path problem? Discuss Dijikstra’s single source shortest path algorithm with an example. (10)
OR
(b) Write an algorithm to find the minimum cost spanning tree of an undirected, weighted graph and explain it. (16)
Return to question paper search
|
|
|
Submit Previous Years University Question Papers and make money from adsense revenue sharing program
Are you preparing for a university examination? Download model question papers
and practise before you write the exam.
|
Watch TV Channels
|