Questions and Answers of Data Structures And Algorithms In C++

Implement Kruskal’s algorithm assuming that the edge weights are integers.
Implement the Prim-Jarn´ık algorithm assuming that the edge weights are integers.
Show how to modify the pseudo-code for Dijkstra’s algorithm for the case when the graph may contain parallel edges and self-loops.
Show that if all the weights in a connected weighted graph G are distinct, then there is exactly one minimum spanning tree for G.
Draw a simple, connected, undirected, weighted graph with 8 vertices and 16 edges, each with unique edge weights. Illustrate the execution of Kruskal’s algorithm on this graph.
Describe the meaning of the graphical conventions used in Figure 13.6 illustrating a DFS traversal. What do the colors blue and black refer to? What do the arrows signify? How about thick lines and
Repeat the previous problem for the Prim-Jarn´ık algorithm.Draw a simple, connected, undirected, weighted graph with 8 vertices and 16 edges, each with unique edge weights. Illustrate the execution
Given a complete binary tree T with n nodes, consider a directed graph G having the nodes of T as its vertices. For each parent-child pair in T, create a directed edge in G from the parent to the
Recalling the definition of a complete graph from Exercise R-13.31, what does a breadth-first search tree of a complete graph look like?Data from in Exercise R-13.31A simple undirected graph is
If we implemented the stack S from the previous problem with an array, as described in this chapter, then what is the current value of the top member variable?
Implement a templated C++ class Vector that manipulates a numeric vector. Your class should be templated with any numerical scalar type T, which supports the operations + (addition), −
Show that n is O(nlog n).
Show that n2 is Ω(nlog n).
Show that n log n is Ω(n).
Explain how you can implement all the functions of the deque ADT using two stacks.
Give an implementation of the deque ADT using an array, so that each of the update functions run in O(1) time.
Describe how to implement a capacity-limited stack, which uses the functions of a capacity-limited deque to perform the functions of the stack ADT in ways that do not throw exceptions when we attempt
Describe how to implement a capacity-limited queue, which uses the functions of a capacity-limited deque to perform the functions of the queue ADT in ways that do not throw exceptions when we attempt
Implement the stack ADT in a fully generic manner (through the use of templates) by means of a singly linked list. (Give your implementation “from scratch,” without the use of any classes from
Suppose an initially empty stack S has performed a total of 25 push operations, 12 top operations, and 10 pop operations, 3 of which generated a StackEmpty exception that was caught and ignored. What
Implement the stack ADT in a fully generic manner using the STL vector class.
Describe how to implement the stack ADT using two queues. What is the running time of the push and pop functions in this case?
Implement the queue ADT in a fully generic manner using a dynamically allocated C++ array.
Describe the output of the following series of stack operations: push(5), push(3), pop(), push(2), push(8), pop(), pop(), push(9), push(1), pop(), push(7), push(6), pop(), pop(), push(4), pop(),
Suppose we have an n×n two-dimensional array A that we want to use to store integers, but we don’t want to spend the O(n2) work to initialize it to all 0’s, because we already know that we are
Implement the queue ADT with a singly linked list.
Implement the deque ADT with an array used in a circular fashion.
Implement the deque ADT with a doubly linked list.
Implement the Stack and Queue interfaces with a unique class that is derived from class LinkedDeque (Code Fragment 5.21).Data from in Code Fragment 5.21The class structure for class LinkedDeque.We
Describe the output for the following sequence of queue operations: enqueue(5), enqueue(3), dequeue(), enqueue(2), enqueue(8), dequeue(), dequeue(), enqueue(9), enqueue(1), dequeue(),
Describe the output for the following sequence of deque operations:insertFront(3), insertBack(8), insertBack(9), insertFront(5), removeFront(), eraseBack(), first(), insertBack(7), removeFront(),
Implement a program that can input an expression in postfix notation (see Exercise C-5.8) and output its value.Data from in Exercise C-5.8Postfix notation is an unambiguous way of writing an
Which of the following is not a valid C++ variable name? (There may be more than one.)a. I think i am validb. I may have 2 many digits 2 be validc. I start and end with underscoresd. I Have A Dollar
A common punishment for school children is to write out the same sentence multiple times. Write a C++ stand-alone program that will write out the following sentence one hundred times: “I will
Write a short C++ function that takes an array of int values and determines if there is a pair of numbers in the array whose product is even.
Write a C++ program that, when given a starting day (Sunday through Saturday) as a string, and a four-digit year, prints a calendar for that year. Each month should contain the name of the month,
Write a pseudo-code description of a method for finding the smallest and largest numbers in an array of integers and compare that to a C++ function that would do the same thing.
Write a C++ function that takes an STL vector of int values and determines if all the numbers are different from each other (that is, they are distinct).
Give a C++ definition of a struct called Pair that consists of two members. The first is an integer called first, and the second is a double called second.
Write a C++ function that takes an STL vector of int values and prints all the odd values in the vector.
What are the contents of string s after executing the following statements.string s = "abc";string t = "cde";s += s + t[1] + s;
Write a C++ function that takes an array containing the set of all integers in the range 1 to 52 and shuffles it into random order. Use the built-in function rand, which returns a pseudo-random
Consider the expression y + 2 * z ++ < 3 - w / 5. Add parentheses to show the precise order of evaluation given the C++ rules for operator precedence.
Write a short C++ program that outputs all possible strings formed by using each of the characters ’a’, ’b’, ’c’, ’d’, ’e’, and ’f’ exactly once.
Consider the following attempt to allocate a 10-element array of pointers to doubles and initialize the associated double values to 0.0. Rewrite the following (incorrect) code to do this
Write a short C++ program that takes all the lines input to standard input and writes them to standard output in reverse order. That is, each line is output in the correct order, but the ordering of
Write a short C++ function that takes an integer n and returns the sum of all the integers smaller than n.
Write a short C++ program that takes two arguments of type STL vector< double>, a and b, and returns the element-by-element product of a and b. That is, it returns a vector c of the same length
Write a short C++ function, is Multiple, that takes two positive long values, n and m, and returns true if and only if n is a multiple of m, that is, n = mi for some integer i.
Write a C++ class Vector2, that stores the (x,y) coordinates of a two dimensional vector, where x and y are of type double. Show how to override various C++ operators in order to implement the
Write a C++ function print Array(A, m, n) that prints an m × n two dimensional array A of integers, declared to be “int** A,” to the standard output. Each of the m rows should appear on a
Write an efficient C++ function that takes any integer value i and returns 2i, as a long value. Your function should not multiply 2 by itself i times; there are much faster ways of computing 2i.
The greatest common divisor, or GCD, of two positive integers n and m is the largest number j, such that n and m are both multiples of j. Euclid proposed a simple algorithm for computing GCD(n,m),
What (if anything) is different about the behavior of the following two functions f and g that increment a variable and print its value?void f(int x){ std::cout << ++x; } void g(int&
Write a C++ class, Flower, that has three member variables of type string, int, and float, which respectively represent the name of the flower, its number of pedals, and price. Your class must
Modify the CreditCard class from Code Fragment 1.3 to check that the price argument passed to function charge It and the payment argument passed to function make Payment are positive.Data from in
Modify the CreditCard class from Code Fragment 1.2 to charge interest on each payment.Data from in Fragment 1.2A typical C++ program includes many different header files, which often include other
Modify the CreditCard class from Code Fragment 1.2 to charge a late fee for any payment that is past its due date.Data from in Fragment 1.2A typical C++ program includes many different header files,
Modify the CreditCard class from Code Fragment 1.2 to include modifier functions that allow a user to modify internal variables in a CreditCard class in a controlled manner.Data from in Fragment 1.2A
Modify the declaration of the first for loop in the Test class in Code Fragment 1.4 so that its charges will eventually cause exactly one of the three credit cards to go over its credit limit. Which
Write a C++ class, All Kinds, that has three member variables of type int, long, and float, respectively. Each class must include a constructor function that initializes each variable to a nonzero
Write a short C++ function, is Multiple, that takes two long values, n and m, and returns true if and only if n is a multiple of m, that is, n = m· i for some integer i.
Write a short C++ function, is Two Power, that takes an int i and returns true if and only if i is a power of 2. Do not use multiplication or division, however.
Write a short C++ function that takes an integer n and returns the sum of all the integers smaller than n.
Write a short C++ function that takes an integer n and returns the sum of all the odd integers smaller than n.
Write a short C++ function that takes a positive double value x and returns the number of times we can divide x by 2 before we get a number less than 2.
Give an example of a C++ program that outputs its source code when it is run. Such a program is called a quine.
Write a C++ program that can take a positive integer greater than 2 as input and write out the number of times one must repeatedly divide this number by 2 before getting a value less than 2.
Suppose you are on the design team for a new e-book reader. What are the primary classes and functions that the C++ software for your reader will need? You should include an inheritance diagram for
Write a C++ program that “makes change.” Your program should input two numbers, one that is a monetary amount charged and the other that is a monetary amount given. It should return the number of
Give three examples of life-critical software applications.
Most modern C++ compilers have optimizers that can detect simple cases when it is logically impossible for certain statements in a program to ever be executed. In such cases, the compiler warns the
Design a class Line that implements a line, which is represented by the formula y = ax+b. Your class should store a and b as double member variables. Write a member function intersect(ℓ) that
Describe a component from a text-editor GUI (other than an “edit” menu) and the member functions that it encapsulates.
Write a C++ class that is derived from the Progression class to produce a progression where each value is the absolute value of the difference between the previous two values. You should include a
Write a C++ program that has a Polygon interface that has abstract functions, area(), and perimeter(). Implement classes for Triangle, Quadrilateral, Pentagon, Hexagon, and Octagon, which implement
Draw a class inheritance diagram for the following set of classes.• Class Goat extends Object and adds a member variable tail and functions milk and jump.• Class Pig extends Object and adds a
Write a C++ class that is derived from the Progression class to produce a progression where each value is the square root of the previous value.You should include a default constructor that starts
Write a C++ program that inputs a document and then outputs a bar-chart plot of the frequencies of each alphabet character that appears in that document.
A derived class’s constructor explicitly invokes its base class’s constructor, but a derived class’s destructor cannot invoke its base class’s destructor. Why does this apparent asymmetry
Write a C++ program that inputs a list of words separated by whitespace, and outputs how many times each word appears in the list. You need not worry about efficiency at this point, however, as this
Write a set of C++ classes that can simulate an Internet application, where one party, Alice, is periodically creating a set of packets that she wants to send to Bob. The Internet process is
Write a C++ program that can input any polynomial in standard algebraic notation and outputs the first derivative of that polynomial.
Consider the inheritance of classes from Exercise R-2.6, and let d be an object variable of type Horse. If d refers to an actual object of type Equestrian, can it be cast to the class Racer? Why or
Consider the following code fragment:class Object{ public: virtual void printMe() = 0; };class Place : public Object{ public: virtual void printMe() { cout << "Buy it.\n"; } };class Region :
Generalize the Person-Student class hierarchy to include classes Faculty, Under graduate Student, Graduate Student, Professor, Instructor. Explain the inheritance structure of these classes, and
Give an example of a C++ code fragment that performs an array reference that is possibly out of bounds, and if it is out of bounds, the program catches that exception and prints an appropriate error
Write a short C++ function that counts the number of vowels in a given character string.
Write a short C++ function that removes all the punctuation from a string s storing a sentence. For example, this operation would transform the string "Let’s try, Mike." to "Lets try Mike".
Write a short C++ program that creates a Pair class that can store two objects declared as generic types. Demonstrate this program by creating and printing Pair objects that contain five different
In the Tic-Tac-Toe example, we used 1 for player X and −1 for player O. Explain how to modify the program’s counting trick to decide the winner if we had used 1 for player X and 4 for player O
Write a C++ function that takes two three-dimensional integer arrays and adds them component wise.
Modify the implementation of class Scores so that at most ⌈maxEnt/2⌉ of the scores can come from any one single player.
Give C++ code for performing add(e) and remove(i) functions for game entries stored in an array a, as in class Scores in Section 3.1.1, except this time, don’t maintain the game entries in order.
Suppose that two entries of an array A are equal to each other. After running the insertion-sort algorithm of Code Fragment 3.7, will they appear in the same relative order in the final sorted order
Write a C++ program for a matrix class that can add and multiply arbitrary two-dimensional arrays of integers. Do this by overloading the addition (“+”) and multiplication (“*”) operators.
Give a C++ code fragment that, given a n×n matrix M of type float, replaces M with its transpose. Try to do this without the use of a temporary matrix.
Perform the previous project but use a linked list that is both circularly linked and doubly linked.
Add a function size() to our C++ implementation of a singly link list. Can you design this function so that it runs in O(1) time?
Write a program that can perform encryption and decryption using an arbitrary substitution cipher. In this case, the encryption array is a random shuffling of the letters in the alphabet. Your

Showing 200 - 300 of 332