资源描述：
《南京理工大学紫金学院《数据结构》试卷_高清数位重置版.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、--..--一、选择题1.树最适合用来表示（）。A.有序数据B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据2.一个堆是一棵（）二叉树。A.普通B.排序C.满D.完全3.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中共有（）个空指针域。A.2m-1B.2mC.2m+1D.4m4.线性结构的顺序存储结构是一种（）的存储结构。A.随机存取B.顺序存取C.索引存取D.散列存取5.一下是平衡二叉树的是（）。A.B.C.D.6.对图进行广度优先遍历时，通常采用（）来实现算法。A.栈B.队列C.树D.图7.有一个有序表为{8，15，20，22，
2、32，41，45，62，75，77，82，85，97}，当二分查找值为22的数据时要进行（）次比较。word可编辑.--..--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的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。A.24B.71C.48
3、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.acfdebB.aebdfcC.aedfcbD.abecdf11.设有广义表D(a,b,D)，其长度为（），深度为（）。A.∞B.3C.2D.512.线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。A.单链表B.仅有头指针的单循环链表C.双链表D.仅有头指针的单循环链表13.在有n个结点的二叉链表中，值为非空的链域
4、的个数为（）。A.n-1B.2n-1C.n+1D.2n+114.稀疏矩阵一般的压缩存储方法有两种，即（）。A.二维数组和三维数组B.三元组与散列C.三元组与十字链表D.散列和十字链表word可编辑.--..--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,2016.一个栈的入栈序列是a,b,c,d,e，则栈的不可能输出序列是（）
5、A.edcbaB.decbaC.dceadD.abcde二、填空题1.下面程序段的时间复杂度是____________。i=1;While(i<=n)i=i*5;2.在一个单链表中，要删除某一个结点，必须找到该结点的________结点。3.在一个长度为n的顺序表中，在第1个元素(1<=i<=n+1)之前插入一个新元素时须向后移动____________个元素。4.有一个10阶对称矩阵A，采用压缩存储方式（以行为主存储，且LOC(A[0][0])=1，则A[8][5]的地址是______。5.设在一棵二叉树中，度为0的结点个数为8，度为2的结点个数为______。6.设二叉树结点的先
6、根序列为ABEDCFGH，中根序列为EDBAFCHG，则二叉树中叶子结点是____________。word可编辑.--..--7.求最小生成树算法有Prim算法和Kruskal算法两种，________算法适合稠密图，________算法适合稀疏图。8.数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用____________是算法最节省时间。9.循环队列中队满条件为：_____________________________。三、综合题1.画出广义表LS=((),(e),(a,(b,c,d)))的头尾链表存储结构。2.已知一棵二叉树的先序序列与中序序列分别为：
7、ABCDEFGHI和BCAEDGHFI（1）给出该二叉树的后序遍历序列。（2）画出该二叉树的带头结点的中序线索二叉树。（3）将该二叉树转换成森林。3.设有无向图G，要求使用Prim算法构造以顶点C为起点的最小生成树，同时，写出构造最小生成树的每一步过程（无需注明权值）。DCAB155566423EF6第3题图V5V4V1V0V2V3第4题图6748910320word可编辑.--..--4.根据下图所示的AOE网，请回答以下问题：（1）求这个工程最早可能在
