数据结构导论资料.docVIP

《数据结构导论》课程 考核形式：闭卷 考试需用时间：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，a B.c，d，b，a C.d，c，a，b D.a，b，c，d 5．设循环队列中数组的下标是0～N-1，其头尾指针分别为f 和r ，则其元素个数为（ ） A. r-f B.r-f-1 C.(r-f)%N+1 D.(r-f+N)%N 6．广义表((a),a)的表头和表尾分别是： A. a, ((a)) B. (a), (a) C. b, (a) D. ((a)), a 7．对稀疏矩阵采用压缩存储，其缺点之一是（ ）。 A.无法判断矩阵有多少行和多少列 B.无法根据行列号查找某个矩阵元素 C.无法根据行列号计算矩阵元素的存储地址 D.使矩阵元素之间的逻辑关系更加复杂 8．以下说法错误的是（ ）。 A.一般在哈夫曼树中，权值越大的叶子离根结点越近 B.哈夫曼树中没有度数为 1 的分支结点 C.若初始森林中共有 n 棵二叉树，最终求得的哈夫曼树中共有 2n-1个结点 D.若初始森林中共有 n 棵二叉树，进行 2n-1 次合并后才能剩下最终的哈夫曼树 9．任何一个无向连通图（ ）最小生成树。 A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在 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、已知