《2016年深圳大学计算机与软件学院FS30专业基础知识综合之数据结构(软件工程专业型)复试笔试最后押题五套卷.doc》由会员分享，可在线阅读，更多相关《2016年深圳大学计算机与软件学院FS30专业基础知识综合之数据结构(软件工程专业型)复试笔试最后押题五套卷.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2016年深圳大学计算机与软件学院FS30专业基础知识综合之数据结构(软件工程专业型)复试笔试最后押题五套卷一、选择题1 设n 是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。 答:A【解析】其中，以基本的原操作重复执行的次数作为算法的时间度量。题目中的基本运算是，则有语句设其执行时间为T （n ） 2 下列指令中，不能在用户态执行的是（ ）A.trap 指令B. 跳转指令C. 后栈指令D. 关中断指令答:D【解析】关中断指令必须在和心态才能执行，trap 指令可以在用户态下执行，执行了就转到和心态，跳转与退栈指令都是可以在用户态下执行的指令。 3 若数据元素序列11, 12, 1
2、3, 7, 8, 9, 23, 4, 5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（ ）。A. 起泡排序B. 插入排序C. 选择排序D. 二路归并排序答:B【解析】经过两趟排序后，A 项起泡排序的结果是两个最小或最大的元素放到了序列的最终位置；B 项插入排序的结果是前三个数有序即可；C 项选择排序结果是两个最小的元素在最前面按顺序排好；D 项二路归并排序的结果是长度为4的子序列有序，即前4个数排好序，接下来的4个数排好序。显然题目中的元素序列只能是插入排序第二趟排序后的结果，因此，B 项正确。 第 2 页，共 43 页4 某数采用IEEE754单精度浮点数格式表示为C6
3、40 0000H, 则该数的值是（ ） A. B. C. D.答:AIEEE754单精度浮点数格式为C640 0000H表示为二进制格式为1100 0110 0100 0000 【解析】0000 0000 0000 0000, 转换为标准的格式为： . 因此，浮点数的值为 5 若串其子串的数目是（ ）。A.8B.37C.36D.9答:B【解析】子串的定义是：串中任意个连续的字符组成的子序列，并规定空串是任意串的子串，任意串是其自身的子串。若字符串长度为长为为：故选B 。 6 已知循环队列存储在一维数组rear 的值分别是（ ）。A.0, 0B.0, n-1C.n-1, 0D.n-1, n-1答
4、:B【解析】题目要求队列非空时front 和rear 分别指向队头元素和队尾元素，若初始时队列为空，且要求第1 个进入队列的元素存储在A0处，则此时front 和rear 的值都为0。由于进队操作要执行（rear+1） % n，则初始 时front 的值为0、rear 的值为n-1。 7 对于循环队列（ ）。A. 无法判断队列是否为空B. 无法判断队列是否为满C. 队列不可能满D. 以上说法都不是第 3 页，共 43 页 长为n 的子串有1个，长为的子串有2个，的子串有3个，长为1的子串有n 个。由于空串是任何串的子串，所以本题的答案中，且队列非空时front 和rear 分别指向队头元素和队
5、尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A0处，则初始时front 和答:D【解析】循环队列也会出现队列满的情况，并且循环队列也可以判断是否为空或满。至少可以通过两种方法进行判断：另设一个布尔变量来区别队列是空还是满；队满时，（rear+1）=font。 8 假定有k 个关键字互为同义词，若用线性探测法把这k 个关键字存入哈希表中，至少要进行多少次探测？（ ） 答:D【解析】至少探测次数 9 已知序列25, 13, 10, 12, 9是大根堆，在序列尾部插入新元素18, 将其再调整为大根堆，调整过程 中元素之间进行的比较次数是（ ）。A.1B.2C.4D.5答:B【解析】对堆插入或删除一个元素，有可能不满足堆的性质，堆被破坏，需要调整为新堆。 （1）为原堆，（2）为插入18后，（3）比较10与18，交换后，（4）比较25与18, 不交换，即为调整后的新的大根堆。因此调整过程中元素之间进行的比较次数为2。 10已知关键字序列5, 8, 12, 19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（ ）。A.3, 5，12，8, 28，20, 15，22，19第 4 页，共 43 页一、选择题考研试题
