CS50x: Introduction to Computer Science Data Structures Syllabus

Data Structures syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Data Structures in CS50x: Introduction to Computer Science, not a summary of it.

1. 1

   Abstract Data Types

   3 topics

   • Structures
   • Stacks
   • Queues
2. 2

   Linked Lists

   2 topics

   • Singly-Linked Lists
   • Doubly-Linked Lists
3. 3

   Trees

   2 topics

   • Binary Search Trees
   • Tries
4. 4

   Hash Tables

   2 topics

   • Hash Functions
   • Collisions and Chaining

Data Structures flashcards for CS50x: Introduction to Computer Science

20 of 50 cards from the Data Structures deck — real questions with worked answers.

1. In C, what is a structure (struct)?

   A composite (user-defined) data type that groups multiple related variables, possibly of different types, together under one name so they can be treated as a single unit (e.g., a person with a name and a phone number).

2. Write the typical C syntax (as used in CS50) to define a structure type called person with a name and a number field.

   typedef struct { string name; string number; } person; — typedef gives the structure a usable type name so you can declare variables like person p;

3. How do you access a field of a struct variable versus a field of a struct accessed through a pointer in C?

   Use the dot operator for a variable: p.name. Use the arrow operator for a pointer: ptr->name, which is shorthand for (*ptr).name (dereference, then access the field).

4. How do you dynamically allocate memory for one struct node in C, and what must you check afterward?

   node *n = malloc(sizeof(node)); You must check whether n == NULL (malloc failed) before using it, and later call free(n) to avoid a memory leak.

5. Why are structures a prerequisite for building linked lists, trees, and tries?

   Because each element (node) must bundle data together with one or more pointers to other nodes; a struct is the mechanism that groups a value and its pointer(s) into a single self-referential type.

6. What is a stack, and what ordering principle does it follow?

   A stack is a data structure in which elements are added and removed only from the top. It follows LIFO — Last In, First Out: the most recently added element is the first one removed.

7. Name and define the two fundamental operations on a stack.

   Push: add an element onto the top of the stack. Pop: remove (and return) the element from the top of the stack.

8. What is the time complexity of push and pop on a stack?

   Both are $O(1)$ — constant time, because they only touch the top of the stack regardless of how many elements it holds.

9. Give two real-world or computing examples that behave like a stack.

   A stack of cafeteria trays (you take the top one, the last one placed); the undo feature in an editor; the function call stack, where the most recently called function returns first.

10. In an array-based stack of fixed capacity, when do overflow and underflow occur?

    Overflow: pushing when the stack is already full (size equals capacity). Underflow: popping when the stack is empty (size is $0$). Both must be guarded against.

11. What is a queue, and what ordering principle does it follow?

    A queue is a data structure where elements are added at the back and removed from the front. It follows FIFO — First In, First Out: the earliest added element is the first one removed.

12. Name and define the two fundamental operations on a queue.

    Enqueue: add an element to the end (back/tail) of the queue. Dequeue: remove the element from the front (head) of the queue.

13. What is the time complexity of enqueue and dequeue on a properly implemented queue?

    Both are $O(1)$ — constant time, achieved by keeping references (or indices) to both the front and the back of the queue.

14. How do a stack and a queue differ in behavior?

    A stack is LIFO: insertions and removals happen at the same end (the top), so the newest element leaves first. A queue is FIFO: insertions happen at the back and removals at the front, so the oldest element leaves first — fair like a line of people.

15. In an array-based queue, why is the array typically treated as circular, and what extra bookkeeping is needed?

    So that dequeuing from the front does not waste slots or require shifting all elements: front and back indices wrap around using modular arithmetic (index $\bmod$ capacity). You track the front index and the current size.

16. What two fields does a node of a singly-linked list contain (in CS50-style C)?

    A value field (the data, e.g., int number) and a pointer to the next node: struct node *next. The struct must use its full name internally because it refers to itself.

17. What is the time complexity of inserting a new element at the head of a singly-linked list, and why?

    $O(1)$ — you allocate a node, point its next at the current head, and update the head pointer; no traversal or shifting is needed regardless of list length.

18. What is the time complexity of searching a singly-linked list of $n$ elements, and why can't you use binary search on it?

    $O(n)$, because you must follow next pointers one node at a time from the head. Binary search is impossible since a linked list has no random access — you cannot jump to the middle element in constant time.

19. When inserting a new node at the head of a linked list, why must you set the new node's next pointer before updating the head pointer?

    If you update head first, you lose your only reference to the rest of the list — the remaining nodes become unreachable (orphaned/leaked). Always link the new node into the list, then move head.

20. How is the end of a linked list marked, and how does a traversal loop use this?

    The last node's next pointer is set to NULL. Traversal runs a cursor: for (node *tmp = list; tmp != NULL; tmp = tmp->next), stopping when the cursor reaches NULL.

See more Data Structures flashcards →

Planning Data Structures for CS50x: Introduction to Computer Science

Data Structures (CS50x: Introduction to Computer Science) FAQ