110年 - 110 國立高雄大學_碩士班招生考試_資訊工程學系：離散數學與資料結構#102139

(a) at least one ball is selected for each color?

(b) no more than four balls are selected for each color?

(c) odd number of red balls, odd number of green balls, even number of white balls, and even number of black balls are selected?

(a) Describe each of the four properties: (i) reflexivity, (ii) symmetry, (iii) transitivity, and (iv) antisymmetry.

(b) Show that R is an equivalence relation.

(c) Describe the equivalence classes of the relation R.

3. (10%) For the B-tree below, show the new B-tree that would result from inserting 21.

(a) (10%) Use Heapsort to sort the array and show the array a[ ] after the complete max heap is constructed (i.e., after phase 1 of Heapsort is done).

(b) (5%) What is the time complexity of Heapsort?

5. (5%) Consider the five keys on the left side of the figure below. Also as shown in the figure, a hash function is applied to these five keys where two keys are hashed to the same integer. Discuss how to solve this collision.

(a) (20%) Discuss how to find the intersection nodes of the two lists (the intersection nodes refer to the nodes appear in both of the two lists), and what is the corresponding time complexity.

(b) (15%) If the nodes in the lists are not lexicographically ordered, discuss how to find the intersection nodes of the two lists, and what is the corresponding time complexity.

7. (5%) Write the code segment that inserts into a circular doubly linked list the node to which x points before the node to which y points.

110年 - 110 國立高雄大學_碩士班招生考試_資訊工程學系：離散數學與資料結構#102139

試卷資訊

選擇題 (0)

申論題 (13)