东华大学数据结构期末复习题

第1章绪论一、选择题1.算法的计算量的大小称为计算的（）。A．效率B.复杂性C.现实性D.难度2.算法的时间复杂度取决于（）A．问题的规模B.待处理数据的初态C.A和B3.计算机算法指的是（1），它必须具备（2）这三个特性。(1)A．计算方法B.排序方法C.解决问题的步骤序列D.调度方法(2)A．可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性4.一个算法应该是（）。A．程序B．问题求解步骤的描述C．数据结构+程序D．以上都不对.5.下面关于算法说法错误的是（）A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性D.以上几个都是错误的6.下面说法错误的是（）(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指随问题规模的增大，算法执行时间的增长率。（4）空间复杂度是算法所需存储空间的量度。A．(1)B.(1),(2)C.(1),(4)D.(3)7.从逻辑上可以把数据结构分为（）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构8.以下与数据的存储结构无关的术语是（）。A．循环队列B.链表C.哈希表D.栈9.连续存储设计时，存储单元的地址（）。A．一定连续B．一定不连续C．不一定连续D．部分连续，部分不连续10.以下属于逻辑结构的是（）。A．顺序表B.哈希表C.有序表D.单链表第2章线性表一、选择题1.下述哪一条是顺序存储结构的优点？（）A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示2.下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。3.线性表是具有n个（）的有限序列（n0）。A．表元素B．字符C．数据元素D．数据项E．信息项4.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表5.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表6.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用()最节省时间。A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表7.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（）存储方式最节省运算时间。A．单链表B．双链表C．单循环链表D．带头结点的双循环链表8.链表不具有的特点是（）A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比9.下面的叙述不正确的是（）A．线性表在链式存储时，查找第i个元素的时间同i的值成正比B.线性表在链式存储时，查找第i个元素的时间同i的值无关C.线性表在顺序存储时，查找第i个元素的时间同i的值成正比D.线性表在顺序存储时，查找第i个元素的时间同i的值无关10.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1=i=n+1)。A.O(0)B.O(1)C.O(n)D.O(n2)11.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。A．O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)12.线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）A．O（i）B．O（1）C．O（n）D．O（i-1）13.非空的循环单链表head的尾结点p满足（）。A．p.next=headB．p.next=NULLC．p=NULLD．p=head14.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。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;15.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）A．head==NULLB．head-next==NULLC．head-next==headD．head!=NULL二、综合应用题1.已知线性表（a1a2a3…an）按顺序存于内存，每个元素都是整数，试设计用最少时间把所有值为负数的元素移到全部正数值元素前边的算法：例：（x,-x,-x,x,x,-x…x）变为（-x,-x,-x…x,x,x）。2.设单链表的表头指针为h，结点结构由data和next两个域构成，其中data域为字符型。写出算法dc(h,n),判断该链表的前n个字符是否中心对称。例如xyx,xyyx都是中心对称。3.已知非空线性链表由list指出，链结点的构造为（data,link）.请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。4.试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。voiddelete（Linklist&L）5.设有一头指针为L的带有表头结点的非循环双向链表，其每个结点中除有pred（前驱指针），data（数据）和next（后继指针）域外，还有一个访问频度域freq。在链表被起用前，其值均初始化为零。每当在链表中进行一次Locate(L,x)运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L,x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。6.已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为0(n)、空间复杂度为0(1)的算法，该算法删除线性表中所有值为item的数据元素。（O（1）表示算法的辅助空间为常量）。第3章栈和队列一、选择题1.对于栈操作数据的原则是（）。A.先进先出B.后进先出C.后进后出D.不分顺序2.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（）。A.不确定B.n-i+1C.iD.n-i3.若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。A.i-j-1B.i-jC.j-i+1D.不确定的4.一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是（）。A.23415B.54132C.23145D.154325.输入序列为ABC，可以变为CBA时，经过的栈操作为（）A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop6.若一个栈以向量V[1..n]存储，栈为空时栈顶指针top为n+1，则下面x进栈的正确操作是()。A．top:=top+1;V[top]:=xB.V[top]:=x;top:=top+1C.top:=top-1;V[top]:=xD.V[top]:=x;top:=top-17.栈在（）中应用。A.递归调用B.子程序调用C.表达式求值D.A，Ｂ，Ｃ8.一个递归算法必须包括（）。A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分9.用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时()。A．仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都要修改D.队头,队尾指针都可能要修改10.递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。A．队列B．多维数组C．栈D.线性表11.假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（）。A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m12.循环队列存储在数组A[0..m]中，则入队时的操作为（）。A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)13.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？()A.1和5B.2和4C.4和2D.5和114.栈的特点是（①）,队列的特点是（②）,栈和队列都是（③）。若进栈序列为1,2,3,4则（④）不可能是一个出栈序列（不一定全部进栈后再出栈）；若进队列的序列为1,2,3,4则（⑤）是一个出队列序列。①,②:A.先进先出B.后进先出C.进优于出D.出优于进③:A.顺序存储的线性结构B.链式存储的线性结构C.限制存取点的线性结构D.限制存取点的非线性结构④,⑤:A.3,2,1,4B.3,2,4,1C.4,2,3,1D.4,3,2,1F.1,2,3,4G.1,3,2,415.栈和队列的共同点是（）。A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点16.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是()。A．6B.4C.3D.217.用单链表表示的链式队列的队头在链表的（）位置。A．链头B．链尾C．链中二、综合应用题1.有5个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？2.设从键盘输入一整数的序列：a1,a2,a3，…，an,试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（栈空等）给出相应的信息。3.设表达式以字符形式已存入数组E[n]中，‘#’为表达式的结束符，试写出判断表达式中括号（‘（’和‘）’）是否配对的C语言描述算法;(注：算法中可调用栈操作的基本算法。)第4章树和二叉树一、选择题1.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（）A．5B．6C．7D．82.在下述结论中，正确的是（）①只有一个结点的二叉树的度为0;②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A．①②③B．②③④C．②④D．①④3.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）A．m-nB．m-n-1C．n+1D．条件不足，无法确定4.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9B．11C．15D．不确定5.设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。A．M1B．M1+M2C．M3D．M2+M36.具有10个叶结点的二叉树中有（）个度为2的结点，A．8B．9C．10D．ll7.若一棵二叉树有126个节点，在第7层（根节点在第1层）至多有（）个