数据结构习题(1,2,3章)

-第一章 绪论一选择题1下面关于算法说法正确的是（ ） A算法最终必须由计算机程序实现 B为解决某问题的算法同为该问题编写的程序含义是相同的 C算法的可行性是指指令不能有二义性 D以上几个都是错误的2以下哪一个术语与数据的存储结构无关？（ ） A栈 B哈希表 C线索树 D循环队列3算法复杂度通常是表达算法在最坏情况下所需要的计算量，O(1)的含义是（ ） A算法执行一步就完成 B算法执行1秒钟就完成 C算法执行常数步就完成 D算法执行可变步数就完成4数据结构研究的内容是（ ）。 A数据的逻辑结构 B数据的存储结构 C建立在相应逻辑结构和存储结构上的算法 D包括以上三个方面5一个正确的算法应该具有 5 个特性，除输入、输出特性外，另外 3 个特性是（ ）。 A确定性、可行性、有穷性 B易读性、确定性、有效性 C有穷性、稳定性、确定性 D可行性、易读性、有穷性 6以下关于数据的逻辑结构的叙述中正确的是（ ）。 A数据的逻辑结构是数据间关系的描述 B数据的逻辑结构反映了数据在计算机中的存储方式 C数据的逻辑结构分为顺序结构和链式结构 D数据的逻辑结构分为静态结构和动态结构 7下列时间复杂度中最坏的是（ ） AO(1) BO(n) CO(log2n） DO(n2)8算法的时间复杂度取决于（ ） A待处理数据的初态 B问题的规模 C程序本身所占的空间 D问题的规模和待处理数据的初态二综合应用题1.有下列运行时间函数： （1）f1(n)=1000; （2）f2(n)=n2+1000n; （3）f3(n)=3n3+100n2+n+1;分别写出相应的大O表示的运算时间。2.下面函数mergesort执行的时间复杂度为多少?假设函数调用为mergesort(1,n)，merge 函数时间复杂度为 O(n)void mergesort(int i,int j)int m;if(i!=j)mergesort(i,m);mergesort(m+1,j);merge(i,j,m);/本函数时间复杂度为 O(n) 第二章 线性表一选择题1下述哪一条是顺序存储结构的优点？（ ）A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示2下面关于线性表的叙述中，错误的是哪一个？（ ）A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。3若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表4某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表5在一个长度为n的顺序表中删除第i个元素(1=inext=p-next-next; Bp=p-next;Cp=p-next-next; Dp-next=p;8在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（ ）As-next=p-next; p-next=sBq-next=s; s-next=pCp-next=s-next; s-next=pDp-next=s; s-next=q9线性表的顺序存储结构是一种（ ）的存储结构。A随机存取B顺序存取C索引存取D散列存取二算法设计1设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在），试编写能实现下列功能的算法（要求用最少的时间和最小的空间）确定在序列中比正整数x大的数有几个（相同的数只计算一次）将单链表中比正整数x小的偶数从单链表中删除2设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。phh3设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。4. 假设链表A、B分别表示一个集合，试设计算法以判断集合A是否是集合B的子集，若是，则返回1，否则返回0，并分析算法的时间复杂度。5设有一单循环链表la，其结点有三个域：prior、data与next，其中data为数据域,，next域指向直接后继，prior域应指向直接前驱，但目前空着。试写一算法将此单循环链表改造为双向循环链表。6设顺序表用数组 A表示，表中元素存储在数组下标 1m+n 的范围内，前 m 个元素递增有序，后 n 个元素递增有序，设计一个算法，使得整个顺序表有序。（1）给出算法的基本设计思想。（2）根据设计思想，采用C或C+语言描述算法，关键之处给出注释。（3）说明你所设计算法的时间复杂度和空间复杂度。第三章 栈和队列一选择题1已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（ ）A.5，4，3，2，1，6B.2，3，5，6，1，4C.3，2，5，4，1，6D.1，4，6，5，2，32在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（ ）Atop不变 Btop=0 Ctop- Dtop+3在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（ ）Arearn= = front B（front+l）n= = rearCrearn -1= = front D(rear+l)n= = front4在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为（ ） Arearn= = front Bfront+l= rearCrear= = front D(rear+l)n= front5在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为（ ）Afront=front-next Brear=rear-nextCrear=front-next Dfront=rear-next6某堆栈的输入序列为1，2，3，n，输出序列的第一个元素是n，则第i个输出元素为（ ）Ai Bn-i Cn-i+1 D哪个元素无所谓7用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( )。A仅修改队头指针 B仅修改队尾指针 C队头、队尾指针都要修改 D队头,队尾指针都可能要修改8最适合用做链队列的链表（链表有头结点，有队首指针则指向头结点，有队尾指针则指向终端结点）是（ ）。A只带队首指针的循环单链表。B只带队尾指针的循环单链表。C只带队首指针的非循环单链表。D只带队尾指针的非循环单链表。9最不适合用做队列的链表是（ ）。A只带队首指针的非循环双链表。B只带队首指针的循环双链表。C只带队尾指针的循环双链表。D只带队尾指针的循环单链表。二填空题1线性表、栈和队列都是 结构。线性表可以在 插入和删除元素；栈只能在 插入和删除元素；队列只能在 插入元素和 删除元素。2假设以S和X分别表示进栈和退栈运算，则对输入序列a,b,c,d,e进行一系列栈运算SSXSXSSXXX之后，得到的输出序列为 。3设栈S和队列Q的初始状态为空，元素a,b,c,d,e,f依次通过栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序是b,d,c,f,e,a，则栈S的容量至少应该是 。三解答题1一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。 试为此双向栈设计初始化InitStack ( S ) 、入栈Push( S , i , x) 和出栈Pop( S , i )等算法， 其中i为0 或1， 用以表示栈号。2利用两个栈S1、S2模拟一个队列时，如何使用栈的运输实现队列的插入、删除运算。3简述下列算法的功能，并给出队