线性表练习题(答案)

第2章线性表

一选择题

下列程序段的时间复杂度为（ C ）。

for( int i=1;i<=n;i++)

for( int j=1;j<= m; j++)

A[i][j] = i*j ;

A. O(m2)

B. O(n2)

C. O(m*n)

D. (m+n)

下面关于线性表的叙述中，错误的是哪一个？（B ）

A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

线性表是具有n个（ C ）的有限序列（n>0）。

A．表元素B．字符C．数据元素D．数据项

若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。

A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表

某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。

A．单链表B．仅有头指针的单循环链表

C．双链表D．仅有尾指针的单循环链表

设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表

若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ D ）存储方式最节省运算时间。

A．单链表B．双链表C．单循环链表D．带头结点的双循环链表

链表不具有的特点是（ B ）

A．插入、删除不需要移动元素B．可随机访问任一元素

C．不必事先估计存储空间D．所需空间与线性长度成正比

下面的叙述不正确的是（B,C ）

A．线性表在链式存储时，查找第i个元素的时间同i的值成正比

B. 线性表在链式存储时，查找第i个元素的时间同i的值无关

C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比

D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关

若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ C ）(1<=i<=n+1)。

A. O(0)

B. O(1)

C. O(n)

D. O(n2)

对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（C ）。

A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)

线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ C ）A．O（i）B．O（1）C．O（n）D．O（i-1）

循环链表H的尾结点P的特点是（A ）。

A．P->next=H B．P->next= H->next C．P=H D．P=H->next

完成在双循环链表结点p之后插入s的操作是（D ）；

A．p->next=s ; s->priou=p; p->next->priou=s ; s->next=p->next;

B．p->next->priou=s; p->next=s; s->priou=p; s->next=p->next;

C．s->priou=p; s->next=p->next; p->next=s; p->next->priou=s ;

D．s->priou=p; s->next=p->next; p->next->priou=s ; p->next=s;

设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（B ）。

A. s->next=p->next；p->next=-s；

B. q->next=s；s->next=p；

C. p->next=s->next；s->next=p；

D. p->next=s；s->next=q；

二、判断

顺序存储结构的主要缺点是不利于插入或删除操作。( 1 )

线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( 1 )

对任何数据结构链式存储结构一定优于顺序存储结构。( 0 )

顺序存储方式只能用于存储线性结构。( 0 )

集合与线性表的区别在于是否按关键字排序。( 0 )

线性表的特点是每个元素都有一个前驱和一个后继。( 0 )

取线性表的第i个元素的时间同i的大小有关. ( 1 )

线性表只能用顺序存储结构实现。( 0 )

顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( 0 )

链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。( 1 )

三、填空

线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是___（n-1）/2_____。

在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动____n+1-i____个元素。

在双向链表结构中，若要求在p 指针所指的结点之前插入指针为s 所指的结点，则需执行下列语句：

s->next=p；

s->prior= __p->prior______；

p->prior=s；

___s->prior->next_____=s；

链接存储的特点是利用___指针_____来表示数据元素之间的逻辑关系。

已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：__p->next=p->next->next______

四、算法设计题

若链表类的定义如下所示，请完成以下成员方法的实现。（另附页提交答案）

void Delete(const DataType& x); //删除值为x的结点

void Convert();//单链表就地逆转

void operator+= (const LinkList &other);//将两个已排序的单链表合并成一个链表（值可重复）#include

#include

#include

#define DataType int

template class LinkList;

第二章线性表答案

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、二阶、三阶行列式 2、全排列和逆序数，奇偶排列（可以不介绍对换及有关定理），n 阶行列式的定义 3、行列式的性质 4、n 阶行列式ij a D =，元素ij a 的余子式和代数余子式，行列式按行（列）展开定理 5、克莱姆法则 （二）基本要求 1、理解n 阶行列式的定义 2、掌握n 阶行列式的性质 3、会用定义判定行列式中项的符号 4、理解和掌握行列式按行（列）展开的计算方法，即 5、会用行列式的性质简化行列式的计算，并掌握几个基本方法： 归化为上三角或下三角行列式， 各行（列）元素之和等于同一个常数的行列式， 利用展开式计算 6、掌握应用克莱姆法则的条件及结论 会用克莱姆法则解低阶的线性方程组 7、了解n 个方程n 个未知量的齐次线性方程组有非零解的充要条件 第二章 矩阵 （一）要点 1、矩阵的概念 n m ?矩阵n m ij a A ?=)(是一个矩阵表。当n m =时，称A 为n 阶矩阵，此时由A 的元素按原来排列的形式构成的n 阶行列式，称为矩阵A 的行列式，记为A . 注：矩阵和行列式是两个完全不同的两个概念。 2、几种特殊的矩阵：对角阵；数量阵；单位阵；三角形矩阵；对称矩阵 3、矩阵的运算；矩阵的加减法；数与矩阵的乘法；矩阵的转置；矩阵的乘法 （1）矩阵的乘法不满足交换律和消去律，两个非零矩阵相乘可能是零矩阵。 如果两矩阵A 与B 相乘，有BA AB =,则称矩阵A 与B 可换。 注：矩阵乘积不一定符合交换 （2）方阵的幂：对于n 阶矩阵A 及自然数k ， 规定I A =0 ,其中I 为单位阵 .

(3) 设多项式函数k k k k a a a a ++++=--λλλλ?1110)( ，A 为方阵，矩阵A 的 多项式I a A a A a A a A k k k k ++++=--1110)( ?,其中I 为单位阵。 （4）n 阶矩阵A 和B ，则B A AB =. （5）n 阶矩阵A ，则A A n λλ= 4、分块矩阵及其运算 5、逆矩阵：可逆矩阵（若矩阵A 可逆，则其逆矩阵是唯一的）；矩阵A 的伴随矩阵记为*A ， 矩阵可逆的充要条件；逆矩阵的性质。 6、矩阵的初等变换：初等变换与初等矩阵；初等变换和初等矩阵的关系；矩阵在等价意义下的标准形；矩阵A 可逆的又一充分必要条件：A 可以表示成一些初等矩阵的乘积；用初等变换求逆矩阵。 7、矩阵的秩：矩阵的k 阶子式；矩阵秩的概念；用初等变换求矩阵的秩 8、矩阵的等价 （二）要求 1、理解矩阵的概念；矩阵的元素；矩阵的相等；矩阵的记号等 2、了解几种特殊的矩阵及其性质 3、掌握矩阵的乘法；数与矩阵的乘法；矩阵的加减法；矩阵的转置等运算及性质 4、理解和掌握逆矩阵的概念；矩阵可逆的充分条件；伴随矩阵和逆矩阵的关系；当A 可逆时,会用伴随矩阵求逆矩阵 5、了解分块矩阵及其运算的方法 （1）在对矩阵的分法符合分块矩阵运算规则的条件下，其分块矩阵的运算在形式上与不分块矩阵的运算是一致的。 （2）特殊分法的分块矩阵的乘法，例如n m A ?，l n B ?，将矩阵B 分块为 ) (21l b b b B =，其中j b （l j 2, ,1=）是矩阵B 的第j 列， 则 又如将n 阶矩阵P 分块为) (21n p p p P =，其中j p （n j 2, ,1=）是矩阵P 的第j 列. （3）设对角分块矩阵

数据结构试题及答案

数据结构试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为（C ） A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时，要求占用的存储空间地址（D ） A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ D ）。 A n B n/2 C (n-1)/2 D (n+1)/2 4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。 A s→link = p→link;p→link = s; B p→link = s; s→link = q; C p→link = s→link;s→link = p; D q→link = s;s→link = p; 5、如果想在4092个数据中只需要选择其中最小的5个，采用（ C ）方法最好。 A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序 6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（ B ）。 A 求子串 B 模式匹配 C 串替换 D 串连接 7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放

该数组至少需要的存储字数是（ C ）。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。 A 栈 B 队列 C 循环队列 D 优先队列 9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。 10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。 A ( front - rear + 1) % m B ( rear - front + 1) % m C ( front - rear + m) % m D ( rear - front + m) % m 11、一个数组元素a[i]与（ A ）的表示等价。 A *（a+i） B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数。 A 指针 B 引用 C 值 D 变量 13、下面程序段的时间复杂度为（ C ） for (int i=0;i

线性代数第二章答案

第二章 矩阵及其运算 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)

数据结构第二章线性表测试题

第二章线性表 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 && jnext; j++;} p=head; while ( p ->next ) p=p->next; while ( p->next->next ) p=p->next; （1）s->next=p->next; p->next=s; （2）q =L ; whil e ( q ->next !=p ) q =q ->next;s->next=p 或 q ->next ; q ->next=s; (3 ) s->next=L ->next; L ->next=s; （4）q =L ; whil e ( q ->next !=NULL) q =q ->next;s->next= q ->next ; q ->next=s;

4、设计算法：在顺序表中删除值为e 的元素，删除成功，返回1；否则，返回0。 5、设计一个算法，将一个带头节点的数据域依次为a 1，a 2，…，a n （n ≥3）的单链表的所有节点逆置，即第一个节点的数据域变为a n ，…，最后一个节点的数据域为a 1。（注意：先用自然语言描述算法基本思想，然后用类C++语言描述） int Sqlist::DeleteElem( T e ) { for (i=1; i<=len g t h ; i ++) // 按值顺序查找 * i 可从0开始 if (elem[i-1]= =e) // 找到，进行删除操作 { for ( j=i; jnext; 4 LinkList* pri = NULL; //之前的节点 5 while(p){ 6 LinkList* q = new LinkList; 7 q->data = p->data; //把当前节点记录下来 8 q->next = pri; 9 pri = q; 10 head->next = q; 11 LinkList* t = p; //当前节点没用了删除掉 12 p=p->next; 13 delete(t); 14 } 15 }

线性代数知识点总结汇总

线性代数知识点总结 1 行列式 （一）行列式概念和性质 1、逆序数：所有的逆序的总数 2、行列式定义：不同行不同列元素乘积代数和 3、行列式性质：（用于化简行列式） （1）行列互换（转置），行列式的值不变 （2）两行（列）互换，行列式变号 （3）提公因式：行列式的某一行（列）的所有元素都乘以同一数k，等于用数k 乘此行列式 （4）拆列分配：行列式中如果某一行（列）的元素都是两组数之和，那么这个行列式就等于两个行列式之和。 （5）一行（列）乘k加到另一行（列），行列式的值不变。 （6）两行成比例，行列式的值为0。 （二）重要行列式 4、上（下）三角（主对角线）行列式的值等于主对角线元素的乘积 5、副对角线行列式的值等于副对角线元素的乘积乘 6、Laplace展开式：（A是m阶矩阵，B是n阶矩阵），则 7、n阶（n≥2）范德蒙德行列式

数学归纳法证明 ★8、对角线的元素为a，其余元素为b的行列式的值： （三）按行（列）展开 9、按行展开定理： （1）任一行（列）的各元素与其对应的代数余子式乘积之和等于行列式的值（2）行列式中某一行（列）各个元素与另一行（列）对应元素的代数余子式乘积之和等于0 （四）行列式公式 10、行列式七大公式： （1）|kA|=k n|A| （2）|AB|=|A|·|B| （3）|A T|=|A| （4）|A-1|=|A|-1 （5）|A*|=|A|n-1 （6）若A的特征值λ1、λ2、……λn，则 （7）若A与B相似，则|A|=|B| （五）克莱姆法则 11、克莱姆法则： （1）非齐次线性方程组的系数行列式不为0，那么方程为唯一解

（2）如果非齐次线性方程组无解或有两个不同解，则它的系数行列式必为0 （3）若齐次线性方程组的系数行列式不为0，则齐次线性方程组只有0解；如果方程组有非零解，那么必有D=0。 2 矩阵 （一）矩阵的运算 1、矩阵乘法注意事项： （1）矩阵乘法要求前列后行一致； （2）矩阵乘法不满足交换律；（因式分解的公式对矩阵不适用，但若B=E,O,A-1，A*,f(A)时，可以用交换律） （3）AB=O不能推出A=O或B=O。 2、转置的性质（5条） （1）（A+B）T=A T+B T （2）（kA）T=kA T （3）（AB）T=B T A T （4）|A|T=|A| （5）（A T）T=A （二）矩阵的逆 3、逆的定义： AB=E或BA=E成立，称A可逆，B是A的逆矩阵，记为B=A-1 注：A可逆的充要条件是|A|≠0 4、逆的性质：（5条） （1）（kA）-1=1/k·A-1 (k≠0) （2）（AB）-1=B-1·A-1 （3）|A-1|=|A|-1 （4）（A T）-1=（A-1）T （5）（A-1）-1=A

数据结构线性表2答案

习题二 一、选择题 1．在一个长度为n的顺序表中删除第i个元素（0＜i

线性代数第二章矩阵试题及答案

第二章矩阵 一、知识点复习 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个列向量(维数相同)对应分量乘积之和.

第二章线性表测试题

第二章测试试题 班级：学号：姓名：成绩： 一、选择题（每小题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. 排列的逆序数 2. 行列式按行（列）展开法则 3. 行列式的性质及行列式的计算 1.行列式的计算： ① (定义法)1212121112121222() 1212()n n n n n j j j n j j nj j j j n n nn a a a a a a D a a a a a a τ= = -∑ L L L L L M M M L 1 ②（降阶法）行列式按行（列）展开定理： 行列式等于它的任一行（列）的各元素与其对应的代数余子式的乘积之和. 推论：行列式某一行（列）的元素与另一行（列）的对应元素的代数余子式乘积之和等于零. ③ (化为三角型行列式)上三角、下三角、主对角行列式等于主对角线上元素的乘积. ④ 若A B 与都是方阵（不必同阶）,则 ==()mn A O A A O A B O B O B B O A A A B B O B O *==* *=-1 ⑤ 关 于 副 对角线： (1)2 1121 21 1211 1 () n n n n n n n n n n n a O a a a a a a a O a O ---* ==-K N N 1

⑥ 范德蒙德行列式：()1 22 22 12111112 n i j n j i n n n n n x x x x x x x x x x x ≤<≤---=-∏L L L M M M L 111 ⑦ a b -型公式：1 [(1)]()n a b b b b a b b a n b a b b b a b b b b a -=+--L L L M M M O M L ⑧ (升阶法)在原行列式中增加一行一列，保持原行列式不变的方法. ⑨ (递推公式法) 对n 阶行列式n D 找出n D 与1n D -或1n D -,2n D -之间的一种关系——称为递推公式，其中 n D ,1n D -,2n D -等结构相同，再由递推公式求出n D 的方法称为递推公式法. (拆分法) 把某一行（或列）的元素写成两数和的形式，再利用行列式的性质将原行列式写成两行列式之和， 使问题简化以例计算. ⑩ (数学归纳法) 2. 对于n 阶行列式A ，恒有：1 (1)n n k n k k k E A S λλ λ-=-=+-∑，其中k S 为k 阶主子式； 3. 证明 0A =的方法： ①、A A =-； ②、反证法； ③、构造齐次方程组0Ax =，证明其有非零解； ④、利用秩，证明()r A n <； ⑤、证明0是其特征值. 4. 代数余子式和余子式的关系：(1)(1)i j i j ij ij ij ij M A A M ++=-=- 第二部分 矩阵 1.矩阵的运算性质 2.矩阵求逆

数据结构课后习题及答案

填空题（10 * 1’ = 10’） 一、概念题 .当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。 .当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。 .带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 .循环队列的引入，目的是为了克服假溢出。 .长度为0的字符串称为空串。 .组成串的数据元素只能是字符。 .设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。 .为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。 .广义表的深度是广义表中括号的重数 .有向图G可拓扑排序的判别条件是有无回路。 .若要求一个稠密图的最小生成树，最好用Prim算法求解。 . 直接定址法法构造的哈希函数肯定不会发生冲突。 .排序算法所花费的时间，通常用在数据的比较和交换两大操作。 .通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。 .对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。 .存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。 .抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。 .一个算法具有五大特性：有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。 .在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s->prior= p->prior; s->next= p; p->prior- next= s; p->prior= s;。 .在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作（如插入和删除）在各种情况下统一。 .队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。 .栈是限定尽在表位进行插入或删除操作的线性表。 .在链式队列中，判定只有一个结点的条件是(Q->rear==Q->front)&&(Q->rear!=NULL)。 .已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x; p->next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 .循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt和(front=-1&&rear+1==MAXSIZE)。 .串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。 .字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。 .所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数，则称该矩阵为稀疏矩阵。 .一维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种不同的存储方式。 .在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第i列非0元素的个数。 网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。 .按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序﹑交换排序﹑插入排序归并排序等4类。 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。 .直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。 .设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。 .下列程序判断字符串s是否对称，对称则返回1，否则返回0；如?(“abba”)返回1，?（”abab”）返回0. Int f (char*s) { Int i=0,j=0; 求串长*/

线性代数课后习题答案(陈维新)

第一章 行列式 习题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 ?。

线性代数知识点总结

线性代数知识点总结 第一章行列式 （一）要点 1、 二阶、三阶行列式 2、 全排列和逆序数，奇偶排列（可以不介绍对换及有关定理） ，n 阶行列式的定义 3、 行列式的性质 4、 n 阶行列式 ^a i j ，元素a j 的余子式和代数余子式，行列式按行（列）展开定理 5、 克莱姆法则 （二）基本要求 1 、理解n 阶行列式的定义 2、掌握n 阶行列式的性质 3 、会用定义判定行列式中项的符号 4、理解和掌握行列式按行（列）展开的计算方法，即 a 1i A Ij ' a 2i A 2 j ' a ni A nj ^ 5、会用行列式的性质简化行列式的计算，并掌握几个基本方法： 归化为上三角或下三角行列式， 各行（列）元素之和等于同一个常数的行列式， 利用展开式计算 6、 掌握应用克莱姆法则的条件及结论 会用克莱姆法则解低阶的线性方程组 7、 了解n 个方程n 个未知量的齐次线性方程组有非零解的充要条件 第二章矩阵 （一）要点 1、 矩阵的概念 m n 矩阵A =（a j ）mn 是一个矩阵表。当 m =n 时，称A 为n 阶矩阵，此时由 A 的 元素按原来排列的形式构成的 n 阶行列式，称为矩阵 A 的行列式，记为 A . 注：矩阵和行列式是两个完全不同的两个概念。 2、 几种特殊的矩阵：对角阵；数量阵；单位阵；三角形矩阵；对称矩阵 a i 1A j 1 ■ a i2A j 2 ? a in A jn = 〔 D '

3、矩阵的运算；矩阵的加减法；数与矩阵的乘法；矩阵的转置；矩阵的乘法 (1矩阵的乘法不满足交换律和消去律，两个非零矩阵相乘可能是零矩阵。如果两矩阵A与B相乘，有AB = BA ,则称矩阵A与B可换。注：矩阵乘积不一定符合交换 (2)方阵的幕：对于n阶矩阵A及自然数k， A k=A A A , 1 k个 规定A° = I ,其中I为单位阵. (3) 设多项式函数(J^a^ k?a1?k^l Z-心律??a k，A为方阵，矩阵A的 多项式(A) = a0A k?a1A k' …-?-a k jA ■ a k I ,其中I 为单位阵。 (4)n阶矩阵A和B ,贝U AB=IAB . (5)n 阶矩阵A ,则∣∕Λ =λn A 4、分块矩阵及其运算 5、逆矩阵：可逆矩阵(若矩阵A可逆，则其逆矩阵是唯一的)；矩阵A的伴随矩阵记 * 为A , AA* = A*A = AE 矩阵可逆的充要条件；逆矩阵的性质。 6、矩阵的初等变换：初等变换与初等矩阵；初等变换和初等矩阵的关系；矩阵在等价 意义下的标准形；矩阵A可逆的又一充分必要条件：A可以表示成一些初等矩阵的乘积； 用初等变换求逆矩阵。 7、矩阵的秩：矩阵的k阶子式；矩阵秩的概念；用初等变换求矩阵的秩 8、矩阵的等价 (二)要求 1、理解矩阵的概念；矩阵的元素；矩阵的相等；矩阵的记号等 2、了解几种特殊的矩阵及其性质 3、掌握矩阵的乘法；数与矩阵的乘法；矩阵的加减法；矩阵的转置等运算及性质 4、理解和掌握逆矩阵的概念；矩阵可逆的充分条件；伴随矩阵和逆矩阵的关系；当A 可逆时，会用伴随矩阵求逆矩阵 5、了解分块矩阵及其运算的方法 (1)在对矩阵的分法符合分块矩阵运算规则的条件下，其分块矩阵的运算在形式上与不分块矩阵的运算是一致的。 (2)特殊分法的分块矩阵的乘法，例如A m n, B nl,将矩

数据结构试题答案

第一章概论 一、选择题 1、研究数据结构就是研究（D ）。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作（研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作） 2、算法分析的两个主要方面是（ A ）。 A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。（线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素，有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继）（链表、栈、队列、数组、串） A. 图 B. 树 C. 广义表（线性表的推广） D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B ）等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是（ C ）。 for(i=0;i

6、算法是（D ）。为了解决某一问题而规定的一个有限长的操作序列 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（C ）。 A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n) 8、下面程序段的时间复杂度为（ C ）。 i=1; while(i<=n) i=i*3; A. O(n) B. O(3n) C. O(log3n) D. O(n3) 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（B ）和运算等的学科。（关系和操作） A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是（ A ）。 i=s=0; while(s

第二章线性表习题及答案

第二章线性表习题及答案 一、基础知识题 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;