3.6 Exercises¶

3.6.1 Check your understanding¶

For each situation below, choose a linear, tree, or network structure based on the relationships between the data, and explain your choice:

Students stand in a line, each concerned only with the people immediately in front of and behind them.
A school is organized in a hierarchy: school → grade → class.
City roads connect intersections. An intersection can lead to several others, and the roads may form cycles.

Reference answer

A linear structure. Apart from the first and last people, each person has exactly one neighbor in front and one behind, forming a line of relationships.
A tree structure. Each class belongs to a grade, and each grade belongs to the school, forming a hierarchy from top to bottom.
A network structure. An intersection can connect to several others, and routes can form cycles. These relationships cannot be arranged in a single sequence or a strict hierarchy.

To identify a structure, first examine the relationships between its elements, rather than how much memory it occupies.

Consider two simplified memory layouts for storing the logical sequence A → B → C:

Layout A: A, B, C are stored in memory cells numbered 20, 21, 22, respectively.
Layout B: A, B, C are stored in cells numbered 20, 7, 31, respectively. A records the location of B, and B records the location of C.

Which layout uses contiguous storage, and which uses noncontiguous storage?
Which layout is more like an array, and which is more like a linked list?
The cell numbers in layout B are not in ascending order. Why can it still represent the logical sequence A → B → C?

Reference answer

Layout A uses consecutive memory cells, so its storage is contiguous. In layout B, nodes occupy separate locations, so its storage is noncontiguous.
Layout A is more like an array; layout B is more like a linked list.
The logical order is determined by the links recorded between nodes, not by the numerical order of their memory cell numbers. The location stored in A leads to B, and the location stored in B leads to C, so we can still visit A, B, C in sequence.

This also shows that logical and physical structure are two ways of looking at the same data.

A study group records whether four students have submitted their homework, in seating order:

[true, false, true, true]

Which basic data type is suitable for each element?
These four elements form a sequence in seating order. What logical structure does this use?
If the group later records homework scores instead, as [90, 0, 85, 100], has the type of content changed, or the way it is organized? Explain.

Reference answer

Each element represents only yes or no, so the Boolean type bool is appropriate.
The elements form a linear structure in seating order and can be stored in an array.
The content type has changed: the elements are now integers instead of Boolean values. Their organization has not changed. The data still forms a sequence in seating order and can still use the linear structure of an array.

A basic data type describes what is stored; a data structure describes how the data is organized.

Given a nonnegative integer n, count the ones in its binary representation.

Use bitwise operations. Do not convert the binary representation to a string or use a built-in function that counts the ones directly.

Hints

n & 1 extracts the rightmost bit of n, allowing you to check whether it is 1.
Shifting right by one bit discards the current rightmost bit; most languages use the >> operator.
After implementing the method that checks each bit and shifts right, observe that n & (n - 1) changes the rightmost 1 in n to 0.