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

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

2、41,45,62,75,77,82,85,97，当）次比较。、选择题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

3、.无向图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.8B.3C.2D.512 .线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用()存储方式最节省运算时间。A.单链表B.仅有头指针的单循环链表C.双链表D.仅有头指针的单循环链表13 .在有n个结点的二叉链表中，值为非空的链域的个数为()。A.n-1

4、B.2n-1C.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,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.edcbaB.decbaC.dceadD.abc

5、de二、填空题1 .下面程序段的时间复杂度是二1 =1;While(i<=n)i=i*5;2 .在一个单链表中，要删除某一个结点，必须找到该结点的结点。3 .在一个长度为n的顺序表中，在第1个元素(1<=i<=n+1)之前插入一个新元素时须向后移动仝元素。4 .有一个10阶对称矩阵A,采用压缩存储方式(以行为主存储，且LOC(A00)=1则A85的地址是o5 .设在一棵二叉树中，度为0的结点个数为8,度为2的结点个数为o6 .设二叉树结点的先根序列为ABEDCFGH,中根序列为EDBAFCHG,则二叉树中叶子结点是二7 .求最小生成树算法有Prim算法和Kruskal算法两种

6、，法适合稠密图，算法适合稀疏图。8 .数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用是算法最节省时间。9 .循环队列中队满条件为：三、综合题1 .画出广义表LS=(),(e),(a,(b,c,d)的头尾链表存储结构。2 .已知一棵二叉树的先序序列与中序序列分别为：ABCDEFGHI和BCAEDGHFI(1)给出该二叉树的后序遍历序列。(2)画出该二叉树的带头结点的中序线索二叉树。(3)将该二叉树转换成森林。3 .设有无向图G,要求使用Prim算法构造以顶点C为起点的最小生成树，同时，写出构造最小生成树的每一步过程(无需注明权值)。第3题图第4题图4 .根据下图所示的AO

7、E网，请回答以下问题:(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)o(3)第二趟归并排序。(4)第一趟快速排序。四、算法设计题有一个带头结点的单链表head,其