数据结构B试题及答案

一、单项选择题（2分×10=20分）1．若某线性表中最常用的操作是提取第i个元素及找第i个元素的前驱元素，则采用（D）存储方式最省时间。A.单链表B.双链表C.单向循环链表D.顺序表2．将含有100个结点的完全二叉树从根开始自上向下，每层从左到右依次编号，且设根结点的编号为1，则编号69的结点的双亲的编号为（A）。A.34B.35C.33D.无法确定3.单循环链表的主要优点是（D）。A.不再需要头指针了B.已知某结点的位置后，很容易找到其前驱C.在进行插入、删除运算时，能更好地保证链表不断开D.从表中任一结点出发都能扫描到整个链表4.在长为n的顺序表中，向第i个元素(1≤i≤n+1)前插入一个元素需要向后移动（B）个元素。A.n-iB.n-i+1C.n-i-1D.i5.一个栈的入栈顺序是1、2、3、4、5，则此栈不可能的输出顺序为（C）。A.5、4、3、2、1C.4、3、5、1、2B.4、5、3、2、1D.1、2、3、4、56.串是一种特殊的线性表，其特殊性表现在（B）。A.可以顺序存储C可以链式存储B.数据元素是一个字符D.数据元素是多个字符7.一棵5层满二叉树中，结点总数为（C）个。A.338.下列4棵二叉树，（B）是平衡树。B.32C.31D.30A.B.C.D.9.n个顶点的无向图中最多有（A）条边。A.n(n-1)/2B.n(n-1)C.n(n+1)D.n(n+1)/210.6个顶点的无向图中，至少有（A）条边才能保证是一个连通图。A.5B.6C.7D.8二、判断题（1分×10=10分）（F）1.线性结构的基本特征是：每个结点有且仅有一个直接前驱和一个直接后继。（F）2.二叉树是树的特殊情形。（T）3.存在这样的二叉树，其先序遍历与中序遍历得到的访问序列相同。（F）4.用一维数组存储二叉树时，总是以先序遍历的顺序存储结点。（F）5.空串就是由空格组成的串。（F）6.在AOE网中，一定只有一条关键路径。（T）7.m阶B-树每一个结点的子树个数都小于或等于m.（T）8.插入排序是稳定的。（T）9.顺序存储的线性表可以实现随机存取。（F）10.二叉树按某种顺序线索化后，任一结点均有指向其直接前驱和直接后继的线索。三、填空题（2分×8=16分）1．在单链表中，若要在指针p所指结点后插入指针s所指结点，则需要执行下列两条语句：s->next=p->next；p->next=s；2.在有头结点的单链表L中，指针p所指结点是第一个结点的条件是p=L->next。3.栈是一种受限制的线性表，也叫LIFO结构，LIFO的含义是后进先出。4.对于队，只能在删除元素。队尾插入元素，只能在队头5.抽象数据类型ADT可以用三元组（D，S，P）表示，它们分别表示：数据对象、数据关系和基本操作。四、简答和应用题（38分）1.（8分）某二叉树先序遍历的结果是ABCDEFG，中序遍历的结果是CBDAFGE.（1）（2）A画出此二叉树；写出其后先序遍历的结果。BECDFG(5分)CDBGFEA(3分)2.（9分）已知如图所示有向图，（1）（2）（3）求各点的入度和出度；给出该图的邻接矩阵；给出该图的邻接表。(1)1:0,32:2,13:3,04:1,15:1,2(3)01→1→3→4^12→2^23^34→2^45→1→2^(2)0101100100000000010001100(各3分)3.给出下面稀疏矩阵的三元组。（5分）5行6列:(1,2,12),(2,1,9),(4,1,-1),(4,5,10),(5