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: vivekanandan Member Level: Gold Posted Date: 18 Jun 2008
|
2007 2007 Anna University B.E Computer Science CS 1151-DATA STRUCTURES Question paper Question paper
B.E/B.Tech. DEGREE EXAMINATION, APRIL/MAY 2007
Third Semester
Computer Science and Engineering
CS 1151-DATA STRUCTURES
Answer all the questions:
PART A-(10 X 2=20 marks)
1.When will you say an algorithm efficient? Give the notations for time complexity.
2.What is a ‘top-down’ design? 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 X 16=80 marks)
11.(a).(i).Given two lists L1 and L2, write the routines to compute L1 n L2 using basic operations.
(ii).Write the routines for inserting and deleting elements from a queue. Check for the conditions Q-empty and Q-full.
(Or)
11.(b).(i).How would you implement a stack of queues? Write routines for creation and inserting of elements into it.
(ii).Write routines to insert heterogeneous data into the list.
12.(a).(i).Write the routines to insert and remove a node from Binary Search Tree.
(ii).A full node is a node with two children. Prove that the number of full nodes plus one is equal to the number of leaves in a binary tree.
(Or)
12.(b).(i).Show the resulting of inserting 2,1,4,5,9,3,6,7 into an empty AVL tree.
(ii).Write the procedure to implement single and double rotations while inserting nodes in an AVL tree.
13.(a).Explain with suitable examples the basic heap operations and algorithms for the same.
(Or)
13.(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.
14.(a).(i).Write the routine for sorting n elements in increasing order using heap sort.
(ii).Sort 3,1,4,1,5,9,2,6 in decreasing order using heap sort.
(Or)
14.(b).(i).Explain with example about the insertion sort.
(ii).What is external sorting? Discuss the algorithms with proper examples.
15.(a).(i).Discuss and write the program to perform topological sorting.
(ii).What is single source shortest path problem? Discuss Dijikstra’s single source shortest path algorithm with an example.
(Or)
15.(b).(i).Write an algorithm to find the minimum cost spanning tree of an undirected, weighted graph.
(ii).Find the MST for the following graph.
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
|