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

...wd......wd......wd...一、选择题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，32，41，45，62，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的叶子结点生成一棵哈夫曼树，它的带权路径长度为〔〕。A.24B.71C.48D.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.∞ B.3 C.2 D.512.线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用〔〕存储方式最节省运算时间。A.单链表B.仅有头指针的单循环链表C.双链表D.仅有头指针的单循环链表13.在有n个结点的二叉链表中，值为非空的链域的个数为〔〕。A.n-1 B.2n-1 C.n+1 D.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,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，则栈的不可能输出序列是〔〕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(A[0][0])=1，则A[8][5]的地址是______。5.设在一棵二叉树中，度为0的结点个数为8，度为2的结点个数为______。6.设二叉树结点的先根序列为ABEDCFGH，中根序列为EDBAFCHG，则二叉树中叶子结点是____________。7.求最小生成树算法有Prim算法和Kruskal算法两种，________算法适合稠密图，________算法适合稀疏图。8.数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用____________是算法最节省时间。9.循环队列中队满条件为：_____________________________。三、综合题1.画出广义表LS=((),(e),(a,(b,c,d)))的头尾链表存储构造。2.一棵二叉树的先序序列与中序序列分别为：ABCDEFGHI和BCAEDGHFI〔1〕给出该二叉树的后序遍历序列。〔2〕画出该二叉树的带头结点的中序线索二叉树。〔3〕将该二叉树转换成森林。3.设有无向图G，要求使用Prim算法构造以顶点C为起点的最小生成树，同时，写出构造最小生成树的每一步过程〔无需注明权值〕。DDCAB155566423EF6第3题图V5V4V1V0V2V3第4题图67489103204.根据以以以下图所示的AOE网，请答复以下问题：〔1〕求这个工程最早可能在什么时间完毕；〔2〕求每个活动的最早开场时间和最迟开场时间；〔3〕确定哪些活动是关键活动。活动<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〕画出构造的一棵平衡二叉树〔只需最后结果图〕。〔3〕HASH表表长为12，HASH函数为H(key)=key%11，试用线性探测再散列解决冲突的方法构造哈希表。012345678910116.设待排序的关键字序列为{27,46,5,18,16,51,32,26},分别使用以下排序方法进展排序，写出题目所给定趟数的结果。〔1〕第三趟直接插入排序的结果。〔2〕第一趟希尔排序的结果〔增量为3〕。〔3〕第二趟归并排序。〔4〕第一趟快速排序。四、算法设计题有一个带