计算机软件基础(一)复习资料

《计算机软件基础(一)复习资料》由会员分享，可在线阅读，更多相关《计算机软件基础(一)复习资料（10页珍藏版）》请在装配图网上搜索。

1、计算机软件基础（一）复习资料二计算机软件基础复习参考题一、基本概念题1、算法的描述方法很多，常用的有： 自然语言 、类语言、流程图、N-S结构图 等。2、常用流程图符号: 起止框 处理框 输入输出框 判断框 流程指示线3、程序设计的关键在于设计出一个好的 算法 。4、程序中/*/表示注释，其位置可以放在程序的任何地方 。5、算法和程序的主要区别是什么？答：1、算法是有穷的，而程序是无穷的。2、算法是不可执行的，程序是可以执行的。3、算法和程序的描述方法不一样。程序是用计算机语言目来描述的。6、计算机的解题基本过程。答：提出问题-构造模型-选择方法-编写程序-上机调试、运行-分析结果7、用C语言

2、编写的程序,计算机是直接执行的这样的程序称为源程序。8、源程序必须翻译成机器语言，这一工作由 “编译系统” 来完成。9、扩展名代表的文件。C -源文件 。OBJ -目标文件 。EXE -执行文件10、C语言的数据结构是以 数据类型 的形式描述出来的。11、三种基本的数据类型： 整型、实型、字符型 12、C语言中的常量有 整型、实型、字符型、字符串 13、整型常量一般占 2 字节。实型常量一般占 4 字节。所有的转义字符在内存中均占 1 字节。字符串的长度为为串中字符的个数，但在内存中所占的字节应比长度多1 14、实型常量的两种书写形式 浮点实数 和 定点实数 。15、字符型常量有用单括号括起来

3、的单个字符和C语言还允许以一个“”开头的控制字符。16、转义字符有哪些，及其含义。答：n 换一行 o 字符串结束 f 换一页 反斜杠字符 单撇号字符 ” 双撇号字符ddd 1到3位八进制所代表的字符xhh 1到2位十六进制所代表的字符17、字符串常量是用 双撇号 括起来的若干字符序列。18、为了识别各个变量,每个变量都有一个名字,这个名字为标识符 。19、变量名只能由字母,下划线、数字 构成，只能下划线和字母开头。20、标识符的注意事项答：1、C语言中大写字母和小写字母是两个不同字符。2、标识符命名不得为C语言中称为保留字的专用名词。21、变量必须遵守 先定义、后使用 原则。22、变量的表示方

4、法答：整型变量：基本整型：int 长整型 Long 短整型 short 实型变量：单精度实型：float 双精度实型 double字符型变量：char23、表达式书写的注意事项。答：1、所有字符必须写在同一行上。2、乘号“*”不能省3、所有括号为圆括号，且配对4、函数的自变量用圆括号括起来，三角函数的自变量用弧度。24、C语言提供了两种类型转换的方法：答1隐式转换2显式转换25、两整数相除其商为整数,%两边的运算对象为整数,其余数也为整数。26、 = 为C语言的赋值运算符。27、在定义时 不能连续 给变量a,b,c赋初值。28、自加、自减运算符只能用于 变量 ，不能用于常量和表达式。29、单独

5、出现的i+或+i的作用相当于 i=i+1 ，但和其他量进行运算时就不同。30、逗号表达式的执行过程是： 从左到右计算每个表达式，逗号表达式的值为最后一个表达式值，即表达式n的值 。31、程序的三种基本结构：答1、顺序结构2、循环结构3、选择结构32、 ； 作为语句的结束标志。33、字符输入输出函数。 getchar putchar34、格式输入输出函数 scanf printf35、格式控制字符。%d 整型格式 %c字符型格式 %f实型格式36、scanf函数使用注意事项答：1、sanf 函数输入实型数据时不能规定精度2、scanf函数中，格式控制字符串后面对应的是“变量地址”，而不是变量名。

6、 3、“%c”格式输入时只能接收一个字符。37、C语言提供的关系运算符有哪些。 = 、=、=-=、!=-&-|42、if语句有几种形式？答单分支语句、双分支语句、嵌套的if 语句43、if与else配对，else总是 与最近的 if配对。44、 ？： 是C语言中唯一一个三目运算符。45、if语句只有两个分支可供选择， switch 是一种实现多分支结构。46、循环结构有三种形式答：while循环、do while循环、for循环47、for语句的书写形式for(表达式1；表达式2表达式3)循环语句S48、 表达式非0才循环 ，是三种循环的共同之处。49、break与cantinue的区别在于：

7、continue只结束本次循环重新进行下次循环判断，而break结束整个循环。50、if与循环结构，不得交叉 可以 并列 ，也可以 内嵌 。51、数组的命名规则答：1、数组名的命名规则同变量名.2、数组元素下标从0开始，最大值为长度减1。3、常量表达式可以为常量和符号常量，不得包含变量。4、数组名后面不能是圆括号。52、数组元素在引用时，下标不得 超界 。53、二维数组在内存中的排列顺序是 按行 存入的。54、在定义数组时，若给出了全部元素值，则第一维的长度可以不写。55、字符数组中的一个元素存放 一个字节 空间。26、常见的字符串函数。字符输入函数gets 字符输出函数puts 长度strl

8、en 字符串连接函数strcat27、字符大小的比较 数字字符大写字母小字字母28、用预编译命令“#include”将用的函数有关信息包括到用户程序中，位置应放在程序开头，且命令结尾不得有“；”。29、C语言规定，不能在一个函数内部再定义其他函数，即C语言不允许函数的嵌套定义。函数的首部结尾结没有“；”。30、一个完整的C程序可由1个主函数main组成，或由1个主函数和若干个子函数构成。31、程序的执行总是从主函数开始并在主函数中结束。32、C语言中数据传递方式有四种；单向值传递方式、地址传递方式、返囬值传递方式、全局变量传递方式。33、一个变量的作用域是指该变量在程序中的有效范围。34、C语

9、言中访问地址的方式有直接存取方式和间接存取方式。35、int*p 说明p是一个指向整型的指针变量，在p的存储空间中可以存放一个整型变量的地址。36、C语言有两个专门的指针运算符&和*，它们都是单目运算符。37、C语言规定，数组名是数组的首地址，也即元素X038、用指针表示一个字符串分两步：答：1、先定义一个指向字符型的指针。2、让该指针指向某一字符串，也就是说将一个串的首地址赋给一个指针变量。39、“.” 是C语言中的成员运算符，它的优先级最高。41、结构变量所占用的存储空间是 所有成员所占空间之和 。42、数据 我们把计算机加工的对象叫数据 。43、数据组织的三个层次 数据、数据节点、数据项

10、。44、数据结构研究的主要内容归纳起来有三点答：1、数据的罗辑结构。2数据的物理结构3定义在数据的逻辑结构上，而实现在物理结构上的运算。45、数据的逻辑结构分两类： 线性结构和非线性结构 。46、数据的物理结构是数据在计算机内的存储表示也称存储结构。47、数据的物理结构可分两类,顺序存储结构和非顺序存储结构。48、数据的逻辑结构和物理结构之间的相互运算是通过算法 来实现的。49、一个算法的时间复杂度是求解问题的算法所耗时间的程度 。50、常见的时间复杂度以及它们之间的关系由小到大依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（n log2n）、平方阶O（n2）、立

11、方阶O（n3）、指数阶O（2n）等。51、同时间复杂度一样，算法的空间复杂度粗略的来讲是 算法消耗空间的程度。52、空间复杂度为O（1），即所耗辅助空间与问题的规模无关。53、同一线性表中的 数据节点 具有相同的属性。54、线性表的存储结构有两种：顺序存储结构、链式存储结构55、可以看出线性表的这种顺序存储结构使得 线性表中逻辑上相邻的数据节点在物理上也相邻。56、线性表中数据节点在一连续空间中存放，所以很容易计算出各节点存储地址，其地址为：Loc(ai)=Loc(a0)+i*d (0in-1)57、顺序表上顺序查找成功的平均查找次数为 （ 表长+1）/2 58、在线性表中插入一个数据节点的平

12、均需移动线性表中一半节点。59、插入运算的时间复杂度与n有关。O（n）= T（n）60、线性表中删除一个节点，约平均需移动线性表中一半节点 。61、单链表中每个节点有两个成员： 数据域和指针域 。62、单链表只能沿链从前向后访问表中节点,无法找到某节点前面的其他节点.而循环单链表可以通过任一点 来访问表中的其他节点。63、若经常进行的运算为查找运算，以 顺序存储 为宜。64、若经常进行的运算为插入、删除运算，以链式存储 为宜。65、顺序存储结构在程序执行之前必须给出空间长度，对数据量事先固定的问题用顺序存储为好。66、顺序存储 空间利用率 高，而链式相应少一些。67、栈是一种 先进后出 的线性

13、表。68、栈也有顺序存储结构和链式存储结构，分别称为顺序栈和链栈。69、进栈和退栈的运算：答：进栈有以下步骤1）、先判断栈是否已满，若满，则进行上溢处理，否则进行2）。2）、栈顶指针上移1个节点。3）将X加入到top所指位置。退栈有以下步骤：1）、检查栈是否为空，若栈空，则进行下溢处理，否则进行2）。2）保留被删元素到变量X中。3）栈顶指针下移1个节点。70、队列是一种 先进先出 的线性表。71、入队和出队的运算 答：入队运算：1）、先判断队列满吗？若满则退出；否则进行第二步；2）、队尾指针后移一个节点位置。3）、在队尾指针的位置加入X。出队运算：1）、判断队列为空？若空则退出；否则进行第二步

14、。2）、保留队头元素内容到X变量中。3）、队头指针后移1个节点位置。72、计算机系统用牺牲一个空间的办法来解决当front=rear时，既是循环队列为空，又是循环队列为满这一矛盾的。73、循环队列空的条件是：front=rear 满的条件是：front=（rear+1）%m74、循环队列中的元素个数为：（rear- front + m）%m75、求元素Ai,j的地址一般形式为： 数组首地址+Ai,j元素前已存入元素的个数*各元素的字节数。76、所谓的压缩存储是指对零元素不分配空间,相同元素只分配一个空间。77、三对角阵公式：已知i和j，求k=2i+j已知k，求i=(k+1)/3向下取整已知k，

15、求j=k-2*i78、下三角阵公式：已知i和j，求k=i(i+1)/2+j (ij)79、上三角阵公式：已知i和j，求k=i(2n-i+1)/2+j-i (ij) 80、对称阵公式：可按下三角阵公式或上三角阵公式储存81、树的有关名词：节点的度：节点的孩子称为节点的度。树的度：树中节点最大的度为该树的度。叶子节点：度为0的点称为叶子节点。双亲节点：一个节点的双亲节点是这个节点的父亲节点。树的高度：树的层数为树的高度。82、树和二叉树的区别是：树不能是空的，但二叉树可以是空的 树是无序的，而二叉树则是有序的83、二叉树的几个性质是：、二叉树的第i层上，最多有2i-1个结点、深度为k的二叉树上最多

16、有2k-1个结点、二叉树上n0=n2+1、具有2k-1个结点的二叉树是滿二叉树、滿二叉树的最下层自右至左连续缺n个结点的二叉树为完全二叉树、完全二叉树上它的左孩子为2i(当2in)，右孩子为2i+1(2i+1n), 当i1根为i/2取整，当i=1根为i、完全二叉树的深度为log2n取整+184、一棵有1000个结点的完全二叉树其n0=500,n1=1,n2=499,h=1085、n个结点的二叉树共有2n个指针域，其中n-1为孩子指针域n+1为空指针域86、二叉树的三种基本遍历方法：先序遍历、后序遍历和中序遍历。87、树的储存结构有：双亲表示法、孩子链表示法和孩子兄弟链表示法三种88、哈夫曼树的

17、性质：答：1）、给定权值的哈夫曼树不唯一；2）权值越大的节点离根节点就越近。3）、哈夫曼树中无度为1的节点。4）、哈夫曼树节点总个数n=2x叶子节点个数-1=2x权值个数-1=2n0-1。89、哈夫曼树是一棵带权路径长度总和最小的二叉树90、哈夫曼树的应用是：分类判定树和哈夫曼树91、图G是由顶点集合V和边集合E组成，记为G=(V，E)，图有有向图和无向图两种。91、对有向完全图其边数e=n(n-1)；对无向完全图其边数为e=n(n-1)/2 图中顶点与度的关系为：e=图中各顶点度数和的一半92、图的储存结构有：邻接矩阵和邻接表两种，无向图和完全有向图的邻接矩阵是：一个对称矩阵93、有向图的邻

18、接矩阵中，有e个非0节点，n 2-e个0节点；无向图的邻接矩阵中，有2e个非0节点，n 2-2e个0节点；94、有向图的邻接表中，有e个表节点，n +e个节点；无向图的邻接矩阵中，有2e个表节点，n +2e个节点；95、图的遍历有：深度优先遍历和广度优先遍历两种，并在邻接矩阵下两种遍历都是从最小顶点序号开始的；96、一个图的生成树只有n个顶点和n-1条边，可通过深度优先遍历和广度优先遍历得到图的生成树97、最小生成树是指图中各边权值最小的生成树，构造最小的生成树的算法有普里姆算法和克鲁斯卡尔算法两种98、拓扑排序的前提条件是：AOV网中不存在回路99、常用的查找方法有：顺序查找、折半查找和二叉

19、排序树上的查找三种100、顺序查找的时间复杂度为：O（n），折半查找的平均查找长度为：ASL=log2 (n+1)-1，但只限于顺序储存的有序表同，二叉排序树上的查找的平均查找长度也是ASL=log2 (n+1)-1，但二叉排序树是一种动态储存结构，进行插入删除操作比较方便，而折半查找采用的是静态储存结构，进行插入删除操作时要移动表中的元素。101、对二叉排序树进行中序遍历的结果是：一个递增序列102、根据排序文件所处位置的不同，可将排序分为内部排序和外部排序两大类。103、内部排序的时间主要用在关键字的比较和交换上，外部排序的时间主要用在外存的访问次数。104、常用的排序方法有：直接插入排序

20、、冒泡排序和直接选择排序三种，105、排序方法的性能指标有：时间复杂度；空间复杂度；稳定性106、接插入排序的时间复杂度：O(n2) ，空间复杂度: O(1)，是一种稳定的排序方法；冒泡排序的时间复杂度：O(n2) ，空间复杂度: O(1) ，是一种稳定的排序方法，直接选择排序的时间复杂度：O(n2) ，空间复杂度: O(1)，是一种不稳定的排序方法；107、软件程序文挡数据，它是一种逻辑产品，可不断修改完善其功能108、软件危机是指在软件的开发和维护过程中遇到的问题得不到解决，积累起来形成尖锐的矛盾，导致了软件危机109、软件工程是指采用工程的概念、原理、技术和方法来开发和维护软件110、软

21、件工程的三个要素是：方法、工具和过程111、软件工程有：七条基本原理112、软件开发的模型有：瀑布型、原型模型和螺旋模型三种113、瀑布型模型分三个阶段八个步骤来开发软件。三个阶段是：计划、开发和维护，八个步骤是：问题定义、可行性研究、需求分析、总体设计、详细设计、编码、测试、运行与维护114、原型模型是在用户的参与下仅从满足基本需求入手，快速构筑系统原型，经过反复试用改进，最终建立满足用户需求的新系统115、螺旋模型是一种风险驱动模型。它将瀑布模型与原型模型结合起来，加入了风险分析，从而弥补了前两种模型的不足.116、软件生存周期由软件定义、软件开发和软件维护三个时期组成。117、结构化分析

22、方法是面向数据流进行需求分析的方法（SA），使用数据流图DFD和数据字典DD构成系统的逻辑模型，适用于数据处理类型的软件定义。118、需求分析阶段的结果是：软件的需求规格说明书。包括一套分层数据流图；数据字典加工小说明119、软件设计包括：总体设计和详细设计两部分120、软件设计采用：结构化设计方法（SD），结构化设计的原理包括：模块化抽象信息隐藏和局部化模块独立性：即模块的块间联系要小（耦合）和块内联系要大（内聚）121、结构化设计是面向数据流的设计方法，数据流有两种：变换型数据流事务型数据流122、结构化程序设计的基本思想：坚持模块化，自顶向下求精原则采用顺序、选择和循环三种基本程序控制结

23、构构造程序保证每个模块单入口、单出口提倡好的程序设计风格123、良好的程序设计风格需遵循以下准则：答：节俭化、模块化、简单化、结构化、文档化、格式化。124、详细设计的工具有：图形工具（程序流程图、盒图（NS）问题分析图（PAD）表格工具（判定树和判定表）过程设计语言（PDL）125、软件测试的目的：通过执行程序证明软件中存在的错误126、查找错误的过程叫测试，而纠正错误的过程叫调试127、软件测试的基本原则 答：1）、尽早地、不断地进行软件测试；2）、设计测试用例时，要给出测试的预期结果。3）、开发小组和测试小组分开。4）、要设计非法输入的测试用期。5）、在对程序修改后要进行回归测试。6）、

24、程序中尚未发现的错误的数量往往与在该段程序中已发现的错误的数量成正比。128、软件测试的步骤 答：1）单元测试2）集成测试3）确定测试4）系统测试。129、软件测试的方法：黒盒法（从软件功能上进行测试）白盒法（采用逻辑覆盖方式对软件进行测试）130、白盒法的逻辑覆盖分为：语句覆盖、判定覆盖、条件覆盖、判定/条件覆盖、条件组合覆盖和路径覆盖六种131、黒盒法采用等价类法、边界值分析法和错误推测法进行软件测试132、软件测试常以黒盒法为主，白盒法为辅133、需要进行软件维护的原因 答：1）、改正程序中的错误和缺陷。2）、改进设计以适应新的软、硬件环境。3）、增加新的应用范围。134、软件维护工作的

25、分类 答：1）、改正性维护；2）、适应性维护；3）、完善性维护；4）、预防性维护。二、C语言基本题1、判断哪个错误 ( B )A、 while (2); 语句; B、do语句; while (0) C、for (; 0 ;) 语句; D、语句;2、哪个保留字不正确？B）、if B、Char C、float D、default 3、以下哪个结果为。（）、3%5 B、3/5.0 C、3/5 D、354、以下哪个表达式不正确？（）、3E1.0 B、1.0E3 C、.2E D、3E-25、以下哪个是字符常量？（）、“” B、x10 C、oa D、.a、设a, b, c, d分别为char , int

26、, float , double 问 a+b*c/d最后的结果为什么类型？ 答：double 型、int n，i ; 以下哪个错误（） 、n = ( i-1 ) B、n = n+ C、i = (n+1)+ D、n= i6 ) printf (*) 的结果是多少？（*）、for ( k = 2 ; +k 0) & (i4) ; i+, j-); 循环几次？答：4次11、int i =10，j = 10 ; printf (i=%d,j= %dn ,-i ; j-) ，输出结果i , j 为多少？ 答： i = 9 , j = 1012、程序：int x = 2; do printf (%d, x

27、 -); while （! ( -x)）；输出结果是多少？ 答：2，013、以下程序输出结果是多少？#include main() int i=1,j=3; printf(%d,i+); int i=0;i+=j*2;printf(%d,%d,i,j); printf(%d,%d,i,j); 答： 1,6,3,2,314、 以下程序段输出是多少？main ( ) int x=2 , y =-1, z = 2; if (xy) z=2; if (y10 & x 50) x +; if (x/3) x+, break ; else continue ; printf (%dn , x ); 答：

28、输出为 1316. main ( ) int k , m = 0 ; for ( k = 0; k 2; k + + ) m + + ; if ( m %2) continue ; m + + ; print f ( m = %dn , m ) ; 输出结果 m = 3 17. 完成填空输出1000以内能被3整除，且个位为6的所有整数， main ( ) int i , m ; for (i = 0 ; i =0 )if (xmax ) max =x ; scanf (%f ,& x); printf (n max =%f, min = %f max ,min ); 19、char a =12

29、3 ,b = 1, 2, 3 以下哪个正确? ( D ) A a3 是不可知的任意字符 B 数组 a, b 的长度相等 C b3 为 0 D 数组 a 长度大于 b 20. char s = 1230 的长度 为 5 21. main ( ) int i , x=10 , a10 ,b 3 for (i=0, i=0 ; i- -) , b i = a i*(i+1) for (i=0; i3; i+ ) x + = bi *2, printf ( %dn x) ; 求输出: 2622. main ( ) int a2 2, i , j; for ( i=0 ; i2; i+) for ( j

30、=0 ; j2; i+) ai j = i+j printf (%d a i j 结果为 0 1 1 2 23. main ( ) char s1 = abcdabdABCD, s2 20 int k=0, j=0 ; while (s1k! =A) s2 j+ =s1 k+; s2 j = 0 pintf ( %sn, s2 ); 结果为：abcdabd24. 指针main ( )int m , n =2 , *p= &m;完成 m=n 功能的语句是 ( B ) A m =*p B *p = * &n ; C m =& n ; 格式 D m= & p ; 25.int x 8 =5,4,3,

31、2,1, *p = x ;则*p+6 = 11 .26.int x8=1,2,3,4,5,6 ,*p =x 则值为5的表达式 (B) A *P +5 =6 B *(p+4) C *p +5 =5 D p+4 27.以下程序为递归函数 int f ( int n ) if (n = =1) return (1); else return ( f (n-1) +1 ); main ( ) int i, j=0; for ( i=1; i5 ; i+) j+ = f ( i) ; printf ( %dn j); 结果为 10 28 计算 xn 的程序。 double f (double x, in

32、t n) int i ; double z=1.0 ; if ( n= 0 ) return (1. 0 ); else for ( i=1 i=n; i+) z =z * x ; return ( z) ; 29. void f ( int *a, int b ) b *a = *a+6; main ( ) int x=1, y 5= 1,2,3,4,5, *p =y; f ( &x , p); printf ( %d/n , (p+x) ); 结果 为b 1 = y 1 =730. int b=1 int f (int * a) b+ =a ; return (b) ; main ( )

33、int a =2, b=3; a+ = f (& b); printf ( %d n ,a ); 输出结果为 631. 下列程序运行后的输出结果是 DCBAEF void fun(char *p1, int n) char t, *p2; p2=p1+n-1; while (p1p2) t=*p1; *p1+=*p2; *p2-=t; main() char *p=ABCDEF; fun(p,4); printf(%sn,p); 32. 下列程序的运行结果是： ABCDEFFEDCBA #define sqstack_maxsize 20typedef struct sqstack char

34、datasqstack_maxsize; int top; SqStackTp;main() SqStackTp sq; int i; char ch;InitStack(&sq)for (ch=A; ch=A+5; ch+) Push(&sq, ch); printf(%c,ch); while(!EmptyStack(sq) Pop(&sq, &ch); printf(%c,ch); printf(n); 31. 在n行10列的二维整数组a中按先行后列的顺序出栈第一次出现的整数 x 用形参返回共行列下标，若二维数位没有 x，则行列下标均为 -1 void fun (int a 10, in

35、t x, int n, int *y, int *c) int k ; flag =0; *y = *c =-1; for (k =0; k n; k+) for (j=0 ; j10 ; j+) if ( ak j = =x) *y = k; *c= j ; flag =1; break ; if ( flag ) break; return; 32. 输入一个长整型形正整数，将其转换成对应的八进制整数的字符串，然后输出main ( ) char s 10, * p ; while (x! = 0L ) long x; y = x %8 ; int y ; * p = y + 0; p =

36、s + 7 ; p - -; * ( p+1) =0; x = x/ 8 ; scanf ( % ld & x ) ; p + +; printf (%sn , p ) ;33. 输入 10整型正整数，存入一维数组中，求其中所有素数之和输出，除1和本身外不能被整除的 main ( ) int x 10 , s=0 , k , j; for ( k=0 ; k10; k+ ) scanf ( %d , & x k); for (k=0; k10; k+) if ( x k = =1) continue; flag =1; for ( j =2; j x k ; j+) if ( xk%j = =

37、 0) flag = 0 ; break; if ( flag = = 1) s += x k ; printf ( %dn s) ; 34、设计结构型数组，包含学生的编号、姓名、4科成绩。编程序，输入100名学生信息存入所设计结构型数组，然后输出有成绩不及格（60分）的学生的编号、姓名和不及格的课程数。struct long num; char name10; float score4; s100, *p;main( ) int k, n; float x; for (p=s; pnum, p-name); for (k=0; kscorek=x; for (p=s; ps+100; p+)

38、 n=0; for (k=0; kscorek0) printf( %ld, %s, %dn, p-num, p-name, n); 35.给定n个元素建立一个有序的单链表的时间复杂度， O（n）36.在带头结点的循环链表中将头指针改设为尾指针（read）后，其第一个结点和尾结点的存储位置分别是 read -next- next 和read37在一个具有n个结点的有序顺序表中插入一个新结点，并仍然有序的时间复杂度 O（n2 ） 38.带头结点的单链表head为空的判点条件是head - next= = NULL39.下列程序中功能是（对顺序表进行插入运算）Void insert _Sq lis

39、t (Sqlist L, datatype x , int i) ; if ( L.last = = maxsize ) error (表满) ； if ( (iL.last +1) ) error (非法位置) ； for ( j=L.last; ji; j - - ) L.data j =L.data j-1 ； data i = x ;L.last = L.last +1 ; 40.以下为计算带头结点单链表的表长int length_lklist (lklist head) lklist p = head ; j=0 ;While (p-next ! = NULL )p = p-next

40、 ; j + + ; return (j) ; 41.以知单链表L中的结点，按值非递减有序排列的，试写一算法，将值为 x的结点插入 L中，使得L仍然有序，Void CR_lk list (lklist *l ,datatype x ) lklist *q, *p,*s;q = l ; p=q -next ;While ( ( p! = NULL ) & (p- data next ; s=( lklist *) mallo (sizeof(lklist) ) ; s- data = x ;s - next = q - next ; q - next = s ; 42.入队列的操作 Void E

41、n_Queve (lqueptrTP * lp ,datatype,x ) lqueueTP * P ; P = (lqueueTP * P ) malloc ( size of (lqueueTP ) ); P - data = x; p- next = NULL ; ( lp- rear ) - next =p ; lp - rear = p ; 43.在以下栈的运算中，不是加工运算的是，( D )A lnitstack (s ) B push ( s, x ) C pop ( s ) D Enpth ( s ) 44.循环队列的队满条件为 （ sq. rear + 1 ）% maxsiz

42、e = = sq . front 45.循环队列的对空条件为 Sq . rear = sq .front .47.改C语言数组 Date m+1 作为循环队列 SQ 的存储空间，frone 为对头指针，rear 为对尾指针，则执行出队操作的语句为 front = ( front+1 ) % (m+1)48.一个队列的输入列序 1,2 ,3,4 则队列的输出序列是 1,2,3,4 49.下列程序的功能是什么？ 借助栈将一个带头结点的单链表倒置void list(LinklistTP *head) LStackTP ls;LinklistTP *p; DataType x; InitStack(&

43、ls); p=head-next; while(p!=NULL) Push (&ls, p-data); p=p-next; p=head-next; While( ! EmptyStack(&ls) Pop(&ls,&x); p-data=x; p=p-next; 50. 深度为6的二叉树最多有 （63 ） 结点 2k-152 树是适合用来表示元素之间具有分支层次关系的数据，53 试编写算法交换二叉树中所有结点上的左、右子树， void exch_tree ( hitreptr ,BT ) ( if (BT ! = NULL ) exch_tree ( BT - lchild ) exch_

44、tree ( BT - rchild ) P= BT -lchild ; BT - lchild =BT -rchild ; BT - rchild =p ; 54 以二叉链表作为存储结构，试编写求二叉树中叶子树的算法 int leaf_count ( bitreptr T) if (T = = NULL ) leaf =0 ; else if ( ( T - lchild = = NULL )& ( T - rchild = NULL) ) leaf = 1; else L= leaf_count ( T- lchild ); R = leafcount ( T- rchild; ); le

45、af = L+ R ; return (leaf ); 55. 以下程序是实现图的深度优先搜索算法 Dfs (GraphTP g , int v) ArcNodeTP * p ; printf ( % d ,v ); visited v =1 p = g.adjlist v .firstarc ; while ( p ! =NULL ) if ( !visited p - adjvex ) Dfs(g, p-adjvex ); p= p -nextarc ; 56. 二分查找法适用于存储结构为顺序存储的且按关键字排好序的线性表57. 用顺序查找法对具有 n个结点的线性表，查找的时间复杂量级为

46、O (n)58. 用二分查找法对具有 n个结点的线性表，查找的时间复杂量级为 O (log2n)59.以下程序是在有序表中用二分查找法，查找关键值等于 K 的元素 int binsearch ( sqtable r, kegtype k) low =1, hig = r.n ; while ( low = hig ) mid = (low +hig ) / 2 ; if (k= = r.wtem mid key) return (mid ); else if (k key = = k) ruturn ( T); else if (T - key k) return (search_bst(T

47、- lchild ; k) ) ; else return (search-bst(T - rchild ; k) ) ; 61、冒泡法:#define N 4Void bustor(int x ,int n)int i, j, m, k ; for (i=1 , i=n-1 ; i+) k=1 ;for (j=1 ; jx j+1) m = x j; x j = x j+1; x j+1 = m; k = 0; if ( k = 1) break; 2、直接选择排序#define N 6void sestor (int x , int n) int i, j, k, m ;for ( i =

48、 1 ; i = n-1; i+) k = i ; for (j = i+1; j= n ; j+) if (x j x k ) k = j ; if (k ! = i) m = x i ; x i = x k ; x k = m; main ( ) int a N+1 , i ; for ( i = 1 ; i = N ; i +) scanf (“%d” , &a i ); sestor (a, N );for ( i=1; i = N ; i+) printf (“%d”, a i );printf (“n”); 4 某学校一年级有n个级，每班有m名学生。编制C语言程序，从键盘输入每个学

49、生1门课的成绩，计算并输出年级最高分及全体学生的平均分。源程序：main() int m,n,i,j; float hf,pf,zf=0.0,amn; scanf(“%d,%d”,&m,&n); for (i=0im;i+) for (j=0jn;j+) anf(“%f”,amn); hf=a00; for (i=0;im;i+) for (j=0;jn;j+) if (hfaij) hf=aij; zf=zf+aij; Pf=zf/(m*n);Prntf(“hf=%f,pf=%f”,hf,pf);11.输出19002000年中所有的闰年。每输出3个年号换一行。（判断闰年的条件为下面二者之一：

50、能被4整除，但不能被100整除。或者能被400整除。）源程序：#include”stdio.h” main() int i,n;for(n=0,i=1900;i=2000;i+)if(i%4=0&i%100!=0|i%400=0) printf(“%d ”,i);n+; if(n%3=0) printf(“n”); 10.三个整数a、b、c，由键盘输入，输出其中最大的一个数。源程序：main() int a,b,c;printf(“请输入三个整数：”);scanf(“%d,%d,%d”,&a,&b,&c);if(ab) if(bc) printf(“max=%dn”,c); else printf(“max=%dn”,b);else if(ac) printf(“max=%dn”,c); elseprintf(“max=%dn”,a); 34 编写c语言程序实现：从键盘上输入10个学生某门课的成绩，计算平均成绩，统计并输出所有高于平均分的学生成绩及人数。main()int i，n=0；fl