Scribd
Upload
3 views3 pages

Data Structures Assignment Overview

This assignment focuses on assessing knowledge of data structures including complexity, linked lists, recursion, binary search trees, and red-black trees without requiring coding. It includes conceptual questions, applied exercises, and pseudocode tasks related to these topics. Students are expected to provide explanations, diagrams, and reasoning to demonstrate their understanding.

Uploaded by

haytam.backup1
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
3 views3 pages

Data Structures Assignment Overview

This assignment focuses on assessing knowledge of data structures including complexity, linked lists, recursion, binary search trees, and red-black trees without requiring coding. It includes conceptual questions, applied exercises, and pseudocode tasks related to these topics. Students are expected to provide explanations, diagrams, and reasoning to demonstrate their understanding.

Uploaded by

haytam.backup1
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

DATA STRUCTURES — HAND-IN ASSIGNMENT 1

This assignment assesses your understanding of complexity, linked lists, recursion, binary search
trees, and red–black trees. No coding is required, but diagrams, reasoning, and pseudocode are
expected.

PART A — Concepts & Understanding


Q1. Time & Space Complexity
1. Explain what it means for an algorithm to run in O(log n) time. Provide a real-world example of a task
whose effort decreases each time you eliminate half of the remaining possibilities.

2. Give an example of a process that grows linearly with input size and explain why it is O(n).

Q2. Data Structure Trade-Offs


1. Describe a scenario where an array is more suitable than a linked list.

2. Describe a scenario where a linked list is more appropriate than an array.

3. For each scenario, name the operation or property being optimized.

PART B — Applied Short Exercises


Q3. Recursion Dry-

Run

Given:

Function Riddle(n)

If n==0

return 2

else

return 3+Riddle(n-1)

Tasks:

1. Identify the base and recursive cases.

2. Draw the call stack for Riddle(4).

3. Show return value propagation.

4. State the final result.


Q4. Linked List Structural Reasoning
Initial list: 7 → 12 → 19 → 24 → null Tasks:

1. Insert 15 after 12: explain the steps needed

2. Remove 19- explain the steps needed.

3. Show traversal steps when searching for 24.

Q5. Binary Search Tree Construction


Insert: 9, 4, 11, 2, 7, 5, 8 Tasks:

1. Draw resulting BST.

2. Provide results of inorder, preorder, and postorder traversals.

3. Explain how to find the minimum value in a BST.

Q6. Red–Black Tree Construction (same sequence as Q5)


Insert: 9, 4, 11, 2, 7, 5, 8 Tasks:

1. Draw the tree after each insertion with node colors.

2. Identify the insertion case for each step.

3. Provide results of inorder, preorder, and postorder traversals of the final tree.

4. Explain why the final tree satisfies the two core RBT properties:

- No red node has a red parent.

- All root-to-leaf paths have the same black-height.

5. Compare the shapes and heights of the BST and RBT.

PART C — Pseudocode
Q7. Doubly Linked List Insertion
Write pseudocode for inserting a new node with value x after the first node containing the value y in a
doubly linked list. Update all relevant next and prev pointers. Handle insertion at end and case where
target is not found.
Q8. Height of a Binary Search Tree
Write recursive pseudocode for TreeHeight(node)-

- Height of empty tree is -1

- Height of leaf is 0

- Otherwise: 1 + max(height of left subtree, height of right subtree)

You might also like