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

1、B. 无序数据元素D.元素之间无联系的数据D.完全假设用二叉链表作为存储结构，那么该哈夫曼树中共D. 4m的存储结构。C. 索引存取D.散列存取、选择题1. 树最适合用来表示。A. 有序数据C.元素之间具有分支层次关系的数据2. 一个堆是一棵二叉树。A.普通 B.排序 C.满3. 设哈夫曼树中的叶子结点总数为 m， 有个空指针域。A. 2m-1B. 2mC. 2m+14. 线性结构的顺序存储结构是一种A.随机存取B.顺序存取5. 一下是平衡二叉树的是。来实现算法D.图6. 对图进行广度优先遍历时，通常采用A.栈B.队列 C.树7. 有一个有序表为 8，15，20，22，32，41，45，62，

2、75，77, 82，85，97 ，当 二分查找值为22的数据时要进行次比拟。A. 2B. 3C. 4D. 58. 设单链表中结点的结构为 ( data , next ) 。指针 n 所指结点不是尾结点，假设在指 针p所指结点之后插入结点S,那么应执行以下哪一个操作？A. s->next=p; p->next=s;B. s->next=p->next; p->next=S;C. S->next=p->next; p=S;D. p->next=S; S->next=p;9. 由权值分别为 11. 8. 6. 2. 5 的叶子结点生成一棵哈夫曼树

3、,它的带权路径长度为( )。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) 。对该图进行深度优先遍历,下面不能得到的序列是( )。A. acfdeb B. aebdfc C. aedfcb D. abecdf11. 设有广义表 D ( a, b, D ) ,其长度为( ),深度为( )。A. gB. 3C. 2D. 512. 线性表中最常用的操作是在最后一个元素之后插入一个

4、元素和删除第一个元素,那么采 用( )存储方式最节省运算时间。A. 单链表 B. 仅有头指针的单循环链表 C. 双链表 D. 仅有头指针的单循环链表13. 在有 n 个结点的二叉链表中,值为非空的链域的个数为( )。A. n-1 B. 2n-1 C. n+1D. 2n+114. 稀疏矩阵一般的压缩存储方法有两种,即( )。A. 二维数组和三维数组 B. 三元组与散列 C. 三元组与十字链表 D. 散列和十字链 表15. 以下不是堆的序列是( )。A. 100, 85, 98, 77, 80, 60, 82, 40, 20, 10, 66B. 100, 98, 85, 82, 80, 77, 6

5、6, 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, 2016. 一个栈的入栈序列是 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 的顺序表中，在第

6、 1 个元素 ( 1 <= i <= n+1 ) 之前插入一个新元素 时须向后移动 个_元素。4. 有一个10阶对称矩阵A，采用压缩存储方式(以行为主存储，且 LOC ( A00)=1，那么 A85 的地址是。5. 设在一棵二叉树中，度为 0 的结点个数为 8，度为 2 的结点个数为 。6. 设二叉树结点的先根序列为 ABEDCFGH，中根序列为EDBAFCHG，那么二叉树中叶子结点是。7. 求最小生成树算法有Prim算法和Kruskal算法两种，算法适合稠密图，算法适合稀疏图。8. 数据表中有10000个元素，如果仅要求求出其中最大的 10个元素，那么采用是算法最节省时间。9.

7、循环队列中队满条件为： 。三、综合题1. 画出广义表LS = ( (), ( e ), ( a, ( b, c, d ) 的头尾链表存储结构。2. 一棵二叉树的先序序列与中序序列分别为：ABCDEFGHI和BCAEDGHFI(1) 给出该二叉树的后序遍历序列。(2) 画出该二叉树的带头结点的中序线索二叉树。(3) 将该二叉树转换成森林。3. 设有无向图G,要求使用Prim算法构造以顶点C为起点的最小生成树，同时，写出构 造最小生成树的每一步过程(无需注明权值)。4. 根据以下图所示的AOE网，请答复以下问题:1求这个工程最早可能在什么时间结束；2求每个活动的最早开始时间和最迟开始时间;3确定哪

8、些活动是关键活动。活动<v0, v1><v0, v2><v1,v3><v2,v3><v2,v5><v3, v4><v3, v5><v4, v5>最早发生时间最迟发生时间5. 输入一个正整数序列 23, 32, 16, 14, 42, 71, 57, 28, 55, 19, 12, 50 1构造一棵二叉排序树只需最后结果图。2画出构造的一棵平衡二叉树只需最后结果图。3HASH表表长为12，HASH函数为H key = key%11 ，试用线性探测再散列解决冲突的方法构造哈希表。012345678910116. 设待排序的关键字序列为 27, 46, 5, 18, 16, 51,32, 26 ,分别使用以下排序方法进行排序，写出题目所给定趟数的结果。1第三趟直接插入排序的结果。 2第一趟希尔排序的结果增量为 3。3第二趟归并排序。4第一趟快速排序。四、算法设计题个算法使其元素递有一个带头结点的单链