## Pokhara University | Old Question Paper

Bachelor of Engineering (BE)

Data and File Structure | Level: Bachelor

Year: 2010 | Semester : Spring

**Download Question Paper File**

[ File Type: PDF | File Size: 227 KB | **Download** ]

**Question Paper is Given Below:**

Full Marks: 100 | Pass Marks: 45 | Time: 3 Hrs

Candidates are required to give their answers in their own words as far as practicable. The figures in the margin indicate full marks.

**Attempt all the questions.**

1. a) What is data structure? How do you represent polynomial as an ADT? [7]

b) Write an algorithm to convert an infix expression to postfix expression. Evaluate the following post expression using stackt [8]

`296+*23*-`

2. a) Discuss the advantage of circular queue over linear queue. Write a C/C ++ code to perform enqueue and dequeue operations on a circular queue in array implementation. [7]

b) Write an algorithm to insert an item at the beginning of a linked list and an algorithm to display the items of the list. [8]

3. a) What is tree traversal? Explain preorder, inorder and postorder tree traversal by constructing expression tree of the given expression. [7]

`b*b-4*a*c`

b) Define AVL tree. What is balancing factor of AVL tree? Construct AVL tree from the following data: [8]

`50, 40, 70, 45, 43, 35, 25`

**OR**

a) Define max and min heap tree. Construct a min heap using following data: [6 +2]

`44, 30, 50, 22, 60, 55, 77, 55.`

b) What do you mean by thread? Explain inorder threading with example. [7]

4. a) Sort the following data using merge-sort algorithm: [7]

`66, 33, 40, 22, 55, 88, 60, 11, 80, 20, 50, 44, 77`

b) Describe primitive operation of file. [8]

5. a) Enlist the basic Unix file system commands along with their functions. Also explain the Unix file Directory structure. [8]

b) Assume that, we have 40,000 records each of size 100 bytes. If we want to store the file in a 6250 bpi tape that stores 200 bytes/block and inter block gap of 0.3 inches, how much tape is needed. If B. F. is made 50, what is the effect? [7]

6. a) Define the term file and record. What are the different methods that are used for organizing the field structure within the records of a file? Explain. [7]

b) How classes are used to manipulate buffer? How inheritance applied to record buffered class? [8]

**7. Write short notes on any two: [2 X 5]**

a) Divide and conquer algorithms

b) Huffman algorithm

c) Strength and weakness of CD-ROM