Questions and Answers of Practical Introduction To Data Structures

What is the result of running sfold from Section 9.4.1 on the following strings? Assume a hash table size of 101 slots.(a) HELLO WORLD(b) NOW HEAR THIS(c) HEAR THIS NOW
Using closed hashing, with double hashing to resolve collisions, insert the following keys into a hash table of thirteen slots (the slots are numbered 0 through 12). The hash functions to be used are
Write an algorithm for a deletion function for hash tables that replaces the record with a special value indicating a tombstone. Modify the functions hashInsert and hashSearch to work correctly with
Consider the following permutation for the numbers 1 to 6:2, 4, 6, 1, 3, 5.Analyze what will happen if this permutation is used by an implementation of pseudo-random probing on a hash table of size
Implement a binary search and the quadratic binary search of Section 9.1.Run your implementations over a large range of problem sizes, timing the results for each algorithm. Graph and compare these
Implement the three self-organizing list heuristics count, move-to-front, and transpose. Compare the cost for running the three heuristics on various input data. The cost metric should be the total
Implement a system for managing document retrieval. Your system should have the ability to insert (abstract references to) documents into the system, associate keywords with a given document, and to
Implement a database stored on disk using bucket hashing. Define records to be 128 bytes long with a 4-byte key and 120 bytes of data. The remaining 4 bytes are available for you to store necessary
Implement the dictionary ADT of Section 4.4 by means of a hash table with linear probing as the collision resolution policy. You might wish to begin with the code of Figure 9.7.Using empirical
Assume that a computer system has disk blocks of 1024 bytes, and that you are storing records that have 4-byte keys and 4-byte data fields. The records are sorted and packed sequentially into the
Assume that a computer system has disk blocks of 4096 bytes, and that you are storing records that have 4-byte keys and 64-byte data fields. The records are sorted and packed sequentially into the
Modify the function binary of Section 3.5 so as to support variable-length records with fixed-length keys indexed by a simple linear index as illustrated by Figure 10.1. Linear Index 37 42 52 73 73
Assume that a database stores records consisting of a 2-byte integer key and a variable-length data field consisting of a string. Show the linear index (as illustrated by Figure 10.1) for the
Each of the following series of records consists of a four-digit primary key (with no duplicates) and a four-character secondary key (with many duplicates).(a) Show the inverted list (as illustrated
Under what conditions will ISAM be more efficient than a B+-tree implementation?
Prove that the number of leaf nodes in a 2-3 tree with k levels is between 2k-1 and 3k-1.
Show the result of inserting the values 55 and 46 into the 2-3 tree of Figure 10.9. 10 12 15 18 33 20 21 23 30 24 Figure 10.9 A 2-3 tree. 31 48 45 47 50 52
You are given a series of records whose keys are letters. The records arrive in the following order: C, S, D, T, A, M, P, I, B, W, N, G, U, R, K, E, H, O, L, J. Show the 2-3 tree that results from
You are given a series of records whose keys are letters. The records are inserted in the following order: C, S, D, T, A, M, P, I, B, W, N, G, U, R, K, E, H, O, L, J. Show the tree that results from
Show the result of inserting the value 55 into the B-tree of Figure 10.16. 10 12 15 20 18 24 21 23 Figure 10.16 A B-tree of order four. 30 31 38 33 45 48 47 50 52 60
Show the result of inserting the values 1, 2, 3, 4, 5, and 6 (in that order) into the B+-tree of Figure 10.17. 101215 18 23 18 19 20 21 22 33 233031 33 45 47 48 48 50 52
Show the result of deleting the values 18, 19, and 20 (in that order) from the B+-tree of Figure 10.22b. 101215 18 18 19 20 21 22 23 (b) 23 30 31 33 45 47 48 50 52
You are given a series of records whose keys are letters. The records are inserted in the following order: C, S, D, T, A, M, P, I, B, W, N, G, U, R,K, E, H, O, L, J. Show the B+-tree of order four
Assume that you have a B+-tree whose internal nodes can store up to 100 children and whose leaf nodes can store up to 15 records. What are the minimum and maximum number of records that can be stored
Assume that you have a B+-tree whose internal nodes can store up to 50 children and whose leaf nodes can store up to 50 records. What are the minimum and maximum number of records that can be stored
Implement a two-level linear index for variable-length records as illustrated by Figures 10.1 and 10.2. Assume that disk blocks are 1024 bytes in length.Records in the database file should typically
Implement the 2-3+ tree, that is, a 2-3 tree where the internal nodes act only as placeholders. Your 2-3+ tree should implement the dictionary interface of Section 4.4. Dictionaries and Comparators
Implement the dictionary ADT of Section 4.4 for a large file stored on disk by means of the B+-tree of Section 10.5. Assume that disk blocks are 1024 bytes, and thus both leaf nodes and internal
Prove by induction that a graph with n vertices has at most n(n−1)/2 edges.
Prove the following implications regarding free trees.(a) If an undirected graph is connected and has no simple cycles, THEN the graph has |V| − 1 edges.(b) If an undirected graph has |V| − 1
(a) Draw the adjacency matrix representation for the graph of Figure 11.25.(b) Draw the adjacency list representation for the same graph.(c) If a pointer requires four bytes, a vertex label requires
Show the DFS tree for the graph of Figure 11.25 , starting at Vertex 1. 10 3 2 3 2 20 5 15 6 10 3 5 11
Wright a pseudocode algorithm to create a DFS tree for an undirected, connected graph starting at a specified vertex V.
Show the BFS tree for the graph of Figure 11.25, starting at Vertex 1. 10 3 2 3 2 20 5 15 6 10 3 5 11
Wright a pseudocode algorithm to create a BFS tree for an undirected, connected graph starting at a specified vertex V.
The BFS topological sort algorithm can report the existence of a cycle if one is encountered. Modify this algorithm to print the vertices possibly appearing in cycles (if there are any cycles).
Explain why, in the worst case, Dijkstra’s algorithm is (asymptotically) as efficient as any algorithm for finding the shortest path from some vertex I to another vertex J.
Show the shortest paths generated by running Dijkstra’s shortest-paths algorithm on the graph of Figure 11.25, beginning at Vertex 4. Show the D values as each vertex is processed, as in Figure
Modify the algorithm for single-source shortest paths to actually store and return the shortest paths rather than just compute the distances.
The root of a DAG is a vertex R such that every vertex of the DAG can be reached by a directed path from R. Write an algorithm that takes a directed graph as input and determines the root (if there
Write an algorithm to find the longest path in a DAG, where the length of the path is measured by the number of edges that it contains. What is the asymptotic complexity of your algorithm?
Write an algorithm to determine whether a directed graph of |V| vertices contains a cycle. Your algorithm should run in Θ(|V| + |E|) time.
Write an algorithm to determine whether an undirected graph of |V| vertices contains a cycle. Your algorithm should run in Θ(|V|) time.
The single-destination shortest-paths problem for a directed graph is to find the shortest path from every vertex to a specified vertex V. Write an algorithm to solve the single-destination
List the order in which the edges of the graph in Figure 11.25 are visited when running Prim’s MST algorithm starting at Vertex 3. Show the final MST. 10 3 2 3 2 20 5 15 6 10 3 5 11
List the order in which the edges of the graph in Figure 11.25 are visited when running Kruskal’s MST algorithm. Each time an edge is added to the MST, show the result on the equivalence array,
Write an algorithm to find a maximum cost spanning tree, that is, the spanning tree with highest possible cost.
When can Prim’s and Kruskal’s algorithms yield different MSTs?
Prove that, if the costs for the edges of Graph G are distinct, then only one MST exists for G.
Consider the collection of edges selected by Dijkstra’s algorithm as the shortest paths to the graph’s vertices from the start vertex. Do these edges form a spanning tree (not necessarily of
Prove that a tree is a bipartite graph.
Prove that any tree can be two-colored.
Write an algorithm that determines if an arbitrary undirected graph is a bipartite graph. If the graph is bipartite, then your algorithm should also identify the vertices as to which of the two
Design a format for storing graphs in files. Then implement two functions:one to read a graph from a file and the other to write a graph to a file. Test your functions by implementing a complete MST
An undirected graph need not explicitly store two separate directed edges to represent a single undirected edge. An alternative would be to store only a single undirected edge (I, J) to connect
While the underlying implementation (whether adjacency matrix or adjacency list) is hidden behind the graph ADT, these two implementations can have an impact on the efficiency of the resulting
The example implementations for DFS and BFS show calls to functions PreVisit and PostVisit. Better is to implement BFS and DFS using the visitor design pattern, with the visitor functions being
Write a program to label the connected components for an undirected graph.In other words, all vertices of the first component are given the first component’s label, all vertices of the second
For each of the following bracket notation descriptions, draw the equivalent multilist in graphical form such as shown in Figure 12.2. L10 a L2 b c de L3
(a) Show the bracket notation for the list of Figure 12.19(a).(b) Show the bracket notation for the list of Figure 12.19(b).(c) Show the bracket notation for the list of Figure 12.19(c). a (a) 20 D
Given the linked representation of a pure list such aswrite an in-place reversal algorithm to reverse the sublists at all levels including the topmost level. For this example, the result would be a
What fraction of the values in a matrix must be zero for the sparse matrix representation of Section 12.2 to be more space efficient than the standard two-dimensional matrix representation when data
Write a function to add an element at a given position to the sparse matrix representation of Section 12.2. 12.2 Matrix Representations Some applications must represent a large, two-dimensional
Write a function to delete an element from a given position in the sparse matrix representation of Section 12.2. 12.2 Matrix Representations Some applications must represent a large, two-dimensional
Write a function to transpose a sparse matrix as represented in Section 12.2. 12.2 Matrix Representations Some applications must represent a large, two-dimensional matrix where many of the elements
Write a function to add two sparse matrices as represented in Section 12.2. 12.2 Matrix Representations Some applications must represent a large, two-dimensional matrix where many of the elements
Write memory manager allocation and deallocation routines for the situation where all requests and releases follow a last-requested, first-released (stack) order.
Write memory manager allocation and deallocation routines for the situation where all requests and releases follow a last-requested, last-released (queue) order.
Show the result of allocating the following blocks from a memory pool of size 1000 using first fit for each series of block requests. State if a given request cannot be satisfied.(a) Take 300 (call
Show the result of allocating the following blocks from a memory pool of size 1000 using best fit for each series of block requests. State if a given request cannot be satisfied.(a) Take 300 (call
Show the result of allocating the following blocks from a memory pool of size 1000 using worst fit for each series of block requests. State if a given request cannot be satisfied.(a) Take 300 (call
Assume that the memory pool contains three blocks of free storage. Their sizes are 1300, 2000, and 1000. Give examples of storage requests for which(a) First-fit allocation will work, but not best
Implement the sparse matrix representation of Section 12.2. Your implementation should support the following operations on the matrix:• Insert an element at a given position,• Delete an element
Implement the MemManager ADT shown at the beginning of Section 12.3.Use a separate linked list to implement the freelist. Your implementation should work for any of the three sequential-fit methods:
Implement the MemManager ADT shown at the beginning of Section 12.3.Do not use separate memory for the free list, but instead embed the free list into the memory pool as shown in Figure 12.12. Your
Implement the MemManager ADT shown at the beginning of Section 12.3 using the buddy method of Section 12.3.1. Your system should support requests for blocks of a specified size and release of
Implement the Deutsch-Schorr-Waite garbage collection algorithm that is illustrated by Figure 12.18. a a 2 2 C e 5 6 (a) 3 b 3 b 5 (b) C curr 4 4 prev 6
Show the binary trie (as illustrated by Figure 13.1) for the following collection of values: 42, 12, 100, 10, 50, 31, 7, 11, 99. 0 0 1 2 0 1 0 24 0 32 0 1 37 0 1 0 0 40 1 0 1 42 1 120
Show the PAT trie (as illustrated by Figure 13.3) for the following collection of values: 42, 12, 100, 10, 50, 31, 7, 11, 99. 000XXXX 2 00XXXXX 2 4 OXXXXXX 1 7 24 4 0 01XXXXX 3 32 37 40 1XXXXXX 120
Write the insertion routine for a binary trie as shown in Figure 13.1. 0 0 1 2 0 1 0 24 0 32 0 1 37 0 1 0 1 0 0 1 40 42 1 120
Write the deletion routine for a binary trie as shown in Figure 13.1. 0 0 1 2 0 1 0 24 0 32 0 1 37 0 1 0 1 0 0 1 40 42 1 120
(a) Show the result (including appropriate rotations) of inserting the value 39 into the AVL tree on the left in Figure 13.4.(b) Show the result (including appropriate rotations) of inserting the
Show the splay tree that results from searching for value 75 in the splay tree of Figure 13.10(d). 17 18 89 (25) (42) 72 (d) (92) (75) 99
Show the splay tree that results from searching for value 18 in the splay tree of Figure 13.10(d). 17 18 89 (25) (42) 72 (d) (92) (75) 99
Some applications do not permit storing two records with duplicate key values.In such a case, an attempt to insert a duplicate-keyed record into a tree structure such as a splay tree should result in
Show the result of deleting point A from the k-d tree of Figure 13.11. B A E C (a) D LL X y X y B (15, 70) A (40, 45) C (70, 10) (b) D (69, 50) E (66, 85) F (85, 90)
(a) Show the result of building a k-d tree from the following points (inserted in the order given). A (20, 20), B (10, 30), C (25, 50), D (35, 25), E (30, 45), F (30, 35), G (55, 40), H (45, 35), I
(a) Show the result of deleting F from the PR quadtree of Figure 13.16.(b) Show the result of deleting records E and F from the PR quadtree of Figure 13.16. 0 127 B A C D E (a) LL 127 A (40,45) C
(a) Show the result of building a PR quadtree from the following points (inserted in the order given). Assume the tree is representing a space of 64 by 64 units. A (20, 20), B (10, 30), C (25, 50),
On average, how many leaf nodes of a PR quadtree will typically be empty? Explain why.
When performing a region search on a PR quadtree, we need only search those subtrees of an internal node whose corresponding square falls within the query circle. This is most easily computed by
(a) Show the result of building a bintree from the following points (inserted in the order given). Assume the tree is representing a space of 64 by 64 units. A (20, 20), B (10, 30), C (25, 50), D
Compare the trees constructed for Exercises 12 and 15 in terms of the number of internal nodes, full leaf nodes, empty leaf nodes, and total depths of the two trees.Data from in Exercise 12(a) Show
Show the result of building a point quadtree from the following points (inserted in the order given). Assume the tree is representing a space of 64 by 64 units. A (20, 20), B (10, 30), C (25, 50), D
Revise the BST class of Section 5.4 to use the AVL tree rotations. Your new implementation should not modify the original BST class ADT. Compare your AVL tree against an implementation of the
Revise the BST class of Section 5.4 to use the splay tree rotations. Your new implementation should not modify the original BST class ADT. Compare your splay tree against an implementation of the
Implement a city database using the k-d tree. Each database record contains the name of the city (a string of arbitrary length) and the coordinates of the city expressed as integer x- and
Implement a city database using the PR quadtree. Each database record contains the name of the city (a string of arbitrary length) and the coordinates of the city expressed as integer x- and
Implement a city database using the bintree. Each database record contains the name of the city (a string of arbitrary length) and the coordinates of the city expressed as integer x- and
Implement a city database using the point quadtree. Each database record contains the name of the city (a string of arbitrary length) and the coordinates of the city expressed as integer x- and

Showing 100 - 200 of 447