Data Structure (3408)-Assignment-old papers-course outline -aiou-spring 2015

AIOU

 

 

 

 

 

 

 

 

Course: Data Structure (3408)

Level: B.S (CS) Semester: Spring, 2015

Total Marks: 100 Pass Marks: 50

ASSIGNMENT No. 1

Note: All questions carry equal marks.

Q.1 a) Write down the difference between linear and 

          non-linear data structure? Give two  examples -of each

b) What types of operations could be performed on 

       data structures?

Q.2 a) Write an algorithm that determines whether a given 

           number is a prime numberor not.

b) Write the difference between one dimension and 

   two-dimension array. How wecan perform 

   different operations  (Insert, Delete and Search) on 

    both array’s.

Q.3 a) Write down the difference between Stack and Queue 

       data structure and write an algorithm to reverse a string 

     “ P A K I S T A N” by usingQueue or Stack data structure.

b) What is a MAX priority physical queue, explain it through 

      the example of place and serve operations.

Q.4 a) List down the difference between singly linked list v/s 

          double linkedlist.

b) How we insert, update & delete items in double linked list.

c) Write an Algorithm of data insertion and deletion into  

       double linked list.

Q.5 Convertthe below mentioned infix expression to postfix

 expression by usingthe Stack.

a) 9+3*4/7-10

b) (A+B)*((D-E)+F)-G

ASSIGNMENT No. 2

Total Marks: 100 Pass Marks: 50

Note: All questions carry equal marks.

Q.1 a) In Queue what’s the disadvantage of single step Append 

           serve model and how we can fix this?

ans:       Disadvantage of Single Step Append-Serve Model Although time efficiency of single step

            append-serve mode is good and no need to move n element on each serve but space utilization is

             poor. 22. Circular Queue ● The solution of append-serve model is circular queue.

b) Write an algorithm to store non-leap years in circular queue 

      of array size 10 YEAR[9]. Make sure if queue full then 

      delete the older years and store the newer year in circular 

      queue until the last year stored in queue.

(Note: Starting year 1980 and Last year 2014. Leap year is a 

            year which is divisible by 4 and not divisible by 100 or A 

            year divisible by 400).

Q.2 Perform Step by Step BFS & DFS Graph traversing of 

       below mentionedundirected graph.

Q.3 a) Perform Quick sort on below mentioned unsorted list to 

            ascending order.

         “44, 20, 5, 8, 100, 99, 1, 2, 6, 10”

b) Perform a more suitable step-by-step search algorithm on sorted array.

         “2, 8, 10, 12, 15, 25, 51, 65, 73, 92”

Q.4 a) What is a Tree data structure and how Binary can differ 

           from non-BinaryTree.

b) Write down the difference between recursive Pre-Order and 

    Post-Order Treetraversal.

c) Drawa Binary Search Tree of 15, 5, 23, 3, 7, 2, 4, 14, 9, 18,

    27, 16, 41

Q.5 a) Write the difference between Data structure and Files 

          structure with some examples.

b) Explainfiles organize using sequential, indexed and hashing 

     method.

Recommended Book:

Introduction to Data Structure with Application by Paul Trembley Sorenson

Course Outlines:

Unit No. 1 Introduction to Data Structures

1-BasicTerminologies

2- Introduction to Data Structures

3-Data Structure (Classification, Types, Operation)

4-Basics of Algorithms

5-Notation used

6-Importance of Algorithms for Optimized Application         

    Development

7- Introduction to Analysis of Algorithms

Unit No. 2 Arrays

1-Arrays (Definition and Examples)

2-Representation of array in Memory

3-Accessing & Traversing Array

4-Inserting & Deleting, MultiDimensional Arrays & their Representation in Memory

Unit No. 3 Stacks

1-Stack

 2-Importance of Stack

3-Array Representation of Stacks

4-Stack Operations(PUSH and POP operations)

5-Infix, Postfix and Prefix Expressions

Unit No. 4 Queues

1-Queue, 

2-Representation of Queues,

3-Operation Perform on Queue (Inserting andRemoving Nodes), 

4-De-queues, 

5-Priority queues

Unit No. 5 Linked Lists

LinkedLists Concept, 

Representation of Linked Lists in Memory, 

Traversing &Searching a Lined List Insertion & Deletion in Linked List, 

types of Linked Lists

Unit No. 6 Trees

Tree, 

Tree Types (simple, Binary, General), 

Representation of Binary Tree in Memory,

 Traversing (Pre order, in order),

 Basic Operation (Insertion Deletion)

Unit No.7 Sorting & Searching

BubbleSort, Quick Sort, Insertion Sort, Selection Sorting, 

SequentialSearch, Binary Search

Unit No. 8 Graphs

GraphTheory Terminology, 

Linked Representation of Graphs, extra

Directed andUndirected Graphs, 

Traversal Methods

Unit No. 9 Files and Data Storage

Basic Operations on Different Files Organizations, 

Add, Update and Delete Record,

 File Organizations, 

Sequential, Indexed Sequential, 

Direct (Hashing), Merging Files.

old papers data structure 3408