第二章 线性表 答案
数据结构与算法上机作业第二章线性表
一、选择题
1、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新的元素算法的时间复杂度为 C 。
A. O(log2n)
B. O(1)
C. O(n)
D. O(n2)
2、以下关于线性表的说法中，不正确的是 C 。
A. 线性表中的数据元素可以是数字、字符、结构等不同类型
B. 线性表中包含的数据元素个数不是任意的
C. 线性表中的每一个结点都有且只有一个直接前驱和直接后继
D. 存在这样的线性表：表中各结点都没有直接前驱和直接后继
3、在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为 B 。
A. O(1)
B. O(n)
C. O(n2)
D. O(log2n)
4、等概率情况下，在有n个结点的顺序表上做插入结点操作，需平均移动的结点数目为
C 。提示：插入的位置有n+1个，移动总数为：1+2+3+……+n
A. n
B. (n-1)/2
C. n/2
D. (n+1)/2
5、在一个长度为n的顺序存储的线性表中查找值为x的元素时，平均查找长度(及x同元素的平均比较次数，假定查找每个元素的概率都相等)为 C 。
A. n
B. n/2
C. (n+1)/2
D. (n-1)/2
6、在顺序表中，只要知道 D ，就可以求出任一结点的存储地址。
A. 基地址
B. 结点大小
C. 向量大小
D. 基地址和结点大小
7、将两个各有n个元素的有序表归并为一个有序表，其最少的比较次数是 A 。
A. n
B. 2n-1
C. 2n
D. n-1
8、线性表采用链表存储时其存储地址要求 D 。
A. 必须是连续的
B. 部分地址必须是连续的
C. 必须是不连续的
D. 连续的和不连续的都可以
9、下面关于线性表的描述中，错误的是 B 。
A. 线性表采用顺序存储，必须占用一片连续的存储单元
B. 线性表采用顺序存储，便于进行插入和删除操作
C. 线性表采用链式存储，不必占用一片连续的存储单元
D. 线性表采用链式存储，便于插入和删除操作
10、向具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是 B
A. O(1)
B. O(n)
C. O(n2)
D. O(log2n)
11、在一个带头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行的语句是 D 。
A. HL=p; p->next=HL;
B. p->next=HL; HL=p;
C. p->next=HL; p=HL;
D. p->next=HL->next; HL->next=p;
12、在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行的语句是C 。
A. p=q->next; p->next=q->next;
B. p=q->next; q->next=p;
C. p=q->next; q->next=p->next;
D. q->next=q->next->next; q->next=q;
13、设有编号为1, 2, 3, 4的4辆列车，顺序进入一个栈结构的站台，下列不可能的出栈顺序为 D 。
A. 1234
B. 1243
C. 1324
D. 1423
14、4个元素按A, B, C, D顺序进入S栈，执行两次Pop(S, x)运算后，栈顶元素的值是B 。
A. A
B. B
C. C
D. D
15、从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列
A 命令。
A. x=top; top=top->next;
B. top=top->next; x=top->data;
C. x=top->data;
D. x=top->data; top=top->next;
16、向顺序栈中输入元素时 B 。
A. 先存入元素，后移动栈顶指针
B. 先移动栈顶指针，后存入元素
C. 谁先谁后无关紧要
D. 同时进行
17、设有一个顺序栈，元素A, B, C, D, E, F依次进栈，如果6个元素出栈的顺序是B, D, C, F, E, A，则栈的容量至少为 A 。
A. 3
B. 4
C. 5 6. 6
18、设已将元素A, B, C依次入栈，元素D正等待进栈。那么下列4个序列中不可能出现的出栈顺序为 A 。
A. CADB
B. CBDA
C. CDBA
D. DCBA
19、栈和队列的相同之处是 C 。
A.元素的进出满足先进后出
B.元素的进出满足后进先出
C.只允许在端点进行插入和删除操作
D.无共同点
20、设栈S 和队列Q 的初始状态为空,元素e1，e2，e3，e4，e5 和e6 依次通过栈，一个元素出栈后即进入队列Q,若6 个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S 的容量至少应该是 C 。
A. 6
B. 4
C. 3
D. 2
21、队列通常采用的两种存储结构是 A 。
A. 顺序存储结构和链式存储结构
B.散列方式和索引方式
C. 链表存储结构和线性存储结构
D.线性存储结构和非线性存储结构
22、循环队列SQ队满的条件是 D 。
A. SQ->rear==SQ->front
B. (SQ->rear+1)%MAXLEN==SQ->front
C. SQ->rear+2 == SQL->front
D. (SQ->rear+2)%MAXLEN==SQL->front
23、若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为 B 。
A. 5和1
B. 4和2
C. 2和4
D. 1和5
24、链栈与顺序栈相比，有一个较为明显的优点是 A 。
A. 通常不会出现满栈的情况
B. 通常不会出现栈空的情况
C. 插入操作更加方便
D. 删除操作更加方便
25、设用一个大小为M=60的顺序表A[M]表示一个循环队列，如果当前的尾指针rear=32，头指针front=15，则当前循环队列的元素的个数为 C 。
A. 42
B. 17
C. 18
D. 41
26、串是一种特殊的线性表，其特殊性体现在 B 。
A. 可以顺序存储
B. 数据元素是一个字符
C. 可以链式存储
D. 数据元素可以是多个字符
27、设主串的长度为n，模式串的长度为m，则串匹配的KMP算法的时间复杂度为 C 。
A. O(m)
B. O(n)
C. O(m+n)
D. O(m×n)
28、已知串S=“abab”，其Next数组值为 C 。
A. 0123
B. 0121
C. 0112
D. 0122
29、若字符串“ABCDEFG”采用不带表头的链式存储，每个结点保存一个字符。假设每个
字符占用1个字节，每个指针占用两个字节，则该字符串的存储密度为 D 。
A. 20%
B. 40%
C. 50%
D. 33.3%
30、在双向链表中，在指针p所指的结点前插入一个指针q所指向的结点，操作是 C 。
A. p->Prior=q; q->Next=p; p->Prior->next=q; q->Prior=q;
B. p->Prior=q; p->Prior->next=q; q->next=p; q->Prior=p->Prior;
C. q->Next=p; q->Prior=p->Prior; p->Prior->Next=q; p->Prior=q;
D. q->Prior=p->Prior; q->Next=q; p->Prior=q; p->Next=q;
31、已知循环队列存储在一维数组A[0…n-1]中，且队列非空时front和rear分别指向对头元素和队尾元素，且要求第一个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是 B 。
A. 0, 0
B. 0, n-1
C. n-1, 0
D. n-1, n-1
32、某队列允许在两端进行入队操作，但仅允许在一端进行出队操作（称为输出受限的双端队列），若a, b, c, d, e元素依次进队，则不可能得到的顺序是 C 。
A. bacde
B. dbace
C. dbcae
D. ecbad
33、在双向链表中间插入一个结点时，需要修改 D 个指针域。
A. 1
B. 2
C. 3
D. 4
34、在按行优先顺序存储的三元组表中，下述陈述错误的是 D 。
A. 同一行的非零元素，是按列号递增次序存储的
B. 同一列的非零元素，是按行号递增次序存储的
C. 三元组表中三元组行号是非递减的
D. 三元组表中三元组列号是非递减的
35、在稀疏矩阵的三元组表示法中，每个三元组表示 D 。
A. 矩阵中非零元素的值
B. 矩阵中数据元素的行号和列号
C. 矩阵中数据元素的行号、列号和值
D. 矩阵中非零数据元素的行号、列号和值
36、对特殊矩阵采用压缩存储的目的主要是为了 D 。
A. 表达变得简单
B. 对矩阵元素的存取变得简单
C. 去掉矩阵中的多余元素
D. 减少不必要的存储空间
37、广义表是线性表的推广，它们之间的区别在于 A 。
A. 能否使用子表
B. 能否使用原子项
C. 表的长度
D. 是否能为空
38、已知广义表(a, b, c, d)的表头是 A ，表尾是 D 。
A. a
B. ()
C. (a, b, c, d)
D. (b, c, d)
39、下面说法不正确的是 A 。
A. 广义表的表头总是一个广义表
B. 广义表的表尾总是一个广义表
C. 广义表难以用顺序存储结构表示
D. 广义表可以是一个多层次的结构
40、若广义表A满足Head(A)=Tail(A)，则A为 B 。
A. ( )
B. (())
C. (( ),( ))
D. (( ), ( ), ( ))
二、填空题
1、线性表中结点的集合是有限的，结点之间的关系是有序关系。
2、顺序表中访问任一个结点的时间复杂度为O（1）。
3、线性表中第一个结点没有直接前驱，称为头结点。
4、在一个长度为n的顺序表中删除第i个元素，要移动n-i 个元素。
5、在一个长度为n的顺序表中，如果要在第i个元素前插入一个元素，要后移n-i+1 个元素，在插入操作中，移动元素的均值为n/2 。
6、根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成单向链表和双向链表。
7、链式存储的特点是利用next指针来表示数据元素之间的逻辑关系。
8、静态链表(线性表的游标实现)是指用元素的下标表示单链表的指针。
9、在静态链表中，一般都有一个变量available表示的结点链，其中的结点为空闲结点。
10、在栈中，可进行插入和删除操作的一端称栈顶。
11、在进栈运算时，应先判别栈是否满。在出栈运算时应先判别栈是否空。当栈中元素为n个时，进栈运算时发生上溢，则说明该栈的最大容量为n 。
12、设有一空栈，现有输入序列为1, 2, 3, 4, 5，经过push, push, pop, push, pop, push, push, pop, pop之后，输出序列为23541 。
13、对于循环队列Q，求队列长度的公式为(Q.rear-Q.front+maxlength+1)%maxlength 。
14、栈的逻辑特点是先进后出。队列的逻辑特点是先进先出。两者的共同特点是只允许在它们的端点出插入和删除数据元素，区别是栈从一段进出，队列从一端进，另一端出。
15、链队列LQ为空时，LQ->front->next= NULL .
16、在一个链队列LQ中，若队首指针为front，队尾指针为rear，则判断该队列只有一个结点的条件为LQ->front->next!=NULL && LQ->front==LQ-rear 。
17、设串S=“Ilikecomputer”，T=“com”，则Length(S)= 13 。Index(S, T)= 5 。
18、在KMP算法中，next[j]只与模式串有关，而与主无关。
19、字符串“ababaab“的Next数组值是0112342 。
20、稀疏矩阵一般压缩存储的方式有三种，分别是三元组、十字链表和行指针链表。
21、二维数组M中每个元素的长度是3字节，行下标i从0~7，列下标j从0～9，从首地址&M[0][0]开始连续存放在存储器中。若按行优先的方式存放，元素M[7][5]的起始地址为&M[0][0]+7*8+5 ；若按列优先方式存放，元素M[7][5]的起始地址为&M[0][0]+5*10+7 。
22、广义表(a, (a, b), d, e, ((i, j), k))的长度是 5 ，深度是 3 。
23、设广义表A((( ), (a, (b), c)))，则Cal(Cdr(Cal(Cdr(Cal(A))))= (b)
三、写一个算法合并两个已排序的线性表。（用两种方法：数组表示的线性表（顺序表）和指针表示的线性表（链表））
要求：1、定义线性表节点的结构，并定义节点的型和位置的型。
2、定义线性表的基本操作
3、在1，2的基础上，完成本题。
4、在main函数中进行测试：先构建两个有序的线性表，然后合并这两个线性表。
四、已知一个单向链表，试给出复制该链表的算法。
要求：1、定义线性表的节点的结构以及节点的型和位置的型。
2、定义线性表的基本操作
3、在1，2的基础上，完成本题。
4、在main函数中进行测试：先构建一个线性表，并定义一个空线性表，然后进行复
制。
五、写出从一个带表头的单链表中删除其值等于给定值x 的结点的算法函数：
int Delete(LIST &L, int x);如果x 在该链表中，则删除对应结点，并返回其在链表中的位置（逻辑位置，第一个结点的逻辑位置为1），否则返回-1。
要求：1、定义线性表的节点的结构以及节点的型和位置的型。
2、定义线性表的基本操作
3、在1，2的基础上，完成本题。
4、在main 函数中进行测试：先构建一个线性表，然后调用函数删除值等于给定
值的节点。
六、写出一个将两个静态链表（属于同一个存储池）合并的算法函数：
void Merge(cursor M, cursor N); 合并的方法是将N 链表中的所有结点添加到M 链表的后面，并将N 链表的表头结点添加到空闲结点链表中。
要求：1、定义静态链表的结点的结构以及结点的型SPACE 以及位置（position ）和游标（cursor ）的型。
2、定义静态链表的基本操作：void Initialize(); 初始化，将所有存储池中的结点设置为空闲；cursor GetNode(); 从空闲链中获取一个结点；void FreeNode(cursor q); 将结点q 加入到空闲链； void Insert ( elementtype x, position p, cursor M ); 在链表M 中的位置为p 的元素后面添加一个值为x 的结点；void Delete (cursor M, position p ); 在链表M 中删除位置为p 的元素的后一个元素。
3、在1、2的基础上完成本题。
4、在main 函数中进行测试：先构建一个存储池，然后在该存储池中创建两个静态表，最后将这两个静态表合并。
七、利用指针表示的线性表(链表)表示一个多项式，并实现两个多项式的相加和相乘运算。假设多项式形式为：1111...)(e e m e m x a x a t a x A m m +++=--
其中，系数a i ≠0，指数e i 满足e m >e m-1>…>e 2>e 1>=0。
要求：1、定义多项式每一项的结构。
2、定义两个多项式的相加和相乘运算函数。
3、在main 函数中，构建两个多项式，并测试相加和相乘运算。
八、试编写一个整数进制转换的通用函数convert(int num, STACK S, int n)，要求将整数m 转换为n 进制数，n 进制数的各位依次存放在栈S 中。并在主函数中进行测试。 要求：1、定义栈以及栈的型。
2、定义栈的各种操作。
3、实现函数convert 。
4、在main 函数中，通过调用函数convert 将num 的n 进制数存放到一个栈中，并通过出栈的方法输出该n 进制数
九、设有一个循环队列Queue ，只有头指针front ，不设尾指针，另设一个含有元素个数的计数器count ，试写出相应的判断队列空、判断队列满、出队算法和入队算法。
要求：
1、定义相应的循环队列的型（只有头指针，没有尾指针，但有一个元素个数的计数器）；
2、定义该队列的四个算法：判断队列空、判断队列满、出队算法和入队算法；
3、在main函数验证算法的正确性。
十、设主串T=“abcaabbabcabaacbacba“，模式为p=“abcabaa”。
1、计算模式p的nextval函数值
2、不写算法，只画出利用KMP算法进行模式匹配时，每一趟的匹配过程。
要求：
1、写出模式p的nextval值；
2、画出KMP算法的每一趟匹配过程（可参照教材P61从第8行开始的内容）；
3、编程检验p在T中是否存在，如果存在，输出相应的位置，如果不存在，输出-1。
十一、假设表达式中允许包含三种括号：圆括号、方括号和大括号。设计一个算法采用顺序栈（用数组表示的栈）判断表达式中的括号是否正确配对。
要求：
1、定义栈以及栈的型，栈中所存放元素的类型为字符型，定义枚举类型Boolean，其中两个元素分别为TRUE和FALSE。
2、定义栈的各种操作。
3、定义函数Boolean check(char *s); 判断s中的括号是否正确配对，如果正确配对，返回TRUE，否则返回FALSE。
4、在主函数中验证所编写函数的正确性。
十二、设有一个带头结点的双向链表h，设计一个算法用于查找第一个元素之为x的结点，并将其与其前驱结点进行交换。
要求：
1、定义带头结点的双向链表的型DLIST。
2、定义双向链表DLIST的基本操作。
3、定义函数int swap(elementtype x, DLIST &h)，查找第一个元素之为x的结点，如果在链表中存在元素值为x的结点，并其与其前驱结点进行交换，并返回1，否则返回0。
4、在主函数中测试所编写函数的正确性。
十三、试编写一个求三元组顺序表示的具有相同的行值和列值的稀疏矩阵对角线元素之和的算法。
十四、当行值和列值都相同两个稀疏矩阵A和B均以三元组顺序表方式存储时，试写出矩阵相加的算法，其结果存放在以三元组方式存储的矩阵C中。
十五、设有一个稀疏矩阵：
????????????????????--00060000200070000500
0000000810030000000
040 1、写出三元组顺序表存储表示
2、写出十字链表存储的顺序表示
十六、画出广义表LS=(( ), (e), (a, (b, c, d)))的头尾链表存储结构(类似于教材P70图2-27.9)。 要求：按照教材中的事例画出相应的图形，不需要编程。
其中第一个节点如下：
十七、试编写求广义表中原子元素个数的算法。
要求：
1、定义广义表的节点的型；
2、定义广义表的基本操作；
3、定义本题要求的函数int elements(listpointer L)；函数返回值为广义表中原子的个数。例如，广义表(a, b, c, d)原子的个数为4，而广义表(a, (a, b), d, e, ((i, j), k))中院子的个数为3。 提示：先利用基本操作Cal(L)获得表头，判断表头是不是原子，再利用基本操作Cdr(L)获得除第一个元素外的其他元素所形成的表L1，利用递归的方法求L1中原子的个数。
要求：
1、上述作业要求在单独完成；
2、完成后，于规定期限内提交到ftp 服务器的相应目录中中，注意，在提交时将所编写的程序统一拷贝到一个Word 文件中，文件名格式为“学号+姓名”
第二章线性表答案
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．下述哪一条是顺序存储结构的优点？（） 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. 下面的叙述不正确的是（）
线性代数第二章答案
第二章 矩阵及其运算 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.线性表是具有n个的有限序列。 A、表元素 B、字符 C、数据元素 D、数据项 E、信息项 2.线性表的静态链表存储结构与顺序存储结构相比优点是。 A、所有的操作算法实现简单 B、便于随机存储 C、便于插入和删除 D、便于利用零散的存储器空间 3.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为。 A、O(log2n) B、O(1) C、O(n) D、O(n2) 4.（1）静态链表既有顺序存储的特点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关； （2）静态链表中能容纳元素个数的最大数在定义时就确定了，以后不能增加；（3）静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 以上错误的是。 A、（1）、（2） B、（1） C、（1）、（2）、（3） D、（2） 6.在双向链表存储结构中，删除p所指的结点时须修改指针。 A、p－＞next－＞prior=p－＞prior; p－＞prior－＞next=p－＞next; B、p－＞next=p－＞next－＞next;p－＞next－＞prior=p; C、p－＞prior－＞next=p;p－＞prior=p－＞prior－＞prior; D、p－＞prior=p－＞next－＞next;p－＞next=p－＞prior－＞prior;
7.在双向循环链表中，在P指针所指的结点后插入q所指向的新结点，其修改指针的操作是。 A、p－＞next=q; q－＞prior=p;p－＞next－＞prior=q;q－＞next=q; B、p－＞next=q;p－＞next－＞prior=q;q－＞prior=p;q－＞next=p－＞next; C、q－＞prior=p; q－＞next=p－＞next; p－＞next－＞prior=q; p－＞next=q; D、q－＞next=p－＞next;q－＞prior=p;p－＞next=q;p－＞next=q; 8.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。 A、 n b、2n－1 c、2n d、n－1 9.在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动个元素。 A、n－i B、n－i+1 C、n－i－1 D、i 10.线性表L=(a1，a2,……an)，下列说法正确的是。 A、每个元素有有一个直接前驱和一个直接后继 B、线性表中至少有一个元素 C、表中诸元素的排列必须是由小到大或由大到小。 D、除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。 11.对单链表表示法，以下说法错误的是。 A、数据域用于存储线性表的一个数据元素 B、指针域(或链域)用于存放一指向本结点所含数据元素的直接后继所在结点的指针 C、所有数据通过指针的链接而组织成单链表 D、NULL称为空指针，它不指向任何结点只起标志作用
数据结构第二章线性表测试题
第二章线性表 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
数据结构第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、矩阵的定义 由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个列向量(维数相同)对应分量乘积之和.
DS第二章-课后习题答案
第二章线性表 2.1 填空题 (1)一半插入或删除的位置 (2)静态动态 (3)一定不一定 (4)头指针头结点的next 前一个元素的next 2.2 选择题 (1)A (2) DA GKHDA EL IAF IFA(IDA) (3)D (4)D (5) D 2.3 头指针：在带头结点的链表中，头指针存储头结点的地址；在不带头结点的链表中，头指针存放第一个元素结点的地址； 头结点：为了操作方便，在第一个元素结点前申请一个结点，其指针域存放第一个元素结点的地址，数据域可以什么都不放； 首元素结点：第一个元素的结点。 2.4已知顺序表L递增有序，写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 void InserList(SeqList *L,ElemType x) { int i=L->last; if(L->last>=MAXSIZE-1) return FALSE; //顺序表已满 while(i>=0 && L->elem[i]>x) { L->elem[i+1]=L->elem[i]; i--; } L->elem[i+1]=x; L->last++; } 2.5 删除顺序表中从i开始的k个元素 int DelList(SeqList *L,int i,int k) { int j,l; if(i<=0||i>L->last) {printf("The Initial Position is Error!"); return 0;} if(k<=0) return 1; /*No Need to Delete*/ if(i+k-2>=L->last) L->last=L->last-k; /*modify the length*/
第二章线性表测试题
第二章测试试题 班级：学号：姓名：成绩： 一、选择题（每小题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的链表的结点仍依元素值递增有序存放。（注意：并集不是归并）
第二章线性表答案
第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
线性代数课后习题答案(陈维新)
第一章 行列式 习题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 ?。
第2章线性表(课堂作业)
第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.线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。（） 选择题 1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( ) （A）110 （B）108 （C）100 （D）120 3. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。 （A）64 （B）63 （C）63.5 （D）7 4.线性表采用链式存储结构时，其地址（）。 (A) 必须是连续的 (B) 部分地址必须是连续的 (C) 一定是不连续的 (D) 连续与否均可以 5. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（） （A）s->next=p;p->next=s; （B） s->next=p->next;p->next=s; （C）s->next=p->next;p=s; （D）p->next=s;s->next=p; 6.在一个单链表中，若删除p所指结点的后续结点，则执行（） （A）p->next=p->next->next; （B）p=p->next; p->next=p->next->next; （C）p->next=p->next; （D）p =p->next->next; 7.下列有关线性表的叙述中，正确的是（） （A）线性表中的元素之间隔是线性关系 （B）线性表中至少有一个元素 （C）线性表中任何一个元素有且仅有一个直接前趋 （D）线性表中任何一个元素有且仅有一个直接后继 8.线性表是具有n个（）的有限序列（n≠0) （A）表元素（B）字符（C）数据元素（D）数据项 填空题 1.已知P为单链表中的非首尾结点，在P结点后插入S结点的语句为：( ) 。 2.顺序表中逻辑上相邻的元素物理位置(一定 )相邻，单链表中逻辑上相邻的元素物理位置( )相邻。
第二章线性表习题及答案
第二章线性表习题及答案 一、基础知识题 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 已知线性变换 ?????++=++=++=3 21332123 2113235322y y y x y y y x y y y x , 求从变量x 1 x 2 x 3到变量y 1 y 2 y 3的线性变换 解 由已知 ? ??? ?????? ? ?=???? ??22 1321323513122y 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 已知两个线性变换 ?????++=++-=+=3 2133 2123 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 ??? ? ?????? ??----=32 1161109412316z z z
所以有?????+--=+-=++-=3 2133 2123 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.一个线性表第一个元素的存储地址是100,每个元素的长度为4,则第5个元素的地址是( ) A.110 B.116 C.100 D.120 2. 向一个有128个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。 A.64 B.63 C.63.5 D.7 3．在循环双链表的p所指接点之前插入s所指接点的操作是 A.p-> prior =s;s-> next t=p;p-> prior t->left=s;s-> prior =p-> prior; B. p-> prior =s;p-> prior -> next =s;s-> next =p;s-> prior =p-> prior; C.s-> next =p;s-> prior =p-> prior;p-> prior =s;p-> prior -> next =s; D.s-> next =p;s-> prior =p-> prior;p-> prior -> next =s;p-> prior =s; 4．从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（）个结点。 A.n B.n/2 C.(n-1)/2 D.(n+1)/2 5．线性表是具有n个（）的有限序列（n≠0） A.表元素 B.字符 C.数据元素 D.数据项 6．非空的循环单链表head的尾结点（由P指向）满足 A. p->next=NULL B. p=NULL C. p->next=head D.p=head 7．在一个单链表中已知q所指的结点是p所指结点的前驱结点，若在q和p之间插入s 结点，则执行( ) 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; 8．已知一个顺序存储线性表，若第1个结点的地址d，第3个的地址是5d，则第n个结点的地址为( ) A．[2*(n-1)+1]*d B.2*(n-1)*d C.[2*(n-1)-1]*d D.(n+1)*d 9．在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( ) A.O(1) B.O(n) C.O(n2) D.O(nlog2n) 10．如果最常用的操作是提取第i个结点及其前驱，则采用( )存储方式最节省时间。 A．单链表 B.顺序表 C.循环链表 D.双链表 11．在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n)之前插入一个新元素时，需要从后向前依次后移( )个元素。 A.n-i B.n-i+1 C.n-i-1 D.i 12．在一个长度为n的顺序存储线性表中，删除第i个元素(0≤i≤n-1)时，需要从后向
线性代数第二章习题答案
习 题 2-1 1．由6名选手参加乒乓球比赛，成绩如下：选手1胜选手2、4、5、6而负于选手3；选手2胜选手4、5、6而负于选手1、3；选手3胜选手1、2、4而负于选手5、6；选手4胜选手5、6而负于选手1、2、3；选手5胜选手3、6而负于选手1、2、4；选手6胜选手2而负于选手1、3、4、5．若胜一场得1分，负一场得0分，使用矩阵表示输赢状况，并排序． 解： ????? ?? ? ? ? ??000010 100100110000001011 1110001110106543216 54321，选手按胜多负少排序为：6,5,4,3,2,1． 2．设矩阵???? ??-=???? ?? +-=2521 ,03231 z x y x B A ，已知B A =，求z y x ,,． 解：由于B A =得?????=-=+=-0253223z x y x ，解得：?? ? ??===211 z y x 。 习 题 2-2 1．设???? ??=0112A ，??? ? ??-=4021B ，求 （1）B A 52-； （2）BA AB -； （3）2 2B A -． 解：（1）??? ? ??--=???? ??--???? ??=???? ??--???? ??=-202892001050224402150112252B A ； （2）???? ??--=???? ??--???? ??--=???? ?????? ??--???? ??-???? ??=-2592041021820112402140210112BA AB ； （3）??? ? ??--=???? ??-???? ??=???? ??-???? ??--???? ?????? ??=-152441606112254021402101120112B A 22． 2．已知????? ??--=230412301321A ，??? ? ? ??---=052110 35123 4B ，求B A 23-． 解：??? ? ? ??----????? ??--=052110351234223041230 13 21 323B -A ??? ? ? ??----=????? ??----????? ??--=61941016151055011010422061024686901236903963 3．设??? ? ? ??----=????? ??=101012121234,432112 122121B A ，求