山东师范大学2012年《806软件设计》考研专业课真题试卷

2012年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解一、单项选择题：l～40小题。

每小题2分，共80分。

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

1．求整数n（n≥0）阶乘的算法如下，其时间复杂度是（）。

A．O（log2n）B．0（n）C．O（nlog2n）D．O（n2）【答案】B。

【解析】设fact（n）的运行时间函数是T（n）。

该函数中语句①的运行时间是0（1），语句②的运行时间是T（n-1）+O（1），其中O （1）为乘法运算的时间。

因此，当n≤1时，T（n）-0（1）；当n>1时，T（n）＝T（n-1）+O（1）。

则，T（n）＝O（1）+T（n-1）＝2×O（1）+T（n-2）＝（n-1）×O（1）+T（1）＝n×O（1）＝O（n）即fact（n）的时间复杂度为O（n）。

2．已知操作符包括‘+’、‘-’、‘*’、‘／’、‘（’和‘）’。

将中缀表达式a+b-a*（（c+d）／e-f）+g转换为等价的后缀表达式ab+acd+e／f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符。

若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是（）。

A．5B．7C．8D．11【答案】A。

【解析】基本思想是：采用运算符栈是为了比较运算符的优先级，所有运算符必须进栈。

只将大于栈顶元素优先级的运算符直接进栈，否则需要退栈栈顶运算符（先出栈的运算符先计算，同优先级的运算符在栈中的先计算）。

表达式a+b-a*（（c+d）／e-f）+g产生后缀表达式的过程如下表所列：“*”的优先级大于栈顶元素“-”，则“*”*ab+acd+e／通过上表可以看出，显然转换过程中同时保存在栈中的操作符的最大个数是5。

3．若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，则根结点的孩子结点（）。

A．只有eB．有e、bC．有e、cD．无法确定【答案】A。

山东师范大学2012年山东省各专业录取情况学院招生专业（类）科类山东计划录取批次线最高分最低分平均分政治与国际关系（马克思主义）学院哲学文史50 573 585 574 576政治与国际关系（马克思主义）学院政治学类（政治学与行政学、思想政治教育（师范）、国际政治（新上专业））文史237 573 601 574 580.8政治与国际关系（马克思主义）学院政治学类（政治学与行政学、思想政治教育（师范）、国际政治（新上专业））理工10 582 608 583 590.6经济学院国际经济与贸易文史60 573 601 578 585.5 经济学院国际经济与贸易理工60 582 614 585 593.8 经济学院金融学文史70 573 617 590 595.4 经济学院金融学理工60 582 627 604 609.1 经济学院经济学文史25 573 602 587 592.5 经济学院经济学理工25 582 607 589 597.2 法学院法学类（法学、法学（知识产权方向））文史165 573 606 576 583.6 法学院法学类（法学、法学（知识产权方向））理工80 582 625 582 592.1 教育学院教育学文史72 573 615 585 593.8 教育学院学前教育文史150 573 602 576 582.1 体育学院体育学类（体育教育（师范）、社会体育）体育270 399 563 402 479.1 体育学院民族传统体育体育50 222 443 222 309.86 体育学院舞蹈学（体育舞蹈方向-体育舞蹈）艺术文15 300 462 353 400.93 体育学院舞蹈学（体育舞蹈方向-体育舞蹈）艺术理15 300 455 345 392.26 体育学院舞蹈学（体育舞蹈方向-健美操）艺术文15 300 445 328 388.33 体育学院舞蹈学（体育舞蹈方向-健美操）艺术理15 300 481 340 392.06 体育学院体育教育（中俄合作）专科体育30 180 390 300 350.75文学院中国语言文学类（汉语言文学（师范）、汉语言）文史247 573 617 586 593.4文学院新闻传播学类（新闻学、广播电视新闻学）文史70 573 609 579 586.5 国际交流学院对外汉语文史40 573 608 577 587 国际交流学院对外汉语理工20 582 626 604 612.8外国语学院英语文史110 573 620 593 600.5 外国语学院英语理工70 582 638 611 618.2 外国语学院俄语文史30 573 594 576 582.1 外国语学院法语文史30 573 619 582 590外国语学院西班牙语文史30 573 616 587 593.9 外国语学院阿拉伯语文史20 573 593 575 586.1 外国语学院日语文史30 573 603 576 583.6 外国语学院朝鲜语文史30 573 592 576 582.2 音乐学院音乐学艺术文120 300 567 351 425.33 音乐学院作曲与作曲技术理论艺术文10 300 431 316 359.88 音乐学院音乐表演（声乐方向）艺术文21 300 426 302 360.21 音乐学院音乐表演（键盘方向）艺术文8 300 488 326 404.5 音乐学院音乐表演（民乐方向）艺术文8 300 425 327 389.85 音乐学院音乐表演（西洋乐方向）艺术文8 300 472 302 407.87 音乐学院音乐学（音乐艺术管理方向) 艺术文30 300 536 369 437.38 音乐学院舞蹈学（男）艺术文15 300 466 326 384.2 音乐学院舞蹈学（女）艺术文30 300 495 310 388.4 美术学院美术学艺术文165 300 538 306 395.09 美术学院艺术设计艺术文70 300 503 302 375.94 美术学院摄影艺术文15 300 525 400 460.26 美术学院摄影艺术理10 300 525 401 436.5 传媒学院教育技术学理工42 582 624 582 593.9 传媒学院戏剧影视文学艺术文70 300 572 484 512.22 传媒学院戏剧影视文学艺术理30 300 572 467 508.33 传媒学院播音与主持艺术艺术文35 300 519 367 438.17 传媒学院播音与主持艺术艺术理15 300 554 416 458.06 传媒学院广播电视编导艺术文50 300 570 506 528.8传媒学院广播电视编导艺术理30 300 567 489 519.13 传媒学院数字媒体艺术理工50 582 623 582 592.6 传媒学院数字媒体艺术（动画艺术方向）艺术文30 300 512 403 436.76 传媒学院数字媒体艺术（动画艺术方向）艺术理20 300 504 402 440.85历史与社会发展学院历史学类（历史学（师范）、世界历史、社会工作）文史262 573 606 574 580.8数学科学学院数学类（数学与应用数学（师范）、信息与计算科学）理工370 582 628 585 599.2物理与电子科学学院物理学类（物理学（师范）、应用物理学、光电信息工程）理工210 582 645 582 594.5物理与电子科学学院电气信息类（电子信息科学与技术、电子信息工程、电子科学与技术）理工170 582 617 582 590.9化学化工与材料科学学院化学类（化学（师范）、应用化学（师范））理工235 582 640 588 598.5 化学化工与材料科学学院化工与制药类（化学工程与工艺、制药工程）理工150 582 619 582 591.2生命科学学院生物科学类（生物科学（师范）、生物技术、食品科学与工程（师范）、食品质量与安全）理工382 582 629 582 594.4人口·资源与环境学院地理科学类（地理科学（师范）、资源环境与城乡规划管理、地理信息系统）文史130 573 608 576 582.4人口·资源与环境学院地理科学类（地理科学（师范）、资源环境与城乡规划管理、地理信息系统）理工107 582 642 582 598.1人口·资源与环境学院环境科学理工70 582 638 582 597.5 心理学院心理学类（心理学（师范）、应用心理学）理工160 582 644 582 593.7 信息科学与工程学院通信工程理工150 582 623 582 591.1信息科学与工程学院计算机科学与技术（计算机科学与技术（师范）、信息技术方向、软件方向、软件服务外包方向）理工187 582 616 582 591.2信息科学与工程学院计算机科学与技术（软件服务外包方向）（与浪潮合作2+2办学，本科二批）理工50 481 609 495 560.4管理科学与工程学院信息管理与信息系统理工140 582 634 582 596.4 管理科学与工程学院人力资源管理文史50 573 596 580 584.7 管理科学与工程学院人力资源管理理工50 582 607 582 591.7 管理科学与工程学院电子商务理工100 582 603 582 589.7 商学院工商管理文史40 573 609 578 587.1 商学院工商管理理工30 582 613 591 597.4商学院工商管理高水平运动员70 313 521 325 394.85商学院财务管理文史35 573 616 588 596.6 商学院财务管理理工35 582 625 601 606.7 商学院旅游管理文史30 573 595 576 582.1 商学院旅游管理理工40 582 606 582 590.9 商学院物流管理（中韩合作本科）文史50 484 565 496 530.2 商学院物流管理（中韩合作本科）理工50 481 591 498 545.7 商学院国际经济与贸易（中韩合作）文史35 180 497 340 412.3 商学院国际经济与贸易（中韩合作）理工35 180 500 258 400.7 商学院财务管理（中美合作）文史15 180 487 341 394.7 商学院财务管理（中美合作）理工15 180 486 330 407.2公共管理学院公共管理类（行政管理、公共事业管理、劳动与社会保障）文史250 573 595 574 581.7。

第1章绪论一、选择题1. 算法的时间复杂度取决于（ C ）A．问题的规模 B. 待处理数据的初态 C. A和B2.计算机算法指的是（C），它必须具备（B）这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性3．从逻辑上可以把数据结构分为（ C ）两大类。

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

A．循环队列 B. 链表 C. 哈希表 D. 栈5．在下面的程序段中，对x的赋值语句的频度为（ C ）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)6．连续存储设计时，存储单元的地址（ A ）。

A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续二、判断题1. 数据元素是数据的最小单位。

( F ) 【山东师范大学 2001 一、1 （2分）】2. 记录是数据处理的最小单位。

( F )3．数据的物理结构是指数据在计算机内的实际存储形式。

( T )【山东师范大学2001 一、2（2分）】4. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。

( F )5. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

( F )三、填空1．数据的物理结构包括的表示和的表示。

2. 对于给定的n个元素,可以构造出的逻辑结构有（1），（2），（3），_（4）四种。

3．数据的逻辑结构是指。

4．一个数据结构在计算机中称为存储结构。

5．数据结构中评价算法的两个重要指标是6．已知如下程序段FOR i:= n DOWNTO 1 DO {语句1}BEGINx:=x+1；{语句2}FOR j:=n DOWNTO i DO {语句3}y:=y+1; {语句4}END；语句1执行的频度为（1）；语句2执行的频度为（2）；语句3执行的频度为（3）；语句4执行的频度为（4）。