下载文档原格式
第3章栈和队列一、选择题1.栈结构通常采用的两种存储结构是（A ）。
A、顺序存储结构和链表存储结构B、散列和索引方式C、链表存储结构和数组D、线性链表结构和非线性存储结构2.设栈ST 用顺序存储结构表示，则栈ST 为空的条件是（ B ）A、ST.top-ST.base<>0B、ST.top-ST.base==0C、ST.top-ST.base<>nD、ST.top-ST.base==n3.向一个栈顶指针为HS 的链栈中插入一个s 结点时，则执行（ C ）A、HS->next=s;B、s->next=HS->next；HS->next=s;C、s->next=HS；HS=s;D、s->next=HS；HS=HS->next;4.从一个栈顶指针为HS 的链栈中删除一个结点，用x 保存被删除结点的值，则执行（ C）A 、x=HS；HS=HS->next;B 、HS=HS->next；x=HS->data;C 、x=HS->data；HS=HS->next;D 、s->next=Hs；Hs=HS->next;5.表达式a*(b+c)-d 的后缀表达式为（ B ）A、abcdd+-B、abc+*d-C、abc*+d-D、-+*abcd6.中缀表达式A-（B+C/D）*E 的后缀形式是（ D ）A、AB-C+D/E*B、ABC+D/E*C、ABCD/E*+-D、ABCD/+E*-7.一个队列的入列序列是1，2，3，4，则队列的输出序列是（ B ）A、4，3，2，1B、1，2，3，4C、1，4，3，2D、3，2，4，18.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为空的条件是（）A、Q.rear-Q.front==nB、Q.rear-Q.front-1==nC、Q.front==Q.rearD、Q.front==Q.rear+19.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为满的条件是（）A、Q.front==Q.rearB、Q.front!=Q.rearC、Q.front==(Q.rear+1)%nD、Q.front!=(Q.rear+1)%n10.若在一个大小为6 的数组上实现循环队列，且当前rear 和front 的值分别为0 和3，当从队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为（）A、1，5B、2, 4C、4，2D、5，111.用单链表表示的链式队列的队头在链表的（）位置A、链头B、链尾C、链中12.判定一个链队列Q（最多元素为n 个）为空的条件是（）A、Q.front==Q.rearB、Q.front!=Q.rearC、Q.front==(Q.rear+1)%nD、Q.front!=(Q.rear+1)%n13.在链队列Q 中，插入s 所指结点需顺序执行的指令是（）A 、Q.front->next=s；f=s;B 、Q.rear->next=s；Q.rear=s;C 、s->next=Q.rear；Q.rear=s;D 、s->next=Q.front；Q.front=s;14.在一个链队列Q 中，删除一个结点需要执行的指令是（）A、Q.rear=Q.front->next;B、Q.rear->next=Q.rear->next->next;C、Q.front->next=Q.front->next->next;D、Q.front=Q.rear->next;15.用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）A、仅修改队头指针B、仅修改队尾指针C、队头尾指针都要修改D、队头尾指针都可能要修改。
数据结构习题及解答第1章概述【例1-1】分析以下程序段的时间复杂度。
for(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]=0;解：该程序段的时间复杂度为O(m*n)。
【例1-2】分析以下程序段的时间复杂度。
i=s=0; ①while(s<n){ i++; ②s+=i; ③}解：语句①为赋值语句，其执行次数为1次，所以其时间复杂度为O(1)。
语句②和语句③构成while循环语句的循环体，它们的执行次数由循环控制条件中s与n的值确定。
假定循环重复执行x次后结束，则语句②和语句③各重复执行了x次。
其时间复杂度按线性累加规则为O(x)。
此时s与n满足关系式：s≥n，而s=1+2+3+…+x。
所以有：1+2+3+…+x ≥n，可以推出：x=x与n之间满足x=f(），所以循环体的时间复杂度为O()，语句①与循环体由线性累加规则得到该程序段的时间复杂度为O(）。
【例1-3】分析以下程序段的时间复杂度。
i=1; ①while(i<=n)i=2*i; ②解：其中语句①的执行次数是1，设语句②的执行次数为f(n)，则有：。
得：T（n）=O()【例1-4】有如下递归函数fact(n)，分析其时间复杂度。
fact(int n){ if(n<=1)return(1); ①elsereturn(n*fact(n-1)); ②}解：设fact（n）的运行时间函数是T(n)。
该函数中语句①的运行时间是O(1)，语句②的运行时间是T(n-1)+ O(1)，其中O(1)为常量运行时间。
由此可得fact（n）的时间复杂度为 O(n)。
习题1一、单项选择题1. 数据结构是指（1. A ）。
A.数据元素的组织形式B.数据类型C.数据存储结构D.数据定义2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（2. C ）。
A.存储结构B.逻辑结构C.链式存储结构D.顺序存储结构3. 树形结构是数据元素之间存在一种（3. D ）。
第3章栈和队列习题1．选择题（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）种情况。
A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1（2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。
A．i B．n-i C．n-i+1 D．不确定（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。
A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n （4）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。
A．x=top->data;top=top->link； B．top=top->link;x=top->link；C．x=top;top=top->link； D．x=top->link；（5）设有一个递归算法如下int fact(int n) { //n大于等于0if(n<=0) return 1;else return n*fact(n-1); }则计算fact(n)需要调用该函数的次数为（）。
A． n+1 B． n-1 C． n D． n+2 （6）栈在（）中有所应用。
A．递归调用 B．函数调用 C．表达式求值 D．前三个选项都有（7）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。
主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。
该缓冲区的逻辑结构应该是（）。
A．队列 B．栈 C．线性表 D．有序表（8）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（）。
第1章绪论习题一、问答题1. 什么是数据结构?2. 四类基本数据结构的名称与含义.3. 算法的定义与特性。
4. 算法的时间复杂度。
5. 数据类型的概念。
6. 线性结构与非线性结构的差别.7. 面向对象程序设计语言的特点.8. 在面向对象程序设计中，类的作用是什么？9. 参数传递的主要方式及特点。
10. 抽象数据类型的概念。
二、判断题1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。
2. 算法就是程序.3. 在高级语言(如C、或PASCAL）中，指针类型是原子类型。
三、计算下列程序段中X=X+1的语句频度for(i=1；i<=n;i++）for(j=1;j〈=i;j++)for（k=1；k<=j；k++）x=x+1;［提示］：i=1时：1 = （1+1)×1/2 = （1+12）/2i=2时：1+2 = （1+2）×2/2 = （2+22)/2i=3时：1+2+3 = （1+3)×3/2 = （3+32)/2…i=n时：1+2+3+……+n = (1+n）×n/2 = （n+n2)/2f(n）= [ (1+2+3+……+n) + （12 + 22 + 32 + …… + n2 ）] / 2=[ （1+n)n/2 + n(n+1)（2n+1)/6 ] / 2=n（n+1）(n+2)/6=n3/6+n2/2+n/3区分语句频度和算法复杂度：O(f(n)）= O(n3)四、试编写算法求一元多项式Pn（x)=a0+a1x+a2x2+a3x3+…a n x n的值P n（x0），并确定算法中的每一语句的执行次数和整个算法的时间复杂度,要求时间复杂度尽可能的小,规定算法中不能使用求幂函数。
注意：本题中的输入a i（i=0,1，…，n), x和n，输出为P n(x0)。
通常算法的输入和输出可采用下列两种方式之一:（1）通过参数表中的参数显式传递；（2）通过全局变量隐式传递。
第3章数据结构一、选择题1. 图形结构是数据元素之间存在一种____B_____。
A 一对多关系B 多对多关系C 多对一关系D 一对一关系2.算法分析的目的是___C_____。
A 找出数据结构的合理性B 研究算法中的输入和输出的关系C 分析算法的效率以求改进D 分析算法的易懂性和文档性3.算法的时间复杂度与___A____ 有关。
A 问题规模B 计算机硬件性能C 程序设计语言的类型或版本D 算法设计者的水平4.有下面的算法段：for (i=0; i<n; i++)k++;其时间复杂度为 B 。
A．O(1) B．O(n) C．O(log2n) D．O(n2)5.计算机算法必须具备输入、输出和___C____。
A、计算方法B、排序方法C、解决问题的有限运算步骤D、程序设计法6.____B___是数据的基本单位。
A、数据结构B、数据元素C、数据项D、数据类型7.下面，对非空线性表特点的论述，___C____是正确的。
A．所有结点有且只有一个直接前驱B．所有结点有且只有一个直接后继C．每个结点至多只有一个直接前驱，至多只有一个直接后继D．结点间是按照1对多的邻接关系来维系其逻辑关系的8.在顺序表中，只要知道____D____，就可以在相同的时间内求出任一结点的存储地址。
A、开始结点B、终端结点C、向量大小D、基地址和结点大小9.在非空线性表中，有且只有一个直接前驱和一个直接后继的结点是__C____。
A、开始结点B、终端结点C、内部结点D、所有结点10.顺序表中逻辑上相邻的结点的物理位置为_____A___。
A、一定相邻B、不必相邻C、按某种规律排列D、不要求11.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是____B___。
A 110B 108C 100D 12012.链表不具有的特点是____A___。
A、可以随机访问任何一个元素B、插入和删除元素不需要移动元素C、不必事先估计存储空间D、所需的存储空间和链表长度无关13.数据结构反映了数据元素之间的结构关系。
第1章 绪论1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。
1。
2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。
1。
3 设有数据结构(D ，R)，其中{}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r =试按图论中图的画法惯例画出其逻辑结构图.1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。
1.5 试画出与下列程序段等价的框图.(1) product=1; i=1; while （i 〈=n)｛ product *= i; i++; ｝ (2） i=0; do { i++;} while(（i ！=n) &＆ （a[i ］！=x)）; （3） switch ｛case x 〈y ： z=y —x ； break; case x=y: z=abs(x ＊y)； break ； default: z=（x —y ）/abs(x)*abs(y ）; ｝1。
6 在程序设计中,常用下列三种不同的出错处理方式：(1） 用exit 语句终止执行并报告错误；（2） 以函数的返回值区别正确返回或错误返回；(3) 设置一个整型变量的函数参数以区别正确返回或某种错误返回. 试讨论这三种方法各自的优缺点。
1.7 在程序设计中，可采用下列三种方法实现输出和输入：(1） 通过scanf 和printf 语句； (2) 通过函数的参数显式传递； (3) 通过全局变量隐式传递。
试讨论这三种方法的优缺点.1。
8 设n 为正整数.试确定下列各程序段中前置以记号@的语句的频度：（1） i=1; k=0；while(i<=n-1){@ k += 10＊i；i++；}(2) i=1； k=0；do {＠ k += 10*i；i++；｝ while（i<=n-1)；(3) i=1; k=0;while (i〈=n-1) {i++；@ k += 10*i；｝（4） k=0;for（i=1; i〈=n； i++) {for(j=i; j<=n； j++）@ k++;}(5) for(i=1; i〈=n； i++) ｛for(j=1； j<=i; j++) {for(k=1； k〈=j； k++）＠ x += delta；}(6) i=1； j=0；while(i+j〈=n) ｛＠ if（i〉j) j++；else i++;}（7) x=n； y=0; // n是不小于1的常数while(x>=(y+1）＊（y+1)） {@ y++;｝（8） x=91； y=100；while(y〉0) {@ if（x>100) { x -= 10; y——; }else x++;}1。
第三章 栈和队列 试题2. 当利用大小为 n 的数组顺序存储一个栈时，假定用首先应执行（ ）语句修改 top 指针。
A. top++ ;B. top -- ;top ==n 表示栈空，则向这个栈插入一个元素时， C. top = 0A. 3, 2, 1B. 2, 1, 3C. 3, 1, 2 4.在一个顺序存储的循环队列中，队头指针指向队头元素的（ ）位置。
A. 前一个B. 后一个C. 当前D. 后面5. 当利用大小为 n 的数组顺序存储一个队列时，该队列的最大长度为（ ）。
A. n-2B. n-1C. nD. n+16. 从一个顺序存储的循环队列中删除一个元素时，需要（ ）。
A. 队头指针加一B. 队头指针减一C. 取出队头指针所指的元素D. 取出队尾指针所指的元素一、单项选择题 1. 栈的插入和删除操作在（ A. 栈顶）进行。
B. 栈底C. 任意位置D. 指定位置3. 若让元素 1,2,3依次进栈，则出栈次序不可能出现（ ）种情况。
D. topD. 1, 3, 27. 假定一个顺序存储的循环队列的队头和队尾指针分别为front 和 rear ，则判断队空的条件为 ）。
A. front+1 == rearB. rear+1 == frontC. front == 0D. front == rear8. 假定一个链式队列的队头和队尾指针分别为A. front == rear C. rear != NULLfront 和 rear ，则判断队空的条件为（ ）。
B. front != NULLD. front == NULL9. 设链式栈中结点的结构为（ data, link 个由指针 s 所指的结点，则应执行操作（ A.top->link = s;C. s->link = top ; top = s），且 top 是指向栈顶的指针。
若想在链式栈的栈顶插入一 ）。
B. s->link = top->link ; top->link = s D. s->link = top; top = top->link;10. 设 链式栈中结点的结构为（ 并将被摘除结点的值保存到 data, link ），且 top x中，则应执行操作（是指向栈顶的指针。
