Question

Q1

A- How linear search and binary search work? What is their time complexity?

B- What is a single linked list? What are the pros and cons of the linked list when comparing to parallel arrays?

Q2

A- What is a register? How registers work together with ALU and Control Unit to execute a program? What is the fetch-execute cycle?

B- What is the difference to implement a control unit using microprogrammed or hardwired approaches? What is clock cycle? What are different addressing modes?

Answer 1

Q1)

A)

Linear search and binary search:

The linear search is a searching algorithm that is used to search for an element in the given data structure.

The linear search checks each element and moves to the next element in a sequential manner.

The binary search is a searching algorithm that is used to search for an element in the given data structure.

For the binary search the list of elements must be in sorted order.

It begins the search with the middle of the sorted list.

It determines whether the search element is greater or less than the middle element.

This helps in finding whether the search element is present in the first half or the second half of the list.

This process repeats until the element is found.

These are the linear and binary search algorithms.

The time complexity of linear search is O(n) and the time complexity of binary search is O(log n)

Where n is the number of elements in the list.

B)

A single linked list is a variant of linked list that is unidirectional.

It can be traversed only in one direction.

The nodes in the single linked list have two fields in it.

The first field is the data field that has the value of the element in it.

The second field is the pointer to the next node.

Pros:

The linked lists are dynamic structures.

They can be used to dynamically allocate memory and store the data in it.

The memory need not be allocated in a contiguous manner.

The parallel arrays are fixed in size and it leads to memory waste.

The memory needs to be allocated in a contiguous blocks for parallel arrays.

Cons:

The linked list occupies extra memory for storing the pointer data that points to the next node.

In the linked list, the elements can not be accessed directly.

To access an element, the list has to be traversed from the first node till the node that needs to be accessed.

The parallel arrays do not need any additional memory for storing the pointer fields.

It is possible to access the required element directly using its index value in case of parallel arrays.

Note:

Please see that as per the guidelines, only single question can be answered when multiple questions are present.

In case of multiple choice type questions, upto 4 can be answered. Thank you.