计算机水平考试-程序员分类模拟题数据结构与算法(二)

《计算机水平考试-程序员分类模拟题数据结构与算法(二)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、程序员分类模拟题数据结构与算法(-)综合知识试题K若二维数组arr[1..8,1..6]的首地址为base,数组元索按列存储，且每个元索占用4个存储单元，则元素arr[5,5]在该数组空间的地址为。A.bas巳+(4*8+4)*4B・base+(5*8+5)*4C.base+(4*6+4)*4D.base+(5*6+5)*42、设线性表(59,53,46,48,37,31,25)采用散列(Hash)法进行存储和查找，散列函数为H(Key)=KeyMOD7(MOD表示整除取余运算)。若用链地址法解决冲突(即将相互冲突

2、的元索存储在同一个单链表中)构造散列表，则散列表中与哈希地址对应的单链表最长。A.2B・3C・4D・63、设递增序列A为円，屯，・・・，an,递增序列B为b】，b?,・・・，b..,且m>n,则将这两个序列合并为一个长度为m+n的递增序列时，当时，归并过程中元素的比较次数最少。A・an>bmB.an

3、为n的有序表进行二分(折半)查找时，无论查找指定的一个元素是否成功，最多只与表屮的个元素进行比较即可。A.[log2n]-1B.[log2n]+1C・n/2D・n-l7、输入受限的双端队列是指只有一端可以进行入队操作而从两端都可以进行出队操作的队列，如图1-23所示。对于输入序列1234,经过一个初始为空且输入受限的双端队列后，不能得到的输出序列为出队、出肌受限的双删列A.1234B.4321C・1243D・42138、对于具有n个元素的关键字序列（K,£,・・・，K）,当且仅当满足关系Ki$K且半bk2i+1L2

4、」时称为大根堆。据此可以断定不是大根堆。A.59,53,48,46,37,31,25B・59,46,53,48,37,31,25C・59,37,53,25,31,46,48D.59,53,48,31,25,46,37案例分析试题试题一阅读以下说明和C函数，回答问题1和问题2,将解答填入答题纸的对应栏内。[说明]对于具有n个元素的整型数组a,需耍进行的处理是删除a中所有的值为0的数组元素，并将a中所冇的非0元素按照原顺序连续地存储在数组空间的前端。下而分别用函数丄和CompactArr_v2来实现上述处理要求，函数的

5、返冋值为非零元素的个数。函数CompactArr_vl(inta[],intn)的处理思路是：先申请一个与数组a的大小相同的动态数组空间，然后顺序扫描数组4的每一个元索，将遇到的非0元索依次复制到动态数组空间中，最后再将动态数组中的元素传回数组a中。函数CompactArr_v2(inta[],intn)的处理思路是：利用下标i(初值为0)顺序扫描数组応的毎一个元素，下标k]初值为0)表示数组応中连续存储的非0元素的下标。扫描时，每遇到一个数组元素，i就增1,而遇到非0元素并将其前移后k才增1。[程序丄-4]int

6、CompactArr_vl(inta[],intn)inti,k；int*temp=(int*)malloc(n*_9_if(!temp)return-1；for(i=0,k=0;i

7、ompactArr_vl的处理思路填补空缺(丄)~(3),根据CompactArr_2的处理思路填补空缺(4)。--10>请说明两数CompactArr_vl存在的缺点。试题二阅读以下说明和c函数，填补C函数中的空缺(1)~(5),将解答写在答题纸的对应栏内。[说明]假设一个算术表达式中可以包含以下三种括号：和'')〃、''[〃和'']〃、''{〃和''}〃，并且这三种括号可以按照任意的次序欧套使用。下而仅考虑表达式中括号的匹配关系，其他问题暂时忽略。例如，表达式''[a.(b.5)]*c[{}]zz中的描号是完全

8、匹配的，而表达式''[a-(b-5]))2〃中的括号不是完全匹配的，因为''(〃与'']〃不能匹配，而且多了一个'')〃，即缺少一个与'')〃相匹配的、'(〃。函数ifMatched(charexpr[])的功能是用栈來判断表达式中的括号是否匹配，表达式以字符吊的形式存储在字符数组expr中。若表达式中的括号完全匹配，贝U该函数的返回值为Matched,否则