计算机软件基础.doc

C语言基础C语言有哪些数据类型？整型、实型、字符型。为什么程序中的变量使用前必须先定义？C程序用到的变量都必须进行定义，即事先定义其类型。变量一经定义，系统就给分配存储空间，以存放相应常量。算法和程序的区别是什么？算法是有穷的，程序是无穷的;算法和程序的描述方法不一样，程序是用计算机语言描述的；算法一般不可执行，程序可以执行算法是解决问题的方法、步骤和思路。C语言源程序的文件的后缀是C，经过编译后生成文件的后缀是 OBJ，经过连接后生成文件的后缀是exe。C程序开发的四个步骤依次是提出问题、构造模型、选择方法、编写程序。数学式sin35+xcos60的C语言表达式为Sin(35*pi/180)+cos(60*pi/180)(其中pi=3.14)。表达式3*9%2+9%2*5的值为6。表达式6.0*(1/2)的值为0。程序就是算法用某种计算机语言表示出来的。一个变量同时只能被定义为一种类型。程序中用到的所有变量必须先定义后使用。变量代表内存中具有特定属性的一个存储单元，它用来存放也就是变量的值，这些值是可以改变的。一个字符型变量只能存储一个字符若a是实型变量，在执行了a=5后，a仍为实型变量。若a和b类型相同，在执行了a=b后，b中仍保留原值。编制C语言程序并上机运行的一般过程是编辑、编译、连接、运行。C语言规定用户标识符由字母、数字和下划线组成，且第一个字符必须是字母或下划线。begin不是C语言的关键字。顺序结构、选择结构和循环结构的程序设计请写出switch语句的一般格式及注意事项。一般格式： Switch（表达式） case常量表达式1：语句组1；break；Case常量表达式2：语句组2；break；Case常量表达式n：语句组n；break；Default：语句组n+1；1switch中表达式可以是任意类型，常用的是字符或整型。2每个常量表达式的值不能相同。3语句组可以为任意语句。4break可以省略，然后执行完本组语句后紧接着执行其后的i+1组语句。5多个case可以用一组执行语句。6break的作用是跳出switch，执行switch下面的语句。 试说明while语句和do-while语句的异同：二者相同点在于都可以进行次数确定的循环体的次数。不同点在于do-while现执行循环中的语句，然后再判断条件是否为真，若为真则继续循环；若为假则终止循环。因此，do-while循环至少要执行一次循环语句。而while则是先判断条件后执行循环体简述for语句的执行过程及注意事项：计算机表达式1表达式2非0？执行语句s计算机表达式3循环结束，执行下面的语句注意事项：for语句中的3个表达式可以省略但后面的分号不能省略。试说明continue语句和break语句的作用及区别：break的功能是跳出本层循环（对多层循环而言），接着执行下面的语句。continue语句的作用是执行continue时，循环体中continue下面的语句都不执行，重新进行循环判断以决定是否继续进行下次循环。Break和continue的区别在于：continue只结束本次循环重新进行下次循环判断，而break结束整个循环。结构化程序的三种基本结构包括顺序结构、选择结构和循环结构。C语言提供的选择结构语句有if和switch。有一段程序为：while（表达式）语句1；语句2；当表达式的值为非零时，执行语句1 ；当表达式的值为零值时执行语句2。do-while语句中while后的表达式的值最终应达到0值，才能正常退出循环。在C语言程序的循环体内，若遇到break语句时，则立即停止当前循环；若遇到continue语句时，则结束本次循环，进行下一次循环判断。C语言中，唯一的三目运算符是？：，而&.&.是双目运算符。C语言中，运算符优先级最高的是&.&.。C语言中，是关系运算符。C语言中，要求运算符数据必须是整型的运算符是%C语言中，语句x=！a=b；的执行的次序是先执行！，再执行=，再执行=。3个关于C语言的结论：可以用while语句实现的循环一定可以用for语句实现；可以用for语句实现的循环一定可以用while语句实现；可以用do-while语句实现的循环一定可以用while语句实现。C语言程序中，continue语句只能用于循环结构。C语言中，if和switch语句属于程序流程控制语句。C语言中，语句while后一对圆括号中的表达式可以是任意表达式。C语言中，关于scanf（）函数正确的叙述是利用scanf（）函数可以给变量提供数据。C语言中，与语句while（！E）括号中的表达式含义等价的是E=0.C语言程序中，for循环语句中的表达式2为一非零常数且循环体内无break语句及goto语句，则循环体的执行次数为无穷次。设i是int型变量，f是float型变量，用下面的语句给这两个变量输入值：scanf（“i=%d，f=%f”，&i，&f）；为了把100和765.12分别赋给i和f，正确的输入为i=100，f=765.12回车。设变量m，n，a，b，c，d均为0，执行（m=a=b）（n=c=d）后，m，n的值是1，0。设变量m，n，a，b，c，d均为1，执行“（m=ab）&（n=ab）”后m，n的值是0，1。若x和y都是int型变量，x=100，y=200，且有下面的程序片段：printf（“%d”，（x，y）；此程序片段的输出结果是200。当执行以下程序段时x=-1；dox=x*xwhile（！x）；循环体将执行一次。执行语句：for（i=1；i+4；）后；变量i的值是5。数组若定义“int a5；”，试说明引用a、a0和&a1的含义。a代表数组名，a0代表数组的第一个元素，&a1代表数组第二个元素的地址。在C语言数值表示中，a“a”相同吗？不同，a表示一个字符，而“a” 表示一个字符串。已知：int s23；试说明数组s在内存存储所占的字节数。因为变量的数据类型int在使用内存空间的时候一个数据占用2个字节的存储空间。而数组s23内部有6个整型的数据，所以一共要占用12个字节。C语言默认数组下标的下界是0。在C语言中，二维数组元素在内存中的存放顺序是按行存入。若定义了一个二维数组int34；且改数组的起始地址为1000，则元素a13的地址为1014。（一个整型变量占两个字节）已知：char str15；str数组的最后一个元素是str14。字符串的结束标志是0。二维数组的最小行、列下标是0。一维数组定义中表示数组长度的表达式可以是常量和符号常量，不得包含变量。同一数组中的所有元素所占字节数相同。引用数组元素越界时，编译时不检测“下标出界”是否越界。C语言中用字符数组存放字符串类型。Static char str=“ok”；与static char c=ok；不一样。在定义int a54；之后，对a的引用正确的是a00。在执行char str10=“China0”；strlen（str）的结果是5。在C语言中，引用数组元素时，其数组下标的数据类型允许是整型常量或整型表达式。字符串“That”小于字符串“The”。若有说明：inta4=1,2,3,4,5,6,7,8,9,10,11,12；，则数组第一维的大小为3。若数组a有m列，则aij之前的数组元素个数为i*m+j。函数调用：strcat（strcpy（str1，str2），str3）的功能是将串str2复制到串str1中后再将串str3连接到串str1之后。函数写出函数定义、函数声明、函数调用的一般格式及注意事项。函数定义：函数类型 函数名（形式参数列表）说明部分；语句部分；函数声明：其形式为：函数类型 函数名（）；函数的调用：主要函数通过传递一定的信息来使用被调函数的功能。（1）无返回值的函数调用格式（2）有返回值的函数调用格式在调用一个函数之前，应考虑哪些问题？若被调函数和主调函数在一个编译单位中，在书写顺序上被调函数在主调函数之前出现；或者被调函数虽然在主调函数之后出现，而被调函数的数据类型是整数型或字符型，可不对被调函数加以说明。试说明实参和形参的关系。形参和实参的关系总的来说是一一对应的关系。具体是：1个数相等2顺序一致3类型相符（或实参可以给形参正确的赋值）。从用户角度看，函数分为库函数和用户自定义函数。若有一下函数调用语句：func（a+b，（x，y），fun（n+k，d，（a，b）；在此函数调用语句中实现的个数是3。输入带空格的字符串时，应该用gets（）函数。求字符串长度的函数是strlen（）。可以用strcpy函数将字符串复制到字符数组中。变量的作用域是指变量的有效范围，在作用域内可以引用该变量。按作用域变量可以分为全局变量和局部变量。从函数形式看，函数分为无参函数和有参函数。函数的返回值是通过函数体中的return语句获得。若被调函数定义为void类型，则被调函数不带回任何值。调用函数在被调用函数之前时，一般要对被调用函数做函数声明。C语言规定不能嵌套定义函数，但可以嵌套调用函数。在不同的函数中定义的变量名若相同，则他们表示不同的变量。C语言总是从主函数开始执行。实参和形参占用不同的存储单元。一个函数可以没有形式参数。在进行函数调用时，被调函数的形参被分配在内存的动态数据区。若函数类型和return语句中表达式的值不一致，则以函数类型为准。函数的嵌套调用是指调用一个函数的过程中，又调用另一个函数。若以数组元素作为函数的实参，则实参向形参传送的是数组元素的值。C语言中，当用数组名做形参时，形参数组改变可以使实参数组随之改变。允许函数递归调用。函数形参的作用范围只是局限于所定义的函数内。函数调用时，只能把实参的值传送给形参，形参的值不能传送给实参。一个函数返回值的类型是由定义函数时指定的函数类型决定的。一个C源程序至少包括一个函数，主函数和其他函数不可调用。C语言程序的简单语句必须用分号（；）做为语句的结束符。函数定义的形参可以有一个、多个，也可以没有。C语言程序总是从main函数开始执行。C语言是由主函数和若干子函数构成。在一个源程序文件中定义的全局变量的有效范围是从定义变量的位置开始到源程序文件结束。指针对指针变量做自加1操作后，一定增加一个字节吗？为什么？不一定，和数据的类型有关。分析“*”在定义指针和引用指针变量时有什么不同？定义语句中“p”前面的“*”是说明p的类型是指针变量。而除定义语句外的其他语句中出现的“*p”里的“*”是对p所指变量的引用，即代表它指向的变量。试说明指针变量可以进行哪些运算。指针变量可以进行赋值和简单的加减运算。指针又可称为地址。专门的指针运算符是&和*。只有先定义一个指针型变量，才能将另一个变量的地址存放在改变量中。若指针变量p指向整型变量i，则i变量又可用*p表示。若指针变量p指向float型数组a10，且a的首地址为1000，则执行p+3后，p应该指向地址为1012单元。malloc（）函数用来在内存中分配一个指定长度的存储空间。C语言中，若int a5，i，*p=a；，则与&ai等价的指针表示是p+i，与ai等价的指针表示是*（p+i）。已知：int a=1,3,5,7,9，*ip=a；表达式*ip+2的值是5.已定义的一个指针变量可以存放定义相同类型的内存单元的地址。指针变量作为形参时，实参也可以是不同类型的指针变量。指针说明时指定的数据类型是指针变量指向的存储单元的数据类型。指针变量赋值时，赋的值是一般变量而不是地址。指针变量的值是可以改变的。变量的指针是变量存储单元的地址。指针变量是指存放变量地址的变量。若有定义：int x，*pb；则正确的赋值表达式是pb=&x。若有定义：char ch；（1）使指针p可以指向变量ch的定义语句是char *p=&ch。（2）使指针p指向变量ch的赋值语句是p=&ch。（3）通过指针p给变量ch读入字符的scanf函数调用语句是scanf（“%c”，p）。（4）通过指针p给变量ch赋字符的语句是ch=*p。（5）通过指针p输出ch中字符的语句是putchar（*p）。数据结构概论通常将数据结构表示为一个二元组（D，R），其中D和R分别表示什么？D代表数据节点的集合，R是D上的关系。什么是数据的逻辑结构？什么是数据的物理结构？一般情况下，两者之间有什么关系？这种关系是如何反映的？数据的逻辑结构是数据间的外在联系（与计算机存储无关）；数据的物理结构是数据在计算机中的存储表示，也称数据的存储结构。一般情况下，二者的关系是相互运算，如何把逻辑结构数据存入计算机；如何把机内表示的数据取出来参加运算，在逻辑结构和物理结构之间转换以及其他运算过程中，数据如何组织才能即节省时间，又节约空间，更重要的是机内表示的数据取出来后要完全体现其逻辑结构。什么是算法？算法与程序有何区别与联系？算法就是解决特定问题的的方法。而程序是通过某种语言将算法的具体实现手段。算法的时间复杂度仅与问题的规模相关吗？不是。算法的时间复杂度还与算法中的语句频度、数据的状态等因素有关。数据结构是指逻辑结构和物理结构两种，通常是指逻辑结构。选择合适的存储结构，通常考虑的指标有逻辑结构和数据类型两个因素。数据结构按节点间的关系，可分为4种，分别是集合、线性结构、树形结构和网状结构。线性结构反映节点间的关系是一对一的，树形结构反映节点间的关系是一对多的，网状结构反映节点间的关系是多对多的。数据的逻辑结构是数据之间的外在联系（与计算机存储无关）。数据的逻辑结构与数据元素的相对位置相关。数据的逻辑结构与其所含数据元素的个数无关。数据元素之间的逻辑关系与存储单元的相邻关系无关。在数据结构中，从逻辑上可以把数据结构分为线性结构和非线性结构。数据结构是一门研究操作对象以及他们之间的关系和运算等的学科。算法分析的目的是分析算法的效率以求改进。算法分析的两个主要方面是空间复杂性和时间复杂性。计算机算法是指可读性科文档性。线性表简述单链表、循环单链表、循环双链表的结构特点。（1）单链表的结构：由节点构成，每个节点有两个成员：数据域和指针域。单链表的特点：每个节点都只有一个指向直接后继节点的指针，最后一个节点的指针域为空，单链表是只有一个链域的链表。（2）循环单链表结构：由节点构成，每个节点有两个成员：数据域和指针域。循环单链表特点：链表中最后一个节点的指针域指向头结点，整个链表形成一个环。（3）循环双链表结构：由节点构成，每个节点包括三个域：数据域、前驱指针域和后继指针域。循环双链表特点：节点的next指针域指向后继节点，prior指针域指向前驱节点。简述顺序表和链表的主要优、缺点及适用范围。（1）顺序表用一组地址连续的存储单元存放线性表中的数据，表中元素的物理关系和逻辑关系是一致的。表中元素可以随机存取，但在程序执行之前必须给出空间长度，容易造成空间浪费或者空间不够的情况。链表用一组任意的存储单元存储线性表的数据元素，利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素。存储空间动态分配，不会产生溢出，但空间利用率低，节点访问需要从表头开始依次访问。（2）顺序表适用于经常进行查找运算的数据，或者对数据量事先固定的问题。链表适用于经常进行插入、删除等数据量变化较大的动态问题。比较线性表的顺序存储结构与链式存储结构存储空间开销大小，并说明理由。顺序存储结构存储空间开销小，链式存储结构存储空间开销大。存储空间开销大小可以用存储密度衡量。存储密度=节点数据域所占空间/节点所占空间。节点存储密度越大，空间利用率越高，则存储空间开销越小。顺序存储结构每个节点占一个空间，即存储数据域的空间，而链式存储结构每个节点所占两个空间，即存储数据域的空间和存储指针域的空间。对于线性表的顺序存储结构与链式存储而言，若线性表的长度基本稳定，且很少进行插入与删除操作，但要尽快地存取表中的数据元素，则应该选择哪种存储结构？为什么？应该选择顺序存储结构。因为线性表的长度基本稳定，可以预先进行分配，且要求尽快地存取表中的数据元素，而顺序表中元素可以随机存取。若频繁地对线性表进行插入与删除操作，该线性表应该采取什么存储结构？为什么？应该选择链式存储结构。对线性表进行插入与删除操作，顺序表需要大量移动元素，而链表只需要修改需要相应的指针域就可以了。有哪些链表可仅由一个尾指针来唯一确定，即从尾指针出发能访问到链表上任意一个节点？循环单链表和循环双链表。在单链表、循环单链表和循环双链表中，若仅知道指针p指向某节点，不知道头指针，能否将节点*p从相应的链表中删除？若可以，且时间复杂度各为多少？单链表不可以。循环单链表、循环双链表可以。单链表时间复杂度O（n），循环单链表时间复杂度O（n），循环双链表时间复杂度O（1）。线性表的两种存储结构分别为顺序表结构和链表结构。访问一个线性表中具有定值元素的时间复杂度为O（n）。对于一个为n的顺序存储的线性表，在表头插入元素的时间复杂性为O（n），在表尾插入元素的时间复杂性为O（1）。线性表是一个有限序列，可以为空。一个线性表是n个数据元素的有限序列。在一个顺序表的表尾插入一个元素的时间复杂度为O（1）。在一个单链表中，若要在p所指向的节点插入一个新节点，则需要相继修改2个指针域的值。在一个单链表中，若要在p所指向的节点插入一个新节点，则此算法的时间复杂度为O（n）。在一个带头节点的双向循环链表中，若要在p所指向的节点之前插入一个新节点，则需要相继修改4个指针域的值。线性结构的特征：有且只有 一个根节点，它无前件；有且只有一个终端节点，它无后件；除根节点和终端节点以外，其他节点有且只有一个前件，也有且只有一个后件。在单链表中，增加头节点的目的是方便运算的实现。用链表表示线性表的优点是便于插入和删除操作。在线性表的顺序存储中，元素之间的逻辑关系是通过物理存储位置决定的；在线性表的链接存储中，元素之间的逻辑关系是通过链域的指针值决定的。在双向链表中，每个节点包含两个指针域，一个指向前驱结点，另一个指向后继结点。在线性表的顺序存储中，若一个元素的下标为i，则它的前驱元素的下标为i-1，后继元素的下标为i+1。一个线性表中，第一个元素的存储地址是100，每个元素的长度是2，则第五个元素的地址是108。栈、队列和数组简述栈和队列的相同点和不同点。相同点：都是存储数据的线性表。不同点： 栈为LIFO（后进线出）线性表，插入、删除操作均在表尾进行。队列为FIFO（先进先出）线性表，插入在表尾进行、删除在表头进行。若进栈的数据元素序列依次为1、2、3、4、5、6，能否得到4、3、5、6、1、2和1、3、5、4、2、6的出栈列？并举例说明为什么不能得到或如何得到。（1）不能得到4、3、5、6、1、2的出栈列。最先出栈的是4，则此时栈底元素为最先入栈的1、然后依次向上为2、3、4、4、3出栈后；5入栈，再出栈；6入栈，再出栈；这时得到序列为4、3、5、6；这时栈顶元素为2,2出栈后，1才能出栈，所以1不可能先于2出栈，因此不能得到此序列。（2）可以得到1、3、5、4、2、6的出栈列。1入栈，再出栈，1为第一个出栈元素；2入栈；3入栈，再出栈，3为第二个出栈元素；4、5一次入栈，此时，栈底元素为1,5成为栈顶元素，则5出栈，然后4出栈，然后2出栈；之后6入栈，再出栈；因此可以得到此出栈序列。向一个顺序栈加一个元素时，首先若栈不满栈顶指针上移，然后将元素加入到栈顶位置。从一个顺序栈删除元素时，首先判断栈是否为空，然后若不为空栈顶指针下移。一个顺序栈存储于一维数组am中，栈顶指针用top表示，当栈顶指针等于-1时，则为空栈；栈顶指针等于m-1时，则为满栈。在一个链栈中，若栈顶指针等于NULL则为空栈；在一个链队列中，若队首指针与队尾指针的值相同，则表示该队为空队列。在具有n个单元的循环队列中，队满时共有n-1个元素。已知二维数组A1：41:6采用行序为主序方式存储，每个元素占用三个存储单元，并且A2,2的存储地址为1200，元素A3,4的存储地址是1224。若将n阶三对角矩阵A按照行序为主序方式将所有非零元素存放在一个一维数组B中，则该三对角矩阵在B中共有3n-2个数据元素。队列只能在队首进行删除，在队尾进行插入。队列属于数据结构中存取受限制的线性结构。链栈的所有操作都限制在表头进行，所有没有必要设置头结点。链栈与顺序栈相比，通常不会出现栈满的情况。顺序栈是线性结构，链栈也是线性结构。一个栈的入栈序列是a、b、c、d、e，则栈的不可能的输出序列是dceab。向顺序栈中压入新元素时，应当先移动栈顶指针，再存入元素。当利用大小为N的数组顺序存储一个栈时，假定用top=N表示栈空，则向这个栈插入一个元素时，首先应执行top语句修改top指针。假定利用数组aN顺序存储一个栈，用top表示栈顶指针，top=-1表示栈空，并已知栈未满，当元素x进栈时所执行的操作为a+top=x。假定一个链式栈的栈顶指针用top表示，每个节点的结构为datanext，所进行的指针操作为top=top-next。一个队列的入队顺序是1、2、3、4，则队列的输出顺序是1、2、3、4。假定一个顺序队列的队首和队尾指针分别用front和rear表示，则判断对空的条件为front=rear。判定一个循环队列Q（最多元素为m0）为空的条件是Q-front=Q-rear。判定一个循环队列Q（最多元素为m0）为队满的条件是Q-front=（Q-rear+1）%m。若将n阶对称矩阵A按照行序为主序方式将包括主对角线在内的下三角形的所有元素存放在一个一维数组B中，则该对称矩阵在B中占用了n（n+1）/2个数组元素。判定一个栈（最多元素为m）为空的条件是ST-top=-1。判定一个栈ST（最多元素为m）为栈满的条件是ST-top=m-1。栈结构通常采用的两种存储结构是顺序线性结构和链式存储结构。栈和队列的共同点是只允许在端点处插入和删除元素。在一个链队中，假设f和r分别为队首和队尾指针，则插入s所指节点的运算是r-next=s；r=s。在一个链队中，假设f和r分别为队首和队尾指针，则删除一个节点的运算是f=f-next。树和二叉树指出树和二叉树的主要区别树无序而二叉树有序。对于一颗具有n个节点的树，该树中所有节点的度数之和为n-1。在一棵树中根节点没有前驱节点，其余每个节点有且仅有一个直接前驱节点，可以有任意多个直接后继节点。在一颗二叉树中，假定度为2的节点数为5个，度为1的节点数为6个，则叶子节点数为6个。具有40个节点的完全二叉树，它的高度为6。已知8个数据元素为34,76,45,18,26,54，92,65，按照依次插入节点的方法生成一颗二叉排序树，则该树的深度为5。二叉树的5种基本形态是空二叉树、只有根的二叉树、只有左子树的二叉树、只有右子树的二叉树、左右子树都有的二叉树。若由3、6、8、12、10作为叶子节点的值生成一颗哈夫曼树，则该树的高度为4，带权路径长度为87。任意一颗有n个节点的二叉树，若它有m个叶子节点，则二叉树上度为1的节点个数为n-2m+1。若一颗二叉树叶子树为n，在该二叉树中，左、右子树皆非空的节点个数为n-1。由一个二叉树的先序和中序或后序和中序遍历结果可以唯一地确定一颗二叉树。二叉树中，任何一个节点的度数为2。一颗哈夫曼树中存在度为1的节点。树的先根遍历顺序与其对应的二叉树的先根遍历序列相同。按二叉树的定义，具有3个节点的二叉树有5种。已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是cedba。树中所有节点的度等于所有节点个数加-1。在一颗度为3的树中，度为3的节点数为2个，度为2的节点数为1个，度为1 的节点数为2个，则度为0的节点数为6个。已知某二叉树的后序遍历序列是DACBE，中序遍历序列是DEBAC，则它的前序遍历序列是EDBAC。在一颗二叉树上第8层的节点数最多是128。在深度为5的满二叉树中，叶子节点的个数为16。设一颗完全二叉树共有500个节点，则在该二叉树中有250个叶子节点。若某二叉树的前序是stuwv，中序是uwtvs，那么后序为wuvts。任何一颗二叉树的叶子节点在先序、中序和后序遍历序列中的相对依次不发生改变。若T2是由有序树T转化而来的二叉树，那么T中节点的前序就是T2中节点的前序。若T2是由有序树T转化而来的二叉树，那么T中节点的后序就是T2中节点的中序。树最适合用来表示元素之间具有分支层次关系的数据。深度为5的二叉树至多有31个节点。在一非空二叉树的中序遍历序列中，根节点的右边只有右子树上的所有节点。在一颗具有n个节点的二叉树中，所有节点的空子树个数等于n+1。某二叉树的前序序列和后序序列正好相反，则该二叉树一定是高度等于其节点数的二叉树。在有n个叶子节点的哈夫曼树中，其节点总数为2n-1。从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是树可以采用二叉树的存储结构并利用二叉树的已有算法解决树的有关问题。图一个带权联通图的最小生成树是否唯一？说明在什么情况下最小生成树有可能不唯一。一个带权联通图的最小生成树不一定唯一。若是图中同时存在若干个权值相同的边，选择不同点起点，可得到不同的最小生成树，但这些最小生成树边上权值之和均为定值。用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否有关？与边的条数是否有关？矩阵元素的个数与顶点个数有关，顶点个数为n，则矩阵元素的个数为n*n；矩阵元素的个数与边的条数无关。简述图的连通分量和图的生成树的区别。图的连通分量是这个图的最大连通子图，就是其本身。图的生成树是含有该连通图的全部顶点的有关极小连通子图。在一个图中，所有顶点的度数之和等于所有边数的2倍。n顶点的无向连通图至少n-1条边，至多n（n-1）/2条边。在利用表示有向图的邻接矩阵中，对第i行的元素进行累加，可得到第i个顶点的出度，而对第j列元素进行累加，可得到第j个顶点的入度。一个连通图的生成树是该图的最小连通子图。若这个连通图有n个顶点，则它的生成树有n-1条边。一个无向图有n个顶点和e条边，则所有顶点的度的和为2e。当无向图G的顶点度数的最大值大于或等于顶点数的2倍时，G至少有一条回路。已知一个图的邻接矩阵表示，删除所有从第i个节点出发的边的方法是将第i行的值置0。在图的邻接表示存储结构上执行深度优先遍历类似于二叉树的先序遍历。在图的邻接表示存储结构上执行广度优先遍历类似于二叉树的按层次遍历。一个图的邻接矩阵表示法是唯一的，而邻接表表示法是不唯一的。在一个具有n个顶点的有向完全图中，所含的边数为n（n-1）。n个顶点的连通图中边的条数至少为n-1条。表示图常用的存储结构为邻接矩阵和邻接链表。对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边节点分别有e个和2e个。在一个图中，所有定点的度数之和等于所有边数的两倍。在一个有向图中，所有定点的入度之和等于所有顶点的出度之和的1倍。一个有n个顶点的无向图最多有n（n-1）/2条边。常用的查找方法假定对节点个数n=50的有序表进行折半查找，则对应的折半查找判定树高度为6，最后一层的节点个数为19。对于节点个数为n的线性表，若顺序查找关键字为k的节点，则成功查找的时间复杂度为O（n）。在插入排序和选择排序中，若原始数据已基本有序，则较适合选用插入排序。在最好情况下，对于具有n个元素的正序序列，若采用冒泡排序，所需的比较次数为n-1。对有序表进行折半查找的过程可用判定树来描述，其判定树的形态只取决于元素的输入顺序。顺序查找法适合于存储结构为顺序存储或链接存储的线性表。对节点个数为18的顺序存储有序表，若采用折半查找，则查找第15个节点的成功查找次数为3。在一颗深度为h的具有n个节点的二叉排序树中，查找所有节点的最大查找次数为h。设有一个长度为100的已排好序的表，用折半查找进行查找，若查找不成功，至少比较7次。从一颗二叉排序树中查找一个元素时，若元素的值等于根节点的值，则表明查找成功，若元素的值小于根节点的值，则继续向左子树查找，若元素的值大于根节点的值，则继续向右子树查找。二分查找的存储结构仅限于顺序存储结构，且是有序。采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（n+1）/2。二叉排序树上的查找长度不仅与节点个数有关，也与二叉排序树的树形有关。常用的排序方法什么是内部排序？什么是外部排序？内部排序是指待排序的数据量不大，在内存中进行的排序。外部排序是指待排序的数据量较大，内存中一次放不下，借助于外存进行排序。学习过的排序方法中哪些排序方法是稳定的？直接插入排序、冒泡排序是稳定的。排序的目的是为了对已排序的数据元素进行查找运算。若对一组记录（46、79、56、38、40、80、35、50、74）进行直接插入排序，当把第8个记录插入到前面已排序的有序表时，为寻找插入位置比较5次。具有24个记录的序列，采用冒泡排序最少的比较次数是23次。在对n个元素进行直接插入排序的过程中，最多需要进行n-1趟。在对n个元素进行直接冒泡排序的过程中，至少需要n-1趟完成。排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列的一端的方法，称为选择排序。冒泡排序算法在最好的情况下的元素交换次数为0。在所有排序方法中，关键字比较的次数与记录的初始排列次序