CS6302-DATABASE MANAGEMENT SYSTEMS Two Marks Questions With Answers 2014

Anna University, Chennai

Anna_University,_Chennai_logo

DHANALAKSHMI SRINIVASAN INSTITUTE OF RESEARCH AND TECHNOLOGY

SIRUVACHUR, PERAMBALUR – 611 113

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING CS6302-DATABASE MANAGEMENT SYSTEMS QUESTION BANK/TWO MARKS

UNIT: 1- INTRODUCTION

1. Who is a DBA? What are the responsibilities of a DBA? April/May-2011

A database administrator (short form DBA) is a person responsible for the design, implementation, maintenance and repair of an organization's database. They are also known by

the titles Database Coordinator or Database Programmer, and is closely related to the Database

Analyst, Database Modeller, Programmer Analyst, and Systems Manager.

The role includes the development and design of database strategies, monitoring and improving database performance and capacity, and planning for future expansion requirements. They may also plan, co-ordinate and implement security measures to safeguard the database

2. What is a data model? List the types of data model used. April/May-2011

A database model is the theoretical foundation of a database and fundamentally determines in

which manner data can be stored, organized, and manipulated in a database system. It thereby defines the infrastructure offered by a particular database system. The most popular example of a database model is the relational model.

Types of data model used

Ø Hierarchical model

Ø Network model

Ø Relational model

Ø Entity-relationship

Ø Object-relational model

Ø Object model

3. Define database management system?

Database management system (DBMS) is a collection of interrelated data and a set of programs to access those data.

4. List any eight applications of DBMS.

a) Banking

b) Airlines

c) Universities

d) Credit card transactions e) Tele communication

f) Finance g) Sales

h) Manufacturing

i) Human resources

5. What are the disadvantages of file processing system?

The disadvantages of file processing systems are

a) Data redundancy and inconsistency b) Difficulty in accessing data

c) Data isolation

d) Integrity problems

e) Atomicity problems

f) Concurrent access anomalies

6. What are the advantages of using a DBMS?

The advantages of using a DBMS are a) Controlling redundancy

b) Restricting unauthorized access

c) Providing multiple user interfaces

d) Enforcing integrity constraints. e) Providing backup and recovery

7. Give the levels of data abstraction?

a) Physical level

b) Logical level c) View level

8. Define instance and schema?

Instance: Collection of data stored in the data base at a particular moment is called an Instance of the database.

Schema: The overall design of the data base is called the data base schema.

9. Define the terms

1) Physical schema

2) logical schema.

Physical schema: The physical schema describes the database design at the physical level,

which is the lowest level of abstraction describing how the data are actually stored.

Logical schema: The logical schema describes the database design at the logical level, which

describes what data are stored in the database and what relationship exists among the data.

10. Mention the actors on scene.

Ø Database administrator

Ø Database designer

Ø End users

11. What is conceptual schema?

The schemas at the view level are called subschema‟s that describe different views of the

database.

12. Define data model?

A data model is a collection of conceptual tools for describing data, data relationships, data

13. What is storage manager?

A storage manager is a program module that provides the interface between the low level data

stored in a database and the application programs and queries submitted to the system.

14. What are the components of storage manager?

The storage manager components include

a) Authorization and integrity manager b) Transaction manager

c) File manager

d) Buffer manager

15. What is the purpose of storage manager?

The storage manager is responsible for the following a) Interaction with the file manager

b) Translation of DML commands in to low level file system commands c) Storing, retrieving and updating data in the database

16. List the data structures implemented by the storage manager . The storage manager implements the following data structure

a) Data files

b) Data dictionary c) Indices

17. What is a data dictionary?

A data dictionary is a data structure which stores meta data about the structure of the database ie. the schema of the database.

18. What is an entity relationship model?

The entity relationship model is a collection of basic objects called entities and relationship among those objects. An entity is a thing or object in the real world that is distinguishable from

other objects.

19. What are attributes? Give examples.

An entity is represented by a set of attributes. Attributes are descriptive properties possessed by

each member of an entity set.

Example: possible attributes of customer entity are customer name, customer id, Customer

Street, customer city.

20. What is relationship? Give examples

A relationship is an association among several entities.

Example: A depositor relationship associates a customer with each account that he/she has.

21. Define the terms i) Entity set ii) Relationship set

Relationship set : The set of all relationships of the same type is termed as a relationship set.

22. Define single valued and multivalued attributes.

Single valued attributes: attributes with a single value for a particular entity are called single

valued attributes.

Multivalued attributes : Attributes with a set of value for a particular entity are called

multivalued attributes.

23. What are stored and derived attributes?

Stored attributes: The attributes stored in a data base are called stored attributes.

Derived attributes: The attributes that are derived from the stored attributes are called derived attributes.

24. What are composite attributes?

Composite attributes can be divided in to sub parts.

25. Define null values

In some cases a particular entity may not have an applicable value for an attribute or if we do not know the value of an attribute for a particular entity. In these cases null value is used.

26. Define the terms i) Entity type ii) Entity set

Entity type: An entity type defines a collection of entities that have the same attributes.

Entity set: The set of all entities of the same type is termed as an entity set.

27. What is meant by the degree of relationship set?

The degree of relationship type is the number of participating entity types.

28. Define the terms i) Key attribute

ii) Value set

Key attribute : An entity type usually has an attribute whose values are distinct from each

individual entity in the collection. Such an attribute is called a key attribute.

Value set: Each simple attribute of an entity type is associated with a value set that specifies the

set of values that may be assigned to that attribute for each individual entity.

29. Define weak and strong entity sets?

Weak entity set: entity set that do not have key attribute of their own are called weak entity sets.

Strong entity set: Entity set that has a primary key is termed a strong entity set.

30. What does the cardinality ratio specify?

Mapping cardinalities or cardinality ratios express the number of entities to which another entity

can be associated. Mapping cardinalities must be one of the following:

• One to one

• One to many

• Many to one

31. Explain the two types of participation constraint.

Total: The participation of an entity set E in a relationship set R is said to be total if every

entity in E participates in at least one relationship in R.

Partial: if only some entities in E participate in relationships in R, the participation of entity set

E in relationship R is said to be partial.

32. What is meant by lossless-join decomposition? APRIL/MAY-2011

We claim the above decomposition is lossless. How can we decide whether decomposition is

lossless?

1. Let R be a relation schema.

2. Let F be a set of functional dependencies on R.

3. Let R1and R2 form a decomposition of R.

4. The decomposition is a lossless-join decomposition of R if at least one of the following functional dependencies are in :

a. R1∩ R2→ R1

b. R1∩ R2→ R2

33. List the disadvantages of relational database system

Repetition of data

Inability to represent certain information.

34. What is first normal form?

The domain of attribute must include only atomic (simple, indivisible) values.

35. What is meant by functional dependencies?

Consider a relation schema R and a C R and ß C R. The functional dependency a ß holds on

relational schema R if in any legal relation r(R), for all pairs of tuples t1 and t2 in r such that t1 [a] =t1 [a], and also t1 [ß] =t2 [ß].

36. What are the uses of functional dependencies?

To test relations to see whether they are legal under a given set of functional dependencie s. To specify constraints on the set of legal relations.

37. Explain trivial dependency?

Functional dependency of the form a ß is trivial if ß C a. Trivial functional dependencies are satisfied by all the relations.

38. What are axioms?

Axioms or rules of inference provide a simpler technique for reasoning about functional dependencies.

39. What is meant by computing the closure of a set of functional dependency?

+ The closure of F denoted b y F is the set of functional dependencies logically implied by F.

40. What is meant by normalization of data?

It is a process of analyzing the given relation schemas based on their Functional Dependencies

(FDs) and primary key to achieve the properties

Ø Minimizing redundancy

Ø Minimizing insertion, deletion and updating anomalies


UNIT:2-RELATIONAL MODEL

1. Define the terms i) DDL ii) DML

DDL: Data base schema is specified by a set of definitions expressed by a special language

called a data definition language.

DML:

A data manipulation language is a language that enables users to access or manipulate data as organized by the appropriate data model

2. What is embedded SQL? What are its advantages? April/May-2011

Embedded SQL is a method of combining the computing power of a programming language and the database manipulation capabilities of SQL. Embedded SQL statements are SQL statements

written in line with the program source code of the host language. The embedded SQL

statements are parsed by an embedded SQL preprocessor and replaced by host-language calls to

a code library. The output from the preprocessor is then compiled by the host compiler. This allows programmers to embed SQL statements in programs written in any number of languages such as: C/C++, COBOL and Fortran

3. Write short notes on relational model

The relational model uses a collection of tables to represent both data and the relationships

among those data. The relational model is an example of a record based model.

4. Define tuple and attribute

Attributes: column headers

Tuple : Row

5. Define the term relation.

Relation is a subset of a Cartesian product of list domains.

6. Define tuple variable

Tuple variable is a variable whose domain is the set of all tuples.

7. Define the term Domain.

For each attribute there is a set of permitted values called the domain of that attribute.

8. What is a candidate key?

9. What is a primary key?

Primary key is chosen by the database designer as the principal means of identifying an entit y in

the entity set.

10. What is a super key?

A super key is a set of one or more attributes that collectively allows us to identify uniquely an entity in the entity set.

11. List the table modification commands in SQL?

Ø Deletion

Ø Insertion

Ø Updates

Ø Update of a view


UNIT:3-TRANSACTION PROCESSING AND CONCURRENCY CONTROL

1. What are the ACID properties? APRIL/MAY-2011

(atomicity, consistency, isolation, durability) is a set of properties that guarantee database

transactions are processed reliably. In the context of databases, a single logical operation on the data is called a transaction. For example, a transfer of funds from one bank account to another, even though that might involve multiple changes (such as debiting one account and crediting another), is a single transaction.

2. What are two pitfalls (problem) of lock-based protocols? APRIL/MAY-2011

Ø Deadlock

Ø Starvation

3. What is transaction?

Collections of operations that form a single logical unit of work are called transactions.

4. What are the two statements regarding transaction?

The two statements regarding transaction of the form:

Ø Begin transaction

Ø End transaction

5. What are the properties of transaction?

The properties o f transactions are:

Ø Atomicity

Ø Consistency

Ø Isolation

Ø Durability

6. What is recovery management component?

Ensuring durability is the responsibility of a software component of the base system called the

recovery management component.

7. When is a transaction rolled back?

Any changes that the aborted transaction made to the database must be undone. Once the changes caused by an aborted transaction have been undone, then the transaction has been rolled

back.

8. What are the states of transaction?

The states of transaction are

Ø Active

Ø Partially committed

Ø Failed

Ø Aborted

Ø Committed

Ø Terminated

Ø

9. List out the statements associated with a database transaction?

Ø Commit work

Ø Rollback work

10. What is a shadow copy scheme?

It is simple, but efficient, scheme called the shadow copy schemes. It is based o n making copies of the database called shadow copies that one transaction is active at a time. The scheme also

assumes that the database is simply a file on disk.

11. Give the reasons for allowing concurrency?

The reasons for allowing concurrency is if the transactions run serially, a short transaction may

have to wait for a preceding long transaction to complete, which can lead to unpredictable delays in running a transaction. So concurrent execution reduces the unpredictable delays in running transactions.

12. What is average response time?

The average response time is that the average time for a transaction to be completed after it has

been submitted.

13. What are the two types of serializability?

The two types of serializability is

Ø Conflict serializability

Ø View serializability

14. Define lock?

Lock is the most common used to implement the requirement is to allow a transaction to access a data item only if it is currently holding a lock on that item.

15. What are the different modes of lock?

The modes of lock are:

16. Define deadlock?

Ø Exclusive

Neither of the transaction can ever proceed with its normal execution. This situation is called deadlock.

17. Define the phases of two phase locking protocol

Growing phase: a transaction may obtain locks but not release any lock.

Shrinking phase: a transaction may release locks but may not obtain any new locks.

18. Define upgrade and downgrade?

It provides a mechanism for conversion from shared lock to exclusive lock is known as upgrade. It provides a mechanism for conversion from exclusive lock to shared lock is known as

downgrade.

19. What is a database graph?

The partial ordering implies that the set D may now be viewed as a directed acyclic graph, called

a database graph.

20. What are the two methods for dealing deadlock problem?

The two methods for dealing deadlock problem is deadlock detection and deadlock recovery.

21. What is a recovery scheme?

An integral part of a database system is a recovery scheme that can restore the database to the consistent state that existed before the failure.

22. What are the two types of errors?

The two types of errors are:

Ø Logical error

Ø System error

23. What are the storage types?

The storage types are:

Ø Volatile storage

Ø Nonvolatile storage

24. Define blocks?

The database system resides permanently on nonvolatile storage, and is partitioned into fixed- length storage units called blocks.

25. What is meant by Physical blocks?

The input and output operations are done in block units. The blocks residing on the disk are referred to as physical blocks.

26. What is meant by buffer blocks?

The blocks residing temporarily in main memory are referred to as buffer blocks.

27. What is meant by disk buffer?

The area of memory where blocks reside temporarily is called the disk buffer.

28. What is meant by log-based recovery?

The most widely used structures for recording database modifications is the log. The log is a

sequence of log records, recording all the update activities in the database. There are several types of log records.

29. What are uncommitted modifications?

The immediate-modification technique allows database modifications to be output to the database while the transaction is still in the active state. Data modifications written by active

transactions are called uncommitted modifications.

30. Define shadow paging.

An alternative to log-based crash recovery technique is shadow paging. This technique needs

fewer disk accesses than do the log-based methods.

31. Define page.

The database is partitioned into some number of fixed-length blocks, which are referred to as

pages.

32. Explain current page table and shadow page table.

The key idea behind the shadow paging technique is to maintain two page tables during the life

of the transaction: the current page table and the shadow p age table. Both the page tables are identical when the transaction starts. The current page table may b e changed when a transaction performs a write operation.

33. What are the drawbacks of shadow-paging technique?

Ø Commit Overhead

Ø Data fragmentation

Ø Garbage collection

34. Define garbage collection.

Garbage may be created also as a side effect of crashes. Periodically, it is necessary to find all the garbage pages and to add them to the list of free pages. This process is called garbage

collection.

35. Differentiate strict two phase locking protocol and rigorous two phase locking protocol.

In strict two phase locking protocol all exclusive mode locks taken by a transaction is held

36. How the time stamps are implemented

• Use the value of the system clock as the time stamp. That is a transactio n‟s time stamp is equal

to the value of the clock when the transaction enters the system.

• Use a logical counter that is incremented after a new timestamp has been assigned; that is the

time stamp is equal to the value of the counter.

37. What are the time stamps associated with each data item?

• W-timestamp (Q) denotes the largest time stamp if any transaction that executed WRITE (Q)

successfully.

• R-timestamp (Q) denotes the largest time stamp if any transaction that executed READ (Q)

successfully.


UNIT:4-TRENDS IN DATABASE TECHNOLOGY

1. What are the advantages and disadvantages of indexed sequential file? APRIL/MAY-

2011

The advantage of ordering records in a sequential file according to a key is that you can then

search the file more quickly. If you know the key value that you want, you can use one of the relatively fast searches. The disadvantage is that when you insert, you need to rewrite at least everything after the insertion point, which makes inserts very expensive unless they are done at the end of the file. An indexed file approach keeps a (hopefully) small part of each row, and some kind of "pointer" to the row's location within the data file. This allows a search to use the index, which is ordered by the index and (again hopefully) much smaller and therefore much faster than scanning the entire data file for the indexed data.

2. What is database tuning? APRIL/MAY-2011

Database tuning describes a group of activities used to optimize and homogenize the

performance of a database. It usually overlaps with query tuning, but refers to design of the database files, selection of the database management system (DBMS), operating system and CPU the DBMS runs on.

3. Give the measures of quality of a disk.

Capacity

Access time

Seek time

Data transfer rate

Reliability

Rotational latency time.

Cheaper than disk Expensive when compared with disk

5. What are the types of storage devices?

Ø Primary storage

Ø Secondary storage

Ø Tertiary storage

6. Define average seek time.

The average seek time is the average of the seek times, measured over a sequence of random

requests.

7. Define rotational latency time.

The time spent waiting for the sector to be accessed to appear under the head is called the

rotational latency time.

8. Define average latency time.

The average latency time of the disk is one-half the time for a full rotation of the disk.

9. What is meant by data-transfer rate?

The data-transfer rate is the rate at which data can be retrieved from or stored to the disk.

10. What is meant by mean time to failure?

The mean time to failure is the amount of time that the system could run continuously without

failure.

11. What are a block and a block number?

A block is a contiguous sequence of sectors from a single track of one platter. Each request

specifies the address on

the disk to be referenced. That address is in the form of a block number.

12. What are called journaling file systems?

File systems that support log disks are called journaling file systems.

13. What is the use of RAID?

A variety of disk-organization techniques, collectively called redundant arrays of independent

disks are used to improve the performance and reliability.

14. Explain how reliability can be improved through redundancy?

The simplest approach to introducing redundancy is to duplicate every disk. This technique is called mirroring or shadowing. A logical disk then consists of two physical disks, and write is

carried out on both the disk. If one of the disks fails the data can be read from the other. Data will be lost if the second disk fails before the first fail ed disk is repaired.

15. What is called mirroring?

The simplest approach to introducing redundancy is to duplicate every disk. This technique is called mirroring or shadowing.

16. What is meant by Multi-dimensional database?

A multi-dimensional database is a computer software system designed to allow for efficient and

convenient storage and retrieval of large volumes of data that is (1) intimately related and (2) stored, viewed and analyzed from different perspectives and these perspectives are called dimensions.

17. What is meant by Spatial database?

A spatial database is a database that is optimized to store query data that represents objects

defined in geometric space. Most spatial databases allow representing simple geometric objects such as points, lines and polygons. Some spatial databases handle more complex structures such as 3D objects, topological coverages,etc.

18. What is meant by Mobile database?

A mobile database is a database that resides on mobile device such as a PDA, a smart phone, or a

laptop. Such devices are often limited in resources such as memory, computing power and battery power.


UNIT:5-ADVANCED TOPICS

1. List the threats to databases.

Ø Loss of integrity

Ø Loss of availability

Ø Loss of confidentiality

2. List out the control measures.

Ø Access control

Ø Inference control

Ø Flow control

Ø Data encryption

3. What is meant by Data warehouse?

A data warehouse is a repository (archive) of information gathered from multiple sources, stored under a unified schema at a single site.

Ø Greatly simplifies querying, permits study of historical trends

Ø Shifts decision support query load away from transaction processing

systems

4. Define Data mining.

Ø Sorting

Ø Selection

6. What is the difference between Information Retrieval and DBMS.

S.No

Information Retrieval

DBMS

1

Imprecise semantics

Precise semantics

2

Keyword search

SQL

3

Unstructured data format

Structured data

4

Reads mostly. Adds document

occasionally.

Expects reasonable number of updates.

5

Displays page through top k results.

Generates full answer.

7. List out the functionalities of Data warehouse.

Ø Data cleaning

Ø Data transformation

Ø Data integration

Ø Data loading &

Ø Periodic data refreshing

8. List the types of security mechanisms.

Ø Discretionary security mechanisms

Ø Mandatory security mechanisms

9. What are the database design issues?

Ø Legal and ethical issues

Ø Policy issues

Ø System related issues

10. What are the actions performed by DBA?

Ø Account creation

Ø Privilege granting

Ø Privilege revocation

Ø Security level assignment

11. What is the difference between Database and Data warehouse?

S.No

Database

Data warehouse

1.

Online transaction & query processing is

done in database

Data analysis & decision making is done in

data warehouse

2.

Online Transaction Processing (OLTP) is

carried out in Database.

Online Analytical Processing (OLAP) is

carried out in Database

12. What are the steps for designing a warehouse?

Ø Choose a business process to model

Ø Choose the grain of the business process

Ø Choose the dimensions that will apply to each fact table record

Ø Choose the measures that will populate each fact table record

13. What are the issues in data warehouse design?

Ø When and how to gather data

Ø What schema to use

Ø Data cleansing

Ø How to propagate updates

Ø What data to summarize

14. What are the goals of data mining?

Ø Prediction

Ø Identification

Ø Classification

Ø Optimization

15. List out the types of Discovered knowledge.

Ø Association rules

Ø Classification Hierarchies

Ø Sequential patterns

Ø Patterns within time series

Ø Clustering

16. What is meant by Association rule?

An association rule is of the form X→Y, where X={x1, x2,……. xn} and Y={y1, y2,……. yn} are set of items with xi and yi being distinct items of all i and j. It must satisfy a minimum support and confidence.

17. What is meant by Confidence rule?

Given a rule of the form A→B, rule confidence is the conditional probability that B is true when

A is known to be true.

18. Define Apriori algorithm.

The Apriori algorithm was the first algorithm used to generate association rules. It uses the general algorithm for creating association rules together with downward closure and anti-

monotonicity.

20. What is meant by frequent pattern tree algorithm?

The Frequent pattern tree algorithm reduces the total number of candidate itemsets by producing a compressed version of the database in terms of an FP-tree. The FP-tree stores relevant

information and allows for the efficient description of frequent itemsets. The algorithm consists of 2 steps:

1. Build FP-tree

2. Use the tree to find frequent itemsets.

21. What is meant by Classification?

Classification is the process of learning a model that is able to describe different classes of data.

22. List the applications of data mining.

Ø Marketing

Ø Finance

Ø Resource optimization

Ø Image Analysis

Ø Fraud detection

CS6302-DATABASE MANAGEMENT SYSTEMS Two Marks Questions With Answers 2014

Anna University, Chennai

Anna_University,_Chennai_logo

DHANALAKSHMI SRINIVASAN INSTITUTE OF RESEARCH AND TECHNOLOGY

SIRUVACHUR, PERAMBALUR – 611 113

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING CS6302-DATABASE MANAGEMENT SYSTEMS QUESTION BANK/TWO MARKS

UNIT: 1- INTRODUCTION

1. Who is a DBA? What are the responsibilities of a DBA? April/May-2011

A database administrator (short form DBA) is a person responsible for the design, implementation, maintenance and repair of an organization's database. They are also known by

the titles Database Coordinator or Database Programmer, and is closely related to the Database

Analyst, Database Modeller, Programmer Analyst, and Systems Manager.

The role includes the development and design of database strategies, monitoring and improving database performance and capacity, and planning for future expansion requirements. They may also plan, co-ordinate and implement security measures to safeguard the database

2. What is a data model? List the types of data model used. April/May-2011

A database model is the theoretical foundation of a database and fundamentally determines in

which manner data can be stored, organized, and manipulated in a database system. It thereby defines the infrastructure offered by a particular database system. The most popular example of a database model is the relational model.

Types of data model used

Ø Hierarchical model

Ø Network model

Ø Relational model

Ø Entity-relationship

Ø Object-relational model

Ø Object model

3. Define database management system?

Database management system (DBMS) is a collection of interrelated data and a set of programs to access those data.

4. List any eight applications of DBMS.

a) Banking

b) Airlines

c) Universities

d) Credit card transactions e) Tele communication

f) Finance g) Sales

h) Manufacturing

i) Human resources

5. What are the disadvantages of file processing system?

The disadvantages of file processing systems are

a) Data redundancy and inconsistency b) Difficulty in accessing data

c) Data isolation

d) Integrity problems

e) Atomicity problems

f) Concurrent access anomalies

6. What are the advantages of using a DBMS?

The advantages of using a DBMS are a) Controlling redundancy

b) Restricting unauthorized access

c) Providing multiple user interfaces

d) Enforcing integrity constraints. e) Providing backup and recovery

7. Give the levels of data abstraction?

a) Physical level

b) Logical level c) View level

8. Define instance and schema?

Instance: Collection of data stored in the data base at a particular moment is called an Instance of the database.

Schema: The overall design of the data base is called the data base schema.

9. Define the terms

1) Physical schema

2) logical schema.

Physical schema: The physical schema describes the database design at the physical level,

which is the lowest level of abstraction describing how the data are actually stored.

Logical schema: The logical schema describes the database design at the logical level, which

describes what data are stored in the database and what relationship exists among the data.

10. Mention the actors on scene.

Ø Database administrator

Ø Database designer

Ø End users

11. What is conceptual schema?

The schemas at the view level are called subschema‟s that describe different views of the

database.

12. Define data model?

A data model is a collection of conceptual tools for describing data, data relationships, data

13. What is storage manager?

A storage manager is a program module that provides the interface between the low level data

stored in a database and the application programs and queries submitted to the system.

14. What are the components of storage manager?

The storage manager components include

a) Authorization and integrity manager b) Transaction manager

c) File manager

d) Buffer manager

15. What is the purpose of storage manager?

The storage manager is responsible for the following a) Interaction with the file manager

b) Translation of DML commands in to low level file system commands c) Storing, retrieving and updating data in the database

16. List the data structures implemented by the storage manager . The storage manager implements the following data structure

a) Data files

b) Data dictionary c) Indices

17. What is a data dictionary?

A data dictionary is a data structure which stores meta data about the structure of the database ie. the schema of the database.

18. What is an entity relationship model?

The entity relationship model is a collection of basic objects called entities and relationship among those objects. An entity is a thing or object in the real world that is distinguishable from

other objects.

19. What are attributes? Give examples.

An entity is represented by a set of attributes. Attributes are descriptive properties possessed by

each member of an entity set.

Example: possible attributes of customer entity are customer name, customer id, Customer

Street, customer city.

20. What is relationship? Give examples

A relationship is an association among several entities.

Example: A depositor relationship associates a customer with each account that he/she has.

21. Define the terms i) Entity set ii) Relationship set

Relationship set : The set of all relationships of the same type is termed as a relationship set.

22. Define single valued and multivalued attributes.

Single valued attributes: attributes with a single value for a particular entity are called single

valued attributes.

Multivalued attributes : Attributes with a set of value for a particular entity are called

multivalued attributes.

23. What are stored and derived attributes?

Stored attributes: The attributes stored in a data base are called stored attributes.

Derived attributes: The attributes that are derived from the stored attributes are called derived attributes.

24. What are composite attributes?

Composite attributes can be divided in to sub parts.

25. Define null values

In some cases a particular entity may not have an applicable value for an attribute or if we do not know the value of an attribute for a particular entity. In these cases null value is used.

26. Define the terms i) Entity type ii) Entity set

Entity type: An entity type defines a collection of entities that have the same attributes.

Entity set: The set of all entities of the same type is termed as an entity set.

27. What is meant by the degree of relationship set?

The degree of relationship type is the number of participating entity types.

28. Define the terms i) Key attribute

ii) Value set

Key attribute : An entity type usually has an attribute whose values are distinct from each

individual entity in the collection. Such an attribute is called a key attribute.

Value set: Each simple attribute of an entity type is associated with a value set that specifies the

set of values that may be assigned to that attribute for each individual entity.

29. Define weak and strong entity sets?

Weak entity set: entity set that do not have key attribute of their own are called weak entity sets.

Strong entity set: Entity set that has a primary key is termed a strong entity set.

30. What does the cardinality ratio specify?

Mapping cardinalities or cardinality ratios express the number of entities to which another entity

can be associated. Mapping cardinalities must be one of the following:

• One to one

• One to many

• Many to one

31. Explain the two types of participation constraint.

Total: The participation of an entity set E in a relationship set R is said to be total if every

entity in E participates in at least one relationship in R.

Partial: if only some entities in E participate in relationships in R, the participation of entity set

E in relationship R is said to be partial.

32. What is meant by lossless-join decomposition? APRIL/MAY-2011

We claim the above decomposition is lossless. How can we decide whether decomposition is

lossless?

1. Let R be a relation schema.

2. Let F be a set of functional dependencies on R.

3. Let R1and R2 form a decomposition of R.

4. The decomposition is a lossless-join decomposition of R if at least one of the following functional dependencies are in :

a. R1∩ R2→ R1

b. R1∩ R2→ R2

33. List the disadvantages of relational database system

Repetition of data

Inability to represent certain information.

34. What is first normal form?

The domain of attribute must include only atomic (simple, indivisible) values.

35. What is meant by functional dependencies?

Consider a relation schema R and a C R and ß C R. The functional dependency a ß holds on

relational schema R if in any legal relation r(R), for all pairs of tuples t1 and t2 in r such that t1 [a] =t1 [a], and also t1 [ß] =t2 [ß].

36. What are the uses of functional dependencies?

To test relations to see whether they are legal under a given set of functional dependencie s. To specify constraints on the set of legal relations.

37. Explain trivial dependency?

Functional dependency of the form a ß is trivial if ß C a. Trivial functional dependencies are satisfied by all the relations.

38. What are axioms?

Axioms or rules of inference provide a simpler technique for reasoning about functional dependencies.

39. What is meant by computing the closure of a set of functional dependency?

+ The closure of F denoted b y F is the set of functional dependencies logically implied by F.

40. What is meant by normalization of data?

It is a process of analyzing the given relation schemas based on their Functional Dependencies

(FDs) and primary key to achieve the properties

Ø Minimizing redundancy

Ø Minimizing insertion, deletion and updating anomalies


UNIT:2-RELATIONAL MODEL

1. Define the terms i) DDL ii) DML

DDL: Data base schema is specified by a set of definitions expressed by a special language

called a data definition language.

DML:

A data manipulation language is a language that enables users to access or manipulate data as organized by the appropriate data model

2. What is embedded SQL? What are its advantages? April/May-2011

Embedded SQL is a method of combining the computing power of a programming language and the database manipulation capabilities of SQL. Embedded SQL statements are SQL statements

written in line with the program source code of the host language. The embedded SQL

statements are parsed by an embedded SQL preprocessor and replaced by host-language calls to

a code library. The output from the preprocessor is then compiled by the host compiler. This allows programmers to embed SQL statements in programs written in any number of languages such as: C/C++, COBOL and Fortran

3. Write short notes on relational model

The relational model uses a collection of tables to represent both data and the relationships

among those data. The relational model is an example of a record based model.

4. Define tuple and attribute

Attributes: column headers

Tuple : Row

5. Define the term relation.

Relation is a subset of a Cartesian product of list domains.

6. Define tuple variable

Tuple variable is a variable whose domain is the set of all tuples.

7. Define the term Domain.

For each attribute there is a set of permitted values called the domain of that attribute.

8. What is a candidate key?

9. What is a primary key?

Primary key is chosen by the database designer as the principal means of identifying an entit y in

the entity set.

10. What is a super key?

A super key is a set of one or more attributes that collectively allows us to identify uniquely an entity in the entity set.

11. List the table modification commands in SQL?

Ø Deletion

Ø Insertion

Ø Updates

Ø Update of a view


UNIT:3-TRANSACTION PROCESSING AND CONCURRENCY CONTROL

1. What are the ACID properties? APRIL/MAY-2011

(atomicity, consistency, isolation, durability) is a set of properties that guarantee database

transactions are processed reliably. In the context of databases, a single logical operation on the data is called a transaction. For example, a transfer of funds from one bank account to another, even though that might involve multiple changes (such as debiting one account and crediting another), is a single transaction.

2. What are two pitfalls (problem) of lock-based protocols? APRIL/MAY-2011

Ø Deadlock

Ø Starvation

3. What is transaction?

Collections of operations that form a single logical unit of work are called transactions.

4. What are the two statements regarding transaction?

The two statements regarding transaction of the form:

Ø Begin transaction

Ø End transaction

5. What are the properties of transaction?

The properties o f transactions are:

Ø Atomicity

Ø Consistency

Ø Isolation

Ø Durability

6. What is recovery management component?

Ensuring durability is the responsibility of a software component of the base system called the

recovery management component.

7. When is a transaction rolled back?

Any changes that the aborted transaction made to the database must be undone. Once the changes caused by an aborted transaction have been undone, then the transaction has been rolled

back.

8. What are the states of transaction?

The states of transaction are

Ø Active

Ø Partially committed

Ø Failed

Ø Aborted

Ø Committed

Ø Terminated

Ø

9. List out the statements associated with a database transaction?

Ø Commit work

Ø Rollback work

10. What is a shadow copy scheme?

It is simple, but efficient, scheme called the shadow copy schemes. It is based o n making copies of the database called shadow copies that one transaction is active at a time. The scheme also

assumes that the database is simply a file on disk.

11. Give the reasons for allowing concurrency?

The reasons for allowing concurrency is if the transactions run serially, a short transaction may

have to wait for a preceding long transaction to complete, which can lead to unpredictable delays in running a transaction. So concurrent execution reduces the unpredictable delays in running transactions.

12. What is average response time?

The average response time is that the average time for a transaction to be completed after it has

been submitted.

13. What are the two types of serializability?

The two types of serializability is

Ø Conflict serializability

Ø View serializability

14. Define lock?

Lock is the most common used to implement the requirement is to allow a transaction to access a data item only if it is currently holding a lock on that item.

15. What are the different modes of lock?

The modes of lock are:

16. Define deadlock?

Ø Exclusive

Neither of the transaction can ever proceed with its normal execution. This situation is called deadlock.

17. Define the phases of two phase locking protocol

Growing phase: a transaction may obtain locks but not release any lock.

Shrinking phase: a transaction may release locks but may not obtain any new locks.

18. Define upgrade and downgrade?

It provides a mechanism for conversion from shared lock to exclusive lock is known as upgrade. It provides a mechanism for conversion from exclusive lock to shared lock is known as

downgrade.

19. What is a database graph?

The partial ordering implies that the set D may now be viewed as a directed acyclic graph, called

a database graph.

20. What are the two methods for dealing deadlock problem?

The two methods for dealing deadlock problem is deadlock detection and deadlock recovery.

21. What is a recovery scheme?

An integral part of a database system is a recovery scheme that can restore the database to the consistent state that existed before the failure.

22. What are the two types of errors?

The two types of errors are:

Ø Logical error

Ø System error

23. What are the storage types?

The storage types are:

Ø Volatile storage

Ø Nonvolatile storage

24. Define blocks?

The database system resides permanently on nonvolatile storage, and is partitioned into fixed- length storage units called blocks.

25. What is meant by Physical blocks?

The input and output operations are done in block units. The blocks residing on the disk are referred to as physical blocks.

26. What is meant by buffer blocks?

The blocks residing temporarily in main memory are referred to as buffer blocks.

27. What is meant by disk buffer?

The area of memory where blocks reside temporarily is called the disk buffer.

28. What is meant by log-based recovery?

The most widely used structures for recording database modifications is the log. The log is a

sequence of log records, recording all the update activities in the database. There are several types of log records.

29. What are uncommitted modifications?

The immediate-modification technique allows database modifications to be output to the database while the transaction is still in the active state. Data modifications written by active

transactions are called uncommitted modifications.

30. Define shadow paging.

An alternative to log-based crash recovery technique is shadow paging. This technique needs

fewer disk accesses than do the log-based methods.

31. Define page.

The database is partitioned into some number of fixed-length blocks, which are referred to as

pages.

32. Explain current page table and shadow page table.

The key idea behind the shadow paging technique is to maintain two page tables during the life

of the transaction: the current page table and the shadow p age table. Both the page tables are identical when the transaction starts. The current page table may b e changed when a transaction performs a write operation.

33. What are the drawbacks of shadow-paging technique?

Ø Commit Overhead

Ø Data fragmentation

Ø Garbage collection

34. Define garbage collection.

Garbage may be created also as a side effect of crashes. Periodically, it is necessary to find all the garbage pages and to add them to the list of free pages. This process is called garbage

collection.

35. Differentiate strict two phase locking protocol and rigorous two phase locking protocol.

In strict two phase locking protocol all exclusive mode locks taken by a transaction is held

36. How the time stamps are implemented

• Use the value of the system clock as the time stamp. That is a transactio n‟s time stamp is equal

to the value of the clock when the transaction enters the system.

• Use a logical counter that is incremented after a new timestamp has been assigned; that is the

time stamp is equal to the value of the counter.

37. What are the time stamps associated with each data item?

• W-timestamp (Q) denotes the largest time stamp if any transaction that executed WRITE (Q)

successfully.

• R-timestamp (Q) denotes the largest time stamp if any transaction that executed READ (Q)

successfully.


UNIT:4-TRENDS IN DATABASE TECHNOLOGY

1. What are the advantages and disadvantages of indexed sequential file? APRIL/MAY-

2011

The advantage of ordering records in a sequential file according to a key is that you can then

search the file more quickly. If you know the key value that you want, you can use one of the relatively fast searches. The disadvantage is that when you insert, you need to rewrite at least everything after the insertion point, which makes inserts very expensive unless they are done at the end of the file. An indexed file approach keeps a (hopefully) small part of each row, and some kind of "pointer" to the row's location within the data file. This allows a search to use the index, which is ordered by the index and (again hopefully) much smaller and therefore much faster than scanning the entire data file for the indexed data.

2. What is database tuning? APRIL/MAY-2011

Database tuning describes a group of activities used to optimize and homogenize the

performance of a database. It usually overlaps with query tuning, but refers to design of the database files, selection of the database management system (DBMS), operating system and CPU the DBMS runs on.

3. Give the measures of quality of a disk.

Capacity

Access time

Seek time

Data transfer rate

Reliability

Rotational latency time.

Cheaper than disk Expensive when compared with disk

5. What are the types of storage devices?

Ø Primary storage

Ø Secondary storage

Ø Tertiary storage

6. Define average seek time.

The average seek time is the average of the seek times, measured over a sequence of random

requests.

7. Define rotational latency time.

The time spent waiting for the sector to be accessed to appear under the head is called the

rotational latency time.

8. Define average latency time.

The average latency time of the disk is one-half the time for a full rotation of the disk.

9. What is meant by data-transfer rate?

The data-transfer rate is the rate at which data can be retrieved from or stored to the disk.

10. What is meant by mean time to failure?

The mean time to failure is the amount of time that the system could run continuously without

failure.

11. What are a block and a block number?

A block is a contiguous sequence of sectors from a single track of one platter. Each request

specifies the address on

the disk to be referenced. That address is in the form of a block number.

12. What are called journaling file systems?

File systems that support log disks are called journaling file systems.

13. What is the use of RAID?

A variety of disk-organization techniques, collectively called redundant arrays of independent

disks are used to improve the performance and reliability.

14. Explain how reliability can be improved through redundancy?

The simplest approach to introducing redundancy is to duplicate every disk. This technique is called mirroring or shadowing. A logical disk then consists of two physical disks, and write is

carried out on both the disk. If one of the disks fails the data can be read from the other. Data will be lost if the second disk fails before the first fail ed disk is repaired.

15. What is called mirroring?

The simplest approach to introducing redundancy is to duplicate every disk. This technique is called mirroring or shadowing.

16. What is meant by Multi-dimensional database?

A multi-dimensional database is a computer software system designed to allow for efficient and

convenient storage and retrieval of large volumes of data that is (1) intimately related and (2) stored, viewed and analyzed from different perspectives and these perspectives are called dimensions.

17. What is meant by Spatial database?

A spatial database is a database that is optimized to store query data that represents objects

defined in geometric space. Most spatial databases allow representing simple geometric objects such as points, lines and polygons. Some spatial databases handle more complex structures such as 3D objects, topological coverages,etc.

18. What is meant by Mobile database?

A mobile database is a database that resides on mobile device such as a PDA, a smart phone, or a

laptop. Such devices are often limited in resources such as memory, computing power and battery power.


UNIT:5-ADVANCED TOPICS

1. List the threats to databases.

Ø Loss of integrity

Ø Loss of availability

Ø Loss of confidentiality

2. List out the control measures.

Ø Access control

Ø Inference control

Ø Flow control

Ø Data encryption

3. What is meant by Data warehouse?

A data warehouse is a repository (archive) of information gathered from multiple sources, stored under a unified schema at a single site.

Ø Greatly simplifies querying, permits study of historical trends

Ø Shifts decision support query load away from transaction processing

systems

4. Define Data mining.

Ø Sorting

Ø Selection

6. What is the difference between Information Retrieval and DBMS.

S.No

Information Retrieval

DBMS

1

Imprecise semantics

Precise semantics

2

Keyword search

SQL

3

Unstructured data format

Structured data

4

Reads mostly. Adds document

occasionally.

Expects reasonable number of updates.

5

Displays page through top k results.

Generates full answer.

7. List out the functionalities of Data warehouse.

Ø Data cleaning

Ø Data transformation

Ø Data integration

Ø Data loading &

Ø Periodic data refreshing

8. List the types of security mechanisms.

Ø Discretionary security mechanisms

Ø Mandatory security mechanisms

9. What are the database design issues?

Ø Legal and ethical issues

Ø Policy issues

Ø System related issues

10. What are the actions performed by DBA?

Ø Account creation

Ø Privilege granting

Ø Privilege revocation

Ø Security level assignment

11. What is the difference between Database and Data warehouse?

S.No

Database

Data warehouse

1.

Online transaction & query processing is

done in database

Data analysis & decision making is done in

data warehouse

2.

Online Transaction Processing (OLTP) is

carried out in Database.

Online Analytical Processing (OLAP) is

carried out in Database

12. What are the steps for designing a warehouse?

Ø Choose a business process to model

Ø Choose the grain of the business process

Ø Choose the dimensions that will apply to each fact table record

Ø Choose the measures that will populate each fact table record

13. What are the issues in data warehouse design?

Ø When and how to gather data

Ø What schema to use

Ø Data cleansing

Ø How to propagate updates

Ø What data to summarize

14. What are the goals of data mining?

Ø Prediction

Ø Identification

Ø Classification

Ø Optimization

15. List out the types of Discovered knowledge.

Ø Association rules

Ø Classification Hierarchies

Ø Sequential patterns

Ø Patterns within time series

Ø Clustering

16. What is meant by Association rule?

An association rule is of the form X→Y, where X={x1, x2,……. xn} and Y={y1, y2,……. yn} are set of items with xi and yi being distinct items of all i and j. It must satisfy a minimum support and confidence.

17. What is meant by Confidence rule?

Given a rule of the form A→B, rule confidence is the conditional probability that B is true when

A is known to be true.

18. Define Apriori algorithm.

The Apriori algorithm was the first algorithm used to generate association rules. It uses the general algorithm for creating association rules together with downward closure and anti-

monotonicity.

20. What is meant by frequent pattern tree algorithm?

The Frequent pattern tree algorithm reduces the total number of candidate itemsets by producing a compressed version of the database in terms of an FP-tree. The FP-tree stores relevant

information and allows for the efficient description of frequent itemsets. The algorithm consists of 2 steps:

1. Build FP-tree

2. Use the tree to find frequent itemsets.

21. What is meant by Classification?

Classification is the process of learning a model that is able to describe different classes of data.

22. List the applications of data mining.

Ø Marketing

Ø Finance

Ø Resource optimization

Ø Image Analysis

Ø Fraud detection

CS6301 - PROGRAMMING AND DATA STRUCTURES II Two Marks Questions With Answers 2014

Anna University, Chennai

Anna_University,_Chennai_logo

DHANALAKSHMI SRINIVASAN INSTITUTE OF RESEARCH AND TECHNOLOGY

SIRUVACHUR, PERAMBALUR – 611 113

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING CS6301 - PROGRAMMING AND DATA STRUCTURES II

QUESTION BANK

UNIT - I

1. Write down the characteristics of object oriented programming.

Hints:

· Encapsulation

· Data abstraction

· Inheritance

· Polymorphism

· Message passing

· Extendibility

2. Explain the elements of object oriented programming.

Hints:

· Classes

· Objects

· Constructor

· Destructor

· Dynamic binding

3. Describe the applications of OOP technology.

Hints:

§ C++ features

§ Function overloading

§ Operator overloading

4. What is function overloading? Explain briefly with program.

Hints:

§ Definition for function overloading

§ Syntax

§ Example

§ Sample program

5. Write a program to demonstrate how a static data is accessed by a static member function.

Hints:

§ Describe a static variable in the class

§ Use a member function as static

§ Define the static member function outside the class’

§ Call the static function so as to demonstrate how a static data is accessed.

6. What is friend function? What is the use of using friend functions in c++?

Explain with a program.

Hints:

§ Definition of friend function

§ Syntax

§ Usage: non member function can access the private data of a class

§ Sample program to implement friend function.

7. Discuss in detail about default arguments with an example.

Hints:

§ Default argument definition

§ Syntax

§ The number of arguments differ in the function definition

§ Sample program


UNIT II

1. Write a program to implement a. dynamic polymorphism

Hints:

¨ During multiple inheritances if the appropriate member function could be selected while the program is running is known as Runtime polymorphism

¨ such polymorphisms are known as dynamic polymorphism

¨ examples

¨ sample programs

b. virtual function

Hints:

¡ Different versions for the virtual function should be present in different derived classes with same name as virtual function name

¡ Syntax

¡ Example

¡ Sample program

2. What is inheritance and explain briefly pointer to derived class.

Hints:

¨ Definition

¨ Types

o Multiple inheritance

If a derived class is derived from more than one base class, then it is called

multiple inheritance.

¨ Hierarchial inheritance

If two or more derived classes are derived from the same base class then it is known as hierarchial inheritance

¨ Multilevel inheritance

If a derived class is derived from another derived class then it is known as

multilevel inheritance.

¨ Sample programs

3. Explain copy constructor and destructor with suitable C++ coding.

Hints:

The copy constructor is a constructor which creates an object by initializing it with an object of the same class, which has been created previously.

The copy constructor is used to:

Þ Initialize one object from another of the same type.

Þ Copy an object to pass it as an argument to a function.

¨ Also write sample program with one argument

4.Explain in detail about constructor with dynamic allocation.

Hints:

¨ Constructor is used to initialize an object

¨ Types of constructor

¨ Dynamic constructor is used at runtime

¨ Syntax

¨ Example source codes

5.With an example explain about operator overloading through friend functions.

Hints:

In case of unary operators, overloaded operator can be invoked as

Operator op (x);

In case of binary operators, overloaded operator can be invoked as

Operator op (x , y)

· Sample program

6.Explain about Unary Operator and Binary Operator Overloading with program.

Hints:

o When unary operators are overloaded using member functions it takes no explicit arguments and return no explicit values.

o Sample program

o When binary operators are overloaded using member functions, it takes one explicit argument. Also the left hand side operand must be an object of the relevant class.

o Sample program

7.List out the rules for overloading operators with example.

Hints:

· Only the existing operators can be overloaded.

· The overloaded operator must have at least one operand that is of user defined data type

· The basic meaning of the operator should not be changed.

· Overloaded operators follow the syntax rules of the original operators. They cannot be overridden.


UNIT III

1. What is the need of Templates? Explain.

Hint:

· Templates support generic programming , which allows to develop reusable software components such as functions, classes etc., supporting different data types in a single framework

· sample program

2. What is uncaught exception function? Give an example.

Hint:

· Exception which is not executed

· Example

· Syntax with program

3. What are the use of terminate () and Unexpected functions? Explain with a program

Hint:

· Terminate is used to denote the end of exception

· Example program

· Unexpected functions are handled by exceptions as per the demonstrations

4. How to use multiple catch functions inside a program? Explain with a program.

Hints:

· Based on the definition of the multiple exception appropriate function is handled according to the choice matches

· Example explanation

· Sample program

5. Write all blocks of exception handling? Explain with a program.

Hints:

· Definition of exception handling

· Example coding

· Throw and catch

· Sample program

6. Write notes on Formatted and Unformatted Console I/O Operations.

Hints:

· Definition for formatted and unformatted operations

· Simple statements

· Statements with additional features

· Examples

· Sample programs if possible

7. Explain about File Pointers and their manipulations with example.

Hints:

· Name the file on the disk

· Open the file to get the file pointer.

· Process the file. (Read / Write )

· Check for errors while processing.

· Close the file after its complete usage.


UNIT IV

1. Explain disjoint set in detail.

Hints:

· Collection of sets where each set has a representative which is a member of the set

· Operations

· Applications

· Equivalence relations

· Find ADT

2. Explain Red Black tree operations with examples.

Hints:

· Self balancing binary search tree

· Properties

· Comparison with AVL trees

· Modifying routines

· Algorithms

3. Explain in detail about splay trees with suitable examples

Hints:

· SPLAY trees are variation of binary search trees

· Not to spend much time on balancing

· Amortized analysis

· Splaying

o Zig zag

o Zig zig

4. What are AVL trees? Describe the different rotations defined for the AVL tree.

Hints:

· Adelson-Velskii and Landis tree is a binary search tree except that for every node in the tree, the height of the left and right subtrees can differ by atmost 1.

· Balance factor

· Example graph

· Algorithm

· Types – single and double rotations

5. Explain in detail about the Fibonacci heaps.

Hints;

· Collection of heap ordered trees, the trees are routed but unordered

· Pointers

· Two fields

· Examples

· Algorithm

6. Give an example for binomial heap and explain the same.

Hints:

· Definition of a binomial heap

· Properties

· Algorithm

o Basic operations, insert,delete

o Find minimum

1. Explain Graph traversals with examples.

Hints:

· Definition for traversals

· Types

· Examples

· Diagrams with algorithms


UNIT V

2. Describe the topological sorting method with suitable examples.

Hints:

· Definition for topological sorting

· Explanation with small array example

· C++ coding

3. What do you know about the breadth first search? Explain.

Hints:

· A type of graph traversal

· Searches on level based

· Draw a graph

· Algorithm with example

4. Write the Prims algorithm and explain the same.

Hints:

· Definition for spanning tree

· To find the minimum spanning tree prims method is used

· The pair with the minimum weight is chosen

· Algorithm with small graph example

5. Explain the kruskals algorithm for minimum spanning tree.

Hints:

· Definition for spanning tree

· To find the minimum spanning tree prims method is used

· Not necessary with the minimum weight

· Circuit should not be formed

· Algorithm with small graph example

6. Discuss any two shortest path algorithms.

Hints:

· Dijkstra’s Algorithm

o Finding the distance between the start node and the neighboring nodes

o Graph example

o Algorithm

· Floyd’s Algorithm

o This algorithm requires a weighted graphs

o Computes the distance matrix of a weighted graph with vertices through a series of n by n matrices.

o Example

o Algorithm

7. Compare depth first search and depth first search.

S.NO

DEPTH FIRST SEARCH

BREADTH FIRST SEARCH

1

Backtracking is possible from dead

end

Backtracking is not possible

2

Search is done in one particular

direction at the time

Vertices in the same level are

maintained parallel

3

LIFO order

FIFO order

· Graph example

· Algorithm

**************

CS6301 - PROGRAMMING AND DATA STRUCTURES Two Marks Questions With Answers 2014

Anna University, Chennai

Anna_University,_Chennai_logo

DHANALAKSHMI SRINIVASAN INSTITUTE OF RESEARCH AND TECHNOLOGY

SIRUVACHUR, PERAMBALUR – 611 113

DEPARTMEN OF COMPUTER SCIENCE AND ENGINEERING CS6301 - PROGRAMMING AND DATA STRUCTURES

QUESTION BANK UNIT I

1. Define object oriented programming.

Object oriented programming is an approach that provides a way of modularizing programs by creating partitioned memory area for both data and functions that can be used as templates for creating such modules on demand.

2. List out the features of OOPS .

· Classes

· Objects

· Data abstraction

· Data encapsulation

· Inheritance

· Polymorphism

· Message passing

· Extensibility

· Persistence

· Delegation

· Genericity

· Dynamic binding.

3. What is an object ?

Objects are the basic run time entities in an object oriented system. They may represent a person , a place or any data item. Objects contain data and code to manipulate data.

4. What is a class?

The entire set of data and code of an object that can be made a user defined data type with the help of a class. A class is a collection of objects of type class.

5. What is data abstraction?

The technique of creating new data types that are well suited to an application to be programmed is known as data abstraction.

6. What is data encapsulation?

The wrapping up of data and functions into a single unit called class is known as data encapsulation.

7. What is data hiding?

The insulation of the data from direct access by the program is called data hiding or information hiding

8. What are inheritance / reusability / derivation?

Inheritance is the process by which objects of one class acquire the properties of objects of another class.

The concept of inheritance provides the idea of reusability. This means that we can add additional features to an existing class without modifying it .

Derivation involves the creation of new classes ( derived class ) from the existing ones

(base class).

9. What is polymorphism?

Polymorphism means the ability to take more than one form.

10. What is the use of a break statement?

A break construct terminates the execution of loop and the control is transferred to the statement immediately following the loop. The term break refers to the act of breaking out of a block of code.

11. What is the use of a continue statement?

The continue statement skips the remainder of the current iteration initiates the execution of the next iteration.

12. Define function.

The process of splitting a large program into small manageable tasks ane designing them independently is popularly called modular programming or divide and conquer technique. A repeated group of instructions in a program can be organized as a function. A function is a set of program statements that can be proceesed independently.

13. What is a pointer? What are the uses of a pointer?

Pointer is defined as a variable used to store memory addresses. Uses :

· Accessing array elements .

· Passing arguments to a function when the function needs to modify the original.

· Passing arrays and strings to functions.

· Creating data structures such as linked lists, binary tree etc .

· Obtaining memory from the system dynamically.

14. What is a friend function?

Friend function is a special type of function which is used to access all the private and protected members of a class. The functions that are declared with the keyword

friend are called friend functions. A function can be a friend to multiple classes.

15. What are the properties of a friend function?

· A friend function is not in the scope of the class to which it has been declared as friend.

· It can be invoked like a normal function without the help of any object.

· Unlike member functions it cannot access the member names directly and has to use an object name and dot membership with each member name.

16. What is the difference between friend function and member function?

The only difference between a friend function and member function is that, the friend function requires the argument to be explicitly passed to the function and processes them explicitly, whereas, the member function considers the first argument implicitly.

17. What is an inline function?

Inline functions are those whose function body is inserted in place of the function call statement during the compilation process. With the inline code the program will not incur any context switching overhead.

18 .What is a recursive function?

A function that contains a function call to itself or a function call to a second function which eventually calls the first function is known as recursive functions.

19. What is data conversion?

When we use the assignment operator we assign a value on the right hand side to a variable on the left side & if it is of a different data type then we have to perform data conversion or type conversion.

20. What are the methods of data conversion?

There are two methods for data conversion:

(i) implicit data conversion (ii) explicit data conversion

21. Give the structure of a C++ program.

Include files

Class definition

Member function definitions

Main function

22. What is function prototype?

Function prototype is otherwise known as function declaration. The prototype describes the function interface to the compiler by giving details such as the number and type of arguments and the type of return values.

23. What is a class ? How will you define a class?

A class is a way to bind the data and its associated functions together. A class specification has two parts :

· Class declaration

· Class function definition

24. What are the characteristics of a static data member?

· Static data member is initialized to zero when the first object of its class is created. No other initialization is permitted.

· Only one copy of that member is created for the entire class and is shared by all

the objects of that class, no matter how many objects are created.

· It is visible only within the class, but its life time is the entire program.

25. What are the properties of a static member function?

· A static function can have access to only other static members, declared in the same class.

· A static member function can be called using the class name as follows

Classname :: function-name;

26. In what way is a private member function different from public member function.

A private member function can only be called by another function that is a member of its class. Even an object cannot invoke a private function using the dot operator.

1.What is a constructor ?


UNIT II

A constructor is a special member function whose task is to initialize the objects of its class. It is special because its name is the same as the class name.

The constructor is invoked whenever an object of its associated class is created. It is called constructor because it constructs the values f data members of the class.

2. How will you declare and define a constructor

Constructor declaration : Class integer

{

int m,n;

public :

}integer ( void )

constructor definition

integer :: integer (void )

{

m=0;

n=0;

3. what are the characteristics of a constructor ?

· They should be declared in the public section.

· They are invoked automatically when the objects are created.

· They do not have return types, not even void and therefore, they cannot return values.

· They cannot be inherited, though a derived class can call the base class constructor.

· Constructors cannot be virtual.

4. what are the types of a constructor ?

· Default constructor

· Parameterized constructor.

· Copy constructor

5. What is a parameteized constructor ?

The constructors that can take arguments are called parameterized

constructors.

Integer ( int x, int y )

{

m=x;

n=y;

}

6. What is a default constructor ?

A constructor that accepts no parameter is called default constructor. Default ( )

{

}

7. What is a destructor ?

A destructor as the name implies is used to destroy the objects that have been created by a constructor. Like a constructor the destructor is a member function whose name is the same as the class name but is preceded by a tilde symbol.

~ integer ( )

{

}

8. what is Dynamic constructors

The constructors can also be used to allocate memory while creating objects. This will enable the system to allocate the right amount of memory for each object when the objects are not of the same size thus resulting in the saving of memory.

Allocation of memory to objects at the time of their construction is known as dynamic constructors. The memory is allocated with the help of the new operator.

9. What is function overloading? Give an example.

Function overloading means we can use the same function name to create functions that perform a variety of different tasks.

Eg: An overloaded add ( ) function handles different data types as shown below.

// Declarations

i. int add( int a, int b); //add function with 2 arguments of same type

ii. int add( int a, int b, int c); //add function with 3 arguments of same type

iii. double add( int p, double q); //add function with 2 arguments of different type

10. What is operator overloading?

C++ has the ability to provide the operators with a special meaning for a data type. This mechanism of giving such special meanings to an operator is known as Operator

overloading. It provides a flexible option for the creation of new definitions for C++

operators.

11. List out the operators that cannot be overloaded.

_ Class member access operator (. , .*)

_ Scope resolution operator (::)

_ Size operator ( sizeof )

_ Conditional operator (?:)

13. What is the purpose of using operator function? Write its syntax.

To define an additional task to an operator, we must specify what it means in

relation to the class to which the operator is applied. This is done by Operator function , which describes the task. Operator functions are either member functions or friend functions. The general form is

return type classname :: operator (op-arglist )

{

function body

}

where return type is the type of value returned by specified operation.

Op-operator being overloaded. The op is preceded by a keyword operator. operator op is the function name.

14. Write at least four rules for Operator overloading.

_ Only the existing operators can be overloaded.

_ The overloaded operator must have at least one operand that is of user defined data type.

_ The basic meaning of the operator should not be changed.

_ Overloaded operators follow the syntax rules of the original operators. They cannot be overridden.

15. How will you overload Unary & Binary operator using member functions?

When unary operators are overloaded using member functions it takes no explicit arguments and return no explicit values.

When binary operators are overloaded using member functions, it takes one explicit argument. Also the left hand side operand must be an object of the relevant class.

16. How will you overload Unary and Binary operator using Friend functions?

When unary operators are overloaded using friend function, it takes one reference argument (object of the relevant class)

When binary operators are overloaded using friend function, it takes two explicit arguments.

17. How an overloaded operator can be invoked using Friend functions?

In case of unary operators, overloaded operator can be invoked as

Operator op (x);

In case of binary operators, overloaded operator can be invoked as

Operator op (x , y)

18. List out the operators that cannot be overloaded using Friend function.

_ Assignment operator =

_ Function call operator ( )

_ Subscripting operator [ ]

®_ Class member access operator

19. Explain basic to class type conversion with an example.

Conversion from basic data type to class type can be done in destination class. Using constructors does it. Constructor takes a single argument whose type is to be converted.

Eg: Converting int type to class type class time

{

int hrs,mins;

public:

………….

Time ( int t) //constructor

{

hours= t/60 ; //t in minutes mins =t % 60;

}

};

Constructor will be called automatically while creating objects so that this conversion is done automatically.

20. Explain class to basic type conversion with an example.

Using Type Casting operator, conversion from class to basic type conversion can be done. It is done in the source class itself.

Eg: vector : : operator double( )

{

double sum=0;

for(int I=0;I<size;I++) sum=sum+v[ i ] *u[ i ] ; return sqrt ( sum ) ;

}

This function converts a vector to the corresponding scalar magnitude.

21. Define inheritance ?

Inheritance is the process of creating new classes from the existing classes. The new classes are called derived classes. The existing classes are called base classes. The derived classes inherit all the properties of the base class plus its own properties. The properties of inheritance does not affect the base classes.

22. What are the types of inheritance ?

· Single inheritance

· Multiple inheritance

· Hierarchial inheritance

Multilevel inheritance.

· Hybrid inheritance

· Multipath inheritance

23. What are the advantages of using a derived class ?

· New classes can be derived by the user from the existing classes without any modification.

· It saves time and money.

· It reduces program coding time.

· It increases the reliability of the program.

24.Define

multiple inheritance

If a derived class is derived from more than one base class, then it is called multiple inheritance.

hierarchial inheritance

If two or more derived classes are derived from the same base class then it is known as hierarchial inheritance

multilevel inheritance

If a derived class is derived from another derived class then it is known as multilevel inheritance.

25. Define abstract class

A class is said to be an abstract class if it satisfies the following conditions :

· It should act as a base class

· It should not be used to create any objects

26. What is an virtual function ?

A member function whose definition can be changed during run time is called virtual function. The class which contains virtual function is called polymorphic class and it should be a base class.

Different versions for the virtual function should be present in different derived classes with same name as virtual function name

27. Define pure virtual function ?

Pure virtual function is a virtual function with no body. The general form is

Virtual void member-function-name( ) = 0

28. What are the properties of pure virtual function ?

· It has no definition in the base class.

· We cannot create object for the class containing pure virtual function.

· Pure virtual function can be called through derived class objects.

· It acts as an empty bucket which has to be filled by its derived classes.

29. What are the rules for virtual functions ?

· Virtual functions must be members of some class.

· They cannot be static members.

· They are accessed by using object pointers.

· A virtual function can be a friend of another class.

· We can have virtual destructors, but we cannot have virtual constructors.

30. Define Polymorphism

It is the property of the same object to behave differently in different contexts given the same message. A single function name can be used for various purposes and single operator is used to achieve multiple operations and the usage of either the function at the operator depends on the context in such cases.

31. Define Compile time polymorphism:

The compiler while compiling the program resolves the function call or the operator call. This is known as compile time polymorphism

32. Define Runtime polymorphism

During multiple inheritances if the appropriate member function could be selected while the program is running is known as Runtime polymorphism


Unit III

1. What is an exception ?

Exception refers to unexpected condition in a program. The unusual conditions could be faults, causing an error which in turn causes the program to fail. The error handling mechanism of C++ is generally referred to as exception handling.

2. What are the types of exception ?

They are classified into synchronous and asynchronous exceptions. Synchronous exception :

The exception which occur during program execution , due to some fault in the input data or technique that is not suitable to handle the current class of data, within the pgogram are known as synchronous exception.

For instance errors such as out-of-range, overflow, underflow and so on. Asynchronous exception :

The exceptions caused by events or faults unrelated to the program and beyond the control of the program are called asynchronous exception.

For instance, errors such as keyboard interrupts, hardware malfunctions, disk failure, and so on.

3. What are the blocks related to exception handling constructs ?

The blocks related to exception handling constructs are

· try

· throw

· catch

The keyword try is used to preface a block of statements. Which may generate exceptions. This block of statements is known as try block.

When an exception is detected, it is thrown using throw statement in the try block.

A catch block catches the exception thrown by the throw statement in the try block and handles it appropriately.

Syntax:

try

{

………

………

throw exception;

}

catch (type arg)

{ }

4. What are the functions supported by C++ to handle uncaught exceptions ?

The functions supported by C++ to handle uncaught exceptions are terminate ( )

set_terminate ( ) unexpected ( ) set_unexpected ( )

5.What is a template ?

Templates support generic programming , which allows to develop reusable software components such as functions, classes etc., supporting different data types in a single framework

6.What is function template ?

The templates declared for functions are called function templates. They perform appropriate operations depending on the data type of the parameters passed to them.

7. What is a class template ?

The templates declared for classes are called function templates. They perform appropriate operations depending on the data type of the parameters passed to them.

8. What is a stream ?

Stream is a series of bytes, which act either as a source from which input data can be extracted or as a destination to which the output can be sent. The source stream provides data to the program called te input stream and the destination stream that receives data from the program is called the output stream.

9. What are the types of standard streams ?

· cin - Standard input corresponding to stdin in C

· cout – Standard output corresponding to stdout in C

· cout – Standard error output corresponding to Stderr in C

· clog – A fully buffered version of cerr.

10. How do you classify ios class ?

Istream – input stream does formatted input. Ostream – output stream does formatted output.

Iostream – input / output stream does formatted input and output.

11. What are manipulators ?

Manipulators are special functions that are specifically designed to modify the working of a stream. They can be embedded in the I/O statements to modify the form parameters of a stream.

12. Give few ios class functions and flags ?

Function

Task performed

Width( )

Specifies the required number of fields to be used while displaying the output value.

Precision ( )

Specifies the number of digits to be

displayed after the decimal point.

Fill ( )

Specifies a character to be used to fill the

unused area of a field. By default, fills blank space character.

Setf ( )

Sets format flag that control the form of output display.

Unsetf ( )

Clears the specified format flag.

13. What is a file ?

A file is a collection of related information defined by its creator. Commonly files represent programs ( boyh source and object forms ) and data. Files may be free-form, such as text files or may be rigidly formatted . In general, a file is a sequence of bits, bytes, lines, or records whose meaning is defined by its creator and user.

14. How many classes are used for handling files ?

ifstream – for handling input files. ofstream – for handling output files.

fstream – for handling files on which both input and output can be performed.

15. What are the steps involved in manipulating a file ?

· Name the file on the disk

· Open the file to get the file pointer.

· Process the file. (Read / Write )

· Check for errors while processing.

· Close the file after its complete usage.

16. What functions are used for manipulation of file pointers ?

· seekg ( ) – Moves get file pointer to a specific location.

· seekp ( ) - Moves put file pointer to a specific location.

· tellg ( ) – Returns the current position of the get pointer

· tellp ( ) - Returns the current position of the put pointer

17. What do you mean by sequential access ?

A sequential file has to be accessed sequentially ; to access the particular data in the file all the preceding data items have to be read and discarded. For example a file on a tape must be accessed sequentially.

18. What do you mean by random access ?

A random file allows access to the specific data without the need for accessing its preceding data items. However, it can be accessed sequentially . For example, a file on a hard disk or floppy disk can be accessed either sequentially or randomly.

PART A


UNIT IV

1. Define tree.

Trees are non-liner data structure, which is used to store data items in a shorted sequence. It represents any hierarchical relationship between any data Item.

It is a collection of nodes, which has a distinguish node called the root and zero or more non-empty sub trees T1, T2,….Tk. each of which are connected by a directed edge from the root.

2. Define Height of tree.

The height of n is the length of the longest path from root to a leaf. Thus all leaves have height zero. The height of a tree is equal to a height of a root.

3. Define Depth of tree.

For any node n, the depth of n is the length of the unique path from the root to node n. Thus for a root the depth is always zero.

4. Define Degree of a node.

It is the number of sub trees of a node in a given tree.

5. Define Degree of a tree.

It is the maximum degree of a node in a given tree.

6. Define Terminal node or leaf?

Nodes with no children are known as leaves. A leaf will always have degree zero and is also called as terminal node.

7. Define Non-terminal node?

Any node except the root node whose degree is a non-zero value is called as a non-terminal node. Non-terminal nodes are the intermediate nodes in traversing the given tree from its root node to the terminal node.

8. Define sibling?

Nodes with the same parent are called siblings.

9. Define binary tree?

A Binary tree is a finite set of data items which is either empty or consists of a single item called root and two disjoin binary trees called left sub tree max degree of any node is two.

10. Define expression tree?

Expression tree is also a binary tree in which the leafs terminal nodes or operands

and non-terminal intermediate nodes are operators used for traversal.

11. Define Construction of expression trees

a. Convert the given infix expression into postfix notation

b. Create a stack and read each character of the expression and push into the stack, if operands are encountered.

c. When an operator is encountered pop 2 values from the stack.

12.Define lazy deletion?

When an element is to be deleted.it is left in the tree itself and marked as being deleted. This is called as lazy deletion and is an efficient procedure if duplicate keys are present in the binary search tree, because the field that keeps count of the frequency of appearance of the element can be decremented of the element can be decremented.

13. Define AVL

AVL tree also called as height balanced tree .It is a height balanced tree in which every node will have a balancing factor of –1,0,1.

Balancing factor of a node is given by the difference between the height of the left sub tree and the height of the right sub tree.

14.What are the various operation performed in the binary search tree?

i. insertion

ii. deletion

iii. find

iv. find min v. find max

15.What are the various transformation performed in AVL tree?

b. Single rotation

1. Single L rotation

2. Single R rotation c. Double rotation

1. LR rotation

2. RL rotation


UNIT V

PART A

1. What is a graph?

A graph consists of a set of vertices V and set of edges E which is mathematically represented as G=(V,E).Each edge in a pair(V,W) where V,W,belongs to E ,edges are sometimes referred to as arcs.

2. What are Directed graphs?

If a pair of vertices for any edge is ordered, then that graph is called as Digraph or directed graph.

3. Define Path.

A path in a graph is a sequence of vertices w1,w2w,3,wN such that Wi,Wi+1 belongs to E for a value 1<=I<=N. The length of such a path is the number of edges on the path, which is equal to n-1.

4. Define Cycle.

A cycle is a path in which the first and last vertices are the same.

5. Define Acyclic graph.

A graph with no cycles is called Acyclic graph. A directed graph with no Edges is called as a directed Acyclic graph (or) DAG. DAGS are used for Compiler Optimization process.

6. Define Connected graph.

A graph is said to be a weighted graph is connected if there is a path from every vertex to every other vertex. A directed graph with this property is called as strongly connected graph. If a directed graph is not strongly connected but the underline graph. Without direction is connected it is called as a weakly connected graph.

7. What are the conditions for a graph to become a tree?

A graph is a tree if it has two properties.

i. If it is a connected graph.

ii. There should not be any cycles in the graph.

8. Define a Weighted Graphgraph if every edge in the graph is assigned

some weight or value. The weight of the edge is a positive value that represents the cost of moving the edge or the distance between two vertices.

9. Give the types of representation of graphs.

1. Adjacency matrix .

2. Adjacency linked list

10.What is a minimum spanning tree?

A minimum spanning tree of an undirected graph G is a tree formed from graph edges that connect all the vertices of G at lowest total cost.

11. Explain about Adjacency Matrix

Adjacency matrix consists of a n*n matrix where n is the no. of vertices present. In the graph, this consists of values either 0 or 1.

12. What is a back edge?

The possibility of reaching an already marked vertex is indicated by a dashed line,

in a graph is called as back edge.

13. What is a single source shortest path problem?

Given as an input, a weighted graph, G=<V,E> and a distinguished vertex „S as the source vertex. Single source shortest path problem finds the shortest weighted path from s to every other vertex in G.

14. Explain about Unweighted shortest path.

Single source shortest path finds the shortest path from the source to each and every vertex present in a unweighted graph. Here no cost is associated with the edges connecting the vertices. Always unit cost is associated with each edge.

15. Explain about Weighted shortest path

Single source shortest path finds the shortest path from the source to each and every vertex present in a weighted graph. In a weighted graph some cost is always associated with the edges connecting the vertices.

16.What are the methods to solve minimum spanning tree?

a) Prim s algorithm

b) Kruskal s algorithm

17.Explain briefly about Prim s algorithm

Prim s algorithm creates the spanning tree in various stages. At each stage, a node is picked as the root and an edge is added and thus the associated vertex along with it.

18. Define a depth first spanning tree.

The tree that is formulated by depth first search on a graph is called as depth first spanning tree. The depth first spanning tree consists of tree edges and back edges.

19. What is a tree edge?

Traversal from one vertex to the next vertex in a graph is called as a tree edge.

**************