Questions and Answers of Data Structures and Other Objects Using Java

Consider an implementation of unsorted circular linked list. Suppose it has its representation with a head pointer only. Given the representation, which of the following operation can be implemented
In singly linear linked list each node contains how many minimum fields?A. Five B. Zero C. Two D. Four
A non-circular doubly linked list can be defined as a……A. Set of nodes, each with two pointers previous and nextB. Set of nodes chained together with pointers C. Linear sequence of nodes in
Which of the below operations is a dictionary operation?A. Search an element B. Delete an element C. Insert an element D. All of these
What is known as a linear collection of data items, where the each node is given by means of a pointer to the next node?A. Linked list B. Node list C. Primitive list D. None of these
In singly linear linked list, each node contains minimum of two fields. One field is the data field to store the data second field. What is it called as?A. Pointer to character array B. Pointer to
Which of the following type of the linked list can be used so that concatenation of two lists can give the time complexity as O (1)?A. Singly linked list B. Doubly linked list C. Doubly circular
The linked lists are not appropriate for implementing?A. Insertion sort B. Radix sort C. Polynomial manipulation D. Binary search
In the worst case, the number of comparisons needs to search a node in a singly linked list of length n is having time complexity.A. log n B. n C. log2n-1 D. n/2
Which of the following C language code is used to create a new node in the singly linear linked list.A. ptr = (LIST*) malloc(sizeof(LIST));B. *ptr = (LIST*) malloc(LIST);C. ptr = (LIST*)
What is the return type of the malloc () function?A. void B. int *C. foat *D. void *
LLINK is the pointer toward the.…A. successor node B. predecessor node C. head node D. last node
Each node of a singly linear linked list must contain at least..…A. Three fields B. Two fields C. Six fields D. Five fields
Linked list data structures are most appropriate A. For comparatively constant collections of data B. For the size of the structure and the data within the structure are continuously changing.C.
Inserting an element at the start of an array is more difficult than inserting an element at the start of a linked list.A. TRUE B. FALSE
The disadvantage in using a circular linked list is …………………….A. It is possible to enter into an infinite loop B. Last node stores the address of first node in circular linked
Which of the following statement is true?a. Using singly linear linked lists and singly circular linked list, it is not possible to traverse the linked list in reverse order.b. To find the
Which of the following singly linear linked list representation using C language is correct? A. struct node { }; B. struct node { }; C. }; int data; struct node *next; struct node { D. int data;
Which of the following statements is false or true?1. In doubly linear linked list contains two link fields one is storing the address of next node and the other stores the address of the previous
Which of the following statements is false or true?1. malloc() function having return type as void * which is generic pointer.2. malloc () function requires only one argument which is size in
Which of the following statements is false or true?1. With linked list, insertion and deletions can be efficiently carried out.2. Once elements are stored sequentially, it becomes very difficult to
Which of the following statements is false or true?A. Statement 1 is false and Statement 2 is trueB. Statement 2 is false and Statement 1 is trueC. Statements 1 and 2 are falseD. Statements 1 and 2
Rewrite the depthFirstPrint method from Figure 14.4 so that it carries out a breadth-first search instead. FIGURE 14.4 Depth-First Search Implementations public static void depthFirstRecurse (Graph
Use edge lists to reimplement the Graph class from Figure 14.3 on page 744. There should be no limit to the number of vertices. Also provide a new method that returns the edge list of a specified
Use edge sets to reimplement the Graph class from Figure 14.3 on page 744. There should be no limit to the number of vertices. Also provide a new method that returns the edge set of a specified
Implement a new class that is derived from the Graph. The new class should permit both edges and vertices to have labels.
Implement a method with three arguments: a graph, a starting vertex number, and an ending vertex number. The method determines whether there is a directed path from the starting vertex to the ending
Implement a new class for graphs with weighted edges. Use the ordinary Graph class as a superclass for your implementation. After implementing the new class, provide two extra methods to implement
Write a program to help a traveler plan the shortest traveling path from one city to another. The program should read a file of data containing a list of cities and a list of roads connecting the
Write a program to help you make better social connections. The program should read a file of data containing a list of people in your community and a list of who knows whom. Allow the user to enter
Choose some graph implementation and implement a graph member function to delete a vertex from the graph. The function should remove not only the vertex, but also all edges that have the vertex as
Implement an undirected graph class by modifying any of the graph implementations discussed in this chapter.
Rewrite the maze program in Chapter 8 using a graph class to represent the maze. A path should be generated with the entrance and exit as endpoints. Use a depth-first search to travel through the
A connected graph is a graph that has a path from every node to every other node. For this project, you are given a connected, undirected, weighted graph in which every edge has a non-negative number
Write an interactive program to help you count all of the boxes in a room. The program should begin by asking something like How many unnumbered boxes can you see? Then the program will have you
Tic-Tac-Twice is a game invented by Pat Baggett and Andrzej Ehrenfeucht. It is distributed by the Aristoplay company. The rules simple, starting with two 4x4 boards that each have a pattern of 16
Write an extended class that has all the operations of the Bag class from Figure 5.2. Use Java’s Vector as the superclass. FIGURE 5.2 Specification and Implementation for the ArrayBag Generic Class
Extend the Organism object hierarchy from Section 13.3 so that there is a new class Carnivore as described in Self-Test Exercise 13 on page 710. Use the hierarchy in a model of life on a small island
Rewrite the pond life program from Figure 13.10 so that the output is presented as a graph in an applet window. The applet can use most of the same graphing techniques as the fractal applet from page
Rewrite the pond life program from Figure 13.10 so that the values declared at the start of the program are no longer constant. The program’s user should be able to enter values for all of these
A set is like a bag, except that a set does not allow multiple copies of any element. If you try to insert a new copy of an item that is already present in a set, then the set simply remains
Reimplement the concurrent Sorter class from Section 12.5 using a quicksort to control the recursion (rather than a mergesort).
In 1959, the American computer scientist Donald Shell invented a technique that can be used to speed up many different sorting algorithm. For this project, you will apply Shell’smethod to
Work out an algorithm that uses a radix sort to sort strings of characters.
The performance of the radix sort from the previous project can be improved by using more supplementary lists (rather than just list0 and list1).For example, you can have an array of 16 lists, which
A radix sort is a technique for sorting nonnegative integers (or other data that has individual characters or digits).One version of radix sort works with a linked list of integers. In addition to
Choose one of the recursive sorting algorithms and vary the point where you cut off the recursion. Below this size, the array is sorted by a quadratic algorithm.For each different recursion
Rewrite the quicksort partition function so that the pivot is chosen by selecting the median of three random values from the array. Narerxaty, write a version using five random values. This may
On problem with mergesort is that it constantly needs a new temporary array. One solution to the problem is to rewrite the mergesort according to the following specification: void mergesort( int
The discussion shows our algorithm for building the initial heap in the heapsort algorithm. The algorithm is reasonably efficient, but we can make it even more efficient. The more efficient algorithm
Rewrite quicksort so that there are no recursive calls. The technique is to use a stack to keep track of which portions of the array still need to be sorted. Whenever we identify a portion of the
One of the advantages of mergesort is that it can easily be adapted to sort a linked list of values. This is because the algorithm retrieves the values from the two lists being merged in the order
Redo the insertionsort algorithm so that the values are inserted into a linked list rather than an array. This eliminates the need to move other values when a new value is inserted because your
If you are familiar with Java’s Comparable interface (Programming Project 11), then rewrite one of the sorting methods so that it sorts an array of Comparable objects. You may choose selectionsort,
Implement the NewTable class from Section 11.5.A New Table ClassWe have implemented hash tables with an array of records (for open-address hashing) and an array of linked lists (for chained hashing).
Implement a dictionary program using a hash table. The user inputs a word, and then the word’s definition is displayed. You’ll need to use Java’s hash table class with a string as both the key
Redesign the interface for a hash table to allow the data to be null and to allow multiple elements with the same key. You’ll have to give some thought to the return value for the get function in
Rewrite one of your hash tables so that it has additional methods to provide statistics. You should include methods to calculate the load factor, the average number of items examined during a
In our open-address hash tables, we have used linear probing or double hashing. Another probing method, which avoids some clustering, is called quadratic probing. The simplest version of quadratic
Use double hashing to reimplement the hash table from Figure 11.5. FIGURE 11.5 Implementation of the Table Class Implementation // FILE: Table.java from the package edu.colorado.collections //
For this project, you must first implement the Polynomial class from the Chapter 3 Programming Project 8 on page 170. Add a new method to the class with four parameters: a polynomial f and three
Use a binary search technique to write a game program that asks the user to think of an integer in a particular range and then tries to guess the number. The program may ask questions such as “Is
Reimplement the binary search using a loop and no recursion. If you are familiar with Java’s Comparable interface, then your implementation search an array of Comparable objects rather than an
Using the heap implementation of a priority queue from Project 1, implement a program that keeps track of the user’s list of prioritized chores.Data from Project 1Using a heap, implement the
The heap in this chapter is referred to as a maxheap because the highest priority value is also the maximum value. Implement the heap as a minheap, in which the entry of the node with the highest
Use the DefaultMutableTreeNode to implement the B-tree set class from Section 10.2.
Use the DefaultMutableTreeNode to reimplement one of these Chapter 9 projects:a. Expression trees (9.1)b. Bag of strings (9.10)
Use the material from Section 10.3 to reimplement the animal-guessing program from Figure 9.8 as a JApplet. You’ll need to research additional details of the Java classes. FIGURE 9.8 The
The java.lang.Math class provides a static method log(x), which returns the logarithm of x with a base that is approximately 2.718282..7This base is written e, and the logarithms with this base are
Use a B-tree to implement the Set class from Figure 10.4. Be sure to write and test small pieces. FIGURE 10.4 The Set of Integers Class IntBalancedSet * public class IntBalancedSet from the package
Using a heap, implement the priority queue ADT from Section 7.4. You can store the heap in arrays, similar to the solution to Self-Test Exercise 1. To have FIFO behavior for elements with equal
Expand the class from Project 10 or 11 so that there is an extra method that produces a Java Iterator for the bag.Data from Project 10Write a class for a bag of strings, where the strings are stored
Java has a generic interface called Comparable. A class that implements the Comparable interface must have a method with this specification:♦ compareTopublic boolean compareTo(E obj)Compare this
Write a class for a bag of strings, where the strings are stored in a binary search tree. In creating the binary search tree, you should use the string’s compareTo method, which is described on
An internal iterator for a bag is a collection of methods that allows a programmer to step through the elements of a bag one at a time.For example, we might have an internal iterator consisting of
Binary search trees have their best performance when they are balanced, which means that at each node n, the size of the left subtree of n is within one of the size of the right subtree of n. Write a
Implement a new method for the BTNode from Figure 9.10. The new method creates a Java Vector that contains the data from all the nodes in a tree, as specified in Figure 9.15. Details about the Java
This project requires that you know how to determine the actual time taken for a method to execute. Write a test program for the bag class from Section 9.5. The program should allow the user to
Revise the animal-guessing program from Figure 9.8 so that the initial knowledge tree is obtained by reading information from a file. Also, when the program ends, the knowledge tree at that point is
Specify, design, and implement a class for binary trees where the node’s elements are stored in an array, similar to the way that a complete binary tree is usually stored. However, these binary
Specify, design, and implement a class for complete binary trees using the array representation from Section 9.2. You should have only one method that adds a new node (since there is only one place
This project deals with a simple kind of expression tree, in which there are two kinds of nodes:(a) Leaf nodes, which contain a real number as their element;(b) Non-leaf nodes, which contain either
Ackermann’s function, named after the German mathematician Wilhelm Ackermann, is used in the theory of recursive functions. There are several variants of this function. Their common properties are
Write a recursive method to convert a character string of digits to an integer. Example: convert("1234") returns 1234.
Rewrite the recursive pow method from Figure 8.11 so that the time to compute pow(x, n) is log(n). FIGURE 8.11 Altemative Implementation of a Method to Compute Powers Implementation public
Rewrite the basic calculator program from Figure 6.5 so that the method evaluate uses recursion instead of stacks. FIGURE 6.5 A Method to Evaluate a Fully Parenthesized Arithmetic Expression Method
Write a Java method with the following header:public static void numbers(String prefix, int n)The number k is non-negative. The argument called prefix is a String of 0s and 1s. The method prints a
Write a Java method with the following header:public static void binaryPrint(int n)The number n is non-negative. The method prints the value of n as a binary number. If n is zero, then a single zero
Write a Java method that meets the following specification:public static void digits(int c)// Precondition: c is one of the ints 0 to 9.// Postcondition: The method has printed a// pattern of digits
A pretty print program takes a program that may not be indented in any particular way and produces a copy with the same program indented so that bracket pairs ({ and }) line up with inner pairs
Let’s think about your computer science class for a moment. You might know several students, perhaps Judy, Jervis, Walter, and Michael. Each of those students knows several other students, and each
For this project, you are to write a recursive method that prints all of the objects in a bag. Use the bag specification from Figure 4.12, which is a bag of integers. The integers are to be printed
This project uses the Towers class from Chapter 3’s Programming Project 12. For the project, write a recursive methodxtxhxat computes and prints a solution to the Towers of Hanoi game. The method
Write a program that asks the user to think of an integer between 1 and 1,000,000, and then guesses the number through a series of yes/no questions. To guess the number, the program calls a recursive
Examine this pattern of asterisks and blanks, and write a recursive method that can generate exactly this pattern:With recursive thinking, the method needs only seven or eight lines of code
Write a recursive method to produce a pattern of n lines of asterisks. The first line contains one asterisk, the next line contains two, and so on, up to the nth line, which contains n asterisks.
Write a recursive method that has as arguments an array of characters and two bounds on array indexes. The method should reverse the order of those entries in the array whose indexes are between the
The formula for computing the number of ways of choosing r different things from a set of n things is the following:In this formula, the factorial function is represented by an exclamation point (!)
Write a recursive method called sumover that has one argument n, which is a nonnegative integer. The method returns a double value, which is the sum of the reciprocals of the first n positive
Write a recursive method that has two parameters, first and second, that are both strings. The method should print all rearrangements of the letters in first followed by second. For example, if first

Showing 300 - 400 of 507