2016 年数据结构联考复习指导 1.1 数据结构的基本概念基本概念和术语 1. 数据 2. 数据元素数据项注意 : 不要混淆数据数据元素数据项之间的概念, 也要注意和数据

Size: px

Start display at page:

Download "2016 年数据结构联考复习指导 1.1 数据结构的基本概念 1.1.1 基本概念和术语 1. 数据 2. 数据元素数据项注意 : 不要混淆数据数据元素数据项之间的概念, 也要注意和数据 "

某双弓
7 years ago
Views:

1 CHAPTER 1 绪论第 1 章复习要点考题分析年份单选题 / 分综合题 / 分考查内容知识框架复习提示本章内容并不在考研大纲中, 它是数据结构的一个概述但读者千万不要忽视本章, 更应该通过对本章的学习初步了解数据结构的基本内容和基本方法分析算法的时间复杂度和空间复杂度是本章的重点, 属必考内容, 一定要熟练掌握, 每年都会结合算法设计题而出现最近 4 年还直接以选择题的形式考查了时间复杂度的计算掌握本章的基本概念, 对后续章节的学习以及整个数据结构课程的理解是非常重要的

基本内容和基本方法分析算法的时间复杂度和空间复杂度是本章的重点, 属必考内容, 一定要熟练掌握, 每年都会结合算法设计题而出现最

2 2016 年数据结构联考复习指导 1.1 数据结构的基本概念基本概念和术语 1. 数据 2. 数据元素数据项注意 : 不要混淆数据数据元素数据项之间的概念, 也要注意和数据库中的相关术语进行区别 : 如数据记录数据字段等概念 3. 数据对象 N={0, 1, 2, } 4. 数据类型抽象数据类型 ADT 6. 数据结构结构 Structure 数据结构 : 逻辑结构存储结构数据的运算数据结构的三要素 1. 数据的逻辑结构 002

别 : 如数据记录数据字段等概念 3. 数据对象 N={0, 1, 2, } 4. 数据类型 1 2 3 5. 抽象数据类型 ADT 6.

3 绪论第第 6 章 1 章数据的存储结构物理结构 Hash 3. 数据的运算本节试题精选一单项选择题 1. 可以用 ( ) 定义一个完整的数据结构 003

4 2016 年数据结构联考复习指导 A. 数据元素 B. 数据对象 C. 数据关系 D. 抽象数据类型 2. 以下数据结构中,( ) 是非线性数据结构 A. 树 B. 字符串 C. 队列 D. 栈 3. 以下属于逻辑结构的是 ( ) A. 顺序表 B. 哈希表 C. 有序表 D. 单链表 4. 以下与数据的存储结构无关的术语是 ( ) A. 循环队列 B. 链表 C. 哈希表 D. 栈 5. 以下关于数据结构的说法中, 正确的是 ( ) A. 数据的逻辑结构独立于其存储结构 B. 数据的存储结构独立于其逻辑结构 C. 数据的逻辑结构唯一决定了其存储结构 D. 数据结构仅由其逻辑结构和存储结构决定 6. 在存储数据时, 通常不仅要存储各数据元素的值, 而且还要存储 ( ) A. 数据的操作方法 B. 数据元素的类型 C. 数据元素之间的关系 D. 数据的存取方法 7. 链式存储设计时, 结点内的存储单元地址 ( ) A. 一定连续 B. 一定不连续 C. 不一定连续 D. 部分连续, 部分不连续二综合应用题 1. 对于两种不同的数据结构, 逻辑结构或物理结构一定不相同吗? 2. 试举一例, 说明对相同的逻辑结构, 同一种运算在不同的存储方式下实现, 其运算效率不同答案与解析一单项选择题 1 D ADT 2 A 3 C 4 D A 004

数据的逻辑结构唯一决定了其存储结构 D. 数据结构仅由其逻辑结构和存储结构决定 6. 在存储数据时, 通常不仅要存储各数据元素的值, 而且还要存储 ( ) A. 数据的操作方法 B. 数据元素的类型 C. 数据元素之间的关系 D.

5 绪论第第 6 章 1 章 6 C 7 A 二综合应用题 1 数据的运算二叉树二叉排序树 O(n) O(log 2 n) 2 线性表 O(n) O(1) 1.2 算法和算法评价算法的基本概念算法 Algorithm 5 1 有穷性 2 确定性 3 可行性 4 输入 5 输出

6 2016 年数据结构联考复习指导算法效率的度量 1. 时间复杂度 T(n) n T(n) 最深层循环内 T(n) f(n) T(n)=O(f(n)) O T(n) T(n) f(n) C n 0 n n 0 0 T(n) C f(n) n 例如 A[0 n 1] K (1)i=n 1; (2)while(i>=0&&(A[i]!=k)) (3) i ; (4)return i; 3 n A K A K 3 f(n)=n A K 3 f(n) 0 最坏时间复杂度平均时间复杂度最好时间复杂度 a T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n))) b T(n)=T1(n) T2(n)=O(f(n)) O(g(n))=O(f(n) g(n)) Ο(1) Ο(log 2 n) Ο(n) Ο(nlog 2 n) Ο(n 2 ) Ο(n 3 ) Ο(2 n ) O(n!) O(n n ) 2. 空间复杂度 S(n) n S(n)=O(g(n)) f(n) n 1 f(n)=a* n 3 +b* n 2 +c*n O(n 3 ) 006

7 绪论第第 6 章 1 章原地工作 O(1) 本节试题精选一单项选择题 1. 一个算法应该是 ( ) A. 程序 B. 问题求解步骤的描述 C. 要满足五个基本特性 D.A 和 C 2. 某算法的时间复杂度为 O(n 2 ), 表明该算法的 ( ) A. 问题规模是 n 2 B. 执行时间等于 n 2 C. 执行时间与 n 2 成正比 D. 问题规模与 n 2 成正比 3. 以下算法的时间复杂度为 ( ) void fun(int n){ int i=1; while(i<=n) i=i*2; } A.O(n) B.O(n 2 ) C.O(nlog 2 n) D.O(log 2 n) 年计算机联考真题设 n 是描述问题规模的非负整数, 下面程序片段的时间复杂度是 ( ) x=2 while(x<n/2) x=2*x A.O(log 2 n) B.O(n) C.O(nlog 2 n) D.O(n 2 ) 年计算机联考真题求整数 n(n 0) 阶乘的算法如下, 其时间复杂度是 ( ) int fact(int n){ if(n<=1) return 1; return n*fact(n 1); } A.O(log 2 n) B.O(n) C.O(nlog 2 n) D.O(n 2 ) 年计算机联考真题已知两个长度分别为 m 和 n 的升序链表, 若将它们合并为一个长度为 m+n 的降序链表, 则最坏情况下的时间复杂度是 ( ) A.O(n) B.O(m n) C.O(min(m, n)) D.O(max(m, n)) 007

O(log 2 n) 4. 2011 年计算机联考真题设 n 是描述问题规模的非负整数, 下面程序片段的时间复杂度是 ( ) x=2 while(x<n/2) x=2*x A.O(log 2 n) B.O(n) C.O(nlog 2 n) D.O(n 2 ) 5.

8 2016 年数据结构联考复习指导 count=0; for(k=1;k<=n;k*=2) for(j=1;j<=n;j++) count++; A O(log 2 n) B O(n) C O(nlog 2 n) D O(n 2 ) 8. 有以下算法, 其时间复杂度为 ( ) void fun(int n){ int i=0; while(i*i*i<=n) i++; } A.O(n) B.O(nlogn) C.O( 3 n ) D.O( n ) 9. 程序段 for(i=n 1;i>1;i ) for(j=1;j<i;j++) if(a[j]>a[j+1]) A[j] A[j+1] ; 其中 n 为正整数, 则最后一行的语句频度在最坏情况下是 ( ) A.O(n) B.O(nlogn) C.O(n 3 ) D.O(n 2 ) 10. 以下算法中加下划线语句的执行次数为 ( ) int m=0,i,j; for(i=1;i<=n;i++) for(j=1;j<=2*i;j++) m++; A.n(n+1) B.n C.n+1 D.n 下面说法错误的是 ( ). 算法原地工作的含义是指不需要任何额外的辅助空间. 在相同的规模 n 下, 复杂度 O(n) 的算法在时间上总是优于复杂度 O(2 n ) 的算法. 所谓时间复杂度是指最坏情况下, 估算算法执行时间的一个上界. 同一个算法, 实现语言的级别越高, 执行效率就越低 A. B., C., D. 二综合应用题 1. 一个算法所需时间由下述递归方程表示, 试求出该算法的时间复杂度的级别 ( 或阶 ) 1 n 1 T(n) 2T(n/2) n n 1 式中,n 是问题的规模, 为简单起见, 设 n 是 2 的整数幂 2. 分析以下各程序段, 求出算法的时间复杂度 i=1;k=0; y=0; while(i<n-1){ k=k+10*i; while((y+1)*(y+1)<=n) y=y+1;

程序段 for(i=n 1;i>1;i ) for(j=1;j<i;j++) if(a[j]>a[j+1]) A[j] A[j+1] ; 其中 n 为正整数, 则最后一行的语句频度在最坏情况下是 ( ) A.O(n) B.O(nlogn) C.O(n 3 ) D.O(n 2 ) 10.

9 绪论第第 6 章 1 章 i++; } for(i=1;i<=n;i++) for(i=0;i<n;i++) 答案与解析 for(j=1;j<=i;j++) for(k=1;k<=j;k++) x++; for(j=0;j<m;j++) a[i][j]=0; 一单项选择题 1 B 2 C O(n 2 ) T(n) c n 2 c T(n)=O(n 2 ) T(n) n n n 2 3 D i=i*2 T(n) 2 T(n) n T(n) log 2 n=o(log 2 n) 4 A x=2*x t 2 t+1 =n/2 t=log 2 (n/2)-1=log 2 n-2 T(n)=O(log 2 n) 5 B n! n*(n-1)* *1 n T(n)=O(n) 6 D O(max(m, n)) 7 C j<=n j 1 n k<=n k*=2 2 k <=n k<=log 2 n O(n) O(log 2 n) T(n)=T 1 (n)*t 2 (n)=o(n)*o(log 2 n)=o(nlog 2 n) C 8 C i++ T(n) T(n) T(n) T(n) n T(n) 3 n T(n) 3 n =O( 3 n ) 更加直观和快速的解题方法 i++ i 1 i 3 =n i= 3 n T(n)= O( 3 n ) 9 D n 1 i 1 n 1 2 T(n) 1 i (n 2)(n 1) / 2 O(n ) i 2 j 1 i 2 最坏情况下 O(n 2 ) 10 A m++ n 2i n n 1 2i 2 i n(n 1) i 1 j 1 i 1 i 1 11 A n O(n) O(2 n ) 009

n=o(log 2 n) 4 A x=2*x t 2 t+1 =n/2 t=log 2 (n/2)-1=log 2 n-2 T(n)=O(log 2 n) 5 B n!

10 2016 年数据结构联考复习指导二综合应用题 1 O(nlog 2 n) n=2 k (k 0) T(2 k )=2T(2 k 1 )+2 k =2 2 T(2 k 2 )+2 2 k T(2 k )=2 i T(2 k i )+i 2 k T(2 k )=2 k T(2 0 )+k 2 k =(k+1)2 k T(n)=2 log2 n + log 2 n*n=n(log 2 n+1) O(nlog 2 n) 2 k=k+10*i n-2 T(n)=O(n) T(n) y 1 T(n)=y (T(n)) 2 n T(n)=O(n 1/2 ) n i j 1 x++ T(n)=O l =O n 3 i 1 j 1 k 1 6 =O(n3 ) a[i][j]=0 m n m*n T(m, n)=o(m*n) 归纳总结一是循环主体中的变量参与循环条件的判断 T(n) 1. int i=1; while(i<=n) i=i*2;. 1 i 2 T(n) 2 T(n) n T(n) log 2 n 2 y 1 T(n) T(n)=y-5 y=t(n)+5 (T(n)+5+1) *(T(n)+ 5+1)<n T(n)< n 6 T(n)=O( n ) 二是循环主体中的变量与循环条件无关 5 T(n)=1+T(n 1)=1+1+T(n 2)= =n 1+T(1) T(n)=O(n) 2. int y=5; while((y+1)*(y+1)<n) y=y+1;. 010

a[i][j]=0 m n m*n T(m, n)=o(m*n) 归纳总结一是循环主体中的变量参与循环条件的判断 T(n) 1. int i=1; while(i<=n) i=i*2;.

11 绪论第第 6 章 1 章 8 9 思维拓展 1, n 0,1 F(n) F(n 1) F(n 2), n 1 ( 提示 : 请结合归纳总结中的两种方法进行解答 ) 011

《C语言基础入门》课程教学大纲

《C语言基础入门》课程教学大纲 C 语言开发入门教程课程教学大纲课程编号 :201409210011 学分 :5 学分学时 :58 学时 ( 其中 : 讲课学时 :39 学时上机学时 :19 学时 ) 先修课程 : 计算机导论后续课程 :C++ 程序设计适用专业 : 信息及其计算机相关专业开课部门 : 计

2016 年 数 据 结 构 联 考 复 习 指 导 1.1 数 据 结 构 的 基 本 概 念 基 本 概 念 和 术 语 1. 数 据 2. 数 据 元 素 数 据 项 注 意 : 不 要 混 淆 数 据 数 据 元 素 数 据 项 之 间 的 概 念, 也 要 注 意 和 数 据

2016 年数据结构联考复习指导 1.1 数据结构的基本概念基本概念和术语 1. 数据 2. 数据元素数据项注意 : 不要混淆数据数据元素数据项之间的概念, 也要注意和数据