2013年—厦大—903数据结构B真题

适用专业：一、单项选择题（每题2分，共40分）1．算法的时间复杂度是指( )A．执行算法程序所需要的时间B．算法程序的长度C．算法执行过程中所需要的基本运算次数D．算法程序中的指令条数2．在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行（）。

A．p = q->next ; p->next = q->next; B．p = q->next ; q->next = p;C．q->next = q->next->next; q->next = q; D．p = q->next ; q->next = p->next; 3．下列叙述中正确的是( )A．线性表是线性结构 B. 栈与队列是非线性结构C．线性链表是非线性结构 D. 二叉树是线性结构4．若让元素1，2，3依次进栈，则出栈次序不可能出现（）种情况。

A．3，2，1 B．2，1，3 C．3，1，2 D．1，3，25．图的广度优先搜索类似于树的（）次序遍历。

A．先根B．中根C．后根D．层次6．具有n个顶点的有向无环图最多可包含（）条有向边。

A．n-1 B．n C．n(n-1)/2 D．n(n-1)7．已知单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为( ) 。

A．O(1) B．O(m) C．O(n) D．O(m+n)8．若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是( )。

A．s->next=p->next; p->next=s; B．p->next=s; s->next=p->next;C．p->next=s->next; s->next=p; D．s->next=p; p->next=s->next;9．假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为( )。

1、已知栈的最大容量为4。

若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（ C ）。

A) 5，4，3，2，1，6 B) 2，3，5，6，1，4C) 3，2，5，4，1，6 D) 1，4，6，5，2，32、（ C ）在进行插入操作时，常产生假溢出现象。

A）顺序栈 B）循环队列C）顺序队列 D）链队列3、用一维数组A进行顺序存储时，若起始地址为loc(A1)，元素长度为c，则A的第i个数组单元在存放地址loc(Ai)，等于（ B ）。

A）loc(A1)+i*c B）loc(A1)+(i-1)*cC）loc(A1)+i*c+1 D）loc(A1)+(i+1)*c4、已知栈的最大容量为4。

若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（ C ）。

A) 5，4，3，2，1，6 B) 2，3，5，6，1，4C) 3，2，5，4，1，6 D) 1，4，6，5，2，35、有一个有序表{1，4，6，10，18，35，42，53，67，71，78，84，92，99}。

当用二分查找法查找键值为84的结点时，经（ B ）比较后查找成功。

A) 4 B)3 C)2 D)126、广义表A=（A,B,(C,D),(E,(F,G))），则head(tail(head(tail(tail(A)))))=（ D ）。

A） (G) B） (D) C） C D） D7、链式存储的存储结构所占存储空间（ A ）。

A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B）只有一部分，存放结点值C）只有一部分，存储表示结点间关系的指针D）分两部分，一部分存放结点值，另一部分存放结点所占单元数8、数据结构研究的内容是（ D ）。

A）数据的逻辑结构 B）数据的存储结构C）建立在相应逻辑结构和存储结构上的算法 D）包括以上三个方面9、如果结点A有3个兄弟，而且B为A的双亲，则B的度为（ B ）。

10级软件工程专业《数据结构》试题B卷答案及评分细则一、选择题（每小题3分，共30分，选错不给分，选对给3分）1,C 2,A 3,D 4,C 5,B 6,C 7,B 8,B 9,A 10,A二、填空题（每空2分，共20分，填对给2分，填错不给分）1,2 4；2，SXSSXXSX3,-+A*BC/DE4,128 75,存储位置指针6，任意若干连续字符序列7，相同类型数据元素三、应用题1 解：其步骤为i1=index(S,S1,1)………………………………………………(2分)i2=index(S,S2,1)+3………………………………………………(2分)sub1=substr(S,i1,length(S)-i1+1) …………………………………(2分)sub2=substr(S,i2,length(S)-i2+1…………………………………………(2分) S3=concat(sub1, sub2) ………………………………………………(2分)2 解本题即为构造最小生成树，按照最小生成树的构造方法，构造如下：303解：其拓扑排序序列为152634；156234；152364；512634；516234；512364；5612344 解：按照题目要求构造的二叉树如下四、算法设计题由于队列是先进先出，而栈是先进后出，所以只有经过两个栈，即先在第一个栈里先进后出，再经过第二个栈后进先出来实现队列的先进先出。

因此用两个栈模拟一个队列运算就是用一个栈作为输入，而另一个栈作为输出。

当进队列时，总是将数据进入到作为输入的栈中。

在输出时，如果作为输出的栈已空，则从输入栈将已输入到输入栈的所有数据压入输出栈中，然后由输出栈输出数据；如果作为输出的栈不空，则就从输出栈输出数据。

显然，只有在输入、输出栈均为空时队列才为空。

…………………………（写出思想给5分）一个栈s1用来插入元素，另一个栈S2用来删除元素，删除元素时应将前一栈s1中的所有元素读出，然后进入到第二个栈s2中，算法描述如下：Void Enqueue(s1,x)……………………………………………(2分)stack s1;int x;{if(s1->top==0)Printf(“队列上溢“)；ElsePush(s1,x);}Void Dequeue(s1,s2,x) ……………………………………………(2分)Stack s1,s2;Int x;{ S->top=0; /将s2清空While (!empty(s1) /将s1的所有元素退栈后压入s2,此时栈s1为空 Push(s2,pop(s1));Pop(s2,x); /弹出栈s2的栈顶元素（对首元素）并赋给xWhile (!empty(s2) /将剩于元素重新压入栈s1恢复为原s1中的顺序 Push(s1,pop(s2));}Int Queue_empty(s1)……………………………………………(1分) Stack s1;{if empty(s1)Return(1);ElseReturn(0);}。

一、单项选择题（每小题2分，共30分）1.下列关于栈的叙述中，正确的是（）oA.栈底元素一定是最后入栈的元素B.栈操作遵循先进后出的原则C.栈顶元素一定是最先入栈的元素D.以上三种说法都不对2.在数据结构中，与所使用的计算机硬件无关的是数据的（）结构。

A.逻辑B.存储C.逻辑和存储D.物理3.以下说法正确的是（）oA.数据项是数据的基本单位B.数据元素是数据的最小单位C.数据结构是带结构的数据项的集合D.一些表面上很不相同的数据可以有相同的逻辑结构4.六个元素按照6, 5, 4, 3, 2, 1的顺序入栈，下列哪一个是合法的出栈序列？（）A.546132B. 453126C. 346512D. 2341565.设树的度为4,其中度为1、2、3、4的结点个数分别是4、2、1、2,则树中叶子个数为（）A.8B. 9C. 10D. 116.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（）A, （100,80,90,60,120,110,130） B. （100,120,110,130,80, 60,90）C, （100,60,80,90,120,110,130）D, （100,80, 60,90,120,130,110）7.下列陈述中正确的是（）A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树，并且有左右之分8.在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）A. eB. 2eC. n2—eD. n2—2e9.栈和队列都是（）A.限制存取位置的线性结构B.顺序存储的线性结构C.链式存储的线性结构D.限制存取位置的非线性结构10.在具有n个叶子结点的严格二叉树（即结点的度要么是0要么是2）中，结点总数为（）A. 2n+lB. 2nC. 2n・lD. 2n-211.在循环双链表的P所指的结点之前插入S所指结点的操作是（）oA.p->prior = s； s->next = p； p->prior->next = s； s->prior = p->priorB.p->prior = s； p->prior->next = s； s->next = p； s->prior = p->priorC.s->next = p； s->prior = p->prior； p->prior = s； p->prior->next = sD.s->next = p； s->prior = p->prior； p->prior->next = s； p->prior = s12,单链表中，增加一个头结点的目的是为了（）oA.使单链表至少有一个结点B.标识表结点中首结点的位置C.方便算法的实现D.说明单链表是线性表的链式存储13,对一个满二叉树，m个叶子，n个结点，深度为h,则（）。

绝密★考试结束前全国2013年10月高等教育自学考试数据结构试题课程代码：02331请考生按规定用笔将所有试题的答案涂、写在答题纸上。

选择题部分注意事项：1. 答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。

2. 每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。

如需改动，用橡皮擦干净后，再选涂其他答案标号。

不能答在试题卷上。

一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。

错涂、多涂或未涂均无分。

1．算法的时间复杂度表征的是A．算法的可读性B．算法的难易程度C．执行算法所耗费的时间D．执行算法所耗费的存储空间2．对需要频繁插入和删除结点的线性表，适合的存储方式是A．顺序储存B．链式存储C．索引存储D．散列存储3．在头指针为head的循环链表中，判断指针变量P指向尾结点的条件是A．p->next->next==head B．p->next==headC．p->next->next==NULL D．p->next==NULL4．迪杰斯特拉(Dijkstra)算法的功能是A．求图中某顶点到其他顶点的最短路径B．求图中所有顶点之间的最短路径C．求图的最小生成树D．求图的拓扑排序序列5．若栈的进栈序列为1，2，3，4，5，则经过出入栈操作不可能．．．获得的出栈序列是A．4，5，3，2，1 B．4，3，5，1，2C．1，2，3，4，5 D．5，4，3，2，16．A是7×4的二维数组，按行优先方式顺序存储，元素A[0][0]的存储地址为1 000，若每个元素占2个字节，则元素A[3][3]的存储地址为A．1015 B．1016C．1028 D．10307．深度为4的完全二叉树的结点数至少为A．4 B．8C．13 D．158．若采用邻接矩阵A存储有向图G，则结点k的入度等于A中A．结点k对应行元素之和B．结点k对应列元素之和C．结点k对应行和列元素之和D．非零元素之和9．无向图G的邻接矩阵一定是A．对称矩阵B．对角矩阵C．三角矩阵D．单位矩阵10．下列关于有向带权图G的叙述中，错误．．的是A．图G的任何一棵生成树都不含有回路B．图G生成树所含的边数等于顶点数减1C．图G含有回路时无法得到拓扑序列D．图G的最小生成树总是唯一的11．在下列排序算法中，关键字比较次数与初始排列次序无关的是A．冒泡排序B．希尔排序C．直接插入排序D．直接选择排序1 2．对下图进行拓扑排序，可以得到的拓扑序列是A．a b c d e B．b a c d eC．b c a d e D．a b d c e13．下列线性表中，能使用二分查找的是A．顺序存储(2,12,5,6,9,3,89,34,25) B．链式存储(2,12,5,6,9,3,89,34,25) C．顺序存储(2,3,5,6,9,12,25,34,89) D．链式存储(2,3,5,6,9,12,25,34,89) 14．在下列查找方法中，平均查找长度与结点数量无直接关系的是A．顺序查找B．分块查找C．散列查找D．基于B树的查找15．下列排序算法中，时间复杂度为O(nlog2 n)的算法是A．快速排序B．冒泡排序C．直接选择排序D．直接插入排序非选择题部分注意事项：用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。

倚窗远眺，目光目光尽处必有一座山，那影影绰绰的黛绿色的影，是春天的颜色。

周遭流岚升腾，没露出那真实的面孔。

面对那流转的薄雾，我会幻想，那里有一个世外桃源。

在天阶夜色凉如水的夏夜，我会静静地，静静地，等待一场流星雨的来临…许下一个愿望，不乞求去实现，至少，曾经，有那么一刻，我那还未枯萎的，青春的，诗意的心，在我最美的年华里，同星空做了一次灵魂的交流…秋日里，阳光并不刺眼，天空是一碧如洗的蓝，点缀着飘逸的流云。

偶尔，一片飞舞的落叶，会飘到我的窗前。

斑驳的印迹里，携刻着深秋的颜色。

在一个落雪的晨，这纷纷扬扬的雪，飘落着一如千年前的洁白。

窗外，是未被污染的银白色世界。

我会去迎接，这人间的圣洁。

在这流转的岁月里，有着流转的四季，还有一颗流转的心，亘古不变的心。

2013年考研数三真题及答案解析一、选择题 1—8小题．每小题4分，共32分．、１．当0→x 时，用)(x o 表示比x 高阶的无穷小，则下列式子中错误的是（ ）（A ）)()(32x o x o x =⋅ （B ）)()()(32x o x o x o = （C ）)()()(222x o x o x o =+ （D ）)()()(22x o x o x o =+【详解】由高阶无穷小的定义可知（A ）（B ）（C ）都是正确的，对于（D ）可找出反例，例如当0→x 时)()(),()(2332x o x x g x o x x x f ===+=，但)()()(x o x g x f =+而不是)(2x o 故应该选（D ）．2．函数xx x x x f xln )1(1)(+-=的可去间断点的个数为（ ）（A ）0 （B ）1 （C ）2 （D ）3 【详解】当0ln →x x 时，x x ex xx xln ~11ln -=-，1ln ln limln )1(1lim)(lim 0==+-=→→→x x x x x x x x x f x xx x ，所以0=x 是函数)(x f 的可去间断点．21ln 2ln limln )1(1lim)(lim 011==+-=→→→xx x x xx x x x f x xx x ，所以1=x 是函数)(x f 的可去间断点． ∞=+-=+-=-→-→-→xx x x xx x x x f x x x x ln )1(ln limln )1(1lim)(lim 111，所以所以1-=x 不是函数)(x f 的可去间断点．故应该选（C ）．３．设k D 是圆域{}1|),(22≤+=y x y x D 的第k 象限的部分，记⎰⎰-=kD k dxdy x y I )(，则（ ）（A ）01>I （B ）02>I （C ）03>I （D ）04>I 【详解】由极坐标系下二重积分的计算可知()ππππππθθθθθθθθ22122110222)1(|cos sin 31)sin (sin 31)cos (sin )(k k kk kk D k d dr r d dxdy x y I k ---+-=-=-=-=⎰⎰⎰⎰⎰所以ππ32,32,04231-====I I I I ，应该选（B ）． ４．设{}n a 为正项数列，则下列选择项正确的是（ ） （A ）若1+>n n a a ，则∑∞=--11)1(n n n a 收敛；（B ）若∑∞=--11)1(n n n a 收敛，则1+>n n a a ；（C ）若∑∞=1n na收敛．则存在常数1>P ，使n pn a n ∞→lim 存在；（D ）若存在常数1>P ，使n pn a n ∞→lim 存在，则∑∞=1n na收敛．【详解】由正项级数的比较审敛法，可知选项（D ）正确，故应选（Ｄ）．此小题的（A ）（B ）选项想考查的交错级数收敛的莱布尼兹条件，对于选项（A ），但少一条件0lim =∞→n n a ，显然错误．而莱布尼兹条件只是交错级数收敛的充分条件，不是必要条件，选项（B ）也不正确，反例自己去构造．５．设Ａ，Ｂ，Ｃ均为n 阶矩阵，若ＡＢ＝Ｃ，且Ｂ可逆，则（A ）矩阵C 的行向量组与矩阵A 的行向量组等价． （B ）矩阵C 的列向量组与矩阵A 的列向量组等价． （C ）矩阵C 的行向量组与矩阵B 的行向量组等价． （D ）矩阵C 的列向量组与矩阵B 的列向量组等价．【详解】把矩阵A ，C 列分块如下：()()n n C A γγγααα,,,,,,,2121 ==，由于ＡＢ＝Ｃ，则可知),,2,1(2211n i b b b n in i i i =+++=αααγ，得到矩阵C 的列向量组可用矩阵A 的列向量组线性表示．同时由于B 可逆，即1-=CB A ，同理可知矩阵A 的列向量组可用矩阵C 的列向量组线性表示，所以矩阵C 的列向量组与矩阵A 的列向量组等价．应该选（B ）．6．矩阵⎪⎪⎪⎭⎫ ⎝⎛1111a a b a a 与矩阵⎪⎪⎪⎭⎫ ⎝⎛00000002b 相似的充分必要条件是（A ）2,0==b a （B ）0=a ，b 为任意常数 （C ）0,2==b a （D ）2=a ，b 为任意常数【详解】注意矩阵⎪⎪⎪⎭⎫ ⎝⎛00000002b 是对角矩阵，所以矩阵A=⎪⎪⎪⎭⎫ ⎝⎛1111a a b a a 与矩阵⎪⎪⎪⎭⎫⎝⎛00000002b 相似的充分必要条件是两个矩阵的特征值对应相等．)22)2((111122a b b aa baa A E -++--=---------=-λλλλλλλ从而可知b a b 2222=-，即0=a ，b 为任意常数，故选择（B ）．7．设321,,X X X 是随机变量，且)3,5(~),2,0(~),1,0(~23221N X N X N X ，{}22≤≤-=i i X P P ，则（A ）321P P P >> （B ）312P P P >> （C ）123P P P >> （D ）231P P P >> 【详解】若),(~2σμN X ，则)1,0(~N X σμ-1)2(21-Φ=P ，{}1)1(212122222-Φ=⎭⎬⎫⎩⎨⎧≤≤-=≤≤-=X P X P P ，{}())13737)1(3523535222333Φ-⎪⎭⎫⎝⎛Φ=⎪⎭⎫ ⎝⎛-Φ--Φ=⎭⎬⎫⎩⎨⎧-≤-≤--=≤≤-=X P X P P ，=-23P P 0)1(32)1(3371<Φ-<Φ-⎪⎭⎫⎝⎛Φ+．故选择（A ）．8．设随机变量X 和Y 相互独立，且X 和Y 的概率分布分别为X 0 1 2 3P P1/21/41/81/8Y -1 0 1 P1/31/31/3则{}==+2Y X P （ ） （A ）121 （B ）81 （C ）61 （D ）21 【详解】{}{}{}{}612412411211,30,21,12=++=-==+==+====+Y X P Y X P Y X P Y X P ，故选择（C ）．二、填空题（本题共6小题，每小题4分，满分24分. 把答案填在题中横线上）9．设曲线)(x f y =和x x y -=2在点()0,1处有切线，则=⎪⎭⎫⎝⎛+∞→2lim n n nf n ．【详解】由条件可知()1)1(',01==f f ．所以2)1('22222)1(221lim 2lim -=-=-+⋅+--⎪⎭⎫ ⎝⎛+-+=⎪⎭⎫ ⎝⎛+∞→∞→f nn n f n f n n nf n n 10．设函数()y x z z ,=是由方程()xy y z x=+确定，则=∂∂)2,1(|xz． 【详解】 设()xyy z z y x F x -+=)(,,，则()1)(),,(,)ln()(,,-+=-++=x z x x y z x z y x F y y z y z z y x F ，当2,1==y x 时，0=z ，所以2ln 22|)2,1(-=∂∂xz． 11．=+⎰∞+x d x x12)1(ln ． 【详解】2ln |1ln )1(1|1ln 11ln )1(ln 111112=+=+++-=+-=+∞+∞+∞+∞+∞+⎰⎰⎰x x dx x x x x x xd x d x x 12．微分方程041=+'-''y y y 的通解为 ． 【详解】方程的特征方程为041=+-λλr，两个特征根分别为2121==λλ，所以方程通解为221)(xe x C C y +=，其中21,C C 为任意常数．13．设()ij a A =是三阶非零矩阵，A 为其行列式，ij A 为元素ij a 的代数余子式，且满足)3,2,1,(0==+j i a A ij ij ，则A = ．【详解】由条件)3,2,1,(0==+j i a A ij ij 可知0*=+TA A ，其中*A 为A 的伴随矩阵，从而可知A AA A T -===-13**，所以A 可能为1-或0．但由结论⎪⎩⎪⎨⎧-<-===1)(,01)(,1)(,)(*n A r n A r n A r n A r 可知，0*=+TA A 可知*)()(A r A r =,伴随矩阵的秩只能为3，所以.1-=A14．设随机变量X 服从标准正分布)1,0(~N X ，则()=XXeE 2 ． 【详解】()=X Xe E 2dx ex edx ex dx exe x x x x⎰⎰⎰∞+∞---∞+∞-+--∞+∞--+-==2)2(222)2(22222)22(2221πππ22222222)(2222e e X E e dt e dt te e t t =+=⎪⎪⎭⎫ ⎝⎛+=⎰⎰∞+∞--∞+∞--π． 所以为22e ．三、解答题15．（本题满分10分）当0→x 时，x x x 3cos 2cos cos 1-与nax 是等价无穷小，求常数n a ,． 【分析】主要是考查0→x 时常见函数的马克劳林展开式． 【详解】当→x 时，)(211cos 22x o x x +-=，)(21)()2(2112cos 2222x o x x o x x +-=+-=，)(291)()3(2113cos 2222x o x x o x x +-=+-=，所以)(7))(291))((21))((211(13cos 2cos cos 122222222x o x x o x x o x x o x x x x +=+-+-+--=-，由于x x x 3cos 2cos cos 1-与nax 是等价无穷小，所以2,7==n a ． 16．（本题满分10分） 设D 是由曲线3x y =，直线a x =)0(>a 及x 轴所转成的平面图形，y x V V ,分别是D 绕x轴和y 轴旋转一周所形成的立体的体积，若y x V V =10，求a 的值． 【详解】由微元法可知πππ35320253a dx x dx y V a ax ===⎰⎰；πππ37340762)(2a dx x dx x xf V a a y ===⎰⎰；由条件y x V V =10，知77=a ． 17．（本题满分10分）设平面区域D 是由曲线8,3,3=+==y x x y y x 所围成，求⎰⎰Ddxdy x 2． 【详解】341683622332222221=+=+=⎰⎰⎰⎰⎰⎰⎰⎰⎰⎰-xx xx D D Ddy dx x dy dx x dxdy x dxdy x dxdy x ． 18．（本题满分10分）设生产某产品的固定成本为6000元，可变成本为20元/件，价格函数为,100060QP -=（P 是单价，单位：元，Q 是销量，单位：件），已知产销平衡，求： （1）该的边际利润．（2）当P=50时的边际利润，并解释其经济意义． （3）使得利润最大的定价P ． 【详解】（1）设利润为y ，则6000100040)206000(2--=+-=Q Q Q PQ y ， 边际利润为.50040'Q y -= （2）当P=50时，Q=10000，边际利润为20．经济意义为：当P=50时，销量每增加一个，利润增加20． （3）令0'=y ，得.40100002000060,20000=-==P Q19．（本题满分10分）设函数()x f 在),0[+∞上可导，()00=f ，且2)(lim =+∞→x f x ，证明（1）存在0>a ，使得();1=a f（2）对（1）中的a ，存在),0(a ∈ξ，使得af 1)('=ξ． 【详解】证明（1）由于2)(lim =+∞→x f x ，所以存在0>X ，当X x >时，有25)(23<<x f ， 又由于()x f 在),0[+∞上连续，且()00=f ，由介值定理，存在0>a ，使得();1=a f（2）函数()x f 在],0[a 上可导，由拉格朗日中值定理， 存在),0(a ∈ξ，使得aa f a f f 1)0()()('=-=ξ．20．（本题满分11分） 设⎪⎪⎭⎫⎝⎛=⎪⎪⎭⎫⎝⎛=b B a A 110,011，问当b a ,为何值时，存在矩阵C ，使得B CA AC =-，并求出所有矩阵C ．【详解】显然由B CA AC =-可知，如果C 存在，则必须是2阶的方阵．设⎪⎪⎭⎫ ⎝⎛=4321x xx x C ， 则B CA AC =-变形为⎪⎪⎭⎫⎝⎛=⎪⎪⎭⎫ ⎝⎛---++-+-b ax x xx x ax x ax ax x 1103243142132， 即得到线性方程组⎪⎪⎩⎪⎪⎨⎧=-=--=++-=+-bax x x x x ax x ax ax x 3243142132110，要使C 存在，此线性方程组必须有解，于是对方程组的增广矩阵进行初等行变换如下()⎪⎪⎪⎪⎪⎭⎫⎝⎛+---→⎪⎪⎪⎪⎪⎭⎫⎝⎛-----=b a ab a aa ab A 0010000001011101010111011010010|， 所以，当0,1=-=b a 时，线性方程组有解，即存在矩阵C ，使得B CA AC =-．此时，()⎪⎪⎪⎪⎪⎭⎫⎝⎛--→00000000000011011101|b A ，所以方程组的通解为⎪⎪⎪⎪⎪⎭⎫ ⎝⎛+⎪⎪⎪⎪⎪⎭⎫ ⎝⎛-+⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=100101110001214321C C x x x x x ，也就是满足B CA AC =-的矩阵C 为⎪⎪⎭⎫⎝⎛-++=211211C C C C C C ，其中21,C C 为任意常数．21．（本题满分11分） 设二次型23322112332211321)()(2),,(x b x b x b x a x a x a x x x f +++++=．记⎪⎪⎪⎭⎫ ⎝⎛=⎪⎪⎪⎭⎫ ⎝⎛=321321,b b b a a a βα．（1）证明二次型f 对应的矩阵为 TTββαα+2；（2）若βα,正交且为单位向量，证明f 在正交变换下的标准形为 22212y y +． 【详解】证明：（1）()()()()()()()()()()⎪⎪⎪⎭⎫ ⎝⎛+=⎪⎪⎪⎭⎫ ⎝⎛+⎪⎪⎪⎭⎫⎝⎛=⎪⎪⎪⎭⎫⎝⎛⎪⎪⎪⎭⎫ ⎝⎛+⎪⎪⎪⎭⎫ ⎝⎛⎪⎪⎪⎭⎫ ⎝⎛=+++++=321321321321321321321321321321321321321321233221123322113212,,,,2,,,,,,,,,,2)()(2),,(x x x x x x x x x x x x x x x x x x x x x b b b b b b x x x x x x a a a a a a x x x x b x b x b x a x a x a x x x f T T TT ββααββαα所以二次型f 对应的矩阵为 TT ββαα+2．证明（2）设=A TTββαα+2，由于0,1==αβαT则()ααββαααββααα2222=+=+=T TT A ，所以α为矩阵对应特征值21=λ的特征向量；()ββββααβββααβ=+=+=222T T T A ，所以β为矩阵对应特征值12=λ的特征向量；而矩阵A 的秩2)()2()2()(=+≤+=TTTTr r r A r ββααββαα，所以03=λ也是矩阵的一个特征值．故f 在正交变换下的标准形为 22212y y +． 22．（本题满分11分）设()Y X ,是二维随机变量，X 的边缘概率密度为⎩⎨⎧<<=其他,010,3)(2x x x f X ，在给定)10(<<=x x X 的条件下，Y 的条件概率密度为⎪⎩⎪⎨⎧<<=其他,0,0,3)/(32x y x y x y f XY ． （1）求()Y X ,的联合概率密度()y x f ,； （2）Y 的的边缘概率密度)(y f Y ．【详解】（1）()Y X ,的联合概率密度()y x f ,：()⎪⎩⎪⎨⎧<<<<=⋅=其他,00,10,9)()/(,2x y x x y x f x y f y x f X XY（2）Y 的的边缘概率密度)(y f Y ：⎪⎩⎪⎨⎧<<-===⎰⎰∞+∞-其他,010,ln 99),()(212y y y dx x y dx y x f y f yY 23．（本题满分11分）设总体X 的概率密度为⎪⎩⎪⎨⎧>=-其他,00,);(32x e x x f x θθθ，其中θ为为未知参数且大于零，n X X X ,21为来自总体X 的简单随机样本．（1）求θ的矩估计量； （2）求θ的极大似然估计量．【详解】（1）先求出总体的数学期望E （X ）θθθ===⎰⎰∞+-∞+∞-022)()(dx e xdx x xf X E x ，令∑===n n i X n X X E 11)(，得θ的矩估计量∑=∧==ni i X n X 11θ． （2）当),2,1(0n i x i =>时，似然函数为⎪⎪⎭⎫ ⎝⎛-==-∑⎪⎪⎭⎫ ⎝⎛=⎪⎪⎭⎫ ⎝⎛==∏∏n i i i x n i i n n i x i e x e x L 11312132)(θθθθθ， 取对数，∑∑==-⎪⎪⎭⎫ ⎝⎛-=n i i n i i x x n L 11ln 31ln 2)(ln θθθ， 令0)(ln =θθd L d ，得0121=-∑=n i i x n θ， 解得的极大似然估计量为．。

学院 姓名 学号 任课老师 考场教室__________选课号/座位号………密………封………线………以………内………答………题………无………效……第 1 页 共 12 页电子科技大学 2012-2013 学年第 2 学期期 末 考试 数据结构 卷课程名称： 数据结构 考试形式：闭卷 考试日期： 2013 年 月 日 考试时长：120 分钟课程成绩构成：平时 0 %， 期中 0 %， 实验 %， 期末 100 % 本试卷试题由_ 五 _部分构成，共 6 页。

选择题（共 20 分，共 10 题，每题 2 分）学院姓名学号任课老师考场教室__________选课号/座位号………密………封………线………以………内………答………题………无………效……1.设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A 是（）。

(A)线性结构 (B) 树型结构 (C) 物理结构(D) 图型结构2.下面程序的时间复杂为（）。

(A)O(n) (B) O(n2) (C) O(n3) (D) O(n4)3.设顺序线性表中有n 个数据元素，则删除表中第i 个元素需要移动（）个元素。

(A)n-i (B) n+l -i (C) n-1-i (D) i4.设一条单链表的头指针变量为head 且该链表没有头结点，则其判空条件是（）。

(A)head==0 (B) head->next==0第 2 页共 12 页学院姓名学号任课老师考场教室__________选课号/座位号………密………封………线………以………内………答………题………无………效……(C) head->next==head (D) head!=05．设用链表作为栈的存储结构则退栈操作（）。