一些資料結構的問題

Question

1.Show that n^2/log n=Θ(n^2) is incorrect.

2.Explain why the array is more suitable to represent a heap.

3.What is a self-referential structure? Give an example to show it.

Leslie · Accepted Answer

1.

n^2/logn=Theta(n^2) if and only if

(1) n^2/logn=O(n^2) and

(2) n^2/logn=Omega(n^2).

(1) means there exists a c>0

such that n^2/logn <= cn^2, for all large enough n.

This is true, because n^2/logn <= n^2 for all n>=2

(supposing log is of base 2, and so logn >= 1) (choosing c=1).

If (2) is true, there exists a c>0

such that n^2/logn >= cn^2, for all large enough n.

This is impossible, because when n gets larger and larger,

(cn^2)/(n^2/logn) will finally approach infinity, for any c>0.

Since (2) is not ture, we know that n^2/logn=Theta(n^2) is incorrect.

2.

According to the definition of a heap (which is a complete binary tree),

and the numbering of elements in a complete binary tree,

we can store the element with number i as the array element with index i.

So, it is easy to find the parent or find its children of any element i.

It saves spaces, compared with the linked representation of a complete

binary tree.

3.

A self-referential structure is a data structure that includes

references to other data of its same type.

Example (in C):

typedef struct linklist

{ int data;

struct linklist *next;

} linklist;

/* 有錯請指教 */

Trending News