2015级数据结构习题
第1章绪论
一、单项选择题：（从给定的选项中选择出一个最恰当的答案） 1．算法分析的目的是 __c___ 。
A．找出数据结构的合理性 B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进 D．分析算法的易懂性和文档性 2．线性表的顺序存储结构是一种 _A__的存储结构。
A．随机存取 B．顺序存取 C．索引存取 D．散列存取 3. 顺序存储设计时，存储单元的地址____A__。
A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续 4. 下列数据中____C___是非线性数据结构。
A．栈 B. 队列 C. 完全二叉树 D. 串 5．一个算法应该是___B____。
A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 6．以下属于逻辑结构的是___C____。
A．顺序表 B．哈希表 C．线性表 D． 单链表 7．计算机执行下面的语句时，语句s的执行频度为 ___D____ 。 FOR(i=l；i
A． O（n） B．O(nlogn) C． O(n3) D．O(n2) 8．算法分析的两个主要方面是 ___A__ 。
A．空间复杂性和时间复杂性 B．正确性和简明性 C．可读性和文档性 D．数据复杂性和程序复杂性 9．下面说法错误的是___A_____.
A．算法原地工作的含义是指不需要增加额外的辅助空间
B. 在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 C. 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 D.同一个算法，实现语言的级别越高，执行效率就越低
10．一个顺序表的第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是______。
A．110 B．108 C．100 D．120
11．从存储结构上可以把数据结构分为_____两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 12．下列叙述中正确的是_____ 。
A．一种逻辑数据结构只能有一种存储结构。
B．数据的逻辑结构属于线性结构，存储结构属于非线性结构。
C．一种逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率。D．一种逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率。
13．算法的计算量的大小称为计算的_______。
A．效率 B. 复杂性 C. 现实性 D. 难度 14．下述_____是顺序存储结构的优点？ A．存储密度大 B．插入运算方便
C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示 15．以下叙述中错误的是_______。 A．算法正确的程序最终一定会结束 B．算法正确的程序可以有零个输出 C．算法正确的程序可以有零个输入
D．算法正确的程序对于相同的输入一定有相同的结果 16．数据结构的定义为(D，S)，其中D是______的**。
A．算法 B．数据元素 C．数据操作 D．逻辑结构 17．执行完下列语句段后，i值为_______。 int f(int x)
{ return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1));
A．2 B． 4 C． 8 D．无限递归 18．一个递归算法必须包括______。
A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分
二、判断对错题：（正确的选A，错误的选B）
1. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。（ ）
2. 顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。（ ） 3. 记录是数据处理的最小单位。（ ） 4. 程序一定是算法。（ ）
5. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。（ ）
6. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。（ ） 7. 递归的算法简单、易懂、容易编写，而且执行效率也高。（ ） 8. 每种数据结构都应具备三种基本运算：插入、删除和搜索。（ ）
三、应用题
1. 给出圆环类的声明（内径为R1, 外径为R2）（包括求圆环面积、圆环内周长和外周长）。 2. 给出等腰三角形类的声明（腰长为a, 底长为b）（包括求面积与周长）。
第2章线性表
一、单项选择题：（从给定的选项中选择出一个最恰当的答案）
1．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用______存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 2．以下数据结构中，_______ 是线性结构。
A．哈希表 B. 二叉树 C. 有向图 D. 串
3．设单链表中结点的结构为struct node {ElemType data；struct node * Link；}；已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列______操作。 A． s->link = p； p->link = s； B． s->link = p->link； p->link = s； C． s->link = p->link； p = s； D． p->link = s； s->link = p； 4. 在作进栈运算时,应先判别栈是否_____。
A. 空 B. 满 C. 上溢 D. 下溢
5．若栈顶指针指向栈顶元素，当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为_____。
A. n-1 B. n C. n+1 D. n/2 6. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，若栈顶指针指向栈顶元素，则栈满的条件是_____。 A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2]
7. 递归过程或函数调用时，处理参数及返回地址，要用一种称为_______的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表 8. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为______. A. 1和 5 B. 2和4 C. 4和2 D. 5和1 9.若进队列的序列为1,2,3,4 则_____是一个出队列序列。 A. 3,2,1,4 B. 3,2,4,1 C. 4,3,2,1 D. 1,2,3,4
10．在一个链队中，假设f和r分别为队首和队尾指针，则删除一个结点的运算时 ___ 。 A．r=f->next; B．r=r->next; C．f=f->next; D．f=r->next; 11．线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为_______。 A．O（i） B．O（1） C．O（n） D．O（i-1）
12．删除一单向链表中P指针所指向结点的后继结点，正确的操作是_______。 A．p->next=p->next->next; B． p=p->next;
C． p->next=p； D． p->next->next=p->next；
13．为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的_______设在内存空间的两端。
A．长度 B．深度 C．栈顶 D．栈底 14．栈在_______中应用。
A．递归调用 B．子程序调用 C．表达式求值 D． A，Ｂ，Ｃ31．栈和队列都是_______。
A．顺序存储的线性结构 B．链式存储的线性结构 C．限制存取点的线性结构 D．限制存取点的非线性结构 15.在作退栈运算时应先判别栈是否______。