LabExamAnswers

Question 1

What is the difference between text files and binary files in C?

Answer 1

Text files store data in human-readable ASCII characters (e.g., .txt, .csv). Binary files store data in raw binary format (e.g., .dat, .bin) and are not human-readable.

Question 2

What is the role of the Header record in the file-based linked list implementation?

Answer 2

The Header record stores metadata, specifically the indices of the list head (listHead) and the head of the avail list (availHead).

Question 3

How does the avail list help in managing deleted nodes?

Answer 3

The avail list keeps indices of deleted nodes for reuse, minimizing file size growth.

Question 4

Write the C structure definition for Header.

Answer 4

typedef struct { int listHead; int availHead; } Header;

Question 5

Write the C structure definition for Node.

Answer 5

typedef struct { int data; int next; } Node;

Question 6

What is the final linked list representation after inserting 10, 5, and 7?

Answer 6

[2] 5 → [3] 7 → [1] 10 → NULL

Question 7

What is the process for deleting a value from the file-based linked list?

Answer 7

Traverse to find the value, update previous node’s next index, set deleted node’s next to availHead, and update availHead.

Question 8

What is the purpose of the getFreeIndex() function?

Answer 8

It determines the index for inserting a new node, either from the avail list or at the file end.

Question 9

Why are file indices used instead of pointers in file-based data structures?

Answer 9

Indices are persistent and can reference positions in the file across executions.

Question 10

What problems can arise if the binary file storing the linked list gets corrupted?

Answer 10

Invalid indices, broken list structure, infinite loops, inability to traverse/modify the list, and possible data loss.

Question 11

Define hashing.

Answer 11

Hashing is a technique to map keys to indices in a table using a hash function for efficient data retrieval.

Question 12

What are the properties of a good hash function?

Answer 12

• Uniformly distributes keys
• Minimizes collisions
• Is deterministic
• Is efficient to compute.

Question 13

Describe the Mid-Square Method for hashing with a table size of 10.

Answer 13

Square the key, extract middle digits, and take mod table size.

Question 14

What is a collision in hashing?

Answer 14

A collision occurs when two different keys hash to the same index.

Question 15

Explain rehashing.

Answer 15

Rehashing means creating a bigger table and reinserting all elements when the current table is too full.

Question 16

Compare chaining and bucket hashing.

Answer 16

Chaining links collided elements in a linked list at each index; bucket hashing uses fixed-size arrays.

Question 17

What is the cycle property of MSTs?

Answer 17

The highest weight edge in any cycle cannot be in the MST.

Question 18

What is the cut property of MSTs?

Answer 18

The smallest weight edge crossing any cut must be in the MST.

Question 19

What data structures are used in Prim’s algorithm?

Answer 19

• Arrays: key[] (min edge weights)
• mstSet[] (included in MST)
• parent[] (MST tree structure).

Question 20

What is the purpose of the find() function in Kruskal’s algorithm?

Answer 20

It identifies the set a vertex belongs to for cycle detection.

Question 21

What is the output of BFS traversal for a graph starting from vertex 0?

Answer 21

0 1 2 3 4

Question 22

What is the time complexity of BFS and DFS for adjacency list?

Answer 22

O(V + E)

Question 23

In a file-based linked list, the avail list is used to keep track of ______.

Answer 23

deleted nodes’ indices for reuse.

Question 24

What is the output of BFS traversal for the given adjacency list graph, starting from vertex 0?

Answer 24

0 1 2 3 4

Question 25

What is the output of BFS traversal for the given adjacency list graph, starting from vertex 0?

Answer 25

0 1 2 3 4 ## Footnote The BFS traversal visits vertices in layers, starting from the specified vertex.

Question 26

What method is used to keep track of deleted nodes' indices for reuse in a file-based linked list?

Answer 26

avail list ## Footnote The avail list helps in efficient memory management for linked lists.

Question 27

How is the hash function for the division method usually expressed?

Answer 27

h(key) = key mod tablesize ## Footnote This formula calculates the index for storing the key in a hash table.

Question 28

In Kruskal’s algorithm, how are edges processed?

Answer 28

in the order of increasing weight ## Footnote This ensures that the minimum spanning tree is built with the least weight edges first.

Question 29

What is the primary data structure used for traversal in BFS?

Answer 29

queue ## Footnote The queue allows for the first-in, first-out processing of vertices.

Question 30

What is the space complexity of an adjacency matrix for a graph with V vertices?

Answer 30

O(V^2) ## Footnote The matrix requires space proportional to the square of the number of vertices.

Question 31

True or False: In a binary file, the data is stored in a human-readable format.

Answer 31

False ## Footnote Binary files store data in a format that is not directly readable by humans.

Question 32

True or False: A good hash function should always produce unique outputs for different inputs.

Answer 32

False ## Footnote Hash functions can produce collisions, where different inputs yield the same output.

Question 33

True or False: The avail list in a file-based linked list helps reduce disk space usage.

Answer 33

True ## Footnote By tracking deleted nodes, the avail list allows for memory reuse.

Question 34

True or False: Prim’s algorithm can only be applied to directed graphs.

Answer 34

False ## Footnote Prim's algorithm is designed for undirected graphs.

Question 35

True or False: DFS can be implemented both recursively and iteratively.

Answer 35

True ## Footnote Both methods are valid for depth-first search implementation.