﻿ C语言代写 | CSc 345: Homework Assignment 4

### C語言代寫 | CSc 345: Homework Assignment 4 ### C語言代寫 | CSc 345: Homework Assignment 4

1. (10pts) Give a θ(n)-time nonrecursive procedure that reverses a singly
linked list of n elements. The procedure should use no more than constant
storage beyond that needed for the list itself.
2. (10pts) Suppose that we are storing a set of n keys into a hash table of
size m. Show that if the keys are drawn from a universe U with |U| > nm,
then U has a subset of size n consisting of keys that all hash to the same
slot, so that the worst-case searching time for hashing with chaining is
θ(n).
3. (10pts) What is the difference between the binary-search-tree property
and the min-heap property (see page 153)? Can the min-heap property
be used to print out the keys of an n-node tree in sorted order in O(n)
time? Show how, or explain why not.
4. (10pts) Write the TREE-PREDECESSOR procedure.
5. (10pts) Consider a binary search tree T whose keys are distinct. Show
that if the right subtree of a node x in T is empty and x has a successor
y, then y is the lowest ancestor of x whose left child is also an ancestor of
x. (Recall that every node is its own ancestor.)
6. (10pts) An alternative method of performing an inorder tree walk of an
n-node binary search tree finds the minimum element in the tree by calling
TREE-MINIMUM and then making n ? 1 calls to TREE-SUCCESSOR.
Prove that this algorithm runs in θ(n) time.
7. (10pts) We can sort a given set of n numbers by first building a binary
search tree containing these numbers (using TREE-INSERT repeatedly
to insert the numbers one by one) and then printing the numbers by an
inorder tree walk. What are the worst-case and best-case running times
for this sorting algorithm?
1
8. (10pts) Given an adjacency-list representation of a directed graph, how
long does it take to compute the out-degree of every vertex? How long
does it take to compute the in-degrees?
9. (10pts) Let (u, v) be a minimum-weight edge in a connected graph G.
Show that (u, v) belongs to some minimum spanning tree of G.
10. (10pts) Prove that if G is an undirected bipartite graph with an odd
number of vertices, then G is nonhamiltonian.

#### 在線客服  Essay_Cheery  