2015级数据结构习题
第1章 绪论
一、单项选择题：（从给定的选项中选择出一个最恰当的答案） 1．算法分析的目的是 _____ 。
A．找出数据结构的合理性 B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进 D．分析算法的易懂性和文档性 2．线性表的顺序存储结构是一种 ____的存储结构。
A．随机存取 B．顺序存取 C．索引存取 D．散列存取 3. 顺序存储设计时，存储单元的地址______。
A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续 4. 下列数据中_______是非线性数据结构。
A．栈 B. 队列 C. 完全二叉树 D. 串 5．一个算法应该是_______。
A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 6．以下属于逻辑结构的是_______。
A．顺序表 B． 哈希表 C．线性表 D． 单链表 7．计算机执行下面的语句时，语句s的执行频度为 _______ 。 FOR(i=l；i
A． O（n） B．O(nlogn) C． O(n3) D．O(n2) 8．算法分析的两个主要方面是 _____ 。
A．空间复杂性和时间复杂性 B．正确性和简明性
C．可读性和文档性 D．数据复杂性和程序复杂性 9．下面说法错误的是________.
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.在作退栈运算时应先判别栈是否______。
A. 空 B. 满 C. 上溢 D. 下溢
16. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是_____。
A. i-j-1 B. i-j C. j-i+1 D. 不确定的 17．在一个链队中，假设f和r分别为队首和队尾指针，则插入s所指结点的运算时 ____ 。 A．f->next=s; f=s; B．r->next=s;r=s; C．s->next=r; r=s; D．s->next=f; f=s;
18．判定一个循环队列QU(最多元素为m0)为空的条件是 。
A．QU.front== （QU.rear+1）%m0 B．QU.front！= （QU.rear+1）%m0 C．QU.front== QU.rear D．QU.front！= QU.rear
19．在单项循环链表head的末尾（rear指针指向）插入s指针指向的结点，正确操作是______。
A．rear->next=s;s->next=head; B．s->next=rear; rear->next=head; C． rear=s; s->next=head; D．rear->next=s; s=head; 20．已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=〃SCIENCESTUDY〃，则调用函数Scopy(P,Sub(S,1,7))后得到_______ 。
A．P=〃SCIENCE〃 B．P=〃STUDY〃 C．S=〃SCIENCE〃 D．S=〃STUDY〃
21. 设计一个判别表达式中左，右括号是否配对出现的算法，采用______数据结构最佳。 A．线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈 22. 用链接方式存储的队列，在进行删除运算时______。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针都不修改
23．以下算法的功能是______(栈和队列的元素类型均为int)。 void algo（Stack S, int e）｛ Stack T； int d； InitStack（T）；
while (!StackEmpty(S)) {
pop(S, d); if (d!=e ) push(T, d); } while (!StackEmpty(T)) { pop(T, d); push(S, d); } ｝
A．删除栈S中的数据e B. 判断栈S中是否存在数据e C．将栈S中的数据逆置 D.将栈S中的数据放入栈T中 24. 以下算法的功能（栈中的数据元素类型为int）是_______。 void status algo( Stack S) {int i, n, a[255]; n=0;
while (!StackEmpty(S)) { n++ ; Pop(S, a[n]);} for ( i=1; i<=n; i++) Push ( S, a[i]); }
A．将栈S中的元素逆置 B．将数组a中的元素逆置 C．输出栈S中的元素 D．输出数组a中的元素
25．与单向链表相比，使用双向链表存储数据，其优点是可以______。 A．提高检索速度 B．很方便地插入和删除数据 C．节约存储空间 D．很快回收存储空间
26．当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为______。 A．n-2 B．n-1 C．n D．n+1
27．指针p、q和r依次指向某循环链表中三个相邻的结点，交换结点*q和结点*r在表中次序的程序段是______。 A．p->next=r；q->next=r->next；r->next=q； B．p->next=r；r->next=q；q->next=r->next；C．r->next=q；q->next=r->next；p->next=r； D．r->next=q；p->next=r；q->next=r->next； 28．串的操作函数str定义为：int str(char*s) {char *p=s；while (*p！=′\\0′)p++；return p-s；}则str(〃abcde〃)的返回值是______。
A．3 B．4 C．5 D．6
29．与线性表相比，串的插入和删除操作的特点是______。
A．通常以串整体作为操作对象 B．需要更多的辅助空间 C．算法的时间复杂度较高 D．涉及移动的元素更多
30．对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K%9作为散列函数，则散列地址为1的元素有______个。
A．1 B．2 C．3 D．4
31．设主串长为n，模式串长为m(m≤n)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为______。
A．m B．n-m C．n-m+1 D．n 32．已知顺序表的存储结构为：typedef struct{Elemtype v[ ]; int length;}L;
以下算法的功能是_______。 void SortA(sqlist &L) { int i=0, zerosum =0; if (L.length==0) return(0);
else for( i=1; i<=L.length; i++) {if (L.v[i]<>0) L.v[i- zerosum]= L.v[i]; else zerosum++; } ｝
A．计算线性表L中非零元素数目 B．将线性表L中零元素集中到表尾 C．删除线性表L中的零元素 D．计算线性表L中零元素数目 33．在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是______。 A．访问第i个元素的前驱( ) B．在第i个元素之后插入一个新元素( ) C．删除第i个元素( ) D．对顺序表中元素进行排序 34．带头结点的单链表first为空的判定条件是______。
A．first==NULL B．first->1ink==NULL C．first->link==first D．first!＝NULL 35．一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是_______。 A．2 3 4 1 5 B．5 4 1 3 2 C．2 3 1 4 5 D．1 5 4 3 2 36．设循环队列的结构是：struct{int data[Maxsize]; int front,rear;}Q;
试问判断队列满的条件应是下列语句______。