2005研究生入学考试数据结构试题

目录1.05年北师大物理类各方向2.05年长光所3.05年东南大学4.05年中科大5.05年南京大学6.05年华中科大7.05年吉林大学（原子所）8.05年四川大学（原子与分子）9.05年北京理工10.05年河北理工11.05年长春理工北京师范大学2005年招收硕士研究生入学考试试题专业:物理类各专业科目代号:459研究方向:各方向考试科目:量子力学[注意]答案写在答题纸上，写在试题上无效。

1.(20分)一个电子被限制在一维谐振子势场中，活动范围求激发电子到第一激发态所需要的能量（用ev表示）（，，）提示：谐振子能量本征函数可以写成2.（30分）一个电子被限制在二维各向同性谐振子势场中（特征频率为）。

（1）写出其哈密顿量，利用一维谐振子能级公式找到此电子的能级公式和简并度。

（2）请推导电子的径向运动方程。

并讨论其在时的渐近解。

提示：极坐标下3．（50分）两个质量为的粒子，被禁闭在特征频率为的一维谐振子势场中，彼此无相互作用（此题中波函数无须写出具体形式）：（1）如果两个粒子无自旋可分辨，写出系统的基态（两个都在自己的基态）和第一激发能级（即一个在基态，另一个在第一激发态）的波函数和能量（注意简并情形）。

（10分）（2）如果两个粒子是不可分辨的无自旋波色子，写出系统的基态和第一激发态的能量和波函数。

如果粒子间互作用势为，计算基态能级到一级微扰项。

（15分）（3分）如果两个粒子是不可分辨的自旋1/2粒子，写出基态能级和波函数（考虑自旋）。

如果粒子间互作用能为，计算基态能量。

（15分）（4）同（3），解除势阱，两个粒子以左一右飞出。

有两个探测器分别（同时）测量它们的y方向自旋角动量。

请问测量结果为两电子自旋反向的几率是多少？（10分）4．（30分）中心力场中电子自旋与轨道角动量存在耦合能。

总角动量，是的共同本征态。

现有一电子处于态，且。

（1）在一基近似下，可用代替，请问电子的能量与态差多少？（2）请计算该电子产生的平均磁矩，并由此计算在z方向均匀磁场B中电子的能量改变多少？（），当，，当，5．（20分）一个定域（空间位置不动）的电子（自旋1/2）处于z方向强磁场中。

南京邮电学院2005年攻读硕士学位研究生入学考试数据结构试题一、单选题（每题3分，共30分）1. 设使用某算法对n个元素进行处理，所需的时间是T(n) = 100n log2n + 200n + 2000则该算法的渐进时间复杂度为。

A. O(1)B. O(n)C. O(200n)D. O(nlog2n)2. 设顺序表的长度为n，并设从表中删除元素的概率相等。

则在平均情况下，从表中删除一个元素需要移动的元素个数是。

A. (n－1)/2B. n/2C. n(n－1)/2D. n(n＋1)/23. 如果只保存一个n阶对称矩阵a的下三角元素（含对角线元素），并采用行主序存储在一维数组b中，a[i][j]（或a[i, j]）存于b[k]，则对i<j，下标k与i，j的关系是。

设一维数组和矩阵元素的行列下标取值均从0开始。

A.(1)2i ij++ B.(1)2j ji++C.(1)2i ij-+ D.(1)2j ji-+4. 一棵三叉树中，已知度为3的结点个数等于度为2的节点数，且树中结点的数目为13，则度为2的结点数目为。

A. 4B. 2C. 3D. 55. 在基于关键字比较的排序算法中，算法在最坏情况下的时间复杂度不高于O （nlog2n）。

A. 冒泡排序B. 合并排序C. 希尔排序D. 快速排序6. 已知一棵由关键字集合{18，43，27，77，44，36，39}所构造的二叉搜索树（也称为二叉排序树），对该树进行中序遍历得到的节点序列为。

A. 树形未定B. 18，43，27，77，44，36，99C. 18，27，36，39，43，44，77D. 77，44，43，39，36，27，187. 一个索引文件，如果经常需要插入和删除元素，宜采用做索引。

A. 二叉排序树B. 二叉平衡树C. B-树D. B+树8. 均匀的散列函数应当使关键字集合中的元素，经过散列函数映射到散列表中任何位置的概率。

A. 相等B. 最小C. 最大D. 一定9. 关键路径是指AOE（Activity On Edge）网中。

大连海事大学2005年硕士研究生招生考试试题考试科目：数据结构适用专业：计算机应用技术、计算机软件与理论考生须知：1、所有答案必须写在答题纸上，写在试题纸上无效；2、考生不得在答题纸上作与答题内容无关的标记，否则试卷作废。

一、判断下列叙述是否正确。

请写出题号并用“√”“×”回答（共20分，每小题1分）1、若（u,v）是连通网络的一条权值最大的边，是不论采用何种方法构造该网络的最小生成树，所构造出的最小生成树一定不包含（u,v）这条边。

2、算法是具有有穷性、确定性、可行性、0个或多个输入、1个或多个输出特性的一组规则。

操作系统一旦被启动后就永远处在工作或等待状态，所以，实现“操作系统”的一组规则不能称为算法。

3、给定n个不同权值的结点，则依据这n个结点构造的Huffman树的结构是唯一的。

4、在线索二叉树中，根据线索可以找到树中任何一个结点在相应遍历序列中的直接前驱或直接后续。

5、在线性表的顺序存储结构中，每删除一个数据元素都必须移动表中的数据元素。

6、在一个AOE网中，若某一尘埃的最早开始时间和最迟开始时间相同，则该活动为关键活动。

7、对有序表而言，采用折半查找方法查找表中的数据元素，其查找成功的平均工长度一定采用顺序查找方法时的平均查找长度要小。

8、在非空完全二叉树中，若某结点不存在左孩子，则该结点一定是叶子结点。

9、设L是广义表，则取表头运算Head（L）的运算结果一定是单元素，而取表尾运算Tail （L）的运算结果一定是广义表。

10、将一棵树转换成二叉树后，根结点没有右子树。

11、就平均时间性能而言，快速排序是最优的。

所以，对于任意的待排序序列，选择快速排序方法进行排序，其执行时间将是最少的。

12、由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。

13、存在着这样的非空二叉树，不论采用怎样的遍历算法其所得到的遍历序列均相同。

14、假设图已经以邻接表存储，，则按深度优先遍历该图所得到的生成树唯一的。

2005级数据结构试题A卷注：回答问题，请在答题卡上回答，不要回答在试题上。

一、是非判断（回答’Y’或者’N’即可，不许多答、不许用其他符号替代24分）（1）线性表的逻辑顺序与物理顺序总是一致的。

（2）线性表的顺序存储表示优于链式存储表示。

（3）线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。

（4）二维数组是其数组元素为线性表的线性表。

（5）每种数据结构都应具备三种基本运算：插入、删除和搜索。

(6 ) 二叉树必须有父结点、但不一定有左孩子结点或是右孩子结点。

（7）用n个结点构造Huffman树，这个树有2n个结点。

（8）有n个顶点的有向图，各个顶点完全连通则有n-1条边。

（9）拓扑排序的有向图，要求图入度为0的顶点只能有一个。

（10）在二叉排序树上查找，其效率总是高于顺序表上查找。

（11）归并排序是稳定排序且时间复杂度为O(nLogn)。

（12）Floyd最短路计算需要深度遍历图、且仅仅适合于有向图。

二，选择判断（每个题目仅有一个答案30分）1．算法指的是A．计算机程序 B．解决问题的计算方法C．排序算法 D．解决问题的有限运算序列2．关于以下图问题的计算，使用深度编历算法的是：A．Dijkstra最短路B．拓扑排序C．关键路径计算D．Prim最小生成树3．将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为A．O（1） B．O（n） C．O（m） D．O（m+n）4．哈希表查找中，填充因子和查找效率的关系是：A．填充因子越大、查找效率越好B．填充因子越小、查找效率越好C．填充因子要根据查找对象计算D．填充因子和查找效率没直接关系5．图的拓扑排序中，主要使用了哪种数据结构存储来暂存顶点?A．顺序表 B．栈C．队列 D．数组6．如下陈述中正确的是A．串是一种特殊的线性表 B．串的长度必须大于零C．串中元素只能是字母 D．空串就是空白串7．图的顶点个数是n，深度遍历该图，时间复杂度是：A．O（1） B．O（n） C．O（n2） D．O（n3）8、有数组char A[3][3][3]，按行存放于一个连续的存储空间中,如A[0][0][0] 存储地址是200（10进制），则它的数组元素A[1][1][2]在内存中的位置是：A．212 B．211 C．214 D．2159．对一个单向链表，下列程序段中，p指针类型为：struct Node {int X;struct Node *next;}如p开始指向链表头结点，最后p一定指向尾结点的是：A．while(p!=NULL) p=p->next;B．while(p!=NULL) p++；C．while(p->next!=NULL) p++;D．while(p++ ->next!=NULL);10．索引文件通常由索引表和主文件两部分构成，其中A．索引表和主文件均必须是有序文件B．索引表和主文件均可以是无序文件C．索引表必须是有序文件D．主文件必须是有序文件11．在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为A．e B．2*e C．n2－e D．n2－2*e12．假设一个有n个顶点和e条弧的有向图用邻接矩阵表示,则删除与某个顶点Vi相关的所有弧的时间复杂度是A．O(n) B．O(e) C．O(n+e) D．O(n*e)13．用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方法是A．选择排序 B．希尔排序 C．归并排序 D．快速排序14．对n个不同值元素的集合，找到最大/最小元的算法，应该进行多少种比较?A．n B．n-1 C．n2 D．n2-115．下列排序方法中，属于不稳定的排序方法是A．直接插入排序法B．快速排序法C．冒泡排序法D．希尔排序法三、计算、简答题(28分)1 有二叉树，先序遍历结果EBADCFHGIKJ，中序遍历结果为ABCDEFGHIJK，则后序遍历结果是什么？2 有数字序列（40，28，16，56，50，32，30，63），按次序插入每个对象生成一棵A VL树，对该树插入完成后，给出该树的后序遍历结果。

全国2005年10月高等教育自学考试全国统一命题考试数据结构试题课程代码：2331一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

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

1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上【】A. 操作的有限集合B. 映象的有限集合C. 类型的有限集合D. 关系的有限集合2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为【】A. n-i+1B. iC. i+1D. n-i3. 若不带头结点的单链表的头指针为head，则该链表为空的判定条件是【】A. head==NULLB. head->next==NULLC. head!=NULLD. head->next==head4. 引起循环队列队头位置发生变化的操作是【】A. 出队B. 入队C. 取队头元素D. 取队尾元素5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是【】A. 2，4，3，1，5，6B. 3，2，4，1，6，5C. 4，3，2，1，5，6D. 2，3，5，1，6，46. 字符串通常采用的两种存储方式是【】A. 散列存储和索引存储B. 索引存储和链式存储C. 顺序存储和链式存储D. 散列存储和顺序存储7. 设主串长为n，模式串长为m(m≤n)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为【】第 1 页共12 页A. mB. n-mC. n-m+1D. n8. 二维数组A［12］［18］采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A［9］［7］的地址为【】A. 429B. 432C. 435D. 4389. 对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是【】A. (e,f)B. ((e,f))C. (f)D. ( )10. 下列图示的顺序存储结构表示的二叉树是【】11. n个顶点的强连通图中至少含有【】A. n-1条有向边B. n条有向边C. n(n-1)/2条有向边D. n(n-1)条有向边12. 对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为【】A. (19，23，56，34，78，67，88，92)B. (23，56，78，66，88，92，19，34)C. (19，23，34，56，67，78，88，92)D. (19，23，67，56，34，78，92，88)13. 若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为【】第 2 页共12 页A. 4B. 5C. 8D. 914. 由同一关键字集合构造的各棵二叉排序树【】A. 其形态不一定相同，但平均查找长度相同B. 其形态不一定相同，平均查找长度也不一定相同C. 其形态均相同，但平均查找长度不一定相同D. 其形态均相同，平均查找长度也都相同15. ISAM文件和VSAM文件的区别之一是【】A. 前者是索引顺序文件，后者是索引非顺序文件B. 前者只能进行顺序存取，后者只能进行随机存取C. 前者建立静态索引结构，后者建立动态索引结构D. 前者的存储介质是磁盘，后者的存储介质不是磁盘二、填空题(本大题共10小题，每空2分，共20分)16. 数据的逻辑结构在计算机存储器内的表示，称为数据的____________。

《数据结构》试题（100分）（供2005级信息管理与信息系统本科专业使用）学号： 姓名： 座号： 系别： 年级： 专业：总分合计人： 复核人：说明：本试卷分为两部分，第I 卷（选择题和判断题）必须在“答题卡”上按规定要求填、涂；第II 卷直接在试卷上作答。

不按规定答题、填涂，一律无效。

第I 卷一、试题类型：单项选择题（每小题2分，共40分） （类型说明：在每小题列出的四个选项中只有一个选项是符合题目要求的，请选出正确选项并在“答题卡”的相应位置上涂黑。

多涂、少涂、错误均无分。

）1. 算法分析的两个主要方面是： （ ）（A) 空间复杂性和时间复杂性 （B) 正确性和简明性 （C) 可读性和文档性 （D) 数据复杂性和程序复杂性2. 计算机算法指的是： （ ）（A) 计算方法 （B) 排序方法 （C) 解决问题的有限运算序列 （D) 调度方法 3． 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称为：（ ）（A ）存储结构 （B ）逻辑结构 （C ）顺序存储结构 （D ）链式存储结构 4.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 。

（ ）（A ）110 （B ）108 （C ）100 （D ）1205. 链接存储的存储结构所占存储空间： （ ）（A ）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 （B ）只有一部分，存放结点值（C ） 只有一部分，存储表示结点间关系的指针（D ） 分两部分，一部分存放结点值，另一部分存放结点所占单元数 6. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址: （ ）（A ）必须是连续的 （B ）部分地址必须是连续的 （C ）一定是不连续的 （D ）连续或不连续都可以7. 栈中元素的进出原则是： （ ） （Ａ）先进先出 （Ｂ）后进先出 （Ｃ）栈空则进 （Ｄ）栈满则出 8. 若已知一个栈的入栈序列是1，2，3，…，n ，其输出序列为p1，p2，p3，…，pn ，若p1=n ，则pi 为： （ ） （Ａ） i （Ｂ） n=i （Ｃ） n-i+1 （Ｄ） 不确定9. 串是一种特殊的线性表，其特殊性体现在： （ ） （Ａ）可以顺序存储 （Ｂ）数据元素是一个字符（Ｃ）可以链式存储 （Ｄ）数据元素可以是多个字符10. 设串s1=‘ABCDEFG’，s2=‘PQRST’，函数con(x,y)返回x 和y 串的连接串，subs(s, i, j)返回串s 的从序号i 开始的j 个字符组成的子串，len(s)返回串s 的长度，则con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的结果串是： （ ） （Ａ）BCDEF （Ｂ）BCDEFG （Ｃ）BCPQRST （Ｄ）BCDEFEF11. 假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为 。

江西财经大学2005年考研数据库原理试题一、概念题(每小题3分，共12分)1.数据模型2.模式(Schema)3.排它锁与共享锁4.数据库设计二、简答题(第1、2、3小题各5分，第4小题7分，共22分)1.简述数据库系统的三级模式结构，并说明它的优点。

(5分)2.事务的特性有哪些，请详细说明其功能。

(5分)3.简述诊断死锁发生的等待图法，当发生死锁后如何解除死锁？(5分)4.叙述在一个DBMS中，事务管理部件(恢复子系统、并发控制子系统)的主要职能及其分别常用的基本技术和手段。

(7分)三、下面有一个销售管理数据库SALES，它包含下面三张表：(每小题4分，共16分)(1) 商品表：Item商品编码商品名称单位成本价库存数量code name unit cost amount(2) 商品销售主表：SaleHead销售单号销售日期客户名称saleOrder saleDate Customer(3) 商品销售明细表：SaleDetail销售单号商品编码单价销售数量saleOrder code price qty基于数据库SALES，完成下面的操作：其中，描述部门的属性有：部门号、部门名称、负责人、电话、地址；描述职工的属性有：职工号、职工姓名、性别、出生日期、职务；描述工程的属性有：工程号、工程名称、开始日期、结束日期；描述材料的属性有：材料号、规格说明、计量单位、单价；描述材料供应商的属性有：供应商号、供应商名称、电话、联系人、地址；描述仓库的属性有：仓库号、仓库名称、保管员、电话。

根据上面已知的语义以及你的领域知识，请设计一个关系数据库(可以增加一些属性)，并指出主键、外键以及约束条件。

2005年全国硕士研究生入学统一考试数学(一)试卷一、填空题(本题共6小题,每小题4分,满分24分.把答案填在题中横线上)(1)曲线122+=x x y 的斜渐近线方程为 _____________.(2)微分方程x x y y x ln 2=+'满足91)1(-=y 的解为____________.(3)设函数181261),,(222z y x z y x u +++=,单位向量}1,1,1{31=n ,则)3,2,1(nu∂∂=.________.(4)设Ω是由锥面22y x z +=与半球面222y x R z --=围成的空间区域,∑是Ω的整个边界的外侧,则⎰⎰∑=++zdxdy ydzdx xdydz ____________.(5)设123,,ααα均为3维列向量,记矩阵123(,,)=A ααα,123123123(,24,39)=++++++B ααααααααα,如果1=A ,那么=B .(6)从数1,2,3,4中任取一个数,记为X , 再从X ,,2,1 中任取一个数,记为Y , 则}2{=Y P =____________.二、选择题(本题共8小题,每小题4分,满分32分.每小题给出的四个选项中,只有一项符合题目要求,把所选项前的字母填在题后的括号内)(7)设函数n n n x x f 31lim )(+=∞→,则()f x 在),(+∞-∞内(A)处处可导 (B)恰有一个不可导点(C)恰有两个不可导点 (D)至少有三个不可导点(8)设()F x 是连续函数()f x 的一个原函数,""N M ⇔表示"M 的充分必要条件是",N 则必有(A)()F x 是偶函数()f x ⇔是奇函数 (B)()F x 是奇函数()f x ⇔是偶函数(C)()F x 是周期函数()f x ⇔是周期函数 (D)()F x 是单调函数()f x ⇔是单调函数(9)设函数⎰+-+-++=yx y x dt t y x y x y x u )()()(),(ψϕϕ, 其中函数ϕ具有二阶导数,ψ 具有一阶导数,则必有(A)2222y ux u ∂∂-=∂∂(B)2222yu x u ∂∂=∂∂(C)222yu y x u ∂∂=∂∂∂(D)222x uy x u ∂∂=∂∂∂ (10)设有三元方程ln e 1xz xy z y -+=,根据隐函数存在定理,存在点(0,1,1)的一个邻域,在此邻域内该方程(A)只能确定一个具有连续偏导数的隐函数(,)z z x y = (B)可确定两个具有连续偏导数的隐函数(,)x x y z =和(,)z z x y = (C)可确定两个具有连续偏导数的隐函数(,)y y x z =和(,)z z x y = (D)可确定两个具有连续偏导数的隐函数(,)x x y z =和(,)y y x z =(11)设21,λλ是矩阵A 的两个不同的特征值,对应的特征向量分别为12,αα,则1α,12()+A αα线性无关的充分必要条件是(A)01≠λ (B)02≠λ (C)01=λ (D)02=λ(12)设A 为(2)n n ≥阶可逆矩阵,交换A 的第1行与第2行得矩阵**.,B A B 分别为,A B 的伴随矩阵,则(A)交换*A 的第1列与第2列得*B (B)交换*A 的第1行与第2行得*B(C)交换*A 的第1列与第2列得*-B (D)交换*A 的第1行与第2行得*-B(13)设二维随机变量(,)X Y 的概率分布为已知随机事件}0{=X 与}1{=+Y X 相互独立,则(A)0.2,0.3a b == (B)0.4,0.1a b == (C)0.3,0.2a b == (D)0.1,0.4a b ==(14)设)2(,,,21≥n X X X n 为来自总体(0,1)N 的简单随机样本,X 为样本均值,2S 为样本方差,则(A))1,0(~N X n (B)22~()nS n χ(C))1(~)1(--n t SXn (D)2122(1)~(1,1)nii n X F n X=--∑三 、解答题(本题共9小题,满分94分.解答应写出文字说明、证明过程或演算步骤) (15)(本题满分11分)设}0,0,2),{(22≥≥≤+=y x y x y x D ,]1[22y x ++表示不超过221y x ++的最大整数. 计算二重积分⎰⎰++Ddxdy y x xy .]1[22(16)(本题满分12分) 求幂级数∑∞=--+-121))12(11()1(n n n x n n 的收敛区间与和函数()f x .(17)(本题满分11分)如图,曲线C 的方程为()y f x =,点(3,2)是它的一个拐点,直线1l 与2l 分别是曲线C 在点(0,0)与(3,2)处的切线,其交点为(2,4).设函数()f x 具有三阶连续导数,计算定积分⎰'''+32.)()(dx x f x x(18)(本题满分12分)已知函数()f x 在[0,1]上连续,在(0,1)内可导,且(0)0,(1)1f f ==. 证明:(1)存在),1,0(∈ξ 使得ξξ-=1)(f .(2)存在两个不同的点)1,0(,∈ζη,使得.1)()(=''ζηf f(19)(本题满分12分)设函数)(y ϕ具有连续导数,在围绕原点的任意分段光滑简单闭曲线L 上,曲线积分24()22Ly dx xydyx y φ++⎰的值恒为同一常数.(1)证明:对右半平面0x >内的任意分段光滑简单闭曲线,C 有24()202Cy dx xydyx yφ+=+⎰.(2)求函数)(y ϕ的表达式.(20)(本题满分9分)已知二次型21232221321)1(22)1()1(),,(x x a x x a x a x x x f +++-+-=的秩为2.(1)求a 的值；(2)求正交变换x y =Q ,把),,(321x x x f 化成标准形. (3)求方程),,(321x x x f =0的解.(21)(本题满分9分)已知3阶矩阵A 的第一行是c b a c b a ,,),,,(不全为零,矩阵12324636k ⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦B (k 为常数),且=AB O ,求线性方程组0x =A 的通解.(22)(本题满分9分)设二维随机变量(,)X Y 的概率密度为(,)f x y =1001,02x y x <<<<其它求:(1)(,)X Y 的边缘概率密度)(),(y f x f Y X . (2)Y X Z -=2的概率密度).(z f Z(23)(本题满分9分)设)2(,,,21>n X X X n 为来自总体(0,1)N 的简单随机样本,X 为样本均值,记.,,2,1,n i X X Y i i =-=求:(1)i Y 的方差n i DY i ,,2,1, =. (2)1Y 与n Y 的协方差1Cov(,).n Y Y2005年考研数学一真题解析一、填空题（本题共6小题，每小题4分，满分24分. 把答案填在题中横线上）（1）曲线122+=x x y 的斜渐近线方程为 .4121-=x y【分析】 本题属基本题型，直接用斜渐近线方程公式进行计算即可.【详解】 因为a=212lim )(lim22=+=∞→∞→x x x x x f x x ， []41)12(2lim)(lim -=+-=-=∞→∞→x x ax x f b x x ，于是所求斜渐近线方程为.4121-=x y （2）微分方程x x y y x ln 2=+'满足91)1(-=y 的解为.91ln 31x x x y -=. 【分析】直接套用一阶线性微分方程)()(x Q y x P y =+'的通解公式：⎰+⎰⎰=-])([)()(C dx e x Q e y dxx P dx x P ， 再由初始条件确定任意常数即可.【详解】 原方程等价为x y xy ln 2=+'， 于是通解为 ⎰⎰+⋅=+⎰⋅⎰=-]ln [1]ln [2222C xdx x xC dx ex ey dxx dxx =2191ln 31x C x x x +-， 由91)1(-=y 得C=0，故所求解为.91ln 31x x x y -=（3）设函数181261),,(222z y x z y x u +++=，单位向量}1,1,1{31=n ，则)3,2,1(nu∂∂=33. 【分析】 函数u(x,y,z)沿单位向量γβαcos ,cos ,{cos =n}的方向导数为：γβαcos cos cos zu y u x u n u ∂∂+∂∂+∂∂=∂∂ 因此，本题直接用上述公式即可.【详解】 因为3x x u =∂∂，6y y u =∂∂，9zz u =∂∂，于是所求方向导数为)3,2,1(nu ∂∂=.33313131313131=⋅+⋅+⋅ （4）设Ω是由锥面22y x z +=与半球面222y x R z --=围成的空间区域，∑是Ω的整个边界的外侧，则⎰⎰∑=++zdxdy ydzdx xdydz 3)221(2R -π. 【分析】本题∑是封闭曲面且取外侧，自然想到用高斯公式转化为三重积分，再用球面（或柱面）坐标进行计算即可.【详解】⎰⎰∑=++zdxdy ydzdx xdydz ⎰⎰⎰Ωdxdydz 3=.)221(2sin 3320402R d d d R⎰⎰⎰-=πππθϕϕρρ （5）设321,,ααα均为3维列向量，记矩阵),,(321ααα=A ，)93,42,(321321321ααααααααα++++++=B ， 如果1=A ，那么=B 2 .【分析】 将B 写成用A 右乘另一矩阵的形式，再用方阵相乘的行列式性质进行计算即可.【详解】 由题设，有)93,42,(321321321ααααααααα++++++=B=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡941321111),,(321ααα， 于是有 .221941321111=⨯=⋅=A B（6）从数1,2,3,4中任取一个数，记为X, 再从X ,,2,1 中任取一个数，记为Y , 则}2{=Y P =4813. 【分析】 本题涉及到两次随机试验，想到用全概率公式, 且第一次试验的各种两两互不相容的结果即为完备事件组或样本空间的划分.【详解】 }2{=Y P =}12{}1{===X Y P X P +}22{}2{===X Y P X P +}32{}3{===X Y P X P +}42{}4{===X Y P X P =.4813)4131210(41=+++⨯ 二、选择题（本题共8小题，每小题4分，满分32分. 每小题给出的四个选项中，只有一项符合题目要求，把所选项前的字母填在题后的括号内）（7）设函数n nn xx f 31lim )(+=∞→，则f(x)在),(+∞-∞内(A) 处处可导. (B) 恰有一个不可导点.(C) 恰有两个不可导点. (D) 至少有三个不可导点. [ C ] 【分析】 先求出f(x)的表达式，再讨论其可导情形. 【详解】 当1<x 时，11lim )(3=+=∞→n nn xx f ；当1=x 时，111lim )(=+=∞→n n x f ；当1>x 时，.)11(lim )(3133x xx x f nnn =+=∞→即.1,11,1,,1,)(33>≤≤--<⎪⎩⎪⎨⎧-=x x x x x x f 可见f(x)仅在x=1±时不可导，故应选(C).（8）设F(x)是连续函数f(x)的一个原函数，""N M ⇔表示“M 的充分必要条件是N ”，则必有(A) F(x)是偶函数⇔f(x)是奇函数. （B ） F(x)是奇函数⇔f(x)是偶函数.(C) F(x)是周期函数⇔f(x)是周期函数.(D) F(x)是单调函数⇔f(x)是单调函数. [ A ] 【分析】 本题可直接推证，但最简便的方法还是通过反例用排除法找到答案.【详解】 方法一：任一原函数可表示为⎰+=xC dt t f x F 0)()(，且).()(x f x F ='当F(x)为偶函数时，有)()(x F x F =-，于是)()1()(x F x F '=-⋅-'，即 )()(x f x f =--，也即)()(x f x f -=-，可见f(x)为奇函数；反过来，若f(x)为奇函数，则⎰xdt t f 0)(为偶函数，从而⎰+=xC dt t f x F 0)()(为偶函数，可见(A)为正确选项.方法二：令f(x)=1, 则取F(x)=x+1, 排除(B)、(C); 令f(x)=x, 则取F(x)=221x , 排除(D); 故应选(A).（9）设函数⎰+-+-++=yx yx dt t y x y x y x u )()()(),(ψϕϕ, 其中函数ϕ具有二阶导数，ψ 具有一阶导数，则必有(A) 2222y u x u ∂∂-=∂∂. （B ） 2222yu x u ∂∂=∂∂. (C) 222y uy x u ∂∂=∂∂∂. (D) 222x u y x u ∂∂=∂∂∂. [ B ] 【分析】 先分别求出22x u ∂∂、22yu∂∂、y x u ∂∂∂2，再比较答案即可.【详解】 因为)()()()(y x y x y x y x xu--++-'++'=∂∂ψψϕϕ，)()()()(y x y x y x y x yu-+++-'-+'=∂∂ψψϕϕ， 于是 )()()()(22y x y x y x y x x u-'-+'+-''++''=∂∂ψψϕϕ，)()()()(2y x y x y x y x yx u-'++'+-''-+''=∂∂∂ψψϕϕ， )()()()(22y x y x y x y x y u-'-+'+-''++''=∂∂ψψϕϕ， 可见有2222yu x u ∂∂=∂∂，应选(B). （10）设有三元方程1ln =+-xzey z xy ，根据隐函数存在定理，存在点(0,1,1)的一个邻域，在此邻域内该方程(A) 只能确定一个具有连续偏导数的隐函数z=z(x,y).(B) 可确定两个具有连续偏导数的隐函数x=x(y,z)和z=z(x,y). (C) 可确定两个具有连续偏导数的隐函数y=y(x,z)和z=z(x,y).(D) 可确定两个具有连续偏导数的隐函数x=x(y,z)和y=y(x,z). [ D ]【分析】 本题考查隐函数存在定理，只需令F(x,y,z)=1ln -+-xzey z xy , 分别求出三个偏导数y x z F F F ,,，再考虑在点(0,1,1)处哪个偏导数不为0，则可确定相应的隐函数.【详解】 令F(x,y,z)=1ln -+-xzey z xy , 则z e y F xzx +='， yz x F y -='，x e y F xzz +-='ln ，且 2)1,1,0(='x F ，1)1,1,0(-='y F ，0)1,1,0(='z F . 由此可确定相应的隐函数x=x(y,z)和y=y(x,z). 故应选(D).（11）设21,λλ是矩阵A 的两个不同的特征值，对应的特征向量分别为21,αα，则1α，)(21αα+A 线性无关的充分必要条件是(A) 01≠λ. (B) 02≠λ. (C) 01=λ. (D) 02=λ. [ B ] 【分析】 讨论一组抽象向量的线性无关性，可用定义或转化为求其秩即可. 【详解】 方法一：令 0)(21211=++αααA k k ，则022211211=++αλαλαk k k ， 0)(2221121=++αλαλk k k . 由于21,αα线性无关，于是有 ⎩⎨⎧==+.0,022121λλk k k当02≠λ时，显然有0,021==k k ，此时1α，)(21αα+A 线性无关；反过来，若1α，)(21αα+A 线性无关，则必然有02≠λ(,否则，1α与)(21αα+A =11αλ线性相关)，故应选(B).方法二： 由于 ⎥⎦⎤⎢⎣⎡=+=+21212211121101],[],[)](,[λλαααλαλααααA ，可见1α，)(21αα+A 线性无关的充要条件是.001221≠=λλλ故应选(B).（12）设A 为n （2≥n ）阶可逆矩阵，交换A 的第1行与第2行得矩阵B, **,B A 分别为A,B 的伴随矩阵，则(A) 交换*A 的第1列与第2列得*B . (B) 交换*A 的第1行与第2行得*B .(C) 交换*A 的第1列与第2列得*B -. (D) 交换*A 的第1行与第2行得*B -. [C ]【分析】 本题考查初等变换的概念与初等矩阵的性质，只需利用初等变换与初等矩阵的关系以及伴随矩阵的性质进行分析即可.【详解】 由题设，存在初等矩阵12E （交换n 阶单位矩阵的第1行与第2行所得），使得 B A E =12，于是 12*11212*12***12*)(E A E E A E A A E B -=⋅===-，即*12*B E A -=,可见应选(C).（13）设二维随机变量(X,Y) 的概率分布为 X Y 0 1 0 0.4 a 1 b 0.1已知随机事件}0{=X 与}1{=+Y X 相互独立，则(A) a=0.2, b=0.3 (B) a=0.4, b=0.1(C) a=0.3, b=0.2 (D) a=0.1, b=0.4 [ B ] 【分析】 首先所有概率求和为1，可得a+b=0.5, 其次，利用事件的独立性又可得一等式，由此可确定a,b 的取值.【详解】 由题设，知 a+b=0.5又事件}0{=X 与}1{=+Y X 相互独立，于是有}1{}0{}1,0{=+===+=Y X P X P Y X X P ， 即 a=))(4.0(b a a ++, 由此可解得 a=0.4, b=0.1, 故应选(B).（14）设)2(,,,21≥n X X X n 为来自总体N(0,1)的简单随机样本，X 为样本均值，2S 为样本方差，则(A) )1,0(~N X n (B) ).(~22n nS χ(C) )1(~)1(--n t SXn (D) ).1,1(~)1(2221--∑=n F X X n n i i [ D ] 【分析】 利用正态总体抽样分布的性质和2χ分布、t 分布及F 分布的定义进行讨论即可.【详解】 由正态总体抽样分布的性质知，)1,0(~10N X n nX =-，可排除(A); 又)1(~0-=-n t SXn nS X ，可排除(C); 而)1(~)1(1)1(2222--=-n S n S n χ，不能断定(B)是正确选项.因为 ∑=-n i in X X222221)1(~),1(~χχ，且∑=-ni i n X X 222221)1(~)1(~χχ与相互独立，于是).1,1(~)1(1122212221--=-∑∑==n F XX n n XX ni ini i故应选(D).三 、解答题（本题共9小题，满分94分.解答应写出文字说明、证明过程或演算步骤.） （15）（本题满分11分） 设}0,0,2),{(22≥≥≤+=y x y x y x D ，]1[22y x ++表示不超过221y x ++的最大整数. 计算二重积分⎰⎰++Ddxdy y x xy .]1[22 【分析】 首先应设法去掉取整函数符号，为此将积分区域分为两部分即可.【详解】 令 }0,0,10),{(221≥≥<+≤=y x y x y x D ， }0,0,21),{(222≥≥≤+≤=y x y x y x D .则⎰⎰++Ddxdy y x xy ]1[22=⎰⎰⎰⎰+122D D xydxdy xydxdy dr r d dr r d ⎰⎰⎰⎰+=20213132cos sin 2cos sin ππθθθθθθ=.874381=+ （16）（本题满分12分） 求幂级数∑∞=--+-121))12(11()1(n n n x n n 的收敛区间与和函数f(x).【分析】 先求收敛半径，进而可确定收敛区间. 而和函数可利用逐项求导得到.【详解】 因为11)12()12()12)(1(1)12)(1(lim=+--⨯+++++∞→n n n n n n n n n ，所以当21x <时，原级数绝对收敛，当21x >时，原级数发散，因此原级数的收敛半径为1，收敛区间为（－1,1）记 121(1)(),(1,1)2(21)n nn S x x x n n -∞=-=∈--∑，则 1211(1)(),(1,1)21n n n S x x x n -∞-=-'=∈--∑，122211()(1),(1,1)1n n n S x x x x ∞--=''=-=∈-+∑. 由于 (0)0,(0)0,S S '==所以 201()()arctan ,1xxS x S t dt dt x t '''===+⎰⎰2001()()arctan arctan ln(1).2x x S x S t dt tdt x x x '===-+⎰⎰又21221(1),(1,1),1n nn x xx x ∞-=-=∈-+∑ 从而 22()2()1x f x S x x =++2222arctan ln(1),(1,1).1x x x x x x=-++∈-+ （17）（本题满分11分）如图，曲线C 的方程为y=f(x)，点(3,2)是它的一个拐点，直线1l 与2l 分别是曲线C 在点(0,0)与(3,2)处的切线，其交点为(2,4). 设函数f(x)具有三阶连续导数，计算定积分⎰'''+32.)()(dx x f x x【分析】 题设图形相当于已知f(x)在x=0的函数值与导数值，在x=3处的函数值及一阶、二阶导数值.【详解】 由题设图形知，f(0)=0, 2)0(='f ; f(3)=2, .0)3(,2)3(=''-='f f 由分部积分，知⎰⎰⎰+''-''+=''+='''+330302232)12)(()()()()()()(dx x x f x f x x x f d x x dx x f x x=dx x f x f x x f d x ⎰⎰'+'+-='+-3330)(2)()12()()12(=.20)]0()3([216=-+f f（18）（本题满分12分）已知函数f(x)在[0，1]上连续，在(0,1)内可导，且f(0)=0,f(1)=1. 证明： （I ）存在),1,0(∈ξ 使得ξξ-=1)(f ；（II ）存在两个不同的点)1,0(,∈ζη，使得.1)()(=''ζηf f【分析】 第一部分显然用闭区间上连续函数的介值定理；第二部分为双介值问题，可考虑用拉格朗日中值定理，但应注意利用第一部分已得结论.【详解】 （I ） 令x x f x F +-=1)()(，则F(x)在[0，1]上连续，且F(0)=-1<0, F(1)=1>0,于是由介值定理知，存在),1,0(∈ξ 使得0)(=ξF ，即ξξ-=1)(f .（II ） 在],0[ξ和]1,[ξ上对f(x)分别应用拉格朗日中值定理，知存在两个不同的点)1,(),,0(ξζξη∈∈，使得0)0()()(--='ξξηf f f ，ξξζ--='1)()1()(f f f于是 .1111)(1)()()(=-⋅-=--⋅=''ξξξξξξξξζηf f f f （19）（本题满分12分）设函数)(y ϕ具有连续导数，在围绕原点的任意分段光滑简单闭曲线L 上，曲线积分⎰++Ly x xydydx y 4222)(ϕ的值恒为同一常数.（I ）证明：对右半平面x>0内的任意分段光滑简单闭曲线C ，有022)(42=++⎰Cyx xydydx y ϕ；（II ）求函数)(y ϕ的表达式.【分析】 证明（I ）的关键是如何将封闭曲线C 与围绕原点的任意分段光滑简单闭曲线相联系，这可利用曲线积分的可加性将C 进行分解讨论；而（II ）中求)(y ϕ的表达式，显然应用积分与路径无关即可.【详解】 （I ）如图，将C 分解为：21l l C +=，另作一条曲线3l=++⎰Cy x xydydx y 4222)(ϕ-++⎰+314222)(l l y x xydydx y ϕ022)(3242=++⎰+l l y x xydydx y ϕ.（II ） 设2424()2,22y xyP Q x yx yϕ==++，,P Q 在单连通区域0x >内具有一阶连续偏导数，由（Ⅰ）知，曲线积分24()22Ly dx xydyx y ϕ++⎰在该区域内与路径无关，故当0x >时，总有Q Px y∂∂=∂∂. 24252422422(2)4242,(2)(2)Q y x y x xy x y y x x y x y ∂+--+==∂++ ①243243242242()(2)4()2()()4().(2)(2)P y x y y y x y y y y y y x y x y ϕϕϕϕϕ'''∂+-+-==∂++ ② 比较①、②两式的右端，得435()2,()4()2.y y y y y y y ϕϕϕ'=-⎧⎨'-=⎩ 由③得2()y y c ϕ=-+，将()y ϕ代入④得 535242,y cy y -= 所以0c =，从而2().y y ϕ=-（20）（本题满分9分）已知二次型21232221321)1(22)1()1(),,(x x a x x a x a x x x f +++-+-=的秩为2.（I ） 求a 的值；（II ） 求正交变换Qy x =，把),,(321x x x f 化成标准形； （III ） 求方程),,(321x x x f =0的解.【分析】 （I ）根据二次型的秩为2，可知对应矩阵的行列式为0，从而可求a 的值；（II ）是常规问题，先求出特征值、特征向量，再正交化、单位化即可找到所需正交变换； （III ）利用第二步的结果，通过标准形求解即可.【详解】 （I ） 二次型对应矩阵为⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-++-=200011011a a a a A ， 由二次型的秩为2，知 020011011=-++-=aa a a A ，得a=0. （II ） 这里⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=200011011A ， 可求出其特征值为0,2321===λλλ. 解 0)2(=-x A E ，得特征向量为：⎪⎪⎪⎭⎫⎝⎛=⎪⎪⎪⎭⎫ ⎝⎛=100,01121αα，解 0)0(=-x A E ，得特征向量为：.0113⎪⎪⎪⎭⎫ ⎝⎛-=α由于21,αα已经正交，直接将21,αα，3α单位化，得：③ ④⎪⎪⎪⎭⎫⎝⎛-=⎪⎪⎪⎭⎫ ⎝⎛=⎪⎪⎪⎭⎫ ⎝⎛=01121,100,01121321ηηη令[]321ααα=Q ，即为所求的正交变换矩阵，由x=Qy ，可化原二次型为标准形：),,(321x x x f =.222221y y + （III ） 由),,(321x x x f ==+222122y y 0，得k y y y ===321,0,0（k 为任意常数）.从而所求解为：x=Qy=[]⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-==⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡0003321c c k k ηηηη，其中c 为任意常数. （21）（本题满分9分）已知3阶矩阵A 的第一行是c b a c b a ,,),,,(不全为零，矩阵⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=k B 63642321（k 为常数），且AB=O, 求线性方程组Ax=0的通解.【分析】 AB=O, 相当于告之B 的每一列均为Ax=0的解，关键问题是Ax=0的基础解系所含解向量的个数为多少，而这又转化为确定系数矩阵A 的秩.【详解】 由AB=O 知，B 的每一列均为Ax=0的解，且.3)()(≤+B r A r（1）若k 9≠, 则r(B)=2, 于是r(A)1≤, 显然r(A)1≥, 故r(A)=1. 可见此时Ax=0的基础解系所含解向量的个数为3-r(A)=2, 矩阵B 的第一、第三列线性无关，可作为其基础解系，故Ax=0 的通解为：2121,,63321k k k k k x ⎪⎪⎪⎭⎫ ⎝⎛+⎪⎪⎪⎭⎫ ⎝⎛=为任意常数.(2) 若k=9，则r(B)=1, 从而.2)(1≤≤A r1） 若r(A)=2, 则Ax=0的通解为：11,321k k x ⎪⎪⎪⎭⎫⎝⎛=为任意常数.2） 若r(A)=1,则Ax=0 的同解方程组为：0321=++cx bx ax ,不妨设0≠a ,则其通解为2121,,1001k k a c k a b k x ⎪⎪⎪⎪⎪⎭⎫ ⎝⎛-+⎪⎪⎪⎪⎪⎭⎫ ⎝⎛-=为任意常数.（22）（本题满分9分）设二维随机变量(X,Y)的概率密度为 .,20,10,0,1),(其他x y x y x f <<<<⎩⎨⎧=求：（I ） (X,Y)的边缘概率密度)(),(y f x f Y X ； （II ）Y X Z -=2的概率密度).(z f Z【分析】 求边缘概率密度直接用公式即可；而求二维随机变量函数的概率密度，一般用分布函数法，即先用定义求出分布函数，再求导得到相应的概率密度.【详解】 （I ） 关于X 的边缘概率密度)(x f X =⎰+∞∞-dy y x f ),(=.,10,0,20其他<<⎪⎩⎪⎨⎧⎰x dy x=.,10,0,2其他<<⎩⎨⎧x x关于Y 的边缘概率密度)(y f Y =⎰+∞∞-dx y x f ),(=.,20,0,12其他<<⎪⎩⎪⎨⎧⎰y dx y=.,20,0,21其他<<⎪⎩⎪⎨⎧-y y （II ） 令}2{}{)(z Y X P z Z P z F Z ≤-=≤=， 1） 当0<z 时，0}2{)(=≤-=z Y X P z F Z ；2） 当20<≤z 时，}2{)(z Y X P z F Z ≤-= =241z z -; 3) 当2≥z 时，.1}2{)(=≤-=z Y X P z F Z即分布函数为： .2,20,0,1,41,0)(2≥<≤<⎪⎩⎪⎨⎧-=z z z z z z F Z故所求的概率密度为：.,20,0,211)(其他<<⎪⎩⎪⎨⎧-=z z z f Z （23）（本题满分9分）设)2(,,,21>n X X X n 为来自总体N(0,1)的简单随机样本，X 为样本均值，记.,,2,1,n i X X Y i i =-=求：（I ） i Y 的方差n i DY i ,,2,1, =； （II ）1Y 与n Y 的协方差).,(1n Y Y Cov【分析】 先将i Y 表示为相互独立的随机变量求和，再用方差的性质进行计算即可；求1Y 与n Y 的协方差),(1n Y Y Cov ，本质上还是数学期望的计算，同样应注意利用数学期望的运算性质.【详解】 由题设，知)2(,,,21>n X X X n 相互独立，且),,2,1(1,0n i DX EX i i ===，.0=X E（I ）∑≠--=-=ni j j i i i X n X n D X X D DY ]1)11[()(=∑≠+-nij ji DXnDX n 221)11(=.1)1(1)1(222n n n n n n -=-⋅+- （II ） )])([(),(111n n n EY Y EY Y E Y Y Cov --= =)])([()(11X X X X E Y Y E n n --==)(211X X X X X X X E n n +--=211)(2)(X E X X E X X E n +-=22121)(][20X E X D X X X E n nj j +++-∑==.112nn n -=+-。

20 ~ 20学年第学期数据结构课程试卷标准答案及评分标准A( )/B() 卷专业班级注意：标题请用宋体4号，内容请用宋体5号。

一、选择题（1 * 25 = 25分）1~5 BCABB 6~10 BBCCB 11~15 BBCAB 16~20 AABCD 21~25 ADBDC二、填空题（2 * 10 = 20分）1．n-i+1 2．3 1 2 3．3 4．’xyxyxywwy’5．232 6．69 7．HIDJKEBLFGCA 8．第k列非零元素个数9．9 10．散列(hash)查找三、简答题（7 + 8 + 10 + 10 = 35分）1．2．树和二叉树的区别有三：一是二叉树的度至多为2，树无此限制；（2分）二是二叉树有左右子树之分，即使在只有一个分枝的情况下，也必须指出是左子树还是右子树，树无此限制；（2分）三是二叉树允许为空，树一般不允许为空（个别书上允许为空）。

（2分）树和二叉树逻辑上都是树形结构，二叉树不是树的特例。

（2分）3．设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列(1)ABGFDEC (2)EACFBDG(3)（（关键路径是：活动与顶点的对照表：a1<α,A> a2<α,B> a3<α,C> a4<α,D> a5<A,E> a6<B,E> a7<B,W>a8<C,G> a9<C,F> a10<D,F> a11<E,G> a12<F,E> a13<F,W> a14<F,H> a15<G,W> a16<H,G> a17<H,W>（2分）四、 算法实现题（2 * 10 = 20分）1.○1 // La 和Lb 均不空 GetElem(La, i, ai); GetElem(Lb, j, bj);if (ai <= bj){ （2分）ListInsert(Lc, ++k, ai); ++i; （2分） }else {ListInsert(Lc, ++k, bj); ++j; （2分） }○2 // 当La 不空时 GetElem(La, i++, ai);ListInsert(Lc, ++k, ai); （2分）○3 // 当Lb 不空时 GetElem(Lb, j++, bj);ListInsert(Lc, ++k, bj); （2分）2．/*直接插入排序算法*/void StrInsSort1(RecType R[],int n){∥本算法是利用监视哨对R[1..n]进行直接插入排序for (i = 2; i <= n; i++){ ∥假定第一个记录有序（2分），长52。

南京大学2005年攻读硕士学位研究生入学考试试题考试科目名称及代码软件基础二838适用专业:计算机软件与理论计算机应用技术注意：1．所有答案必须写在研究生入学考试答题纸上，写在试卷和其他纸上无效。

2．本科目不允许使用无字典存储和编程功能的计算器。

《程序设计》一:程序设计基本概念:1.在定义函数参数时,何时需要把参数定义成指针或引用类型?C++提供了什么机制,可以防止指针或引用类型参数可能带来的函数副作用问题?2.抽象类的作用是什么?二. 请把下面的过程程序改写为面向对象程序:enum FigureType { LINE, RECTANGLE,CLRCLE };struct Line{FigureType t;double x1,y1,x2,y2;};void draw_line (struct Line x) {…………..}void save_line (struct Line x) {…………..}struct Rectangle{FigureType t;double left,top,right,bottom;};void draw_rectangle (struct Line x) {…………..}void save_rectangle (struct Line x) {…………..}struct Circle{FigureType t;double x,y,r;};void draw_circle (struct Line x) {…………..}void save_circle (struct Line x) {…………..}union Figure{FigureType type;Line line;Rectangle rect;Circle circle;};void main(){union Figure *figure[100]int i;//初始化…….//显示图形for(i=0;i<100;i++){switch (figure[i]->type){case LINE: draw_line(figure[i]->line); break;case RECTANGLE: draw_rectangle(figure[i]->rect); break;case CIRCLE: draw_circle(figure[i]->circle); break;}}//存储图形for(i=0;i<100;i++){switch (figure[i]->type){case LINE: save_line(figure[i]->line); break;case RECTANGLE: save_rectangle(figure[i]->rect); break;case CIRCLE: save_circle(figure[i]->circle); break;}}}三．根据下图写一个函数：int path(int n);计算从结点1到结点n（n大于1）共有多少条不同的路径。