Question

In: Computer Science

Related with the below statements, write the missing words: A variation of linked list, named as...

Related with the below statements, write the missing words:

  1. A variation of linked list, named as Doubly Linked List contains a link element called _______,_______.
  2. The heap sort has an average-case complexity of _________.
  3. The algorithms like merge sort, quick sort and binary search are based on __________ and _____________ algorithm.
  4. In stack terminology, the insertion operation is defined to be ___________.
  5. The asymptotic notation O(1) defines the complexity of type ___________.
  6. Looking for the next cell in the array, until an empty cell is found is known to be ___________.(To handle collision)
  7. A data structure named stack is an __________.
  8. Binary search has a worst-case complexity of __________.

Related with the below statements, write the missing words:

  1. A variation of linked list, named as Doubly Linked List contains a link element called _______,_______.
  2. The heap sort has an average-case complexity of _________.
  3. The algorithms like merge sort, quick sort and binary search are based on __________ and _____________ algorithm.
  4. In stack terminology, the insertion operation is defined to be ___________.
  5. The asymptotic notation O(1) defines the complexity of type ___________.
  6. Looking for the next cell in the array, until an empty cell is found is known to be ___________.(To handle collision)
  7. A data structure named stack is an __________.
  8. Binary search has a worst-case complexity of __________.

Solutions

Expert Solution

Solution:

(a)

The answer will be "first and last".

Explanation:

=>In the doubly linked list every node contains three things that are data value, previous pointer and next pointer.

=>Doubly linked list contains a link element that is the first and last element.

(b)

The answer will be "(nlog(n))"

Explanation:

=>The worst case time complexity of heap sort = O(nlog(n))

=>The best case time complexity of heap sort = (nlog(n))

=>The average case time complexity of heap sort = (nlog(n))

(c)

The answer will be "Devide and Conquer"

Explanation:

=>Merge sort, quick sort and binary search devide the array or partition the array for sorting and searching in case of binary search.

=>Devide and conquer algorithm devides the problem into subproblem and then finding the solution of small problems then merging(conquering) the solution of small problems to find the overall solution.

(d)

The answer will be "PUSH"

Explanation:

=>In stack insertion is called PUSH.

=>In stack deletion is called POP.

(e)

The answer will be "Constant time"

Explanation:

=>O(1) means the problem can be solved in finite number of steps hence O(1) means constant time.

(f)

The answer will be "Collision resolution techniques/linear probing"

Explanation:

=>Finding the location to insert in the hash table by resolving collisions. This techique is called collision resolution techniques.

(g)

The answer will be "LIFO/FILO"

Explanation:

=>Stack is last in first out(LIFO) or first in last out(FILO) data structure.

(h)

The answer will be "O(logn)"

Explanation:

=>Worst case time complexity of binary search = O(logn)

=>Best case time complexity of binary search = (1)

=>Average case time complexity of binary search = (logn)

I have explained each and every part with the help of statements attached to it.


Related Solutions

Write a subroutine named swap in C thatswaps two nodes in a linked list. The first...
Write a subroutine named swap in C thatswaps two nodes in a linked list. The first node should not be able to change places. The nodes are given by: Struct nodeEl { int el; struct nodeEl * next; }; typdef struct nodeEl node; The list header (of type node *) is the first parameter of the subroutine. The second and third parameters consist of integers and are the places in the list where the nodes are to change places. The...
You are to write one essay (750 words) based on the article linked below that has...
You are to write one essay (750 words) based on the article linked below that has been previously chosen from ChemMatters. You may consult more advanced academic references such as reputable research journals to ensure that the information provided has scientific merit. Please be clear and concise in your writing and make sure you condense the important points of the topic in the 750 words allocated.Your essay has to deal with the topic of "going green", how plastics, commonly used...
Fill in these missing words in the following statements. Some possible words are given as follows....
Fill in these missing words in the following statements. Some possible words are given as follows. reject, Type I error, p-value, parameter, null hypothesis, Type II error, test statistic (a) A statistical hypothesis is a hypothesis concerning a of a population or distribution. (b) If a test is devised to detect a change in some standard or prevailing value for the parameter in question, then the hypothesis of no change is generally labeled the hypothesis. (c) The error of rejecting...
The financial statements for Linked Ltd. are shown below:
The financial statements for Linked Ltd. are shown below: During the year, the company purchased a capital asset valued at $30,000; payment was made by issuing common shares. Additional capital assets were acquired for cash. Changes in other accounts were typical transactions. Required:1. Prepare the SCF using the indirect method. Include required note disclosure of non-cash transactions. Omit the separate disclosure of cash flow for interest, investment income, and income tax.2. Explain the company’s cash transactions for the year, based...
TITLE Updating Accounts Using Doubly Linked List TOPICS Doubly Linked List DESCRIPTION General Write a program...
TITLE Updating Accounts Using Doubly Linked List TOPICS Doubly Linked List DESCRIPTION General Write a program that will update bank accounts stored in a master file using updates from a transaction file. The program will maintain accounts using a doubly linked list. The input data will consist of two text files: a master file and a transaction file. See data in Test section below.  The master file will contain only the current account data. For each account, it will contain account...
You are given an ANOVA table below with some missing entries. Source Variation Sum of Squares...
You are given an ANOVA table below with some missing entries. Source Variation Sum of Squares Degrees of Freedom Mean Square F Between Treatments 3 1198.8 Between Blocks 5040 6 840 Error 5994 18 Total 27 ​ a. State the null and alternative hypotheses. b. Compute the sum of squares due to treatments. c. Compute the mean square due to error. d. Compute the total sum of squares. e. Compute the test statistic F. f. Test the null hypothesis stated...
(a) Write a stack class that is based on a linked list. It can be just...
(a) Write a stack class that is based on a linked list. It can be just pop(), push(), and anything you need for those methods or testing. (b) Write a queue class that is based on a linked list. As above, it can be just enqueue() and dequeue(), as well as anything you need for those methods or testing. (c) Write some test cases, trying to include edge cases. Why did you choose those tests? Did you get the results...
Write the following algorithms for a Doubly Linked List Inserting an item                              
Write the following algorithms for a Doubly Linked List Inserting an item                                                                                                                              [7] Deleting an item                                                                                                                               [7] Question two Take a queue containing numbers 10, 15, 5, 25, 30 in which 30 has been inserted first. After performing the following operations, what would be the contents of the queue? Delete two elements                                                                                                                      [2] Insert 7 and then 20                                                                                                                        [2] Delete an element                                                                                                                          [2]
3.1 Write code that creates an ArrayList object named list and fills list with these numbers...
3.1 Write code that creates an ArrayList object named list and fills list with these numbers (using one or a pair of for or while loops): 0 1 2 3 4 0 1 2 3 4 3.2 Consider the ArrayList object named list containing these Integers: list = { 1, 2, 3, 4, 5, 4, 3, 2, 1, 0 } What are the contents of list after this loop completes? for (int i = 1; i < 10; ++i) {...
C++, Write a routine that would receive a pointer to the top of the linked list...
C++, Write a routine that would receive a pointer to the top of the linked list that has an integer for each node. Count all positive even integers in the linked list but make negatives into positives. Return the count negatives that became positives. Hint, use Node<ItemType>* to define pointers and use pointers to go through the linked list.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT