Education Computer Science, Data Structure, Exam Past Questions and Answers BRUCASBLOG 2024-05-15 1 Comments

DATA STRUCTURE – 2022/2023 PGD PAST QUESTION & ANSWER

This Article shows the Past question and Answer workings for the Post Graduate Diploma program of Federal Polytechnic Bauchi in Affiliation with Joseph Sarwvan Tarka University, Markurdi.

This Past Question is for the year 2022/2023 Academic Session, and it’s helpful for those currently writing their on going exams in the department of Mathematics, Statistics and Computer Science.

N.B – These questions and answers are uploaded only as a guide and ease for your studies.

Below are the Questions:

Joseph Sarwvan Tarka University, Makurdi

College of Science

Department of Mathematics, Statistics, and Computer science

First Semester 2022 /2023 Examination

COURSE: CMP 741 |Data Structure]

INSTRUCTION: Answer any FIVE questions

1. What is data structure?

b. Give the criteria for the selection of a particular data model

c. List and briefly explain any five (5) operations that can be performed on a data structure

d. With examples for each, explain the types of data structure

2. Define STACK

b. What are the operations associated with a STACK

c. Write an algorithm for the two operations associated with STACK.

d. List any three (3) applications of STACK.

3. Explain the term ‘notation in data structure.

b. With example(s) for each, briefly explain the basic notation types you know.

c. Convert the infix expression K+L-M*N+(0^P)*W/U/V*T+ Q to prefix using stack

4. Given N elements in an array A, sorted in non decreasing order, Write an algorithm to

Determine whether a given element X is present in the list. If X exists, determine a value such that A=X. If X is not in the list then is to be set to zero.

b. Define the following terms in relation to directed graph

i) Sink ii) Source iii) Path iv) Weighted graph

a. What do you understand by linear array’?

Declare six (6) elements linear array in the following programming languages

i) PHP ii) Pascal iii) C++ iv) Java

Consider the array POLY that records the number of students admitted by FPTB from 1932 to 1984. Write an algorithm that determines the number of times through which more than 300 students were admitted. Also, write an algorithm that print each year with the number of students admitted that year from 1932-1984

6. What is Hashing?

b. Explain the two key features used in hashing

c. Highlight any three solutions to collision occurrence in hashing

d. Differentiate between static and dynamic hashing

7. What is algorithm?

b. List any four (4) characteristics of algorithm

c. List and briefly explain the five areas involved in the study of algorithm

Goodluck!

Study Questions & Answers on Survey of Programming Languages

below are the Answers:

1. Definition of Data Structure: Data Structure are the Programmatic way of storing data so that data can be used effectively.

b. Criteria for the selection of a particular data model.

(i) Rich in structure to show the relationship between the model and the real world: A data model should indeed represent real-world entities and their relationships accurately.

(ii) Simplicity: While simplicity is an admirable goal, it is relative and should not come at the cost of the model’s expressiveness.

(iii) Flexibility: The data model should be adaptable to changing requirements and accommodate future modifications without requiring significant restructuring.

(iv) Query performance: Choose a data model that supports efficient querying and data retrieval, particularly for the types of queries most relevant to your application.

(v) Data consistency: Consider the level of data consistency required by your application and choose a data model that supports the necessary consistency guarantees.

(vi) Scalability: Ensure that the data model can scale as the data volume grows or the application expands.

(vii) Integration: Consider the compatibility of the data model with existing systems, tools, and frameworks in your technology stack.

c. Operations that can be performed on a data structure: (i) Traversing (ii) Insertion (iii) Searching (iv) Deletion (v) Sorting

(i) Traversing — visiting each element in a data structure in a specific order

(ii) Insertion — Adding a new element to the data structure

(iii) Searching — Finding a specific element within a data structure

(iv) Deletion — Removing an existing element from the data structure

(v) Sorting — Arrange the element of a data structure in a specific order

d. Explaining the types of data structure with examples each.

(i) Arrays — A collection of elements, each associated with a unique index or key

Example:-

Element : 35 33 42 10 14 19 27 44 26 31

Index : 0 1 2 3 4 5 6 7 8 9

(ii) Linked Lists — A link list is a sequence of data structure which are connected together via links

Example;

Head —-> Data Items, Next —> Data Items

(iii) Stack — A stack is a Linear data structure that follows the Last In First Out (LIFO) principles. e.g A stack containing [ 10, 20, 30, 40, 50 ] in ascending order.

(iv) Queue — A Queue is a linear data structure that follows the First In First Out (FIFO) principles. e.g [10, 20, 30, 40, 50]

2. Definition of a Stack: A stack is a Linear data structure that follows the Last In First Out (LIFO) principles.

b. Operations associated with a Stack

— Insertion Operations also know as a PUSH operation

— Removal Operation also known as POP operation

• PUSH – Pushing (storing) an element on the stack

• POP – Removing (Accessing) an element from the stack

(a) Algorithm: PUSH (STACK, TOP, MAXSTK, ITEM)

This procedure pushes an ITEM onto a stack.

1. (Stack already filled?’)

If TOP = MAXSTK, then, Print: OVERFLOW, and Return.

2. Set TOP = TOP + 1 [increases TOP by 1]

3. Set STACK [TOP]: ITEM. [Insert ITEM in new TOP position).

4. Return.

(b). Algorithm: POP (STACK, TOP, ITEM)

This procedure deletes the top element of STACK and assigns it to a variable ITEM

1. [Stack has an item to be removed?

If TOP = 0, then, Print: UNDERFLOW, and Return.

2. Set ITEM: – STACK [TOP]. [Assigns TOP element to ITEM]

3. Set TOP = TOP – 1. [Decrease TOP by 1].

4. Return.

d. Applications of Stack

(i) Expression evaluation and syntax parsing: Stacks are used to parse and evaluate arithmetic, logical, or other expressions, such as converting infix notation to postfix or prefix notations and evaluating postfix expressions.

(ii) Memory management: Stacks are crucial in memory management and function calls in programming languages. The call stack is used to keep track of function calls and local variables, allowing the program to return to the calling function after the called function completes execution.

(iii) Backtracking algorithms: In algorithms that require backtracking, such as graph traversal (depth-first search), tree traversal, or maze solving, stacks are used to keep track of the path taken, allowing the algorithm to backtrack when needed.

(iv) Undo operations: Stacks are used to implement undo operations in text editors, image editing software, and other applications where reverting to a previous state is required. Each state change is pushed onto the stack, and an undo operation pops the most recent change from the stack.

(v) Stack-based languages: Some programming languages, like Forth and PostScript, use stacks as their primary data structure to store and manipulate data, perform arithmetic operations, and manage control flow.

(vi) Parenthesis matching: Stacks can be used to check for balanced parentheses, brackets, or braces in expressions or code by pushing opening symbols and popping corresponding closing symbols.

3. Explain the term notation in Data Structure

Notation is simply a way to write arithmetic expression. In data structures and algorithms, “notation” typically refers to a way of representing the efficiency or performance of an algorithm in terms of the time it takes to run and the space (memory) it requires.

b. Basic Notation Types

• Infix Notation — In infix Notation, operators are used in between operand e.g a – b + c

• Prefix Notation — In this notation, operator is prefixed to operands i.e operators is written ahead of operands. Example; + ab , which is equivalent to it’s Infix Notation a+b

• Postfix Notation — This notation style is known as reversed polish notation. In this notation style the operator is post fixed to the operands. The operator is written after the operands. Example; ab+ . This is equivalent to it’s Infix Notation a+b

c. Convert the infix expression K+L-M*N+(0^P)*W/U/V*T+ Q to prefix using stack.

L. H. S

K + L = + KL connecting it to – M it becomes; + KL – M

Connecting (+ KL – M) to * N it becomes; + N – M + KL

Again, connecting (+ N – M + KL) to + (O ^ P). Where (O ^ P) = ^ OP. It becomes; + KL – M + N ^ OP

R. H. S

W / U = /WU connecting it to /V it becomes; /WU/V

Connecting (/WU/V) to *T + Q, where * T + Q = + TQ . It becomes; /WU/V *+ TQ

Joining the L.H.S and R.H.S together

The final prefix expression is: +KL – M * + N ^ OP * / WU / V * + TQ

4. The problem can be solved using a simple linear search algorithm since the array is not sorted. However, if the array is sorted in non-decreasing order, a more efficient approach is to use binary search. Here is a Python implementation of the algorithm using binary search:

def find_x(array, x):

low = 0

high = len(array) – 1

index = -1

while low <= high:

mid = (low + high) // 2

# Find the middle index

if array[mid] == x:

index = mid

break

elif array[mid] < x:

low = mid + 1

else:

high = mid – 1

if index != -1:

# Found X in…

b. Defining the following terms:

(i) Sink — A sink in a directed graph is a vertex or node that has no outgoing edges and only incoming edges.

(ii) Source — A source in a directed graph is a vertex or node that has no incoming edges and only outgoing edges.

(iii) Path — A path in a directed graph is a sequence of verticles (nodes) and edges where the direction of each edge in the sequence align with the order of the verticles.

(iv) Weighted Graph — A weighted graph is a graph in which each edge has an associated value, called a weight. The weight of an edge can represent different things, such as distance, cost, or capacity, depending on the context of the problem.

5. Definition of A Linear Array: A linear array also known as a dimensional array is a container which can hold a fixed number of items and this items should be of the same type.

6. Definition of Hashing: Hashing is a technique used to convert a range of indexes of an array.

b. Key features used in Hashing

(i) Hash Function: A hash function is a mathematical function that maps data of any size to a fixed-size value, typically an integer. The main purpose of a hash function is to distribute data uniformly across an array or table, minimizing collisions and maintaining constant time complexity for search, insert, and delete operations.

(ii) Collision Resolution: Collisions occur when two or more different inputs hash to the same index in the array or table. Collision resolution is a strategy to handle such situations, ensuring that elements can still be stored and accessed efficiently.

c. Highlight any three solutions to collision occurrence in hashing

Collision resolution is a critical aspect of hashing, as collisions can negatively impact the performance of hash tables.

Here are three common solutions to address collisions:

Chaining: Chaining is a method that uses a linked list (or another data structure) to store multiple elements that hash to the same index. When a collision occurs, the new element is added to the linked list at that index, allowing multiple elements to be stored in the same index.

Open Addressing: Open addressing is another approach to resolving collisions in a hash table. When a collision occurs, the algorithm searches for the next available “free” slot in the table to store the element.

Robin Hood Hashing: This method uses open addressing, but when a collision occurs, the algorithm checks the distance each involved element has traveled from its original hash position. The element with the longest distance is placed closer to its original position, while the other element is moved further away. This technique helps prevent clustering and maintains more uniform distribution of elements in the hash table.

d. Differentiating between static and dynamic hashing

Static Hashing: In static hashing, the size of the hash table remains constant throughout the program execution. When a hash table is initialized, a fixed number of buckets or slots are allocated based on the expected number of elements to be stored. While,

Dynamic Hashing: Dynamic hashing, also known as extendible hashing or dynamic hash tables, allows the size of the hash table to grow or shrink as needed, depending on the number of elements being stored. When the load factor (the ratio of elements to table size) exceeds a certain threshold, the table size is increased to maintain efficient performance.

7. Definition of Algorithm: Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in

a certain order to get the desired output. Algorithms are generally created independent of

underlying languages, ie. an algorithm can be implemented in more than one programming

languages

b. Characteristics of an Algorithm

• Unambiguous – Algorithm should be clear and unambiguous. Each of its steps (or phases), and their inputs/outputs should be clear and must lead to only one meaning.

• Input – An algorithm should have O or more well-defined inputs.

• Output – An algorithm should have 1 or more well-defined outputs, and should match the desired output.

• Finiteness – Algorithms must terminate after a finite number of steps.

• Feasibility – Should be feasible wvith the available resources.

• Independent – An algorithm should have step-bystep directions, which should be independent of any programming code

c. List and briefly the five areas involved in the study of algorithm

Design and Analysis of Algorithms: This area focuses on creating efficient algorithms for solving computational problems, as well as analyzing their performance and resource requirements, such as time and space complexity.

Data Structures: Algorithms often rely on efficient data structures, such as arrays, linked lists, trees, graphs, stacks, and queues, to organize and manage data.

Computational Complexity Theory: This field deals with classifying problems based on their inherent difficulty and the resources required to solve them.

Graph Theory: Graphs are versatile mathematical structures used to model complex relationships between objects.

Combinatorial Optimization: This area focuses on finding optimal solutions to problems with discrete variables and constraints, such as scheduling, routing, and resource allocation.