第2章线性表作业参考答案
第2章作业参考答案
1. B
2. A，D
3. 1，n/2，(n-1)/2，n，0，0
4.
templete
void SqList
{
ElemType e;
for (int i = 0; i < len / 2; i++)
{
e = elem[i];
elem[i] = elem[len – i -1];
elem[len – i – 1] = e;
}
}
templete
void LinkList
{
if (!head->next) return;
LinkNode
q -> next = NULL;
tail = q;
while (p)
{
q = p;
p = p –> next;
q –> next = head -> next;
head -> next = q;
}
}
8.
void add(LinkList
int pa_len, pb_len, i, j;
pa_len = pa.Length();
pb_len = pb.Length();
i = j = 1;
Monomial pa_e, pb_e;
pa.GetElem(pa_e, 1);
pb.GetElem(pb_e, 1);
while (i <= pa_len && j <= pb_len)
{
if (pa_e.exp < pb_e.exp)
{
i++;
if (i <= pa_len) pa.GetElem(pa_e, i);
}
else if (pa_e.exp > pb_e.exp)
{
pa.Insert(pb_e, i);
i++;
pa_len++;
j++;
if (j <= pb_len) pb.GetElem(pb_e, j);
}
else
{
if (pa_e.coef += pb_e.coef)
{
pa.SetElem(pa_e, i);
i++;
}
else
{
pa.Delete(pa_e, i);
pa_len--;
}
j++;
if (i <= pa_len) pa.GetElem(pa_e, i);
if (j <= pb_len) pb.GetElem(pb_e, j);
}
}
while (j <= pb_len)
{
pb.GetElem(pb_e, j++);
pa.Append(pb_e);
}
}
第二章 考研试题精选
第二章线性表作业 一、选择题 1．下述哪一条是顺序存储结构的优点？（） A．存储密度大B．插入运算方便 C．删除运算方便D．可方便地用于各种逻辑结构的存储表示 2．下面关于线性表的叙述中，错误的是哪一个？（） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具有n个（）的有限序列（n>0）。 A．表元素B．字符C．数据元素D．数据项 4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。 A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表 5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。 A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表 6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（）存储方式最节省运算时间。 A．单链表B．双链表C．单循环链表D．带头结点的双循环链表 8. 静态链表中指针表示的是（）. A．内存地址B．数组下标C．下一元素地址D．左、右孩子地址 9. 链表不具有的特点是（） A．插入、删除不需要移动元素B．可随机访问任一元素 C．不必事先估计存储空间D．所需空间与线性长度成正比 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章作业 线性表(答案)
第2章线性表 班级学号__________-姓名 一、判断正误 （×）1. 链表的每个结点中都恰好包含一个指针。 链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。 （×）2. 链表的物理存储结构具有同链表一样的顺序。 链表的存储结构特点是无序，而链表的示意图有序。 （×）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 链表的结点不会移动，只是指针内容改变。 （×）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。 （×）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜” （×）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。 （×）7. 线性表在物理存储空间中也一定是连续的。 线性表有两种存储方式，顺序存储和链式存储。后者不要求连续存放。 （×）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。 （×）9. 顺序存储方式只能用于存储线性结构。 顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如 完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。（后一节介绍） （×）10. 线性表的逻辑顺序与存储顺序总是一致的。 理由同7。链式存储就无需一致。 二、单项选择题 （C ）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构（ B ）2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（A）110 （B）108 （C）100 （D）120 （ A ）3. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是： （A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） （B）在第i个结点后插入一个新结点（1≤i≤n） （C）删除第i个结点（1≤i≤n） （D）将n个结点从小到大排序 （ B ）4. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素（A）8 （B）63.5 （C）63 （D）7 （ A ）5. 链式存储的存储结构所占存储空间：
线性代数课后作业答案(胡觉亮版)
第一章 1．用消元法解下列线性方程组： （1）??? ??=++=++=++. 5432,9753,432321 321321x x x x x x x x x 解 由原方程组得同解方程组 12323234,23,x x x x x ++=?? +=? 得方程组的解为13232, 2 3. x x x x =-?? =-+?令3x c =，得方程组的通解为 c x c x c x =+-=-=321,32,2，其中c 为任意常数． 2．用初等行变换将下列矩阵化成行阶梯形矩阵和行最简形矩阵： （2）???? ? ??--324423211123． 解 1102 232111232551232041050124442300000000r r ? ?- ?-???? ? ? ? ? -??→--??→- ? ? ? ? ?- ????? ? ?? ? ，得 行阶梯形：????? ? ?---0000510402321（不唯一）；行最简形：???? ??? ? ? ? - -00004525 10212 01 3．用初等行变换解下列线性方程组： （1）?? ? ??=+-=+-=++.3,1142,53332321321x x x x x x x x
解 2100313357214110109011320019r B ? ? ??? ? ? ?=-??→- ? ? ?- ??? ? ?? ?M M M M M M ， 得方程组的解为 9 20 ,97,32321=-==x x x ． （2）??? ??=+++=+++=++-. 2222,2562, 1344321 43214321x x x x x x x x x x x x 解 114311143121652032101222200001r B --???? ? ? =?? →-- ? ? ? ????? M M M M M M ， 得方程组无解． 第二章 1.（2） 2 2 x y x y ． 解 原式()xy y x =-． （2）01000 020 00010 n n -L L L L L L L L L ． 2.解 原式1 100 020 (1) 001 n n n +=-=-L L M M M L !)1(1n n +-
第2章线性表习题解答
第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.wendangku.net/doc/d115191181.html,st=-1; } //求表长度 int listLength(seqList S) { return https://www.wendangku.net/doc/d115191181.html,st+1; } //按序号取元素 bool getElement(seqList S,int i,elementType &x) { if(i<1 || i>https://www.wendangku.net/doc/d115191181.html,st+1) //i为元素编号，有效范围在https://www.wendangku.net/doc/d115191181.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.wendangku.net/doc/d115191181.html,st;i++) { if(S.data[i]==x) return i+1; //找到，转换为元素编号输出 } return 0; } //插入元素 int listInsert(seqList &S,elementType x, int i)
2019春北京大学网络教育学院线性代数作业答案
春季学期线性代数作业 一、选择题（每题2分，共20分） 1.（教材§1.1，课件第一讲）行列式（B ）。 A.13 B.-11 C.17 D.-1 2.（教材§1.3，课件第二讲）下列对行列式做的变换中，（B ）不会改变行列式的值。 A.将行列式的某一行乘以一个非零数 B.将行列式的某一行乘以一个非零数后加到另外一行 C.互换两行 D.互换两列 3.（教材§2.2，课件第四讲）若线性方程组无解，则a的值为（ D ）。 A.1 B.0 C.-1 D.-2 4.（教材§3.3，课件第六讲）下列向量组中，线性无关的是（C ）。 A. B. C. D. 5.（教材§3.5，课件第八讲）下列向量组中，（D ）不是的基底。 A. B. C. D.
6.（教材§4.1，课件第九讲）已知矩阵，矩阵和矩阵均为n阶矩阵，和均为实数，则下列结论不正确的是（ A ）。 A. B. C. D. 7.（教材§4.1，课件第九讲）已知矩阵，矩阵，则 （ C ）。 A. B. C. D. 8.（教材§4.1，课件第九讲）已知矩阵，为矩阵，矩阵为矩阵，为实数，则下列关于矩阵转置的结论，不正确的是（ D ）。 A. B. C. D. 9.（教材§4.3，课件第十讲）下列矩阵中，（A ）不是初等矩阵。 A. B. C. D. 10.（教材§5.1，课件第十一讲）矩阵的特征值是（B ）。 A. B. C. D. 二、填空题（每题3分，共30分）
11.（教材§1.1，课件第一讲）行列式的展开式中，的一次项的系数是 2 。 12.（教材§1.4，课件第三讲）如果齐次线性方程组有非零解，那么的值为0或1 。 13.（教材§2.3，课件第四讲）齐次线性方程组有（填“有”或“没有”）非零解。 14. （教材§3.1，课件第五讲）已知向量则 。 15. （教材§3.3，课件第六讲）向量组是线性无关（填“相关”或“无关”）的。 16. （教材§4.1，课件第九讲）已知矩阵，矩阵，那 么。 17. （教材§4.2，课件第九讲）已知矩阵，那么 。 18. （教材§5.1，课件第十一讲）以下关于相似矩阵的说法，正确的有1,2,4
线性代数课后习题答案全)习题详解
线性代数课后习题答案全)习题详解 第一章 行列式 1.利用对角线法则计算下列三阶行列式： （1）381141102---； （2）b a c a c b c b a ; （3）222111c b a c b a ； （4）y x y x x y x y y x y x +++. 解 （1）=---3 811411 02811)1()1(03)4(2??+-?-?+?-?)1()4(18)1(2310-?-?-?-?-??- =416824-++-=4- （2）=b a c a c b c b a cc c aaa bbb cba bac acb ---++3333c b a abc ---= （3）=2 221 11c b a c b a 222222cb ba ac ab ca bc ---++))()((a c c b b a ---= （4）y x y x x y x y y x y x +++yx y x y x yx y y x x )()()(+++++=333)(x y x y -+-- 33322333)(3x y x x y y x y y x xy ------+= )(233y x +-=
2.按自然数从小到大为标准次序，求下列各排列的逆序数： （1）1 2 3 4； （2）4 1 3 2； （3）3 4 2 1； （4）2 4 1 3； （5）1 3 … )12(-n 2 4 … )2(n ； （6）1 3 … )12(-n )2(n )22(-n … 2. 解（1）逆序数为0 （2）逆序数为4：4 1，4 3，4 2，3 2 （3）逆序数为5：3 2，3 1，4 2，4 1,2 1 （4）逆序数为3：2 1，4 1，4 3 （5）逆序数为 2 ) 1(-n n ： 3 2 1个 5 2，5 4 2个 7 2，7 4，7 6 3个 ……………… … )12(-n 2，)12(-n 4，)12(-n 6，…，)12(-n )22(-n )1(-n 个 （6）逆序数为)1(-n n 3 2 1个 5 2，5 4 2个 ……………… … )12(-n 2，)12(-n 4，)12(-n 6，…，)12(-n )22(-n )1(-n 个 4 2 1个 6 2，6 4 2个 ……………… … )2(n 2，)2(n 4，)2(n 6，…，)2(n )22(-n )1(-n 个 3.写出四阶行列式中含有因子2311a a 的项.
线性代数(本)习题册行列式-习题详解(修改)(加批注)
||班级： 姓名： 学号： 成绩： 批改日期： || 第 1 页 共 18 页 行列式的概念 一、选择题 1． 下列选项中错误的是( ) (A) b a d c d c b a - = ； (B) a c b d d c b a = ； (C) d c b a d c d b c a = ++33； (D) d c b a d c b a ----- =. 答案：D 2．行列式n D 不为零，利用行列式的性质对n D 进行变换后，行列式的值（ ）． (A)保持不变； (B)可以变成任何值； (C)保持不为零； (D)保持相同的正负号． 答案：C 二、填空题 1. a b b a log 1 1 log = . 解析： 0111log log log 1 1log =-=-=a b a b b a b a . 2. 6 cos 3sin 6sin 3 cos π π ππ = . 解析： 02cos 6sin 3sin 6cos 3cos 6 cos 3 sin 6sin 3 cos ==-=πππππππ π π 3.函数x x x x x f 1213 1 2)(-=中，3x 的系数为 ； x x x x x x g 2 1 1 12)(---=中，3x 的系数为 . 答案：-2；-2.
||班级： 姓名： 学号： 成绩： 批改日期： || 第 2 页 共 18 页 阶行列式n D 中的n 最小值是 . 答案：1. 5. 三阶行列式11342 3 2 1-中第2行第1列元素的代数余子式 等于 . 答案：5. 6.若 02 1 8 2=x ，则x = . 答案：2. 7.在 n 阶行列式ij a D =中，当i （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 的结点的后继结点 线性代数（试卷一) 一、 填空题(本题总计2０分,每小题2分） 1. 排列76２３451的逆序数是_______。 2． 若 122 21 12 11 =a a a a ,则=1 6 030322211211 a a a a 3。 已知n 阶矩阵A 、B 和C 满足E ABC =,其中E 为n 阶单位矩阵，则CA B =-1。 4. 若A 为n m ?矩阵,则非齐次线性方程组AX b =有唯一解的充分要条件是 ＿＿＿__＿_＿_ 5. 设A 为86?的矩阵，已知它的秩为４，则以A 为系数矩阵的齐次线性方程组的解空间维数为_ ＿2__＿__＿____＿． ６. 设Ａ为三阶可逆阵,??? ? ? ??=-1230120011 A ，则=*A ７。若Ａ为n m ?矩阵,则齐次线性方程组0Ax =有非零解的充分必要条件是 ８．已知五阶行列式1 23453 2011 11111 2 1403 54321=D ,则=++++4544434241A A A A A 9。 向量α=(2,1,0,2)T -的模（范数)______________ 。 1０。若()T k 11=α与()T 121-=β正交,则=k 二、选择题（本题总计10分,每小题2分） 1。 向量组r ααα,,,21 线性相关且秩为s ，则（D) Ａ.s r = B.s r ≤ C.r s ≤ ? D ．r s < 2. 若A 为三阶方阵,且043,02,02=-=+=+E A E A E A ，则=A (A) Ａ.8? B.8- Ｃ． 34?? Ｄ.3 4- 3.设向量组A 能由向量组B 线性表示，则( ｄ ) Ａ．)()(A R B R ≤ Ｂ．)()(A R B R < C.)()(A R B R = Ｄ．)()(A R B R ≥ ４. 设n 阶矩阵A 的行列式等于D ，则 () * kA 等于_____。c )(A *kA )(B *A k n )(C *-A k n 1)(D *A 5。 设n 阶矩阵A ，B 和C ，则下列说法正确的是_____. )(A AC AB = 则 C B =)(B 0=AB ,则0=A 或0=B )(C T T T B A AB =)()(D 22))((B A B A B A -=-+ 三、计算题(本题总计60分.１-3每小题８分，4-7每小题９分） １。 计算n 阶行列式22221 =D 22222 22322 2 12 2 2-n n 2 222 ． 2．设A 为三阶矩阵,* A 为A 的伴随矩阵，且2 1= A ，求* A A 2)3(1--. ３．求矩阵的逆 111211120A ?? ?=- ? ??? 第一部分 专项同步练习 第一章 行列式 一、单项选择题 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 阶行列式的展开式中含1211a a 的项共有( )项. (A) 0 (B)2-n (C) )!2(-n (D) )!1(-n 4． =0 00100100 1001 000( ). (A) 0 (B)1- (C) 1 (D) 2 5. =0 00110000 0100 100( ). (A) 0 (B)1- (C) 1 (D) 2 6．在函数1 3232 111 12)(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 7341111 1 326 3 478 ----= D ，则D 中第一行元的代数余子式的和为( ). (A)1- (B)2- (C)3- (D)0 11. 若2 23 5 001 01 11 10 403 --= D ，则D 中第四行元的余子式的和为( ). (A)1- (B)2- (C)3- (D)0 12. k 等于下列选项中哪个值时，齐次线性方程组??? ??=++=++=++0 00321 321321x x kx x kx x kx x x 有非零解. ( ) (A)1- (B)2- (C)3- (D)0 二、填空题 第2章线性表 1．下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 2．线性表是具有n个（）的有限序列（n>0）。 A．表元素 B．字符 C．数据元素 D．数据项 E．信息项 3.线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置 元素的时间复杂性为（） A．O（i） B．O（1） C．O（n） D．O（i-1） 4.若长度为n的线性表采用顺序存储结构，在其第i个位置插 入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 5. 对于顺序存储的线性表，访问结点和增加、删除结点的时间 复杂度为（）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 6．对于一个头指针为head的带头结点的单链表，判定该表为空 表的条件是（） A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 7.链表不具有的特点是（） A．可随机访问任一元素 B．插入、删除不需要移动元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 8.在双向链表指针p的结点前插入一个指针q的结点操作是（）。 >Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q； >Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink ; C. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q; >Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q ; 9.在单链表指针为p的结点之后插入指针为s的结点，正确的 操作是：（）。 A． s->next=p->next;p->next=s; B． p->next=s;s->next=p->next; C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s; 10．对于一个头指针为head的带头结点的单链表，判定该表为 第三章 线性方程组 一、温习巩固 1. 求解齐次线性方程组??? ??=-++=--+=-++0 51050363024321 43214321x x x x x x x x x x x x 解： 化系数矩阵为行最简式 ???? ? ????→?????? ??----=000001001-0215110531631121行变换A 因此原方程同解于? ? ?=+-=0234 21x x x x 令2412,k x k x ==，可求得原方程的解为 ???? ?? ? ??+??????? ??-=1001001221k k x ，其中21,k k 为任意常数。 2. 求解非齐次线性方程组?? ? ??=+=+-=-+8 31110232 2421321321x x x x x x x x 解：把增广矩阵),(b A 化为阶梯形 ?? ? ? ? ????→?????? ??---??→?????? ??--=-6-000341110-08-3-318031110213833180311102132124),(21行变换r r b A 因此3),(2)(=<=b A R A R ，所以原方程组无解。 3. 设)1,2,1,3(),1,1,2,3(--=--=βα。求向量γ，使βγα=+32。 解：??? ? ? --=-= 31,0,35,3)2(31αβγ 4. 求向量组123(1,1,2,4),(0,3,1,2),(3,0,7,14),T T T ααα=-==4(1,1,2,0),T α=- T )6,5,1,2(5=α的秩和一个极大线性无关组。 解：将51,ααΛ作为列向量构成矩阵，做初等行变换 第二章线性表习题及答案 一、基础知识题 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; 线性代数课后题详解 第一章 行列式 1.利用对角线法则计算下列三阶行列式： (1) ； 21-1 2 解：；5)1(1222 1-12=-?-?= (2) ；1 1 12 2 ++-x x x x 解： ； 1)1)(1(11 1232222--=-++-=++-x x x x x x x x x x (3) ;22b a b a 解： ;222 2ba ab b a b a -= (4) ;5 984131 11 解： ;59415318119318415115 984131 11=??-??-??-??+??+??= (5) ;0 00 00d c b a 解： ;00000000000000 00=??-??-??-??+??+??=d c b a d b c a d c b a (6) .132213321 解： .183211322133332221111 322133 21=??-??-??-??+??+??= 2.求下列排列的逆序数： （1）34215； 解：3在首位，前面没有比它大的数，逆序数为0；4的前面没有比它大的数，逆序数为0；2的前面有2个比它大的数，逆序数为2；1的前面有3个比它大的数，逆序数为3；5的前面没有比它大的数，逆序数为0.因此排列的逆序数为5. （2）4312； 解：4在首位，前面没有比它大的数，逆序数为0；3的前面有1个比它大的数，逆序数为1；1的前面有2个比它大的数，逆序数为2；2的前面有2个比它大的数，逆序数为2.因此排列的逆序数为5. （3）n(n-1)…21； 解：1的前面有n-1个比它大的数，逆序数为n-1；2的前面有n-2个比它大的数，逆序数为n-2；…；n-1的前面有1个比它大的数，逆序数为1；n 的前面没有比它大的数，逆序数为0.因此排列的逆序数为n(n-1)/2. (4）13…(2n-1)(2n) …42. 解：1的前面没有比它大的数，逆序数为0；3的前面没有比它大的数，逆序数为0；…；2n-1的前面没有比它大的数，逆序数为0；2的前面有2n-2个比它大的数，逆序数为2n-2；4的前面有2n-4个比它大的数，逆序数为2n-4；…；2n 的前面有2n-2n 个比它大的数，逆序数为2n-2n.因此排列的逆序数为n(n-1). 3.写出四阶行列式中含有因子2311a a 的项. 解 由定义知，四阶行列式的一般项为 43214321)1(p p p p t a a a a -，其中t 为4321p p p p 的逆序数．由于3,121==p p 已固定，4321p p p p 只能形如13□□， 即1324或1342.对应的t 分别为 10100=+++或22000=+++ ∴44322311a a a a -和42342311a a a a 为所求. 4.计算下列各行列式： (1) 71100 251020214214 ； 解： 7110025102 021 4214343 27c c c c --0 1 14 23102021 10214 ---= 34)1(14 3 10 2211014 +-?--- =- 14 3 10 2211014 --3 2 1 132c c c c ++- 14 17172 1099 -= 0. (2) ;0111101111011 110 解： 0111101111011 1104342c c c c --0 1 1 1 1 10110111000--=14)1(1 11 101 1 1+-?-- =-1 1 1 101 01 1-- 12c c +-1 2 1111 001-=- 1 2 11-=-3. 第二章线性表 一、填空题 1、数据逻辑结构包括线性结构、树型结构、图型结构这三种类型，树形结构和图形结构合称为非线性结构。 2、在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有个前驱结点，最后一个结点没有后续结点，其余每个结点有且只有一个后续结点。 3、在顺序表中插入或删除一个元素，需要平均移动一半元素，具体移动的元素个数与插入或删除的位置有关。 4、在顺序表中，逻辑上相邻的元素，其物理位置一定相邻。在单链表中，逻辑上相邻的元素，其物理位置不一定相邻。 5、在带头结点的非空单链表中，头结点的存储位置由头指针指示，首元素结点的存储位置由头结点的next域指示，除首元素结点外，其它任一元素结点的存储位置由其直接前趋结点的next域指示。 6、阅读下列算法，并补充所缺内容。 void purge_linkst( ListNode *& la ) { // 从头指针为 la 的有序链表中删除所有值相同的多余元素，并释放被删结点空间ListNode *p,*q; if(la==NULL) return; q=la; p = la->link; while (p) { if (p && ___(1)p->data!=q->data___) {q=p; p = p->link;} else { q->link= ___(2)p->link___; delete(p); p=___(3)q->link___; } }//while }// purge_linkst 二、选择题 1、在数据结构中，从逻辑上可以把数据结构分成 C。 A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 2、线性表的逻辑顺序与存储顺序总是一致的，这种说法 B。 A、正确 B、不正确 3、线性表若采用链式存储结构时，要求内存中可用存储单元的地址D。 A、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、连续或不连续都可以 4、在以下的述叙中，正确的是B。 A、线性表的线性存储结构优于链表存储结构 B、二维数组是其数据元素为线性表的线性表 C、栈的操作是先进先出 D、队列的操作方式是先进后出 三、综合题 1、已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 A、在P结点后插入S结点的语句序列是（（4）、（1））； B、在P结点前插入S结点的语句序列是（（7）、（11）、（8）、（4）、（1））； C、在表首插入S结点的语句序列是（（5）、（12））； 一、选择题 1. D 2. B 3. B 4. B 5. B 6. B 7. D 8. B 9. C 10. B 11. C 12. C 13. B 14. D 15. A 16. B 17. B 18. C 19. A 20. C 21. D 22. A 23. A 24. A 二、填空题 1. 首元素其直接前驱结点的链域的值 2. HL→next =NULL； HL=HL→next 3. 有限、一对一 4. O(1) 随机存取 5. 表中一半表长和该元素在表中的位置 6. 必定不一定 7. O（1） O（n） 8. 前驱结点的地址 O（n） 9. n-i+1 n-i 10. s->left=p p->right 三、判断题 1. × 2. × 3. × 4. × 5. × 6. × 7. √ 8. × 9. × 10. × 11. × 四、简答题 1. 线性表为：（78，50，40，60，34，90） 2. (36, 12, 8, 50, 25, 5, 15) 3. 解答： 尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next和rear, 查找时间都是O(1)。 若用头指针来表示该链表，则查找终端结点的时间为O(n)。 五、编程题 1. 解答：由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法如下： int ListLength ( LinkList L ) { int len=0 ; ListNode *p; p=L; //设该表有头结点 while ( p->next ) { p=p->next; len++; } return len; } 2. int searchmin(linklist l) { int min; int *p; p=l; min=p->data; p=p->next; while (p->next< >nil) { if (min>p->data) min=p->data; p=p->next; } return min; } 3. int searchmax(linklist l) { int max; int *p; p=l; max=p->data; p=p->next; while (p->next< >nil) { if (max 第四章 向量组的线性相关性 1. 设v 1=(1, 1, 0)T , v 2=(0, 1, 1)T , v 3=(3, 4, 0)T , 求v 1-v 2及3v 1+2v 2-v 3. 解 v 1-v 2=(1, 1, 0)T -(0, 1, 1)T =(1-0, 1-1, 0-1)T =(1, 0, -1)T . 3v 1+2v 2-v 3=3(1, 1, 0)T +2(0, 1, 1)T -(3, 4, 0)T =(3?1+2?0-3, 3?1+2?1-4, 3?0+2?1-0)T =(0, 1, 2)T . 2. 设3(a 1-a )+2(a 2+a )=5(a 3+a ), 求a , 其中a 1=(2, 5, 1, 3)T , a 2=(10, 1, 5, 10)T , a 3=(4, 1, -1, 1)T . 解 由3(a 1-a )+2(a 2+a )=5(a 3+a )整理得 )523(6 1 321a a a a -+= ])1 ,1 ,1 ,4(5)10 ,5 ,1 ,10(2)3 ,1 ,5 ,2(3[61 T T T --+= =(1, 2, 3, 4)T . 3. 已知向量组 A : a 1=(0, 1, 2, 3)T , a 2=(3, 0, 1, 2)T , a 3=(2, 3, 0, 1)T ; B : b 1=(2, 1, 1, 2)T , b 2=(0, -2, 1, 1)T , b 3=(4, 4, 1, 3)T , 证明B 组能由A 组线性表示, 但A 组不能由B 组线性表示. 证明 由 ????? ??-=3121 23111012421301 402230) ,(B A ??? ? ? ??-------971820751610402230 421301 ~r ???? ? ? ?------531400251552000751610 421301 ~r ??? ? ? ? ?-----000000531400751610 421301 ~r 知R (A )=R (A , B )=3, 所以B 组能由A 组线性表示.(完整版)数据结构第二章线性表1答案
线性代数试题及答案.
线性代数习题集(带答案)
第2章线性表(课堂作业)
修订版-线性代数习题三答案
第二章线性表习题及答案
线性代数课后习题1答案(谭琼华版)
第二章_线性表(参考答案)
第2章线性表习题参考答案
线性代数第四版同济大学课后习题答案04