大学专业试卷数据结构试卷下(B).doc

数据结构期末考试试卷（B）一大题 单选题（每小题2分 ，共30分）1下列叙述中中正确的是（ ）A一个逻辑数据结构只能有一种存储结构 B数据的逻辑结构属于线性结构，存储结构属于非线性结构 C一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率 D一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率2.某带头结点的单链表的头指针为head，判定该链表为非空的条件是( )A.head=NULLB.head-next=NULLC.head!=NULLD.head-next!=NULL3.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（）A3，2，6，1，4，5 B3，4，2，1，6，5C1，2，5，3，4，6 D5，6，4，2，3，14设树T的度为4，其中度为1,2,3，和4的结点个数分别为4,2,1,1，则，T中的叶子数为（ ）A6 B.7 C.8 D.55. 栈和队列的共同点是（ ）A. 都是先进先出 B.都是先进后出 C.只允许在端点处插入和删除元素 D.没有共同点6.假设一棵完全二叉树按层次遍历的顺序依次存放在数组BTm中，其中根结点存放在BT0，若BTi中的结点有左孩子，则左孩子存放在( )A.BTi/2B.BT2*i-1C.BT2*i D.BT2*i+17.连通图是指图中任两个顶点之间( )A.都连通的无向图B.都不连通的无向图 C.都连通的有向图D.都不连通的有向图8. 二维数组A89按行优先顺序存储，若数组元素A23的存储地址为1087，A47的存储地址为1153，则数组元素A67的存储地址为（）A1207 B1209 C1211 D12139若用邻接矩阵表示一个有向图，则其中每一列包含的1的个数为（）A图中每个顶点的入度 B图中每个顶点的出度C图中弧的条数D图中连通分量的数目10. 如图所示的4棵二叉树中，（ ）不是完全二叉树。 A. B. C. D.11. 在一是个具有n个顶点的有向图中，若具有e条边，则所有顶点的度数之和为（ ） A. n B. e C. n+e D. 2e12.以下数据结构中，（ ）是非线性数据结构A树 B字符串 C队 D栈13.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。Ap-next=s; s-next=p-next; B s-next=p-next; p-next=s;Cp-next=s； p-next=s-next; D p-next=s-next; p-next=s;14. 若串S=“software”,其子串的数目是（ ）。A8 B37 C36 D915. 假定一棵三叉树的结点数为50，规定根结点的层次从0开始，则它的最小深度为（ ）。 A3 B.4 C. 5 D.6二大题 填空题（每空1分，共10分）1.对于给定的n个元素,可以构造出的逻辑结构有 （1） ， （2） ， （3） 。2. 在双向链表中，每个结点含有两个指针域，一个指向 （4） 结点，另一个指向 （5） 结点。3. 队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是 （6） 。4. 循环队列的引入，目的是为了克服 （7） 。5.设一棵完全二叉树共有699个结点，则在该二叉树中的叶子节点数为（），度为的结点个数为（）。6. 深度为k的完全二叉树至多有 （） 个结点。(注:空树的深度为-1)三大题应用题（每小题10分，共0分）1已知二叉树的先序序列和中序序列分别为HDACBGFE和ADCBHFEG。（1）画出该二叉树；（5分）（2）写出该二叉树的后序遍历和层次遍历。（5分）2若字母A,B,C,D,E,F给定一组权值5，9，11，2，7，16，试设计相应的哈夫曼树和字母相应的哈夫编码。3 画出该图的邻接矩阵存储结构图,并按照邻接矩阵存储结构给出每个结点的邻接结点次序，给出该有向图的深度优先遍历的结点访问序列。ADFCEB108122593020225将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果）NPGHJMOLIKEDFBAC四大题程序设计题（每小题10分，共分）. 设头指针为head,并设带头结点的单链表中的数据元素递增有序，编写算法将 后数据元素X插入到带头结点单链表的合适位置上，要求插入后保持单链表数据元素的递增有序。2. 在二叉树的链式存储结构下设计算法：求一棵二叉树的结点总数。2