B卷第1页/共9页一、单项选择题（每小题2分，共30分）1.下列关于栈的叙述中，正确的是（）。A．栈底元素一定是最后入栈的元素B．栈操作遵循先进后出的原则C．栈顶元素一定是最先入栈的元素D．以上三种说法都不对2.在数据结构中，与所使用的计算机硬件无关的是数据的（）结构。A．逻辑B．存储C．逻辑和存储D．物理3.以下说法正确的是（）。A．数据项是数据的基本单位B．数据元素是数据的最小单位C．数据结构是带结构的数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构4.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（）A．546132B．453126C．346512D．2341565.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（）A．8B．9C．10D．116.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（）A.（100,80,90,60,120,110,130）B.（100,120,110,130,80,60,90）C.（100,60,80,90,120,110,130）D.（100,80,60,90,120,130,110）7.下列陈述中正确的是（）A．二叉树是度为2的有序树B．二叉树中结点只有一个孩子时无左右之分C．二叉树中必有度为2的结点D．二叉树中最多只有两棵子树，并且有左右之分8.在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）A．eB．2eC．n2－eD．n2－2e9.栈和队列都是（）A．限制存取位置的线性结构B．顺序存储的线性结构C．链式存储的线性结构D．限制存取位置的非线性结构10.在具有n个叶子结点的严格二叉树（即结点的度要么是0要么是2）中，结点总数为（）A．2n+1B．2nC．2n-1D．2n-211.在循环双链表的p所指的结点之前插入s所指结点的操作是（）。A．p->prior=s；s->next=p；p->prior->next=s；s->prior=p->priorB．p->prior=s；p->prior->next=s；s->next=p；s->prior=p->priorB卷第2页/共9页C．s->next=p；s->prior=p->prior；p->prior=s；p->prior->next=sD．s->next=p；s->prior=p->prior；p->prior->next=s；p->prior=s12.单链表中，增加一个头结点的目的是为了（）。A．使单链表至少有一个结点B．标识表结点中首结点的位置C．方便算法的实现D．说明单链表是线性表的链式存储13.对一个满二叉树，m个叶子，n个结点，深度为h，则（）。A．n=h+mBh+m=2nCm=h-1Dn=2h-114.采用邻接表存储的图的广度优先遍历算法类似于二叉树的（）。A．先序遍历B．中序遍历C．后序遍历D．按层遍历15.n个结点的有向图，至少需要（）条有向边（弧）才能构成强连通图。A．2nB．nC．n(n-1)D．n-1二、判断题（在你认为正确的题后写上“对”;在你认为是错误的题后写上“错”并予以改正，但要符合原义,改动应少，每小题1分，共15分）1.对于一个线性表，采用顺序存储方式进行插入和删除结点时效率太低，采用链式存储方式更好。（）2.在顺序表中，最后一个元素有一个后继。（）3.使用双向链表可随机访问任一结点。（）4.在单链表中，给定任一结点的地址p，则可用下述语句将新结点s插入结点p的后面：p－＞next；（）5.完全二叉树不一定是平衡二叉树。（）6.堆排序是非稳定的排序算法。（）7.抽象数据类型与计算机内部表示和实现无关。（）8.顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。（）9.线性表采用链式存储结构时，结点和结点内部的存储空间可以是不连续的。（）10.对稀疏矩阵进行压缩存储的目的是便于输入和输出。（）11.起泡排序算法在最好情况下的时间复杂度为O（n）。（）12.串是一种特殊的线性表，其特殊性体现在数据元素可以是多个字符。（）13.空串和空白串是相同的。（）14.任意一棵二叉树中的度可以小于2。（）15.顺序查找法适合于存储结构为顺序存储或链式存储的线性表。（）三、填空题（每空1分，共15分）1.如果M有5个兄弟，而N是M的双亲，则N的度是(1)。B卷第3页/共9页2.如果二叉树中有20个叶子节点，30个度为1的结点，则该二叉树的总结点数为(2)。3.若用n表示图中的顶点数目，则有(3)条边的无向图被称为完全图。4.在二叉树的第i(i>=1)层上至多有(4)个结点。5.克鲁斯卡尔算法的时间复杂度是(5)，它适合求(6)图的最小生成树。6.高度为6的完全二叉树，其结...
