课程名称：资料结构 课程性质：必修 课程范围：课本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