数据结构-经典笔试题.doc

软件技术基础一、名词解释：1. 数据结构数据结构就是数据的组织形式，也可看成是包含数据结构的数据表，说明数据之间存在着一定的相互关系或约束。2. 逻辑结构我们把只表现元素之间逻辑关系，而不涉及它们在计算机中的表示，只是理论的、反映在纸面上的东西，这种抽象的数据结构称为逻辑结构。3. 物理结构抽象的数据结构在计算机内的表示，也就是映射在存储空间上的、具体的数据结构在计算机内表示，也就是映射在存储空间上的、具体的数据结构。二、问答题：1. 简述“软件工程”的工程化的思想。答：软件工程就是应用一些科学理论和工程上的技术来指导软件开发。软件工程将研制软件的全过程分为六个阶段：问题说明，需求分析，系统设计，编写程序，测试工作，运行与维护。软件工程的基本原则是：划分软件生命期，运行计划评审，编制软件文档。2. 说明对程序进行评价时，“时间”与“空间”之间的关系。答：时间性和空间性是程序的效率问题。时间效率决定于：源程序转换为目标程序的时间和目标程序执行的时间。时间效率与编译质量有关，与算法的简化程度有关，还与用户对语言的熟练程度有关，其中，算法的效率起主要作用。空间效率一般指程序花费的内存空间的问题。对于同等复杂程度的程序：一般时间效率越高的程序，占用的内存就越大，空间效率就越低；一般时间效率越低的程序，占用的内存就越小，空间效率就越高。两者具有一定的矛盾性。但是随着内存容量的不断增大，往往会牺牲空间性来提高时间性。3. 依照“软件工程”的思想，叙述软件生命周期的不同阶段及各阶段的主要工作内容。答：在软件工程中，把从软件的计划开始，经历问题的说明（定义），需求分析，设计代码，测试与维护，直到软件报废为止的整个期间，称为软件的生命周期。在软件生命周期中，除了最后的运行与维护属于运行期，其它都称为开发期。1） 问题说明：对研究的问题进行完整而且适当的说明。2） 需求分析：根据问题说明，确定软件必须具有的功能。不是具体解决问题，而是明确必须“做什么”。3） 系统设计：将反映用户要求的逻辑模型转换为一个具体的设计方案，使用伪码来描述算法。4） 编写程序：将伪码转换为高级语言的形式。5） 测试工作：检查程序和系统的其他部分是否满足设计要求。6） 运行与维护：将验收后的软件交付用户使用，通过实际运行环境的检验，对不适应的部分进行修改和扩充。4. 拓扑排序中使用了那些数据结构共使用了数组，链表，图和堆栈四种数据结构。三、求二叉树的叶节点的个数：algorithm countleaf( Tree *t, int count )if( t != null )if( t-lchild = null & t-rchild = null )count+;coutleaf( t-lchild, count );coutleaf( t-rchild, count );四、求二叉树深度的算法：algorithm depth( Tree *t ) if( t = null ) return( 0 ); else hl = depth( t-lchild ); hr = depth( t-rchild ); if( hl hr ) return( hl + 1 ); else return( hr + 1 ); 五、将二叉树的左右孩子交换的算法：algorithm swap( Tree *b ) /自顶向下的交换 Tree *t; if( b = null ) return; else t = b-lchild; b-lchild = b-rchild; b-rchild = t; swap( b-lchild ); swap( b-rchild ); 六、用两个栈模拟一个队列：algorithm 用两个栈模拟一个队列stack s1, s2; / 容量都为n。 void 元素入队 int x; if( s1-top = n ) printf( 队列上溢 ); else push( s1, x ); void 元素出队 int x; s2-top = 0; while( !Empty( s1 ) ) push( s2, pop( s1 ) ); pop( s2, x ); while( !Empty( s2 ) ) push( s1, pop( s2 ) ); void 判断队列是否为空 if( isEmpty( s1 ) ) return( 1 ); else return( 0 ); 七、邻接表的排序： 对给定的数组A 1:n ，假定每个元素是由形式age-link的记录组成，其中age域表示年龄，link域指向由name-link组成的链表，该链表记录了同龄人的姓名。要求设计算法，使A 1 链表中的年龄小于A 2 链表中的年龄，A 2 链表中的年龄小于A 3 链表中的年龄algorithm 邻接表的排序 for( i = 1; i n; i+ ) pos = i; for( j = i + 1; j age age ) pos = j; if( pos != i ) temp = A( i )-age; ptr = A( i )-link; A( i )-age = A( pos )-age; A( i )-link = A( pos )-link; A( pos )-age = temp; A( pos )-link = ptr; 八、写出Floyd求最短路径的算法，并要求能求出具体路径及路径长。Algorithm Floydfor( i = 1; i = n; i+ )for( j = 1; j = n; j+ )A( i, j ) = Cost( i, j );If( i != j & A( i, j ) )Path( i, j ) = i j ;for ( k = 1; k = n; k+ )for( i = 1; i = n; i+ )for（j=1;i=n;j+） if( A( i, k ) + A( k, j ) A( i, j ) ) A( i, j ) = A( i, k ) + A( k, j );Path( i, j ) = path( i, k )path( k, j );九、修改Dijkstra求最短路径的算法，使其能求出具体路径及路径长。/ 出发点为节点1。/ Cost( i, j )为两个节点间的路径长，当没有路径时为无穷大，当i = j时为0。/ Dist为路径长。Path为路径，用从节点1出发经过的节点的集合表示。/ S指示是否为最短路径经过点。algorithm Dijstrate( Cost, Dist, Path, S ) for( i = 1; i = n; i+ ) S( i ) = 0; Dist( i ) = Cost( 1, i ); Path( i ) = 1 v ; S( 1 ) = 1; for( i = 2; i = n; i+ ) /大循环 u = 无穷大; for ( i = 2; i = n; i+ )/作用是找出到出发点1距离最短的点i if( Dist( i ) u & S( i ) =0 )u = Dist( i ); v = i;/加入循环后的结果是v=3 S( v ) = 1;/则把S（3）=1，接下去要做的是修改目前的距离和以及路径 for( j = 1; j Dist( v ) + cost( v, j ) )/该点没有访问过 Dist( j ) = Dist( v ) + cost( v, j );Path( j ) = Path( v ) j ;/把该点加入路径集合中 十、设有一小段小写英文字母存储在以t为根节点的二叉树种，设计算法依照字母出现的频率从大到小的顺序输出这段文字中的a,b,c,z这26个字母。其中，t的形式为：struct node char data; node *l,*u; algorithm字母频率 new letter 1 : 26 ; new count 1: 26 ; 将letter数组中的元素依次赋值为a,b,c,.,z; 将count数组中的元素全部初始化为0； Travel( T ) if( T != null ) out = T - data; for( i = 1; i LChild ); call Travel( T -RChild ); for( i = 1; i = n-1; i+ ) pos = i; for( j = i + 1; j = n; j+ ) if( count j count pos ) pos = j; if( pos != i ) temp1 = count i , temp2 = letter i ; count i = count pos , letter i = letter pos ; count pos = temp1; letter pos = temp2; 十一、进行一次人口普查，资料为name和age，对资料进行分类，并按某一年龄输出资料（按人数多少的顺序输出）。与第七题相似。十二、给定一个由几个正整数组成的向量V 1 : n 。试设计算法，将V 1 : n 的元素移到R 1 : n 内，使R 1 = R 2 = R n / 2 ，R n = R n-1 = R n / 2 + 1 ，即R中的元素呈现中间大两边小的均匀分布状态。例如：V = 11，5，3，9，7，1 ，则R = 1，5，9，11，7，3 。algorithm sort( V, R ) W = V;将向量W中元素从小到大排列;index = falsefor( i = 1; i = n; i+ )index = !( index );if( index )R ( i + 1 ) / 2 = W i ；elseR n + 1 - i / 2 = W i ；十三、稀疏矩阵的转置算法，算法时间为O( n ) + O( t )：algorithm转置算法( A, B ) m = A 0, 1 ;n = A 0, 2 ;t = A 0, 3 ;B 0, 1 = n;B 0, 2 = m;B 0, 3 = t;for( int i = 0; i = t; i+ )num i = 0;pos i = 0;for( int i = 1; i = t; i+ ) num A i 1 +;pos 1 = 1;for( int i = 2; i = n; i+ ) pos i = pos i - 1 + num i - 1 ;for( int i = 1; i 0 )k = 1;for( i = 1; i = n; i+ )for( j = 1; j lchild );if( t-lchild=null )t-lchild = pr;t-lflag = 1;if( pr != null & pr-r = null )pr-rchild = t;pr-rflag = 1;pr = t;S( t-r );十六、快速排序：/ V为表名，l和h分别为要排序文件的第一个和最后一个标号。algorithm Quick_Sort( V, l, h ) if( l h )i = l;j = h;temp = V( i );while( i j );while( i = V( j ) )j-;if( i j )V( i ) = V ( j );i +;while( i = temp )i+;if( i data );visited v = 1;while( v-next != null )v = v-next;if( visited v = 0 )Call DFS( v );十八、无向图的广度遍历，其中无向图用邻接链表表示。Algorithm BFS( v ) / v为出发点。printf( v-data );visited v = 1;AddQ( Q, v );while( !isEmpty( Q ) )w = OutQ( Q );while( w-next != null )w = w-next;if( visited w = 0 )visited w = 1;AddQ( Q, w );十九、用克鲁斯卡尔方法构造最小代价树：algorithm KMST( G, T, n ) / 图G，树T，节点数n。E( T ) = null / 将边的集合E( T )先置为空。for( i = 1; i top = 0; / 新建一个空栈。for( i = 1; i count = 0 ) Push( S, i );/把所有入度为0的点入栈for( i = 1; i top != 0 ) /如果栈不是空Pop( s, i );/出栈printf( i );/访问该点ptr = i-link;/继续下一个点while( ptr != null ) /当下一个点也不是空的时候k = ptr-data;/删除一条有i发出的边k-count-;/同时k的入度减1if( k-count = 0 )/此时入度为0的话Push( S, k );/再入栈ptr = ptr-link;elseprintf(“网中有回路”);break;二十二、回答问题： 1. 算法、数据结构和程序有什么