第二章线性表
一、填空题
1.通常将含n(n>=0)个结点的线性表表示成(a1，a2,……a n)。a1称为______结点，a n称为______结点，i称为a i在线性表中的________。对任意一对相邻结点a i、a i┼1(1<=i 2.线性表的基本特征是:若表非空，则除起始结点没有直接______外，其他结点有且仅有一个直接______;除终端结点没有直接______外，其它结点有且仅有一个直接______. 3.线性表所含结点的个数称为线性表的______，简称______. 4.表长为O的线性表称为______ 5.线性表典型的基本运算包括:______、______、______、______、______、______等六种。 6.顺序表的特点是______。 7.顺序表的类型定义可经编译转换为机器级。假定每个datatype类型的变量占用k(k>=1)个内存单元，其中，b是顺序表的第一个存储结点的第一个单元的内存地址，那么，第i个结点a i的存储地址为______。 8.以下为顺序表的插入运算，分析算法，请在______处填上正确的语句。 void insert_sqlist(sqlist L，datatype x，int i) /*将X插入到顺序表L的第i个位置，假设表L不会溢出*/ { if( L.length == L.list size) error(“表满”)； if(i<0||i>L.length)error(“非法位置”); for(j=L.length-1;j>=i+1;j--)______; L.elem[i]=x; L.length++; } 9.对于顺序表的插入算法insert_sqlist来说，若以结点移动为标准操作，则插入算法的最坏时间复杂度为________，平均时间复杂度为________。 10.以下为顺序表的删除运算，分析算法，请在________处填上正确的语句。 void delete_sqlist(sqlist L,int i) /*删除顺序表L中的第i个位置上的结点，假设表L为非空表*/ {if(i<0||i>L.length)error(“非法位置”)； for(j=i+1;j=L.length-1;j++)________; L.length--; } 11.对于顺序表的删除算法delete_sqlist来说，若以结点移动为标准操作，最坏情况时间复杂度为________，平均时间复杂度为________。 12.以下为顺序表的查找运算，分析算法，请在________处填上正确的语句。 int locate_sqlist(sqlist L,datatype X) /*在顺序表L中查找第一个值等于X的结点。若找到返回该结点序号；否则返回0*/ { ________; while(i<=L.length&&L.elem[i-1]!=X) { if (________) return (i); else i++; } return(0); } 13.线性表的常见链式存储结构有________、________和________。 14.单链表表示法的基本思想是用________表示结点间的逻辑关系。 15.为了便于实现各种运算，通常在单链表的第一个结点之前增设一个类型相同的结点，称为________。 16.在单链表中，表结点中的第一个和最后一个分别称为________和________。头结点的数据域可以不存储________，也可以存放一个________或________。 17.以下为求单链表表长的运算，分析算法，请在________处填上正确的语句。 int ListLength(LinkList L) /*求单链表L的长度*/ { ________; j=0; while (p->next!=NULL) { ________________; j++; } return (j); /*返回表长*/ } 18.以下为单链表定位运算，分析算法，请在____处填上正确的语句。 Status LocatePos(LinkList L,int i, Link &p) { p=L;j=0; while (________________) { p=p->next; j++; } if(i==j) return(p); else return(NULL); } 19．循环链表与单链表的区别仅仅在于其尾结点的链域值不是_________，而是一个指向_________的指针。 20．在单链表中若在每个结点中增加一个指针域,所含指针指向前驱结点，这样构成的链表中有两个方向不同的链，称为______。 二、单项选择题 1.线性表中的一个结点代表一个（） ①数据元素②数据项③数据④数据结构 2．顺序表是线性表的（） ①链式存储结构②顺序存储结构③索引存储结构④散列存储结构 3.对于顺序表，以下说法错误的是（） ①顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址 ②顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列 ③顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻 ④顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中 4.对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（）为基本操作 ①条件判断②结点移动 ③算术表达式④赋值语句 5.对于顺序表的优缺点，以下说法错误的是（） ①无需为表示结点间的逻辑关系而增加额外的存储空间 ②可以方便地随机存取表中的任一结点 ③插人和删除运算较方便 ④由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配) ⑤容易造成一部分空间长期闲置而得不到充分利用 6.单链表的一个存储结点包含（） ①数据域或指针域 ②指针域或链域 ③指针域和链域 ④数据域和链域 7.对于单链表表示法，以下说法错误的是（） ①数据域用于存储线性表的一个数据元素 ②指针域或链域用于存放一个指向本结点所含数据元素的直接后继所在结点的指针 ③所有数据通过指针的链接而组织成单链表 ④NULL称为空指针，它不指向任何结点，只起标志作用 8．设指针P指向双链表的某一结点，则双链表结构的对称性可用（）式来刻画 ①p->prior->next->==p->next->next ②p->prior->prior->==p->next->prior ③p->prior->next->==p->next->prior ④p->next->next==p->prior->prior 9.以下说法错误的是（） ①对循环链表来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表 ②对单链表来说，只有从头结点开始才能扫描表中全部结点 ③双链表的特点是找结点的前趋和后继都很容易 ④对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。 10．在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置分别是（） ①rear和rear->next->next ②rear->next 和rear ③rear->next->next和rear ④rear和rear->next 2.11 设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。 Status OrderListInsert-sq(SqList va, ElemType x) { //将x插入到递增有序的顺序表va中，插入后va仍然递增有序(算法1) if (va.length==va.listsize){ newbase=(ElemType *)realloc(va.elem,(va.listsize+LISTINCREMENT)*sizeof(ElemType)); if (!newbase) exit(OVERFLOW); va.elem=newbase; va.listsize+=LISTINCREMENT; }//当前存储空间已满，增加分配空间 if (!va.length) {va.elem[0]=x; ++va.length; return OK;} q=&(va.elem[0]); while (*q<=x)&&(q<=&(va.elem[va.length-1])) ++q; //查找插入位置 for (p=&(va.elem[va.length-1]); p>=q; --p) *(p+1)=*p; *q=x; ++va.length; return OK; }//OrderListInsert-sq Status OrderListInsert-sq(SqList va, ElemType x) { //将x插入到递增有序的顺序表va中，插入后va仍然递增有序(算法2) if (va.length==va.listsize){ newbase=(ElemType *)realloc(va.elem,(va.listsize+LISTINCREMENT)*sizeof(ElemType)); if (!newbase) exit(OVERFLOW); va.elem=newbase; va.listsize+=LISTINCREMENT; }//当前存储空间已满，增加分配空间 if (!va.length) {va.elem[0]=x; ++va.length; return OK;} p=&(va.elem[va.length-1]); while (P>=&(va.elem[0])&&*p>x) {*(p+1)=*p; --p;} *(p+1)=x; ++va.length; 第二章 矩阵及其运算 1 已知线性变换 ?????++=++=++=3 213321232113235322y y y x y y y x y y y x 求从变量x 1 x 2 x 3到变量y 1 y 2 y 3的线性变换 解 由已知 ? ??? ?????? ? ?=???? ??221321323513122y y y x x x 故 ???? ?????? ? ?=???? ??-3211 221323513122x x x y y y ? ??? ?????? ??----=321423736 947y y y ?????-+=-+=+--=3 21332123 211423736947x x x y x x x y x x x y 2 已知两个线性变换 ?????++=++-=+=321332123 11542322y y y x y y y x y y x ?????+-=+=+-=3 233122 11323z z y z z y z z y 求从z 1 z 2 z 3到x 1 x 2 x 3的线性变换 解 由已知 ???? ?????? ? ?-=???? ??221321514232102y y y x x x ??? ? ?????? ??--???? ??-=32131 010 2013514232102z z z ??? ? ?????? ??----=321161109412316z z z 所以有?????+--=+-=++-=3 21332123 2111610941236z z z x z z z x z z z x 3 设???? ??--=111111111A ??? ? ??--=150421321B 求3AB 2A 及A T B 解 ??? ? ??---???? ??--???? ??--=-1111111112150421321111111111323A AB ???? ??----=???? ??---???? ??-=2294201722213211111111120926508503 ??? ? ??-=???? ??--???? ??--=092650850150421321111111111B A T 4 计算下列乘积 (1)??? ? ?????? ??-127075321134 解 ???? ?????? ??-127075321134???? ???+?+??+?-+??+?+?=102775132)2(71112374??? ? ??=49635 (2)???? ??123)321( 解 ??? ? ??123)321((132231)(10) 第2章线性表 一选择题 1．下述哪一条是顺序存储结构的优点？（ A ） A．存储密度大 B．插入运算方便 C．删除运算方 便 D．可方便地用于各种逻辑结构的存储表示 2．下面关于线性表的叙述中，错误的是哪一个？（ B ）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具有n个（ C ）的有限序列（n>0）。 A．表元素 B．字符 C．数据元 素 D．数据项 E．信息项 4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。 AHA12GAGGAGAGGAFFFFAFAF A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A．单链表 B．仅有头指针的单循环链 表 C．双链表D．仅有尾指针的单循环链表 6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ D ）存储方式最节省运算时间。 AHA12GAGGAGAGGAFFFFAFAF A．单链表 B．双链表 C．单循环链 表 D．带头结点的双循环链表 8. 静态链表中指针表示的是（ BC ）. A．内存地址 B．数组下标 C．下一元素地址D．左、右孩子地址 9. 链表不具有的特点是（ C ） A．插入、删除不需要移动元素 B．可随机访问任一元素C．不必事先估计存储空间 D．所需空间与线性长度成正比 10. 下面的叙述不正确的是（ BC ） A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 AHA12GAGGAGAGGAFFFFAFAF 第2章数据库和表的创建 一、选择题 1．建立表的结构时，一个字段由（）组成。 A．字段名称 B.数据类型 C.字段属性 D.以上都是 2．Access2003中，表的字段数据类型中不包括（）。 A.文本型 B.数字型 C.窗口型 D.货币型 3．Access2003的表中，（）不可以定义为主键。 A.自动编号 B.单字段 C.多字段 D.OLE对象 4．可以设置“字段大小”属性的数据类型是（）。 A.备注 B.日期/时间 C.文本 D.上述皆可 5．在表的设计视图，不能完成的操作是（）。 A.修改字段的名称 B.删除一个字段 C.修改字段的属性 D.删除一条记录 6．关于主键，下列说法错误的是（）。 A.Access2003并不要求在每一个表中都必须包含一个主键。 B.在一个表中只能指定一个字段为主键。 C.在输入数据或对数据进行修改时，不能向主键的字段输入相同的值。 D.利用主键可以加快数据的查找速度。 7．如果一个字段在多数情况下取一个固定的值，可以将这个值设置成字段的（）。 A.关键字 B.默认值 C.有效性文本 D.输入掩码 二、填空题 1．是为了实现一定的目的按某种规则组织起来的数据的集合。 2．在Access2003中表有两种视图，即视图和视图。 3．如果一张数据表中含有“照片”字段，那么“照片”字段的数据类型应定义为。4．如果字段的取值只有两种可能，字段的数据类型应选用类型。 5．是数据表中其值能惟一标识一条记录的一个字段或多个字段组成的一个组合。6．如果字段的值只能是4位数字，则该字段的输入掩码的定义应为。 三、判断题 1．要使用数据库必须先打开数据库（） 2．“文件”→“关闭”菜单命令可退出Access 2003应用程序（） 3．最常用的创建表的方法是使用表设计器。（） 4．表设计视图中显示的是字段标题（） 5．在表的设计视图中也可以进行增加、删除、修改记录的操作。（） 6．要修改表的字段属性，只能在表的设计视图中进行。（） 7．文本类型的字段只能用于英文字母和汉字及其组合。（） 8．字段名称通常用于系统内部的引用，而字段标题通常用来显示给用户看。（）9．如果一个字段要保存照片，该字段的数据类型应被定义为“图像”类型。（）10．“有效性规则”用来防止非法数据输入到表中，对数据输入起着限定作用。（）四、简答题 1．创建数据库和表的方法有哪些？ 2．简述使用“表设计器”创建表的基本步骤？ 第一章行列式·1.1 二阶与三阶行列式 1.(单选题) 计算？A．; B．; C．; D．. 参考答案：A 2.(单选题) 行列式？A．3; B．4; C．5; D．6. 参考答案：B 3.(单选题) 计算行列式. A．12； B．18； C．24； D．26. 参考答案：B 4.(单选题) 计算行列式？A．2； B．3； C．0； D．. 第一章行列式·1.2 全排列及其逆序数 1.(单选题) 计算行列式？ A．2； B．3； C．； D．. 参考答案：C 2.(单选题) 计算行列式？ A．2； B．3； C．0； D．. 参考答案：D 第一章行列式·1.3 阶行列式的定义 1.(单选题) 利用行列式定义，计算n阶行列式：=? A．; B．; C．; D．. 参考答案：C 2.(单选题) 计算行列式展开式中，的系数。A．1, 4; B．1，-4; C．-1，4; D．-1，-4. 参考答案：B 第一章行列式·1.4 行列式的性质 1.(单选题) 计算行列式=？ A．-8; B．-7; C．-6; D．-5. 参考答案：B 2.(单选题) 计算行列式=？ A．130 ; B．140; C．150; D．160. 参考答案：D 3.(单选题) 四阶行列式的值等于多少？ A．； B．； C．； D．. 参考答案：D 4.(单选题) 行列式=？ A．； B．； C．； D．. 参考答案：B 5.(单选题) 已知，则？A．6m； B．-6m； C．12m； D．-12m. 参考答案：A 一章行列式·1.5 行列式按行（列）展开 1.(单选题) 设＝，则? A．15|A|; B．16|A|; C．17|A|; D．18|A|. 参考答案：D 第二章线性表 1、描述一下三个概念的区别：头指针，头结点，首元结点。并给予图示。 2、对于有头结点的单链表，分别写出定位成功时，实现下列定位语句序列。(1)定位到第i 个结点a i ； (2)定位到第i 个结点的前驱a i-1； (3)定位到尾结点； (4)定位到尾结点的前驱。 3、已知L 是有表头结点的单链表，且P 结点既不是首元结点，也不是尾结点，试写出实现下列功能的语句序列。 (1)在P 结点后插入S 结点；(2)在P 结点前插入S 结点；(3)在表首插入S 结点；(4)在表尾插入S 结点 . p=head; p=head; j=0; while ( p && jnext; j++;} p=head; j=0; while ( p && j 4、设计算法：在顺序表中删除值为e 的元素，删除成功，返回1；否则，返回0。 5、设计一个算法，将一个带头节点的数据域依次为a 1，a 2，…，a n （n ≥3）的单链表的所有节点逆置，即第一个节点的数据域变为a n ，…，最后一个节点的数据域为a 1。（注意：先用自然语言描述算法基本思想，然后用类C++语言描述） int Sqlist 第二章矩阵 一、知识点复习 1、矩阵的定义 由m n个数排列成的一个m行n列的表格，两边界以圆括号或方括号，就成为一个m n型矩阵。例如 2 -1 0 1 1 1 1 1 0 2 2 5 4 -2 9 3 3 3 -1 8 是一个45矩阵. 一个矩阵中的数称为它的元素,位于第i行第j列的数称为(i,j)位元素。 元素全为0的矩阵称为零矩阵,通常就记作0。 两个矩阵A和B相等(记作A=B)，是指它的行数相等，列数也相等(即它们的类型相同)，并且对应的元素都相等。 2、 n阶矩阵与几个特殊矩阵 行数和列数相等的矩阵称为方阵，行列数都为n的矩阵也常常叫做n阶矩阵。 n阶矩阵的从左上角到右下角的对角线称为主对角线。 下面列出几类常用的n阶矩阵,它们都是考试大纲中要求掌握的. 对角矩阵: 对角线外的的元素都为0的n阶矩阵. 单位矩阵: 对角线上的的元素都为1的对角矩阵,记作E(或I). 数量矩阵: 对角线上的的元素都等于一个常数c的对角矩阵,它就是c E. 上三角矩阵: 对角线下的的元素都为0的n阶矩阵. 下三角矩阵: 对角线上的的元素都为0的n阶矩阵. 对称矩阵: 满足A T=A矩阵，也就是对任何i,j,(i,j)位的元素和(j,i)位的元素总是相等的n阶矩阵. 反对称矩阵:满足A T=-A矩阵.也就是对任何i,j,(i,j)位的元素和(j ,i)位的元素之和总等于0的n阶矩阵.反对称矩阵对角线上的元素一定都是0.) 正交矩阵：若AA T=A T A=E，则称矩阵A是正交矩阵。 （1）A是正交矩阵?A T=A-1 （2）A是正交矩阵?2 A=1 阶梯形矩阵:一个矩阵称为阶梯形矩阵，如果满足: ①如果它有零行，则都出现在下面。 ②如果它有非零行，则每个非零行的第一个非0元素所在的列号自上而下严 格单调递增。 把阶梯形矩阵的每个非零行的第一个非0元素所在的位置称为台角。 每个矩阵都可以用初等行变换化为阶梯形矩阵，这种运算是在线性代数的各类 计算题中频繁运用的基本运算，必须十分熟练。 请注意：一个矩阵用初等行变换化得的阶梯形矩阵并不是唯一的，但是其非零 行数和台角位置是确定的。 3、矩阵的线形运算 （1）加(减)法:两个m n的矩阵A和B可以相加(减),得到的和(差)仍是m n 矩阵,记作A+B (A-B),运算法则为对应元素相加(减). （2）数乘: 一个m n的矩阵A与一个数c可以相乘,乘积仍为m n的矩阵, 记作c A,运算法则为A的每个元素乘c. 这两种运算统称为线性运算,它们满足以下规律: ①加法交换律:A+B=B+A. 2加法结合律:(A+B)+C=A+(B+C). ③加乘分配律:c(A+B)=c A+c B.(c+d)A=c A+d A. ④数乘结合律: c(d)A=(cd)A. ⑤ c A=0 c=0 或A=0. 4、矩阵乘法的定义和性质 （1）当矩阵A的列数和B的行数相等时,则A和B可以相乘,乘积记作AB. AB的行数和A相等,列数和B相等. AB的(i,j)位元素等于A的第i个行向量 和B的第j个列向量(维数相同)对应分量乘积之和. 第2章线性表习题解答 第2章习题 (2) 第2章习题 2.1若将顺序表中记录其长度的分量listlen改为指向最后一个元素的位置last，在实现各基本运算时需要做那些修改？ 【解】 //用线性表最后一个元素的下标last代替listLen实现顺序表 #define MAXLEN 100 typedef int elementType; typedef struct sllLast { elementType data[MAXLEN]; int last; }seqList; //初始化 void initialList(seqList &S) { https://www.doczj.com/doc/a815745238.html,st=-1; } //求表长度 int listLength(seqList S) { return https://www.doczj.com/doc/a815745238.html,st+1; } //按序号取元素 bool getElement(seqList S,int i,elementType &x) { if(i<1 || i>https://www.doczj.com/doc/a815745238.html,st+1) //i为元素编号，有效范围在https://www.doczj.com/doc/a815745238.html,st+1之间 return false; else { x=S.data[i-1]; return true; } } //查找元素x，成功：返回元素编号；失败：返回0 int listLocate(seqList S,elementType x) { int i; for(i=0;i<=https://www.doczj.com/doc/a815745238.html,st;i++) { if(S.data[i]==x) return i+1; //找到，转换为元素编号输出 } return 0; } //插入元素 int listInsert(seqList &S,elementType x, int i) 第一章 行列式 （√）1．若11 12 13 2122 23313233a a a a a a d a a a =，则13 1211 23222133 32 31 a a a a a a d a a a =. 2.互换行列式的任意两行，行列式值不变. （ ） 3.排列631254的逆序数是6. （ ） 4.对角行列式的值等于其所有对角元素的乘积． （ ） 5.分块对角阵的行列式等于对角线上各方块行列式之积．（ ） 6.设A 为3阶方阵，2A =，则 12 T A A =__________. 7.逆序数()21n τ= _____________. 8.排列32514的逆序数是： ． 9.排列631254的逆序(631254)t = 8 . 10.设四阶行列式1 11 222 43334 4 4 p a b c p a b c D p a b c p a b c = ,则第四列的代数余子式之和 = 0 . 11.设3312243,0311A t B ?-?? ? =≠ ? ?-?? 且AB=0,则t = 3 . 12.设a 、b 为实数，则当a =＿_＿且b =＿_＿时，01 0000 =--a b b a 13.== 3 4 3 3 3 2 3 1 242322214 3211 111 x x x x x x x x x x x x D __________________________. 14.设D 为一个三阶行列式，第三行元素分别为-1，2,3，其余子式分别为1,2,1，则D ____________=. 15.设 211 111 401 D - = - ， ij A为D中元素 ij a的代数余子式，则 313233 A A A ++=_ ______. 16.sin cos cos sin αα αα - =_____________. 17.001 020 00 n = _____________. 18.设 211 111 401 D - = - ， ij A为D中元素 ij a的代数余子式，则 313233 A A A ++=_ ______. 19．若D是n阶行列式，下列说法中错误的是（）． .A D与T D相等； .B若D中有两行元素成比例，则D等于零； .C若D中第i行除()j i,元外都为零，则D等于()j i,元与它的代数余子式的乘积；.D D的某一行元素与另一行的对应元素的余子式乘积之和为零． 20.行列式349 571 214 -的元素 23 a的代数余子式 23 A为（） A. 3 B.3- C.5 D.5- 21．方程 1 110 12 λλ λ λ - =的实根个数为（） A. 0 B. 1 .C 2 .D 3 22． 23.计算行列式 2111 1211 1121 1112 D=； 1 311 131 113 D=； 2 111 135 1925 D=； 1 411 141 114 D=； 第二章测试试题 班级：学号：姓名：成绩： 一、选择题（每小题5分） 1.线性表是( A )。 A一个有限序列，可以为空；B一个有限序列，不能为空； C一个无限序列，可以为空；D一个无序序列，不能为空。 2.用链表表示线性表的优点是（C）。 A便于随机存取 B花费的存储空间较顺序存储少 C便于插入和删除 D数据元素的物理顺序与逻辑顺序相同 3.某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( D )存储方式最节省运算时间。 A单链表 B双链表 C单循环链表 D带头结点的双循环链表 4.带头结点的单链表head为空的判定条件是（B ）。 A.head==NULL; B.head->next==NULL; C.head->next==head; D.head!=NULL; 5.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行（C ）。 A.s->next=p->next;p->next=s; B.p->next=s->next;s->next=p; C.q->next=s;s->next=p; D.p->next=s; s->next=q; 二、填空题（每小题5分） 1．给定有n个结点的向量，建立一个单链表的时间复杂度_______。建立一个有序单链表的时间复杂度_______。 2．从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较_____个结点。 3．在一个长度为n的线性表（采用顺序存储结构）中删除第i个元素(1≤i≤n)时，需向前移动____个元素。 4．当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_____存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用_______存储结构为宜。5．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的个元素。 三、算法设计题（每小题25分） 1．设有一个用向量表示的线性表L，要求写出一个将该表逆置的过程，允许在原表的存储空间外再增加一个附加的工作单元。 2．已知两个整数集合A和B，它们的元素分别依元素值递增有序存放在两个单链表HA 和HB中，编写一个函数求出这两个集合的并集C，并要求集合C的链表的结点仍依元素值递增有序存放。（注意：并集不是归并） 第一章 行列式 习题1.1 1. 证明：（1）首先证明)3(Q 是数域。 因为)3(Q Q ?，所以)3(Q 中至少含有两个复数。 任给两个复数)3(3,32211Q b a b a ∈++，我们有 3 )()3()3)(3(3)()()3()3(3)()()3()3(2121212122112121221121212211b a a b b b a a b a b a b b a a b a b a b b a a b a b a +++=++-+-=+-++++=+++。 因为Q 是数域，所以有理数的和、差、积仍然为有理数，所以 ) 3(3)()3()3)(3()3(3)()()3()3()3(3)()()3()3(2121212122112121221121212211Q b a a b b b a a b a b a Q b b a a b a b a Q b b a a b a b a ∈+++=++∈-+-=+-+∈+++=+++。 如果0322≠+b a ，则必有22,b a 不同时为零，从而0322≠-b a 。 又因为有理数的和、差、积、商仍为有理数，所以 )3(33) (3)3() 3)(3()3)(3(3 32 2 22212122222121222222112211Q b a b a a b b a b b a a b a b a b a b a b a b a ∈--+--= -+-+= ++。 综上所述，我们有)3(Q 是数域。 （2）类似可证明)(p Q 是数域，这儿p 是一个素数。 （3）下面证明：若q p ,为互异素数，则)()(q Q p Q ?。 （反证法）如果)()(q Q p Q ?，则q b a p Q b a +=? ∈?,，从而有 q ab qb a p p 2)()(222++==。 由于上式左端是有理数，而q 是无理数，所以必有02=q ab 。 所以有0=a 或0=b 。 如果0=a ，则2 qb p =，这与q p ,是互异素数矛盾。 如果0=b ，则有 a p =，从而有“有理数=无理数”成立，此为矛盾。 所以假设不成立，从而有)()(q Q p Q ?。 （A ）需经常修改L 中的结点值 （E ）需不断对L 进行删除插入 第二部分线性表 、选择题 1 ?关于顺序存储的叙述中，哪一条是不正确的 （B ） A. 存储密度大 B. 逻辑上相邻的结点物理上不必邻接 C. 可以通过计算直接确定第 i 个结点的位置 D. 插入、删除操作不方便 2.长度为n 的单链表连接在长度为 m 的单链表后的算法的时间复杂度为 （C ） A 0（ n ） B 0（1） C 0（m ） D 0（m+n ） 3 .在n 个结点的顺序表中，算法的时间复杂度是 0（1）的操作是：（A ） A 访问第i 个结点（1<=i<=n ）和求第i 个结点的直接前趋（2<=i<=n ) B 在第i 个结点（1<=i<=n ）后插入一个新结点 C 删除第i 个结点（1<=i<=n ) D 将n 个结点从小到大排序 4.一个向量第一个兀素的存储地址是 100 ,每个兀素的长度为 2 ,则第5 个兀素的地址是 (B ) ( A ) 110 ( B ) 108 (C ) 100 ( D ) 120 5 .已知一个顺序存储的线性表， 设每个结点需要占 m 个存储单元，若第一个结点的地址为 da , 则第i 个结点的地址为：（A ） 7 .链表是一种采用（ B ）存储结构存储的线性表。 （A ）顺序 （B ）链式 （C ）星式 （D ）网状 8 .线性表若采用链式存储结构时，要求内存中可用存储单兀的地址： （D ） （A ）必须是连续的 （B ）部分地址必须是连续的 （C ）一定是不连续的 （D ）连续或不连续都可以 9 .线性表L 在_ （ B ）情况下适用于使用链式结构实现。 A ） da+（i-1）*m B ） da+i*m 6.在具有n 个结点的单链表中，实现（ A ）遍历链表和求链表的第 i 个结点 C ）删除开始结点 C ） da-i*m D ） da+（i+1）*m A ）的操作，其算法的时间复杂度为 0（n ）。 B ）在地址为p 的结点之后插入一个结点 D ） 删除地址为p 的结点的后继结点 第二章数据库及其操作 练习一 一、选择题 1．打开一个数据库的命令是（） A USE B USE DATABASE C OPEN D OPEN DATABASE 2．VISUAL FOXPRO 数据库文件是（） A 是存放用户数据文件 B 管理数据库对象的系统文件 C 是存放用户数据和系统数据的文件 D 前三种说法都对 3．要为当前表所有职工0增加100元工资应该使用的命令 A CHANGE 工资WITH 工资+100 B REPLACE 工资WITH 工资+100 C CHANGE ALL WITH 工资+100 D REPLAC E ALL 工资WITH 工资+100 4．以下关于自由表的叙述，正确的是（） A 全部是用以前版本的FOXPRO（FOXBASE）建立的表 B 可以用VISUAL FOXPRO建立，但是不能把它添加到数据库中 C 自由表可以添加到数据库中，数据库表也可以从数据库中移出成为自由表 D 自由表可以添加到数据库中，但数据库表不可以从数据库中移出成为自由表5．VISUAL FOXPRO 参照完整性规则不包括（） A 更新规则 B 删除规则 C 查询规则 D 插入规则 6．在VISUAL FOXPRO 中以下叙述错误的是（） A 关系也被称作表 B 一个表被存储为一个文件 C 文件的扩展名.DBF D 多个表存储在一个文件中 7.在VISUAL FOXPRO中不允许出现重复字段值的索引是( ) A 侯选索引和主索引 B 普通索引和惟一索引 C 惟一索引和主索引 D 惟一索引 8.如果在命令输入命令”LIST名称”.主窗口中显示: 记录号名称 1 电视机 2计算机 3电话线 4电冰箱 5电线假定名称学段为字符型,宽度为6,那么下面程序段的输出结果是 GO 2 SCAN NEXT 4 FOR LEFT (名称,2)=”电” IF RIGHT(名称,2)=”线” EXIT ENDIF ENDSCAN ? 名称 A 电话线 B 电线 C 电冰箱 D 电视机 9.在创建数据库表结构是,给指定了主索引,这属于数据完整性的( ) A 参照完整性 B 实体完整性 C 域完整性 D 用户定义完整性 10.在创建数据库表结构时,为该表中一些字段建立普通索引,其目的是( ) A 改变表中记录的物理顺序 B 为了对表进行实体完整性约束 C 加快数据库表的更新速度 D 加快数据库表的查询速度 11.设有两个数据库表,父表子表之间是一对多的联系,为控制父表和子表中数据的一致性可以设置”参照完整性规则”,要求这两个表 A 在父表连接字段上建立索引,在子表连接字段上建立主索引 B 在父表连接字段上建立主索引,在子表连接字段上建立普通索引 C 在父表连接字段上不需要建立任何索引,在子表连接字段上建立普通索引 D 在父表和子表的连接字段上都要建立主索引 12．Visual FoxPro的“参照完整性”中“插入规则”包括的选择是（） A）级联和忽略B）级联和删除C）级联和限制D）限制和忽略 13．在Visual FoxPro中，使用LOCAT FOR 第一章 行列式 一、单项选择题 1．下列排列是5阶偶排列的是 ( ). (A) 24315 (B) 14325 (C) 41523 (D)24351 2．如果n 阶排列n j j j 21的逆序数是k , 则排列12j j j n 的逆序数是( ). (A)k (B)k n (C) k n 2 ! (D)k n n 2)1( 3. n 阶行列式的展开式中含1122a a 的项共有( )项. (A) 0 (B)2 n (C) )!2( n (D) )!1( n 4． 001001001001 000( ). (A) 0 (B)1 (C) 1 (D) 2 5. 0 001100000100100( ). (A) 0 (B)1 (C) 1 (D) 2 6．在函数10 3 23211112)(x x x x x f 中3x 项的系数是( ). (A) 0 (B)1 (C) 1 (D) 2 7. 若2 1 33 32 31 232221 131211 a a a a a a a a a D ，则 32 3133 31 2221232112 111311122222 2a a a a a a a a a a a a D ( ). (A) 4 (B) 4 (C) 2 (D) 2 8．若 a a a a a 22 2112 11，则 21 11 2212ka a ka a ( ). (A)ka (B)ka (C)a k 2 (D)a k 2 9． 已知4阶行列式中第1行元依次是3,1,0,4 , 第3行元的余子式依次为 x ,1,5,2 , 则 x ( ). (A) 0 (B)3 (C) 3 (D) 2 10. 若5 7 3 4 111113263478 D ，则D 中第一行元的代数余子式的和为( ). (A)1 (B)2 (C)3 (D)0 11. 若2 23 5 1 011110403 D ，则D 中第四行元的余子式的和为( ). (A)1 (B)2 (C)3 (D)0 12. k 等于下列选项中哪个值时，齐次线性方程组 00321 321321x x kx x kx x kx x x 有非零解. ( ) (A)1 (B)2 (C)3 (D)0 二、填空题 1. n 2阶排列)12(13)2(24 n n 的逆序数是. 2．在六阶行列式中项261365415432a a a a a a 所带的符号是. 3．四阶行列式中包含4322a a 且带正号的项是 . 4．若一个n 阶行列式中至少有12 n n 个元素等于0, 则这个行列式的值等于 . 第二章线性表习题及答案 一、基础知识题 2.1 试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。 答：始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。 链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。 头结点是我们人为地在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。 2.2 何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑： 1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。 2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。 2.3 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素? 答：在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点。删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i 越接近n则所需移动的结点数越少。 2.4 为什么在单循环链表中设置尾指针比设置头指针更好? 答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和rear, 查找时间都是O(1)。 若用头指针来表示该链表，则查找终端结点的时间为O(n)。 2.5 在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少? 答：我们分别讨论三种链表的情况。 1. 单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。 2. 双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。 3. 单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。 2.6 下述算法的功能是什么? LinkList Demo(LinkList L){ // L 是无头结点单链表 ListNode *Q,*P; if(L&&L->next){ Q=L;L=L->next;P=L; 根据上图的的两个表，完成下列操作题。 １、在２号工作区打开xscj01.dbf表；再在１号工作区打开xsda.dbf表。 ２、使用Browse命令浏览xsda.dbf表中“计算机01”班的学生记录。（并说出这是什么关系操作？） ３、使用Browse命令浏览xsda.dbf表中所有记录的姓名、班级和入学成绩信息。（并说出这是什么关系操作？） ４、将记录指针定位到第3条记录，分别执行display和list命令，对比两个命令单独使用有何区别？ ５、先清屏，再显示xsda.dbf表中4~7条记录，然后显示当前记录号。 ６、先清屏，定位到xsda.dbf表中第4条记录，然后显示第４条至最后一条的所有记录。 ７、先清屏，用函数显示xsda.dbf表中当前的记录号和记录总数。 ８、先清屏，将记录指针定位到第8条，再向下移4条，分别求RECNO()和EOF()的值？（想一想为什么？） ９、先清屏，将记录指针定位到第1条，再向上移3条，分别求RECNO()和BOF()的值？（想一想为什么？） １０、将xsda.dbf中“计算机01”班的学生记录复制成xsda_jsj01.dbf表。并在3号工作区打开并浏览xsda_jsj01.dbf表，最后还要切换到1号工作区。 １１、将xsda.dbf表结构复制成xsda_blank.dbf表，新表中只含学号、姓名、班级和入学成绩四个字段。（在3号工作区打开并浏览xsda_blank.dbf） １２、打开xsgl.pjx项目，将xsda_blank.dbf表添加到xs.dbc数据库中，然后在该表的姓名和班级之间插入一新字段性别C(2)，并要求性别字段只能输入“男”或“女”，并将性别字段的默认值设为“男”；然后将要求学号字段只能输入数字字符；最后在表中输入一条记录：20040011 蔡健志男计算机01615 １３、先使用命令关闭所有打开的文件，再使用“数据工作期”分别打开并浏览xsda.dbf、xscj01.dbf、xsda_blank.dbf三个表。 １４、用命令打开xs.dbc数据库设计器窗口，将xsda_jsj01.dbf表添加至当前数据库。 １５、使用菜单方式将xsda_blank表中的记录追加到xsda_jsj01.dbf表。 １６、使用命令给xsda_jsj01.dbf表中所有女生作逻辑删除，再作物理删除。 １７、使用命令zap彻底删除xsda_jsj01.dbf表中所有记录。 １８、用locate命令逐一查找xsda.dbf表中入学成绩高于400分的记录，并显示记录号和记录内容，并判断查找是否成功。 １９、使用索引命令对xsda.dbf表按入学成绩降序排序，并显示排序的结果。 ２０、使用SORT 命令对xsda.dbf表按入学成绩降序排序，排序的结果保存为xsda1.dbf。 （思考：比较使用索引命令和排序命令对表进行排序有何不同？）并查看xsda1.d bf表的内容。 ２１、使用表设计器对xsda1.dbf表先根据学号建立主索引xh，再根据班级建立普通索引bj，并将bj设为当前索引并浏览。（看该表是否根据班级进行排序） ２２、对xsda1.dbf表先根据班级建立普通索引，班级相同再根据入学成绩升序建立索引。 第四章 （×）1．若向量组123,,ααα线性相关，则3α可由12,αα线性表示. （√）2．若向量组A 可由向量组B 线性表示，则()()R A R B ≤. （×）3．若向量组123,,ααα线性相关，则1α可由23,αα线性表示. （√）4．若向量组A 可由向量组B 线性表示，则()()R A R B ≤. 5.若齐次线性方程组0AX = 只有零解，则A 的列向量组线性无关. 6．等价的向量组具有相同的秩. （ ） 设A 为n 阶矩阵，则T A 与A 的特征值相同． （ ） 4．非零向量组的最大无关组存在且唯一． （ ） 5．对于任意参数123,,m m m ，向量组11100m α?? ? ?= ? ???，22102m α?? ? ?= ? ???，3 3123m α?? ? ?= ? ??? 总是线性 无关． （ ） 6. 设V =({)}1,,,,,,212121=+++∈=n n T n x x x R x x x x x x x 满足， 则V 是向量空间. （ ） 7.设21,V V 分别为向量组A ,B 生成的向量空间，且向量组A ,B 等价,则21V V =． 8.若存在一组数120m k k k ==== ，使得 11220m m k k k ααα+++= 成立，则向量组12,,,m ααα （ ） .A 线性相关 .B 线性无关 .C 可能线性相关，也可能线性无关 .D 部分线性相关 9．已知43?的矩阵A 的行向量组线性无关，则=')(A R （ ） .A 1； .B 2； .C 4； .D 3. 10．向量组12,,,m a a a （2m ≥）线性相关，则 （ ） .A 12,,,m a a a 中每一个向量均可由其余向量线性表示； .B 12,,,m a a a 中每一个向量均不可由其余向量线性表示； .C 12,,,m a a a 中至少有一个向量可由其余向量线性表示；第二章线性表答案
线性代数第二章答案
第二章线性表答案
第2章数据库和表的创建
2019线性代数与概率统计随堂练习答案
数据结构第二章线性表测试题
线性代数第二章矩阵试题及答案
第2章线性表习题解答
线性代数第一章自测题
第二章线性表测试题
线性代数课后习题答案(陈维新)
(完整版)数据结构第二章线性表1答案
第二章 数据库及其操作
线性代数1-2章精选练习题
第二章线性表习题及答案
第二章 数据库和表上机作业
线性代数第四章自测题
相关主题
文本预览