上海科技大学数据结构与算法2018,2019年考研真题

>>1251 2019年全国硕士研究生招生考试计算机科学与技术学科联考计算机学科专业基础综合试题 一、单项选择题：1～40小题，每小题2分，共80分。

下列每题给出的四个选项中，只有一个选项符合试题要求。

1.设n 是描述问题规模的非负整数，下列程序段的时间复杂度是x=0；while(n>=(x+1)*（x+1))x=x+1； A.O (log n ) B.O (n 1/2) C.O (n ) D.O (n 2)2.若将一棵树T 转化为对应的二叉树BT ，则下列对BT 的遍历中，其遍历序列与T 的后根遍历序列相同的是A.先序遍历B.中序遍历C.后序遍历D.按层遍历3.对n 个互不相同的符号进行哈大曼编码。

若生成的哈夫曼树共有115个结点．则n的值是A.56 B.57 C.58 D.604.在任意一棵非空平衡二叉树(AVL 树)T 1中，删除某结点v 之后形成平衡二叉树T 2，再将v 插入T 2形成平衡二叉树T 3。

下列关于T 1与T 3的叙述中，正确的星I.若v 是T 1的叶结点，则T 1与T 3可能不相同 Ⅱ.若v 不是T 1的叶结点．则T 1与T 3一定不相同 Ⅲ.若v 不是T 1的叶结点，则T 1与与T 3一定相同 A.仅I B.仅Ⅱ C.仅I 、Ⅱ D.仅I 、Ⅲ5.下图所示的AOE 网表示一项包含8个活动的工程。

活动d 的最早开始时问和最迟开始时间分别是126<<A.3和7B.12和I2C.12和14D.15和156.用有向无环图描述表达式(x+y)*((x+y)／x)，需要的顶点个数至少是A.5B.6C.8D.97.选择一个排序算法时,除算法的时空效率外，下列因素中，还需要考虑的是I.数据的规模Ⅱ.数据的存储方式Ⅲ.算法的稳定性Ⅳ.数据的初始状态A.仅ⅢB.仅I、ⅡC.仅Ⅱ、ⅢIVD.I、Ⅱ、Ⅲ.IV8.现有长度为11且初始为空的散列表HT，散列函数是H(key)=key％7，采用线性探查(线性探测再散列)法解央冲突。

上海科技大学2018年攻读硕士学位研究生招生考试试题科目代码：991 科目名称：数据结构与算法考生须知：1. 本试卷满分为150分，全部考试时间总计180分钟。

2. 所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。

3. 每道题的中文部分均已翻译为英文，考生可在中英文中任选一种语言作答。

1.True or False (5 problems, 2 points each) 判断题（5题，每题2分）Please indicate in the answer sheet whether each statement is true or false. Write down “T” for being true and “F” for being false.请在答题纸上写明下列每个命题的真假。

真则写“T”，假则写“F”。

1.Let f(n) = n3 - 4n + 4 and g(n) = 5n3– 100, then f(n) + g(n) is Ω(n3) and f(n)*g(n) is o(n6).若函数f(n) = n3 - 4n + 4 以及g(n) = 5n3– 100, 则f(n) + g(n) 是Ω(n3) 并且f(n)*g(n) 是o(n6).ing a simple uniform hashing function h to hash n distinct keys into an array of length m,the expected cardinality of {{k, l}: k≠l and h(k) = h(l)} is n/m.用简单均匀的哈希函数将n个不同的keys映射到一个长度为m的数组，集合{{k, l}: k≠l and h(k) = h(l)}的期望大小是n/m.3. A directed acyclic graph with n nodes has at most n(n-1)/2 edges.一个有n个节点的有向无环图最多有n(n-1)/2条边。

一、选择题1. 算法的计算量的大小称为计算的（ B ）。

【北京邮电大学2000 二、3 （20/8 分）】A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（ C ）【中科院计算所1998 二、1 （2 分）】A．问题的规模 B. 待处理数据的初态 C. A 和B3. 计算机算法指的是（C），它必须具备（B）这三个特性。

(1) A ．计算方法 B. 排序方法 C. 解决问题的步骤序列D. 调度方法(2) 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) 的算法在时间上总是优于复杂度nO(2 )的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低 4A ．(1) B.(1),(2) C. (1),(4) D.(3)7．从逻辑上可以把数据结构分为（ C ）两大类。

【武汉交通科技大学1996 一、4（2 分）】A．动态结构、静态结构 B ．顺序结构、链式结构C．线性结构、非线性结构 D ．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（ D ）【。

上海科技大学2019年攻读硕士学位研究生招生考试试题科目代码：991 科目名称：数据结构与算法考生须知：1. 本试卷满分为150分，全部考试时间总计180分钟。

2. 所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。

3. 每道题的英文部分均已翻译为中文，考生可在中英文中任选一种语言作答。

1.True or False (10 problems, 2 points each) 判断题（10题，每题2分）Please indicate in the answer sheet whether each statement is true or false. Write down “T” for being true and “F” for being false.请在答题纸上写明下列每个命题的真假。

真则打“√”，假则打“⨯”。

1.In a circular linked list, some link fields may be null. （）在循环链表中，某些链接域可能为空。

（）2.Given any functions f(n) and g(n), it is possible to have both f(n) = Ω(g(n)) and f(n) = o(g(n)).（）给定任意函数f(n)和g(n)，f(n) = Ω(g(n))和f(n) = o(g(n))可能同时成立。

（）3. A good hash function of a hash table satisfies the assumption of simple uniform hashing. （）一个好的哈希函数需满足简单均匀。

（）5.The number of nodes in a tree can be more than twice the number of leaf nodes. （）一棵树的节点个数有可能大于叶节点个数的两倍。

上海科技大学2021年攻读硕士学位研究生招生考试试题科目代码：991 科目名称：数据结构与算法考生须知：1. 本试卷满分为150分，全部考试时间总计180分钟。

2. 所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。

3. 考生可用中文或者英文作答。

1. 判断题（10题，每题1分，共10分）请在答题纸上写明题号后，对正确的命题则打“√”，错误的命题则打“⨯”。

1)数组（Array）是一种线性结构，因此只能用来存储线性表。

（）2)设堆栈 S 和队列 Q 的初始状态为空，元素 a1,a2,a3,a4,a5,a6 依次通过堆栈 S，一个元素出栈后即进入队列 Q ，如果6个元素出队列 Q的顺序是 a2,a4,a3,a6,a5,a1 ,那么堆栈 S 的容量至少是 3。

（）3)长度为 n 的单向链表（Linked list），如果查找每个元素的概率相同，则查找表中任意元素的平均查找长度为Θ(n)。

（）4)冒泡排序（Bubble sort）算法中的比较次数与初始元素序列的排列无关。

（）5)在排序算法中，快速排序（Quick sort）的执行时间一定最短。

（）6)一个复杂度为T(n)=4n3+n2log2(n)的算法执行时间一定比一个复杂度为 T(n)=n3+6log2(n)的算法执行时间长。

（）7)一棵完全二叉树（Complete binary tree）的节点数量为n，则该树中节点的平均深度为Θ(log2(n))。

（）8)如果要存储一个稀疏图，邻接矩阵法的空间复杂度小于邻接表法。

（）9)寻找最短路径的迪杰斯特拉（Dijkstra）算法不属于贪心法。

（）10)所有的NP问题都可以约化到NPC问题。

（）2. 单选题（15题，每题2分，共30分）每题只有一个正确选项。

请在答题纸上写下正确选项的序号。

1)下列数据结构中，哪一个不是线性结构？（）。

A. 链表B. 完全二叉树C.堆栈D. 循环队列（Circular queue）2)设计一个可以用于判别表达式中左、右括号是否配对出现的算法，采用（）数据结构最有效。

上海科技大学2018年攻读硕士学位研究生招生考试试题科目代码： 641 科目名称：生物化学与分子生物学考生须知：1. 本试卷满分为150分，全部考试时间总计180分钟。

2. 所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。

3. 每道题目的中文部分均已翻译为英文，考生可在中英文中任选一种语言作答。

一、名词解释（每小题5分，共20分）1.流动镶嵌模型（Fluid m osaic m odel）2.糖酵解（Glycolysis）3.基因组编辑（Genome e diting）4.增强子（Enhancer）二、单选题（每小题1分，共20分）1.规则的二级结构解折叠将导致（The u nfolding o f r egular s econdary s tructure c auses）：（ ）A.蛋白质熵的轻微增加（Little i ncrease i n t he e ntropy o f p rotein）B.蛋白质熵的大量降低（Large d ecrease i n t he e ntropy o f t he p rotein）C.蛋白质的熵不变（No c hange i n t he e ntropy o f t he p rotein）D.蛋白质熵的大量增加（Large i ncrease i n t he e ntropy o f t he p rotein）2.甘氨酸的分子式是C2H5O2N。

通过缩合反应形成的甘氨酸线性寡聚体的分子式应该是下面哪个（The m olecular f ormula f or g lycine i s C2H5O2N. W hat w ould b e t he m olecular f ormula f or a linear o ligomer m ade b y l inking t en g lycine m olecules t ogether b y c ondensation s ynthesis）：（ ）A.C20H50O20N10B.C20H32O11N10C.C20H40O10N10D.C20H68O29N103.肽链延伸时，tRNA在核糖体上的移动路线是（The p athway o f a t RNA d uring p olypeptideelongation o n t he r ibosome i s）：（ ）A.A 位点 → P位点→ E位点（A s ite → P s ite → E s ite）B.P 位点 → 进入位点→ 脱离位点（P s ite → e ntry s ite → e xit s ite）C.A位点→ P位点→ 进入位点（A s ite → P s ite → e ntry s ite）D.P位点→ A位点→ E位点（P s ite → A s ite → E s ite）4.肽聚糖是复合物，它包含（Peptidoglycan i s a c omplex t hat c ontains）：（ ）A.寡聚糖和蛋白（Oligo-­‐saccharide a nd p rotein）B.多聚糖和蛋白（Poly-­‐saccharide a nd p rotein）C.单糖和蛋白（Mono-­‐saccharide a nd p rotein）D.氨基酸和碳水化合物（Amino a cid a nd c arbohydrate）5.下面哪些属于丝氨酸蛋白酶（Which o f t he f ollowing (s) i s/are s erine p roteases）：（ ）A.胰凝乳蛋白酶（Chymotrypsin）B.胰蛋白酶（Trypsin）C.弹性蛋白酶（Elastase）D.上面所有的（All a bove o nes）6.以下选项中哪个不属于RNA的基本结构（Which o f t he f ollowing c omponent i s N OT b elongedto t he b asic s tructure o f R NA）：（ ）A.碱基（Base）B.脱氧核糖（Deoxyribose）C.磷酸二酯键（Phosphodiester b ond）D.糖苷键（Glycosidic b ond）7.以下哪种代谢物能引起痛风（Which o f t he f ollowing m etabolite c an c ause g out）：（ ）A.尿酸（Uric a cid）B.尿素（Urea）C.黄嘌呤（Xanthine）D.次黄嘌呤（Hypoxanthine）8.以下哪种酶负责催化dCTP到dUTP的转化（Which o f t he f ollowing e nzyme c atalyzes t heconversion o f d CTP t o d UTP）：（ ）A.dCTP氧化酶（dCTP o xidase）B.dCTP还原酶（dCTP r eductase）C.dCTP甲基化酶（dCTP m ethyltransferase）D.dCTP脱氨酶（dCTP d eaminase）9.真核生物核小体是由几个组蛋白分子组成的（How m any m olecules o f h istone c ompose o neeukaryotic n ucleosome）（ ）A.5B.6C.7D.810.以下哪种组分不是PCR反应所需的（Which o f t he f ollowing c omponent i s N OT r equired i n aPCR r eaction）：（ ）A.模版（Template）B.引物（Primer）C.DNA聚合酶（DNA p olymerase）D.dNMP11.碳水化合物完全氧化后的最终产物是（The u ltimate p roduct o f c omplete o xidation o fcarbohydrates i s）：（ ）A.二氧化碳（Carbon d ioxide）B.乙酰辅酶A（Acetyl C oA）C.丙酮酸（Pyruvate）D.乙酸（Acetate）12.一个β–氧化循环产生多少个FADH2和NADH（How m any F ADH2 a nd N ADH a re p roduced b yone r ound o f t he β–oxidation p athway）：（ ）A.各1个（1 e ach）B.1 F ADH2 和2 N ADH （1 F ADH2 a nd 2 N ADH）C.各2个（2 e ach）D.2 F ADH2 和1 N ADH （2 F ADH2 a nd 1 N ADH）13.以下哪个属于酮体（Which o f t he f ollowing i s a k etone b ody）：（ ）A.草酰乙酸（Oxaloacetate）B.乙酰乙酸（Acetoacetate）C.脂肪酸（Fatty a cid）D.氨基酸（Amino a cid）14.以下哪个不是细胞内降解蛋白质的途径之一（Which o ne o f t he f ollowing i s N OT a w ay f orcellular d egradation o f p rotein）：（ ）A.溶酶体途径（lysosome）B.自噬途径（autophagy）C.泛素修饰途径（ubiquitin-­‐proteasome）D.胰蛋白酶水解途径（Trypsin）15.以下哪种关于类固醇激素的描述是正确的（Which s tatement c orrectly d escribes s teroidhormones）：（ ）A.它们在细胞中的作用是通过膜蛋白介导的（Their i ntracellular a ctions a re m ediated b yintegral m embrane p roteins）B.它们对细胞的作用需要水溶性细胞内的信号（Their e ffects o n c ells r equire a w ater-­‐soluble i ntracellular s ignal）C.它们的作用是通过结合水溶性受体蛋白来介导的（Their e ffects a re m ediated b y b indingto a w ater-­‐soluble r eceptor p rotein）D.它们是由氨基酸前体直接合成而来（They a re s ynthesized d irectly f rom a mino a cidprecursors）16.密码子简并性导致（The d egeneracy o f g enetic c ode r esults i n）：（ ）A.tRNA的种类多于密码子的种类（More t RNAs t han c odons）B.密码子的种类多于氨基酸的种类（More c odons t han a mino a cids）C.核酸的种类多于密码子的种类（More n ucleotides t han c odons）D.密码子和氨基酸的种类同样多（The s ame n umber o f c odons a nd a mino a cids）17.下列关于λ噬菌体阻遏物哪一项是错误的（Which o ne i s N OT c orrect a bout l ambdarepressor）：（ ）A.λ噬菌体阻遏物的DNA结合形式是二聚体（The D NA-­‐binding f orm o f t he L ambdarepressor i s a d imer）B.λ噬菌体阻遏物使用亮氨酸拉链基序来结合DNA（Lambda r epressor u ses a L eucineZipper m otif t o b ind D NA）C.λ噬菌体阻遏物的功能是维持溶原性（The f unction o f t he l ambda r epressor i s t o m aintainlysogeny）D.一个λ噬菌体阻遏物结合操纵基因后将增强下一个阻遏物结合相邻操纵基因的亲和力（Lambda r epressor b inding t o o ne o perator i ncreases t he a ffinity f or b inding a s econdrepressor d imer t o t he a djacent o perator）18.下列哪些蛋白结构域最有可能识别并结合核小体上的乙酰化赖氨酸（Which o f t he f ollowingprotein d omains w ould b e m ost l ikely t o r ecognize a nd b ind t o a cetylated l ysine r esidues o n nucleosomes）：（ ）A.同源异形域（Homeodomains）B.锌指结构域（Zinc f ingers）C.布罗膜结构域（Bromodomains）D.克罗莫结构域（Chromodomains）19. “摆动碱基配对”会发生在下列哪一对密码子中（‘Wobble b ase p airing’ w ill o ccur f or w hichone o f t he f ollowing p airs c odons）：（ ）A.AUG 和 U GG（AUG a nd U GG）B.AAA 和 U UU（AAA a nd U UU）C.GGA 和 G GC（GGA a nd G GC）D.UAG 和 U GA（UAG a nd U GA）20.你在实验过程中发现了一个新的DNA结合蛋白。

2019年上海科技大学考研专业课真题试卷上海科技大学2019年攻读硕士学位研究生招生考试试题科目代码：991 科目名称：数据结构与算法考生须知：1. 本试卷满分为150分，全部考试时间总计180分钟。

2. 所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。

3. 每道题的英文部分均已翻译为中文，考生可在中英文中任选一种语言作答。

1.True or False (10 problems, 2 points each) 判断题（10题，每题2分）Please indicate in the answer sheet whether each statement is true or false. Write down “T” for being true and “F” for being false.请在答题纸上写明下列每个命题的真假。

真则打“√”，假则打“⨯”。

1.In a circular linked list, some link fields may be null. （）在循环链表中，某些链接域可能为空。

（）2.Given any functions f(n) and g(n), it is possible to have both f(n) = Ω(g(n)) and f(n) = o(g(n)).（）给定任意函数f(n)和g(n)，f(n) = Ω(g(n))和f(n) = o(g(n))可能同时成立。

（）3. A good hash function of a hash table satisfies the assumption of simple uniform hashing. （）一个好的哈希函数需满足简单均匀。

（）。

第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) 的算法在时间上总是优于复杂度nO(2 ) 的算法（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:=1TOn DOFOR j:=1TOn DOx:=x+1;A． O(2n)B． O(n)C． O(n2)D． O(logn 2 )12．程序段FOR i:=n-1DOWNTO1DOFOR 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(n 3)D. O(n 2)【南京理工大学 1998 一、 1(2 分 ) 】13．以下哪个数据结构不是多型数据类型（）【中山大学1999一、 3（ 1 分）】A．栈B．广义表C．有向图D．字符串14．以下数据结构中，（）是非线性数据结构【中山大学1999一、 4】A．树B．字符串C．队D．栈15.下列数据中，（）是非线性数据结构。

一、选择题1. 算法的计算量的大小称为计算的（ B ）。

【北京邮电大学2000 二、3 （20/8分）】A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（C ）【中科院计算所 1998 二、1 （2分）】A．问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是（C），它必须具备（B）这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列D. 调度方法(2) 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）同一个算法，实现语言的级别越高，执行效率就越低4A．(1) B.(1),(2) C.(1),(4) D.(3)【武汉交通科技大学 1996 7．从逻辑上可以把数据结构分为（ C ）两大类。

一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（ D ）。

2022年上海理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

A.13B.33C.18D.402、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。

A.插入B.选择C.希尔D.二路归并3、若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（）。

A.单链表B.双向链表C.单循环链表D.顺序表4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。

A.（rear+1）MOD n=frontB.rear=frontC.rear+1=frontD.（rear-1）MOD n=front5、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。

A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)6、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（）。

A．只有e B．有e、b C．有e、c D．无法确定7、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（）。

8、每个结点的度或者为0或者为2的二叉树称为正则二叉树。

n个结点的正则二叉树中有（）个叶子。

A.log2nB.（n－1）/2C.log2n+1D.（n＋1）/29、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。

A.107B.108C.214D.21510、下列二叉排序树中查找效率最高的是（）。

A.平衡二叉树B.二叉查找树C.没有左子树的二叉排序树D.没有右子树的二叉排序树二、填空题11、分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是______算法，最费时间的是______算法。

第1页 共2页上海科技大学2019年攻读硕士学位研究生招生考试试题科目代码： 881 科目名称：信息与通信工程专业基础考生须知：1. 本试卷满分为150分，全部考试时间总计180分钟。

2. 所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。

1.（30分）判断下列叙述是否正确，正确的请填写“√”，错误的请填写“⨯”。

（每小题3分）（1） 离散信号 x [n ]=jπn √2 是一个周期信号；（ ） （2） 离散信号 x [n ]=sin(πn 5)πn是一个周期信号；（ ） （3） 离散系统 T (x [n ])=(cos πn )x[n] 是一个线性系统；（ ）（4） 离散系统 T (x [n ])=(cos πn )x[n] 是一个时不变系统；（ ）（5） 离散系统 T (x [n ])=x[n 2] 是一个线性系统；（ ）（6） 离散系统 T (x [n ])=x[n 2] 是一个时不变系统；（ ）（7） 一个线性时不变系统由该系统的脉冲响应唯一决定；（ ）（8） 两个序列：x [n ]=[1,2,3],y [n ]=[1,1,1]的线性卷积为 [1,3,6,5,3] ；（ ）（9） 两个序列：x [n ]=[1,2,3],y [n ]=[1,1,1]的循环(圆)卷积为 [6,6,6] ；（ ）（10）循环卷积和线性卷积结果总是不一样的。

（ ）2. （30分）计算下图信号的离散时间傅立叶变换 (Discrete-time Fourier Transform (DTFT) ).x [n ]={0 n <0cos (2πn)n ∈[0,60]0 n >602019年上海科技大学考研专业课真题试卷精都考研网（专业课精编资料、一对一辅导、视频网课）。