数据结构例题解析.doc

I Single Choice(10 points)1. ( a )For the following program fragment the running time(Big-Oh) is .i = 0;s = 0;while(s ( 5*n*n + 2) i+; s = s + i;a. O(n) b. O(n2) c. O(n1/2) d. O(n3)2. ( c )Which is non-linear data structure_.a. queue b.stack c. tree d. sequence list3.( b )The worst-time for removing an element from a sequence list (Big-Oh) is . a. O(1) b. O(n) c. O(n2) d. O(n3)4.( d )In a circular queue we can distinguish(区分) empty queues from full queues by .a. using a gap in the array b. incrementing queue positions by 2 instead of 1 c.keeping a count of the number of elements d. a and c 5. ( b )A recursive function can cause an infinite sequence of function calls if .a. the problem size is halved at each step b. the termination condition is missing c. no useful incremental computation is done in each step d. the problem size is positive 6( c )The full binary tree with height 4 has nodes. a. 15 b. 16 c.31 d.32 7. ( b )Searching in an unsorted list can be made faster by using .a. binary search b. a sentinel（哨兵） at the end of the list c. linked list to store the elements d. a and c 8.（ b ）Suppose there are 3 edges in an undirected graph G, If we represent graph G with a adjacency matrix, How many “1”s are there in the matrix? a. 3 b. 6 c. 1 d. 99. ( d ) Construct a Huffman tree by four leaf whose weights are 9, 2, 5, 7 respectively. The weighted path length is_.a. 29 b. 37 c. 46 d.4410. Consider the following weighted graph. Consider Dijkstras algorithm on this graph to find the shortest paths with s as a starting vertex. Which are the first four vertices extracted from the priority queue by the algorithm (listed in the order they are extracted) ? a. s, y, t, x b. s, y, x, z c. s, t, y, x d. s, y, x, tFig. 111. Here is an array of ten integers:5 3 8 9 1 7 0 2 6 4Suppose we partition this array using quicksorts partition function and using 5 for the pivot. Which shows the array after partition finishes:a. 5 3 4 2 1 0 7 9 6 8b. 0 3 4 2 1 5 7 9 6 8c. 3 1 0 2 4 5 8 9 6 7d. 3 1 0 2 4 5 8 9 7 6e. None of the aboveII Fill in Blank (10 points)1. For the following program fragment the running time(Big-Oh) is O(n2) . for ( int i = 0; i n; i+ ) for ( int j = 0; j =i; j+) s; /s为某种基本操作2. We store a 44 symmetric matrix A into an array B with row major order, Store the lower triangle only. the index of element a23 in B is 6 .3 We can use 3 vector type to store value and of non-zero elements in a sparse matrix.4. A_stack_ is a list where removal and addition occur at the same end . Frequently known a LIFO (Last-In-First-Out) structure. 5. T( n ) = 2T( n/2 )+ cn, T(n)=O(logn) T(n) = T( n-1)+cn, T( n ) = O(_n_)6. There is a binary tree whose elements are characters. Preorder list of the binary tree is “ABECDFGHIJ” and inorder list of the binary tree is “EBCDAFHIGJ”. Postorder traversal sequence of the binary tree is EDCBIHJGFA . 7There are (n+1)/2 leaf nodes in a full binary tree with n nodes.8When the input has been sorted ,the running time of insertion sort(Big-Oh) is O(n) .9We sort the sequence（43，02，80，48，26，57，15，73，21，24，66）with shell sort for increment 3, the result is _ (15 02 21 24 26 57 43 66 80 48 73) _ .10、In a circular queue, “front” and “rear” are the front pointer and rear pointer respectively. Queue size is “maxsize”. When insert an element in the queue, rear = _ (rear+1)%maxsize_ 11. A _B树_ is an example of a search tree which is multiway (allows more than two children).12. A tree in which every node is no smaller than its children is termed _大顶堆_.III Application of Algorithms （35 points）1.Graph G shown in Fig 2 is a directed graph, please describe G with adjacency matrix and write the orders of breadth first traversal and depth first traversal. Fig.2 A B C D E A 0 1 0 1 0B 0 0 1 1 0C 0 0 0 0 1D 0 0 0 0 1E 0 0 0 0 0Dft:ABCEDBft:ABDCE2The sequence of input keys is shown below: 19，1，23，14，55，20，84，27，68，11，10，17A fixed table size of 19 and a hash function H(key)=key%13，with linear probing(线性探测), fill the table below and compute the average length of successful search.3. Show the results of inserting 53,17,78,09,45,65,87 each , one at a time, in a initially empty max heap（大根堆） 4. write the sequence of preorder,postorder traversals and add inorder threads in the tree. Fig. 35. Build a Huffman tree and determine Huffman code when the probability distribution(概率分布) over the 8 alphabets ( c1, c2, c3, c4, c5, c6, c7, c8 ) is (0.05, 0.25, 0.03, 0.06, 0.10, 0.11, 0.36, 0.046. Graph G shown in Fig 4 is a directed graph, please describe G with adjacency list and write topological ordering. Fig. 4IV Fill in blank of algorithms. （15）1 Here is single source shortest path algorithm Dijkstra. Fill in blank of the algorithm.class Graph /图的类定义 private: float EdgeNumVerticesNumVertices; float distNumVertices; /最短路径长度数组 int pathNumVertices; /最短路径数组 int SNumVertices; /最短路径顶点集public: void ShortestPath ( int, int ); int choose ( int ); void Graph : ShortestPath ( int n, int v )/在具有 n 个顶点的带权有向图中, 各边上权值由Edgeij给出。建立一个数组: distj, 0 j n, /保存从顶点 v 到顶点 j 的最短路径长度, 同时用数组pathj, 0 j n, 存放求到的最短路径。 for ( int i = 0; i n; i+) disti = Edgevi; /dist数组初始化 Si = 0; if ( i != v & disti MAXNUM) pathi = v; else pathi = -1; /path数组初始化 Sv = 1; distv = 0;/顶点v加入顶点集合 /选择当前不在集合S中具有最短路径的顶点u for ( i = 0; i n ; i+ ) float min = MAXNUM; int u = v; for ( int j = 0; j n; j+ ) if ( !Sj & distj min ) u = j; min = distj; Su = 1; /将顶点u加入集合S for ( int w = 0; w n; w+ ) /修改 if ( !Sw & Edgeuw (min+Edgeuw) ) distw = min + Edgeuw ; pathw = u; 3Consider the following function to balance symbols stored in string exp that includes parentheses（圆括号） and numbers.Please Fill in blank.#include Using namespace std;int matching(string &exp) /exp is a pointer to a string to check int state = 1,i=0; char e; stack s; while ( i_%注意10题在priority_queue里进行更新时一开始肯定加入s、y结点，而后x结点会因为松弛操作从而距离变为1+3=4T(8)-T(4)-T(2)-T(1),所以计算次数为log16=4,类似T(n) = T( n-1)+cn的复杂度可以计算。6、 树的前、中、后序遍历，重点首先要明白前、中、后序遍历是根据根的位置决定的，比如前序遍历就是(根左右)，中序遍历为(左根右).首先你得能很熟练的写出一棵树的前、中、后序遍历(preorder、inorder、postorder)，然 后可以进行一下分析，对于前序遍历ABECDFGHIJ，中序遍历EBCDAFHIGJ，由前序遍历可知根结点肯定为A，那么从中序遍历里面可以以A为中点进行分割，左边的部分必定属于左子树，右边的部分肯定属于右子树，然后进行一步步分割，自己多尝试一下就ok了构造树如下：所以后序遍历为:EDCBIHJGFAps:已知前序遍历和后序遍历，不能确定唯一的中序遍历7、 n/2+1 满二叉树,设叶子层leaf node为第p层，则非叶子结点20+21+22+.+2p-1 = 2p-1 叶子结点：2p 若总结点为n,那叶子结点为n/2+1 ps:有好多种答案，比如(n+1)/2,n/2取下界等。8、 O(N) 关于插入排序，最好的情况就是序列已经有序，那就少去了比较的步数，直接进行 n个元素的插入，故复杂度为O(N)9、15 02 21 24 26 57 43 66 80 48 73 希尔排序。每个数与增量处进行大小比较若大于则交换。10、 (rear+1)%maxsize 前面讲过11、B树 B树相对来说复杂一点，只会这样考了。= =12、 大顶堆 大顶堆的定义，如题目所说3、 算法应用题1、 邻接矩阵为： A B C D E A 0 1 0 1 0 B 0 0 1 1 0 C 0 0 0 0 1 D 0 0 0 0 1 E 0 0 0 0 0dfs序列:ABCEDbfs序列:ABDCE考点、重点：图的存储及dfs、bfs序列。区分dfs与bfs，dfs为走子结点走到不能走为止，bfs为要先走遍所有的邻居结点。2、 考点：hash hash序列如下 average length search = (1+1+1+2+3+1+3+4+3+1+3+6)/12=29/12次(ps:hash这一章我们班还没有学,答案仅是靠自己感觉写的,当某链只有一个元素时 查询长度为1= =)3、考点：大根堆的构造 4、 考点：前、中、后序遍历+线索树 5、 考点：哈夫曼树 构造树如下： 6、 考点：拓扑排序 邻接表如下： 邻接表形式如上，构造拓扑序列的算法请自行看书， 主要是对入度为0的结点进行压队列(或栈) 一个可能的答案为：1 2 3 4 5 6 7 8 9 V、编程题 以下所有代码均为大致思路代码，细节请忽略()1、 计算叶子结点数 2、 求无向图最大度数结点 3、 裸链表？随便写写。