Vidyarthi AIStudent Career Compass

BCS301AKTU · Sem 3

Data Structure

AKTU 2023-24 scheme (B.Tech 2nd Year, AICTE model curriculum) · 100 marks: 70 end-sem theory (3 hrs; Section A: 7 short questions x 2 = 14; Section B: any 3 of 5 x 7 = 21; Section C: 5 questions, one per unit, attempt 1 of 2 parts each, x 7 = 35) + 30 internal (CT 20 + TA 10). Lab BCS351 (1 credit) is marked separately out of 100.

Official syllabus

Revised 0 of 1010 high-repeat questions

One-Night Pass Pack

Scan left to right: operand goes to output; '(' is pushed; on ')' pop to output until '('. On an operator, pop operators of higher or equal precedence (except right-associative ^), then push it. At the end pop everything left. A+B*C-D/F gives ABC*+DF/-. Evaluation: push operands; on an operator pop B then A, push A op B; the last value on the stack is the answer. Both run in O(n) time.
Full-marks tip: Draw a three-column table (Symbol, Stack, Postfix) and fill one row per symbol. Write the precedence order first. Common mistake: popping the operands in the wrong order for - and /.

Exam kal hai? Send this Pass Pack to your batch group.

Unit-wise syllabus

U1Introduction, Arrays and Linked Lists

Weightage: Not officially published (Section C has one 7-mark question per unit; Sections A and B are not split equally)

Basic terminology, algorithm complexity, asymptotic notations (Big O, Omega, Theta)Time-space trade-off, abstract data typesArrays: 1D and 2D, row-major and column-major address calculationSparse matricesSingly, doubly and circular linked lists: insertion, deletion, traversalPolynomial representation and addition using linked lists

U2Stacks, Recursion and Queues

Weightage: Not officially published (Section C has one 7-mark question per unit; Sections A and B are not split equally)

Stack ADT: push, pop, array and linked implementationInfix, prefix and postfix expressions; conversion and evaluationRecursion vs iteration, tail recursion, removal of recursionBinary search, Fibonacci and Tower of Hanoi using recursionQueue: array and linked implementation, circular queueDeque and priority queue

U3Searching, Hashing and Sorting

Weightage: Not officially published (Section C has one 7-mark question per unit; Sections A and B are not split equally)

Sequential, index sequential and binary searchHashing: hash functions, collision resolution (linear probing, quadratic probing, chaining)Insertion, selection and bubble sortQuick sort and merge sortHeap sort and radix sort

U4Trees

Weightage: Not officially published (Section C has one 7-mark question per unit; Sections A and B are not split equally)

Binary tree terminology, array and linked representationComplete, extended and strictly binary treesInorder, preorder, postorder traversal; constructing a tree from traversalsBinary search tree: insertion, deletion, searchingThreaded binary trees, Huffman codingAVL trees, B-trees, binary heaps

U5Graphs

Weightage: Not officially published (Section C has one 7-mark question per unit; Sections A and B are not split equally)

Graph terminology, adjacency matrix and adjacency listDepth first search and breadth first searchConnected components and spanning treesMinimum spanning tree: Prim's and Kruskal's algorithmsTransitive closure (Warshall's algorithm)Shortest path: Dijkstra's algorithm

Curated video lectures

Free lectures from well-known educators, matched to units. Videos load only when you tap “Watch here”, to save data.

Complete Data Structure lectures for AKTU (all units)

University Academy · Playlist · 112 videos · Hindi

Data Structures and Algorithms full course (stacks, queues, trees, graphs)

Jenny's Lectures CS IT · Playlist · 122 videos · English

Data Structures (arrays, linked lists, stacks, queues, trees)

Neso Academy · Playlist · 144 videos · English

Linked lists, stacks, queues and BST in C

mycodeschool · Playlist · 42 videos · English · Unit 1

Algorithms: sorting, Dijkstra, Prim and Kruskal

Abdul Bari · Playlist · 84 videos · English · Unit 5

Exam Guide Radar

Standard textbook

Aaron M. Tenenbaum, Yedidyah Langsam and Moshe J. Augenstein, Data Structures Using C and C++, PHI (first text in the AKTU BCS301 list; Horowitz and Sahni and Lipschutz Schaum's Outline are also listed)

Exam guide students buy

Quantum Series: Data Structure (BCS301) by Quantum Publications

Unit-wise short and long answers with solved AKTU papers. Buy the edition that matches your scheme code (BCS/BAS, not the old KCS/KAS).

Local market tip

Buy the Quantum for code BCS301 (2023-24 onward), not the older KCS301 edition, from bookshops near your college around October before the odd-semester exams.

Lab Viva Survival

BCS351: Stack and queue programs (array and linked stack, infix to postfix, postfix evaluation, circular queue)

Q. What is stack overflow and underflow?: → Overflow is pushing into a full stack; underflow is popping from an empty stack.
Q. Why is postfix notation preferred by compilers?: → It needs no parentheses or precedence rules and can be evaluated in one left-to-right scan with a stack.
Q. How do you check balanced parentheses?: → Push every opening bracket, pop on a closing bracket and check it matches; the stack must be empty at the end.
Q. How is a circular queue better than a linear queue?: → It reuses empty slots at the front by wrapping rear with (rear + 1) % size, so no space is wasted.

BCS351: Linked list programs (singly, doubly, circular; insert, delete, reverse, polynomial addition)

Q. What is the advantage of a linked list over an array?: → Size grows at run time and insertion/deletion needs only pointer changes, no shifting.
Q. How do you reverse a singly linked list?: → Use prev, cur and next pointers: point cur->next to prev and move all three forward until cur is NULL.
Q. Why is a doubly linked list useful?: → Each node has prev and next, so you can move both ways and delete a node without searching for its previous node.

BCS351: Sorting, searching, BST and graph programs

Q. What is the condition for binary search?: → The array must be sorted; it halves the range each step, so it is O(log n).
Q. Which BST traversal gives sorted output?: → Inorder traversal (left, root, right).
Q. Which data structures are used in BFS and DFS?: → BFS uses a queue; DFS uses a stack or recursion.