課程名稱：資料結構 課程性質：必修 課程範圍：課本1~3章 開課教師：沈錳坤 開課學院：理學院 開課系級：資科系 考試日期(年月日)：2011/11/17 考試時限(Mins)：180分 試題本文： 1.(20%) Given the following declarations of the linked list with a header node, typedef struct Node *List; typedef struct Node *Position; Struct Node { Integer Element; Position *Next; } (1)What does the following funcion do? Position Magic( Integer X, List L) { Position P; P = L; while( P->Next != NULL && P->Next->Element != X) { P = P->Next; } return P; } (2)Please write the code in C language to get the intersection of two sorted list P and Q. (For example, P is a sorted list {1, 3, 5, 7, 9, 11, 13, 15, 18} while Q is a sorted list {3, 6, 9, 12, 15}, the intersection will be a sorted list {3, 9, 15 }) 2.(10%)Alogical expression contains three types of operators, namely, in order of precedence, ~(not), v(or), ^(and). Given the following logical expression B ^ ( A ^ F v ~ C ) v E ^ D (1)Please convert this expression from infix to postfix. (2)Please give the expression tree for this logical expression. (3)To convert this logical expression from infix to postfix, please give the content of the stack, from top to bottom, after the operand "F" is read. (4)To convert this logical expression from infix to postfix, please give the content of the stack, from top to bottom, after the operand ")" is read. 3.(10%) (1)Please show the result of sorting 64, 16, 9, 316, 56, 27, 35, 136, using radix sort with 7 buckets. (The result of each pass must be listed.) (2)Please show that the time complexity of radix sorting of n keys with r buckets. 4.(10%)Given an n-node binary search tree using array implementation, please give (1)the smallest possible position, and (2)the largest possible position in this array for (a)the smallest element and (b)the largest element of this bianry search tree respectively. 5.(20%)Given the following AVL tree in array implementation shown below, value | 8 4 12 2 6 10 30 - - - - - - 14 32 ------------------------------------------------------ id | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 (1)Please five the result (by drawing the tree) after insertion of 28. (2)Please give the result after insertion of 26 (continuing from the above). (3)Please illustrate why RL is a double rotation by drawing trees. (4)Please give the time complexity of double rotaion, insertion operation of AVL tree respectively. 6.(10%)Please give an O(n) algorithm to count the number of nodes in an AVL tree. (Assume that only element, left pointer, right pointer are stored in each node.) 7.(10%)Please show the result of inserting the follwoing keys into an initially empty B-tree of order 3: 30, 10, 40, 50, 90, 20, 60, 80, 70. 8.(10%)Single Choice (1)The worst time complexity of deleting a key, after finding this key, in a sorted array of N keys. (a) O(1) (b) O(logN) (c) O(N) (d) O(NlogN) (e) O(N^2) (f) O(N^2logN) (2)The worst time complexity of deleting a key, after finding this key, in a sorted linked list of N keys. (a) O(1) (b) O(logN) (c) O(N) (d) O(NlogN) (e) O(N^2) (f) O(N^2logN) (3)The best time complexity of deleting a key, after finding this key, in a sorted linked list of N keys. (a) O(1) (b) O(logN) (c) O(N) (d) O(NlogN) (e) O(N^2) (f) O(N^2logN) (4)The worst time complexity of comparison operations in selection sorting of N keys. (a) O(1) (b) O(logN) (c) O(N) (d) O(NlogN) (e) O(N^2) (f) O(N^2logN) (5)The worst time complexity of deleting a key in a binary search tree of N keys. (a) O(1) (b) O(logN) (c) O(N) (d) O(NlogN) (e) O(N^2) (f) O(N^2logN) (6)The best time complexity of deleting a key in a binary search tree of N keys. (a) O(1) (b) O(logN) (c) O(N) (d) O(NlogN) (e) O(N^2) (f) O(N^2logN) (7)The worst time complexity of finding the maximum in an AVL tree of N keys. (a) O(1) (b) O(logN) (c) O(N) (d) O(NlogN) (e) O(N^2) (f) O(N^2logN) (8)The worst time complexity of insertion a key in a N-key B-tree of order M ( in memory) (a) O(1) (b) O(log[M/2]N) (c) O(N) (d) O(Nlog[M/2]N) (e) O(N^2) (f) O(N^2log[M/2]N) (用[]括住的表示為底數) (9)The worst time complexity of pushing an element into a stach of N elements in linked list implementation. (a) O(1) (b) O(logN) (c) O(N) (d) O(NlogN) (e) O(N^2) (f) O(N^2logN) 10.Which of the following data, inserted in the input order, will produce a complete binary search tree? (a)(Bill, Grace, James, John, Lily, Mary) (b)(John, Mary, Grace, Bill, Lily, James) (c)(Mary, Lily, John, James, Grace, Bill) (d)(James, Grace, John, Bill, Lily, Mary) (e)(Grace, Bill, James, John, Mary, Lily) --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.119.41.122