Data Types and Structures：练习题

Which of the following describes the fundamental property of an Abstract Data Type (ADT)?

A 1D array Arr contains 8 elements. During a bubble sort (ascending), the following comparisons are made in the first pass:
\(Arr[1]\) vs \(Arr[2]\), \(Arr[2]\) vs \(Arr[3]\), ..., \(Arr[7]\) vs \(Arr[8]\).

If the array is [12, 5, 8, 1, 15, 7, 3, 10], what is the value of the element at index 8 after the completion of the first pass?

A queue is implemented using a 1D array of size 10, named MyQueue, with two pointers: HeadPointer (points to the first element) and TailPointer (points to the last element added).

If the queue is currently empty and HeadPointer is 0, what are the values of the pointers after three elements are added (ENQUEUE) and then one element is removed (DEQUEUE)? (Assume the first index is 0)

In pseudocode, which data type is most appropriate for a variable that must only store the value TRUE or FALSE?

In a linked list, what is the specific purpose of a null pointer?

A 1D array named TemperatureData contains 365 real numbers representing daily recordings. Identify the technical term used to refer to the individual position of a specific value within this array, and state the typical data type used for this purpose.

A programmer needs to store the results of a science experiment where 50 different sensors each record a temperature reading at 10 distinct time intervals throughout the day.

Identify the most appropriate data structure to store all these readings and state the total number of elements it would contain.

A programmer is implementing a Linked List using two 1D arrays: DataArray and PointerArray. Currently, the list contains three names in the following logical order: "Alpha", "Beta", "Gamma".

Assume "Alpha" is stored at index 3 and "Beta" is stored at index 1. Describe the value that must be stored in PointerArray[3] and explain why this value is necessary to maintain the linked structure.

A programmer needs to store a set of related data for a library's digital catalog. Each book entry requires a unique ID number, the title of the book, the date it was last borrowed, and a flag indicating if it is currently available.

(a) Define a composite data type named BookRecord in pseudocode to store these four pieces of data. (3 points)

(b) State the most appropriate primitive data type for each field defined in part (a). (2 points)

Abstract Data Types (ADTs) can be implemented using existing data structures.

(a) Describe how a Stack ADT behaves differently from a Queue ADT when removing items. (2 points)

(b) A linear array Q[1:10] is used to implement a queue. Explain the logic of a Circular Queue and why it is more efficient than a simple linear queue for this array. (3 points)