CS301 Midterm Solved Short Notes  cs301 midterm exams preparation 2022| cs301 midterm exams

Definition

·        Deferent B/W Merge sort and Linked Lists?

·        Define merge Arrays?

·        What is Bubble Sort?

·        Insertion Sort?

·        Hashing is Suitable?

·        Applications of Hashing?

·        Linear Probing and Collision?

 

 

·        What are the constraints?

Constraint defines a limitation or restriction on resources of a system. In the computer, we have hard disk, memory and other hardware. We also have time to consider as a resource. Suppose you are writing an algorithm to solve a given problem and you have disc space of 400 Mega bytes. So, here you have space constraint that your algorithm should use only the available space in an efficient way. A solution is considered to be an efficient solution if it solves the problem within its resource constraints.

 

·         What is lvalue?

In an assignment statement, lvalue refers to some memory location where some value can be stored. Lvalue variable is written on left hand side of an assignment statement. For example, in the following statement, variable ‘var’ is lvalue variable and value 7 will be stored in it. int var= 7;

 

·        What is “current” pointer ?

“Current” is a variable showing the status of currently focused element in array/list, for example if current = 5, it means that currently the focus is on element no. 5 in the array/list.

 

What is algorithm?

Algorithm is a finite sequence of steps for the solution of a problem.

 

 WHAT IS ROLE OF ARRAYS IN DATA STRUCTURE?

Array is the most widely used data structure. It is also used as constituting integral part of other data structures. Array is mainly used to store similar data. For storing elements of indexed data, the particular method is array. For example, if you were storing information about each day in August, you would create an array with an index capable of addressing 31 values -- one for each day of the month. Think of a notebook with pages numbered 1 through

12. Each page may or may not contain information on it. The notebook is an array of pages. Each page is an element of the array 'notebook'. Arrays can also be multidimensional – instead of accessing an element of a one-dimensional list, elements are accessed by two or more indices, as from a matrix or tensor. Arrays guarantee constant time read and write access,O(1) , however many lookup operations (find_min, find_max, find_index) of an instance of an element are linear time, O(n). Arrays are very efficient in most languages, as operations compute the address of an element via a simple formula based on the base address element of the array.

 

·        HOW MANY TYPES AN DATA CAN BE ORGANIZE?

Data can be organized in two main ways

1- Linear as in arrays, lists

2-Non Linear or Hierarchical like Trees

 

 

 

·        Data structures importance/applications in Daily life :

 

In bank service rows of men follow the Queue data structure.

In online shopping, selection and cancelation in the list of items is done/maintained via data structures. For representing a city region telephone network. Used to store a set of fixed key words which are referenced very frequently. DS are used to represent an image in the form of a bitmap. To implement back functionality in the internet browser. To implement printer spooler so that jobs can be printed in the order of their arrival. To record the sequence of all the pages browsed in one session. To implement the undo function in a text editor. To store information about the directories and

files in a system .

 

·        What is chunk?

Chunk means "a piece of reasonable size". Computer memory is divide into small parts. Combination (allocation in sum) of these parts constitutes and can be called as chunk.

 

What is Basic purpose of data structure?

The main purpose of data structure is to organize and store the Data in Computer, in order to make the use of data efficient. Use of data efficiently means to use less space by the data and operations like searching, deletion, insertion etc on data took less time.

 

 What are argc and argv ?

The variables argc and argv in the definition of main function, that is, main( int argc, char**argv) are called command line arguments.

 

What is the difference between the Data structure and Algorithms?

Data Structure is the organization of Data in computer in an efficient way, while Algorithm is a finite sequence of steps for the solution of a problem.

Example, Consider there are a number of students whose marks are needed to be store in the computer, now we can stored them in computer in an efficient way by using data structure like array, Linked List etc..

Consider we need to find the maximum marks obtained by a student in this

list, now for this we need to use an algorithm (Sequence of steps), for

example,

 

 What is efficiency?

A solution is said to be efficient if it solves the problem within its resource

constraints.

 Space

 Time

The cost of a solution is the amount of resources that the solution

consumes. What is x?

X is a name of collection of items. Its individual items are numbered from zero to one less

than array size. To access a cell, use the array name and an index as under:

x[0], x[1], x[2], x[3], x[4], x[5]

 

 What is Array Name?

-‘x’ is an array name but there is no variable x. ‘X’ is not an ‘l’ value.

For example, if we have the code Int a, b;

Then we can write b=2;

a=b; a=5;

But we cannot write 2=a;

List Data Structure:

 

 

What are lists?

A list is collection of items that are all of the same type (grocery items, integers, names)

Operation Name           Description

create List()                Create a new list (presumably empty)

copy()                          Set one list to be a copy of another

clear();                        Clear a list (remove all elements)

insert(X, ?)                        Insert element X at

a particular position in the list remove(?)         Remove element at some position in the list

get(?)                            Get element at a given position

update(X, ?)               Replace the element at a given position with X find(X)

Determine if the element X is in the list

length()                         Returns the length of the list.

If we use the “current” marker, the following four methods would be useful:

Functions Description

 

start() Moves the “current” pointer to the very first element

tail() Moves the “current” pointer to the very last element

next() Move the current position forward one element

back() Move the current position backward one element

 

 

What are dynamic arrays?

In computer science, a dynamic array, grow able array, resizable array, dynamic table, or array list is a data structure that can be resized and allows elements to be added or removed. It is supplied with standard libraries in many modern mainstream programming languages.

 

A dynamic array is not the same thing as a dynamically-allocated array, which is a fixed-size array whose size is fixed when the array is allocated.

 

 what is the majour difference between "Array" and "List"?

Array is a collection of memory cells of same type. In computer science, an array data structure or simply array is a data structure consisting of a collection of elements (values or variables), each identified by one or more integer indices, stored so that the address of each element can be computed from its index topple by a simple mathematical formula. For example, an array of 10 integer variables, with indices 0 through 9, may be stored as 10 words at memory addresses 2000, 2004, 2008, ... 2036; so that the element with index i has address 2000 + 4 × I In computer science, a linked list is a data structure that consists of a sequence of data records such that in each record there is a field that contains a reference (i.e., a link) to the next record in the sequence.

 

 what is the basic concept of Data Structures?

This is very important subject as the topics covered in it will be encountered by you again and again in the future courses. Due to its great applicability, this is usually called as the foundation course. You have already studied Introduction to programming using C and C++C and used some data structures. The focus of that course was on how to carry out programming with the use of C and C++ languages besides the resolution of different problems. In this course, we will continue problem solving and see that the organization of data in some cases is of immense importance. Therefore, the data will be stored in a special way so that the required result should be calculated as fast as possible

 

 what is list data structure ?

In computer science, a list or sequence is an abstract data structure that implements an ordered collection of values, where the same value may occur more than once. An instance of a list is a computer representation of the mathematical concept of a finite sequence, that is, a tuple. Each instance of a value in the list is usually called an item, entry, or element of the list; if the same value occurs multiple times, each occurrence is considered a distinct item.

 

 what parameters are considered to identify l value.?

If we can assign a value to a variable then we can the variable is lvalue type. Lets see with an examples

int x;

Here x is a integer type variable we can assign any integer value to x like x = 10 or x = 2

In the following code statement y is an array which can hold 10 values. int y[10]; In this scenario y is not lvalue, the reason is we cannot assign a single integer value to y like y = 10 Lets we elaborate it with diagram.Suppose the box given below is int variable x. we can easily assign (save) 10 or 2 to it.Assume 10 boxes given below are representing an array y. We cannot assign single value 10 or 2 to y. The problem is, if we will assign 10 to y then which box (place) in array it will save. This is the reason array is not lvalue.

 

 

Data structure concept in easy wording?

A data structure is a group of data elements grouped together under one name. Data structure helps to store the data in computer in an organized and efficient way. Data structures are used to efficiently utilize the memory of computer. Data structures not only consider the items stored but also the relationship to each other.

 

 What is Difference b/w arrays and linked list?

i. The difference between arrays and linked lists are:

ii. Arrays are linear data structures. Linked lists are linear and non-linear data structures.

iii. Linked lists are linear for accessing, and non-linear for storing in memory

iv. Array has homogenous values. And each element is independent of

each other positions.

v. Each node in the linked list is connected with its previous node

which is a pointer to the node.

vi. Array elements can be modified easily by identifying the index value. It

is a complex process for modifying the node in a linked list.

vii. Array elements cannot be added, deleted once it is declared. The nodes in

the linked list can be added and deleted from the list.

 

 What are Linked lists ?

Linked lists are a way to store data with structures so that the programmer can

automatically create a new place to store data whenever necessary. Specifically,

the programmer writes a struct definition that contains variables holding

information about something and that has a pointer to a struct of its same type (it

has to be a pointer--otherwise, every time an element was created, it would create a new element, infinitely). Each of these individual structs or classes in the list is

commonly known as a node or element of the list.

 

 Why we need array to implement this linked memory list?

Using linked memory method is the other way of implementing the list. We have

to implement a list of elements, so this implementation can be done in 2 ways.

First is array implementation in which the elements will be stored in contiguous

memory locations. There are certain limitations of this type of implementation of

list i.e. the size is fixed. So to avoid these limitations, we can implement list by

other method. That method is implementing via linked memory locations which do not restrict the list items to be stored contiguously.