1) Base of hexadecimal number system? Answer : 16 2) Universal gate in digital logic? Answer : NAND 3) Memory type that is non-volatile? Answer : ROM 4) Basic building block of digital circuits? Answer : Gate 5) Device used for data storage in sequential circuits? Answer : Flip-flop 6) Architecture with shared memory for instructions and data? Answer : von Neumann 7) The smallest unit of data in computing? Answer : Bit 8) Unit that performs arithmetic operations in a CPU? Answer : ALU 9) Memory faster than main memory but smaller in size? Answer : Cache 10) System cycle that includes fetch, decode, and execute? Answer : Instruction 11) Type of circuit where output depends on present input only? Answer : Combinational 12) The binary equivalent of decimal 10? Answer : 1010 13) Memory used for high-speed temporary storage in a CPU? Answer : Register 14) Method of representing negative numbers in binary? Answer : Two's complement 15) Gate that inverts its input signal? Answer : NOT 16)...
CLASSIFICATION OF DATA STRUCTURES
Data structures are generally categorized into two classes: primitive and non-primitive data structures.
Primitive and Non-primitive Data Structures
Primitive data structures are the fundamental data types which are supported by a programming language. Some basic data types are integer, real, character, and boolean. The terms ‘data type’, ‘basic data type’, and ‘primitive data type’ are often used interchangeably.
Non-primitive data structures are those data structures which are created using primitive data structures. Examples of such data structures include linked lists, stacks, trees, and graphs.
Non-primitive data structures can further be classified into two categories: linear and non-lineardata structures.
Linear and Non-linear Structures
If the elements of a data structure are stored in a linear or sequential order, then it is a linear data structure. Examples include arrays, linked lists, stacks, and queues. Linear data structures can be
represented in memory in two different ways. One way is to have to a linear relationship between elements by means of sequential memory locations. The other way is to have a linear relationship
between elements by means of links.
However, if the elements of a data structure are not stored in a sequential order, then it is a non-linear data structure. The relationship of adjacency is not maintained between elements of a
non-linear data structure. Examples include trees and graphs.
C supports a variety of data structures. We will now introduce all these data structures and they would be discussed in detail in subsequent chapters.
Arrays
An array is a collection of similar data elements. These data elements have the same data type. The elements of the array are stored in consecutive memory locations and are referenced by an index (also known as the subscript).
In C, arrays are declared using the following syntax:
type name[size];
For example,
int marks[10];
The above statement declares an array marks that contains 10 elements. In C, the array index starts from zero. This means that the array marks will contain 10 elements in all. The first element will
be stored in marks[0], second element in marks[1], so on and so forth. Therefore, the last element, that is the 10th element, will be stored in marks[9]. In the memory, the array will be stored
Arrays are generally used when we want to store large amount of similar type of data. But they have the following limitations:
* Arrays are of fixed size.
* Data elements are stored in contiguous memory locations which may not be always available.
* Insertion and deletion of elements can be problematic because of shifting of elements from their positions.
However, these limitations can be solved by using linked lists.
Linked Lists
A linked list is a very flexible, dynamic data structure in which elements (called nodes) form a sequential list. In contrast to static arrays, a programmer need not worry about how many elements will be stored in the linked list. This feature enables the programmers to write robust programs
which require less maintenance.
In a linked list, each node is allocated space as it is added to the list. Every node in the list points to the next node in the list. Therefore, in a linked list, every node contains the following two types of data:
* The value of the node or any other data that corresponds to that node
* A pointer or link to the next node in the list
The last node in the list contains a NULL pointer to indicate that it is the end or tail of the list. Since the memory for a node is dynamically allocated when it is added to the list, the total number of nodes that may be added to a list is limited only by the amount of memory available.
Stacks
A stack is a linear data structure in which insertion and deletion of elements are done at only one end, which is known as the top of the stack. Stack is called a last-in, first-out (LIFO) structure because the last element which is added to the stack is the first element which is deleted from the stack.
In the computer’s memory, stacks can be implemented using arrays or linked lists.The below figshows the array implementation of a stack.
Every stack has a variable top associated with it. top is used to store the address of the topmost element of the stack. It is this position from where the element will be added or deleted. There is another variable MAX, which is used to store the maximum number of elements that the stack can store.
If top = NULL, then it indicates that the stack is empty and if top = MAX–1, then the stack is full.
top = 4, so insertions and deletions will be done at this position. Here, the stack
can store a maximum of 10 elements where the indices range from 0–9. In the above stack, five more elements can still be stored.
A stack supports three basic operations: push, pop, and peep. The push operation adds an element to the top of the stack. The pop operation removes the element from the top of the stack. And the peep operation returns the value of the topmost element of the stack (without deleting it).
However, before inserting an element in the stack, we must check for overflow conditions. An overflow occurs when we try to insert an element into a stack that is already full.
Similarly, before deleting an element from the stack, we must check for underflow conditions. An underflow condition occurs when we try to delete an element from a stack that is already empty.
Queues
A queue is a first-in, first-out (FIFO) data structure in which the element that is inserted first is the first one to be taken out. The elements in a queue are added at one end called the rear and removed from the other end called the front. Like stacks, queues can be implemented by using
either arrays or linked lists.
Every queue has front and rear variables that point to the position from where deletions and insertions can be done, respectively.
Here, front = 0 and rear = 5. If we want to add one more value to the list, say, if we want to add another element with the value 45, then the rear would be incremented by 1 and the value would be stored at the position pointed by the rear. The queue, after the addition, would be as
shown in below figure.
Here, front = 0 and rear = 6. Every time a new element is to be added, we will repeat the same procedure
Now, if we want to delete an element from the queue, then the value of front will be incremented. Deletions are done only from this end of the queue. The queue after the deletion will be as shown in below figure.
However, before inserting an element in the queue, we must check for overflow conditions. An overflow occurs when we try to insert an element into a queue that is already full. A queue is full when rear = MAX–1, where MAX is the size of the queue, that is MAX specifies the maximum number of elements in the queue. Note that we have written MAX–1 because the index starts from 0.
Similarly, before deleting an element from the queue, we must check for underflow conditions. An underflow condition occurs when we try to delete an element from a queue that is already empty. If front = NULL and rear = NULL, then there is no element in the queue.
Trees
A tree is a non-linear data structure which consists of a collection of nodes arranged in a hierarchical order. One of the nodes is designated as the root node, and the remaining nodes can be partitioned
into disjoint sets such that each set is a sub-tree of the root.
The simplest form of a tree is a binary tree. A binary tree consists of a root node and left and right sub-trees, where both sub-trees are also binary trees. Each node contains a data element, a left pointer which points to the left sub-tree, and a right pointer which points to the right sub-tree. The root element is the topmost node which is pointed by a ‘root’ pointer. If root = NULL then the tree is empty.
Below figure shows a binary tree,
where R is the root node and T1 and T2 are the left and right sub-trees of R. If T1 is non-empty, then T1 is said to be the left successor of R. Likewise, if T2is non-empty, then it is called the right successor of R.node 2 is the left child and node 3 is the right child of the root node 1. Note that the left sub-tree of the root node consists of the nodes 2, 4, 5, 8, and 9. Similarly, the right sub-tree of the root node consists of
the nodes 3, 6, 7, 10, 11, and 12.
Graphs
A graph is a non-linear data structure which is a collection of vertices (also
called nodes) and edges that connect these vertices. A graph is often viewed
as a generalization of the tree structure, where instead of a purely parent-to-child relationship between tree nodes, any kind of complex relationships between the nodes can exist.
In a tree structure, nodes can have any number of children but only one parent, a graph on the other hand relaxes all such kinds of restrictions. Figure shows a graph with five nodes.
A node in the graph may represent a city and the edges connecting the nodes can represent roads.
A graph can also be used to represent a computer network where the nodes are workstations and the edges are the network connections. Graphs have so many applications in computer science and mathematics that several algorithms have been written to perform the standard graph operations, such as searching the graph and finding the shortest path between the nodes of a graph.
Note that unlike trees, graphs do not have any root node. Rather, every node
in the graph can be connected with every another node in the graph. When two
nodes are connected via an edge, the two nodes are known as neighbours. For
example, in Fig. , node A has two neighbours: B and D.