《数据结构》试卷----第1页共16页《数据结构导论》课程考核形式：闭卷考试需用时间：100分钟层次：专科班级：计应专朗沃姓名：学号：题号一二三四五六七八九十总分分值得分阅卷人日期一、选择题（本题共20分，每小题2分）。1．在数据结构中，与所使用的计算机无关的是（）。A.存储结构B.物理结构C.物理和存储结构D.逻辑结构2．线性表采用链式存储结构时，其地址是（）。A.必须是连续的B.一定是不连续的C.部分地址必须是连续的D.连续与否均可以3．在下列链表中不能从当前结点出发访问到其余各结点的是（）。A.单链表B.单循环链表C.双向链表D.双向循环链表4．设一个栈的进栈序列是a，b，c，d，进栈的过程中可以出栈，不可能的出栈序列是（）A.d，c，b，aB.c，d，b，aC.d，c，a，bD.a，b，c，d5．设循环队列中数组的下标是0～N-1，其头尾指针分别为f和r，则其元素个数为（）A.r-fB.r-f-1C.(r-f)%N+1D.(r-f+N)%N6．广义表((a),a)的表头和表尾分别是：A.a,((a))B.(a),(a)C.b,(a)D.((a)),a7．对稀疏矩阵采用压缩存储，其缺点之一是（）。A.无法判断矩阵有多少行和多少列B.无法根据行列号查找某个矩阵元素C.无法根据行列号计算矩阵元素的存储地址D.使矩阵元素之间的逻辑关系更加复杂8．以下说法错误的是（）。A.一般在哈夫曼树中，权值越大的叶子离根结点越近B.哈夫曼树中没有度数为1的分支结点C.若初始森林中共有n棵二叉树，最终求得的哈夫曼树中共有2n-1个结点D.若初始森林中共有n棵二叉树，进行2n-1次合并后才能剩下最终的哈夫曼树9．任何一个无向连通图（）最小生成树。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在《数据结构》试卷----第2页共16页10．树最适合用来表示（）：A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据二、填空题（本大题共9小题，每空2分，共20分）1．在双向链表中，每个结点包含两个指针域，一个指向____结点，另一个指向____结点。2.只允许在表的一端进行插入，而在另一端进行删除元素操作的线性表称为。3.设数组a[1,60,1,70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为4.一个n×n的对称矩阵，如果以行或列为主序放入内存，则容量为。5.n个顶点的有向图G最多有条弧。6.某棵树的的结点A有3兄弟，而且结点B是A的双亲，则结点B的度是。7.n个结点的二叉树，最大高度是。8.克鲁斯卡尔(Kruskal)算法适用于求的网的最小生成树。9.在一个无向图中，所有顶点的度数之和等于所有边数的_________倍。三、判断题（在正确的说法后面打√，反之打×，每题1分，共计10分）1.算法分析的目的是分析算法的效率以求改进。()2.在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。（）3.线性表在物理存储空间中也一定是连续的。（）4.线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。（）5.栈和队列是一种非线性数据结构。（）6.一个栈的输入序列是12345，则栈的输出序列不可能是12345。（）7.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i-1个结点。（）8.数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。()9.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n-1个非空指针域。（）10.存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。()四、应用题（本题共50分，每小题10分）1、已知一棵二叉树的顺序存储结构如下图1所示。1234567891011121314ABFCGJDEHIK图1.某二叉树的顺序存储结构（1）画出此棵二叉树。(4分)《数据结构》试卷----第3页共16页（2）写出该二叉树的先根遍历和后根遍历的序列。(6分)2、设无向图有6个结点，依次输入的9条边为(1,2)，(1,3)，(1,5)，(1,6)，(2,3)，(3,4)，(3,5)，(4,5)，(5,6)。（1）画出无向图G。(4分)（2）画出G的邻接表(6分)3、假设通信电文使用的字符集为{a,b,c,d,e,f,g},字符的哈夫曼编码依次为:0110，10，110，111，00，0111和010。（1）请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应字符。（2）若...
