数据结构2009-2010-1-期末考试试卷

杭州师范大学信息科学与工程学院2009-2010学年第一学期期末考试 《数据结构》试卷（A ） Item Number Ⅰ Ⅱ Ⅲ Ⅳ Ⅴ total mark Note: Please write your answers on the answer sheet. 注意：请将答案填写在答题纸上。

I. Please select the answer for the following problems.(20 points) (1). The running time of binary search (二分查找) is ( ) A.(1)O B.()O N C.(log )O N D.(log )O N N (2). The running time of Quicksort (快速排序) is ( ) A.(1)O B.()O N C.2()O N D.(log )O N N (3).Given a directed graph represented by adjacency matrix, then the number of '1' in each column means ( ). A. in-degree of each vertex B. out-degree of each vertex C. the number of edges D. the number of connected components(连通分量) (4). Among the following sorting algorithms, ( ) has the average run time O(NlogN) with max extra space. A. Merge sort B. Heap sort C. Quick sort D. Shell sort (5).Given a complete undirected graph(无向完全图) with n vertices, the maximum number of edges in the graph must be ( ). A. n B. n ( n – 1) / 2 C. n + 1 D. n – 1 (6). In the following integer sequences, ( ) is NOT a heap(堆). A. {100, 98, 85, 82, 80, 77, 66, 60, 40, 20, 10} B. {100, 85, 98, 77, 80, 60, 82, 40, 20, 10, 66} C. {10, 20, 40, 60, 66, 77, 80, 82, 85, 98, 100} D. {100, 85, 40, 77, 80, 60, 66, 98, 82, 10, 20} (7). If the input to a stack is 1,2,3, and the output must not ( ). A. 1,2,3 B. 3,1,2 C. 3,2,1 D. 2,1,3 (8). If each node has only the left and right-child, in a binary tree of N nodes, there are ( ) NULL pointers representing children. A. N B.N 2 C.N+1 D.1 (9). For any nonempty binary tree, there are ( ) where n0 is the number of leaf nodes and n2 the number of nodes of degree 2. A. n2 = n1+1 B. n0 = n2+1 C. n0= n2 D. n0 = n2+2 (10). Given an circular queue (循环队列) Q[maxSize] with front and rear pointer (initially, front = 1 and rear = 0), its maximum capacity is maxSize and there is no other elements in it, then the condition of queue full is ( ). A. Q.front == Q.rear B. Q.front+Q.rear >= maxSize C. Q.front == (Q.rear+1) % maxSize D. Q.front == (Q.rear+2) % maxSize II. Please fill in the blank lines (12 points) Given an integer sequence 50, 60, 45, 32, 72, 63, 84, 35, 20, 78 and sorting them with an increasing order, please complete three problems (as below shows) and fill the solutions in blank lines on the answer sheet . (1) After the first run of the merge sorting(归并排序), the integer sequence is(4 points): __________________________________________________. (2) After the run of the shell sorting(希尔排序) by an increment 3, the integer sequence is (4 points): __________________________________________________.score score 班级： 学号： 姓名： 装 订 线 数据结构试题（第1页 共3页）(3) After the first run of quick sorting(快速排序) with the pivot which is selected by median-of-three (left, right, center) partitioning method, the integer sequence is(4 points):__________________________________________________.III. Please write or draw your answers for the following problems on the answer sheet. (44 points)(1) For the graph given by the right figure, obtain: (22 points)① the degree (度) of each vertex; (4 points); ② its adjacency matrix (邻接矩阵); (3 points) ③ its adjacency list (邻接表) representation; (3 points)④ the result of Depth First Search (DFS,深度优先搜索) with the adjacency list representation starting from vertex “1”; (3 points) ⑤ the result of Breath First Search (BFS 广度优先搜索) with the adjacency list representation starting from vertex “2”; (3 points) ⑥ the minimum cost spanning tree (最小生成树) using Primalgorithm or Kruskal algorithm. (6 points)(2). Given a binary tree with array representation as below shows, the questions are following(12points)1 2 3 4 5 6 7 8 9 10 11 12 13A B C D E F G H① draw the logical structure of this binary tree; (4 points)② give the results of preorder (先序), postorder (中序) and level-order (层次) traversal;(3 points) ③ draw its threaded binary trees(线索化二叉树).(5 points)(3). Insert the keys: 50, 60, 45, 32, 72, 63 and 84 into a hash table with open addressing (开放定址法) of quadratic probing (二次探测, f (i ) = i 2 ) and a size of 13. Use the hash function hash(k ) = k %13, Please draw the resulting table and computing the average search time of successful search (计算查找成功时的平均查找时间).(10 points)IV . Please complete the Insertion algorithm for a binary search tree. (6 points)Note : The data structure of binary search tree is defined as follows.typedef int ElementType;struct TreeNode;typedef struct TreeNode *SearchTree;struct TreeNode{ElementType Element;SearchTree Left;SearchTree Right;};SearchTree Insert( ElementType X, SearchTree T ){if ( T == NULL ) { /* Create and return a one-node tree */T = malloc( sizeof( struct TreeNode ) );if ( T == NULL ) FatalError( "Out of space!!!" );else { T->Element = X;T->Left = T->Right = NULL;}score 0 1 2 3 48 7 5 6 9 8 4 11 6 3 12 9 1 7 18 5 数据结构试题（第2页 共3页）} /* End creating a one-node tree */else /* If there is a tree */if ( X < T->Element ) A;else if ( B) C;/* Else X is in the tree already; we'll do nothing */return T; /* Do not forget this line!! */}V. Coding. (18 points)score1. Please write a recursive (递归) C function that counts the number of nodeswith 1 degree (度为1的结点) in a binary tree. The input is a binary tree and the output is the number of nodesm in that tree. (10 points)2. Write an Insert function for List represented by single linked list with a head node(带头结点的单链表), and the Insert is : Insert an element X into i position in the single linked list, if element X is inserted successfully, then return 0, otherwise return -1. (8 points)数据结构试题（第3页共3页）。