<http://cnfolio.com/ISADReview3>
Systems analysis

Algorithms analysis



ARRAYS


  1.   In Java, 'C' or Pascal, write a complete program to perform the following tasks:   [14 Marks]
    1.   To declare a real (floating-point) array which stores ten numbers.
    2.   To enter ten values from the keyboard into the array of elements.
    3.   To write a method (function or subroutine) called from the main program which selects and displays the largest array value.
  2.   Construct a simple effects table ('dry run'), showing how the program variables change, with the ten values:   [3 Marks]
    •   63,   21,   -9,   64,   206,   184,   -300,   128,   206,   -80
  3.   Explain how you would modify your selection method to detect and display duplicate maximum values as in the test data above.   [3 Marks]


LINKED LISTS


Linked list data structures can be used to create variable length records on disc.
  1.   With the aid of a diagram, explain the terms:   [11 Marks]
    1.   Linked list.
    2.   Control (or header) record.
    3.   Pointers.
    4.   Freespace (or garbage) blocks.
  2.   Using further diagrams (or flowcharts if you prefer), explain how:   [9 Marks]
    1.   A variable length record is extended by one block.
    2.   A record is deleted.



A linked list data structure may be used to implement variable length records on disc storage.
  1.   With the aid of a diagram, explain how linked list records may be organised in a disc file. If possible, explain the terms block, pointer, header and freespace.   [10 Marks]
  2.   Suggest a suitable application for linked lists.   [2 Marks]
  3.   Suggest TWO advantages of using linked lists.   [4 Marks]
  4.   Distinguish between singly linked lists and doubly linked lists.   [4 Marks]



The linked list data is a powerful data structure with a wide range of applications.
  1.   With the aid of a diagram, explain what is meant by a linked list data structure.   [4 Marks]
  2.   Describe briefly the benefits of using linked lists.   [4 Marks]
  3.   Distinguish between singly linked lists and doubly linked lists.   [4 Marks]
  4.   Describe how a stack could be implemented on a disc storage using a linked list structure. Explain the purpose of any header block, pointers, and freespace (garbage).   [8 Marks]



  1.   What is meant by a linked list structure?   [4 Marks]
  2.   Explain how linked lists can be used to support variable length records.   [4 Marks]
  3.   By means of a flowchart show how a block can be transferred from the freespace chain to a variable length file record (the getblock logic).   [10 Marks]
  4.   Suggest, with a reason, a suitable application for linked lists.   [2 Marks]


QUEUES


The queue is an important data structure. Queues are sometimes implemented using a circular store, as in the case of entering characters from a keyboard.
  1.   With the aid of a diagram, explain the meaning of a Queue.   [4 Marks]
  2.   Describe briefly how a queue may be implemented using a circular store.   [4 Marks]
  3.   Using flowcharts, or otherwise, describe the procedure when:   [10 Marks]
    1.   an item is added to the queue.
    2.   an item is removed from the queue.
  4.   Explain one method for distinguishing between an empty queue and a full queue when using a circular store.   [2 Marks]



  1.   Using a diagram, define the data structure known as a Queue; explain how a queue may be implemented with a one-dimensional array.   [6 Marks]
  2.   Construct flowcharts (or pseudocode) to show how an item of data is:
    1.   added to a queue.   [4 Marks]
    2.   removed from a queue; (when an item is removed, assume that any remaining items advance one place so that the head of the queue stays in a fixed position in the array).   [7 Marks]
  3.   Describe briefly TWO applications for queue storage.   [3 Marks]



  1.   With a diagram define the data structure known as a Queue, showing how it may be implemented using a simple linear array.   [6 Marks]
  2.   Construct flowcharts to show how an item is: (in each case, identify any error situations.)   [8 Marks]
    1.   Added to a queue.
    2.   Removed from a queue.
  3.   Suggest a disadvantage of using the simple linear array.   [2 Marks]
  4.   Describe briefly ONE alternative method of queue storage management.   [4 Marks]


STACKS


The Stack is an important data structure.
  1.   Explain the term Stack and describe its principle of operation. Using a diagram, explain how a stack may be implemented in a high level programming language.   [8 Marks]
  2.   Name TWO processes applicable to stacks. Describe the logic of these processes using flowcharts or pseudocode.   [6 Marks]
  3.   Explain the terms Stack Overflow and Stack Underflow; suggest how each can arise and describe the likely consequences.   [4 Marks]
  4.   Describe briefly TWO uses of stacks.   [2 Marks]



  1.   With the aid of a diagram, define the data structure known as the Stack.   [4 Marks]
  2.   With the help of a flowchart or pseudocode, explain the PUSH and POP operations.   [6 Marks]
  3.   In a high level language such as Java, Pascal or 'C', implement a stack; your program should include PUSH and POP methods (or functions), and, should input three items of data (X, then Y, then Z) to the stack; finally, the program should recover the data from the stack and display the output.   [10 Marks]



Stacks are widely used in computer systems.
  1.   Explain the meaning of the term Stack.   [4 Marks]
  2.   By constructing flowcharts, show how a data item is: (in each case, identify any error conditions which can arise).   [8 Marks]
    1.   added to the stack.
    2.   removed from the stack.
  3.   Describe an application which requires a stack and explain how the stack would be used.   [5 Marks]
  4.   The job scheduler (part of an operating system) selects one task at a time for execution. Discuss the suitability of a stack for storing tasks awaiting processing.   [3 Marks]


TREES


  1.   With the aid of a diagram, define the data structure known as a Tree, and distinguish between a binary tree and a general (multiway) tree.   [8 marks]
  2.   With the aid of a flowchart, or otherwise, describe the search process for a binary tree.   [8 marks]
  3.   Suggest TWO differences between the tree search and the binary search (binary chop).   [4 marks]



  1.   With the aid of a diagram, define the data structure known as a Tree, and distinguish between a binary tree and a general (simple) tree.   [8 marks]
  2.   With the aid of a flowchart, or otherwise, describe the search process for a binary tree.   [8 marks]
  3.   Compare, under TWO headings, the tree search and the binary search (binary chop).   [4 marks]



Tree structures are very useful for storing data and for retrieving records quickly.
  1.   With the aid of a diagram, explain carefully the meaning of an Ordered Binary Tree.   [7 Marks]
  2.   Using a flowchart, or pseudocode, show the logic of a tree search process (starting from the entry of the search key).   [9 Marks]
  3.   Compare the tree search and the binary search ('binary chop') in terms of:   [4 Marks]
    1.   their search time for a given dataset size;
    2.   their use in on-line applications.



The tree below contains records about individuals (Mike, Helen, Sue, ...):
Tree
  1.   Describe in detail, by flowchart or or pseudocode, a process for traversing the records in alphabetical order (Alan, Helen, Leo, ... Sue, Tom).   [8 Marks]
  2.   Construct an effects table ('dry run') to show the steps as your process traverses the tree.   [4 Marks]
  3.   State the conditions necessary for the correct operation of the process.   [4 Marks]
  4.   Name and briefly describe TWO other methods of traversing the tree.   [4 Marks]



  1.   Define the term Binary Tree.   [6 Marks]
  2.   One method of traversing a binary tree is known as lnorder. Name, and describe briefly, the other TWO methods.   [4 Marks]
  3.   Describe in detail a procedure for the inorder traversal of a binary tree; (you may use a flowchart, pseudocode or a program). Apply the procedure to the binary tree below, showing the exact traversal sequence.   [10 Marks]
Binary tree



Tree structures are often used in file directory and database systems.
  1.   With the aid of a diagram, define the term Tree (include in the definition: node, predecessor, descendant, root and leaf).   [7 Marks]
  2.   State the conditions necessary for a tree to be a Binary Tree.   [3 Marks]
  3.   With the aid of a flowchart, or otherwise, describe the Tree Search procedure for an ordered binary tree.   [8 Marks]
  4.   Explain why binary trees are often less useful than other types of tree when searching.   [2 Marks]


SORTING AND SEARCHING


  1.   Distinguish between Sorting and Merging.   [5 Marks]
  2.   Describe in detail how a large data file of some 256,000 records, could be sorted (preferably using a two-way merge process).   [9 Marks]
  3.   Explain how the sort time (T) would vary according to the number of records (N) to be sorted. If the time to sort 256,000 records is 90 minutes, estimate the sort times for:   [6 Marks]
    1.   N = 64,000 records.
    2.   N = 1,000,000 records.



Sorting processes, whether internal or external, can be very time-consuming.
  1.   Suggest TWO reasons for sorting records.   [4 Marks]
  2.   Distinguish between an lntemal Sort and an Extemal Sort.   [3 Marks]
  3.   Explain briefly why, if there is a choice, an intemal sort would normally be preferable to an external sort.   [2 Marks]
  4.   A data file having 256,000 records, and 128 Mbytes in volume, needs to be sorted on a single name field. Describe in detail a suitable sort process.   [8 Marks]
  5.   Discuss whether the benefits of sorted data sets can be obtained without the need for a lengthy sorting process.   [3 Marks]



Some internal sorting methods, such as Shell or Quicksort, are usually much faster than Selection or Exchange methods.
  1.   Explain the term Internal Sort.   [2 Marks]
  2.   With the aid of a dry run (effects table), describe EITHER Shell sort OR Quicksort on the following numbers:   [12 Marks]
      9   14   16   18   2   7   3   5  

  3.   Suggest how the sorting time depends on the number of items (N) to be sorted. Explain why Shell or Quicksort are quicker than Selection or Exchange sorts.   [6 Marks]



The time to sort N items using an internal sort depends, for a given computer, on the value of N and on the sort algorithm. Using the numeric list shown, with N=8 :

  10   3   6   11   5   12   9   8  

  •   Define the term Internal Sort.   [2 Marks]
  •   With a flowchart, or otherwise, describe a simple internal sort procedure; name the procedure chosen.   [6 Marks]
  •   By means of a dry run (effects table), show in detail the action of your procedure on the list above; identify as accurately as possible the main processes which contribute to the overall sort time.   [8 Marks]
  •   Discuss how the sort time would vary as N increased.   [4 Marks]



  • The merge, search, sort and critical path network analysis are well-known processes. The time to complete each process in the computer depends partly on the number of data items (N) in the data structure.
    1.   Describe briefly a method (algorithm) for THREE of the following:   [14 Marks]
      1.   a two-way merge of N records.
      2.   a search for a key field in a database of N records.
      3.   a sort of a file containing N records.
      4.   a project analysis where there are N activities.
    2.   If the process time was 10 seconds for each of the above methods when N = 1000, estimate the process times for your three chosen algorithms when:   [6 Marks]
      1.   N = 32000 (three estimates).
      2.   N = 1000000 (three estimates).



    Internal sorting methods vary in efficiency. Partition methods, such as Shell or Quicksort, are far superior both to exchange methods such as 'bubblesort' and to insertion methods.
    1.   Explain the term Internal Sort.   [2 Marks]
    2.   With the aid of a simple effects table ('dry run') show how the set of numbers below would be sorted using:
      1.   A simple exchange sort (or an insertion sort).   [6 Marks]
      2.   A partition sort.   [8 Marks]
          38   31   18   50   12   10   44   16  

    3.   Give reasons why partition sorts are more efficient than exchange and insertion sorting methods.   [4 Marks]



    There are many methods of sorting data; the time taken to complete a sort process depends on several factors.
    1.   Distinguish between an lntemal Sort and an Extemal Sort.   [3 Marks]
    2.   Explain how a large data file having some 512,000 records could be sorted, preferably using a merge process.   [7 Marks]
    3.   Discuss FIVE factors which influence the time required to sort a set of N records (where 'N' is the number of records to be sorted).   [10 Marks]