数据结构试卷.docx

密封线内不要答题数据结构大题号三四五总分得分评卷人得分一、单项选择题（每题3分共30分）1具有4个顶点的无向完全图含有的边数是（）。A.10B.12C.6D.202深度为5的二叉树至多有（）个结点A.31B.32C.16D.103. 数据结构通常有四类基本结构，不包含在基本结构内的是（）A.集合B.树形结构C.图状结构D.块结构4. 6个结点的无向连通图，最多的边数是（）A.5B.15C.7D.65. 一个栈的入栈序列是1234,则栈的不可能的输出序列是（）A.4321B.3421C.4312D.12346.某二叉树的后序遍历序列是dabc,中序序列是dbac,它的前序序列是（）oA.acbdB.dcabC.dabcD.cdba7 .某高度为h的二叉树只有度为。和2的结点，此二叉树的结点数至少为（）。A.2hB.2h-1C.2h+1D.h+18 .有n个叶子的哈夫曼树的结点总数为（）。A,不确定B.2nC.2n+1D.2n-19 .带头结点的单链表head为空的判定条件是（）A.head->next=headB.head=NU11C.head->next=NU11D.head!=NU1110.向量地址是200,每个元素长为2,第5个元素的地址是（）A.210B,220C.200D.208二、填空题（每题3分共30分）1直接插入排序的方法中，当需要将第一个数据插入时，此时前i-1个数据是的。2 .在一个无向图中，所有顶点的度数之和等于所有边数的一倍。3 .n个顶点的连通图至少有一条边。4 .二维数组AIO2O采用列序为主方式存储，每个元素占一个存储单元，并且A的存储地址是200,则A6I2的地址是o5 .二维数组A10采用行序为主方式存储，每个元素占4个存储单元.并且A00的存储地址是1000,则A的地址是o6 .10阶对称方阵A采用压缩存储方式，以行序为主存储，A00=1,则A8的地址是07 .二叉树度为零的结点数n,度为2的结点数为n2,则有n二。8 .在无向图G的邻接矩阵A中，若Aij等于1,则Aji等于o9 .在排序前，关键字值相等的不同记录，排序前后其相对位置的排序方法称为稳定的。10 .采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为一o三、简答题（每题8分共40分）1算法必须具有哪5个特性，并叙述。2 .线性表的顺序存储结构和链式存储结构各有什么优缺点？3 .已知权值W=5,6,2,9,8,试构造赫夫曼树，并求WP145 .求如图所示的有向无环图的拓扑排序序列。67 .依次用序列（17,18,60,40,7,32性成二叉排序树。