徐英数据结构期中考试

1、编号： qmsd/jwc-21-01信息工程系数据结构期末试卷第 1 页 共 4 页班级姓名学籍号考考生答题不得超过此密封线数据结构期中 试卷（ 2008 / 2009 学年度第一 学期）用卷班级07 计信 2 五班用卷人数39 命 题 人徐英审核人王香菊核 对 人徐英一、选择题（1*30=30 ）1、算法指的是（） 。a、计算机程序b、解决问题的计算方法c、排序算法d、解决问题的有限运算序列2、数据的不可分割的基本单位是（） 。a、元素b、结点c、数据类型d、数据项3、某线性表采用顺序存储结构，每个元素占4 个存储单元，首地址为100，则第 12 个元素的存储地址为（） 。a、144 b、1

2、45 c、147 d、148 4、设线性表l=（a1，a2， an） ，下列关于线性表的叙述正确的是（） 。a、每个元素都有一个直接前驱和一个直接后继b、线性表中至少要有一个元素c、表中元素排列顺序必须按由小到大或由大到小d、除第一个和最后一个元素外，其余每个元素都有且只有一个直接前驱和一个直接后继5、对线性表，在下列情况下应当采用链表表示的是（） 。a、经常需要随机地存取元素b、经常需要进行插入和删除操作c、表中元素需要占据一片连续的存储空间d、表中元素的个数不变d、顺序访问相邻结点更加灵活6、带头结点的双向循环链表l 为空的条件是（） 。a、l= =null b、lnext= =null

3、c、l prior= =null d、lnext= =l 7、下面关于线性表的叙述错误的是（） 。a、若用数组表示，表中诸元素的存储位置是连在一起的b、若用链表表示，便于插入和删除操作c、若用链表表示，不需要占用一片相邻的存储空间d、表的插入和删除操作仅允许在表的一端进行8、单链表的每个结点中包括一个指针link ，它指向该结点的后继结点。现要将指针q 指向的新结点插入到指针p 指向的单链表结点之后，下面的操作序列中（）是正确的。a、q=plink ；plink= q link ；b、plink= q link ；q=plink ；c、qlink= p link ；plink=q ；d、pli

4、nk= q ；qlink= p link ；9、线性表采用链式存储时，结点的存储地址（） 。a、必须是不连续的b、连续与否均可c、必须是连续的d、和头结点的存储地址相连续10、在单链表中，指针p 指向元素为x 的结点，实现“删除x 的后继”的语句是（） 。a、p =pnext ；b、pnext =pnext next ；c、pnext=p；d、 p=p next next ；11、 若已知一个栈的进栈序列是1， 2， 3 n， 其输出序列是p1， p2， p3pn， 若 p1=3， 则 p2 为 （） 。a、可能是2 b、一定是 2 c、可能是 1 d、一定是1 12、设初始输入序列为1，2，

5、3，4，5，利用一个栈产生输出序列，下列（）序列是不可能通过栈产生的。a、1，2，3，4，5 b、5，3， 4，1，2 c、4，3， 2，1，5 d、3，4，5，2，1 13、设栈s 的初始状态为空，6 个元素入栈的顺序为e1，e2，e3，e4，e5 和 e6。若出栈的顺序是e2，e4， e3，e6，e5，e1，则栈 s 的容量至少应该是（） 。a、6 b、4 c、3 d、2 14、 4 个元素a1，a2，a3 和 a4 依次入栈，入栈过程中允许栈顶元素出栈，假设某一时刻栈的状态是 a3（栈顶），a2，a1（栈底），则不可能的出栈序列是（） 。a、a4，a3，a2，a1 b、a3，a2， a4

6、，a1 c、a3，a1， a4，a2 d、a3，a4，a2，a1 15、向顺序栈中压入新元素时，应当（） 。a、先移动栈顶指针，再存入元素b、先存入元素，再移动栈顶指针c、先后次序无关紧要d、同时进行16、栈和队列的共同点是（） 。a、都是先进先出b、都是先进后出c、只允许在端点处插入和删除元素d、没有共同点17、下列关于线性表、栈和队列的叙述，错误的是（） 。a、线性表是给定的n（n 必须大于零）个元素组成的序列b、线性表允许在表的任何位置进行插入和删除操作c、栈只允许在一端进行插入和删除操作d、队列允许在一端进行插入在另一端进行删除18、设一个栈的输入序列为a，b，c，d，则借助一个栈所得

7、到输出序列不可能是（） 。a、a，b，c，d b、d，c，b，a 编号： qmsd/jwc-21-01信息工程系数据结构期末试卷第 2 页 共 4 页班级姓名学籍号考考生答题不得超过此密封线c、a，c， d， b d、d，a，b，c 19、从一个顺序队列中删除元素时，首先要（） 。a、前移一位队首指针b、后移一位队首指针c、取出队首指针所指位置上的元素d、取出队尾指针所指位置上的元素20、下列有关树的概念错误的是（） 。a、一棵树中只有一个无前驱的结点b、一棵树的度为树中各个结点的度数之和c、一棵树中，每个结点的度数之和等于结点总数减1 d、一棵树中每个结点的度数之和与边的条数相等21、在一棵

8、非空二叉树的中序遍历序列中，根结点的右边（） 。a、只有右子树上的所有结点b、只有右子树上的部分结点c、只有左子树上的部分结点d、只有左子树上的所有结点22、下面关于二叉树的叙述正确的是（） 。a、一棵二叉树中叶子结点的个数等于度为2 的结点个数加1 b、一棵二叉树中的结点个数大于0 c、二叉树中任何一个结点要么是叶，要么恰有两个子女d、二叉树中任何一个结点的左子树和右子树上的结点个数一定相等23、已知某二叉树的后序遍历序列是dacbe ，中序遍历序列是debac ，则它的前序遍历序列是（） 。a、acbed b、deabc c、decab d、edbca 24、如果一棵二叉树中所有结点的值都

9、大于其左子树中所有结点的值，且小于其右子树中所有结点的值，现欲得到各个结点值的递增序列，采用的方法是（） 。a、前序遍历b、后序遍历c、中序遍历d、层次遍历25、设二叉树根结点的层次为0，一棵树深为h 的满二叉树中结点个数是（） 。a、2hb、2h-1 c、 2h-1 d、2h+1- 1 26、有关二叉树的下列说法正确的是（） 。a、二叉树的度为2 b、一棵二叉树的度可以小于2 c、二叉树中任何一个结点的度都为2 d、任何一棵二叉树中至少有一个结点的度为2 27、树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫

10、做这棵树对应的二叉树，其中结论（）是正确的。a、树的先根遍历序列与其对应的二叉树的先序遍历序列相同b、树的后根遍历序列与其对应的二叉树的后序遍历序列相同c、树的先根遍历序列与其对应的二叉树的中序遍历序列相同d、以上都不对28、深度为5 的二叉树至多有（）个结点。a、16 b、 32 c、31 d、 10 29、对一个满二叉树，m 个树叶， n 个结点，深度为h，则（） 。a、n=h+m b、 h+m=2n c、m=h- 1 d、 n=2h-1 30、在下列存储形式中， （）不是树的存储形式。a、双亲表示法b、孩子链表表示法c、孩子兄弟表示法d、顺序存储表示法题号1 2 3 4 5 6 7 8

11、9 10 11 12 13 14 15 答案题号16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 答案二、填空题（1*25=25 ）1、数据的存储结构主要分为和两种。2、算法的5 个重要特性是：输入、输出、可行性、确定性和。3、算法的时间复杂度取决于和特处理的数据的初态。4、线性表中称为表的长度。5、在双向链表中，每个结点有两个指针域，一个指向，另一个指向。6、在一个单链表中的p 所指结点之前插入一个s 所指的结点时，可以执行如下操作：（1）s next= ；（2）pnext= ；7、针对线性链表的基本操作有很多，但其中最基本的4 种操作分别为、删除、查

12、找和排序。8、栈中元素的进出原则是。9、队列中元素的进出原则是。10、假设以s 和 x 分别表示进栈和退栈操作，则对输入序列a，b，c，d，e 进行一系列栈操作ssxsxssxxx之后，得到的输出序列为。11、设栈 s 初始状态为空，队列q 的初始状态如下图所示。a1 a2 a3 a4 编号： qmsd/jwc-21-01信息工程系数据结构期末试卷第 3 页 共 4 页班级姓名学籍号考考生答题不得超过此密封线队头队尾对栈 s和队列 q 进行以下两步操作：（1）删除 q 中的元素，将删除的元素插入s，直到 q 为空；（2）依次将s中的元素插入q，直到 s为空。在上述两步操作后，队列q 的状态是。

13、12、有一棵树如图所示，请回答以下问题：（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 。画出这棵二叉树并给出前序序列。4、. 设给定权值w=8 ， 4，5，3，1， 1,试构造一棵哈夫曼树,并求其带权路径长度wpl 。5、对于图中所给