CS301 Midterm Solved Short Notes  cs301 midterm exams preparation 2022| 


Difference between Programming and Data Structure?

Programming is very wide topic and covers lots of computer science concepts. In simple words programming is developing software to automate or solve a problem, with the help of different data structures and algorithms.  While data structure is a part of programming. Data structures are instructions to solve a problem by using

computer resources efficiently.

 

 What are LValues Variables?

Lvalue variables are those variables that can used on left side to save a value.

Variables are labels of memory locations that we want to use in our program. Assigning a value to variable is saving value on a memory location.

In following example int x = 10;

Here x is Lvalue and holding a value 10.

int y[10];

Here y is not Lvalue and we cannot write y = 20;

Because y is an array and can be used to hold 10 values. In above line out program will not know on which location it should save value 20.

 

 What is Index?

Index is location of element in an array. With the help of index we can reach to any element in the array. Here is example of using index

int grades[10]; // declaring an integer array to store 10 integer values

grades[4] = 3; // assigning integer 3 to 5th location of array. here 4 is index of element.

 

 

 What do u meant By Link Memory?

Average case: Normally we may have to move half of the elements.

 

 

 What is Add method and Current Pointer?

Add method is used to add an element in the list. A list can be implemented either by using an array or linked list. When we implement a list by using an array then it is called array list. When we will add an element at the start of an array list then we should have to move every element to the right to make space for the new element. When we will add the element at the end of an array list then we will not move or shift any other array element. Normally we may have to move half of the elements in average cases.Current marker or pointer refers to a particular position in the list where we are currently standing. If we do not use current pointer then we will not be able to keep track of our list i.e. we will be unable to identify our current position so it will become difficult for us to add or remove an element from list.

 

What do we meant by Link list inside a computer memory ?

It means how the memory will be allocated to the linked list and how memory is linked for your list elements.

 What is Node?

These are the elements that make it possible to have a linked list. Without them, there would be no listing.

Each node contains two parts; a part for the data and a part for the address of the next element. As you can see,

this will use pointers.

 

 

 What is state variables?

The products that are made by the factory have their own characteristics. For example, a car made by an automobile factory has an engine, wheels, steering and seats etc. These variables inside a class are called state variables.

getNext()

getNext() which returns a pointer to an object of type Node lying somewhere in the memory. It returns next Node i.e. a pointer to an object of type Node. NextNode contains the address of next node in the linked

list.

setNext()

setNext()

that accepts a pointer of type Node, further assigned to nextNode data member of the object. This method is used to connect the next node of the linked list with the current object. It is passed an address of the next node in the linked list.

 

 What are list interface, list implementation and analysis?

List interface means that how list works internally and how we interact with the list. If write the C++ program to implement the list then we simply need to know that what are those methods, their names and what arguments that method takes etc. Now we will see what the implementation of the list is and how one can create a list in C++. After designing the interface for the list, it is advisable to know how to implement that interface. Suppose we want to create a list of integers. For this purpose, the methods of the list can be implemented with the use of an array inside.For example, the list of integers (2, 6, 8, 7, 1) can be represented in the following manner where the current position is 3.

A 2 6 8 7 1 Current Size

1 2 3 4 5 3 5

 

In this case, we start the index of the array from 1 just for simplification against the usual practice in which the index of an array starts from zero in C++. It is not necessary to always start the indexing from zero.

Sometimes, it is required to start the indexing from 1. For this, we leave the zeroth position and start using the array from index 1 that is actually the second position. Suppose we have to store the numbers from 1 to 6 in the array. We take an array of 7 elements and put the numbers from the index 1. Thus there is a

correspondence between index and the numbers stored in it. This is not very useful. So, it does not justify the non-use of zeroth position of the array out-rightly. However for simplification purposes, it is good to use the index from 1.

 

 

 What is the main purpose of node?

For the utilization of the concept of linked memory, we usually define a structure, called linked list. To form a linked list, at first, we define a node. A node comprises two fields. i.e. the object field that holds the actual list element and the next that holds the starting location of the next node.

 

 

 What is the importance of link list in memory?

Linked lists are among the simplest and most common data structures, and are used to implement many important abstract data structures, such as stacks, queues, hash tables, symbolic expressions, skip lists, and many more.The principal benefit of a linked list over a conventional array is that the order of the linked items may be different from the order that the data items are stored in memory or on disk. For that reason, linked lists allow insertion and removal of nodes at any point in the list, with a constant number of operations

 

 what are the operations of the linked list?

The linked list data structure provides operations to work on the nodes inside the list.The first operation we are going to discuss here is to create a new node in the memory. The Add(9) is used to create a new node in the memory at the current position to hold ‘9’. You must remember while working with arrays, to add an element at the current position that all the elements after the current position were shifted to the right and then the element was added to the empty slot. Here, we are talking about the internal representation of the list using linked list. Its interface will remain the same as in case of arrays.

We can create a new node in the following manner in the add() operation of the linked list with code in C++:

Node * newNode = new Node(9);

The first part of the statement that is on the left of the assignment is declaring a variable pointer of type Node.

It may also be written as Node * newNode. On the right of this statement, the new operator is used to create a

new Node object as new Node(9). This is one way in C++ to create objects of classes. The name of the class is

provided with the new operator that causes the constructor of the class to be called. The constructor of a class

has the same name as the class and as this a function, parameters can also be passed to it. In this case, the

constructor of the Node class is called and ‘9’ is passed to it as an int parameter.

Hence, the whole statement means:

“Call the constructor of the Node class and pass it ‘9’ as a parameter. After constructing the object in memory,

give me the starting memory address of the object. That address will be stored in the pointer variable

newNode.”

Limitation of array and use of linked list

There are number of limitations of array data structure. Most common are as follows:-

1O.nce an array is created, its size cannot be altered

Array provides inadequate support for inserting and deleting operations.

A linked list is a popular data structure to store data in sequential order. Meanwhile, linked list structure allow

following operations which overcomes limitation of array: for example

1. Retrieve an element from list.

2. Insert a new element to the list.

3. Delete an element from the list.

4. Find how many elements are in the list.

5. Find a specific element is in the list.

6. Find if this list is empty.



part one