线性表习题参考答案
习题二参考答案
一、选择题
1. 链式存储结构的最大优点是（ D ）。
A.便于随机存取
B.存储密度高
C.无需预分配空间
D.便于进行插入和删除操作
2. 假设在顺序表{a 0,a 1,……,a n －1}中，每一个数据元素所占的存储单元的数目为4，且第0个数据元素的存储地址为100，则第7个数据元素的存储地址是（ D ）。
A. 106
B. 107
C.124
3. 在线性表中若经常要存取第i 个数据元素及其前趋，则宜采用（ A ）存储方式。
A.顺序表
B. 带头结点的单链表
C.不带头结点的单链表
D. 循环单链表
4. 在链表中若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，则宜采用（ C ）存储方式。
A. 顺序表
B. 用头指针标识的循环单链表
C. 用尾指针标识的循环单链表
D. 双向链表
5. 在一个单链表中的p 和q 两个结点之间插入一个新结点，假设新结点为S,则修改链的java 语句序列是（ D ）。
A. (p); (s);
B. ()); (p);
C. ()); (p);
D. (s); (q);
6. 在一个含有n 个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度是（ C ）。
A. O(1)
B. O(log 2n)
C. O(n)
D. O(n2)
7. 要将一个顺序表{a 0,a 1,……,a n-1}中第i 个数据元素a i (0≤i ≤n-1)删除，需要移动（ B ）个数据元素。
A. i
B. n-i-1
C. n-i
D. n-i+1
8. 在带头结点的双向循环链表中的p 结点之后插入一个新结点s ，其修改链的java 语句序列是（ D ）。
A. (s); (p); ().setPrior(s);
());
B. (s); ().setPrior(s); (p);
());
C. (p); ()); (s);
().setPrior(s);
D. ()); (p); ().setPrior(s);
(s);
9. 顺序表的存储密度是（ B ），而单链表的存储密度是（ A ）。
A ．小于1 B. 等于1 C. 大于1 D. 不能确定
10. 对于图所示的单链表，下列表达式值为真的是（ D ）。
图 单链表head 的存储结构图 A. ().getData()=='C' B. ()=='B'
C. ()==’D ’
D. ()==null
二、填空题
1. 线性表是由n （n ≥0）个数据元素所构成的 有限序列 ，其中n 为数据元素的个数，称为线性表的 长度 ，n=0的线性表称为 空表 。
2. 线性表中有且仅有一个开始结点和终端结点，除开始结点和终端结点之外，其它每一个数据元素有且仅有一
个前驱，有且仅有一个后继。
3.线性表通常采用顺序存储和链式存储两种存储结构。若线性表的长度确定或变化不大，则适合采用顺序
存储存储结构进行存储。
4.在顺序表{a0,a1,……,a n-1}中的第i(0≤i≤n-1)个位置之前插入一个新的数据元素，会引起 n-i 个数据元素
的移动操作。
5.在线性表的单链表存储结构中，每一个结点有两个域，一个是数据域，用于存储数据元素值本身，另一个是指
针域，用于存储后继结点的地址。
6.在线性表的顺序存储结构中可实现快速的随机存取，而在链式存储结构中则只能进行
顺序存取。
7.顺序表中逻辑上相邻的数据元素，其物理位置一定相邻，而在单链表中逻辑上相邻的数据元素，其物理位
置不一定相邻。
8.在仅设置了尾指针的循环链表中，访问第一个结点的时间复杂度是 O（1）。
9.在含有n个结点的单链表中，若要删除一个指定的结点p，则首先必须找到指定结点p的前驱，其时间复
杂度为 O（n）。
10.若将单链表中的最后一个结点的指针域值改为单链表中头结点的地址值，则这个链表就构成了循环单链
表。
三、算法设计题
1.编写一个顺序表类的成员函数，实现对顺序表就地逆置的操作。所谓逆置，就是把（a1,a2,…,a n）变成
（a n,a n-1,…,a1）；所谓就地，就是指逆置后的数据元素仍存储在原来顺序表的存储空间中，即不为逆置后的顺序表另外分配存储空间。
参考答案:
public void reverse() {
for (int i = 0,j=curLen-1; i < j; i++,j--) {
Object temp = listElem[i];
listElem[i] = listElem[j];
listElem[j] = temp;
}
}
2.编写一个顺序表类的成员函数，实现对顺序表循环右移k位的操作。即原来顺序表为（a1,a2,…,a n-k,a n-k+1,…,
a n），循环向右移动k位后变成（a n-k+1,…, a n ,a1,a2,…,a n-k）。要求时间复杂度为O（n）。
参考答案:
public void shit(int k) {
int n=curLen,p=0,i,j,l;
Object temp;
for(i=1;i<=k;i++)
if(n%i==0&&k%i==0) ....直到最终回到listElem[0].然而这并没有全部解决问题,因为有可能有的元素在此过程中始终没有被访问过,而是被跳了过去.分析可知,当n和k的最大公约数为p时,只要分别以
listElem[0], listElem[1],... listElem[p-1]为起点执行上述算法,就可以保证每一个元素都被且仅被右移一次,从而满足题目要求.也就是说,A的所有元素分别处在p个"循环链"上面.举例如下:
n=15,k=6,则p=3.
第一条链: listElem[0]->listElem[6], listElem[6]->listElem[12], listElem[12]-> listElem[3], listElem[3]-> listElem[9], listElem[9]-> listElem[0].
第二条链: listElem[1]->listElem[7], listElem[7]->listElem[13], listElem[13]-> listElem[4], listElem[4]->listElem[10], listElem[10]-> listElem[1].
第三条链: listElem[2]-> listElem[8], listElem[8]-> listElem[14], listElem[14]->listElem[5], listElem[5]->listElem[11], listElem[11]->listElem[2].
恰好使所有元素都右移一次.
虽然未经数学证明,但相信上述规律应该是正确的.
3.编写一个单链表类的成员函数，实现在非递减的有序单链表中插入一个值为x的数据元素，并使单链表仍保
持有序的操作。
参考答案(方法一):
public void insert(int x) {
Node p = ();ntValue();
if (temp < x) {
q = p;
p = ();
} else
break;
}
Node s = new Node(x); etData()).intValue() p = (); } Node s = new Node(x); quals(x)) { q=p; p = ();quals(x)) { ()); ++j;etNext();// 原多项式的首结点 while (p!=()) { PolynNode data = (PolynNode) (); int expn = (); if (expn % 2 != 0) {// 加入奇次项多项式 (p); p1 = p; } else {// 加入偶此项多项式 (p); p2 = p; } p = (); } ()); ()); CircleLinkList[] polyns = { cList1, cList2 }; return polyns; } 线性代数（A 卷） 一﹑选择题(每小题3分,共15分) 1. 设A ﹑B 是任意n 阶方阵,那么下列等式必成立的是( ) (A)AB BA = (B)222()AB A B = (C)222()2A B A AB B +=++ (D)A B B A +=+ 2. 如果n 元齐次线性方程组0AX =有基础解系并且基础解系含有()s s n <个解向量,那么矩阵A 的秩为( ) (A) n (B) s (C) n s - (D) 以上答案都不正确 3.如果三阶方阵33()ij A a ?=的特征值为1,2,5,那么112233a a a ++及A 分别等于( ) (A) 10, 8 (B) 8, 10 (C) 10, 8-- (D) 10, 8-- 4. 设实二次型11212222(,)(,)41x f x x x x x ?? ??= ? ?-???? 的矩阵为A ,那么( ) (A) 2331A ??= ?-?? (B) 2241A ??= ?-?? (C) 2121A ??= ? -?? (D) 1001A ?? = ??? 5. 若方阵A 的行列式0A =，则( ) (A) A 的行向量组和列向量组均线性相关 (B)A 的行向量组线性相关,列向量组线性无关 (C) A 的行向量组和列向量组均线性无关 (D)A 的列向量组线性相关,行向量组线性无关 二﹑填空题(每小题3分,共30分) 1 如果行列式D 有两列的元对应成比例,那么该行列式等于 ； 2. 设100210341A -?? ? =- ? ?-?? ，*A 是A 的伴随矩阵，则*1()A -= ； 3. 设α,β是非齐次线性方程组AX b =的解,若λαμβ+也是它的解, 那么λμ+= ； 4. 设向量(1,1,1)T α=-与向量(2,5,)T t β=正交,则t = ； 5. 设A 为正交矩阵,则A = ； 一．选择题 1. 已知在单链表中指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作？（ B ） 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； 2. 非空的循环单链表first的尾结点（由p所指向）满足：（ C ） A、 p->next == NULL； B、 p == NULL； C、 p->next == first； D、 p == first； 3. 在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）插入一个新元素时，需要从后向前依次后移___C___个元素。 A、n-i B、n-i-1 C、n-i+1 D、i 4. 线性表是具有n个__C____的有限序列。 A、表元素 B、字符 C、数据元素 D、数据项 5. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较___B___个结点。 A、 n B、n/2 C、(n-1)/2 D、(n+1)/2 6. 若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用___A___存储方式最节省运算时间。 A、单链表 B、双链表 C、单循环链表 D、带头结点的双循环链表 7. 已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a.在P结点后插入S结点的语句序列是：＿＿。 b.在P结点前插入S结点的语句序列是：。 c.在表首插入S结点的语句序列是：。 d.在表尾插入S结点的语句序列是：。 供选择的语句有： （1）P->next=S;（2）P->next=P->next->next; （3）P->next=S->next;（4）S->next=P->next; （5）S->next=L;（6）S->next=NULL;（7）Q=P; （8）while(P->next!=Q)P=P->next; （9）while(P->next!=NULL)P=P->next; （10）P=Q;（11）P=L;（12）L=S;（13）L=P; 二．填空题 1．在顺序表中插入或删除一个元素，需要平均移动________元素，具体移动的元素个数与_______有关。 2．在顺序表中，逻辑上相邻的元素，其物理位置________相邻。在单链表中，逻辑上相邻的元素，其物理位置__________相邻。 3．在带头结点的非空单链表中，头结点的存储位置由___________指示，首元素结点的存储位置由_________指示，除首元素结点外，其它任一元素结点的存储位置由_______指示。4.当对一个基本线性表进行的插入和删除操作较频繁时，基本线性表应采用存储结构；当对基本线性表的操作不会引起它的变化时，基本线性表应采用存储结构。 5.设某有一双链表，若要在指针q所指结点（中间结点）的后面插入一个新结点s，则需要执行下述语句段： s->prior=q；s->next=q->next；；q->next=s; 一、 已知线性约束条件,探求线性目标关系最值问题 1. 设变量x 、y 满足约束条件?? ???≥+-≥-≤-1122y x y x y x ,则y x z 32+=的最大值为 。 二、 已知线性约束条件,探求非线性目标关系最值问题 2. 已知1,10,220x x y x y ≥??-+≤??--≤? 则22x y +的最小值就是 。 3. 已知变量x,y 满足约束条件+201-70x y x x y -≤??≥??+≤? ,则 y x 的取值范围就是( )、 A 、 [95,6] B 、(－∞,95 ]∪[6,＋∞) C 、(－∞,3]∪[6,＋∞) D 、 [3,6] 三、 研究线性规划中的整点最优解问题 4. 某公司招收男职员x 名,女职员y 名,x 与y 须满足约束条件?? ???≤≥+-≥-.112,932,22115x y x y x 则1010z x y =+的最大值 就是 。 四、 已知最优解成立条件,探求目标函数参数范围问题 5. 已知变量x ,y 满足约束条件1422x y x y ≤+≤??-≤-≤? 。若目标函数z ax y =+(其中0a >)仅在点(3,1)处取得最大值,则a 的取值范围为 。 6. 已知x 、y 满足以下约束条件5503x y x y x +≥??-+≤??≤? ,使z=x+a y (a >0) 取得最小值的最优解有无数个,则a 的值为( ) A. －3 B 、 3 C 、 －1 D 、 1 五、 求可行域的面积 7. 不等式组260302x y x y y +-≥??+-≤??≤? 表示的平面区域的面积为 ( ) A. 4 B 、 1 C 、 5 D 、 无穷大 线性代数考试题库及答案 第一部分 客观题（共30分） 一、单项选择题（共 10小题，每小题2分，共20分） 1. 若行列式11 121321 222331 32 33 a a a a a a d a a a =，则212223 11 121331 32 33 232323a a a a a a a a a 等于 ( ) (A) 2d (B) 3d (C) 6d (D) 6d - 2. 设123010111A ?? ? =- ? ??? ，ij M 是A 中元素ij a 的余子式，则313233M M M -+=（ ） (A) 0 (B) 1 (C) 2 (D) 3 3. 设A 为n 阶可逆矩阵，则下列各式恒成立的是（ ） (A) |2|2||T A A = (B) 11(2)2A A --= (C) *1A A -= (D) 11[()][()]T T T T A A --= 4. 初等矩阵满足（ ） (A) 任两个之乘积仍是初等矩阵 (B) 任两个之和仍是初等矩阵 (C) 都是可逆矩阵 (D) 所对应的行列式的值为1 5. 下列不是．．n 阶矩阵A 可逆的充要条件为（ ） (A) 0≠A (B) A 可以表示成有限个初等阵的乘积 (C) 伴随矩阵存在 (D) A 的等价标准型为单位矩阵 6. 设A 为m n ?矩阵，C 为n 阶可逆矩阵，B AC =，则 ( )。 (A) 秩(A )> 秩(B ) (B) 秩(A )= 秩(B ) (C) 秩(A )< 秩(B ) (D) 秩(A )与秩(B )的关系依C 而定 7. 如果向量β可由向量组12,, ,s ααα线性表示,则下列结论中正确的是（ ） (A) 存在一组不全为零的数12,,s k k k ，使得1122s s k k k βααα=+++ 成立 (B) 存在一组全为零的数12,,s k k k ，使得1122s s k k k βααα=++ + 成立 (C) 存在一组数12,, s k k k ，使得1122s s k k k βααα=+++ 成立 (D) 对β的线性表达式唯一 8. 设12,ξξ是齐次线性方程组0AX =的解，12,ηη是非齐次线性方程组AX b =的解，则（ ） (A) 112ξη+为0AX =的解 (B) 12ηη+为AX b =的解 (C) 12ξξ+为0AX =的解 (D) 12ηη-为AX b =的解 9. 设110101011A ?? ? = ? ??? ,则A 的特征值是( )。 (A) 0,1,1 (B) 1,1,2 (C) 1,1,2- (D) 1,1,1- 10. 若n 阶方阵A 与某对角阵相似，则 ( )。 (A) ()r A n = (B) A 有n 个互不相同的特征值 (C) A 有n 个线性无关的特征向量 (D) A 必为对称矩阵 二、判断题（共 10小题，每小题1分，共10分 ）注：正确选择A,错误选择B. 11. 设A 和B 为n 阶方阵，则有22()()A B A B A B +-=-。（ ） 12. 当n 为奇数时，n 阶反对称矩阵A 是奇异矩阵。（ ） 第2章线性表 一选择题 1．下述哪一条是顺序存储结构的优点？（）【北方交通大学 2001 一、4（2分）】A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示 2．下面关于线性表的叙述中，错误的是哪一个？（）【北方交通大学 2001 一、14（2分）】 A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具有n个（）的有限序列（n>0）。【清华大学 1998 一、4（2分）】A．表元素 B．字符 C．数据元素 D．数据项 E．信息项 4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。【哈尔滨工业大学 2001 二、1（2分）】A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。【南开大学 2000 一、3】 A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表 6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 【合肥工业大学 2000 一、1（2分）】 7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（）存储方式最节省运算时间。【北京理工大学 2000 一、1（2分）】A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表 8. 静态链表中指针表示的是（）. 【北京理工大学 2001 六、2（2分）】 A．内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址 9. 链表不具有的特点是（）【福州大学 1998 一、8 (2分)】 A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 10. 下面的叙述不正确的是（）【南京理工大学 1996 一、10（2分）】 A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关 11. 线性表的表元存储方式有(（1）)和链接两种。试指出下列各表中使用的是何种存储方式：表1是(（2）)存储方式；表2是(（3）)存储方式；表3是(（4）)存储方式；表4是(（5）)存储方式。表左的s指向起始表元。 信号与系统期末考试试题 一、选择题（共10题，每题3分 ，共30分，每题给出四个答案，其中只有一个正确的） 1、 卷积f 1(k+5)*f 2(k-3) 等于 。 （A ）f 1(k)*f 2(k) （B ）f 1(k)*f 2(k-8)（C ）f 1(k)*f 2(k+8)（D ）f 1(k+3)*f 2(k-3) 2、 积分 dt t t ? ∞ ∞ --+)21()2(δ等于 。 （A ）1.25（B ）2.5（C ）3（D ）5 3、 序列f(k)=-u(-k)的z 变换等于 。 （A ） 1-z z （B ）-1-z z （C ）11-z （D ）1 1--z 4、 若y(t)=f(t)*h(t),则f(2t)*h(2t)等于 。 （A ） )2(41t y （B ）)2(21t y （C ）)4(41t y （D ）)4(2 1 t y 5、 已知一个线性时不变系统的阶跃相应g(t)=2e -2t u(t)+)(t δ,当输入f(t)=3e —t u(t)时，系 统的零状态响应y f (t)等于 （A ）(-9e -t +12e -2t )u(t) （B ）(3-9e -t +12e -2t )u(t) （C ）)(t δ+(-6e -t +8e -2t )u(t) （D ）3)(t δ +(-9e -t +12e -2t )u(t) 6、 连续周期信号的频谱具有 （A ） 连续性、周期性 （B ）连续性、收敛性 （C ）离散性、周期性 （D ）离散性、收敛性 7、 周期序列2)455.1(0 +k COS π的 周期N 等于 （A ） 1（B ）2（C ）3（D ）4 8、序列和 ()∑∞ -∞ =-k k 1δ等于 （A ）1 (B) ∞ (C) ()1-k u (D) ()1-k ku 9、单边拉普拉斯变换()s e s s s F 22 12-+= 的愿函数等于 ()()t tu A ()()2-t tu B ()()()t u t C 2- ()()()22--t u t D 10、信号()()23-=-t u te t f t 的单边拉氏变换()s F 等于 ()A ()()()232372+++-s e s s ()() 2 23+-s e B s 线性规划常见题型及解法 求线性目标函数的取值范围 2 2 2 x y A D y 2 O x x=2 求可行域的面积 y y M 5 2 x y 2 y x y 2 x y 2 x y x (3,5] y =2 ( 13 例1 x+2y 时 6 的点 C 、 x ， 个 y 6 y 3 2 x + y —3 = 0 C 、 5 A 、 4 B 、 1 D 、无穷大 () 0,将 有 最小值 故选A .B A --- 作出可行域如右图 点个数为13个，选D x + y =2 则z=x+2y 的取值范围是 () 旦y =2 0 0表示的平面区域的面积为 三、求可行域中整点个数 解：|x| + |y| <2等价于 解：如图，作出可行域，作直线I : I 向右上方平移，过点A ( 2,0 ) 2,过点B ( 2,2 )时，有最大值 [2,6] B 、[2 ,5] C 、[3,6] 解：如图，作出可行域，△ ABC 的面积即为所求，由梯形OMBC 的面积减去梯形OMAC 的 面积即可，选B 例 3、满足 |x| + |y| <2 A 、9 个 B 、10 个 由已知条件写出约束条件，并作出可行域，进而通过平移直线在可行域内求线性 目标函数的最优解是最常见的题型，除此之外，还有以下六类常见题型。 (x 0,y 0) (x 0,y p 0) (xp 0,y 0) (xp 0,y p 0) 是正方形内部(包括边界)，容易得到整 y)中整点(横纵坐标都是整数)有() D 、 14 个 2x 例2、不等式组x x 若x 、y 满足约束条件 y O C V —? x 2x + y —6= 0 东 北 大 学 考 试 试 卷（A 卷） 2010 — 2011学年 第二学期 课程名称：线性代数 （共2页） ┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄ (15分) 设三阶矩阵()321,,ααα=A ， ()3323214,3,32αααααα+-+=B ， 且A 的行列式1||=A ，求矩阵B 的行列式||B . 解 因为()3323214,3,32αααααα+-+=B ＝? ???? ??-413031002),,(321ααα， 所以，24413031002||||=-=A B 分) 设向量组????? ??-=2111α，????? ??=1122α，????? ??=a 213α线性相关，向量 ???? ? ??=b 13β可由向量组321,,ααα线性表示，求b a ,的值。 解 由于 ????? ??-=b a 1212113121),,,(321βααα????? ??---→62304330312 1b a ? ???? ??-+→210043303121b a 所以，.2,1=-=b a 三分) 证明所有二阶实对称矩阵组成的集合V 是R 2? 2 的子空间，试在 V 上定义内积运算，使V 成为欧几里得空间，并给出V 的一组正交基. 解 由于任意两个二阶实对称矩阵的和还是二阶实对称矩阵，数乘二阶实对称矩阵还是 二阶实对称矩阵，即V 对线性运算封闭，所以V 是R 2? 2 的子空间。 对任意V b b b b B a a a a A ∈??? ? ??=???? ??=2212121122121211,,定义内积：[A,B]=222212121111b a b a b a ++， 显然满足：[A,B]=[B,A], [kA,B]=k[A,B], [A,A]≥0且[A,A]=0当且仅当A=0. ???? ??=00011A ,???? ??=01102A ,???? ??=10003A 就是V 的一组正交基. 注：内积和正交基都是不唯一的. 2－1 第二章线性表练习题 一、选择题 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、若x、y满足约束条件 2 2 2 x y x y ≤ ? ? ≤ ? ?+≥ ? ，则z=x+2y的取值范围是（） A、[2,6] B、[2,5] C、[3,6] D、（3,5] 解：如图，作出可行域，作直线l：x+2y＝0，将l向右上方平移，过点A（2,0）时，有最小值2，过点B（2,2）时，有最大值6，故选 A 二、求可行域的面积 例2、不等式组 260 30 2 x y x y y +-≥ ? ? +-≤ ? ?≤ ? 表示的平面区域的面积为（） A、4 B、1 C、5 D、无穷大 解：如图，作出可行域，△ABC的面积即为所求，由梯形OMBC 的面积减去梯形OMAC的面积即可，选 B 三、求可行域中整点个数 例3、满足|x|＋|y|≤2的点（x，y）中整点（横纵坐标都是整数）有（） A、9个 B、10个 C、13个 D、14个 解：|x|＋|y|≤2等价于 2(0,0) 2(0,0) 2(0,0) 2(0,0) x y x y x y x y x y x y x y x y +≤≥≥ ? ?-≤≥ ? ? -+≤≥? ?--≤ ? 作出可行域如右图，是正方形内部（包括边界），容易得到整点个数为13个，选 D 四、求线性目标函数中参数的取值范围 例4、已知x、y满足以下约束条件 5 50 3 x y x y x +≥ ? ? -+≤ ? ?≤ ? ，使z=x+ay(a>0) 取得最小值的最优解有无数个，则a的值为（） A、－3 B、3 C、－1 D、1 解：如图，作出可行域，作直线l：x+ay＝0，要使目标函数z=x+ay(a>0)取得最小值的最优解有无数个，则将l向右上方平移后与直线x+y＝5重合，故a=1，选 D 五、求非线性目标函数的最值 例5、已知x、y满足以下约束条件 220 240 330 x y x y x y +-≥ ? ? -+≥ ? ?--≤ ? ，则z=x2+y2的最大值和最小值分别是（） A、13，1 B、13，2 C、13，4 5 D 、 解：如图，作出可行域,x2+y2是点（x，y）到原点的距离的平方，故最大值为点A（2,3）到原点的距离的平方，即|AO|2=13，最小值为原点到直线2x＋y－2=0的距离的平方， 即为4 5 ，选 C 六、求约束条件中参数的取值范围 例6、已知|2x－y＋m|＜3表示的平面区域包含点（0,0）和（－1,1），则m的取值范围是（） A、（-3,6） B、（0,6） C、（0,3） D、（-3,3） 解：|2x－y＋m|＜3等价于 230 230 x y m x y m -++>? ? -+- ? ? -< ? ,故0＜m＜3，选 C 第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 ）； 重庆大学信号与线性系统期末考试试题 一、填空题：（30分，每小题3分） 1. =-? ∞ ∞ -dt t t )()5cos 2(δ 。 2. ()dt t e t 12-?+∞ ∞ --δ= 。 3. 已知 f (t )的傅里叶变换为F (j ω), 则f (2t -3)的傅里叶变换为 。 4. 已知 6 51 )(2 +++= s s s s F ，则=+)0(f ; =∞)(f 。 5. 已知 ω ωπδεj t FT 1 )()]([+=，则=)]([t t FT ε 。 6. 已知周期信号 )4sin()2cos()(t t t f +=，其基波频率为 rad/s ； 周期为 s 。 7. 已知 )5(2)2(3)(-+-=n n k f δδ，其Z 变换 =)(Z F ；收敛域为 。 8. 已知连续系统函数1342 3)(2 3+--+= s s s s s H ，试判断系统的稳定性： 。 9．已知离散系统函数1.07.02 )(2+-+=z z z z H ，试判断系统的稳定性： 。 10．如图所示是离散系统的Z 域框图，该系统的系统函数H(z)= 。 二．(15分)如下方程和非零起始条件表示的连续时间因果LTI 系统， ?????==+=++-- 5 )0(',2)0() (52)(4522y y t f dt df t y dt dy dt y d 已知输入 )()(2t e t f t ε-=时，试用拉普拉斯变换的方法求系统的零状态响应 )(t y zs 和零输入响应)(t y zi ，0≥t 以及系统的全响应),(t y 0≥t 。 三．（14分） ① 已知2 36 62)(22++++=s s s s s F ,2]Re[->s ,试求其拉氏逆变换f (t )； ② 已知) 2(2 35)(2>+-=z z z z z X ，试求其逆Z 变换)(n x 。 四 （10分）计算下列卷积： 1. }1,0,6,4,3{}4,1,2,1{)()(21--*=*k f k f ； 2． )(3)(23t e t e t t εε--* 。 高考线性规划归类解析 一、平面区域和约束条件对应关系。 例1、已知双曲线224x y -=的两条渐近线与直线3x =围成一个三角形区域,表示该区域的不等式组是（） (A)0003x y x y x -≥??+≥??≤≤? (B)0003x y x y x -≥?? +≤??≤≤? (C) 003x y x y x -≤?? +≤??≤≤? (D) 0003x y x y x -≤?? +≥??≤≤? 解析：双曲线224x y -=的两条渐近线方程为y x =±，与直线3x =围 成一个三角形区域（如图4所示）时有0 003x y x y x -≥?? +≥??≤≤? 。 点评：本题考查双曲线的渐近线方程以及线性规划问题。验证法或排除法是最效的方法。 例2：在平面直角坐标系中，不等式组20 200x y x y y +-≤??-+≥??≥? 表示的平面区域的面积是（） (A)42 (B)4 (C) 22 (D)2 解析：如图６，作出可行域，易知不等式组20 200x y x y y +-≤??-+≥??≥? 表示的平面区域是一个三角形。容 易求三角形的三个顶点坐标为Ａ（０，２），B(2,0),C(-2,0).于是三角形的面积为： 11 ||||42 4.22 S BC AO =?=??=从而选Ｂ。 点评：有关平面区域的面积问题，首先作出可行域，探求平面区域图形的性质；其次利用面积公式整体或部分求解是关键。 二、已知线性约束条件，探求线性截距——加减的形式(非线性距离——平方的形式，斜率——商的形式)目标关系最值问题（重点） 例3、设变量x 、y 满足约束条件?? ? ??≥+-≥-≤-1122y x y x y x ，则 ①y x 32+的最大值为 。（截距） 解析：如图1，画出可行域，得在直线 2x-y=2与直线x-y=-1 的交点A(3,4)处，目标函数z 最大值为18 点评：本题主要考查线性规划问题,由线性约束条件画出可行域,然后求出目标函数的最大值.，是一道较为简单的送分题。数形结合是数学思想的重要手段之一。 ②则2 2 x y +的最小值是 . ③1y x =+的取值范围是 . 图1 线性代数习题和答案 第一部分选择题(共28分) 一、单项选择题（本大题共14小题，每小题2分，共28分）在每小题列出的四个选项中只有 一个是符合题目要求的，请将其代码填在题后的括号内。错选或未选均无分。 1.设行列式a a a a 1112 2122 =m， a a a a 1311 2321 =n，则行列式 a a a a a a 111213 212223 + + 等于（） A. m+n B. -(m+n) C. n-m D. m-n 2.设矩阵A= 100 020 003 ? ? ? ? ? ? ? ，则A-1等于（） A. 1 3 00 1 2 001 ? ? ? ? ? ? ? ? ? ? B. 100 1 2 00 1 3 ? ? ? ? ? ? ? ? ?? C. 1 3 00 010 00 1 2 ? ? ? ? ? ? ? ?? D. 1 2 00 1 3 001 ? ? ? ? ? ? ? ? ? ? 3.设矩阵A= 312 101 214 - - - ? ? ? ? ? ? ? ，A*是A的伴随矩阵，则A *中位于（1，2）的元素是（） A. –6 B. 6 C. 2 D. –2 4.设A是方阵，如有矩阵关系式AB=AC，则必有（） A. A =0 B. B≠C时A=0 C. A≠0时B=C D. |A|≠0时B=C 5.已知3×4矩阵A的行向量组线性无关，则秩（A T）等于（） A. 1 B. 2 C. 3 D. 4 6.设两个向量组α1，α2，…，αs和β1，β2，…，βs均线性相关，则（） A.有不全为0的数λ1，λ2，…，λs使λ1α1+λ2α2+…+λsαs=0和λ1β1+λ2β2+…λsβs=0 B.有不全为0的数λ1，λ2，…，λs使λ1（α1+β1）+λ2（α2+β2）+…+λs（αs+βs）=0 C.有不全为0的数λ1，λ2，…，λs使λ1（α1-β1）+λ2（α2-β2）+…+λs（αs-βs）=0 D.有不全为0的数λ1，λ2，…，λs和不全为0的数μ1，μ2，…，μs使λ1α1+λ2α2+…+ λsαs=0和μ1β1+μ2β2+…+μsβs=0 7.设矩阵A的秩为r，则A中（） A.所有r-1阶子式都不为0 B.所有r-1阶子式全为0 C.至少有一个r阶子式不等于0 D.所有r阶子式都不为0 8.设Ax=b是一非齐次线性方程组，η1，η2是其任意2个解，则下列结论错误的是（） A.η1+η2是Ax=0的一个解 B.1 2 η1+ 1 2 η2是Ax=b的一个解 一、判断题 1．线性表的逻辑顺序与存储顺序总是一致的。(FALSE) 2．顺序存储的线性表可以按序号随机存取。(TRUE) 3．顺序表的插入和删除一个数据元素，每次操作平均只有近一半的元素需要移动。（TRUE） 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。（TRUE） 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。（FALSE） 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（TRUE）7．线性表的链式存储结构优于顺序存储结构。（FALSE） 8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。（TRUE） 9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（TRUE）10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（FALSE） 二、单选题、(请从下列A，B，C，D选项中选择一项) 11．线性表是( ) 。 (A) 一个有限序列，可以为空；(B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空；(D) 一个无序序列，不能为空。 答：A 12．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等 概率的。插入一个元素时平均要移动表中的（）个元素。 (A) n/2 (B) (n+1)/2 (C) (n –1)/2 (D) n 答：A 13．线性表采用链式存储时，其地址( D ) 。 (A) 必须是连续的；(B) 部分地址必须是连续的； (C) 一定是不连续的；(D) 连续与否均可以。 答：D 14．用链表表示线性表的优点是（）。 (A)便于随机存取 (B)花费的存储空间较顺序存储少 (C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同 答：C 15. 某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。 (A)单链表 (B)双链表 (C)单循环链表 2006-2007学年第二学期《信号与线性系统》（课内）试卷A 卷 一、计算题（共45分） 1.（5分）计算积分dt t t t )6 ()sin (π δ- +?+∞ ∞-的值。 2.（5分）绘出函数)1()]1()([-+--t u t u t u t 的波形图。 3.（6分）已知)2()()(),1()()(21--=--=t u t u t f t u t u t f ，求卷积)()(21t f t f *。 4.（6分）若)(t f 的傅里叶变换已知，记为)(ωF ，求)1()1(t f t --对应的傅里叶变换。 5.（6分）如下图所示信号，已知其傅里叶变换，记为)(ωF ， 求： （1）)0(F ； （2）?+∞ ∞ -ωωd F )(。 6.（5分）已知)(t f 对应的拉氏变换为)(s F ，求)/(/a t f e a t -（0>a ）对应的拉氏变换。 7.（6分） 已知)(t f 对应的拉氏变换2 3)(2 +-=-s s e s F s ，求)(t f 8．（6分）线性时不变系统的单位样值响应为)(n h ，输入为)(n x ，且有 )4()()()(--==n u n u n x n h ，求输出)(n y ，并绘图示出)(n y 。 二、综合题（共计55分） 1、（10分）系统如图所示，已知t t x 2000cos )(=，t t t f 2000cos 100cos )(=，理想低通滤波器)300()300()(--+=ωωωu u H ，求滤波器的响应信号)(t y 。 x(t) y(t) f(t) 1 / 6 一、 已知线性约束条件，探求线性目标关系最值问题 1. 设变量x 、y 满足约束条件?? ? ??≥+-≥-≤-1122y x y x y x ,则y x z 32+=的最大值为 。 二、 已知线性约束条件,探求非线性目标关系最值问题 2. 已知1,10,220x x y x y ≥??-+≤??--≤? 则22 x y +的最小值是 。 3. 已知变量x ，y 满足约束条件+201-70x y x x y -≤?? ≥??+≤? ,则 错误! 的取值范围是（ )。 A 。 ［错误!，6] B.（－∞，错误!］∪［6，＋∞） C.（－∞，3］∪［6，＋∞） D 。 ［3，6］ 三、 研究线性规划中的整点最优解问题 4. 某公司招收男职员x 名，女职员y 名，x 和y 须满足约束条件?? ? ??≤≥+-≥-.112,932,22115x y x y x 则1010z x y =+的最大 值是 。 四、 已知最优解成立条件，探求目标函数参数范围问题 5. 已知变量x ，y 满足约束条件14 22x y x y ≤+≤?? -≤-≤? 。若目标函数z ax y =+(其中0a >）仅在点(3,1)处 取得最大值，则a 的取值范围为 。 6. 已知x 、y 满足以下约束条件5503x y x y x +≥?? -+≤??≤? ,使z=x+a y (a >0) 取得最小值的最优解有无数个，则a 的 值为（ ） A. －3 B. 3 C 。 －1 D. 1 五、 求可行域的面积 7. 不等式组260302x y x y y +-≥?? +-≤??≤? 表示的平面区域的面积为 （ ） A. 4 B. 1 C. 5 D 。 无穷大 例1说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首元结点的关系。 答：在线性表的链式存储结构中，头指针是指指向链表的指针，若链表有头指针则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一数据元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用作监视哨，等等），有了头结点后，对在第一数据元素结点前插入结点和删除第一结点，其操作与对其它结点的操作就统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一数据元素结点，它是头结点后边的第一个结点。 例2 为什么在单循环链表中设置尾指针比设置头指针更好？ 答：尾指针是指指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一个带头结点的单循环链表，其尾指针是rear，则开始结点和终端结点分别为指针rear所指结点的后继结点的后继结点和指针rear所指结点（利用C语言分别描述为rear->next->next和rear，利用标准Pascal语言分别描述为rear↑.next↑.next和rear），查找时间均为O(1)。若用头指针来表示该链表，则查找时间均为O(n)。 例3请分析含有n个结点的顺序表，在进行插入和删除操作时的时间复杂度，并对计算的结果进行分析，由此可得到线性表的适用范围的什么结论。 解：值得注意的是，插入操作是指在某个元素前面或后面插入，是针对位置的，因此可插入的位置为n+1个，而删除操作是删除线性表中某个位置上的元素，是针对元素的，因此可删除的元素为n个。 设p i为在第i个元素之前插入一个元素的概率，在等概率的条件下，其值为1/(n+1)。在第i个元素之前插入一个元素需要移动的元素的个数为：n-i+1。所以，在长度为n的线性表中插入一个元素所需要移动的元素次数的数学期望值（平均次数）为： E in=∑+ = + - 1 1 )1 ( n i i i n p=n/2 同理，设q i为删除第i个元素的概率，在等概率的条件下，其值为1/n。删除第i 个元素需要移动的元素的个数为：n-i。所以，在长度为n的线性表中删除一个元素所需要移动的元素次数的数学期望值（平均次数）为： E del=∑ =- n i i i n q 1 ) (=(n-1)/2 由于这两个操作的时间主要消耗在数据元素的移动上，所以插入算法和删除算法的时间复杂度均为：O(n)。 从上述分析可知，在顺序存储结构下，在线性表上插入或删除一个元素时需要平均移动线性表长度一半的元素个数，因此当n的值较大时，在顺序结构下，不宜对它频繁线性代数测试试卷及答案
数据结构习题二线性表
线性规划经典例题及详细解析
线性代数考试题库及答案(六)
有关线性表的题目及答案
信号与系统期末考试试题(有答案的)
六种经典线性规划例题
2010-2011-2线性代数试卷及答案
第2章线性表习题解析(答)
八种 经典线性规划例题(超实用)
线性表练习题(答案)
信号与系统期末考试试题
高中数学线性规划经典题型
线性代数试题和答案(精选版)
线性表练习题答案
《信号与线性系统》期末试卷
线性规划经典例题及详细解析
线性表例题