南京理工大学紫金学院《数据结构》试卷-高清数位重置新版

1、1 / 6、选择题1. 树最适合用来表示（）。A.有序数据C.元素之间具有分支层次关系的数据2. 一个堆是一棵（）二叉树。A.普通 B.排序 C.满3. 设哈夫曼树中的叶子结点总数为 m，有（）个空指针域。A. 2m-1B. 2mC. 2m+14. 线性结构的顺序存储结构是一种（A.随机存取B.顺序存取5. 一下是平衡二叉树的是（）。二分查找值为 22 的数据时要进行（）B. 无序数据元素D.元素之间无联系的数据D.完全若用二叉链表作为存储结构，则该哈夫曼树中共D. 4m）的存储结构。C. 索引存取D.散列存取2 / 6A. 2B. 3C. 4D. 58.设单链表中结点的结构为（data ,

2、next ）。已知指针 n 所指结点不是尾结点，若在指针 p 所指结点之后插入结点 s,则应执行下列哪一个操作？A. s-n ext=p; p-next=s;n ext=s;B. s-n ext=p-n ext;p-3 / 69. 由权值分别为 11. 8. 6. 2. 5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。A. 24 B. 71 C. 48 D. 5310. 无向图 G = ( V, E ) ，其中 V = a ，b，c，d，e，f ，E = (a, b) , (a, c) , (a, e) , (b,e) , (c, f) , (f, d) , (e, d) 。对该图进

3、行深度优先遍历，下面不能得到的序列是( )。A. acfdeb B. aebdfc C. aedfcb D. abecdf11. 设有广义表 D ( a, b, D ) ，其长度为( )，深度为( )。A.gB. 3C. 2D. 512. 线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采 用( )存储方式最节省运算时间。A. 单链表 B. 仅有头指针的单循环链表 C. 双链表 D. 仅有头指针的单循环链表13. 在有 n 个结点的二叉链表中，值为非空的链域的个数为( )。A. n-1 B. 2n-1 C. n+1D. 2n+114. 稀疏矩阵一般的压缩存储方法有两种，

4、即( )。A. 二维数组和三维数组 B. 三元组与散列 C. 三元组与十字链表 D. 散列和十字链 表15. 以下不是堆的序列是( )。A. 100, 85, 98, 77, 80, 60, 82, 40, 20, 10, 66B. 100, 98, 85, 82, 80, 77, 66, 60, 40, 20, 10C. 10, 20, 40, 60, 66, 77, 80, 82, 85, 98, 100D. 100, 85, 40, 77, 80, 60, 66, 98, 82, 10, 20C. s-next=D. p-next=s; s-next=p;4 / 616. 一个栈的入栈序

5、列是 a, b, c, d, e ，则栈的不可能输出序列是( )A. edcba B. decba C. dcead D. abcde二、填空题1. 下面程序段的时间复杂度是 _ 。_i = 1;While ( i = n )i = i * 5;2. 在一个单链表中，要删除某一个结点，必须找到该结点的 _ 结_ 点。3. 在一个长度为 n 的顺序表中，在第 1 个元素 ( 1 = i = n+1 )之前插入一个新元素时须向后移动 _ 个_元素。4. 有一个 10 阶对称矩阵 A，采用压缩存储方式(以行为主存储，且 LOC ( A00 ) = 1则 A85 的地址是 _。5. 设在一棵二叉树中，

6、度为 0 的结点个数为 8，度为 2 的结点个数为 _。6. 设二叉树结点的先根序列为 ABEDCFGH ，中根序列为 EDBAFCHG ，则二叉树中叶子结点是 _。_7. 求最小生成树算法有 Prim 算法和 Kruskal 算法两种， _ 算_ 法适合稠密图，_ 算_ 法适合稀疏图。8. 数据表中有 10000 个元素，如果仅要求求出其中最大的 10 个元素，则采用是 算法最节省时间5 / 69.循环队列中队满条件为:三、综合题1.画出广义表 LS = ( (), ( e ), ( a, ( b, c, d )的头尾链表存储结构2.已知一棵二叉树的先序序列与中序序列分别为：ABCDEFGH

7、I 和 BCAEDGHFI(1)给出该二叉树的后序遍历序列。(2)画出该二叉树的带头结点的中序线索二叉树(3)将该二叉树转换成森林。6 / 6（1）构造一棵二叉排序树（只需最后结果图）（2）画出构造的一棵平衡二叉树（只需最后结果图）。（3）HASH 表表长为 12，HASH 函数为 H （key ） = key%11 ，试用线性探测再散列解决冲突的方法构造哈希表。012345678910116.设待排序的关键字序列为 27,46, 5, 18, 16, 51,32, 26 ,分别使用以下排序方法进设有无向图 G,要求使用 Prim 算法构造以顶点 造最小生成树的每一步过程(无需注明权值)。3.C 为起点的最小生成树，同时, 写出构5.输入一个正整数序列 23, 32, 16, 14, 42, 71, 57, 28, 55, 19, 12, 50 7 / 6行排序，写出题目所给定趟数的结果。（1） 第三趟直接插入排序的结果。（2） 第一趟希尔排序的结果（增量为 3 ）。（3） 第二趟归并排序。（4） 第一趟快速排序。四、算法设计题有一个带头结点的单链表 head，其 ElemType 类型