《数据结构例题解析_资格考试-公务员考试.pdf》由会员分享，可在线阅读，更多相关《数据结构例题解析_资格考试-公务员考试.pdf（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、.专业 .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 list 3.(b )The worst-time for removing an element from a seque
2、nce 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 in
3、finite 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 u
4、nsorted 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.9
5、9.(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.44 10.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 v
6、ertices 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,t Fig.1 11.Here is an array of ten integers:5 3 8 9 1 7 0 2 6 4 Suppose we partition this array using quicksorts partition function and using 5 for the pivot.Which
7、 shows the array after partition finishes:a.5 3 4 2 1 0 7 9 6 8 b.0 3 4 2 1 5 7 9 6 8 c.3 1 0 2 4 5 8 9 6 7 d.3 1 0 2 4 5 8 9 7 6 e.None of the above II 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
8、.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.Frequen
9、tly known a LIFO(Last-In-First-Out)structure.5.T(n)=2T(n/2)+,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
10、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).数组最短路径顶点集专业在具有个顶点的带权有向图中各边上权值由给出建立一个数组保存从顶点到顶点的最短路径长度同时用数组存放求到的最短路径数组初始化数组初始化顶点加入顶点集合选择当前不在集合中具有最短路径的路复杂度主要计算算法的步数可以看出当前循环执行的步数与的值是相等的所以可列
11、复杂度的计算忽略常数知识点与的区别知识点复杂度分析线性序列思路很显然当元素在的末尾的时候元素复杂度最高知识点循环队列重点思路主要置就是题目中说的重点代表头指针代表尾指针循环队列空时满时知识点递归的定义终止条件缺失则可能无调用知识点完全二叉树与满二叉树的区别思路学院上有如下定义并且有结点计算公式其中为树的高度与某百度定义树的高度不.专业 .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
12、 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 n
13、ode 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.BDCAE Fig.2 A B C D E A 0 1 0 1 0 B 0 0 1 1 0 C 0
14、 0 0 0 1 D 0 0 0 0 1 E 0 0 0 0 0 Dft:ABCED Bft:ABDCE 2The sequence of input keys is shown below:19，1，23，14，55，20，84，27，68，11，10，17 A 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
15、results of inserting 53,17,78,09,45,65,87 each,one at a time,in a initially empty max heap（大根堆）数组最短路径顶点集专业在具有个顶点的带权有向图中各边上权值由给出建立一个数组保存从顶点到顶点的最短路径长度同时用数组存放求到的最短路径数组初始化数组初始化顶点加入顶点集合选择当前不在集合中具有最短路径的路复杂度主要计算算法的步数可以看出当前循环执行的步数与的值是相等的所以可列复杂度的计算忽略常数知识点与的区别知识点复杂度分析线性序列思路很显然当元素在的末尾的时候元素复杂度最高知识点循环队列重点思路主要置就是
16、题目中说的重点代表头指针代表尾指针循环队列空时满时知识点递归的定义终止条件缺失则可能无调用知识点完全二叉树与满二叉树的区别思路学院上有如下定义并且有结点计算公式其中为树的高度与某百度定义树的高度不.专业 .4.write the sequence of preorder,postorder traversals and add inorder threads in the tree.ACEFBD Fig.3 5.Build a Huffman tree and determine Huffman code when the probability distribution(概率分布)over
17、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.04 6.Graph G shown in Fig 4 is a directed graph,please describe G with adjacency list and write topological ordering.Fig.4 IV Fill in blank of algorithms.（15）1 Here is single source shortest path algorithm Dijkstra.Fill
18、in blank of the algorithm.class Graph /图的类定义 private:float EdgeNumVerticesNumVertices;float distNumVertices;/最短路径长度数组 int pathNumVertices;/最短路径数组 int SNumVertices;/最短路径顶点集 数组最短路径顶点集专业在具有个顶点的带权有向图中各边上权值由给出建立一个数组保存从顶点到顶点的最短路径长度同时用数组存放求到的最短路径数组初始化数组初始化顶点加入顶点集合选择当前不在集合中具有最短路径的路复杂度主要计算算法的步数可以看出当前循环执行的步数与
19、的值是相等的所以可列复杂度的计算忽略常数知识点与的区别知识点复杂度分析线性序列思路很显然当元素在的末尾的时候元素复杂度最高知识点循环队列重点思路主要置就是题目中说的重点代表头指针代表尾指针循环队列空时满时知识点递归的定义终止条件缺失则可能无调用知识点完全二叉树与满二叉树的区别思路学院上有如下定义并且有结点计算公式其中为树的高度与某百度定义树的高度不.专业 .public:void ShortestPath(int,int);int choose(int);void Graph:ShortestPath(int n,int v)/在具有 n 个顶点的带权有向图中,各边上权值由 Edgeij 给出
20、。建立一个数组: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 mi
21、n )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)
22、/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、树的前、中、后序遍历，重点 首先要明白前、中、后序遍历是根据根的位置决定的，比如前序遍历就是(根左右)，中 序遍历为(左根右).首先你得能很熟练的写出一棵树的前、中、后序
23、遍历(preorder、inorder、postorder)，然 后可以进行一下分析，对于前序遍历 ABECDFGHIJ，中序遍历 EBCDAFHIGJ，由前序 遍历可知根结点肯定为 A，那么从中序遍历里面可以以 A 为中点进行分割，左边的部 分必定属于左子树，右边的部分肯定属于右子树，然后进行一步步分割，自己多尝试一 下就 ok 了 构造树如下：数组最短路径顶点集专业在具有个顶点的带权有向图中各边上权值由给出建立一个数组保存从顶点到顶点的最短路径长度同时用数组存放求到的最短路径数组初始化数组初始化顶点加入顶点集合选择当前不在集合中具有最短路径的路复杂度主要计算算法的步数可以看出当前循环执行的
24、步数与的值是相等的所以可列复杂度的计算忽略常数知识点与的区别知识点复杂度分析线性序列思路很显然当元素在的末尾的时候元素复杂度最高知识点循环队列重点思路主要置就是题目中说的重点代表头指针代表尾指针循环队列空时满时知识点递归的定义终止条件缺失则可能无调用知识点完全二叉树与满二叉树的区别思路学院上有如下定义并且有结点计算公式其中为树的高度与某百度定义树的高度不.专业 .所以后序遍历为:EDCBIHJGFA ps:已知前序遍历和后序遍历，不能确定唯一的中序遍历 7、n/2+1 满二叉树,设叶子层 leaf node为第 p 层，则非叶子结点 20+21+22+.+2p-1=2p-1 叶子结点：2p 若
25、总结点为 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、大顶堆 大顶堆的定义，如题目所说 三、算法应用题 1、邻接矩阵为：A B C D E A 0 1 0 1 0 B 0 0 1 1 0 C 0 0 0
26、0 1 D 0 0 0 0 1 E 0 0 0 0 0 dfs 序列:ABCED bfs 序列:ABDCE 考点、重点：图的存储及 dfs、bfs 序列。区分 dfs 与 bfs，dfs 为走子结点走到不能走为止，bfs 为要先走遍所有的邻居结点。2、考点：hash hash 序列如下 数组最短路径顶点集专业在具有个顶点的带权有向图中各边上权值由给出建立一个数组保存从顶点到顶点的最短路径长度同时用数组存放求到的最短路径数组初始化数组初始化顶点加入顶点集合选择当前不在集合中具有最短路径的路复杂度主要计算算法的步数可以看出当前循环执行的步数与的值是相等的所以可列复杂度的计算忽略常数知识点与的区别知
27、识点复杂度分析线性序列思路很显然当元素在的末尾的时候元素复杂度最高知识点循环队列重点思路主要置就是题目中说的重点代表头指针代表尾指针循环队列空时满时知识点递归的定义终止条件缺失则可能无调用知识点完全二叉树与满二叉树的区别思路学院上有如下定义并且有结点计算公式其中为树的高度与某百度定义树的高度不.专业 .average length search=(1+1+1+2+3+1+3+4+3+1+3+6)/12=29/12次(ps:hash这一章我们班还没有学,答案仅是靠自己感觉写的,当某链只有一个元素时 查询长度为 1=)3、考点：大根堆的构造 4、考点：前、中、后序遍历+线索树 5、考点：哈夫曼树
28、构造树如下：数组最短路径顶点集专业在具有个顶点的带权有向图中各边上权值由给出建立一个数组保存从顶点到顶点的最短路径长度同时用数组存放求到的最短路径数组初始化数组初始化顶点加入顶点集合选择当前不在集合中具有最短路径的路复杂度主要计算算法的步数可以看出当前循环执行的步数与的值是相等的所以可列复杂度的计算忽略常数知识点与的区别知识点复杂度分析线性序列思路很显然当元素在的末尾的时候元素复杂度最高知识点循环队列重点思路主要置就是题目中说的重点代表头指针代表尾指针循环队列空时满时知识点递归的定义终止条件缺失则可能无调用知识点完全二叉树与满二叉树的区别思路学院上有如下定义并且有结点计算公式其中为树的高度与某
29、百度定义树的高度不.专业 .6、考点：拓扑排序 邻接表如下：邻接表形式如上，构造拓扑序列的算法请自行看书，主要是对入度为 0 的结点进行压队列(或栈)一个可能的答案为：1 2 3 4 5 6 7 8 9 V、编程题 以下所有代码均为大致思路代码，细节请忽略()1、计算叶子结点数 数组最短路径顶点集专业在具有个顶点的带权有向图中各边上权值由给出建立一个数组保存从顶点到顶点的最短路径长度同时用数组存放求到的最短路径数组初始化数组初始化顶点加入顶点集合选择当前不在集合中具有最短路径的路复杂度主要计算算法的步数可以看出当前循环执行的步数与的值是相等的所以可列复杂度的计算忽略常数知识点与的区别知识点复杂
30、度分析线性序列思路很显然当元素在的末尾的时候元素复杂度最高知识点循环队列重点思路主要置就是题目中说的重点代表头指针代表尾指针循环队列空时满时知识点递归的定义终止条件缺失则可能无调用知识点完全二叉树与满二叉树的区别思路学院上有如下定义并且有结点计算公式其中为树的高度与某百度定义树的高度不.专业 .2、求无向图最大度数结点 3、裸链表？随便写写。数组最短路径顶点集专业在具有个顶点的带权有向图中各边上权值由给出建立一个数组保存从顶点到顶点的最短路径长度同时用数组存放求到的最短路径数组初始化数组初始化顶点加入顶点集合选择当前不在集合中具有最短路径的路复杂度主要计算算法的步数可以看出当前循环执行的步数与
31、的值是相等的所以可列复杂度的计算忽略常数知识点与的区别知识点复杂度分析线性序列思路很显然当元素在的末尾的时候元素复杂度最高知识点循环队列重点思路主要置就是题目中说的重点代表头指针代表尾指针循环队列空时满时知识点递归的定义终止条件缺失则可能无调用知识点完全二叉树与满二叉树的区别思路学院上有如下定义并且有结点计算公式其中为树的高度与某百度定义树的高度不.专业 .数组最短路径顶点集专业在具有个顶点的带权有向图中各边上权值由给出建立一个数组保存从顶点到顶点的最短路径长度同时用数组存放求到的最短路径数组初始化数组初始化顶点加入顶点集合选择当前不在集合中具有最短路径的路复杂度主要计算算法的步数可以看出当前循环执行的步数与的值是相等的所以可列复杂度的计算忽略常数知识点与的区别知识点复杂度分析线性序列思路很显然当元素在的末尾的时候元素复杂度最高知识点循环队列重点思路主要置就是题目中说的重点代表头指针代表尾指针循环队列空时满时知识点递归的定义终止条件缺失则可能无调用知识点完全二叉树与满二叉树的区别思路学院上有如下定义并且有结点计算公式其中为树的高度与某百度定义树的高度不