CSC301: Data Structures

Flashcards covering key concepts from the CSC301 Data Structures course, including definitions, terminology, and classifications related to data structures.

What are the main topics covered in the CSC301 Data Structures course?

Primitive types, arrays, records, strings and string processing, data representation in memory, stack and heap allocation, queues, trees.

What is the logical or mathematical model of a particular organization of data called?

Data structure.

What are the five considerations for choosing a particular data model?

Short access time, ease of update, economy of storage, simple maintenance, reliability.

What is an entity in the context of data structures?

An entity is something that has certain attributes or properties which may be assigned values.

What is the difference between data items and group items?

Data items are single units of values, while group items are data items divided into sub-items.

What does the term 'field' represent in data structures?

A single elementary unit of information representing an attribute of an entity.

How are records classified in data structures?

Records are classified into fixed-length records and variable-length records.

What defines a fixed-length record?

All records contain the same data items with the same amount of space assigned to each data item.

How are variable-length records different from fixed-length records?

Variable-length records can contain different lengths and may have a minimum and maximum length.

What is a primary key in the context of files in data structures?

A field in a record that uniquely determines the record in the file.

What are the two classifications of data structures?

Primitive data structures and non-primitive data structures.

What are primitive data structures?

Fundamental data types supported by a programming language, such as integers, reals, characters, and booleans.

What are non-primitive data structures?

Data structures created using primitive data structures, such as arrays, linked lists, queues, stacks, trees, and graphs.

What is a linear data structure?

A data structure where elements form a sequence or a linear list.

What is an array in the context of data structures?

A linear data structure consisting of a list of similar data elements referenced by consecutive numbers.

How is a two-dimensional array defined?

A collection of similar data elements where each element is referenced by two subscripts.

What distinguishes a binary tree?

A binary tree is a finite set of elements called nodes, with a distinguished node called the root, and each node can have at most two successors.

What are terminal nodes in a binary tree?

Nodes with no successors.

What is the height of a tree?

The maximum number of nodes in a branch of the tree.

What does the term 'root' refer to in a tree?

The top node in a tree.

What is a path in a binary tree?

A sequence of edges connecting nodes.

What is the significance of sibling nodes in a tree?

Sibling nodes are nodes that share the same parent.

What is a leaf node in a tree structure?

A node with no children, also called a terminal node.

What does the degree of a node refer to in a tree?

The number of subtrees of a node.

What is an internal node in terms of tree structures?

A node with at least one child.

What is a non-terminal node?

A node that is not a terminal node.

What does the level of a node in a tree indicate?

The level denotes the node's distance from the root, with the root assigned level number 0.

Define a descendant of a node in a tree.

A node reachable by proceeding from parent to child repeatedly.

What is a predecessor in a tree?

The unique parent of a node.

What is used to represent an algebraic expression using trees?

Each variable or constant in the expression appears in an internal node in a binary tree.

What is an edge in a binary tree?

A line drawn from a node to its successor.