数据结构各章复习题.doc

第一章 概述一、选择题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正确性6下面运算中（ ）不是数据结构所具备的基本运算。A插入 B排序 C退出 D删除7数据结构是一门研究非数值计算的程序设计问题中计算机的（ 1 ）以及它们之间的（ 2 ）和运算等的学科。（1）A数据元素 B计算方法 C逻辑存储 D数据映像（2）A结构 B关系 C运算 D算法8数据结构被形式地定义为（K，R），其中K是（ 1 ）的有限集，R是K上的（ 2 ）的有限集。（1）A算法 B数据元素 C数据操作 D逻辑结构（2）A操作 B映像 C存储 D关系 9在数据结构中，从逻辑上可以把数据结构分成（ ）。A动态结构和静态结构 B紧凑结构和非紧凑结构C线性结构和非线性结构 D内部结构和外部结构10数据结构在计算机内存中的表示是指（ ）。A数据的存储结构 B数据结构 C数据的逻辑结构 D数据元素之间的关系11在数据结构中，与所使用的计算机无关的是数据的（ ）结构。A逻辑 B存储 C逻辑和存储 D物理12算法分析的目的是（ 1 ），算法分析的两个主要方面是（ 2 ）。（1）A找出数据结构的合理性 B研究算法中的输入和输出的关系 C分析算法的效率以求改进 D分析算法的易懂性和文档性（2）A空间复杂度和时间复杂度 B正确性和简明性 C可读性和文档性 D数据复杂性和程序复杂性13计算机算法指的是（ 1 ），它必须具备输入、输出和（ 2 ）等5个特性。（1）A计算方法 B排序方法 C解决问题的有限运算序列 D调度方法（2）A可行性、可移植性和可扩充性 B可行性、确定性和有穷性 C确定性、有穷性和稳定性 D易读性、稳定性和安全性14在以下的叙述中，正确的是（ ）。A线性表的线性存储结构优于链式存储结构 B二维数组是其数据元素为线性表的线性表C栈的操作方式是先进先出 D队列的操作方式是先进后出15在决定选取何种存储结构时，一般不考虑（ ）。A各结点的值如何 B结点个数的多少C对数据有哪些运算 D所用编程语言实现这种结构是否方便16在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（ ）。A数据的处理方法 B数据元素的类型C数据元素之间的关系 D数据的存储方法17下面说法错误的是（ ）。（1）算法原地工作的含义是指不需要任何额外的辅助空间。（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法。（3）所谓时间复杂度是指最坏情况下，估计算法执行的一个上界。（4）同一个算法，实现语句的级别越高，执行效率越低。A（1） B（1）（2） C（1）（4） D（3）二、填空题1一种数据结构在计算机内存中的（ ）称为存储结构。2数据的逻辑结构包括（ ）（ ）和（ ）三种结构，树形结构和图形结构合称为（非线性结构）。3在线性结构中，第一个结点（ ）前驱结点，其余每个结点有且只有（ ）个前驱结点；最后一个结点（ ）后继结点，其余每个结点有且只有（ ）个后继结点。4在树形结构中，根结点没有（ ）结点，其余每个结点有且只有（ ）个前驱结点，叶子结点没有（ ）结点，其余每个结点的后继结点可以（ ）。5在图形结构中，每个结点的前驱结点数和后继结点数可以（ ）。6线性结构中元素之间存在（ ）关系，树形结构中元素之间存在（ ）关系，图形结构中元素之间存在（ ）关系。7算法的5个重要特性是（ ）、（ ）、（ ）输入和输出。8算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实现上就是程序了。这种说法是（ ）的。9算法效率分析可分为（ ）分析和（ ）分析。10数据结构的存储方式有（ ）、（ ）、（ ）和（ ）4种。11数据结构包括（ ）、（ ）、（ ）三个组成部分。12数据对象是性质相同的（ ）的集合。三、判断题1顺序存储方式只能用于存储线性结构。（ ）2数据元素是数据的最小单位。（ ）3数据结构、数据元素、数据项在计算机中的映像（或表示）分别称为存储结构、结点、数据域。（ ）4数据的物理结构是指数据在计算机内实际的存储形式。（ ）5数据的逻辑结构是对数据元素之间关系的描述，它与数据元素的存储形式无关。（ ）四、问答题1指出下列程序段的时间复杂度（1）i=1 (2) i=n while(i=0 & ai!=k) i=i*3; i-;(3) for(i=0;im;i+) (4) fact(n) for(j=0;jn;j+) if (n=1) aij=i*j; return (1); else return(n*fact(n-1); 2画出下列二元组表示的数据结构对应的逻辑图形，并指出分别属于何种结构。（1）B=（K，R） K=a,b,c,d,e,f,g,h R=, (2) C=(K,R) K=1,2,3,4,5,6 R=(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)第二章 线性表一、选择题1链表不具备的特点是（ ）。A可随机访问任一结点 B插入删除不需要移动元素C不必事先估计存储空间 D所需空间与其长度成正比2不带头结点的单链表head为空的判定条件是（ ）。Ahead=NULL Bhead-next=NULL Chead-next=head Dhead!=NULL3带头结点的单链表head为空的判定条件是( )。Ahead=NULL Bhead-next=NULL Chead-next=head Dhead!=NULL4带头结点的双循环链表L为空表的条件是（ ）。AL=NULL BL-next=NULL CL-prior=NULL DL-next=L5非空的循环单链表head的尾结点（由P所指向）满足（ ）。Ap-next=NULL Bp=NULL Cp-next=head Dp=head6. 在循环双链表的p所指结点之前插入s所指结点的操作是（ ）。Ap-prior=s；s-next=p；p-prior-next=s；s-prior=p-prior；Bp-prior=s；p-prior-next=s；s-next=p；s-prior=p-prior；Cs-next=p；s-prior=p-prior；p-prior=s；p-right-next=s；Ds-next=p；s-prior=p-prior；p-prior-next=s；p-prior=s；7若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用（）存储方式最节省运算时间。A单链表 B给出表头指针的单循环链表 C双链表D带头结点的双循环链表8某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，故采用（）存储方式最节省运算时间。A单链表B仅有头结点的单循环链表C双链表D仅有尾指针的单循环链表9如果最常用的操作是取第i个结点及其前驱，则采用（）存储方式最节省时间。A单链表 B双链表 C单循环链表 D顺序表10在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（）。AO(1) BO(n) CO(n2) DO(nlog2n)11在一个长度为n(n1)的单链表上，设有头和尾两个指针，执行（）操作与链表的长度有关。A删除单链表中的第一个元素 B删除单链表中的最后一个元素C在单链表第一个元素前插入一个新元素 D在单链表最后一个元素后插入一个新元素12设线性表有n个元素，以下算法中，（ ）在顺序表上实现比在链表上实现效率更高。A输出第i(0in-1)个元素值 B交换第0个元素与第1个元素的值C顺序输出这n个元素的值 D输出与给定值x相等的元素在线性表中的序号13设线性表中有2n个元素，算法（ ），在单链表上实现比在顺序表上实现效率更高。A删除所有值为x的元素 B在最后一个元素的后面插入一个新元素C顺序输出前k个元素 D交换第i个元素和第2n-i-1个元素的值(i=0，1，.，n-1)14与单链表相比，双链表的优点之一是（ ）。A插入、删除操作更简单 B可以进行随机访问C可以省略表头指针或表尾指针 D顺序访问相邻结点更灵活15如果对线性表的运算只有4种，即删除第一个元素，删除最后一个元素，在第一个元素前面插入新元素，在最后一个元素的后面插入新元素，则最好使用（）。A只有表尾指针没有表头指针的循环单链表 B只有表尾指针没有表头指针的非循环双链表C只有表头指针没有表尾指针的循环双链表 D既有表头指针也有表尾指针的循环单链表16如果对线性表的运算只有2种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用（）。A只有表头指针没有表尾指针的循环单链表 B只有表尾指针没有表头指针的循环单链表C非循环双链表 D循环双链表17设有两个长度为n的单链表，结点类型相同，若以h1为表头指针的链表是非循环的，以h2为表头指针的链表是循环的，则（ ）。A对于两个链表来说，删除第一个结点的操作，其时间复杂度都是O(1)B对于两个链表来说，删除最后一个结点的操作，其时间复杂度都是O(n)C循环链表要比非循环链表占用更多的内存空间Dh1和h2是不同类型的变量18在长度为n的（ ）上，删除第一个元素，其算法的时间复杂度为O(n)。A只有表头指针的不带表头结点的循环单链表 B只有表尾指针的不带表头结点的循环单链表C只有表尾指针的带表头结点的循环单链表 D只有表头指针的带表头结点的循环单链表19线性表是（ ）。A一个有限序列，可以为空 B一个有限序列，不能为空 C一个无限序列，可以为空 D一个无限序列，不能为空20.设单链表中指针p指向结点M，指针f指向将要插入的新结点X：（1）当X插在链表中两个数据元素M和N之间时，只要先修改（ ）后修改（ ）即可。（2）当X插在链表中最后一个结点M之后时，只要先修改（ ）后修改（ ）即可。Ap-next=f Bp-next=p-next-next Cp-next=f-next Df-next=p-next Ef-next=NULL Ff-next=p21.在单循环链表中指针p指向结点A，若要删除A之后的结点，则指针的操作方式为（ ）。 Ap-next=p-next-next Bp=p-next Cp=p-next-next Dp-next=p22给定有n个元素的向量，建立一个有序单链表的时间复杂度为（ ）。AO（1） BO（n） CO(n2) DO(nlog2n) 23线性表采用链式存储时，其地址（ ）。A必须是连续的 B一定是不连续的 C部分地址必须是连续的 D连续与否均可以24从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（ ）个元素。 An/2 Bn C(n+1)/2 D(n-1)/2二、填空题1在单链表中，要删除某一指定的结点，必须找到该结点的（ ）结点。2访问单链表中的结点，必须沿着（ ）依次进行。3在双链表中，每个结点都有两个指针域，一个指向（ ），另一个指向（ ）。4在（ ）链表上，删除最后一个结点，其算法的时间复杂长为O（1）。5在非循环的（ ）链表中，可以用表尾指针代替表头指针。6在一个单链表中的p所指结点之前插入一个s所指结点时，可执行如下操作：(1)s-next=( )； (2)p-next=s； (3)t=p-data； (4)p-data=( )； (5)s-data=( )；7在一个单链表中删除p所指结点时，应执行以下操作： q=p-next； p-data=p-next-data； p-next=( ) free(q)；8在一个单链表中p所指结点之后插入一个s所指结点时，应执行s-next=( )和p-next=( )的操作。9对于一个具有n个结点的单链表，在*p结点后插入一个新的结点的时间复杂度是（ ），在给定值为x的结点后插入一个新结点的时间复杂度是（ ）。10在一个长度为n的顺序表的第i（1=i=n）个元素之前插入一个元素需向后移动（ ）个元素。11在长度为n的顺序表中，删除第i(1=imin）13已知带头结点的单链表中的元素是无序的，编写函数删除表中所有值大于min且小于max的元素。（maxmin）14编写函数，对一单链表反复找出表中最小元素，并在输出该元素后删除它，直到表为空时结束。15有一个单链表，其结点的元素值以递增有序排列，编写函数删除该单链表中多余的元素值相同的结点。16试写出一个在不带头结点的单链表的第i个元素之前插入一个新元素x 的算法。17有一个有序单链表，表头指针为head，编写函数向该单链表中插入一个元素为x的结点，使插入后该链表仍然有序。18设A，B是两个线性表，其表中元素递增有序，长度分别为m和n，试写算法分别以顺序存储和链式存储将A 和B归并成一个仍按元素值递增有序的线性表C。19编写一个算法将一个头结点指针为pa的单链表A分解成两个单链表A和B，其头结点指针分别为pa和pb，使得A链表中含有原链表A中序号为奇数的元素，而B链表中含有原链表A中序号为偶数的元素，且保持原来的相对顺序。20有一个循环双链表，每个结点由两个指针（prior和next）以及data三个域构成，p指向其中某一结点，编写一函数删除p所指结点。21设有一个循环双链表，其中有一结点的指针为p，编写一个算法将p与其后继结点进行交换。第三章 栈和队列一、选择题1栈和队列的共同点是（ ）。A都是先进后出 B都是先进先出 C只允许在端点处插入和删除元素D没有共同点2一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是（）。Aedcba Bdecba Cdceab Dabcde 3若已知一个栈的进栈序列是1,2,3,.,n,其输出序列为p1,p2,p3,.,pn,若p1=n则pi(1in)为（ ）。Ai Bn-i Cn-i+1 D不确定4若已知一个栈的进栈序列是1,2,3,.,n,其输出序列为p1,p2,p3,.,pn,若pn=n则pi(1itop!=-1 BST-top=-1 CST-top!=MaxSize-1 DST-top=MaxSize-18判定一个栈ST（最多元素为MaxSize）为栈满的条件是（ ）。AST-top!=-1 BST-top=-1 CST-top!=MaxSize-1 DST-top=MaxSize-19最不适合用作链栈的链表是（ ）。A只有表头指针没有表尾指针的循环双链表 B只有表尾指针没有表头指针的循环双链表C只有表尾指针没有表头指针的循环单链表 D只有表头指针没有表尾指针的循环单链表10向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行()。AHS-next=s； Bs-next=HS-next； HS-next=s；Cs-next=HS； HS=s； Ds-next=HS；HS=HS-next；11从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删除结点的值，则执行（ ）。Ax=HS；HS=HS-next； Bx=HS-data；CHS=HS-next；x=HS-data； Dx=HS-data；HS=HS-next；12一个队列的入队序列是1，2，3，4，则队列的输出序列是（ ）。A4，3，2，1B1，2，3，4C1，4，3，2D3，2，4，113判定一个队列QU(最多元素为MaxSize)为空的条件是( )。AQU-rear-QU-front=MaxSize BQU-rear-QU-front-1=MaxSizeCQU-front=QU-rear DQU-front=QU-rear+114循环顺序队列中是否可以插入下一个元素，（ ）。A与队头指针和队尾指针的值有关B只与队尾指针的值有关，与队头指针的值无关C只与数组大小有关，与队首指针和队尾指针的值无关D与曾经进行过多少次插入操作有关15判定一个循环队列QU（最多元素为MaxSize）为空的条件是（ ）。AQU-front=QU-rear BQU-front!=QU-rearCQU-front=(QU-rear+1)%MaxSize DQU-front!=(QU-rear+1)%MaxSize16判定一个循环队列QU（最多元素为MaxSize）为满队列的条件是（ ）。AQU-front=QU-rear BQU-front!=QU-rearCQU-front=(QU-rear+1)%MaxSize DQU-front!=(QU-rear+1)%MaxSize17循环队列用数组A0，m-1存放其元素值，已知其头尾指针分别是front 和rear，则当前队列中的元素个数是（ ）。A(rear-front+m)%m Brear-front+1 Crear-front-1 Drear-front18.若用一个大小为6的一维数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是（ ）。A1 和 5 B2 和 4 C4 和 2 D5 和 119最不适合用作链队列的链表是（ ）。A只带队头指针的非循环双链表 B只带队头指针的循环双链表C只带队尾指针的循环双链表 D只带队尾指针的循环单链表20.在一个链队列中,假设f和r 分别为队头和队尾指针，则插入s所指结点的运算是（）。Af-next=s；f=s； Br-next=s；r=s； Cs-next=r；r=s； Ds-next=f；f=s；21.在一个链队列中,假设f和r 分别为队头和队尾指针，则删除一个结点的运算是（ ）。Ar=f-next； Br=r-next； Cf=f-next； Df=r-next；22设有一个顺序栈S，元素的入栈顺序是S1，S2，S3，S4，S5，S6，如果6个元素出栈的顺序是S2，S4，S3，S6，S5，S1，则栈的容量至少应该是（ ）。 A2 B3 C5 D623和顺序栈相比，链栈比较明显的优势是（ ）。 A通常不会出现栈满的情况 B通常不会出现栈空的情况 C插入操作更容易实现 D删除操作更容易实现24如果以链表作为栈的存储结构，则退栈操作时（ ）。 A必须判别栈是否满 B判别栈元素类型 C必须判别栈是否空 D对栈不作任何判别25设C语言定义数组datam+1作为循环队列的存储空间，front，rear分别为队头，队尾指针，则执行出队操作的语句是（ ）。 Afront=front+1 Bfront=(front+1)%m Cfront=(front+1)%(m+1) Drear=(rear+1)%m26. 输入序列为ABC，可以变为CBA时，经过的栈操作为（ ）。A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop27. 若一个栈以向量V1.n存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是( )。Atop=top+1; V top=x B. V top=x; top=top+1 C. top=top-1; V top=x D. V top=x; top=top-128. 栈在（ ）中应用。A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，29. 表达式a*(b+c)-d的后缀表达式是( )。Aabcd*+- B. abc+*d- C. abc*+d- D. -+*abcd二、填空题1栈的特点是（ ），队列的特点是（ ）。2设栈采用顺序存储结构，若已知i1个元素进栈，则将第i个元素进栈时，进栈算法的时间复杂度为（ ）。3.若用不带头结点的单链表来表示链栈S，则创建一个空栈所要执行的操作是（ ）。4在具有n个单元的循环队列中，队满时共有（ ）个元素。5循环队列的引进目的是为了解决（ ）问题。6在队列中，新插入的结点只能添加到（ ）。7（ ）可以作为实现递归函数调用的一种数据结构。8通常元素进栈的操作方式是（ ）。9通常元素退栈的操作方式是（ ）。10一个栈的输入序列是12345，则栈的输出序列43512是（ ）。11在作进栈运算时应先判别栈是否（满）；在作退栈运算时应先判别栈是否（ ），当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为（ ）。三、简答题1. 用栈实现将中缀表达式8-(3+5)*(5-6/2)转换成后缀表达式，画出栈的变化过程图。2栈和队列的共同点和区别是什么？3. 怎样判定循环队列的空和满？ 4. 画出后缀表达式ABC*D/-E-，求值时操作数栈和运算符栈的变化过程。5. 在一个循环链队中只有尾指针（记为rear，结点结构为数据域data，指针域next），请给出这种队列的入队和出队操作的实现过程。四、算法题1分别写出顺序栈、链栈，顺序队列、链队列的进栈，出栈，入队列、出队列的算法。2利用栈和队列的特点。编写算法判断一个字符串是否为回文。3编写算法将一个十进制数转换成二进制。第四章 串一、选择题1空串与空格串是相同的，这种说法（ ）。A正确 B不正确2串是一种特殊的线性表，其特殊性体现在（ ）。A可以顺序存储 B数据元素是一个字符 C可以链式存储 D数据元素可以是多个字符3设有两个串p和q，求q在p中首次出现的位置的运算称作（ ）。A连接 B模式匹配 C求子串 D求串长4有串s1=“ABCDEFG”，s2=“PQRST”，假设函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s从序号i字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2),subs(s1,len(s2),2)的结果是（ ）。ABCDEF BBCDEFG CBCPQRST DCDEFGFG5已知t=“abcaabbcabcaabdab”，该模式串的next数组值为（ ）。A-1,0,0,0,1,1,2,0,0,1,2,3,4,5,6,0,1 B 0,1,0,0,1,1,2,0,0,1,2,3,4,5,6,0,1C-1,0,0,0,1,1,2,0,0,1,2,3,4,5,6,7,1 D-1,0,0,0,1,1,2,3,0,1,2,3,4,5,6,0,16若串s=”software”,其子串的个数是（ ）。 A8 B37 C36 D97KMP算法的特点是在模式匹配时指示主串的指针不会变小，这种说法（ ）。A正确 B错误二、填空题1串的两种最基本的存储方式是（ ）。2两个串相等的充分必要条件是（ ）。3空串的长度等于（ ），空格串的长度等于（ ）。4设s=“I AM A TEACHER”其长度是（ ）。5设s1=”GOOD”,s2=” ”,s3=”BYE!”则s1,s2,s3连接后的结果是（ ）。6BF算法的时间复杂度为（ ），KMP算法的时间复杂度为（ ）第五章 数组和广义表一、选择题1一维数组和线性表的区别是（ ）。A前者长度固定，后者长度可变 B后者长度固定，前者长度可变C两者长度均固定 D两者长度均可变2二维数组M的成员是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要（ ）个字节，M的第8列和第5行共占（ ）个字节，若M按行优先方式存储，元素M85的起始地址与当M按列优先方式存储时元素（ ）的起始地址一致。A90 B180 C240 D540A108 B114C54D60AM85 BM310 CM58 DM093二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i范围从0到4，列下标j的范围从0到5，M按行优先存储时元素M35的起始地址与M按列优先存储时元素（ ）的起始地址相同。AM24 BM34 CM35 DM444数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是（ ）。A80 B100 C 240 D2705数组A中每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A85的起始地址为（ ）。ASA+141 BSA+144 CSA+222 DSA+2256