数据结构各章复习题

11．在下面的程序段中，对x的赋值语句的频度为（c）FORi:=1TOnDOFORj:=1TOnDOx:=x+1;A．O(2n)B．O(n)C．O(n2)D．O(log2n)12．程序段FORi:=n-1DOWNTO1DOFORj:=1TOiDOIFA[j]A[j+1]THENA[j]与A[j+1]对换；其中n为正整数，则最后一行的语句频度在最坏情况下是（d）A．O（n）B.O(nlogn)C.O(n3)D.O(n2)3.数据的逻辑结构是指数据的各数据项之间的逻辑关系；(f)5．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。(t)8．数据的物理结构是指数据在计算机内的实际存储形式。(t)13.数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构.(f)3．数据的逻辑结构是指:数据的组织形式，即数据元素之间逻辑关系的总体。而逻辑关系是指数据元素之间的关联方式或称“邻接关系”4．一个数据结构在计算机中称为存储结构:表示（又称映像）9．已知如下程序段FORi:=nDOWNTO1DO{语句1}BEGINx:=x+1；{语句2}FORj:=nDOWNTOiDO{语句3}y:=y+1;{语句4}END；语句1执行的频度为（1）；语句2执行的频度为（2）；语句3执行的频度为（3）；语句4执行的频度为（4）。9．（1）n+1（2）n（3）n(n+3)/2（4）n(n+1)/2。10．在下面的程序段中，对ｘ的赋值语句的频度为______（表示为n的函数）FORi：＝１TOnDOFORj：＝１TOiDOFORk：＝1TOjDOｘ：＝ｘ＋delta；10．1+（1+2++（1+2+3）+…+（1+2+…+n）=n(n+1)(n+2)/6O(n3)3.数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？符型等。整型值的范围（对具体机器都应有整数范围），其操作有加、减、乘、除、求余等。实际上数据类型是厂家提供给用户的已实现了的数据结构。“抽象数据类型（ADT）”指一个数学模型及定义在该模型上的一组操作。“抽象”的意义在于数据类型的数学抽象特性。抽象数据类型的定义仅取决于它的逻辑特性，而与其在计算机内部如何表示和实现无关。无论其内部结构如何变化，只要它的数学特性不变就不影响它的外部使用。抽象数据类型和数据类型实质上是一个概念。此外，抽象数据类型的范围更广，它已不再局限于机器已定义和实现的数据类型，还包括用户在设计软件系统时自行定义的数据类型。使用抽象数据类型定义的软件模块含定义、表示和实现三部分，封装在一起，对用户透明（提供接口），而不必了解实现细节。抽象数据类型的出现使程序设计不再是“艺术”，而是向“科学”迈进了一步。6．解释和比较以下各组概念（1）抽象数据类型及数据类型:见上面题3（2）数据结构、逻辑结构、存储结构:4．（1）数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，和存储结构无关，而运算的实现则是依赖于存储结构。（2）逻辑结构相同但存储不同，可以是不同的数据结构。例如，线性表的逻辑结构属于线性结构，采用顺序存储结构为顺序表，而采用链式存储结构称为线性链表。（3）栈和队列的逻辑结构相同，其存储表示也可相同（顺序存储和链式存储），但由于其运算集合不同而成为不同的数据结构。（4）数据结构的评价非常复杂，可以考虑两个方面，一是所选数据结构是否准确、完整的刻划了问题的基本特征；二是是否容易实现（3）抽象数据类型:）见上面题3（4）算法的时间复杂性:（4）算法的时间复杂性是算法输入规模的函数。算法的输入规模或问题的规模是作为该算法输入的数据所含数据元素的数目，或与此数目有关的其它参数。有时考虑算法在最坏情况下的时间复杂度或平均时间复杂度。（5）算法:算法是对特定问题求解步骤的描述，是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有五个重要特性：有穷性、确定性、可行性、输入和输出（6）频度:在分析算法时间复杂度时，有时需要估算基本操作的原操作，它是执行次数最多的一个操作，该操作重复执行的次数称为频度。第二章4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（a）存储方式最节省时间。A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（d）存储方式最节省运算时间。A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用(d)最节省时间。A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表9.链表不具有的特点是（b）A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比18．在一个以h为头的单循环链中，p指针指向链尾的条件是（a）A.p＾.next=hB.p＾.next=NILC.p＾.next.＾next=hD.p＾.data=-119．完成在双循环链表结点p之后插入s的操作是（d）；A．p^.next:=s;s^.priou:=p;p^.next^.priou:=s;s^.next:=p^.next;B．p^.next^.priou:=s;p^.next:=s;s^.priou:=p;s^.next:=p^.next;C．s^.priou:=p;s^.next:=p^.next;p^.next:=s;p^.next^.priou:=s;D．s^.priou:=p;s^.next:=p^.next;p^.next^.priou:=s;p^.next:=s;20．在双向循环链表中,在p指针所指向的结点前插入一个指针q所指向的新结点,其修改指针的操作是(c)。注:双向链表的结点结构为(llink,data,rlink)。供选择的答案：A．p↑.llink：=q；q↑.rlink：=p；p↑.llink↑.rlink：=q；q↑.llink：=q；B．p↑.llink：=q；p↑.llink↑.rlink：=q；q↑.rlink：=p；q↑.llink:=p↑.llink；C．q↑.rlink：=p；q↑.llink：=p↑.llink；p↑.llink↑.rlink：=q;p↑.llink：=q;D．q↑.llink:=p↑.llink；q↑.rlink:=p；p↑.llink：=q；p↑.llink：=q；（编者按：原题如此）22．双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（dA.p＾.llink:=q;q＾.rlink:=p;p＾.llink＾.rlink:=q;q^.llink:=p^.llink;B.q＾.llink:=p^.llink;p＾.llink^.rlink:=q;q＾.rlink:=p;p^.llink:=q^.rlink;C.q^.rlink:=p;p^.rlink:=q;p^.llink^.rlink:=q;q^.rlink:=p;D.p^.llink^.rlink:=q;q^.rlink:=p;q^.llink:=p^.llink;p^.llink:=q;23．在双向链表指针p的结点前插入一个指针q的结点操作是（c）。【青岛大学2000五、2（2分）】A.p-Llink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q；B.p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink;C.q-Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=q;p-Llink=q;D.q-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q;14.已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：14．u=p-next;p-next=u-next;free(u);________16.在单链表L中，指针p所指结点有后继结点的条件是：_16．p-next!=null_24.已知双链表中结点的类型定义为：TYPEdpointer=^list;list=RECORDdata:integer;left,right:dpointer;END;如下过程将在双链表第i个结点（i=0）之后插入一个元素为x的结点，请在答案栏给出题目中___b___处应填入的语句或表达式，使之可以实现上述功能。PROCEDUREinsert(VARhead:dpointer;i,x:integer);VARs,p:dpointer;j:integer;BEGINnew(s);s^.data:=x;IF(i=0)THENBEGINs^.right:=head;(1)___head:=sEND{如果i=0,则将s结点插入到表头后返回}ELSEBEGINp:=head;(2)_______；{在双链表中查找第i个结点,由p所指向}WHILE((pNIL)AND(ji))DOBEGINj:=j+1;(3)_END;IFpNILTHENIF（p^.right=NIL）THENBEGINp^.right:=s;s^.right:=NIL;(4)__ENDELSEBEGINs^.right:=p^.right;(5)_;p^.right:=s;(6)ENDELSEwriteln(‘cannotfindnode!’)ENDEND;24.(1)head^.left:=s∥head的前驱指针指向插入结点(2)j:=1;(3)p:=p^.right∥工作指针后移(4)s^.left:=p(5)p^.right^.left:=s;∥p后继的前驱是s(6)s^.left:=p;第三章6.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（c）A.543612B.453126C.346521D.2341568.一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是（b）。A.23415B.54132C.23145D.1543225.假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（a）A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m27.循环队列存储在数组A[0..m]中，则入队时的操作为（d）。A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)2．___栈___是限定仅在表尾进行插入或删除操作的线性表19．设循环队列用数组A[1..M]表示，队首、队尾指针分别是FRONT和TAIL，判定队满的条件为___（TAIL+1）MODM=FRONT(数组下标0到M-1，若一定使用1到M，则取模为0者，值改取M____。20.设循环队列存放在向量sq.data[0:M]中，则队头指针sq.front在循环意义下的出队操作可表示为_______，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为_______。sq.front=(sq.front+1)%(M+1)；return(sq.data(sq.front))；(sq.rear+1)%(M+1)==sq.front；22．循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear，则