Home / Archived For November 2012

Wednesday, November 28, 2012

Solved MCQ of System Analysis and Design Set-3

Solved MCQ of System Analysis and Design Set-3


 Q.1 A ……………… system in no more than idea.
A) Conceptual
B) Logical
C) Physical
D) None

Q.2 Design Phase consists of …………………….
1.       Identity the functions to be performed
2.       Design the input/output and file design
3.       Defining basic parameters for system design
A) 1 & 2
B) 2 & 3
C) 1 & 3
D) 1, 2 & 3


Q.3 A context diagram
A) Describes the context of a system
B) is a DFD which gives an overview of the system
C) is a detailed description of a system
D) is not used in drawing a detailed DFD

Q. 4 HIPO stand for
A) Hierarchy input process output
B) Hierarchy input plus output
C) Hierarchy plus input process output
D) Hierarchy input output Process

Q.5 Statement of scope and objectives, opportunities and performance criteria ………….
A) Problem definition
B) System analysis
C) System Design
D) Documentation

Q.6 Information can be categorized into …………….
1.       Environmental information
2.       Competitive information
3.       Government information
4.       Internal information
A) 1, 2 & 3
B) 1, 2 & 4
C) 2, 3 & 4
D) 1, 3 & 4

Q.7 System Development process is also called as ……………..
A) System Development Life Cycle
B) System Life Cycle
C) Both A and B
D) System Process Cycle

Q.8 The output of problem definition stage is ……………..
A) Master Development Plan
B) Terms of reference
C) Feasibility report
D) Final product

Q.9 Advantages of system flowcharts ………………….
A) Effective communication
B) Effective analysis
C) Queasier group or relationships
D) All A, B, C

Q.10 Based on the identification of objectives, input, output and file content, the vital document is called …
A) System Definition
B) System Document
C) System Requirement Document
D) System Subject

Q.11 A context diagram is used
A) as the first step in developing a detailed DFD of a system
B) in systems analysis of very complex systems
C) as an aid to system design
D) as an aid to programmer

Q.12 Which of the following is/are the sources for project requests?
A) Request from Department managers
B) Request from senior executives
C) Request from system Analyst
D) All of the above

Q.13 DDS stands for …………………
A) Data Data Systems
B) Data Digital System
C) Data Dictionary Systems
D) Digital Data Service

Q.14 ………….. Phase is a time consuming phase and yet a very crucial phase
A) Feasibility Study
B) Requirement Phase
C) Analysis Phase
D) Testing Phase

Q.15 A DFD is normally leveled as
A) It is a good idea in design
B) It is recommended by many experts
C) it is easy to do it
D) It is easier to read and understand a number of smaller DFDs than one large DFD

Q.16 ………………. is responsible for all aspects of data processing, operation research, organization and method, system analysis and design investments.
A) Management Services Director
B) Data Processing Manager
C) Computer Manager
D) Both B and C

Q.17 ……………… is a tabular method for describing the logic of the decisions to be taken.
A) Decision tables
B) Decision tree
C) Decision Method
D) Decision Data

Q.18 In ……………… system the interaction between various subsystems cannot be defined with certainty
A) Open System
B) Closed System
C) Deterministic System
D) Probabilistic System

Q. 19 State True or False.
1.       Term of reference is the final output of Feasibility Study
2.       Design specification report is the final output of System Analysis
A) 1-true, 2-true
B) 1-false, 2-true
C) 1-true, 2-false
D) 1-false, 2-false

Q.20 The key considerations involved in the feasibility analysis is include
i) Economical      ii) Technical         iii) Behavioral     iv) Personal
A) i, ii, iv              
B) i, ii, iii
C) ii, iii, iv
D) All of the above

Answers:
1.       A) Conceptual
2.       D) 1, 2 & 3
3.       B) is a DFD which .... of the system
4.       A) Hierarchy input process output
5.       A) Problem definition
6.       B) 1, 2 & 4
7.       A) System Development Life Cycle
8.       B) Terms of reference
9.       D) All A, B, C
10.   B) System Document
11.   A) as the first step ... DFD of a system
12.   D) All of the above
13.   C) Data Dictionary Systems
14.   C) Analysis Phase
15.   D) It is easier to ..... one large DFD
16.   A) Management Services Director
17.   A) Decision tables
18.   D) Probabilistic System
19.   D) 1-false, 2-false
20.   B) i, ii, iii

     

Sunday, November 25, 2012

Solved MCQ of System Analysis and Design Set-1

Solved MCQ of System Analysis and Design Set-1

Q. 1 …………………………. is an important factor of management information system.
A) System
B) Data
C) Process
D) All

Q.2  Which are the following is / are the level(s) of documentation?
A) Documentation for management
B) Documentation for user
C) Documentation for data processing department
D) All of the above


Q.3 ………………………….. level supply information to strategic tier for the use of top management.
A) Operational
B) Environmental
C) Competitive
D) Tactical

Q.4  In a DFD external entities are represented by a
A) Rectangle
B) Ellipse
C) Diamond shaped box
D) Circle
Q.5  …………… can be defined as data that has been processed into a form that is meaningful to the recipient and is of real or perceive value in current or prospective decisions.
A) System
B) Information
C) Technology
D) Service
Q.6 Use the new system as the same time as the old system to compare the results. This is known as ……
A) Procedure Writing
B) Simultaneous processing
C) Parallel Operation
D) File Conversion

Q.7 Decision making model was proposed by ………………….
A) Harry Goode
B) Herbert A Simon
C) Recon Michal
D) None of this

Q.8 A data flow can
A) Only emanate from an external entity
B) Only terminate in an external entity
C) May emanate and terminate in an external entity
D) May either emanate or terminate in an external entity but not both

Q. 9 …………… can be defined as most recent and perhaps the most comprehensive technique for solving computer problems.
A) System Analysis
B) System Data
C) System Procedure
D) System Record

Q.10 SDLC stands for
A) System Development Life Cycle
B) Structure Design Life Cycle
C) System Design Life Cycle
D) Structure development Life Cycle



Answers:
1.       A) System
2.       D) All of the above
3.       D) Tactical
4.       A) Rectangle
5.       B) Information

6.       C) Parallel Operation
7.       B) Herbert A Simon
8.       C) May emanate and ………entity
9.       A) System Analysis
10.   A) System Development Life Cycle

You Might also view the following Related Posts 

You can view the following other posts

For other more Multiple Choice Questions (MCQs): Click Here

     

Tuesday, November 20, 2012

Database Management System (DBMS)

Database Management System (DBMS)


Data: Data is raw fact or figures or entity. When activities in the organization takes place, the effect of these activities need to be recorded which is known as Data.

          For example, the raw material to be purchased may have many facts like type of raw material, vendor name, address, quantity etc. Likewise Organization will have many transactions and entities which are to be recorded.

Information: Processed data is called information.

A database management system (DBMS) is a collection of program that enables user to create and maintain a database. In other words, the systematic organization of data is called database.

The DBMS is hence general purpose software system that facilities the process of defining constructing and manipulating database for various applications.
  •       Defining a database involves specifying the data types, structures and constraints for the data to be stored in the database.
  •      Constructing the database is the process of storing the data itself on some stored medium that is controlled by the DBMS.
  •       Manipulating database includes such functions as querying the database to retrieve specific data updating the database to reflect change and generation of reports from the data.

DBMS Characteristics

The data processing system should have some characteristics to produce the information. Some of the requirements are listed below.
  •  To incorporate the requirements of the organization, system should be designed for easy maintenance.
  •    Information systems should allow interactive access to data to obtain new information without writing fresh programs.
  •  System should be designed to co-relate different data to meet new requirements.
  •  Data should be stored with minimum redundancy to ensure consist in stored data across different application.
  •  An independent central repository, which gives information and meaning of available data, is required.
  •    Integrated database will helps in understanding the inter-relationships between data stored in different applications.
  •  The stored data should be made available for access by different users simultaneously.
  •  Automatic recovery feature has to be provided to overcome the problems with processing system failure.


Advantage of using a DBMS

The following are the advantages of using DBMS.
1.       Controlling redundancy
2.       Restricting unauthorized access.
3.       Providing persistent storage for program object and data structures.
4.       Permitting interface and actions by using rules.
5.       Providing multiple user interfaces.
6.       Presenting complex relationships among data.
7.       Enforcing integrity constraints.
8.       Providing backup and recovery.


     

Monday, November 12, 2012

E-commerce Security Issues

E-commerce Security Issues

First of all e-commerce is surrounded by different issues such as commercial, Network infrastructure, Social and Cultural and Security issues are presented below which are important for successful business. E-commerce security issues are frequently aired in the press and are certainly important. Customers are concerned that the item ordered won’t materialize, or be as described. As (much worse) they worry about their social security number and credit card details being misappropriated. However rare, these things do happen, and customers need to be assured that all e-commerce security issues have been covered. Your guarantees and returns policies must be stated on the website and they must be adhered to. Let us first state the security attacks on e-commerce process and Security goals we want to achieve for successful e-commerce.

Attacks on Security
Security attacks can be classified in the following categories depending on the nature of the attacker.

a)      Passive Attacks
The attacker can only eavesdrop or monitor the network traffic. Typically, this is the easiest form of attack and can be performed without difficulty in many networking environments, e.g. broadcast type networks such as Ethernet and wireless networks.

b)      Active Attacks
The attacker is not only able to listen to the transmission but is also able to actively alter or obstruct it. Furthermore, depending on the attackers actions, the following subcategories can be used to cover to cover the majority to cover the majority of attacks.

c)       Eavesdropping
This is attack is used to gain knowledge of the transmitted data. This is passive attack which is easily performed in many networking environments as motioned above. However, this attack can easily perform in many networking environments. However this attack can easily be prevented by using an encryption scheme to protect the transmitted data.

d)      Traffic Analysis
The main goal of this attack is not to gain direct knowledge about the transmitted data, but to extra information from the characteristics of the transmission, e.g. amount of data transmitted, identity of the communicating nodes etc. This information may allow the attacked to deduce sensitive information, e.g., the roes of the communicating nodes, their position etc. Unlike the previously described attack, this one is more difficult to prevent.

e)      Impersonation
Here, the attacker uses the identity of another node to gain unauthorized access to resource or data. This attack is often used as a prerequisite to eavesdropping. By impersonating a legitimate node, the attacker can try to gain access to the encryption key used to protect the transmitted data. Once, this key is known by the attacker, she can successfully perform the eavesdropping attack.


f)       Modification
This attack modifies data during the transmission between the communicating nodes, implying that the communicating nodes do not share the same view of the transmitted data. An example could be when the transmitted data represents a financial transaction where the attacker has modified the transactions value.

g)      Insertion
This attack involves an unauthorized party, who inserts new data claiming that it originates from a legitimate party. This attack is related to that of impersonation.

You may also wanted to view the following related posts

You can view the following other posts

         
    Risk of e-commerce

    Risk of e-commerce

    As e-commerce evolves, it will present huge risks for those who don’t take advantage of it. The main risk of e-commerce is that the business won’t capitalize on all it has to offer, while the competition moves ahead. The traditional supply chain consists of the manufacturer, the distributor; the traditional supply chain consists of the manufacturer, the distributor, the retailer, and the end consumer. E-commerce is changing this linear view of the supply chain. Instead of goods flowing from one participant to the next, this new online marketplace can connect each participant to the end-consumer. For some links in the supply chain, increased access to customers could be dangerous as partners could even become competitors.

    In the physical world today, there are requirements for documents to be in writing and for hand-written signatures. Such requirements need to be translated into the electronic realm with the rapid development of electronic commerce and to resolve questions raised regarding the applicability of such legislation to the unique features of the electronic regime. The advent or e-commerce and the use of the digital medium as an alternative to the physical, have created some novel legal issues where there are no clear answers.

    The users of information technology must have trust in the security of information and communication infrastructures, network and systems, in the confidentiality, integrity, and availability of data on them, and in the ability to prove the origin and receipt of data. For communication and transactions occurring over a faceless network, there is a need or reliable methods to authenticate a person’s identity and to ensure the integrity of the electronically transmitted documents.

    The concepts of a secure electronic record and a secure electronic signature, and the rebuttable presumptions that flow from that status, are thus necessary for a viable system of electronic commerce. In the context of electronic commerce, none of the usual indicators of reliability present in a paper-based transaction (the use of paper, letterhead, etc.) exist, making it difficult to know when one can rely on the integrity and authenticity of an electronic record. This lack of reliability can make proving one’s case in court virtually impossible. Rebuttable presumptions with respect to secure records and secure signatures put a relying partying a position to know, at the time of receipt and/or reliance, whether the message is authentic and the integrity of its contents intact and, equally important, whether it will be able to establish both of these facts in court in the event of subsequent disputes.

    You may also wanted to view the following related posts

    You can view the following other posts

         
    Benefits of e-commerce

    Benefits of e-commerce

    Use of e-commerce technologies helps speed up the flow of information and to eliminate unnecessary human intervention; the computer can now accomplish what computers do better than people process routine business transactions quickly and accurately, 24 hours a day. This in turn, frees up people to handle tasks that computers may never be able to do exercising judgment, creativity, and experience to manage exceptions, solve problems and continually improve business processes.

            E-commerce is growing in importance and means unprecedented opportunities for everyone. When a business takes advantage of the power of e-commerce, it will be able to.


            i.            Increase customer satisfaction
    Internet is always open, even on holidays; business is thus always open, 24 hours a day, 7 days a week and 365 days a year. Customers will appreciate the extra access to product updates, shipping details, billing information and more. And since the internet knows no boundaries, customers can shop from home, work, or anywhere they can make a connection. Besides, by connecting the e-commerce and shipping systems, it would be possible to ship products faster and for less money.

          ii.            Increase sales volumes
    The Internet is a new channel to reach new customers. With a web site, a company can automatically become a global provider of goods and services, with an edge over even the largest competitors. Interactive selling is advantageous because a company is no longer limited by shelf-space or inventory concerns but instead offer all products to suit the customers exact specifications.

        iii.            Decrease costs of doing business
    E-commerce helps cut out or streamline processes that eat away profits. For instance exchange of information from advertising to availability updates, can add to the cost of sale. However, the web site can be an efficient, cost-effective communication vehicle. Customers can find timely accurate information in one place when they need it. By using e-commerce, everything from purchase orders to funds transfer can be handled faster and more efficiently. Even payment processing and bookkeeping are easier.


    You may also wanted to view the following related posts

    You can view the following other posts

         

    Sunday, November 11, 2012

    Development of e-commerce

    Development of e-commerce

    Now, most of the companies are using e-commerce technology and going to be used. Even small companies have their own web sites, giving details about their profile, Products and services and are moving up in the e-commerce value chain. Companies that were earlier providing access to information on their respective web sites are now engaging themselves in e-commerce practices. Some of the e-commerce practices which are being done by most of the companies for the development of e-commerce technology for them are as follows.

    a) Better Information technology infrastructure

            E-business models are moving from the proprietary ‘Electronic Data Interchange’ (EDI) ‘Specific’ solutions to internet based ‘mass’ solutions. It has more to do with better computer penetration, increase in number of internet users and high-speed connectivity rather than anything else.

    b) Wider acceptance of online payment system

            Online payment mechanism means ‘payment’ and ‘acceptance’ of virtual money. Any such online payment system requires not only the parties transacting business over the Internet but also a ‘payment gateway’ facilitating such transactions. To begin with, it requires use of credit cards and other modes of online payment using advanced technological tools.

              Master Card has recently introduced Site Data Protection Service (SDP), a comprehensive set of global e-business security services that proactively protects online merchants from hacker intrusions. It is a satellite communications network. Also credit card companies have come out with a technology that proactively helps prevents and skimming by using the ‘intrinsic noise’ properties of magnetic strip, which are unique for every card, to differentiate between and original and cloned cards.

    Apart from credit card based transactions, other proprietary online payment systems to initiate the ‘uninitiated’ to shop on the Internet are:

    • Cybercash: Ensuring encrypted passage over the internet for the data card data.
    • E-Cash: Issued online for use over the Internet and is stored in an electronic device such as a chip card of computer memory. The person who has purchased such cash can use it online for making payments.
    • Online Pay: Online Pay allows consumers to shop online without fear of fraud by allowing them to make purchases without giving out information about their credit card or their checking account to the online vendor.
    • Secure Sockets Layers: It is developed by Netscape, which provides privacy, integrity and authentication through digital certificates. Increasing use of Smart Card has also given fillip to the e-commerce activities. Smart cards store all their information on a chip buried within the card. It works as an electronic purse storing digital money, which could be used over public terminals (Web sites, ATMs, Telephone lines) etc. A new system of credit card transactions over the Internet is being currently developed jointly by Visa and MasterCard with technical assistance from the Internet Information system and cryptology companies like Netscape, IBM. It is known to Secure Electronic Transactions (SET). It is expected that in coming years, SET would become the standard of payment over the Internet. Another important development has the adoption of digital signatures as authentication standards providing integrity, confidentiality and non-repudiation of electronic records. It has paved the way for legal recognition of electronic contracts, an extremely important step in giving legal sanctity to online payment system.

    c) Legal recognition to e-commerce practices. 

          Legal recognition of E-commerce practices has come a long way from the initial adoption of UNCITRAL’s Model Law on Electronic commerce by the General Assembly of the United Nations in early 1997. The purpose of the UNCITRAL Model Law on electronic ecommerce is to encourage the use of electronic commerce and to provide nations with model legislation “governing the use of alternative to paper – based methods of communication and storage of information”. It is based on “fundamental-equivalent” approach and extends notions such as “writing”, “signature” and “original” of traditional paper based requirements to a paperless world. It gives legal acceptance to electronic records and digital signatures. Countries, by adopting the UNCITRAL’s Model Law on Electronic commerce have not only given credence to E-commerce laws globally. The most important element is that the nations’ laws on e-commerce have been based on a similar technology platform, i.e. asymmetric cryptography.


    d) Adoption of security standards by the industry

            Business thrives on safety, security and trust whether it is offline or online. The internet being an open, integrated and public system requires far better security coverage than its offline counterpart. It needs an ‘encryption’ technology that provides (i) confidentially (ii) authentication (iii) Integrity (iv) non repudiation and of electronic transactions.

    1. Confidentiality: The idea that the information should be protected from unauthorized internal as well as external users by making it undecipherable. It uses encryption technology to ‘encrypt’ the information in such a way that only an intended user could ‘decrypt’ the information.
    2. Authentication: It means use of encryption technology to identify the sender of originator of the information. Similarly it should be possible to ensure that the message is sent to the person of whom it is meant.
    3. Integrity: It is to verify that the information, which is received, has not been manipulated during its transmission. On retrieval or receipt at the other end of a communication network the information should appear exactly as it was stored or sent by the sender of originator.
    4. Non-repudiation: It is ensure that sender or originator cannot disown information at a later date. Encryption technologies make it possible to bind messages and message acknowledgements with their originators. 

    You may also wanted to view the following related posts

    You can view the following other posts

         

    Friday, November 9, 2012

    Graph Definition


     
    A graph is a kind of data structure, which is a collection of nodes, called vertices and line segments called arcs or edges that connect pairs of nodes.

             In the concept of mathematics, a graph G is defined as follows: G=(V,E), where V is a finite, non-empty set of vertices (singular vertex) and E is a set of edges (links between pairs of vertices).  When the edges in a graph have no direction, the graph is called undirected, otherwise called directed.

    Cycle:A cycle is a path consisting of at least three vertices that starts and ends with same vertex. Two vertices are said to be connected if there is a path between them.
    • A directed graph is strongly connected if there is a path from each vertex to every other vertex in the graph.
    • A directed graph is weakly connected if at least two vertices are not connected.
    • Adjacency list: An adjacency list is the representation of all edges or arcs in a graph as a list.
    • Adjacency matrix: The adjacency matrix uses a vector (one-dimensional array) for the vertices and a matrix (two –dimensional array) to store the edges.
    • Depth First Traversal: In the depth first traversal. We process all of the vertex’s descendants before we move to an adjacent vertex. It uses stack to store the nodes.
    • Breadth – First Traversal: In the breadth – first traversal of a graph, we process all adjacent vertices of a vertex before going to the next level. The breadth – first traversal uses a queue rather than a stack. As we process each vertex, we place all of its adjacent vertices in the queue.

    • Spanning trees: A spanning tree of a graph is an undirected tree consisting of only those edges necessary to connect all the nodes in the original graph.
    • Network: A network is a graph that has weights or costs associated with its edges. It is also called weighted graph.
    • Minimum Spanning Tree: This is a spanning tree that covers all vertices of a network such that the sum of costs of its edges is minimum. There are two algorithms which are:
               1)      Kruskals algorithm     2) Prims algorithm

    • Forest: An undirected graph which contains no cycles is called a forest.  A directed acyclic graph is often referred to as dag.
    • Complete graph: A graph is said to be complete if there is an edge between every pair of vertices.
    • Bipartite graph: A graph is said to be bipartite if the vertices can be split into sets V1 and V2. Such there are no edges between two vertices of V1 or vertices of V2.

    • Uniformed search: A problem consists of four parts: the initial state, a set of operators, a goal test function, a path cost function. A path through the state space from the initial state to a goal state is a solution.
    Search algorithms are judged on the basis of completeness, optimally, time complexity and space complexity.
    • Completeness:It is the strategy guaranteed to find a solution when there in one.
    • Time complexity: It is the how long does it take to find a solution.
    • Space complexity: It is the how much memory needs to perform the search.
    • Optimality: Does the strategy find the highest quality solution when there are several different solutions.
    Breadth first search: Expands the shallowest node in the search tree first. It is complete optimal for unit-cost operations, and has time and space complexity of O(b^d). The space complexity makes it impractical in most cases. Using BFS Strategy, the root node is expanded first, then all the nodes generated by the root node are expanded next, and their successors and so on.

    Uniform cost search: Expands the least – cost leaf nod first. It is complete, and unlike breadth-first search is optimal even when operators have differing costs. It’s space and time complexity are the same as BFS.

    Depth- First search: Expands the deepest node in the search tree first. It is neither complete nor optimal, and has time complexity of O(b^m) and space complexity of O(bm), where m is the maximum depth. In search trees of large of finite depth, the time complexity makes this impractical.

    Depth-Limited search: Places a limit on how deep a depth-first search can go. If the limit happens to be equal to the depth of shallowest goal state, then the time and space complexity are minimized.

    Iterative deepening search: Calls depth – limited search with increasing limits until a goal is found. It is completed and optimal, and has time complexity of O(b^d).

    Bidirectional search: Can enormously reduce time complexity, but is not always applicable. Its memory requirements may be impractical. BDS simultaneously search both forward form the initial state and backward from the goal and stop when the two search meet in the middle.


    You Might also view the following Related Posts

    For more other Posts: Click Here

         

    Thursday, November 8, 2012

    Definition of Tree


    A tree is a combination of a finite set of elements, called nodes and a finite set of directed lines, called branches that connect the nodes.

    The number of branches associated with a node is the degree of the node. When the branch is directed towards the node, it is an indegree branch. When the branch is directed away from the node, it is an out degree branch, the sum of outdegree and indegree branches equal to the degree of the node.

    Some important terms:

    Definition of Tree
      Definition of Tree
    • Root node: If the tree is non empty, then the first node is called as root. The indegree of root by definition is zero.
    • Leaf node: A node with no successors (nodes after it). There will usually be many leaves in a tree.
    • Non Leaf node: A node which has both a parent and at least one child.
    • Internal nodes: Nodes that are not root and not leaf are called as internal nodes
    • Parent node: A node is a parent if it has successor nodes; means out degree greater than zero.
    • Child node: A node is child node if indegree is one.
    • Siblings: Two or more nodes with same parent are siblings.
    • Ancestor node: An ancestor is any node in the path from the root to the node.
    • Descendant node: A descendent is any node on the path below the parent node.
    • Subtree: A subtree is any connected structure below the root.
    • Directed tree: A directed tree is an acyclic digraph, which has only one node with indegree 0, and others nodes have indegree 1.
    • Binary tree: A binary tree is a tree in which no node can have more than two subtrees. In other word it is a directed tree in which outdegree of each node is less than or equal to two. (i.e. zero, one or two). An empty tree is also a binary tree.
    • Strictly binary tree: If the outdegree of every node in a tree is either 0 or 2, then the tree is said to be strictly binary tree. i.e. each node can have maximum two children or empty left and empty right child.
    • Complete binary tree: A strictly binary tree in which the number of nodes at any level i is 2 i-1 then the tree is said to be complete binary tree.
    • Almost binary tree: A tree of depth d is an almost complete binary tree, if the tree is complete up to the level d-1.
    • Tree traversals: Tree traversal is the technique in which each node in the tree is processed or visited exactly once systematically one after the other. The different tree traversal techniques are Inorder, Preorder and Postorder.Algorithm for tree traversal
         i) Inorder (Left-Root-Right)
    • Traverse the left sub tree in inorder [L]
    • Process the root node [N]
    •  Traverse the right sub tree in inorder [R]
         ii) Preorder (Root-Left-Right)
    • Process the root node [N]
    • Traverse the left sub tree in preorder [L]
    • Traverse the right sub tree in Preorder [R]
         iii) Postorder (Left-Right-Root)
    • Traverse the left subtree in post order. [L]
    • Traverse the Right sub tree in postorder [R]
    • Process the root node [N]
    Binary Search tree: A binary search tree is a binary tree in which for each node say x in the tree elements in the left subtree are less than info(x) and elements in the left subtree are greater or equal to info(x).

    The operations performed on binary search tree are:

    •  Insertion: An item is inserted
    •  Searching: Search for a specific item in the tree.
    •  Deletion: Deleting a node from a given tree.

      Balanced Search trees: Balanced search tree is on that exhibits a good ratio of breadth to depth. There are special classes of Balanced Search Trees that are self-balancing. That is as new nodes are added or existing nodes are deleted, these Balanced search Trees automatically adjust their topology to maintain an optimal balance. With an ideal balance, the running time for inserts, searches, and deletes even in the worst case is log2n.
      AVL trees, Red-Black trees, Lemma are the examples of balanced search trees.


      AVL Trees: An AVL tree is a binary search tree whose left subtree and right subtree differ in height by at most 1 unit, and whose left and right trees are also AVL trees.
      To maintain balance in a height balanced binary tree, each node will have to keep an additional piece of information that is needed to efficiently maintain balance in the tree after every insert and delete operation has been performed. For an AVL tree, this additional piece of information is called the balance factor and it indicates if the difference in height between the left and right subtrees is the same or, if not, which of the two subtrees has height one unit larger. If a node has a balance factor rh(right high). It indicates that the height of the left subtree. Similarly the balance factor for a node could be lh(left height) or eh(equal height).



      Binary Heap tree: A binary heap is a complete binary tree. A tree that is completely filled except possibly at the bottom level, which is filled from left to right with no missing nodes.
           

      Wednesday, November 7, 2012

      Definition of List and Linked List

      Definition of List and Linked List

      List is a generic term for a collection of objects. It may or may not contain duplicates and application may or may not require that it be kept in specified order.

      The functions defined to operate on a list are


      ·         Insert:  Insert a new entry into a list
      ·         Delete: Delete an entry from list
      ·         Length: Compute length of a list
      ·         Next: Return the next element in a list
      ·         Search: Search if an element is in a list

      Linear list: A linear list is a sequence of n>=0 nodes x[1], x[2], x[3] ……………x[n] whose essential structural properties between items as they appear in a line.

      Restricted list: In restricted list, Data can only be added or deleted at the ends of a structure and processing is restricted to operations at the end of lists.

      The two restricted list structures are First In First Out (FIFO) stacks and Last In First Out (LIFO) queue.

      The four operations performed on linear lists are


               i.            Insertion
             ii.            Deletion
            iii.            Retrieval
           iv.            Traversal


               Depending on the type of linear list, an insertion can be made at the beginning of the list, or at the end of the lists. When inserting data into ordered list, the data must be inserted so that the ordering is maintained. Deletion from general lists requires that the list be searched for the data to be deleted.



      List retrieval requires that data be located in a list and presented to the calling module without changing the contents of the lists.


      List traversal is a special case of retrieval in which all the elements are retrieved in a sequence.

      Definition of Linked list


      A link list is a collection of records, called nodes, each containing at least one field(member) that gives the location of the next node contains two members; a data member (the value of the list item) and a link member (a value locating the next node).The link list is a very flexible dynamic data structure. It is a low-level structure upon which high-level data structures can be built.

      The Typical basic linked-list operations are


               i.            Create: Makes a new linked list
             ii.            Insert: Puts a new node in its place in the list.
            iii.            Remove: Remove a node from the list.
           iv.            Traverse: This function allow user to visit each node in the list.
             v.            Is empty: The function returns a true/false indication of whether or not there are any nodes in the list.
           vi.            Is full: This function returns a true/false indication of whether or not the list is full

      Types of linked lists


               i.            Singly linked lists
             ii.            Circular singly linked lists
            iii.            Doubly linked lists
           iv.            Circular Doubly linked lists


      You Might also view the following Related Posts

      For more other Posts: Click Here