发布时间 : 星期三 文章数据结构更新完毕开始阅读
数据结构
1
1.为解决计算机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。（全国统考2009） A．栈 B．队列 C．树 D．图
2.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后入队Q，若出队序列为e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是（ ）。（全国统考2009）
A．1 B．2 C．3 D．4
3.若元素abcdef依次进栈，允许进栈、出栈交替进行，不允许连续三次进行出栈操作，则不可能得到的出栈序列是（ ）。（全国统考2010）
A．dcebfa B．cbdaef C．dbcaef D．afedcb 4.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是（ ）。（全国统考2010） A．bacde B．dbace C．dbcae D．ecbad
5.元素abcde依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是 （ ）。（全国统考2011）
A．3 B．4 C．5 D．6
6.已知循环队列存放在一维数组A[0..n-1]，且队列非空时front和rear分别指向队列的队头元素和队尾元素。若初始时队列为空，且要求第一个入队的元素存储在A[0]处，则初始时front和rear的值分别是（ ）。（全国统考2011） A．0，0 B．0，n-1 C．n-1，0 D．n-1，n-1
7.已知操作符包括‘+’，‘-’，‘*’，‘/’，‘(’和‘)’，将中缀表达式a+b-a*((c +d)/e-f)+g转化为等价的后缀表达式ab+acd+e/f-*-g+时，用栈来存放暂时还不能确定的运算次序的操作符，若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是（ ）。（全国统考2011） A．5 B．7 C．8 D．11
第一章 绪论
考纲分析
1.理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。
2.掌握基本的数据处理原理和方法的基础上，能够对算法进行基本的时间复杂度与空间复杂度进行设计与分析。
3.能够选择合适的数据结构和方法进行问题求解，具备采用C 或C++或 JAVA 语言设计与实现算法的能力。 典型题目解析 基本概念
本章题目主要考查数据结构的基本概念，要求深刻理解数据元素、数据的逻辑结构、数据的存储结构、抽象数据类型等有关概念，理解数据类型、数据结构和抽象数据类型间的关系。
1、顺序存储结构中数据元素之间的逻辑关系是由（ ）表示，链表存储结构中的数据元素之间的逻辑关系是由（ ）表示的。 A线性结构 B非线性结构 C存储位置 D指针
2、在存储数据时，通常不仅要存储各数据元素的值，还要存储（ ）
2
3、在链式存储结构中，要求（ ） A、每个结点占用一片连续的存储区域 B、所有结点占用一片连续的存储区域 C、结点的最后一个域是指针类型 D、每个结点有多少个后继就设多少个指针 4、以下术语属于逻辑结构的是( )
A、顺序表B、哈希表C、有序表D、单链表 4+、以下与数据的存储结构无关的术语是（ ） A、循环队列B、链表C、散列表D、栈 5、可以用（ ）、数据关系和基本操作定义一个完整的抽象数据类型 A、数据元素 B、数据对象 C、原子类型 D、存储结构 6、对于数据结构的描述，不正确的是（ ） A、相同的逻辑结构对应的存储结构也相同
B、数据结构由逻辑结构、存储结构和基本操作三方面组成 C、数据结构基本操作的实现与存储结构有关 D、数据的存储结构是数据的逻辑结构的机内实现
7、抽象数据类型的表示与计算机内部表示和实现无关（ ）
考查算法的基本概念、特性、算法与程序的关系，掌握算法时间性能的度量方法、基本语句执行次数的计算，时间复杂度的计算和分析。
8、当输入非法错误时，一个“好”的算法会进行适当处理，而不会产生难以理解的输出结果。这被称为算法的（ ）。
A、可读性B、健壮性C、正确性D、有穷性 9、算法的时间复杂度与（ ）有关
A、问题规模 B、待处理数据的初始状态 C、算法的特性 D、A和B 9+、算法的时间复杂度与（ ）有关
A、问题规模 B、计算机硬件性能 C、编译程序的质量 D、程序设计语言 典型题目解析 算法和算法分析 10、算法的时间复杂度是O（n2），表明该算法（ ） A、问题规模是n2 B、执行时间等于n2 C、执行时间与n2成正比 D、问题规模与n2成正比 11、下列说法错误的是（ ）
① 算法原地工作的含义是指不需要任何额外的辅助空间②在相同的规模n下，复杂度O（n）的算法在时间上总是优于复杂度O（ 2n）的算法 ③所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上限④同一个算法，实现语言级别越高，执行效率越低
A、 ① B、 ① ② C、 ① ④ D、 ③
12、假设时间复杂度为O(n2)的算法在有200个元素的数组上运行需要3.1ms，则在有400个元素的数组上需要（ ）ms。
13、设有2个算法在同一机器上运行，其执行时间分别为100n2和2n，要使前者快于后者，n至少为（ ）
14、n是描述问题的非负整数，下面程序段的时间复杂度是（ ） x ＝2;while（x A、O(log2n) B、O(n) C、O(nlog2n) D、O(n2) 15、求整数n阶乘的算法如下，其时间复杂度是（ ） int fact(int n){if (n<=1) return 1; return n*fact(n-1)} 3 A、O(log2n) B、 O(n) C、O(nlog2n) D、O(n2) 16、将下列函数按它们在n趋向无穷时，从小到大排序。 n,n-n3+7n5,nlog2n,2n/2,n3,log2n,n1/2+log2n,(3/2)n,n!,n2+log2n 17、分析下列时间复杂度 ①y=0；while((y+1)*(y+1)<=n) y=y+1; ②i=1;j=0;while(i+j<=n) if(i>j) j++;else i++; ③n为偶数，语句y=y+i*j的执行次数是多少？ for(i=1;i<=n;i++) if(2*i<=n) for(j=2*i;j<=n;j++) y=y+i*j; ④T(n) =1 n=1 =2T(n/2)+n n>1 第二章 线性表 考纲分析 线性表 （一）线性表的定义和基本操作 （二）线性表的实现 1.顺序存储 2.链式存储 3.线性表的应用 典型题目解析 顺序表 1、线性表的顺序存储结构是一种（ ）的存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、散列存取 2、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。 A、顺序表 B、双链表 C、带尾指针的单循环链表 D、单链表 3、在n个结点的线性表的数组实现中，算法的时间复杂度是O(1)的操作是（ ）。 A、访问第i个结点和求第i个结点的直接前驱 B、在第i个结点后插入一个新结点 C、删除第i个结点 D、以上都不对。 4、关于线性表，下列说法正确的是（ ） A、线性表中每个元素都有一个直接前驱和一个直接后继 B、线性表中的数据元素可以具有不同的数据类型 C、线性表中数据元素的类型是确定的 D、线性表中任意一对相邻的数据元素之间存在序偶关系 5、顺序表的插入算法中，当n个空间已满时，可再申请增加分配m个空间，若申请失败，则说明系统没有（ ）可分配存储空间。 A、m个 B、m个连续的 C、n+m个 D、 n+m个连续的 6、将下算法改成一个既正确又高效的算法。 Status Delete(Sqlist &a,int i, int k) //删除顺序表a中从第i个元素起的k个元素 {if(i<1||k<0||i+k>a.length)return ERROR; else 4