Data Structures | Semester 3 Core Notes
Semester 3 - Page 1: Data Structures. 36 numbered topics, highlighted invariants, worked traces, answered exam questions, three diagrams and six complete C11 programs. General common-core BTech CSE guide, not an official assessed syllabus or past-paper prediction. Compare your assigned outline.
gcc -std=c11 -Wall -Wextra -pedantic demo.c -o demo, then run ./demo. Fixed trusted inputs are supplied by main. Dynamic-memory examples check allocation failure. Fixed capacity, recursion depth and index contracts are explicit limits.Topic map
- Data structures and ADTs
- Time and space analysis
- Worst, average and amortized costs
- Arrays and addresses
- Matrices and sparse storage
- Linear and binary search
- Singly linked lists
- Doubly and circular lists
- Allocation and pointer safety
- List reversal
- Stack contracts and bounds
- Bracket matching
- Infix and postfix conversion
- Postfix evaluation
- Circular queues
- Deque and priority queue
- Recursion and stack space
- Tree terms and height
- Binary tree traversals
- BST search and insertion
- BST deletion
- AVL and red-black trees
- Binary heaps
- B-trees, tries and threading
- Hashing and load factor
- Collision handling
- Elementary sorting and stability
- Merge, quick and heap sort
- Counting, radix and lower bounds
- Graph terms and representation
- BFS and shortest paths
- DFS and disconnected graphs
- DAGs and topological order
- Weighted paths and spanning trees
- Testing and choosing structures
- Practice answers and revision
1. Data structures and ADTs
An ADT defines operations and behavior; a data structure selects storage and algorithms..
Answer: No. It specifies a contract, not a programming language.
2. Time and space analysis
State input size, operation, case and auxiliary storage. O is an upper bound, Omega a lower bound and Theta a tight bound.
Answer: No. A constant-time operation is also O(n); Theta(1) is more informative.
3. Worst, average and amortized costs
Average-case needs an input distribution. Amortized cost bounds a sequence without assuming random inputs.
Answer: No. It bounds total work over a sequence.
4. Arrays and addresses
Contiguous arrays support O(1) indexed access in the usual RAM model. Validate indices in C.
Answer: Later elements shift; capacity and allocation are separate costs.
5. Matrices and sparse storage
For row-major R by C storage, offset(i, j)=i*C+j. Sparse formats store nonzero values and positions.
Answer: No. Separately allocated rows differ from a contiguous 2 D array.
6. Linear and binary search
Linear search needs no order. Binary search requires sorted data and a shrinking interval. Specify duplicate behavior.
Answer: Not with its usual correctness guarantee.
Binary search and insertion sort
#include <stdio.h>
#include <stddef.h>
int first_match(const int a[], size_t n, int key) {
size_t lo=0, hi=n;
while (lo<hi) {
size_t mid=lo+(hi-lo)/2;
if (a[mid]<key) lo=mid+1; else hi=mid;
}
return lo<n && a[lo]==key ? (int)lo : -1;
}
void insertion_sort(int a[], size_t n) {
for (size_t i=1; i<n; ++i) {
int key=a[i]; size_t j=i;
while (j>0 && a[j-1]>key) {
a[j]=a[j-1]; --j;
}
a[j]=key;
}
}
int main(void) {
int a[]={7,4,2,4,9};
insertion_sort(a,5);
for (size_t i=0;i<5;++i)
printf("%d%s",a[i],i==4 ? "\n" : " ");
printf("first 4: %d; missing 6: %d\n",
first_match(a,5,4),first_match(a,5,6));
printf("empty: %d\n",first_match(NULL,0,4));
return 0;
}Checked output:
2 4 4 7 9 first 4: 1; missing 6: -1 empty: -1
The search assumes sorted data and a size that fits its int return index. NULL is valid here only with n=0. This is a bounded demonstration, not an arbitrary-size library API.
7. Singly linked lists
Each node stores data and next. Insertion after a known node is O(1); locating it is separate.
Answer: Not generally; finding the predecessor needs traversal.
8. Doubly and circular lists
Doubly linked nodes store prev too. Circular lists have no null terminator; stop at the starting node or use a count.
Answer: Forward and backward traversal disagree and may touch stale memory.
9. Allocation and pointer safety
Check allocation failure, define ownership and free each owned allocation once. Never read freed storage.
Answer: A pointer to an object whose lifetime ended; clearing one pointer does not repair aliases.
10. List reversal
Maintain prev, current, next. Save the unreversed suffix before changing the current link.
Answer: Otherwise changing current.next loses access to the remaining list.
Owned list reversal and cleanup
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *next; } Node;
void clear(Node *p) {
while (p) { Node *next=p->next; free(p); p=next; }
}
int push_front(Node **head,int value) {
Node *p=malloc(sizeof *p);
if (!p) return 0;
p->value=value; p->next=*head; *head=p;
return 1;
}
Node *reverse(Node *head) {
Node *prev=NULL;
while (head) {
Node *next=head->next;
head->next=prev; prev=head; head=next;
}
return prev;
}
int main(void) {
Node *head=NULL;
for (int v=3;v>=1;--v) {
if (!push_front(&head,v)) {
clear(head); fputs("allocation failed\n",stderr); return 1;
}
}
head=reverse(head);
for (Node *p=head;p;p=p->next)
printf("%d%s",p->value,p->next ? " " : "\n");
clear(head); head=NULL;
printf("empty reverse: %s\n",reverse(head)==NULL ? "ok" : "bad");
return 0;
}Checked output:
3 2 1 empty reverse: ok
11. Stack contracts and bounds
A stack is LIFO. Reject full push and empty pop before accessing the array.
Answer: Overflow adds beyond capacity; underflow removes from empty storage.
12. Bracket matching
Push openers; each closer must match the latest opener. Reject leftover openings. The simple model ignores quoted-string syntax.
Answer: Nesting order matters.
Bracket stack with bounds
#include <stdio.h>
#include <stddef.h>
#define CAP 64
/* 1 balanced; 0 mismatch; -1 capacity exceeded.
Other characters ignored; not a source-code parser. */
int balanced(const char *text) {
char stack[CAP]; size_t count=0;
for (size_t i=0;text[i]!='\0';++i) {
char c=text[i];
if (c=='(' || c=='[' || c=='{') {
if (count==CAP) return -1;
stack[count++]=c;
} else if (c==')' || c==']' || c=='}') {
if (count==0) return 0;
char open=stack[--count];
if ((c==')' && open!='(') ||
(c==']' && open!='[') ||
(c=='}' && open!='{')) return 0;
}
}
return count==0;
}
int main(void) {
const char *tests[]={"([{}])","([)]","", ")","(("};
for (size_t i=0;i<5;++i)
printf("\"%s\": %d\n",tests[i],balanced(tests[i]));
char full[CAP+2];
for (size_t i=0;i<CAP+1;++i) full[i]='(';
full[CAP+1]='\0';
printf("capacity: %d\n",balanced(full));
return 0;
}Checked output:
"([{}])": 1
"([)]": 0
"": 1
")": 0
"((": 0
capacity: -1
13. Infix and postfix conversion
Use an operator stack with precedence, associativity and parentheses. Unary operators require an explicit grammar.
Answer: No. Equal-precedence behavior depends on associativity.
14. Postfix evaluation
Push operands. For binary operations pop right then left. Check arity, division and final stack size.
Answer: Exactly one result without earlier underflow.
15. Circular queues
FIFO removes the oldest item. Wrap indices modulo capacity; count distinguishes empty from full.
Answer: It can mean empty or full without a separate occupancy convention.
Fixed circular queue
#include <stdio.h>
#include <stddef.h>
#define CAP 3
typedef struct { int data[CAP]; size_t front,count; } Queue;
int enqueue(Queue *q,int value) {
if (q->count==CAP) return 0;
q->data[(q->front+q->count)%CAP]=value;
++q->count; return 1;
}
int dequeue(Queue *q,int *out) {
if (q->count==0) return 0;
*out=q->data[q->front];
q->front=(q->front+1)%CAP; --q->count;
return 1;
}
int main(void) {
Queue q={{0},0,0}; int value=0;
if (!enqueue(&q,10) || !enqueue(&q,20) || !enqueue(&q,30)) return 1;
printf("full insert: %d\n",enqueue(&q,99));
if (dequeue(&q,&value)) printf("first: %d\n",value);
if (!enqueue(&q,40)) return 1;
while (dequeue(&q,&value)) printf("next: %d\n",value);
printf("empty remove: %d\n",dequeue(&q,&value));
return 0;
}Checked output:
full insert: 0 first: 10 next: 20 next: 30 next: 40 empty remove: 0
16. Deque and priority queue
Deque supports both ends. Priority queue removes by priority rather than arrival time.
Answer: No. Equal-priority order also needs a rule.
17. Recursion and stack space
A recursive algorithm needs progress and a base case. Count recursive frames as auxiliary storage.
Answer: No.
18. Tree terms and height
Use height in edges: leaf 0, empty tree-1. A nonempty tree with n nodes has n-1 edges.
Answer: Some courses count nodes instead; formulas differ by one.
19. Binary tree traversals
At most two children. Preorder root-left-right; inorder left-root-right; postorder left-right-root; level order uses a queue.
Answer: Only if the BST ordering property holds.
20. BST search and insertion
Smaller keys go left and larger keys right under a stated duplicate rule. Cost is O(h), not always O(log n).
Answer: The C demo ignores them; other APIs may keep counts.
21. BST deletion
Leaf: remove its link. One child: splice it in. Two children: use successor or predecessor, then delete that replacement node.
Answer: Move the associated record consistently with its ownership rule.
BST insert, delete and cleanup
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int key; struct Node *left,*right; } Node;
void clear(Node *p) {
if (!p) return;
clear(p->left); clear(p->right); free(p);
}
int insert(Node **root,int key) {
if (!*root) {
Node *p=malloc(sizeof *p);
if (!p) return 0;
*p=(Node){key,NULL,NULL}; *root=p; return 1;
}
if (key<(*root)->key) return insert(&(*root)->left,key);
if (key>(*root)->key) return insert(&(*root)->right,key);
return 1; /* duplicates ignored */
}
Node *erase(Node *p,int key) {
if (!p) return NULL;
if (key<p->key) p->left=erase(p->left,key);
else if (key>p->key) p->right=erase(p->right,key);
else {
if (!p->left || !p->right) {
Node *child=p->left ? p->left : p->right;
free(p); return child;
}
Node *s=p->right;
while (s->left) s=s->left;
p->key=s->key; p->right=erase(p->right,s->key);
}
return p;
}
void inorder(const Node *p) {
if (!p) return;
inorder(p->left); printf("%d ",p->key); inorder(p->right);
}
int main(void) {
Node *root=NULL; int keys[]={8,3,10,6,6};
for (size_t i=0;i<5;++i) {
if (!insert(&root,keys[i])) {
clear(root); fputs("allocation failed\n",stderr); return 1;
}
}
printf("before: "); inorder(root); putchar('\n');
root=erase(root,8); root=erase(root,99);
printf("after: "); inorder(root); putchar('\n');
clear(root); return 0;
}Checked output:
before: 3 6 8 10 after: 3 6 10
22. AVL and red-black trees
AVL keeps child-height difference at most one. Rotations keep inorder order. Red-black color rules keep logarithmic height.
Answer: No. A plain BST does not repair imbalance.
23. Binary heaps
A min-heap is complete and each parent is no greater than its children. Zero-based children 2 i+1, 2 i+2; parent(i-1)/2 for i>0.
Answer: Peek O(1), insert/extract O(log n), bottom-up build O(n).
24. B-trees, tries and threading
B-trees use multi-key nodes with occupancy bounds. Tries follow key symbols. Threaded-tree links may store inorder neighbors and need tags.
Answer: No. Its tag distinguishes traversal links from children.
25. Hashing and load factor
Keys map to buckets; equal keys must hash consistently. Load factor alpha=n/m. Expected constant lookup needs hashing and load assumptions.
Answer: No. Compare actual keys.
26. Collision handling
Chaining stores bucket collections. Open addressing probes within the table. Deletion usually needs tombstones or a supported repair.
Answer: O(n) when collisions or probing require many inspections.
27. Elementary sorting and stability
Stable sorting preserves equal-key order. In-place usually means constant auxiliary storage, with call-stack treatment stated separately.
Answer: No. Swap-based selection is generally unstable; strict-shift insertion is stable.
28. Merge, quick and heap sort
Merge sort has O(n log n) worst time and typical array buffer O(n). Quicksort expected O(n log n) needs pivot/input assumptions; worst O(n squared). Heap sort worst O(n log n).
Answer: No. Repeated n-1 sized partitions give quadratic work.
29. Counting, radix and lower bounds
Counting sort costs O(n+k) for bounded integer range k. Radix uses stable digit passes. Comparison sorting has worst-case Omega(n log n) comparison lower bound.
Answer: It uses values as indices rather than only comparisons.
30. Graph terms and representation
State directedness, weights and loop/parallel-edge rules. Matrix space O(V squared); adjacency lists O(V+E). Undirected edges appear twice in lists.
Answer: O(1), but scanning neighbors costs O(V).
31. BFS and shortest paths
Use a queue and mark on discovery. Layers find shortest paths by edge count in unweighted graphs. Adjacency-list traversal O(V+E).
Answer: No. Its guarantee applies to unweighted or equal-weight edges.
BFS path and DFS forest
#include <stdio.h>
#define N 5
/* A-B,A-C,B-D,C-D; E isolated. Matrix representation. */
const int edge[N][N]={
{0,1,1,0,0},{1,0,0,1,0},{1,0,0,1,0},
{0,1,1,0,0},{0,0,0,0,0}
};
void bfs(int start,int dist[],int parent[]) {
int queue[N],front=0,back=0;
for (int i=0;i<N;++i) { dist[i]=-1; parent[i]=-1; }
dist[start]=0; queue[back++]=start;
while (front<back) {
int u=queue[front++]; printf("%c ",'A'+u);
for (int v=0;v<N;++v) {
if (edge[u][v] && dist[v]==-1) {
dist[v]=dist[u]+1; parent[v]=u;
queue[back++]=v; /* marked before enqueue */
}
}
}
}
void dfs(int u,int seen[]) {
seen[u]=1; printf("%c ",'A'+u);
for (int v=0;v<N;++v) if (edge[u][v] && !seen[v]) dfs(v,seen);
}
void print_path(int v,const int parent[]) {
if (parent[v]!=-1) print_path(parent[v],parent);
printf("%c ",'A'+v);
}
int main(void) {
int dist[N],parent[N],seen[N]={0};
printf("BFS: "); bfs(0,dist,parent); putchar('\n');
printf("A to D: "); print_path(3,parent); putchar('\n');
printf("distance D: %d; E: %d\n",dist[3],dist[4]);
printf("DFS forest: ");
for (int u=0;u<N;++u) if (!seen[u]) dfs(u,seen);
putchar('\n'); return 0;
}Checked output:
BFS: A B C D A to D: A B D distance D: 2; E: -1 DFS forest: A B D C E
Representation caveat: this small runnable example uses an adjacency matrix and scans every possible neighbor, so its traversal is O(V squared), not the O(V+E) adjacency-list bound. Helper functions assume a valid vertex 0..N-1. Call print_path only for a reachable target, otherwise it would print that target alone rather than indicate no path.
32. DFS and disconnected graphs
Use recursion or a stack with visited state. Restart from unvisited vertices to cover every component.
Answer: Without visited state, a cycle can revisit vertices indefinitely.
33. DAGs and topological order
A directed acyclic graph admits an order where every edge goes forward. Kahn removes zero-indegree vertices; fewer than V removals signals a cycle.
Answer: Not generally; multiple ready vertices permit alternatives.
34. Weighted paths and spanning trees
Usual Dijkstra needs nonnegative weights. Bellman-Ford allows negative edges and detects reachable negative cycles. Prim/Kruskal solve connected undirected weighted MST.
Answer: There is no all-vertex spanning tree; compute a minimum spanning forest.
35. Testing and choosing structures
Choose by operations, ordering, capacity and memory. Test invariants and boundary cases. Assertions are test checks, not production validation.
Answer: Broken invariant, smallest failing input, expected/actual result and checked fix.
36. Practice answers and revision
State contracts and case qualifiers before quoting complexity. Use a small trace instead of slogans.
Answer: No. Compare this common-core guide against your course outline and extra topics.
Operation-cost reference
| Operation | Cost | Condition |
|---|---|---|
| Array index | O(1) | Middle insert/delete O(n) |
| Dynamic array append | Amortized O(1) | Individual resize O(n) |
| Known-node singly splice | O(1) | Finding node/predecessor may be O(n) |
| Fixed stack / circular queue | O(1) | Check capacity and empty state |
| BST search/insert/delete | O(h) | Balanced O(log n); chain O(n) |
| Hash lookup | Expected O(1) | Hash/load assumptions; worst O(n) |
| Heap insert/extract | O(log n) | Peek O(1); build O(n) |
| BFS / DFS adjacency lists | O(V+E) | Full traversal; auxiliary O(V) |
| BFS / DFS matrix | O(V squared) | All possible neighbors scanned |
Sorting entries refer to the stated standard variants; k is key-range size. Quicksort expected time needs pivot/input assumptions. Stability belongs to an implementation, not the name alone.
Sorting reference
| Sort | Best | Worst | Auxiliary space | Stable? |
|---|---|---|---|---|
| Bubble, early-stop | O(n) | O(n squared) | O(1) | Yes, strict swap |
| Selection, ordinary | O(n squared) | O(n squared) | O(1) | No |
| Insertion | O(n) | O(n squared) | O(1) | Yes, strict shift |
| Merge, array | O(n log n) | O(n log n) | O(n) | Yes, left on ties |
| Quick, ordinary | O(n log n) balanced | O(n squared) | O(log n) typical stack; O(n) worst | No |
| Heap | O(n log n) bound | O(n log n) | O(1) iterative | No |
| Counting | O(n+k) | O(n+k) | O(n+k) stable version | Yes, stable variant |
Revision checklist
- Trace mutations without losing links.
- State ordering, duplicate and capacity contracts.
- Separate amortized, expected and worst-case costs.
- Explain BST deletion and rotations with small traces.
- Trace expression operand order, queue wrap and graph visited state.
- Keep actual test evidence, including failed results.
Practice resources
Use the Data Structures Lab File, Lab Files index and Online Compiler: choose C.
Sources
Textbook references support definitions and cost qualifiers. Explanations, fixed examples and six programs are original teaching material.
Comments
Post a Comment