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)...
BASIC TERMINOLOGY
Our aim has been to design good programs, where a good program is defined as a program that
* runs correctly
* is easy to read and understand
* is easy to debug and
* is easy to modify.
A program should undoubtedly give correct results, but along with that it should also run efficiently. A program is said to be efficient when it executes in minimum time and with minimum memory space. In order to write efficient programs we need to apply certain data management concepts.
The concept of data management is a complex task that includes activities like data collection, organization of data into appropriate structures, and developing and maintaining routines for quality assurance.
Data structure is a crucial part of data management and in this book it will be our prime concern. A data structure is basically a group of data elements that are put together under one name, and which defines a particular way of storing and organizing data in a computer so that it can be used efficiently.
Data structures are used in almost every program or software system. Some common examples of data structures are arrays, linked lists, queues, stacks, binary trees, and hash tables. Data structures
are widely applied in the following areas:
* Compiler design * Operating system
* Statistical analysis package * DBMS
* Numerical analysis * Simulation
* Artificial intelligence * Graphics
When you will study DBMS as a subject, you will realize that the major data structures used in the Network data model is graphs, Hierarchical data model is trees, and RDBMS is arrays.
Specific data structures are essential ingredients of many efficient algorithms as they enable the programmers to manage huge amounts of data easily and efficiently. Some formal design methods
and programming languages emphasize data structures and the algorithms as the key organizing factor in software design. This is because representing information is fundamental to computer science. The primary goal of a program or software is not to perform calculations or operations
but to store and retrieve information as fast as possible.
Be it any problem at hand, the application of an appropriate data structure provides the most efficient solution. A solution is said to be efficient if it solves the problem within the required resource constraints like the total space available to store the data and the time allowed to perform
each subtask. And the best solution is the one that requires fewer resources than known alternatives. Moreover, the cost of a solution is the amount of resources it consumes. The cost of a solution is
basically measured in terms of one key resource such as time, with the implied assumption that the solution meets the other resource constraints.
Today computer programmers do not write programs just to solve a problem but to write an efficient program. For this, they first analyse the problem to determine the performance goals that must be achieved and then think of the most appropriate data structure for that job. However,
program designers with a poor understanding of data structure concepts ignore this analysis step and apply a data structure with which they can work comfortably. The applied data structure may not be appropriate for the problem at hand and therefore may result in poor performance (like slow speed of operations).
Conversely, if a program meets its performance goals with a data structure that is simple to use, then it makes no sense to apply another complex data structure just to exhibit the programmer’s
skill. When selecting a data structure to solve a problem, the following steps must be performed.
1. Analysis of the problem to determine the basic operations that must be supported. For example, basic operation may include inserting/deleting/searching a data item from the data structure.
2. Quantify the resource constraints for each operation.
3. Select the data structure that best meets these requirements.
This three-step approach to select an appropriate data structure for the problem at hand supports a data-centred view of the design process. In the approach, the first concern is the data and the operations that are to be performed on them. The second concern is the representation of the data, and the final concern is the implementation of that representation.
There are different types of data structures that the C language supports. While one type of data structure may permit adding of new data items only at the beginning, the other may allow it to
be added at any position. While one data structure may allow accessing data items sequentially, the other may allow random access of data. So, selection of an appropriate data structure for the
problem is a crucial decision and may have a major impact on the performance of the program.
Elementary Data Structure Organization
Data structures are building blocks of a program. A program built using improper data structures may not work as expected. So as a programmer it is mandatory to choose most appropriate data structures for a program.
The term data means a value or set of values. It specifies either the value of a variable or a constant (e.g., marks of students, name of an employee, address of a customer, value of pi, etc.).
While a data item that does not have subordinate data items is categorized as an elementary item, the one that is composed of one or more subordinate data items is called a group item. For
example, a student’s name may be divided into three sub-items—first name, middle name, and last name—but his roll number would normally be treated as a single item.
A record is a collection of data items. For example, the name, address, course, and marks obtained are individual data items. But all these data items can be grouped together to form a record.
A file is a collection of related records. For example, if there are 60 students in a class, then there are 60 records of the students. All these related records are stored in a file. Similarly, we can have a file of all the employees working in an organization, a file of all the customers of a company, a file of all the suppliers, so on and so forth.
Moreover, each record in a file may consist of multiple data items but the value of a certain data item uniquely identifies the record in the file. Such a data item K is called a primary key, and the values K1
, K2 ... in such field are called keys or key values. For example, in a student’s
record that contains roll number, name, address, course, and marks obtained, the field roll number is a primary key. Rest of the fields (name, address, course, and marks) cannot serve as primary keys, since two or more students may have the same name, or may have the same address (as they might be staying at the same place), or may be enrolled in the same course, or have obtained same marks.