数据结构A卷3答案.docVIP

系别 系别 班级 姓名 学号 密封线 《 数据结构 》试卷（A）卷 第 1 页，共 2 页 兰州交通大学博文学院2014-2015学年第二学期 《数据结构》期末考试试卷（A卷）考核形式（闭卷） 题号 一 二 三 四 五 总分 评卷人 得分 第一题、选择题（每小题2分，共30分） 注：本试卷作答时间为120分，满分为100分 得分 用链接方式存储的队列，在进行插入运算时（A） A. 仅修改头指针 　 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 2.深度为k的二叉树至多有多少个结点（C） A. B. 2k-1 C.-1 D. k 以下数据结构中哪一个是非线性结构？(D) A. 队列 　　 B. 栈 C. 线性表 　　 D. 二叉树 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。C A．688 B．678 C．692 D．696 树最适合用来表示( C )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（D）。 (A) 20 (B) 30 (C) 40 (D) 45 7. 下面关于线性表的叙述错误的是（D）。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现 8. 设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（B ）个空指针域。 (A) 2m-1 (B) 2m (C) 2m+1 (D) 4m 9. 设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={01，02，01，03，01，04，02，05，02，06，03，07，03，08，03，09}，则数据结构A是（ B ）。 (A) 线性结构 (B) 树型结构 (C) 物理结构 (D) 图型结构 10. 设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（ B ）。 (A) s-next=p-next；p-next=-s； (B) q-next=s； s-next=p； (C) p-next=s-next；s-next=p； (D) p-next=s；s-next=q； 11.数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（ C ）。 (A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n2) 12. .设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（B）个结点。 (A) 2n (B) n+l (C) 2n-1 (D) 2n+l 13.无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（D ）。 (A) n (B) e (C) 2n (D) 2e 14. 设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（C）。 (A) N0=N1+1 (B) N0=Nl+N2 (C) N0=N2+1 (D) N0=2N1+l 15. 数据的最小单位是（ A ）。 (A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量 第二题、填空题（每空2分，共20分） 得分 通常从四个方面评价算法的质量：_正确性_、_可读性_、_健壮性_和_通用性_。 一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为__O(n)__。 假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为___9___个，树的深度为____3_______，树的度为____3_____。 若用链表存储一棵二叉树