Skip to content

3.6   Exercises

3.6.1   Concept Review

1.   Data Relationships in Everyday Situations

Based on the relationships among the data, choose one of "linear structure," "tree structure," and "network structure" for each situation below, and explain why:

  1. Students stand in a line; we consider only each student's immediate neighbors in front of and behind them.
  2. A school is organized in levels: "school → grade → class."
  3. City roads connect many intersections. One intersection may lead to several others, and the roads may form cycles.
Answer

  1. This is a linear structure. Except for the first and last students, each person is adjacent to exactly one person in front and one behind, so the relationships extend along a single line.

  2. This is a tree structure. Each class belongs to one grade, and each grade belongs to the school, so the relationships form levels from top to bottom.

  3. This is a network structure. An intersection can connect to several other intersections, and the routes can form cycles, so they cannot be arranged in a single order or a strict hierarchy.

    To identify a structure, first examine the relationships among the elements rather than how much space it uses in memory.

2.   Storing a Logical Order in Memory

Consider two simplified memory layouts for storing the logical order 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 memory cells numbered 20, 7, 31, respectively. A records the location of B, and B records the location of C.
  1. Which layout uses contiguous-space storage, and which uses dispersed-space storage?
  2. Which layout is more like an array, and which is more like a linked list?
  3. The memory-cell numbers in Layout B are not in increasing order. Why can it still represent the logical order A → B → C?
Answer

  1. Layout A uses consecutive memory cells, so it uses contiguous-space storage. The nodes in Layout B are scattered across different locations, so it uses dispersed-space storage.

  2. Layout A is more like an array, and Layout B is more like a linked list.

  3. The logical order is determined by the links recorded between nodes, not by the numerical order of the memory-cell numbers. The location stored by A leads to B, and the location stored by B then leads to C, so A, B, C can still be visited in order.

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

3.   Data Types and Structures in Homework Records

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

[true, false, true, true]

  1. Which basic data type is suitable for each element?
  2. The four elements are arranged in a line by seating order. What logical structure does this use?
  3. Suppose the group later records each student's homework score as [90, 0, 85, 100]. Does this change the data's "content type" or its "organization"? Explain why.
Answer

  1. Each element represents only "yes" or "no," so the Boolean type bool is suitable.

  2. The elements are arranged in seating order, forming a linear structure that can be stored in an array.

  3. The content type changes: the elements change from Boolean values to integers. The organization does not change. The data is still arranged in a line by seating order and can still be stored in an array, which is a linear structure.

    A basic data type describes "what is stored," while a data structure describes "how the data is organized."

3.6.2   Programming Exercises

1.   Count the 1s in a Binary Representation

Given a non-negative integer n, count the number of 1s in its binary representation.

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

Hints
  1. n & 1 extracts the rightmost bit of n, which tells you whether that bit is 1
  2. Shifting right by one discards the current rightmost bit; most languages use the operator >>
  3. After implementing the method that checks and shifts one bit at a time, observe that n & (n - 1) turns the rightmost 1 in n into 0

LeetCode

Feel free to drop your insights, questions or suggestions