1、软件水平考试中级软件设计师下午应用技术（数据结构）模拟试卷 1及答案与解析 一、必答题（共 4道大题，每道大题 15分） 0 阅读下列说明和 C代码，回答问题 1至问题 3，将解答写在答题纸的对应栏内。 【说明】 堆数据结构定义如下。 对于 n个元素的关键字序列 a1， a2 ， an，当且仅当满足下列关系时称其为堆：在一个堆中，若堆项元素为最大元素，则称为大顶堆；若堆顶元素为最小元素，则称为小项堆。堆常用完全二叉树表示，图 8 11是一个大顶堆的例子。 堆数据结构常用于优先队列中，以维护由一组元素构成的集合。对 应于两类堆结构，优先队列也有最大优先队列和最小优先队列，其中最大优先队列采用大顶
2、堆，最小优先队列采用小顶堆。以下考虑最大优先队列。 假设现已建好大项堆 A，且已经实现了调整堆的函数 heapify(A， n， index)。 下面将 C代码中需要完善的 3个函数说明如下。 (1)heapMaximum(A)：返回大顶堆 A中的最大元素。 (2)heapExtractMax(A)：去掉并返回大顶堆 A的最大元素，将最后一个元素 “提前 ”到堆顶位置，并将剩余元素调整成大顶堆。 (3)maxHeapInsert(A， key)：把元 素key插入到大顶堆 A的最后位置，再将 A调整成大顶堆。优先队列采用顺序存储方式，其存储结构定义如下： #define PARENT(i)i
3、2typedef struct array int *int_array；优先队列的存储空间首地址 int array_size；优先队列的长度 int capacity；优先队列存储空间的容量 ARRAY；【 C代码】 (1)函数heapMaximum int heapMaximum(ARRAY*A)return_(1)； (2)函数heapExtractMaxint heapExtractMax(ARRAY *A) int max； max=A- int array0； _(2); A- array size-； Heapify(A， A- array size， 0);将剩余元素调整成大
4、顶堆 return max； (3)函数 maxHeapInsertint maxHeapInsert(ARRAY*A， int key)int i， *p； if(A- array-size=A- capacity)存储空间的容量不够时扩充空间 p=(int*)realloc(A- int array， A- capacity*2*sizeof(int); if(!p)return-1； A-int_array=p； A- capacity=2*A- capacity； A- array_size+： I=_(3); while(i 0 return 0； 1 根据以上说明和 C代 码，填充
5、 C代码中的空 (1) (5)。 2 根据以上 C代码，函数 heapMaximum， heapExtractMax和 maxHeaplnsert的时间复杂度的紧致上界分别为 _(6)、 _(7)和 _(8)(用 O符号表示 )。 3 若将元素 10插入到堆 A=(15， 13， 9， 5， 12， 8， 7， 4， 0， 6， 2， 1)中，调用maxHeapInsert函数进行操作，则新插入的元素在堆 A中第 _(9)个位置 (从 1开始 )。 软件水平考试中级软件设计师下午应用技术（数据结构）模拟试卷 1答案与解析 一、必答题（共 4道大题，每道大题 15分） 【知识模块】 数据结构 1
6、 【正确答案】 (1)A- int_array0 (2)A- int_array0=A- inc_arrayA- array_size-1 (3)A- array_size-1 (4)key A- int_arrayPARENT(i) (5)A- int_atrayi=key 【试题解析】 heapMaximum(A)函数返回大顶堆 A中的最大元素。大项堆 A的优先队列采用顺序存储方式，指针 int array指向优先队列的存储空间首地址，其内容为大项堆 A中的最大元素，因此空 (1)处应填入 A- int_array0。 heapExtractMax(A)的功能是去掉并返回大顶堆 A的最大元
7、素，将最后一个元素“提前 ”到堆项位置，并将剩余元素调整成大顶堆。可知空 (2)处所填的语句应该是将最后一个元素的值存储在原最大元素所在的位置，即存储空间的首地址。 maxHeapInsert(A， key)的功能是把元素 key插入大顶堆 A的最后位 置，再将 A调整成大项堆。在将 A调整成大顶堆的过程中需要用到上滤策略。maxHeaplnsert(A， key)函数中，首先用 i指示元素 key的位置，则 i=array_size-1；然后将 im_arrayi与其父节点进行比较，如果大于其父节点的值，将两者的位置进行交换， key的位置 i=PARENT(i)；往上比较，直至 key的值
8、不大于其父节点的值。 【知识模块】 数据结构 2 【正确答案】 (6)O(1) (7)O(log2n) (8)O(log2n) 【试题解析】 heapMaximum(A)函 数不需要进行比较，直接输出存储空间首地址中的内容，时间复杂度的紧致上界为 O(1)。 heapExtractMax(A)函数将最后一个元素 “提前 ”到堆顶位置，并将剩余元素调整成大顶堆。在最坏的情况下，需要从根节点下滤比较到最底层，时间复杂度的紧致上界为 O(log2n)。 maxHeapInsert(A， key)函数把元素 key插入大项堆 A的最后位置，再将 A调整成大顶堆。在最坏的情况下，需要从最底层上滤比较到根节点，时间复杂度的紧致上界为 O(log2n)。 【知识模块】 数据结构 3 【正确答案】 (9)3 【试题解析】 调用 maxHeapInsert函数进行排序的过程如图 8 12所示。可见，元素 10在堆 A中第 3个位置。 【知识模块】 数据结构
