练习题1-6章(含答案)

1习题练习第一章1.算法的计算量的大小称为计算的（B）。A．效率B.复杂性C.现实性D.难度2.算法的时间复杂度取决于（c）A．问题的规模B.待处理数据的初态C.A和B3.计算机算法指的是（1c），它必须具备（2b）这三个特性。(1)A．计算方法B.排序方法C.解决问题的步骤序列D.调度方法(2)A．可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性4．一个算法应该是（b）。A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C.5、下面属于逻辑结构的是（c）A顺序表B哈希表C有序表D单链表6、某算法的时间复杂度为O(n2)，表明该算法的（c）A问题规模是n2B执行时间等于n2C执行时间与n2成正比D问题规模与n2成正比7、下面关于算法说法错误的是（c）A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性D.以上几个都是错误的8．从逻辑上可以把数据结构分为（c）两大类。A．动态结构、静态结构B．顺序结构、链式结构2C．线性结构、非线性结构D．初等结构、构造型结构9．以下与数据的存储结构无关的术语是（d）。A．循环队列B.链表C.哈希表D.栈10．以下数据结构中，哪一个是线性结构（d）？A．广义表B.二叉树C.稀疏矩阵D.串11．以下那一个术语与数据的存储结构无关？（a）A．栈B.哈希表C.线索树D.双向链表12．在下面的程序段中，对x的赋值语句的频度为（c）FORi:=1TOnDOFORj:=1TOnDOx:=x+1;A．O(2n)B．O(n)C．O(n2)D．O(log2n)14．以下数据结构中，（a）是非线性数据结构A．树B．字符串C．队D．栈15.下列数据中，（c）是非线性数据结构。A．栈B.队列C.完全二叉树D.堆16．连续存储设计时，存储单元的地址（a）。A．一定连续B．一定不连续C．不一定连续D．部分连续，部分不连续17．以下属于逻辑结构的是（c）。A．顺序表B.哈希表C.有序表D.单链表二、问答：1.数据结构是一门研究什么内容的学科？2.数据元素之间的关系在计算机中有几种表示方法？各有什么特点？3.数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类型的主3要特点是什么？使用抽象数据类型的主要好处是什么？4.回答问题（1）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？（2）若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗？举例说明之。（3）在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说法对吗？举例说明之。5．评价一个好的算法，您是从哪几方面来考虑的？第二章1．下述哪一条是顺序存储结构的优点？（a）A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示2．下面关于线性表的叙述中，错误的是哪一个？（b）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。3．线性表是具有n个（c）的有限序列（n0）。A．表元素B．字符C．数据元素D．数据项E．信息项4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，4则利用（a）存储方式最节省时间。A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（d）存储方式最节省运算时间。A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表6．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（d）存储方式最节省运算时间。A．单链表B．双链表C．单循环链表D．带头结点的双循环链表7.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（c）(1=i=n+1)。A.O(0)B.O(1)C.O(n)D.O(n2)8.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（c）。A．O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)9．线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（c）A．O（i）B．O（1）C．O（n）D．O（i-1）16．非空的循环单链表head的尾结点p↑满足（a）。A．p↑.link=headB．p↑.link=NILC．p=NILD．p=head17．循环链表H的尾结点P的特点是（a）。A．P^.NEXT:=HB．P^.NEXT:=H^.NEXTC．P:=HD．P:=H^.NEXT18．在一个以h为头的单循环链中，p指针指向链尾的条件是（a）A.p＾.next=hB.p＾.next=NILC.p＾.next.＾next=hD.p＾.data=-119．在双向链表指针p的结点前插入一个指针q的结点操作是（c）。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;5C.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;20．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（b）。A．p-next=s;s-next=p-next;B．s-next=p-next;p-next=s;C．p-next=s;p-next=s-next;D．p-next=s-next;p-next=s;25．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（b）A．head==NULLB．head→next==NULLC．head→next==headD．head!=NULL二、算法设计：1.插入算法，在带有头结点的单链表La中第i个元素之前插入e。2.删除算法，删除带有头结点的单链表La中第i个元素3.将两个有序的带有头结点单链表Ｌａ和Ｌｂ进行合并成一个有序的单链表Ｌｃ算法4.将链表Ｌａ进行逆置等操作。5.已知非空线性链表由list指出，链结点的构造为（data,link）.请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。6.(6)有一个单链表L（至少有1个结点），其头结点指针为head，编写一个过程将L逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。7.在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如：（7，10，10，21，30，42，42，42，51，70）将变作（7，10，21，30，42，51，70），分析算法的时间复杂度。第三章1.对于栈操作数据的原则是（b）。A.先进先出B.后进先出C.后进后出D.不分顺序2.在作进栈运算时,应先判别栈是否(①b),在作退栈运算时应先判别栈是否(②a)。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③b)。6为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的(④d)分别设在这片内存空间的两端,这样,当(⑤c)时，才产生上溢。①,②:A.空B.满C.上溢D.下溢③:A.n-1B.nC.n+1D.n/2④:A.长度B.深度C.栈顶D.栈底⑤:A.两个栈的栈顶同时到达栈空间的中心点.B.其中一个栈的栈顶到达栈空间的中心点.C.两个栈的栈顶在栈空间的某一位置相遇.D.两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.3.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（b）。A.不确定B.n-i+1C.iD.n-i4.若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（d）。i-j+1A.i-j-1B.i-jC.j-i+1D.不确定的5.若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是(d)。A.iB.n-iC.n-i+1D.不确定6.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（c）A.543612B.453126C.346521D.2341568.一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是（b）。A.23415B.54132C.23145D.1543213.输入序列为ABC，可以变为CBA时，经过的栈操作为（b）【中山大学1999一、8(1分)】7A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop14.若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是(b)。A．top:=top+1;V[top]:=xB.V[top]:=x;top:=top+1C.top:=top-1;V[top]:=xD.V[top]:=x;top:=top-115.若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈(i=1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（b）。A.|top[2]-top[1]|=0B.top[1]+1=top[2]C.top[1]+top[2]=mD.top[1]=top[2]16.栈在（d）中应用。【中山大学1998二、3（2分）】A.递归调用B.子程序调用C.表达式求值D.A，Ｂ，Ｃ17.一个递归算法必须包括（b）。A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分19.表达式a*(b+c)-d的后缀表达式是(b)。A．abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd21.设计一个判别表达式中左，右括号是否配对出现的算法，采用（d）数据结构最佳。A．线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈22.用链接方式存储的队列，在进行删除运算时（d）。【A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针8可能都要修改23.用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时(d)。A．仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都要修改D.队头,队尾指针都可能要修改24.递归过程或函数调用时，处理参数及返回地址，要用一种称为（c）的数据结构。A．队列B．多维数组C．栈D.线性表25.假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（a）。A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m26.循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是(a)。A.(rear-front+m)%mB.rear-front+1C.rear-front-1D.rear-front27.循环队列存储在数组A[0..m]中，则入队时的操作为（d）。A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)mod