山东大学考研真题2001数据结构
- 格式:doc
- 大小:31.50 KB
- 文档页数:3
2001年山东大学宪法学与行政法考研真题
一、简答题
1、修宪提案权与修宪建议权有何不同?
2、第二次世界大战后,人权国际化的标志性文件有哪些?有何意义?
3、中央与特别行政区的职权是如何划分的
4、简述没有救济便没有处罚的价值追求
5、简述行政应急权力行使得条件要求
6、简述行政法上反射性利益的局限性
二、论述与评析体
1、据不完全统计,在行政领域中现时生效的法律四百余部,行政法规千余部,地方性法规近气千项,还有那以计数的行政规章,它们构成了我国庞杂的行政法律体系。
在这个庞杂的法律体系中,有下位阶法对上位阶法的突破和抵触,也有同一位阶法之间的不一致和对立。
若干法律冲突现象引起人们的广泛关注。
试述法律体系冲突消解的基本思路
2、某国家机关招考国家公务员的文件中规定,中小学教师不得报考。
该规定侵犯了公民的何种权利?简述该权利的含义。
在我国目前的宪法监督体制中,人民法院能否有效的保护该项权利?为什么?
3、原告刘兵,22岁,安徽萧县人,原是轻工学院化工系的学生。
据原告称,学院的宿舍楼下堆放了大量的废气自行车,199年10月22日上午,他收集了一些废旧零部件,向组成整车使用,学校的保卫人员发现后,以盗窃为名将其送交派出所。
12月31日,学校勒令其退学,无奈将学校告上法庭,请求其撤销勒令退学的处分决定。
学生对学校的处分不服,是不是可以进入司法程序?该问题引起法学界和教育届的广泛关注。
试阐述你的看法。
第 5 章数组和广义表一、选择题1.设有一个10阶的对称矩阵A,采用压缩存储方式,以行序为主存储,a11为第一元素,其存储地址为1,每个元素占一个地址空间,则a85的地址为()。
【燕山大学 2001 一、2 (2分)】A. 13B. 33C. 18D. 402. 有一个二维数组A[1:6,0:7] 每个数组元素用相邻的6个字节存储,存储器按字节编址,那么这个数组的体积是(①)个字节。
假设存储数组元素A[1,0]的第一个字节的地址是0,则存储数组A的最后一个元素的第一个字节的地址是(②)。
若按行存储,则A[2,4]的第一个字节的地址是(③)。
若按列存储,则A[5,7]的第一个字节的地址是(④)。
就一般情况而言,当(⑤)时,按行存储的A[I,J]地址与按列存储的A[J,I]地址相等。
供选择的答案:【上海海运学院 1998 二、2 (5分)】①-④: A.12 B. 66 C. 72 D. 96 E. 114 F. 120G. 156 H. 234 I. 276 J. 282 K. 283 L. 288⑤: A.行与列的上界相同 B. 行与列的下界相同C. 行与列的上、下界都相同D. 行的元素个数与列的元素个数相同3. 设有数组A[i,j],数组的每个元素长度为3字节,i的值为1 到8 ,j的值为1 到10,数组从内存首地址BA开始顺序存放,当用以列为主存放时,元素A[5,8]的存储首地址为( )。
A. BA+141B. BA+180C. BA+222D. BA+225【南京理工大学 1997 一、8 (2分)】4. 假设以行序为主序存储二维数组A=array[1..100,1..100],设每个数据元素占2个存储单元,基地址为10,则LOC[5,5]=()。
【福州大学 1998 一、10 (2分)】A. 808B. 818C. 1010D. 10205. 数组A[0..5,0..6]的每个元素占五个字节,将其按列优先次序存储在起始地址为1000的内存单元中,则元素A[5,5]的地址是( )。
第10章 排序排序排序一、选择题 1.某内排序方法的稳定性是指.某内排序方法的稳定性是指( )( )( )。
【南京理工大学【南京理工大学 1997 1997 1997 一、一、一、101010((2分)】 A .该排序算法不允许有相同的关键字记录该排序算法不允许有相同的关键字记录 B B B..该排序算法允许有相同的关键字记录记录C .平均时间为0(n log n n log n)的排序方法)的排序方法)的排序方法D D D.以上都不对.以上都不对.以上都不对2.下面给出的四种排序法中下面给出的四种排序法中( )( )( )排序法是不稳定性排序法。
排序法是不稳定性排序法。
【北京航空航天大学北京航空航天大学 1999 1999 1999 一、一、10 10 ((2分)】 A. A. 插入插入插入 B. B. B. 冒泡冒泡冒泡 C. C. C. 二路归并二路归并二路归并 D. D. D. 堆积堆积堆积 3.下列排序算法中,其中(.下列排序算法中,其中( )是稳定的。
)是稳定的。
)是稳定的。
【福州大学【福州大学 1998 1998 1998 一、一、一、3 (23 (2分)】A. A. 堆排序,冒泡排序堆排序,冒泡排序堆排序,冒泡排序B. B. B. 快速排序,堆排序快速排序,堆排序快速排序,堆排序C. C. 直接选择排序,归并排序直接选择排序,归并排序直接选择排序,归并排序D. D. D. 归并排序,冒泡排序归并排序,冒泡排序归并排序,冒泡排序4.稳定的排序方法是(.稳定的排序方法是( )) 【北方交通大学【北方交通大学【北方交通大学 2000 2000 2000 二、二、二、33(2分)】 A .直接插入排序和快速排序.直接插入排序和快速排序 B B B.折半插入排序和起泡排序.折半插入排序和起泡排序.折半插入排序和起泡排序C .简单选择排序和四路归并排序.简单选择排序和四路归并排序D D D.树形选择排序和.树形选择排序和shell 排序排序5.下列排序方法中,哪一个是稳定的排序方法?(.下列排序方法中,哪一个是稳定的排序方法?( ) 【北方交通大学【北方交通大学【北方交通大学 2001 2001 2001 一、一、一、88(2分)】A .直接选择排序.直接选择排序B B B.二分法插入排序.二分法插入排序.二分法插入排序C C C.希尔排序.希尔排序.希尔排序D D D.快速排序.快速排序.快速排序6.若要求尽可能快地对序列进行稳定的排序,则应选(.若要求尽可能快地对序列进行稳定的排序,则应选(A A .快速排序.快速排序 B B B.归并排序.归并排序.归并排序 C C C.冒.冒泡排序)。
数据结构1800例题与答案第一章绪论一、选择题(每小题2分)1.算法的计算量的大小称为计算的( B )。
【北京邮电大学2000 二、3 (20/8分)】A.效率B.复杂性C.现实性D.难度2.算法的时间复杂度取决于(C)。
【中科院计算所1998 二、1 (2分)】A.问题的规模B.待处理数据的初态C.A和B D.都不是3.计算机算法指的是(①C ),它必须具备(② B )这三个特性。
①A.计算方法B.排序方法C.解决问题的步骤序列D.调度方法②A.可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性【南京理工大学1999 一、1(2分)【武汉交通科技大学1996 一、1(4分)】4.一个算法应该是(B )。
【中山大学1998 二、1(2分)】A.程序B.问题求解步骤的描述C.要满足五个基本特性D.A和C.5.下面关于算法说法错误的是( D )【南京理工大学2000 一、1(1.5分)】A.算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是(C )【南京理工大学2000 一、2 (1.5分)】(1)算法原地工作的含义是指不需要任何额外的辅助空间(2)在相同的规模n下,复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法(3)所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界(4)同一个算法,实现语言的级别越高,执行效率就越低A.(1) B.(1),(2) C.(1),(4) D.(3)7.从逻辑上可以把数据结构分为( C )两大类。
【武汉交通科技大学1996 一、4(2分)】A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构8.以下与数据的存储结构无关的术语是( D )。
【北方交通大学2000 二、1(2分)】A.循环队列 B. 链表 C. 哈希表 D. 栈9.以下数据结构中,哪一个是线性结构( D )?【北方交通大学2001 一、1(2分)】A.广义表 B. 二叉树 C. 稀疏矩阵 D. 串10.以下那一个术语与数据的存储结构无关?(A)【北方交通大学2001 一、2(2分)】A.栈 B. 哈希表 C. 线索树 D. 双向链表11.在下面的程序段中,对x的赋值语句的频度为(C)【北京工商大学2001 一、10(3分)】FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A.O(2n) B.O(n) C.O(n2) D.O(log2n)12.程序段FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换;其中n为正整数,则最后一行的语句频度在最坏情况下是(D)A. O(n)B. O(nlogn)C. O(n3)D. O(n2) 【南京理工大学1998一、1(2分)】13.以下哪个数据结构不是多型数据类型(D)【中山大学1999 一、3(1分)】A.栈B.广义表C.有向图D.字符串14.以下数据结构中,(A)是非线性数据结构【中山大学1999 一、4】A.树B.字符串C.队D.栈15. 下列数据中,(C)是非线性数据结构。
第1章绪论一、选择题1. 算法的计算量的大小称为计算的()。
【北京邮电大学2000 二、3 (20/8分)】A.效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于()【中科院计算所1998 二、1 (2分)】A.问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是(1),它必须具备(2)这三个特性。
(1) A.计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A.可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性【南京理工大学1999 一、1(2分)【武汉交通科技大学1996 一、1(4分)】4.一个算法应该是()。
【中山大学1998 二、1(2分)】A.程序B.问题求解步骤的描述C.要满足五个基本特性D.A和C.5. 下面关于算法说法错误的是()【南京理工大学2000 一、1(1.5分)】A.算法最终必须由计算机程序实现B. 为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是()【南京理工大学2000 一、2 (1.5分)】(1)算法原地工作的含义是指不需要任何额外的辅助空间(2)在相同的规模n下,复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法(3)所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界(4)同一个算法,实现语言的级别越高,执行效率就越低A.(1) B.(1),(2) C.(1),(4) D.(3)7.从逻辑上可以把数据结构分为()两大类。
【武汉交通科技大学1996 一、4(2分)】A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构8.以下与数据的存储结构无关的术语是()。
【北方交通大学2000 二、1(2分)】A.循环队列 B. 链表 C. 哈希表 D. 栈9.以下数据结构中,哪一个是线性结构()?【北方交通大学2001 一、1(2分)】A.广义表 B. 二叉树 C. 稀疏矩阵 D. 串10.以下那一个术语与数据的存储结构无关?()【北方交通大学2001 一、2(2分)】A.栈 B. 哈希表 C. 线索树 D. 双向链表11.在下面的程序段中,对x的赋值语句的频度为()【北京工商大学2001 一、10(3分)】FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A.O(2n) B.O(n) C.O(n2) D.O (log2n)12.程序段FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换;其中n为正整数,则最后一行的语句频度在最坏情况下是()A. O(n)B. O(nlogn)C. O(n3)D. O(n2) 【南京理工大学1998一、1(2分)】13.以下哪个数据结构不是多型数据类型()【中山大学1999 一、3(1分)】A.栈B.广义表C.有向图D.字符串14.以下数据结构中,()是非线性数据结构【中山大学1999 一、4】A.树B.字符串C.队D.栈15. 下列数据中,()是非线性数据结构。
数据结构考研真题试卷一、选择题(每题2分,共20分)1. 在数据结构中,线性结构和非线性结构的区别在于:A. 数据元素的个数B. 是否有前驱和后继元素C. 数据元素之间是否有一对一的线性关系D. 数据元素的存储方式2. 栈(Stack)是一种特殊的线性表,其特点是:A. 只能在一端进行数据的插入和删除操作B. 只能在两端进行数据的插入和删除操作C. 可以在任意位置进行数据的插入和删除操作D. 只能在中间进行数据的插入和删除操作3. 以下哪个算法不是排序算法:A. 冒泡排序B. 快速排序C. 二分查找D. 归并排序4. 哈希表(Hash Table)解决冲突最常用的方法是:A. 链接法B. 线性探测法C. 二次探测法D. 所有选项都是5. 在二叉树的遍历算法中,先序遍历的顺序是:A. 根-左-右B. 左-根-右C. 右-根-左D. 根-右-左...二、填空题(每空1分,共10分)1. 在图的遍历中,深度优先搜索(DFS)使用___________实现。
2. 一个具有n个顶点的无向图最多有___________条边。
3. 折半查找法的时间复杂度是___________。
4. 树的度是___________。
5. 一个栈的初始状态为空,如果只允许push和pop操作,那么该栈的容量至少是___________。
...三、简答题(每题10分,共20分)1. 简述什么是二叉搜索树,并说明其特点。
2. 解释什么是图的连通分量,并举例说明。
...四、计算题(每题15分,共30分)1. 给定一个数组A[1...n],请计算其快速排序的时间复杂度,并分析最好、最坏和平均情况。
2. 假设有一个哈希表,其大小为m,使用线性探测法解决冲突。
如果表中已有k个元素,试计算此时的平均查找长度。
...五、编程题(每题20分,共20分)1. 编写一个函数,实现单链表的反转,并说明其时间复杂度和空间复杂度。
...注意:- 请在规定时间内完成试卷。
一、选择题1. 算法的计算量的大小称为计算的(B )。
【北京邮电大学2000 二、3 (20/8分)】A.效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于(C )【中科院计算所1998 二、1 (2分)】A.问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是(1),它必须具备(2)这三个特性。
(1) A.计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A.可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性【南京理工大学1999 一、1(2分)【武汉交通科技大学1996 一、1(4分)】4.一个算法应该是()。
【中山大学1998 二、1(2分)】A.程序B.问题求解步骤的描述C.要满足五个基本特性D.A 和C.5. 下面关于算法说法错误的是()【南京理工大学2000 一、1(1.5分)】A.算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是()【南京理工大学2000 一、2 (1.5分)】(1)算法原地工作的含义是指不需要任何额外的辅助空间(2)在相同的规模n下,复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法(3)所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界(4)同一个算法,实现语言的级别越高,执行效率就越低A.(1) B.(1),(2) C.(1),(4) D.(3)7.从逻辑上可以把数据结构分为()两大类。
【武汉交通科技大学1996 一、4(2分)】A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构8.以下与数据的存储结构无关的术语是()。
【北方交通大学2000 二、1(2分)】A.循环队列 B. 链表 C. 哈希表 D. 栈9.以下数据结构中,哪一个是线性结构()?【北方交通大学2001 一、1(2分)】A.广义表 B. 二叉树 C. 稀疏矩阵 D. 串10.以下那一个术语与数据的存储结构无关?()【北方交通大学2001 一、2(2分)】A.栈 B. 哈希表 C. 线索树 D. 双向链表11.在下面的程序段中,对x的赋值语句的频度为()【北京工商大学2001 一、10(3分)】FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A.O(2n) B.O(n) C.O(n2) D.O(log2n)12.程序段FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换;其中n为正整数,则最后一行的语句频度在最坏情况下是()A. O(n)B. O(nlogn)C. O(n3)D. O(n2) 【南京理工大学1998一、1(2分)】13.以下哪个数据结构不是多型数据类型()【中山大学1999 一、3(1分)】A.栈B.广义表C.有向图D.字符串14.以下数据结构中,()是非线性数据结构【中山大学1999 一、4】A.树B.字符串C.队D.栈15. 下列数据中,()是非线性数据结构。
[考研类试卷]计算机专业基础综合数据结构(集合)历年真题试卷汇编5.doc[考研类试卷]计算机专业基础综合数据结构(集合)历年真题试卷汇编5一、填空题1 对于具有144个记录的文件,若采用分块查找法,且每块长度为8,则平均查找长度为__________。
【北方交通大学2001二、8】2 有一个2000项的表,欲采用等分区间顺序查找方法进行查找,则每块的理想长度是 (1),分成 (2) 块最为理想,平均查找长度是 (3) 。
【中国矿业大学2000一、6(3分)】3 分块检索中,若索引表和各块内均用顺序查找,则有900个元素的线性表分成__________块最好;若分成25块,其平均查找长度为__________。
【北京工业大学1999一、5(2分)】4 执行顺序查找时,储存方式可以是(1),二分法查找时,要求线性表(2),分块查找时要求线性表(3),而散列表的查找,要求线性表的存储方式是(4)。
【山东大学1998一、1(3分)】5 查找是非数值程序设计的一个重要技术问题,基本上分成(1)查找,(2)查找和(3)查找。
处理哈希冲突的方法有(4)、(5)、(6)和(7)。
【华北计算机系统工程研究所1999一(5分)】6 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中,则对这样的二叉排序树检索时,平均比较次数为__________。
【山东大学1999二、1(4分)】7 在含有n个结点的二叉排序树中查找一个关键字,进行关键字比较次数的最大值是__________。
【北京交通大学2004一、15(2分)】8 在二叉排序树上成功地找到一个结点,在平均情况下的时间复杂性是:__________,在最坏情况下的时间复杂性是__________。
【上海交通大学2004五、1(15/4分)】9 AVL树__________是完全二叉树;完全二叉树__________是AVL 树。
【电子科技大学2005二、5(1分)】10 一棵深度为k的平衡二叉树,其每个非终端结点的平衡因子均为0,则该树共有__________个结点。
计算机专业基础综合数据结构(概论)历年真题试卷汇编3计算机专业基础综合数据结构(概论)历年真题试卷汇编3(总分:70.00,做题时间:90分钟)一、单项选择题(总题数:15,分数:30.00)1.设n是描述问题规模的非负整数,下面程序片段的时间复杂度是( )。
【2011年全国硕士研究生入学计算机学科专业基础综合试题】简称【201 1年全国试题1(2分)】 x=2; while(x *x;(分数:2.00)A.O(log 2 n) √B.O(n)C.O(nlog 2 n)D.O(n 2 )解析:2.求整数n(n≥0)阶乘的算法如下,其时间复杂度是( )。
【2012年全国试题1(2分)】int fact(int n){if(n<=i) return i;return n*fact(n 一1);(分数:2.00)A.O(log 2 n)B.O(n) √C.O(nlog 2 n)D.O(n 2 )解析:3.已知两个长度分别为m和n的升序链表,若将它们合并为一个长度为m+n的降序链表,则最坏情况下的时间复杂度是( )。
【2013年全国试题1(2)分】(分数:2.00)A.O(n)B.O(m×n)C.O(min(m,n))D.O(max(m,n)) √解析:4.下列程序段的时间复杂度是( )。
【2014年全国试题1(2分)】count=0;for(k=1;k<=n;k*=2)for(j=1;j<=n;j++)count++;(分数:2.00)A.O(log 2 n)B.O(n)C.O(nlog 2 n) √D.O(n 2 )解析:5.在数据结构中,数据的最小单位是( )。
【北京理工大学2006九、1(1分)】(分数:2.00)A.数据元素B.字节C.数据项√D.结点解析:6.在数据结构中,数据的基本单位是( )。
【北京理工大学2004五、1(1分)】(分数:2.00)A.数据项B.数据类型C.数据元素√D.数据变量解析:7.数据对象是指( )。
第十一章文件一、选择题1. 散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址,因为散列函数是一对一的关系,则选择好的()方法是散列文件的关键。
【哈尔滨工业大学 2001二、5 (2分)】A. 散列函数B. 除余法中的质数C. 冲突处理D. 散列函数和冲突处理2. 顺序文件采用顺序结构实现文件的存储,对大型的顺序文件的少量修改,要求重新复制整个文件,代价很高,采用()的方法可降低所需的代价。
【北京邮电大学 2000 二、8 (20/8分)】A. 附加文件B. 按关键字大小排序C. 按记录输入先后排序D. 连续排序3. 用ISAM组织文件适合于()。
【中科院软件所 1998】A.磁带 B.磁盘4.下述文件中适合于磁带存储的是()。
【中科院计算所 2000 一、7(2分)】A. 顺序文件B. 索引文件C. 散列文件D. 多关键字文件5. 用ISAM和VSAM组织文件属于()。
A. 顺序文件B. 索引文件C. 散列文件【中国科技大学 1998 二、5(2分)中科院计算所 1998 二、5(2分)】6. ISAM文件和VASM文件属于()。
【山东大学 2001 二、5 (1分)】A. 索引非顺序文件B. 索引顺序文件C. 顺序文件D. 散列文件7. B+树应用在()文件系统中。
【北京邮电大学 2001 一、1(2分)】A. ISAMB. VSAM二、判断题1. 文件是记录的集合,每个记录由一个或多个数据项组成,因而一个文件可看作由多个记录组成的数据结构。
【长沙铁道学院 1998 一、5 (1分)】2. 倒排文件是对次关键字建立索引。
【南京航空航天大学 1997 一、10(1分)】3. 倒排序文件的优点是维护简单。
【南京航空航天大学 1995 五、10(1分)】4. 倒排文件与多重表文件的次关键字索引结构是不同的。
【西安交通大学 1996 二、6 (3分)】5. Hash表与Hash文件的唯一区别是Hash文件引入了‘桶’的概念。
一、选择题1. 算法的计算量的大小称为计算的(B )。
【北京邮电大学2000 二、3 (20/8分)】A.效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于(C )【中科院计算所1998 二、1 (2分)】A.问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是(1),它必须具备(2)这三个特性。
(1) A.计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A.可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性【南京理工大学1999 一、1(2分)【武汉交通科技大学1996 一、1(4分)】4.一个算法应该是()。
【中山大学1998 二、1(2分)】A.程序B.问题求解步骤的描述C.要满足五个基本特性D.A 和C.5. 下面关于算法说法错误的是()【南京理工大学2000 一、1(1.5分)】A.算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是()【南京理工大学2000 一、2 (1.5分)】(1)算法原地工作的含义是指不需要任何额外的辅助空间(2)在相同的规模n下,复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法(3)所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界(4)同一个算法,实现语言的级别越高,执行效率就越低A.(1) B.(1),(2) C.(1),(4) D.(3)7.从逻辑上可以把数据结构分为()两大类。
【武汉交通科技大学1996 一、4(2分)】A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构8.以下与数据的存储结构无关的术语是()。
【北方交通大学2000 二、1(2分)】A.循环队列 B. 链表 C. 哈希表 D. 栈9.以下数据结构中,哪一个是线性结构()?【北方交通大学2001 一、1(2分)】A.广义表 B. 二叉树 C. 稀疏矩阵 D. 串10.以下那一个术语与数据的存储结构无关?()【北方交通大学2001 一、2(2分)】A.栈 B. 哈希表 C. 线索树 D. 双向链表11.在下面的程序段中,对x的赋值语句的频度为()【北京工商大学2001 一、10(3分)】FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A.O(2n) B.O(n) C.O(n2) D.O(log2n)12.程序段FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换;其中n为正整数,则最后一行的语句频度在最坏情况下是()A. O(n)B. O(nlogn)C. O(n3)D. O(n2) 【南京理工大学1998一、1(2分)】13.以下哪个数据结构不是多型数据类型()【中山大学1999 一、3(1分)】A.栈B.广义表C.有向图D.字符串14.以下数据结构中,()是非线性数据结构【中山大学1999 一、4】A.树B.字符串C.队D.栈15. 下列数据中,()是非线性数据结构。
第1章绪论一、选择题1. 算法的计算量的大小称为计算的()。
【北京邮电大学2000 二、3 (20/8分)】A.效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于()【中科院计算所1998 二、1 (2分)】A.问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是(1),它必须具备(2)这三个特性。
(1) A.计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A.可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性【南京理工大学1999 一、1(2分)【武汉交通科技大学1996 一、1(4分)】4.一个算法应该是()。
【中山大学1998 二、1(2分)】A.程序B.问题求解步骤的描述C.要满足五个基本特性D.A和C.5. 下面关于算法说法错误的是()【南京理工大学2000 一、1(1.5分)】A.算法最终必须由计算机程序实现B. 为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是()【南京理工大学2000 一、2 (1.5分)】(1)算法原地工作的含义是指不需要任何额外的辅助空间(2)在相同的规模n下,复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法(3)所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界(4)同一个算法,实现语言的级别越高,执行效率就越低A.(1) B.(1),(2) C.(1),(4) D.(3)7.从逻辑上可以把数据结构分为()两大类。
【武汉交通科技大学1996 一、4(2分)】A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构8.以下与数据的存储结构无关的术语是()。
【北方交通大学2000 二、1(2分)】A.循环队列 B. 链表 C. 哈希表 D. 栈9.以下数据结构中,哪一个是线性结构()?【北方交通大学2001 一、1(2分)】A.广义表 B. 二叉树 C. 稀疏矩阵 D. 串10.以下那一个术语与数据的存储结构无关?()【北方交通大学2001 一、2(2分)】A.栈 B. 哈希表 C. 线索树 D. 双向链表11.在下面的程序段中,对x的赋值语句的频度为()【北京工商大学2001 一、10(3分)】FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A.O(2n) B.O(n) C.O(n2) D.O (log2n)12.程序段FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换;其中n为正整数,则最后一行的语句频度在最坏情况下是()A. O(n)B. O(nlogn)C. O(n3)D. O(n2) 【南京理工大学1998一、1(2分)】13.以下哪个数据结构不是多型数据类型()【中山大学1999 一、3(1分)】A.栈B.广义表C.有向图D.字符串14.以下数据结构中,()是非线性数据结构【中山大学1999 一、4】A.树B.字符串C.队D.栈15. 下列数据中,()是非线性数据结构。
一、填空题(1)【答案】220y y y '''-+=.【详解】因为二阶常系数线性齐次微分方程0y py qy '''++=的通解为12(sin cos )x y e c x c x αββ=+时,则特征方程20r pr q ++=对应的两个根为一对共轭复根:1,2i λαβ=±,所以根据题设12(sin cos )xy e c x c x =+(12,c c 为任意常数)为某二阶常系数线性齐次微分方程的通解,知:1,1αβ==,特征根为1,2λi αβ=±1,i =±从而对应的特征方程为:()()2(1)(1)220,i i λλλλ-+--=-+=于是所求二阶常系数线性齐次微分方程为220y y y '''-+=.(2)【答案】2.3【分析】若(),,r x y z 具有连续的一阶偏导数,梯度gr adr 在直角坐标中的计算公式为:r r r gradr i j k x y z∂∂∂=++∂∂∂设()()()(),,,,,,,,A x y z P x y z i Q x y z j R x y z k =++,其中,,P Q R 具有一阶连续偏导数,散度d ivA 在直角坐标中的计算公式为:P Q R divA x y z∂∂∂=++∂∂∂若(),,r x y z 具有二阶连续偏导数,则在直角坐标中有计算公式:222222()r r rdiv gradr x y z∂∂∂=++∂∂∂【详解】本题实际上是计算222222r r rx y z∂∂∂++∂∂∂r x ∂∂222x y z x ∂++=∂22222xx y z=++222x x y z =++xr=2001年全国硕士研究生入学统一考试数学一试题解析22r x ∂∂x x r ∂⎛⎫= ⎪∂⎝⎭2rr xx r∂-∂=2x r x r x r x r r -∂ = ∂223r x r -=类似可得r y y r ∂=∂,22r y ∂∂223r y r -=;r z z r ∂=∂,22r z ∂∂223r z r -=根据定义有()div gradr 222222r r r x y z ∂∂∂=++∂∂∂222222333r x r y r z r r r ---=++222233r x y z r ---=2233r r r-=232r r =2r =2222x y z =++于是(1,2,2)()|div gradr -()2221,2,22x y z -=++2222231(2)2==+-+(3)【答案】211(,).xdx f x y dy -⎰⎰【详解】由题设二次积分的限,画出对应的积分区域,如图阴影部分.但在10y -≤≤内,21y ≥-,题设的二次积分并不是(,)f x y 在某区域上的二重积分,因此,应先将题设给的二次积分变形为:1021211(,)(,),yydy f x y dx dy f x y dx ----=-⎰⎰⎰⎰其中{}(,)10,12,D x y y y x =-≤≤-≤≤再由图所示,又可将D 改写为{}(,)12,10,D x y x x y =≤≤-≤≤于是112(,)ydy f x y dx --⎰⎰211(,)ydy f x y dx --=-⎰⎰2011(,)xdx f x y dy-=-⎰⎰211(,).xdx f x y dy -=⎰⎰(4)【答案】1(2).2A E +【详解】要求()A E -的逆,应努力把题中所给条件化成()A EB E -=的形式.由题设240A A E +-=⇒222A A E E +-=⇒()()22A E A E E-+=Oxyx+y=1x=21即()()12,2A E A E E -⋅+=故()()1122A E A E --=+.(5)【答案】12【分析】切比雪夫不等式:{}2()()D X P X E X εε-≥≤【详解】根据切比雪夫不等式有{}22()21()2222D X P XE X -≥≤==二、选择题(1)【答案】(D)【详解】从题设图形可见,在y 轴的左侧,曲线()y f x =是严格单调增加的,因此当0x <时,一定有'()0f x >,对应()y f x '=图形必在x 轴的上方,由此可排除(A),(C);又()y f x =的图形在y 轴右侧靠近y 轴部分是单调增,所以在这一段内一定有'()0f x >,对应()y f x '=图形必在x 轴的上方,进一步可排除(B),故正确答案为(D).(2)【答案】(C)【详解】题目仅设函数(,)f x y 在点(0,0)附近有定义及''(0,0)3,(0,0)1,x y f f ==未设(,)f x y 在点(0,0)可微,也没设(,)z f x y =,所以谈不上dz ,因此可立即排除(A);令(,,)(,)F x y z z f x y =-,则有''''',,1x x y y z F f F f F =-=-=.因此过点(0,0,(0,0))f 的法向量为{}''',,x y z F F F ±={}'',,1x y f f ±--=±{−3,−1,1},可排除(B);曲线(,)z f x y y =⎧⎨=⎩可表示为参数形式:0,(,0)x x y z f x =⎧⎪=⎨⎪=⎩点(0,0,(0,0))f 的切向量为{}{}'1,0,(0,0)1,0,3x f ±=±.故正确选项为(C).(3)【答案】(B)【详解】方法1:因为001()()lim (1)1lim lim ln(1)ln(1)h h h x x f x f x xf e e x h x x x →→→--==⋅--0()ln(1)limx f x x x x x x → -- ⋅- ()()00()0()lim 0limx x f x f f x f x x →→-=- =0 -()0f '=可见,若()f x 在点0x =可导,则极限01lim(1)h h f e h→-一定存在;反过来也成立.方法2:排除法:举反例说明(A),(C),(D)说明不成立.比如,()f x x =,在0x =处不可导,但2220001cos 11cos lim (1cos )lim lim h h h h h f h h h h →→→---==22012sin 2lim h h h →⎛⎫ ⎪⎝⎭=2201112sin lim 22h h h h h →⎛⎫ ⎪⎝⎭ 12=,故排除(A)2200sin 1lim (sin )lim h h h h f h h h h→→--=30sin lim h h h h h →-=⋅其中,30sin limh h h h →-30sin lim h h h h →-=201cos lim 3h h h →- 洛22012sin 2lim 3h h h →⎛⎫ ⎪⎝⎭=22012lim 3h hh → 等16=根据有界量与无穷小的乘积为无穷小,所以3sinhlim0h h h h→-⋅=.故排除(C).又如1,0()0,0x f x x ≠⎧=⎨=⎩在0x =处不可导,但[]00111lim (2)()lim0h h f h f h h h →→--==存在,进一步可排除(D).(4)【答案】(A)【详解】方法1:因为A 是实对称矩阵,必相似于对角阵Λ.1111111111111111E A λλλλλ---------=--------44442,3,41111111111111λλλλλλλ----------------行分别加到行111111111(4)111141111λλλλλ--------------行提出公因子()11111000(4)000000λλλλ-行分别加到2,3,4行34λλ=-()=0得A 的特征值为:12344,0,λλλλ====故必存在正交矩阵Q ,使得14000000000000000T Q AQ Q AQ -⎡⎤⎢⎥⎢⎥==⎢⎥⎢⎥⎣⎦因此,A B 与相似.由两矩阵合同的充要条件:实对称矩阵A B 与合同的充要条件是A B 与相似.因此,A B 与也合同.即A B 与既合同且相似.应选(A).方法2:因为A 是实对称矩阵,故A 必相似于一对角阵Λ.又由相似矩阵有相同的特征值,相同的秩,知A 与Λ有相同的秩,故()()1,r r A Λ==即Λ对角线上有3个元素为零.因此,1230λλλ===是A 的特征值.求另一个特征值,由特征值的和等于矩阵主对角线元素之和,知444114.iii i i a λλ=====∑∑故,44λ=.即A 有特征值40λλ==和(三重根),和对角阵B 的特征值完全一致,故A ,B 相似.又由两矩阵合同的充要条件:实对称矩阵A B 与合同的充要条件是A B 与相似.知A ,B 合同.(5)【答案】A【详解】掷硬币结果不是正面向上就是反面向上,所以X Y n +=,从而Y n X =-,故()DY D n X DX=-=由方差的定义:22()DX EX EX =-,所以[]22()()()DY D n X E n X E n X =-=---222(2)()E n nX X n EX =-+--222222()n nEX EX n nEX EX =-+-+-22()EX EX DX =-=)由协方差的性质:c ov(,)0X c =(c 为常数);c ov(,)cov(,)aX bY ab X Y =1212cov(,)cov(,)cov(,)X X Y X Y X Y +=+)所以c ov(,)cov(,)cov(,)cov(,)0X Y X n X X n X X DX DX=-=-=-=-由相关系数的定义,得c ov(,)(,)1X Y DX X Y DX DYDX DXρ-===-三【详解】2a rctan x x e dx e⎰2a rctan x x e e dx -=⎰()21arctan 22x xe e d x -=--⎰()21arctan 2x x e d e -=-⎰()221arctan arctan 2x x x xe e e d e ----⎰分部2221arctan 2(1)x x xx x de e e e e -⎛⎫=-- ⎪+⎝⎭⎰222111arctan 21x x x x x e e de ee -⎛⎫⎛⎫=---⎪ ⎪+⎝⎭⎝⎭⎰22211arctan 21x x x x x x e e e de de e --⎛⎫=--+ ⎪+⎝⎭⎰⎰()21arctan arctan 2xx x x e e e e C --=-+++四【详解】由题设,()d x dx ϕ[](,(,))df x f x x dx=()12(,(,))(,(,))(,)f x f x x f x f x x f x x '''=+1212(,(,))(,(,))(,)(,)f x f x x f x f x x f x x f x x ⎡⎤''''=++⎣⎦这里1f f x ∂'=∂,2ff y∂'=∂,所以1()x d x dx ϕ={}12121(,(,))(,(,))(,)(,)x f x f x x f x f x x f x x f x x =⎡⎤''''=++⎣⎦1212(1,1)(1,1)(1,1)(1,1)f f f f ⎡⎤''''=++⎣⎦[]2323=+⋅+17=又(1,1)1,f =()(,(,))x f x f x x ϕ=,所以(1)(1,(1,1))f f ϕ=(1,1)1(1,1)f f = 1,=所以3211()()3()x x d d x x x dxdx ϕϕϕ==⎡⎤=⎢⎥⎣⎦21()3(1)x d x dx ϕϕ==1()(1)1,173117x d x dx ϕϕ= == ⋅⋅51=五【详解】首先将a rctan x 展开.因为()a rctan 'x =2211(1),(1,1)1n n n x x x ∞==-∈-+∑故()0arctan arctan 0arctan 'xx x dx =+⎰2000(1)xn n n x dx ∞=⎛⎫=+- ⎪⎝⎭∑⎰22100(1)(1)21n xnnn n n x dx x n ∞∞+==-=-=+∑∑⎰,()1,1x ∈-于是21()arctan x f x x x +=22101(1)21n n n x x x n ∞+=+-=+∑220(1)(1)21n n n x x n ∞=-=++∑22200(1)(1)2121n n n n n n x x n n ∞∞+==--=+++∑∑()()011210210(1)(1)(1)20121211n n n n n n x x x n n +-∞∞+==---=++⋅+++-∑∑12211(1)(1)12121n n n n n n x x n n -∞∞==--=+++-∑∑2211(1)(1)12121n n n nn n x xn n ∞∞==--=+-+-∑∑21111(1)2121nn n x n n ∞=⎛⎫=+-- ⎪+-⎝⎭∑221(1)2114n n n x n ∞=-=+-∑,()1,1,0x x ∈-≠又0lim ()x f x →2201(1)2lim 114n n x n x n ∞→=⎛⎫-=+ ⎪-⎝⎭∑1=,且(0)1f =,所以()f x 在0x =处连续,从而0x =时,()f x 221(1)2114n n n x n ∞=-=+-∑也成立.进而()f x 221(1)2114n nn x n∞=-=+-∑,(1,1)x ∈-,又在1x =±处级数22211(1)2(1)21414n n n n n x n n ∞∞==--=--∑∑收敛,2111lim ()lim arctan x x x f x x x --→→+=2111lim lim arctanx x xx x --→→+=⋅242ππ=⋅=()1f =,2111lim ()lim arctan x x x f x x x ++→-→-+=2111lim lim arctan x x xx x ++→-→-+=⋅()2142f ππ⎛⎫=-⋅-==- ⎪⎝⎭,所以()f x 在1x =处左连续,在1x =-处右连续,所以等式可扩大到1x =±,从而221(1)2()114n n n f x x n ∞=-=+-∑,[]1,1x ∈-,变形得221(1)()1142n n n f x x n∞=--=-∑因此21(1)14n n n ∞=--∑221(1)114n n n n ∞=-=⋅-∑[]1(1)12f =-1122π⎡⎤=⋅-⎢⎥⎣⎦1.42π=-六【详解】方法1:用斯托克斯公式之后化成第一型曲面积分计算.记S 为平面2x y z ++=上由L 所围成的有界部分的上侧,(曲线的正向与曲面的侧的方向符合右手法则)D 为S 在x oy 坐标面上的投影,{(,)| 1 }D x y x y =+={}221cos ,cos ,cos {,,1}1x y x yz z z zαβγ''=--''++在2x y z ++=中,左右两边关于x 求偏导,得10x z '+=,得1x z '=-.在2x y z ++=中,左右两边关于y 求偏导,得10y z '+=,得1y z '=-.代入上式得{}111cos ,cos ,cos ,,333αβγ⎧⎫=⎨⎬⎩⎭为S 指定侧方向的单位法向量,由斯托克斯公式得I 222222()(2)(3)Ly z dx z x dy x y dz=-+-+-⎰Sdy dz dzdx dxdy x y z P Q R∂∂∂=∂∂∂⎰⎰22222223Sdydzdzdx dxdy x y z y z z x x y ∂∂∂=∂∂∂---⎰⎰(24)(26)(22)Sy z dydz z x dzdx x y dxdy=--+--+--⎰⎰将题中的空间曲线积分化为第二类曲面积分,而对于第二类曲面积分,一般的解答方法是将它先化为第一类曲面积分,进而化为二重积分进行计算.把111,,cos cos cos dS dydz dS dzdx dS dxdy αβλ===代入上式,I [](24)cos (26)cos (22)cos Sy z z x x y dSαβγ=--+--+--⎰⎰[]1(24)(26)(22)3Sy z z x x y dS =--+--+--⎰⎰[]18463S x y z dS =---⎰⎰2(423)3Sx y z dS =-++⎰⎰按第一型曲面积分的算法,将S 投影到x oy ,记为σ.d S 与它在x oy 平面上的投影d σ的关系是2211cos x y dS d z z d σσγ''==++故3dS d σ=,将2x y z ++=代入2(423)3S I x y z dS =-++⎰⎰2[423(2)](3)3Sx y x y d σ=-++--⎰⎰2(6)Dx y d σ=--+⎰⎰由于D 关于y 轴对称,利用区域的对称性,因为区域关于y 轴对称,被积函数是关于x 的奇函数,所以0Dxd σ=⎰⎰.D 关于x 轴对称,利用区域的对称性,因为区域关于x 轴对称,被积函数是关于y 的奇函数,故0Dyd σ=⎰⎰,所以2(6)DI x y d σ=--+⎰⎰2212DDDxd yd d σσσ=-+-⎰⎰⎰⎰⎰⎰12Ddxdy=-⎰⎰12D =-⋅的面积(由二重积分的几何意义知,Ddxdy ⎰⎰即D 的面积)其中,D 为1x y +≤,D 的面积141122=⋅⋅⋅=,所以12224.I =-⋅=-方法2:转换投影法.用斯托克斯公式,取平面2x y z ++=被L 所围成的部分为S ,按斯托克斯公式的规定,它的方向向上(曲线的正向与曲面的侧的方向符合右手法则),S 在x oy 平面上的投影域记为{(,)| 1 }D x y x y =+=.由斯托克斯公式得I 222222()(2)(3)Ly z dx z x dy x y dz=-+-+-⎰ Sdy dz dzdx dxdy x y z P Q R ∂∂∂=∂∂∂⎰⎰22222223Sdydzdzdxdxdy x y z y z z x x y ∂∂∂=∂∂∂---⎰⎰(24)(26)(22)Sy z dydz z x dzdx x y dxdy=--+--+--⎰⎰由111,,cos cos cos dS dydz dS dzdx dS dxdy αβλ===,及{}221cos ,cos ,cos {,,1}1x y x yz z z zαβγ''=--''++知11cos cos dS dydz dxdy αλ==,11cos cos dS dzdx dxdy βλ==,故22221cos 1cos 1xx yx x yz z z dydz dxdy dxdy z dxdy z z αλ'-''++'===-''++22221cos 1cos 1yx yy x yz z z dzdx dxdy dxdy z dxdy z z βλ'-''++'===-''++因为S 为2z x y =--,式子左右两端分别关于,x y 求偏导,1,1,z zx y∂∂=-=-∂∂于是(24)(26)(26)SI y z dydz z x dzdx x y dxdy=--+--+--⎰⎰{}24,26,26,,1S z z y z z x x y dxdyx y ⎧⎫∂∂=------⋅--⎨⎬∂∂⎩⎭⎰⎰2(423)2(6)SDx y z dxdy x y dxdy=-++=--+⎰⎰⎰⎰因为区域D 关于y 轴对称,被积函数是关于x 的奇函数,所以0Dxd σ=⎰⎰.类似的,因为区域D 关于x 轴对称,被积函数是关于y 的奇函数,故0Dyd σ=⎰⎰,所以2(6)DI x y d σ=--+⎰⎰2212DDDxd yd d σσσ=-+-⎰⎰⎰⎰⎰⎰12Ddxdy=-⎰⎰12D =-⋅的面积(由二重积分的几何意义知,Ddxdy ⎰⎰即D 的面积)D 为1x y +≤,D 的面积141122=⋅⋅⋅=,所以12224.I =-⋅=-方法3:降维法.记S 为平面2x y z ++=上由L 所围成的有界部分的上侧(曲线的正向与曲面的侧的方向符合右手法则),D 为S 在x oy 坐标面上的投影,{(,)| 1 }D x y x y =+=把2x y z ++=代入I 中,1L 为L 在x oy 平面上投影,逆时针.1222222((2))(2(2))(3)()L I y x y dx x y x dy x y dx dy =---+---+---⎰ 12222(42444)(324888)L y x xy x y dx y x xy x y dy =--++-+-+--+⎰ 12222(324888)(42444)[]L y x xy x y y x xy x y dxdy x y ∂-+--+∂--++--∂∂⎰ 格林公式2(6)24Dx y dxdy =--+=-⎰⎰方法4:用斯托克斯公式后用第二型曲面积分逐个投影法.记S 为平面2x y z ++=上由L 所围成的有界部分的上侧,(曲线的正向与曲面的侧的方向符合右手法则){}221cos ,cos ,cos {,,1}1x y x yz z z zαβγ''=--''++在2x y z ++=中,左右两边关于x 求偏导,得10x z '+=,得1x z '=-.在2x y z ++=中,左右两边关于y 求偏导,得10y z '+=,得1y z '=-.代入上式得{}111cos ,cos ,cos ,,333αβγ⎧⎫=⎨⎬⎩⎭为S 指定侧方向的单位法向量,由斯托克斯公式得I 222222()(2)(3)Ly z dx z x dy x y dz=-+-+-⎰ Sdy dz dzdx dxdy x y z P Q R∂∂∂=∂∂∂⎰⎰22222223Sdydzdzdx dxdy x y z y z z x x y ∂∂∂=∂∂∂---⎰⎰(24)(26)(22)Sy z dydz z x dzdx x y dxdy=--+--+--⎰⎰用逐个投影法,先计算1(24),SI y z dydz =--⎰⎰其中{}(,)|21yz D y z y z y =--+≤为S 在y oz 平面上的投影,分别令0,0,20,20y y y z y z ≥≤--≥--≤,可得到y z D 的4条边界线的方程:右:23y z +=;上:3z =;左:21y z +=;下:1z =.于是13(3)2111(1)22(2)16z z I dz y z dy --=-+=-⎰⎰再计算2(26)SI z x dzdx =--⎰⎰,其中{}(,)|21xzD x z x x z =+--≤为S 在xoz 平面上的投影,分别令0,0,20,20x x x z x z ≥≤--≥--≤,可得到x z D 的4条边界线的方程:右:23y z +=;上:3z =;左:21y z +=;下:1z =.于是13(3)321211(1)22(3)(6)8z z I dz z x dx z dz --=-+=-=-⎰⎰⎰再计算3(22)D I x y dxdy =--⎰⎰,其中{}(,)|1xyDx y x y =+≤为S 在xoy 平面上的投影,因为区域关于y 轴和x 轴均对称,被积函数是关于x 和y 都是奇函数,于是32()0SI x y dxdy =-+=⎰⎰故12324.I I I I =++=-方法5:参数式法.L 是平面2x y z ++=与柱面1x y +=的交线,是由4条直线段构成的封闭折线,将题中要求的空间曲线积分分成四部分来求.当0,0x y ≥≥时,1:1,2L y x z x y =-=--,则,dy dx dz dx =-=-,x 从1到0.以x 为参数,于是222222()(2)(3)y z dx z x dy x y dz-+-+-222222[(1)(2)][2(2)]()[3(1)]()x x y dx x y x dx x x dx =----+----+---22[(1)1(2)(1)]x x dx=--+--则1222222()(2)(3)L y z dx z x dy x y dz-+-+-⎰221(1)1(2)(1)x x dx ⎡⎤=--+--⎣⎦⎰7.3=当0,0x y ≤≥,2:1,12L y x z x =+=-,则,2dy dx dz dx ==-,x 从0到1-于是222222()(2)(3)y z dx z x dy x y dz-+-+-222222[(1)(12)][2(12)][3(1)](2)x x dx x x dx x x dx =+--+--+-+-(24)x dx=+所以212222220()(2)(3)(24)3L y z dx z x dy x y dz x dx --+-+-=+=-⎰⎰ 当0,0x y ≤≤,3:1,3L y x z =-=,则,0dy dx dz =-=,x 从1-到0,于是222222()(2)(3)y z dx z x dy x y dz-+-+-222222[(1)3][23]()[3(1)]0x dx x dx x x =--+⋅--+--⋅2(2226)x x dx=+-所以32222222179()(2)(3)(2226)3L y z dx z x dy x y dz x x dx --+-+-=+-=-⎰⎰ 当0,0x y ≥≤,4:1,32L y x z x =-=-,则,2dy dx dz dx ==-,x 从0到1,于是222222()(2)(3)y z dx z x dy x y dz-+-+-222222[(1)(32)][2(32)][3(1)](2)x x dx x x dx x x dx =---+--+---(1812)x dx=-+所以412222220()(2)(3)(1812) 3.L y z dx z x dy x y dz x dx -+-+-=-+=⎰⎰ 所以123424.LL L L L I ==+++=-⎰⎰⎰⎰⎰ 七【分析】拉格朗日中值定理:如果()f x 满足在闭区间[],a b 上连续,在开区间(),a b 内可导,则至少存在一点(),a b ξ∈,使等式()()()()f b f a f b a ξ'-=-成立【详解】(1)因为()y f x =在(1,1)-内具有二阶连续导数,所以一阶导数存在,由拉格朗日中值定理得,任给非零(1,1)x ∈-,存在()x θ∈(0,1),()(1,1)x x θ⋅∈-,使[]()(0)'()f x f xf x x θ=+⋅,(0()1)x θ<<成立.因为()f x ''在(1,1)-内连续且"()0,f x ≠所以()f x ''在(1,1)-内不变号,不妨设"()0,f x >则()f x '在(1,1)-内严格单调且增加,故()x θ唯一.(2)方法1:由(1)知[]()(0)'()f x f xf x x θ=+⋅,(0()1)x θ<<于是有[]'()()(0)xf x x f x f θ=-,即[]()(0)'()f x f f x x xθ-=所以[]2'()'(0)()(0)'(0)f x x f f x f f xxx θ---=上式两边取极限,再根据导数定义,得左端=[]0'()'(0)limx f x x f x θ→-[]0'()'(0)lim ()()x f x x f x x x θθθ→-=[]0'()'(0)limlim ()()x x f x x f x x xθθθ→→-=0"(0)lim ()x f x θ→=右端=20()(0)'(0)limx f x f f x x →--0'()'(0)lim2x f x f x →- 洛01'()'(0)lim 20x f x f x →-=-1"(0)2f 导数定义左边=右边,即01"(0)lim ()"(0)2x f x f θ→=,故01lim ().2x x θ→=方法2:由泰勒公式得()21()(0)'(0)"(),02f x f f x f x x ξξ=++ ∈,再与(1)中的[]()(0)'()(0()1)f x f xf x x x θθ=+<<比较,所以[]21'()()(0)'(0)"(),2xf x x f x f f x f x θξ=-=+约去x ,有[]1'()'(0)"(),2f x x f f x θξ=+凑成[]'()'(0)1()"(),()2f x x f x f x xθθξθ-=由于[]0'()'(0)lim "(0)()x f x x f f x xθθ→-=,00lim "()lim "()"(0)x f x f f ξξ→→==所以01"(0)lim ()"(0)2x f x f θ→=故01lim ().2x x θ→=八【详解】222222()1()0()()2x y z h t x y h t h t +=-≥⇒+≤,所以侧面在x oy 面上的投影为:()2221,:()2D x y x y h t ⎧⎫=+≤⎨⎬⎩⎭记V 为雪堆体积,S 为雪堆的侧面积,则由体积公式V (),Df x y dxdy =⎰⎰Dzdxdy =⎰⎰222()()()D x y h t dxdy h t ⎡⎤+=-⎢⎥⎣⎦⎰⎰化为极坐标,令c os ,sin x r y r θθ= =,()0,022h t r πθ≤≤≤≤V ()22202()()h t r d h t rdr h t πθ⎛⎫=- ⎪⎝⎭⎰⎰()22022()()h tr h t rdr h t π⎛⎫=- ⎪⎝⎭⎰()()22222()()h t h t r h t rdr rdr h t π⎛⎫=--⎪ ⎪⎝⎭⎰⎰()()24222()22()h t h t r r h t h t π⎛⎫ ⎪=-⎪⎪⎝⎭33()()248h t h t π⎛⎫=- ⎪⎝⎭3()4h t π=再由侧面积公式:()()22''1x y DS f f dxdy =++⎰⎰()()221xy Dz z dxdy''=++⎰⎰22441()()Dx y dxdy h t h t ⎛⎫⎛⎫=++ ⎪ ⎪⎝⎭⎝⎭⎰⎰22216()1()D x y dxdy h t +=+⎰⎰化为极坐标,令c os ,sin x r y r θθ= =,()0,022h t r πθ≤≤≤≤S =()()22220161h t r d rdr h t πθ+⎰⎰()()22201621h t r rdr h t π=+⎰()()22220161h t r dr h t π=+⎰()()()()22222201616116h t h t r r d h t h t π=+⎰()()()32222202161163h t h t r h t π⎛⎫=⋅⋅+ ⎪ ⎪⎝⎭()()()32232228211163h t h t h t π⎡⎤⎛⎫⎢⎥=⋅⋅+- ⎪ ⎪⎢⎥⎝⎭⎢⎥⎣⎦()()22271163h t π=⋅⋅-213()12h t π=由题意知0.9(),dVS t dt =-将上述()V t 和()S t 代入,得32()13()40.912dh t h t dt ππ=-⋅223()13()()0.9412dh t h t h t dt ππ⇒=-⋅() 1.3dh t dt ⇒=-积分解得13()10h t t C =-+由()0130h =,得130C =.所以13()130.10h t t =-+令()0h t →,即13130010t -+→100t ⇒→因此高度为130厘米的雪堆全部融化所需要时间为100小时.九【详解】由题设知,12,,,s βββ 均为12,,,s ααα 的线性组合,齐次方程组当有非零解时,解向量的任意组合仍是该齐次方程组的解向量,所以12,,,s βββ 均为0Ax =的解.下面证明12,,,s βββ 线性无关.设11220s s k k k βββ+++= ()*把11122,t t βαα=+21223,t t βαα=+121,,s s t t βαα=+ 代入整理得,()()()1121211222110s s s s t k t k t k t k t k t k ααα-++++++= 由12,,,s ααα 为线性方程组0Ax =的一个基础解系,知12,,,s ααα 线性无关,由线性无关的定义,知()*中其系数全为零,即112211221100 0s s s t k t k t k t k t k t k -+=⎧⎪+=⎪⎨⎪⎪+=⎩ 其系数行列式122121210000000000t t t t t t t t122211321211211100000000000(1)ss s t t t t t t t t t t t +--*+-()1121111(1)ss s s t tt t -+-⎛⎫=+- ⎪⎝⎭112(1)s s s t t +=+-(*()变换:把原行列式第i 行乘以21t t -加到第1i +行,其中1,, 1.i s =- )由齐次线性方程组只有零解得充要条件,可见,当12(1)0,sst t +-≠,即12(),sst t ≠-即当s 为偶数,12;t t ≠±当s 为奇数,12t t ≠时,上述方程组只有零解120,s k k k ==== 因此向量组12,,,s βββ 线性无关,故当12122,21,s n t t s n t t =≠±⎧⎨=+≠⎩时,12,,,s βββ 也是方程组0A x =的基础解系.十【详解】(1)方法1:求B ,使1A PBP -=成立,等式两边右乘P ,即AP PB =成立.由题设知,AP ()2,,A x Ax A x =()23,,Ax A x A x =,又3232A x Ax A x =-,故有AP ()22,,32Ax A x Ax A x =-()2000,,103012x Ax A x ⎛⎫⎪= ⎪ ⎪-⎝⎭000103012P ⎛⎫⎪= ⎪⎪-⎝⎭即如果取000103012B ⎛⎫⎪= ⎪ ⎪-⎝⎭,此时的B 满足1A PBP -=,即为所求.方法2:由题设条件()2,,P x Ax A x =是可逆矩阵,由可逆的定义,知有1P -使11PP P P --=()()121112,,,,P x Ax A x P x P Ax P A x ----==E =100010001⎛⎫ ⎪= ⎪⎪⎝⎭即有11121000,1,0001P x P Ax P A x ---⎛⎫⎛⎫⎛⎫ ⎪ ⎪ ⎪=== ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭.由题设条件,3232A x Ax A x =-,有()131232P A x P Ax A x --=-11232P Ax P A x --=-00312001⎛⎫⎛⎫ ⎪ ⎪=- ⎪ ⎪ ⎪ ⎪⎝⎭⎝⎭032⎛⎫⎪= ⎪ ⎪-⎝⎭由1A PBP -=,得1B P AP -=()12,,P A x Ax A x -=()123,,P Ax A x A x -=()11213,,P Ax P A x P A x ---=000103012⎛⎫⎪= ⎪⎪-⎝⎭(2)由(1)及矩阵相似的定义知,A 与B 相似.由矩阵相似的性质:若A B ,则()()f A f B ,则A E +与A E -也相似.又由相似矩阵的行列式相等,得100113011A E B E ⎡⎤⎢⎥+=+=⎢⎥⎢⎥-⎣⎦1001(1)0132011⎡⎤⨯-⎢⎥⎢⎥⎢⎥-⎣⎦行加到行1113(1)11+=--4=-十一【分析】首先需要清楚二项分布的产生背景.它的背景是:做n 次独立重复试验,每次试验的结果只有两个(要么成功,要么失败),每次试验成功的概率都为p ,随机变量X 表示n 次试验成功的次数,则~(,)X B n p .在此题中,每位乘客在中途下车看成是一次实验,每个人下车是独立的,有n 个人相当于做了n 次独立重复实验,把乘客下车看成实验成功,不下车看成实验失败,而且每次实验成功的概率都为p ,则问题(1)成为n 重伯努利实验中有m 次成功.【详解】(1)求在发车时有n 个乘客的条件下,中途有m 人下车的概率,相当于求条件概率{}|P Y m X n ==,由题设知,此条件概率服从二项分布,因此根据二项分布的分布律有:{}|(1),0,0,1,2m mn m n P Y m X n C P P m n n -===-≤≤=(2)求二维随机变量(,)X Y 的概率分布,其实就是求{},P X n Y m ==,利用乘法公式,有{}{}{},|P X n Y m P Y m X n P X n ======又X 服从参数(0)λλ>的泊松分布,由泊松分布的分布律有{}!nP X n en λλ-==故{}{}{},|(1)!m mn mn neP X n Y m P Y m X n P X n C P P n λλ--=======-⋅,其中0,0,1,2m n n ≤≤=十二【详解】记121111,n n i n i i i X X X X n n +====∑∑,则()1212X X X =+,即122X X X =+且1111nin i i i E Xnu E X E X u n nn ==⎛⎫==== ⎪⎝⎭∑∑,211n n i i E X E X u n +=⎛⎫== ⎪⎝⎭∑因此()()()221211()2nn i n i i n i i i E Y E X X XE X X X X ++==⎡⎤⎧⎫⎡⎤=+-=-+-⎨⎬⎢⎥⎣⎦⎣⎦⎩⎭∑∑()()()()22112212n i i n i n i i E X X X X XX X X ++=⎧⎫⎡⎤=-+--+-⎨⎬⎢⎥⎣⎦⎩⎭∑()()()()2211221112n n ni i n i n i i i i E X X E X X X X E X X ++===⎡⎤⎧⎫⎡⎤⎡⎤=-+--+-⎨⎬⎢⎥⎢⎥⎣⎦⎣⎦⎩⎭⎣⎦∑∑∑因为样本方差()221111n i i S X X n =⎡⎤=-⎢⎥-⎣⎦∑是总体方差的无偏估计,则22ES σ=,即()2221111ni i ES E X X n σ=⎡⎤=-=⎢⎥-⎣⎦∑所以()2211(1)ni i E X X n σ=⎡⎤-=-⎢⎥⎣⎦∑,同理()2221(1)nn i i E X X n σ+=⎡⎤-=-⎢⎥⎣⎦∑而()()()()12121122n n i n i i n ii i E X X X X E X X XX ++==⎧⎫⎧⎫⎡⎤⎡⎤--=--⎨⎬⎨⎬⎣⎦⎣⎦⎩⎭⎩⎭∑∑()()1212ni n ii E X X XX +=⎡⎤=--⎣⎦∑()21121ni n i i n i i E X X X X X X X X ++==--+∑()21121ni n i i n i i EX X EX X E X X E X X ++==--+∑由于122,,,(2)n X X X n ≥ 相互独立同分布,则2i X X 与,1n i X X +与,12X X 与也独立(1,2i n = ).而由独立随机变量期望的性质(若随机变量,X Y 独立,且,E X EY 都存在,则E XY EXEY =),所以2i n i i n i EX X EX EX u ++==,222i i EX X EX E X u ==211n i n i E X X E X EX u ++==,21212E X X E X E X u ==故有()()121n i n i i E X X XX +=⎧⎫⎡⎤--⎨⎬⎣⎦⎩⎭∑()21121ni n i i n i i EX X EX X E X X E X X ++==--+∑()22221ni u u u u ==--+=∑即()()()()221122111()2n n n i i n i n i i i i E Y E X X E X X X X E X X ++===⎡⎤⎧⎫⎡⎤⎡⎤=-+--+-⎨⎬⎢⎥⎢⎥⎣⎦⎣⎦⎩⎭⎣⎦∑∑∑()()()2221121n n n σσσ=-+-=-。
山东大学2001
一判断题
1.顺序查找法适用于存储结构为顺序或链接存储的线行表。
2.一个广义表可以为其他广义表所共享。
3.快速排序是选择排序的算法。
4.完全二叉树的某结点若无左子树,则它必是叶子结点。
5.最小代价生成树是唯一的。
6.哈希表的结点中只包含数据元素自身的信息,不包含任何指针。
7.存放在磁盘,磁带上的文件,即可意识顺序文件,也可以是索引文件。
8.折半查找法的查找速度一定比顺序查找法快。
二选择题
1.将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是()。
A. n
B. 2n-1
C. 2n
D. n-1
2.在文件"局部有序"或文件长度较小的情况下,最佳内部排序的方法是()。
A. 直接插入排序
B.气泡排序
C. 简单选择排序
D. 快速排序
3.高度为K的二叉树最的结点数为()。
A. 2
4.一个栈的输入序列是12345,则占的不可能的输出序列是()
A.54321
B. 45321
C.43512
D.12345
5.ISAM文件和V ASM文件属于()
A索引非顺序文件 B. 索引顺序文件 C. 顺序文件 D. 散列文件
6. 任何一棵二叉树的叶子结点在先序,中序和后序遍历序列中的相对次序()
A. 不发生变化
B. 发生变化
C. 不能确定
D. 以上都不对
7.已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是()。
A. acbed
B. decab
C. deabc
D.cedba
三.填空题
1.将下图二叉树按中序线索化,结点的右指针指向(),Y的左指针指向()
E
2.一棵树T中,包括一个度为1的结点,两个度为2的结点,三个。