徐英数据结构期中考试.doc

班级 姓名 学籍号 考 考 生 答 题 不 得 超 过 此 密 封 线编号：QMSD/JWC-21-01数据结构期 中 试卷（ 2008 / 2009 学年度第 一 学期）用卷班级07计信2五班用卷人数39命 题 人徐英审核人王香菊核 对 人徐英 一、选择题（1*30=30）1、算法指的是（ ）。A、计算机程序B、解决问题的计算方法C、排序算法D、解决问题的有限运算序列2、数据的不可分割的基本单位是（ ）。A、元素B、结点C、数据类型D、数据项3、某线性表采用顺序存储结构，每个元素占4个存储单元，首地址为100，则第12个元素的存储地址为（ ）。A、144B、145C、147D、1484、设线性表L=（a1，a2，an），下列关于线性表的叙述正确的是（ ）。A、每个元素都有一个直接前驱和一个直接后继B、线性表中至少要有一个元素C、表中元素排列顺序必须按由小到大或由大到小D、除第一个和最后一个元素外，其余每个元素都有且只有一个直接前驱和一个直接后继5、对线性表，在下列情况下应当采用链表表示的是（ ）。A、经常需要随机地存取元素B、经常需要进行插入和删除操作C、表中元素需要占据一片连续的存储空间D、表中元素的个数不变D、顺序访问相邻结点更加灵活6、带头结点的双向循环链表L为空的条件是（ ）。A、L= =NULLB、Lnext= =NULLC、Lprior= =NULLD、Lnext= =L7、下面关于线性表的叙述错误的是（ ）。A、若用数组表示，表中诸元素的存储位置是连在一起的B、若用链表表示，便于插入和删除操作C、若用链表表示，不需要占用一片相邻的存储空间D、表的插入和删除操作仅允许在表的一端进行8、单链表的每个结点中包括一个指针link，它指向该结点的后继结点。现要将指针q指向的新结点插入到指针p指向的单链表结点之后，下面的操作序列中（ ）是正确的。A、q=plink；plink= qlink；B、plink= qlink；q=plink；C、qlink= plink；plink=q；D、plink= q；qlink= plink；9、线性表采用链式存储时，结点的存储地址（ ）。A、必须是不连续的B、连续与否均可C、必须是连续的D、和头结点的存储地址相连续10、在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是（ ）。A、p =pnext；B、pnext=pnextnext；C、pnext=p；D、p=pnextnext；11、若已知一个栈的进栈序列是1，2，3n，其输出序列是p1，p2，p3pn，若p1=3，则p2为（ ）。A、可能是2B、一定是2C、可能是1D、一定是112、设初始输入序列为1，2，3，4，5，利用一个栈产生输出序列，下列（ ）序列是不可能通过栈产生的。A、1，2，3，4，5B、5，3，4，1，2C、4，3，2，1，5D、3，4，5，2，113、设栈S的初始状态为空，6个元素入栈的顺序为e1，e2，e3，e4，e5和e6。若出栈的顺序是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是（ ）。A、6B、4C、3D、214、4个元素a1，a2，a3和a4依次入栈，入栈过程中允许栈顶元素出栈，假设某一时刻栈的状态是a3（栈顶），a2，a1（栈底），则不可能的出栈序列是（ ）。A、a4，a3，a2，a1B、a3，a2，a4，a1C、a3，a1，a4，a2D、a3，a4，a2，a115、向顺序栈中压入新元素时，应当（ ）。A、先移动栈顶指针，再存入元素B、先存入元素，再移动栈顶指针C、先后次序无关紧要D、同时进行16、栈和队列的共同点是（ ）。A、都是先进先出B、都是先进后出C、只允许在端点处插入和删除元素D、没有共同点17、下列关于线性表、栈和队列的叙述，错误的是（ ）。A、线性表是给定的n（n必须大于零）个元素组成的序列B、线性表允许在表的任何位置进行插入和删除操作C、栈只允许在一端进行插入和删除操作D、队列允许在一端进行插入在另一端进行删除18、设一个栈的输入序列为A，B，C，D，则借助一个栈所得到输出序列不可能是（ ）。A、A，B，C，DB、D，C，B，AC、A，C，D，BD、D，A，B，C19、从一个顺序队列中删除元素时，首先要（ ）。A、前移一位队首指针B、后移一位队首指针C、取出队首指针所指位置上的元素D、取出队尾指针所指位置上的元素20、下列有关树的概念错误的是（ ）。A、一棵树中只有一个无前驱的结点B、一棵树的度为树中各个结点的度数之和C、一棵树中，每个结点的度数之和等于结点总数减1D、一棵树中每个结点的度数之和与边的条数相等21、在一棵非空二叉树的中序遍历序列中，根结点的右边（ ）。A、只有右子树上的所有结点B、只有右子树上的部分结点C、只有左子树上的部分结点D、只有左子树上的所有结点22、下面关于二叉树的叙述正确的是（ ）。A、一棵二叉树中叶子结点的个数等于度为2的结点个数加1B、一棵二叉树中的结点个数大于0C、二叉树中任何一个结点要么是叶，要么恰有两个子女D、二叉树中任何一个结点的左子树和右子树上的结点个数一定相等23、已知某二叉树的后序遍历序列是DACBE，中序遍历序列是DEBAC，则它的前序遍历序列是（ ）。A、ACBEDB、DEABCC、DECABD、EDBCA24、如果一棵二叉树中所有结点的值都大于其左子树中所有结点的值，且小于其右子树中所有结点的值，现欲得到各个结点值的递增序列，采用的方法是（ ）。A、前序遍历B、后序遍历C、中序遍历D、层次遍历25、设二叉树根结点的层次为0，一棵树深为h的满二叉树中结点个数是（ ）。A、2hB、2h-1C、2h -1D、2h+1 -126、有关二叉树的下列说法正确的是（ ）。A、二叉树的度为2B、一棵二叉树的度可以小于2C、二叉树中任何一个结点的度都为2D、任何一棵二叉树中至少有一个结点的度为227、树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树，其中结论（ ）是正确的。A、树的先根遍历序列与其对应的二叉树的先序遍历序列相同B、树的后根遍历序列与其对应的二叉树的后序遍历序列相同C、树的先根遍历序列与其对应的二叉树的中序遍历序列相同D、以上都不对28、深度为5的二叉树至多有（ ）个结点。A、16B、32C、31D、1029、对一个满二叉树，m个树叶，n个结点，深度为h，则（ ）。A、n=h+mB、h+m=2nC、m=h-1D、n=2h-130、在下列存储形式中，（ ）不是树的存储形式。A、双亲表示法B、孩子链表表示法C、孩子兄弟表示法D、顺序存储表示法题号123456789101112131415答案题号161718192021222324252627282930答案二、填空题（1*25=25）1、数据的存储结构主要分为 和 两种。2、算法的5个重要特性是：输入、输出、可行性、确定性和 。3、算法的时间复杂度取决于 和特处理的数据的初态。4、线性表中 称为表的长度。5、在双向链表中，每个结点有两个指针域，一个指向 ，另一个指向 。6、在一个单链表中的p所指结点之前插入一个s所指的结点时，可以执行如下操作：（1）snext= ；（2）pnext= ；7、针对线性链表的基本操作有很多，但其中最基本的4种操作分别为 、删除、查找和排序。8、栈中元素的进出原则是 。9、队列中元素的进出原则是 。10、假设以S和X分别表示进栈和退栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为 。11、设栈S初始状态为空，队列Q的初始状态如下图所示。 a1a2a3a4队头 队尾对栈S和队列Q进行以下两步操作：（1）删除Q中的元素，将删除的元素插入S，直到Q为空；（2）依次将S中的元素插入Q，直到S为空。在上述两步操作后，队列Q的状态是 。12、有一棵树如图所示，请回答以下问题：k1k2k3k4k5k6k7（1）这根树的根结点是_；（2）这根树的叶子结点是_；（3）结点k3的度是_；（4）这根树的度是_；（5）这根树的深度是_；（6）结点k3的孩子结点是_；（7）结点k3的双亲结点是_；13、在一棵二叉树中，叶子结点的个数为n0，度为2的结点的个数为n2，则有n0=_。14、二叉树如图所示，回答下面问题。（1）其中序遍历序列为_。（2）其先序遍历序列为_。（3）其后序遍历序列为_。三、综合题（4+4+6+6+10+10+5=45）1、写出将循环链表A和循环链表B合并成一个循环链表A的主要操作语句。2、写出在双向链表中的P结点前插入一个S结点的主要操作语句。3、已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA。画