CS3301 Data Structures Important questions

CS3301 – SYLLABUS

UNIT I LISTS
Abstract Data Types (ADTs) – List ADT – Array-based implementation – Linked list implementation – Singly linked lists – Circularly linked lists – Doubly-linked lists – Applications of lists – Polynomial ADT – Radix Sort – Multilists.

UNIT II STACKS AND QUEUES
Stack ADT – Operations – Applications – Balancing Symbols – Evaluating arithmetic expressions- Infix to Postfix conversion – Function Calls – Queue ADT – Operations – Circular Queue – DeQueue – Applications of Queues.

UNIT III TREES
Tree ADT – Tree Traversals – Binary Tree ADT – Expression trees – Binary Search Tree ADT – AVL Trees – Priority Queue (Heaps) – Binary Heap.

UNIT IV MULTIWAY SEARCH TREES AND GRAPHS
B-Tree – B+ Tree – Graph Definition – Representation of Graphs – Types of Graph – Breadth-first traversal – Depth-first traversal –– Bi-connectivity – Euler circuits – Topological Sort – Dijkstra’s algorithm – Minimum Spanning Tree – Prim’s algorithm – Kruskal’s algorithm

UNIT V SEARCHING, SORTING AND HASHING TECHNIQUES
Searching – Linear Search – Binary Search. Sorting – Bubble sort – Selection sort – Insertion sort – Shell sort –. Merge Sort – Hashing – Hash Functions – Separate Chaining – Open Addressing – Rehashing – Extendible Hashing.

Unit I

1. Singly Linked List
2. Doubly Linked List
3. Circularly Linked List
4. Polynomial ADT

Unit II

1. Applications of Stack
2. Stack ADT
3. DeQue
4. Circular Queue

Unit III

1. Tree Traversal
2. Binary Search Tree
3. Binary Heap
4. AVL Tree

Unit IV

1. B tree/ B+ tree
2. BFS and DFS
3. Dijkstra’s / Prim’s Algorithm
4. Euler Circuit

Unit V

1. Binary Search
2. Insertion/Selection/Merge sort
3. Closed hashing (Open Addressing)
4. Extendible Hashing