Comprehensive Lab (1).docx

UNIT-1 1. What is security? In general, security is defined as “the quality or state of being secure—to be free from danger.” Security is often achieved by means of several strategies usually undertaken simultaneously or used in combination with one another. 2. What are the different Information Security Components?  Confidentiality  Integrity  Availability (CIA) 3. List out the different characteristics of information? Confidentiality Integrity Availability Privacy Identification Authentication Authorization Accountability Accuracy Utility Possession 4. Define Confidentiality. Confidentiality of information ensures that only those with sufficient privileges may access certain information. When unauthorized individuals or systems can access information, confidentiality is breached. To protect the confidentiality of information, a number of measures are being used. 5. Define Integrity Integrity is the quality or state of being whole, complete, and uncorrupted. The integrity of information is threatened when it is exposed to corruption, damage, destruction, or other disruption of its authentic state. 6. Define Availability Availability is the characteristic of information that enables user access to information without interference or obstruction and in a required format. A user in this definition may be either a person or another computer system. Availability does not imply that the information is accessible to any user; rather, it means availability to authorized users. 7. Define Privacy The information that is collected, used, and stored by an organization is to be used only for the purposes stated to the data owner at the time it was collected. This definition of privacy does focus on freedom from observation (the meaning usually associated with the word), but rather means that information will be used only in ways known to the person providing it.

8. Define Identification An information system possesses the characteristic of identification when it is able to recognize individual users. Identification and authentication are essential to establishing the level of access or authorization that an individual is granted. 9. Define Authentication Authentication occurs when a control provides proof that a user possesses the identity that he or she claims. 10. Define Authorization After the identity of a user is authenticated, a process called authorization provides assurance that the user (whether a person or a computer) has been specifically and explicitly authorized by the proper authority to access, update, or delete the contents of an information asset. 11. Define Accountability The characteristic of accountability exists when a control provides assurance that every activity undertaken can be attributed to a named person or automated process. For example, audit logs that track user activity on an information system provide accountability. 12. Define Accuracy Information should have accuracy. Information has accuracy when it is free from mistakes or errors and it has the value that the end users expects. If information contains a value different from the user’s expectations, due to the intentional or unintentional modification of its content, it is no longer accurate. 13. What are the Components of an Information System? Software Hardware Data People Procedures Networks 14. Define Software The software components of IS comprises applications, operating systems, and assorted command utilities. Software programs are the vessels that carry the lifeblood of information through an organization. These are often created under the demanding constraints of project management, which limit time, cost, and manpower. 15. Define Hardware Hardware is the physical technology that houses and executes the software, stores and carries the data, and provides interfaces for the entry and removal of information from the system. Physical security policies deal with hardware as a physical asset and with the protection of these physical assets from harm or theft.

16. Define Data. Data is often the most valuable asset possessed by an organization and is the main target of intentional attacks. The raw, unorganized, discrete(separate, isolated) potentially-useful facts and figures that are later processed(manipulated) to produce information. 17. Define People There are many roles for people in information systems. Common ones include  Systems Analyst  Programmer  Technician  Engineer  Network Manager  MIS (Manager of Information Systems)  Data entry operator 18. Define Procedures A procedure is a series of documented actions taken to achieve something. A procedure is more than a single simple task. A procedure can be quite complex and involved, such as performing a backup, shutting down a system, patching software. 19. Define Networks When information systems are connected to each other to form Local Area Network (LANs), and these LANs are connected to other networks such as the Internet, new security challenges rapidly emerge. 20. What are the different steps involved in SDLC?  Investigation  Analysis  Logical design  Physical design  Implementation  Maintenance and  Search.

UNIT-2 1. Define Threats. A threat is an object, person, or other entity, that represents a constant danger to an asset. To protect an organization’s information, you must 1. Know yourself: (i.e) be familiar with the information to be protected, and the systems that store, transport and process it. 2. Know the threats you face: To make sound decisions about information security, management must be informed about the various threats facing the organization, its application, data and information systems. 2. What are the different categories of threats? 1. Acts of human error or failure 2. Compromises to intellectual property 3. Deliberate acts of espionage or trespass 4. Deliberate acts of information extortion 5. Deliberate acts of sabotage or vandalism 6. Deliberate acts of theft 7. Deliberate software attacks 8. Forces of nature 9. Deviations in quality of service 10. Technical hardware failures or errors 11. Technical software failures or errors 12. Technological obsolescence 3. Define Virus. Segments of code that performs malicious actions. Virus transmission is at the opening of Email attachment files.  Macro virus: Embedded in automatically executing macrocode common in word processors, spreadsheets and database applications.  Boot Virus: infects the key operating files located in the computer’s boot sector. 4. Define Worms. A worm is a malicious program that replicates itself constantly, without requiring another program to provide a safe environment for replication. Worms can continue replicating themselves until they completely fill available resources, such as memory, hard drive space, and network bandwidth. Eg: MS-Blaster, MyDoom, Netsky, are multifaceted attack worms.

5. Define Trojan Horses. Are software programs that hide their true nature and reveal their designed behavior when activated. 6. Define Back Door or Trap Door. A Virus or Worm has a payload that installs a backdoor or trapdoor component in a system, which allows the attacker to access the system at will with special privileges. Eg: Back Orifice 7. Define Polymorphism. A Polymorphic threat is one that changes its apparent shape over time, making it undetectable by techniques that look for preconfigured signatures. These viruses and Worms actually evolve, changing their size, and appearance to elude detection by antivirus software programs. 8. Different Types of Trojans  Data Sending Trojans  Proxy Trojans  FTP Trojans  Security software disabler Trojans  Denial of service attack Trojans (DOS) 9. Define Man-in-the –Middle. Otherwise called as TCP hijacking attack. An attacker monitors packets from the network, modifies them, and inserts them back into the network. This type of attack uses IP spoofing. 10. Define Sniffers. A sniffer is a program or device that can monitor data traveling over a network. Unauthorized sniffers can be extremely dangerous to a network’s security, because they are virtually impossible to detect and can be inserted almost anywhere. Sniffer often works on TCP/IP networks, where they are sometimes called “packet Sniffers”. 11. Define Attacks. An attack is an act of or action that takes advantage of a vulnerability to compromise a controlled system. It is accomplished by a threat agent that damages or steals an organization’s information or physical asset. 12. Define malicious code. The malicious code attack includes the execution of viruses, worms, Trojan horses, and active Web scripts with the intent to destroy or steal information. The state –of-the-art malicious code attack is the polymorphic or multivector, worm.

13. Define IP scan & attack. The infected system scans a random or local range of IP addresses and targets any of several vulnerabilities known to hackers. 14. Define Web browsing. If the infected system has write access to any Web pages, it makes all Web content files (.html,.asp,.cgi & others) infectious, so that users who browse to those pages become infected. 15. Define Unprotected shares. Using vulnerabilities in file systems and the way many organizations configure them, the infected machine copies the viral component to all locations it can reach. 16. Define Mass Mail. By sending E-mail infections to addresses found in the address book, the infected machine infects many users, whose mail -reading programs also automatically run the program & infect other systems. 17. Define Simple Network Management Protocol (SNMP). By using the widely known and common passwords that were employed in early versions of this protocol, the attacking program can gain control of the device. Most vendors have closed these vulnerabilities with software upgrades. 18. Define Password Crack Attempting to reverse calculate a password is often called cracking. A password can be hashed using the same algorithm and compared to the hashed results, If they are same, the password has been cracked. The (SAM) Security Account Manager file contains the hashed representation of the user’s password. 19. Define Brute Force The application of computing & network resources to try every possible combination of options of a password is called a Brute force attack. This is often an attempt to repeatedly guess passwords to commonly used accounts, it is sometimes called a password attack. 20. Define Spoofing It is a technique used to gain unauthorized access to computers, where in the intruder sends messages to a computer that has an IP address that indicates that the messages are coming from a trusted host.

UNIT-3 1. What are the different steps involved in risk management? There are three steps  Risk Identification.  Risk Assessment  Risk Control 2. Define Risk Identification. It is the process of examining and documenting the security posture of an organization’s information technology and the risk it faces. 3. Define Risk Assessment. It is the documentation of the results of risk identification. 4. Define Risk Control. It is the process of applying controls to reduce the risks to an organization’s data and information systems. To keep up with the competition, organizations must design and create safe environments in which business process and procedures can function. 5. What are the different assets of an organization? Includes all the elements of an organization’s system, such as people, procedures, data and information, software, hardware, and networking elements. 6. Define Risk control strategies. Four basic strategies to control each of the risks that result from these vulnerabilities.  Apply safeguards that eliminate the remaining uncontrolled risks for the vulnerability [Avoidance]  Transfer the risk to other areas (or) to outside entities[transference]  Reduce the impact should the vulnerability be exploited[Mitigation]  Understand the consequences and accept the risk without control or mitigation[Acceptance] 7. Define Transference. Transference is the control approach that attempts to shift the risk to other assets, other processes, or other organizations.

8. Define Mitigation. It is the control approach that attempts to reduce the impact caused by the exploitation of vulnerability through planning & preparation. Mitigation begins with the early detection that an attack is in progress and the ability of the organization to respond quickly, efficiently and effectively. Includes 3 types of plans.  Incident response plan (IRP) -Actions to take while incident is in progress  Disaster recovery plan (DRP) - Most common mitigation procedure.  Business continuity plan (BCP) - Continuation of business activities if catastrophic event occurs. 9. What are the different Characteristics of Secure Information?  Confidentiality  Integrity  Availability  Authentication  Authorization  Accountability  Privacy 10. Define Authentication. The control assures that the entity (person or computer) accessing information assets is in fact the stated entity. Ex: The use of cryptographic certificates to establish SSL connections, or the use of cryptographic hardware tokens such as SecurID cards as a second authentication of identity. 11. Define Authorization. The control assures that a user has been specifically and explicitly authorized to access, update, or delete the contents of an information asset. Ex: Use of access control lists and authorization groups in the Windows networking environment. Another example is the use of a database authorization scheme to verify the designated users for each function. 12. Define Cost Avoidance. It is the process of avoiding the financial impact of an incident by implementing a control. It Includes  Cost Benefit analysis  Organizational feasibility  Operational Feasibility  Technical Feasibility  Political feasibility.

13. Define Single Loss expectancy A Single loss expectancy (SLE) is the calculation of the value associated with the most likely loss from an attack. It is a calculation based on the value of the asset and the exposure factor (EF), which is the expected percentage of loss that would occur from a particular attack. 14. Define Cost Benefit Analysis (CBA) The most common approach for a project of information Security controls and safeguards is the economic feasibility of implementation. Begins by evaluating the worth of information assets are compromised. 15. Define Asset -An asset is the organizational resource that is being protected. -An Asset can be logical, such as Website, information or data - Asset can be physical, such as person, computer system 16. Define Security Blueprint It is the plan for the implementation of new security measures in the organization. Sometimes called a frame work, the blueprint presents an organized approach to the security planning process. 17. Define Security Model A security model is a collection of specific security rules that represents the implementation of a security policy. 18. Define Threat agent A threat agent is the specific instance or component of a threat. For example, you can think of all hackers in the world as a collective threat, and Kevin Mitnick, who was convicted for hacking into phone systems, as a specific threat agent. Likewise, a specific lightning strike, hailstorm, or tornado is a threat agent that is part of the threat of severe storms. 19. Define Vulnerability Weaknesses or faults in a system or protection mechanism that expose information to attack or damage are known as vulnerabilities. Vulnerabilities that have been examined, documented, and published are referred to as well-known vulnerabilities. 20. What are the different types of Access controls?  Mandatory Access Controls (MACs)  Nondiscretionary Controls  Discretionary Access Controls ( DAC)  Lattice-based Access Control

UNIT –IV 1. Define policy? The course of action used by organization to convey instructions from management to those who perform duties. Policies are organizational laws. For a policy to be effective, it must be properly disseminated, read, understood, and agreed to by all members of organization and uniformly enforced. 2. Define Standards and practices? Standards, more detailed statements of what must be done to comply with policy Practices, procedures, and guidelines effectively explain how to comply with policy. 3. What is use of information security policy? It provides rules for the protection of the information assets of the organization. The task of information security professionals is to protect the confidentiality. Integrity, and availability of information and information systems, whether in the state of transmission, storage, or processing. 4. What is Issue-Specific Security Policy (ISSP)? The ISSP: Addresses specific areas of technology requires frequent updates and contains statements on organization’s position on specific issue. Three approaches when creating and managing ISSPs:  Create a number of independent ISSP documents  Create a single comprehensive ISSP document  Create a modular ISSP document 5. What is Systems-Specific Policy (SysSP)? SysSPs frequently function as standards and procedures used when configuring or maintaining systems. Systems-specific policies fall into two groups  Managerial guidance  Technical specifications 6. Define Policy Management? Policies are living documents that must be managed and nurtured, and they are constantly changing and growing. These documents must be properly disseminated and managed. To remain viable, security policies must have: Individual responsible for the policy (policy administrator) A schedule of reviews Method for making recommendations for reviews Specific policy issuance and revision date Automated policy management

7. Describe information Security blueprint? Basis for design, selection, and implementation of all security policies, education and training programs, and technological controls. More detailed version of security framework (outline of overall information security strategy for organization). Should specify tasks to be accomplished and the order in which they are to be realized. Should also serve as scalable, upgradeable, and comprehensive plan for information security needs for coming years. 8. What is ISO 17799/BS7799? One of the most widely referenced and often discussed security models. Framework for information security that states organizational security policy is needed to provide management direction and support. Purpose is to give recommendations for information security management. Provides a common basis for developing organizational security 9. List NIST Security Models? Documents available from Computer Security Resource Center of NIST  SP 800-12, The Computer Security Handbook  SP 800-14, Generally Accepted Principles and Practices for Securing IT Systems  SP 800-18, The Guide for Developing Security Plans for IT Systems  SP 800-26, Security Self-Assessment Guide for Information Technology Systems  SP 800-30, Risk Management Guide for Information Technology Systems 10. What is IETF (Internet Engineering Task Force) Security Architecture? Security Area Working Group acts as advisory board for protocols and areas developed and promoted by the Internet Society. RFC 2196: Site Security Handbook covers five basic areas of security with detailed discussions on development and implementation. 11. Describe VISA International Security Model? Visa International, the credit card processing vendor, promotes strong security measures in its business associates, and has established guidelines for the security of its information systems. Visa has developed two important documents that improve and regulate its information systems: “Security Assessment Process” and “Agreed Upon Procedures.” Using the two documents, a security team can develop a sound strategy for the design of good security architecture. The only down side to this approach is the very specific focus on systems that can or do integrate with VISA’s systems with the explicit purpose of carrying the aforementioned cardholder information. 12. What is Baselining and Best Business Practices? Baselining and best practices are solid methods for collecting security practices, but provide less detail than a complete methodology. Possible to gain information by baselining and using best practices and thus work backwards to an effective design.

13. Describe about Spheres of security? Spheres of security: foundation of the security framework. Levels of controls. Management controls cover security processes designed by strategic planners and performed by security administration. Operational controls deal with operational functionality of security in organization. Technical controls address tactical and technical implementations related to designing and implementing security in organization. 14. What is meant by defense in depth and security perimeter? Defense in depth of Implementation of security in layers. Requires that organization establish sufficient security controls and safeguards so that an intruder faces multiple layers of controls, Security perimeter. Point at which an organization’s security protection ends and outside world begins. Does not apply to internal attacks from employee threats or on-site physical threats 15. What is use of firewall, DMZ, proxy servers and IDS? Firewall: device that selectively discriminates against information flowing in or out of organization. DMZs: no-man’s land between inside and outside networks where some place Web servers. Proxy servers: performs actions on behalf of another system. Intrusion detection systems (IDSs): in effort to detect unauthorized activity within inner network, or on individual machines, organization may wish to implement an IDS. 16. List various plans in continuity strategies?  Incident response plans (IRPs);  disaster recovery plans (DRPs);  business continuity plans (BCPs) 17. What are the primary functions of various plans in continuity strategies? IRP focuses on immediate response; if attack escalates or is disastrous, process changes to disaster recovery and BCP. DRP typically focuses on restoring systems after disasters occur; as such, is closely associated with BCP. BCP occurs concurrently with DRP when damage is major or long term, requiring more than simple restoration of information and information resources. 18. What is contingency planning (CP)? It comprises a set of plans designed to ensure the effective reaction to and recovery from an attack and the subsequent restoration to normal modes of business operations.

19. What are the six steps to contingency planning?  Identifying the mission- or business-critical functions  Identifying the resources that support the critical functions,  Anticipating potential contingencies or disasters,  Selecting contingency planning strategies  Implementing the contingency strategies  Testing and revising the strategy 20. List members in contingency planning team? Champion: high-level manager to support, promote, and endorse findings of project Project manager: leads project and makes sure sound project planning process is used, a complete and useful project plan is developed, and project resources are prudently managed Team members: should be managers, or their representatives, from various communities of interest, business, IT, and information security

UNIT-V 1. What is IDS? An intrusion detection system (IDS) is a type of security software designed to automatically alert administrators when someone or something is trying to compromise information system through malicious activities or through security policy violations. 2. Why use an IDS? To prevent problem behaviors by increasing the perceived risk of discovery and punishment To detect attacks and other security violations not prevented by other security measures To detect and deal with the preambles to attacks To document existing threat to an organization To act as quality control for security design and administration To provide useful information about intrusions that do take place 3. Give classification of IDS. All IDSs use one of two detection methods: Signature-based Statistical anomaly-based IDSs operate as: Network-based Host-based Application-based systems 4. What is network-based IDS? A network-based intrusion detection system (NIDS) is used to monitor and analyze network traffic to protect a system from network-based threats. A NIDS reads all inbound packets and searches for any suspicious patterns. When threats are discovered, based on its severity, the system can take action such as notifying administrators, or barring the source IP address from accessing the network. 5. What is Host-based IDS? A host-based intrusion detection system (HIDS) is a system that monitors a computer system on which it is installed to detect an intrusion and/or misuse, and responds by logging the activity and notifying the designated authority. A HIDS can be thought of as an agent that monitors and analyzes whether anything or anyone, whether internal or external, has circumvented the system’s security policy.

6. How does an Application-Based IDS (AppIDS) differ from a host-based IDS? A refinement of the host-based IDS is the application-based IDS (AppIDS). Whereas the HIDS examines a single system for file modification, the application-based IDS examines an application for abnormal events. 7. What is Signature-Based IDS? A knowledge-based (Signature-based) Intrusion Detection Systems (IDS) references a database of previous attack signatures and known system vulnerabilities. Examine data traffic in search of patterns that match known signatures 8. What is Statistical Anomaly-Based IDS (or) behavior-based IDS? The statistical anomaly-based IDS (stat IDS) or behavior-based IDS sample network activity to compare to traffic that is known to be normal. When measured activity is outside baseline parameters or clipping level, IDS will trigger an alert. IDS can detect new types of attacks. 9. Give some possible responses of IDS?  Audible/visual alarm  SNMP traps and plug-ins  E-mail message  Page or phone message  Log entry  Evidentiary packet dump  Take action against the intruder  Launch program  Reconfigure firewall  Terminate session or connection 10. Write about strengths of IDS.  Monitoring and analysis of system events and user behaviors.  Testing security states of system configurations.  Baselining security state of system and then tracking any changes to that baseline.  Recognizing patterns of system events that correspond to known attacks.  Recognizing patterns of activity that statistically vary from normal activity.  Managing operating system audit and logging mechanisms and the data they generate.  Alerting appropriate staff by appropriate means when attacks are detected.  Measuring enforcement of security policies encoded in the analysis engine.  Providing default information security policies.  Allowing non-security experts to perform important security monitoring functions.

11. Write about limitations of IDS.  Compensating for weak or missing security mechanisms in the protection infrastructure.  Instantaneously detecting, reporting, responding to attack during heavy network/processing load.  Detecting newly published attacks or variants.  Effectively responding to sophisticated attacks.  Automatically investigating attacks.  Resisting all attacks intended to defeat them.  Compensating for fidelity issues of data sources.  Dealing effectively with switched networks. 12. List control strategies in the deployment and implementation of an IDS.  Centralized: all IDPS control functions are implemented and managed in a central location  Fully distributed: all control functions are applied at the physical location of each IDPS component  Partially distributed: combines the best of the other two strategies; while individual agents still analyze and respond to local threats, their reporting to a hierarchical central facility enables the organization to detect widespread attacks 13. How does the effectiveness of IDS measured? Once implemented, IDSs are evaluated using two dominant metrics:  Administrators evaluate the number of attacks detected in a known collection of probes.  Administrators examine the level of use, commonly measured in megabits per second of network traffic, at which the IDPSs fail. 14. What is Honey pots, Honey Nets and Padded Cell? A class of powerful security tools that go beyond routine intrusion detection is known variously as honey pots, honey nets, or padded cell systems Honeypots: decoy systems designed to lure potential attackers away from critical systems. Honeynets: collection of honeypots connecting several honey pot systems on a subnet. Padded cell: honeypot that has been protected so it cannot be easily compromised. 15. What are Port mappers? Identify computers that are active on a network, as well as their active ports and services, the functions and roles fulfilled by the machines, and other useful information

16. What is use of Scanning and Analysis Tools and list them? Used to find vulnerabilities in systems, holes in security components, and other unsecured aspects of the network such as:  Port mappers  Network mappers  Firewall analysis  OS detection tools  Vulnerability scanners  Packet sniffers  Wireless sniffers  Password crackers 17. What is Network mappers? Software tools that identify all systems connected to a network. Eg. Nmap, LanState and SolarWinds’ LanSurveyor 18. What is Firewall analysis? Several tools automate remote discovery of firewall rules and assist the administrator in analyzing them. 19. What is OS detection tools? Detecting a target computer’s operating system (OS) is very valuable to an attacker. There are many tools that use networking protocols to determine a remote computer’s OS, e.g. Nmap, Xprobe. 20. What is packet sniffers? A network tool that collects and analyzes packets on a network. It can be used to eavesdrop on network traffic. Connects directly to a local network from an internal location.

UNIT-II 1. What is Stack? Stack is a linear and static data structure. Stack is an ordered collection of elements in which insertion and deletion of elements is performed at only one end called Top. Initial condition of the stack Top=-1. It is otherwise called as LIFO (Last In First Out). 2. What are the various operations that can be performed on stack? In Stack, we can perform two operations namely Push and Pop. Push: Push means inserting a new element into the stack. Insertion can be done by incrementing top by 1. Pop: Pop means deleting an element from the stack. Deletion can be done by decrementing top by 1. 3. What do you mean by Top in Stack? Top is the pointer which always points the top element of the Stack. If Top =-1, then Stack is Empty. We can insert a new element into stack by incrementing top by 1. We can delete an element from stack by decrementing top by 1. 4. What are the applications of Stack? i. Matching of nested parenthesis in a mathematical expression. ii. Conversion of infix to postfix. iii. Evaluation of postfix. iv. Towers of Hanoi v. Shipment in cargo vi. Arrangement of books/plates in table 5. What are the conditions that should be satisfied in the matching of nested parenthesis? Matching of nested parenthesis should satisfy the following two conditions: i. Number of opening parenthesis should be equal to the number of closing parenthesis. ii. The closing parenthesis should be preceded by the matching opening parenthesis. 6. What are types of Expression? Expression is classified as three types according to position of operator with respect to the operands. They are: i. Infix: The operator is placed in between two operands. E.g.: A+B. ii. Postfix: The operator is placed after the operands. E.g.: AB+. iii. Prefix: The operator is placed before the operands. E.g.: +AB.

7. What is Queue? Queue is a linear and static data structure. Queue is an ordered collection of elements in which we can insert an element at one end called Rear and delete an element at another end called Front. Initial condition of the stack Rear=Front=-1. It is otherwise called as FIFO (First In First Out). 8. What are the various operations that can be performed on Queue? In Queue, we can perform two operations namely Insertion and Deletion. Enqueue: Insertion can be done by incrementing Rear by 1. Dequeue: Deletion can be done by incrementing Front by 1. 9. What do you mean by Queue empty? If Queue has no data, then it is called as Queue Empty. Queue may be empty on two conditions. i. Front = Rear = -1 and ii. Front = = Rear while performing dequeue. 10. What is Linked list? Linked list is a dynamic and linear data structure. Linked list is an ordered collection of elements in which each element is referred as a Node. Node has two parts. Data field and link field. 11. What are various fields in a Linked list? Each node has two fields namely i. Data field or Information field: Data field contains the actual data. ii. Address field or Link field: Address field contains the address of next node in list. 12. Define Head Pointer? Head pointer is the pointer which always points the first node in the list. Head pointer holds the address of the first node. Using Head pointer only we can move from first node to last node. 13. What are the types of Linked List? There are three types of Linked list. They are i. Single Linked list, ii. Double Linked list

iii. Circular Linked list.

14. List out the application of a linked list  Manipulation of polynomials  Implementation of Stacks and Queues  Sparse matrices

15. What is Single linked list? In Single linked list, each node has data to be stored and one link to the next node. In Single linked list, we can move only in one direction from head pointer to Null pointer. Each node has two fields namely: i. Data field or Information field and ii. Address field or Link field. It is otherwise called as Linear Linked list. 16. What is Double Linked list? Double linked list is a linked list where the elements can be traversed both in forward direction and also in backward direction. 17. What is Circular Single Linked list? In Circular Single linked list, the last node is connected to the first node. In Circular Single linked list, we can move only in one direction from head pointer to Null pointer. 18. List the advantages and drawbacks of circular linked list. Advantages: If we are at a node, we can to go to any node.But in linear list,it’s not possible to go to previous node. It saves time in traversing from last node to 1st node than in double linked list which traverse entire list backwards. Drawbacks: It is not easy to reverse a list. Accessing previous element cannot be done in single step. 19. What is Circular Double Linked list? In Circular Double linked list, the last node is connected to the first node. In Circular Double Linked list, we can move in both the direction from head pointer to Null address or vice versa. 20. Define Priority Queue. Priority Queue is the ordered collection of elements which are placed on the priority. Insertion and deletion are done according to the priority. There are two types of Priority Queue. They are i. Ascending Priority Queue and ii. Descending Priority Queue.

UNIT-III 1. Define Tree .Give an example. Tree is a non-linear data structure, where there is no linear relation between the data items. It can be defined as finite set of more than one node. There is a special node designated as root node. The remaining nodes are partitioned into sub-trees(T1, T2,…,Tn) of a tree T. 2. Define a path in a tree. Give example. The path in a tree is referred as the nodes in which the successive nodes are connected by the edge in a tree. Example: In the above tree,the path from A to I is A – B, B – D, D – I. A path from a node n1 to nk is defined as the sequence of nodes n1, n2…..nk such that ni is the parent of ni+1 for 1
9. Define height of the node and tree? The height of a node is the length of the longest downward path between the node and a leaf. The height of a tree is the length of the longest downward path between the root and a leaf. 10. Define binary tree A binary tree is a tree, which is, either empty or consists of a root node and two disjoint binary trees called the left sub-tree and right sub-tree. In a binary tree, no node can have more than two children. 11. List the properties of binary tree. In any binary tree, the maximum number of nodes on level L is 2L , where L ≥0. The maximum number of nodes possible in a binary tree of height H is 2H -1. The minimum number of nodes possible in a binary tree of height H is h. The height of a complete binary tree with n number of nodes is log2(n+1). 12. What is meant by full binary tree? A Full binary tree is a binary tree in which all intermediate nodes have same degree as 2 and all leaves are at the same level. 13. What is meant by complete binary tree? A binary tree is said to be a complete binary tree if all its levels, except possibly the last level, have the maximum number of possible nodes, and all the nodes in the last level appear as far left as possible. 14. What are the different ways of representing a binary tree?  Linear representation using arrays  Linked representation using pointers 15. What is meant by binary tree traversal? Traversing a binary tree means moving through all the nodes in the binary tree visiting each node in the tree only once. 16. What are the difference binary tree traversal techniques?  Inorder traversal  Preorder traversal  Postorder traversal

17. Define a binary search tree. A binary tree T is termed binary search tree or binary sorted tree, if each node N of T satisfies the following property: “The value at N is greater than every value in the left sub-tree of N and is less than every value in the right sub-tree of N”. 18. Define B – Tree and its properties. B-tree is a self-balancing tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children. B tree is a m-way search tree, such that, All leaf nodes are at same level. All internal nodes have m/2 to m children. Root have atleast two children unless it act as leaf node. The number of keys is one less than the number of children for non-leaf nodes and m/2 to m for leaf nodes. 19. Define B+ tree and its properties. A B+ tree is a rooted tree satisfying the following properties:  All paths from root to leaf are of the same length  Leaf nodes store the actual record. Other nodes only have an index that is used to access that record  Each internal node has n/2 to n children.  Each leaf node has between (n–1)/2 and n–1 values  Left child of parent is strictly less than the parent node and the right child of parent is greater than or equal to parent node. 20. Define AVL tree. AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the left and right sub-trees of any node differ by at most one Balance Factor(BF) = Height(Left Sub-tree) – Height(Right sub-tree). BF can be either -1, 0 or +1. If not tree should be balanced by making single or double rotations. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes.

UNIT-I 1. Define Data Structure. A data structure is a data organization, management and storage format that enables efficient access and modification. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data. 2. In what areas do data structures are applied? Data structures are essential in almost every aspect where data is involved. In general, algorithms that involve efficient data structure is applied in the following areas: numerical analysis, operating system, A.I., compiler design, database management, graphics, and statistical analysis, to name a few. 3. When is a binary search best applied? A binary search is an algorithm that is best applied to search a list when the elements are already in order or sorted. The list is searched starting in the middle, such that if that middle value is not the target search key, it will check to see if it will continue the search on the lower half of the list or the higher half. The split and search will then continue in the same manner. 4. Which data structures are applied when dealing with a recursive function? Recursion, is a function that calls itself based on a terminating condition, makes use of the stack. Using LIFO, a call to a recursive function saves the return address so that it knows how to return to the calling function after the call terminates. 5. How does dynamic memory allocation help in managing data? Apart from being able to store simple structured data types, dynamic memory allocation can combine separately allocated structured blocks to form composite structures that expand and contract as needed. 6. What is merge sort? Merge sort, is a divide-and-conquer approach for sorting the data. In a sequence of data, adjacent ones are merged and sorted to create bigger sorted lists. These sorted lists are then merged again to form an even bigger sorted list, which continues until you have one single sorted list. 7. What is a linear search? A linear search refers to the way a target key is being searched in a sequential data structure. In this method, each element in the list is checked and compared against the target key. The process is repeated until found or if the end of the file has been reached.

8. What are dynamic data structures? Dynamic data structures are structures that expand and contract as a program runs. It provides a flexible means of manipulating data because it can adjust according to the size of the data. 9. Which sorting algorithm is considered the fastest? There are many types of sorting algorithms: quick sort, bubble sort, balloon sort, radix sort, merge sort, etc. Not one can be considered the fastest because each algorithm is designed for a particular data structure and data set. It would depend on the data set that you would want to sort. 10. What is a bubble sort and how do you perform it? A bubble sort is one sorting technique that can be applied to data structures such as an array. It works by comparing adjacent elements and exchanges their values if they are out of order. 11. Differentiate linear from a nonlinear data structure. The linear data structure is a structure wherein data elements are adjacent to each other. Examples of linear data structure include arrays, linked lists, stacks, and queues. On the other hand, a non-linear data structure is a structure wherein each data element can connect to more than two adjacent data elements. Examples of nonlinear data structure include trees and graphs. 12. What is Fibonacci search? Fibonacci search is a search algorithm that applies to a sorted array. It makes use of a divide-and-conquer approach that can significantly reduce the time needed in order to reach the target element. 13. Briefly explain recursive algorithm. Recursive algorithm targets a problem by dividing it into smaller, manageable subproblems. The output of one recursion after processing one sub-problem becomes the input to the next recursive process. 14. What are the various operations that can be performed on different Data Structures?  Insertion: Add a new data item in the given collection of data items.  Deletion: Delete an existing data item from the given collection of data items.  Traversal: Access each data item exactly once so that it can be processed.  Searching: Find out the location of the data item if it exists in the given collection of data items.  Sorting: Arranging the data items in some order i.e. in ascending or descending order in case of numerical data and in dictionary order in case of alphanumeric data.

15. How is an Array different from Linked List?  The size of the arrays is fixed, Linked Lists are Dynamic in size.  Inserting and deleting a new element in an array of elements is expensive, whereas both insertion and deletion can easily be done in Linked Lists.  Random access is not allowed in Linked Listed. 16. What is Stack and where it can be used? Stack is a linear data structure which the order LIFO (Last In First Out) or FILO(First In Last Out) for accessing elements. Basic operations of stack are: Push, Pop , Peek. Applications of Stack:  Infix to Postfix Conversion using Stack  Evaluation of Postfix Expression  Reverse a String using Stack 17. What are Infix, prefix, Postfix notations? Infix notation: X + Y – Operators are written in-between their operands. This is the usual way we write expressions. An expression such as A*(B+C)/D Postfix notation (also known as “Reverse Polish notation”): X Y + Operators are written after their operands. The infix expression given above is equivalent to A B C + * D/ Prefix notation (also known as “Polish notation”): + X Y Operators are written before their operands. The expressions given above are equivalent to /*A+BCD 18. What does sorting mean? Ordering the data in an increasing or decreasing fashion, according to some linear relationship among the data items is called sorting .19. What are the two main classification of sorting based on the source of data? According to the source of data sorting is classified into, a. External sorting b. Internal sorting 20. What does internal and external sorting mean? Internal sorting is a process of sorting the data in the main memory. External sorting is a process of sorting in which large blocks of data stored in storage device are moved to the main memory and then sorted.

UNIT-IV 1. Define a graph. A graph is a non-linear data structure that represents less relationship between its adjacent elements. There is no hierarchical relationship between the adjacent elements in case of graphs. 2. List the two types of graphs.  Directed graph  Undirected graph 3. Define undirected graph. If an edge between any two nodes in a graph is not directionally oriented a graph is called as undirected graph. It is also referred as unqualified graph. 4. Define directed graph. If an edge between any two nodes in a graph is directionally oriented, a graph is called as directed graph; it is also referred as a digraph. 5. Define a path in a graph. A path in a graph is defined as a sequence of distinct vertices each adjacent to the next, except possibly the first vertex and last vertex is different. 6. Define a cycle in a graph. A cycle is a path containing at least three vertices such that the starting and the ending vertices are the same. 7. Define a strongly connected graph. A directed graph is said to be strongly connected if, for every pair of distinct vertices there is a directed path from every vertex to every other vertex. It is also referred as a complete graph. 8.

Define a weakly connected graph. A directed graph is said to be weakly connected graph, if any vertex doesn’t have a directed path to any other vertices. 9. Define a weighted graph. A graph is said to be weighted graph if every edge in the graph is assigned some weight or value. The weight of an edge is a positive value that may be representing the distance between the vertices or the weights of the edges along the path.

10. What is meant by traversing a graph? State the different ways of traversing a graph. Traversing a graph means visiting all the nodes in the graph. In many practical applications traversing a graph is important, such that each vertex is visited once systematically by traversing through minimum number of paths. The two important graph traversal methods are,  Depth-first traversal(or) Depth-first search(DFS)  Breath-first traversal(or)Breath-first search(BFS) 11. What is meant by topological sorting? Topological sorting is an ordering of the vertices in a directed acyclic graph, such that if there is a path from x to y, then y appears after x in the ordering. As each vertices is visited, push the vertex in to the stack. Finally print the stack elements in order. 12. What is the use of Dijkstra’s algorithm? Dijkstra’s algorithm is a greedy algorithm to find the minimum distance from a node to all other nodes. Our aim is to visit any two nodes, with a minimum weight, such that the distance travelled is minimum. One such algorithm is referred as Dijkstra’s shortest path algorithm. This is very much used in travelling salesman problem. 13. Define spanning trees? A spanning tree of a graph is just a sub graph that contains all the vertices of the graph, but uses sufficient edges to form a tree. A graph may have spanning trees. 14. Define minimum spanning trees? A minimum spanning tree is one of the spanning trees of the graph which has the smallest sum of weights amongst all spanning trees. 15. How can you minimum spanning trees from graphs? You can create minimum spanning trees from graphs using two different greedy algorithms. They are,  Prim’s algorithm  Kruskal’s algorithm 16. How can you create minimum spanning tree using prim’s algorithm? In Prim’s algorithm, for creating minimum spanning tree, start with any node and include the other node in the spanning tree, on the basis of its weight of their edges connected to that node, and move on until it includes all the n vertices are connected by n-1 edges. The resulting tree contains all the vertices present in the given graph, such that the weight of the edges in the resulting tree is minimum. The tree produced by the above algorithm, is the minimum spanning tree.

17. How can you create minimum spanning tree using Kruskal’s algorithm? In Kruskal’s algorithm, for creating minimum spanning tree, sort the edges in the graph on increasing order by its weight. Take the first edge from the ordered list and add the source vertex to form a tree. Check whether the destination vertex to the tree. If it already exists, move to the next edge in the ordered list. Repeat the steps until the tree contains all the n vertices. The tree produced by the above algorithm, is the minimum spanning tree. 18. Explain the following terms i)Degree ii)indegree iii)outdegree i) Degree-it denotes the number of edges for a node ii) In degree-Number of edges entering from the vertex iii) The number of edges exiting from the vertex. 19. What is Acyclic graph? If there is no path from any node back to itself then the graph is said to be acyclic graph. 20. Define the term Prim’s Algorithm. In a graph a pair with the minimum weight is to be chosen. Then adjacent to these vertices is the edge having minimum weight is selected ie., in each stage, one node is picked as the root, then add an edge and thus an associated vertex to the tree.

UNIT-V 1. Define sequential files. Sequential files have data records stored in a specific sequence. A sequentially organized file may be stored on either a serial-access or a direct-access storage medium. 2. What are the methods used for transaction logging? The common method is to use transaction logging this works as follows:  Collect records for insertion in a transaction file in their order of arrival.  When population of the transaction file has ceased, sort the transaction file in the order of the key of the primary data file.  Merge the two files on the basis of the key to get a new copy of the primary sequential file. 3. What do you mean by insertion in sequential files? Records must be inserted at the place dictated by the sequents of the keys. As it is obvious direct insertion in ti the main data file would lead to frequent rebuilding of the file. This problem could be mitigated by reserving overflow areas in the file for insertions. But this leads to wastage of space and also the overflow areas may also be filled. 4. What do you mean by deletion in sequential files? Deletion is the reverse process of insertion. The space occupied by the record should be free for use. Usually deletion (like insertion) is not done immediately. The concerned record (along with a marker or `tombstone‟ to indicate deletion) is a transaction file. At the time of merging the corresponding data record will be dropped from the primary data file. 5. What do you mean by updation in sequential files? Updation is a combination of insertion and deletions. The record with the new values is inserted and the earlier version deleted. This is also done using transaction files. 6. What do you mean by retrival in sequential files? User programs will often retrieve data for viewing prior to making decisions, therefore, is is vital that this data reflects the latest state of the data if the merging activity has not yet taken place. 7. What do you mean by indexed sequential files? An index in a set of Y, address pairs. A sequential (or sorted on primary keys) file that is indexed is called an index sequential file, The index provides for random access to records, while the sequential nature of the file provides easy access to the subsequent records as well as sequential processing.

8. Define a field. It is an elementary data item characterized by its size, length and type. For example: Name: A character type of size 10 ; Age: A numeric type. 9. Define a record. It is a collection of related fields that can be treated as a unit from an applications point of view. For example,: A university could use a student‟s record with the fields, university enrolment no., name, major subjects. 10. Define an index file. An index file corresponds to a data file. Its records contain a key field and a pointer to that record of the data file which has the same value of the key field. The data stored in files is accessed by software which can be divided into the following two categories. 11. What Is The Need For Extendible Hashing? If either open addressing hashing or separate chaining hashing is used, the major problem is that collisions could cause several blocks to be examined during a Find, even for a welldistributed hash table. Extendible hashing allows a find to be performed in two disk accesses. Insertions also require few disk accesses. 12. What Do You Mean By Rehashing? If the table gets too full, the running time for the operations will start taking too long and inserts might fail for open addressing with quadratic resolution. A solution to this is to build another table that is about twice as big with the associated new hash function and scan down the entire original hash table, computing the new hash value for each element and inserting it in the new table. This entire operation is called rehashing. 13. What Do You Mean By Double Hashing? Double hashing is an open addressing collision resolution strategy in which F(i)=i.hash2(X). This formula says that we apply a second hash function to X and probe at a distance hash2(X), 2hash2(X),….,and so on. A function such as hash2(X)=R-(XmodR), with R a prime smaller than Tablesize. 14. Write The Importance Of Hashing?  Maps key with the corresponding value using hash function.  Hash tables support the efficient addition of new entries and the time spent on searching for the required data is independent of the number of items stored.

15. What Do You Mean By Hash Function? A hash function is a key to address transformation which acts upon a given key to compute the relative position of the key in an array. The choice of hash function should be simple and it must distribute the data evenly. A simple hash function is hash_key=key mod tablesize. 16. What Do You Mean By Hash Table? The hash table data structure is merely an array of some fixed size, containing the keys. A key is a string with an associated value. Each key is mapped into some number in the range 0 to tablesize-1 and placed in the appropriate cell. 17. Define Hashing? Hashing is the transformation of string of characters into a usually shorter fixed length value or key that represents the original string. Hashing is used to index and retrieve items in a database because it is faster to find the item using the short hashed key than to find it using the original value. 18. Define symbol table. Symbol table is an important data structure created and maintained by compilers in order to store information about the occurrence of various entities such as variable names, function names, objects, classes, interfaces, etc. Symbol table is used by both the analysis and the synthesis parts of a compiler. 19. What is an inverted page table? The simplest form of an inverted page table contains one entry per physical pagein a linear array. Since the table is shared, each entry must contain the process ID of the page owner. And since physical pages are now mapped to virtual, each entry contains a virtual page number instead of a physical. 20. Define static and dynamic tree table. Static Data structure has fixed memory size whereas in Dynamic Data Structure, the size can be randomly updated during run time which may be considered efficient with respect to memory complexity of the code. Static Data Structure provides easier access to elements with respect to dynamic data structure.