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.
0 Comments
Post a Comment