自学考试-数据结构自考题模拟12

《自学考试-数据结构自考题模拟12》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构自考题模拟12一、单项选择题K当初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为()A・r?B・n・]_onanC・log2nD.n-12、长度为12的按关键字有序的查找表采用顺序组织方式。若采用二分查找方法，则在等概率情况下,查找失败时的ASL值是()A.37/12B.62/13C.39/12D.49/133、对广义表((a),(b))进行下面的操作head(head((a),(b)))后的结果是()A・aB・(a)C.()D.不确定4、顺序存储结构()A・仅适合于静态查找表的存储B.仅适合干动态查找表的

2、存储C.既适合静态乂适合动态查找表的存储D.既不适合静态又不适合动态查找表的存储5、将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的结点的双亲结点编号为()A.42B.40C・21D・206、非空的单循环链表L的尾结点Pt,满足()A・Pt.next=NULL；B・P=NULL；C・Pt・next=L；D.P=L7、对长度为n的关键字序列进行堆排序的空间复杂度为()A・OdognB.0(1)C・O(n)D・O(n*log2n)8、堆排序的最坏时间复杂度为()A.O(n

3、)B・OCLOg：!!)C・omiog?!!)D.O(n2)9、在线性表的下列运算中，不改变数据元素Z间结构关系的运算是()A.插入B.删除C.排序D.定位10、深度为k的二叉树，所含叶子的个数最多为()A.2KB・KC・2K-1D・2K-111＞对关键字序列(6,1,4,3,7,2,8,5)进行快速排序时，以第1个元素为基准的一次划分的结果为()A.(5,1,4,3,6,2,8,7)B.(5,1,4,3,2,6,7,8)C.(5,1Z4Z3Z2Z6,8Z7)D.(8,7,6,5z4,3,2,1))条边。C・N(N+1)D.N(N+

4、1)/212、一个具有N个顶点的有向图最多有(A.N(N-l)/2B.N(N-l)丄3、通常要求同一逻辑结构中的所冇数据元素具冇相同的特性，这意味着（）A.数拯元素具有同一特点B.不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C.每个数据元索都一样D.数据元素所包含的数据项的个数耍相等14、采用分治法进行排序的方法是（）A.快速排序B.插入排序C・堆排序D.希尔排序15、下列说法中正确的是（）A.二叉树中任何一个结点的度都为2B.二叉树的度为2C.任何一棵二叉树中至少有一个结点的度为2D.一棵二叉树的度可以小于2

5、二.填空题丄6、一个字符串相等的充耍条件是和o17.当所有结点的权值都相等时，用这些结点构造的二叉排序树上只右。18、假设散列文件中一个桶能存放m个记录，则桶''溢出〃的含义是，当需要插入新的记录时，该桶中19、数组的长度是,线性表的长度是。20、对表长为9000的索引顺序表进行分块查找，假设每一块的长度均为15,且以顺序查找确定块，则在各记录的查找概率均相等的情况下，其查找成功的平均查找长度为o21、多维数组和广义表是一种非常复杂的非线性结构，它们的逻辑特点是o22、假设以列优先顺序存储二维数组A[5][8],其中元索A[0][0

6、]的存储地址为LOC（a00）,冃•每个元素占4个存储单元，则数组元素A[i][j]的存储地址为。23、一棵含999个结点的完全二叉树的深度为o24、控制区间和控制区域是文件的逻辑存储单位。25、对于数组，通常具有的基木操作有种，它们分别是o三、解答题26、对于下面用三元组表示的稀疏矩阵，请分别写出它们所对应的稀疏矩阵。57604—'p10610一佃324543355402314-112140127、图的邻接表的类型定义如下所示：#defineMaxVertexNum50typedefstructnode{intadjvex；str

7、uctnode*next；}EdgeNode；typedefstruct{VertexTypevertex；EdgeNode*firstedge；}VertexNode；typedefVertexNodeAdjList[MaxVertexNum]；typedefstruct{AdjListadjiist;O-RTHTFIintn,e；}ALGraph；为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如下图所示，请写出重新定义的类型说明。28、假设有一个长度为n的有序序列，在进行查找时，可以借

8、助二叉树来进行，请结合二叉树的性质来分析二分查找的最坏性能和平均性能。29、某类物品的编号由一个大写英文字母及2位数字（0...9）组成，形如E32。运用基数排序对下列物詁编号序列进行按字典序的排序，写出每一趟（分配和收集）后的结果。