【2016年湘潭大学考研真题】870数据结构二
- 格式:pdf
- 大小:727.30 KB
- 文档页数:3
数据结构考研真题与答案解析【数据结构考研真题与答案解析】数据结构是计算机科学与技术中的重要学科,也是考研中不可或缺的一部分。
在考研中,掌握数据结构的相关知识对于顺利通过考试至关重要。
本文将为大家介绍一些历年考研真题,并对答案进行解析,希望对大家备考有所帮助。
一、堆排序相关问题1. 2014年考研真题(题目描述)给定n个整数的序列S,其中$n \leq 10^6$且没有相同元素,并且给定另外的一个元素x,输出S中小于x的最大的数,如果不存在则输出“-1”。
(解析)这是一道关于堆排序的问题。
我们可以利用大顶堆来解决这个问题。
首先建立一个大顶堆,然后依次将序列S中的元素插入到堆中。
在插入的过程中,我们可以通过比较当前元素和x的大小,找到小于x的最大的数。
最后输出即可。
若不存在小于x的元素,则输出“-1”。
二、图的遍历问题2. 2016年考研真题(题目描述)对于一个无向图G,设计一个算法,判断图G是否连通,并给出详细的算法描述和复杂度分析。
(解析)对于这个问题,我们可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来解决。
我们可以从图中的任意一个节点开始进行深度或广度遍历,然后标记遍历过的节点。
最后判断所有的节点是否都被遍历到,若是,则图G是连通的,否则不连通。
若使用邻接表表示图,则DFS和BFS的时间复杂度均为O(|V|+|E|),其中|V|和|E|分别代表图中的节点数和边数。
三、二叉搜索树相关问题3. 2018年考研真题(题目描述)给定一个二叉搜索树,请设计一个算法,找出其中第k大的节点。
(解析)对于这个问题,我们可以利用二叉搜索树的性质。
由于二叉搜索树的中序遍历结果是有序的,我们可以进行中序遍历,并将遍历结果保存到一个有序数组中。
然后根据数组中第k个位置的元素找到对应的节点即可。
算法的时间复杂度为O(n),其中n为二叉搜索树中节点的个数。
四、哈夫曼编码问题4. 2017年考研真题(题目描述)给定一段文字,编写一个算法,根据字符出现的频率构建哈夫曼编码。
考研数二历年真题(2016-2002)22016年考研数学二真题一、选择题 1—8小题.每小题4分,共32分. 1.当+→0x 时,若)(lnx 21+α,α11)cos (x -均是比x 高阶的无穷小,则α的可能取值范围是( )(A )),(+∞2 (B )),(21 (C )),(121(D )),(212.下列曲线有渐近线的是 (A )x x y sin += (B )xxy sin +=2(C )xx y 1sin += (D )xx y 12sin+=3.设函数)(x f 具有二阶导数,x f x f x g )())(()(110+-=,则在],[10上( )(A )当0≥)('x f 时,)()(x g x f ≥ (B )当0≥)('x f 时,)()(x g x f ≤(C )当0≥'')(x f 时,)()(x g x f ≥ (D )当0≥'')(x f 时,)()(x g x f ≤ 4.曲线⎩⎨⎧++=+=14722t t y t x ,上对应于1=t 的点处的曲率半径是347.行列式dc d c ba b a 00000等于 (A )2)(bc ad - (B )2)(bc ad -- (C )2222c b da -(D )2222c b da +-8.设321ααα,, 是三维向量,则对任意的常数l k ,,向量31ααk +,32ααl +线性无关是向量321ααα,,线性无关的(A )必要而非充分条件 (B )充分而非必要条件(C )充分必要条件 (D ) 非充分非必要条件二、填空题(本题共6小题,每小题4分,满分24分. 把答案填在题中横线上) 9.⎰∞-=++12521dx x x .10.设)(x f 为周期为4的可导奇函数,且[]2012,),()('∈-=x x x f ,则=)(7f .11.设),(y x z z =是由方程4722=+++z y x eyz确定的函数,则=⎪⎭⎫ ⎝⎛2121,|dz .512.曲线L 的极坐标方程为θ=r ,则L 在点⎪⎭⎫⎝⎛=22ππθ,),(r 处的切线方程为 .13.一根长为1的细棒位于x 轴的区间[]10,上,若其线密度122++-=x x x )(ρ,则该细棒的质心坐标=x .14.设二次型3231222132142x x x ax x x x x x f ++-=),,(的负惯性指数是1,则a 的取值范围是 . 三、解答题15.(本题满分10分) 求极限)ln())((lim xx dt t e t x tx 1112112+--⎰+∞→.16.(本题满分10分) 已知函数)(x y y =满足微分方程''y y y x -=+122,且02=)(y ,求)(x y 的极大值和极小值. 17.(本题满分10分) 设平面区域{}004122≥≥≤+≤=y x y x y x D .,|),(.计算⎰⎰++Ddxdyyx y x x )sin(22π18.(本题满分10分) 设函数)(u f 具有二阶连续导数,)cos (y ef z x=满足6x x e y e z yzx z 222224)cos (+=∂∂+∂∂.若0000==)(',)(f f ,求)(u f 的表达式.19.(本题满分10分)设函数)(),(x g x f 在区间[]b a .上连续,且)(x f 单调增加,10≤≤)(x g ,证明:(1) []b a x a x dt t g x a,,)(∈-≤≤⎰0; (2) ⎰⎰≤⎰+badtt g a adxx g x f dx x f ba )()()()(.20.(本题满分11分)设函数[]101,,)(∈+=x x x x f ,定义函数列)()(x f x f =1,))(()(x f f x f 12=,ΛΛ)),(()(,x f f x fn n1-=设nS 是曲线)(x f y n=,直线01==y x ,所围图形的面积.求极限nn nS ∞→lim .21.(本题满分11分)已知函数),(y x f 满足)(12+=∂∂y yf,且yy y y y f ln )()(),(--+=212,求曲线0=),(y x f 所成的图形绕直线1-=y 旋转所成的旋转体的体积.22.(本题满分11分) 设⎪⎪⎪⎭⎫⎝⎛---=302111104321A ,E 为三阶单位矩阵.7(1) 求方程组0=AX 的一个基础解系; (2) 求满足E AB =的所有矩阵. 23.(本题满分11分) 证明n 阶矩阵⎪⎪⎪⎪⎪⎭⎫⎝⎛111111111ΛM M M ΛΛ与⎪⎪⎪⎪⎪⎭⎫⎝⎛n 00200100ΛM M M ΛΛ相似.2015年全国硕士研究生入学统一考试数学二试题及答案一、选择题:1~8小题,每小题4分,共32分.下列每题给出的四个选项中,只有一个选项符合 题目要求的,请将所选项前的字母填在答题纸...指定位置上.1、下列反常积分中收敛的是() (A)2+∞⎰(B )2ln x dx x+∞⎰(C)21ln dx x x +∞⎰(D)2x x dx e +∞⎰2、函数20sin ()lim(1)x tt t f x x→=+在(,)-∞+∞内()(A )连续 (B )有可去间断点 (C )有跳跃间断8点 (D)有无穷间断点 3、设函数1cos ,0()0,0x x f x xx αβ⎧>⎪=⎨⎪≤⎩(0,0)αβ>>,若()f x '在0x =处连续,则()(A )1αβ-> (B)01αβ<-≤ (C)2αβ-> (D)02αβ<-≤ 4、设函数()f x 在(,)-∞+∞连续,其二阶导函数()f x ''的图形如右图所示,则曲线()y f x =的拐点个数为() (A )0 (B)1 (C)2 (D)35、设函数(u v)f ,满足22(,)yf x y xy x +=-,则11u v fu==∂∂与11u v f v ==∂∂依次是()(A )12,0 (B)0,12(C )-12,0 (D)0 ,-126、设D 是第一象限中曲线21,41xy xy ==与直线,y x y ==围成的平面区域,函数(,)f x y 在D 上连续,则(,)Df x y dxdy ⎰⎰=()(A )12sin 2142sin 2(cos ,sin )d f r r drπθπθθθθ⎰⎰(B)24(cos ,sin )d f r r drππθθθ⎰ (C )13sin 2142sin 2(cos ,sin )d f r r drπθπθθθθ⎰⎰(D)34(cos ,sin )d f r r drππθθθ⎰97、设矩阵A=211112a 14a ⎛⎫ ⎪ ⎪⎪⎝⎭,b=21d d ⎛⎫⎪ ⎪ ⎪⎝⎭,若集合Ω=}{1,2,则线性方程组Ax b =有无穷多个解的充分必要条件为() (A ),a d ∉Ω∉Ω (B),a d ∉Ω∈Ω (C),a d ∈Ω∉Ω (D) ,a d ∈Ω∈Ω8、设二次型123(,,)f x x x 在正交变换x Py =下的标准形为2221232,y y y +-其中123P=(e ,e ,e ),若132(,,)Q e e e =-,则123(,,)f x x x 在正交变换x Py =下的标准形为( ) (A)2221232y y y -+ (B) 2221232y y y +- (C)2221232y y y --(D) 2221232yy y ++二、填空题:9~14小题,每小题4分,共24分.请将答案写在答题纸指定位置上. 9、设2231arctan ,3t x t d ydx y t t ==⎧=⎨=+⎩则10、函数2()2xf x x =在0x =处的n 阶导数()(0)n f =11、设函数()f x 连续,2()(),x x xf t dt ϕ=⎰若(1)ϕ1=,'(1)5ϕ=,则(1)f =12、设函数()y y x =是微分方程'''20y y y +-=的解,且在0x =处()y x 取值3,则()y x = 13、若函数(,)z z x y =由方程231x y zexyz +++=确定,则(0,0)dz =1014、设3阶矩阵A 的特征值为2,-2,1,2B A A E=-+,其中E 为3阶单位矩阵,则行列式B =三、解答题:15~23小题,共94分.请将解答写在答题纸指定位置上.解答应写出文字说明、证明过程或演算步骤. 15、(本题满分10分)设函数()ln(1)sin f x x x bx x α=+++,2()g x kx =,若()f x 与()g x 在0x →是等价无穷小,求,,a b k 的值。
湘潭大学833 数据结构真题一、选择题(共15 小题,每小题2 分,共30 分)1.某算法的时间复杂度为O(n^2),表明该算法的()。
[单选题] *A. 问题规模是n^2B.执行时间等于n^2C.执行时间与n^2 成正比(正确答案)D. 问题规模与n^2 成正比2.在一个单链表中,删除p 结点(非尾结点)之后的一个结点的操作是()。
[单选题] *A.p->next=pB.p->next->next=p->nextC.p->next->next=pD.p->next=p->next->next(正确答案)3.设计算法要求算法能够提供异常处理,对不合理的数据进行检查,这属于算法设计的()目标。
[单选题] *A.正确性B.可读性C.可使用性D.茁壮性(正确答案)4.在下列排序方法中,关键字比较的次数与记录的初始罗列次序无关的是()。
[单选题] *A.希尔排序B. 冒泡排序C.直接插入排序D.简单选择排序(正确答案)5.在一棵3 叉树中度为3 的结点数为两个,度为2 的结点数为一个,度为1 的结点数为两个,则度为0 的结点数为()个。
[单选题] *A.4B.5C.6(正确答案)D.76.若无向图G(V,E)中含有17 个顶点,则保证图G 在任何情况下,都是连通的需要的边数至少是()。
[单选题] *A .6B.15C.16(正确答案)D.217.在以下排序方法中,()是稳定的排序方法。
[单选题] *A.简单选择排序B.折半插入排序(正确答案)C.希尔排序D.快速排序8.一棵彻底二叉树有1001 个结点,其叶子结点的个数是()。
[单选题] *A.250B.501(正确答案)C.254D.5059.经过以下栈运算后StackEmpty(s)的值为()。
InitStack(s);Push(s,a);Push(s,b);Pop(s,x);Pop(s,y) [单选题] *A.aB.bC.1(正确答案)D.010.已知一棵3 阶B-树中有2047 个关键字,则树的最大高度是()。