2016年武汉大学测绘遥感信息工程国家重点实验室数据结构复试笔试最后押题五套卷
● 摘要
目录
2016年武汉大学测绘遥感信息工程国家重点实验室数据结构复试笔试最后押题五套卷（一） . 2 2016年武汉大学测绘遥感信息工程国家重点实验室数据结构复试笔试最后押题五套卷（二） 12 2016年武汉大学测绘遥感信息工程国家重点实验室数据结构复试笔试最后押题五套卷（三） 20 2016年武汉大学测绘遥感信息工程国家重点实验室数据结构复试笔试最后押题五套卷（四） 30 2016年武汉大学测绘遥感信息工程国家重点实验室数据结构复试笔试最后押题五套卷（五） 38
一、选择题
1． 哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（ ）方法是哈希文件的关键。
A. 哈希函数 B. 除余法中的质数 C. 冲突处理
D. 哈希函数和冲突处理 答:D
【解析】哈希表是根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上。
2． 循环队列元素数是（ ）。
答:A
【解析】对于循环队列，需要深刻理解队头在队尾进行进队操作。
和队尾
的概念，在队头进行出队操作，
如果为负则元
可能为正也可能为负，为正时元素个数=
存放其元素值，用front 和rear 分别表示队头和队尾，则当前队列中的
素的个数=所以统一的公式就是
3． 下列选项中，不属于网络体系结构中所描述的内容是（ ）。
A. 网络的层次 B. 每一层使用的协议 C. 协议的内部实现细节 D. 每一层必须完成的功能 答:C
【解析】体系结构仅规定协议的功能和消息格式，但对具体的实现细节由具体设备厂商来确定，对于网络的层次，以及每一个层次的协议及其功能都是网络体系结构所要描述的内容，因此答案为选项C 。
4． 程序段
其中n 为正整数，则最后一行的语句最坏情况下的时间复杂度是（ ）。
答:D
【解析】这个是冒泡排序，最坏的情况下需要进行次交换，即时间复杂度是
5． 使用浏览器访问某大学Web 网站主页时，不可能使用的协议是（ ）
A.PPP B.ARP C.UDP D.SMTP 答:D
【解析】SMTP 是简单邮件传输协议，访问主页时并不涉及邮件相关协议。
6． 某计算机有16个通用寄存器，采用32位定长指令字操作码字段（含寻址方式位）为8位，Store 指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址方式，若基址寄存器可使用任一通用寄存器，且偏移量用补码表示，则Store 指令中偏移量的取值范围是（ ）
A.-32768〜+32767 B.-32767〜+32768 C.-65536〜+65535 D.-65535〜+65536 答:A
【解析】寄存器个数指令编址方式如下所示：
16位补码取值范围为-32768〜+32767，所以偏移量取值范围为-32768〜+32767
7． 下面关于哈希（Hash ，杂凑）查找的说法正确的是（ ）。
A. 哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B. 除留余数法是所有哈希函数中最好的 C. 不存在特别好与坏的哈希函数，要视情况而定
D. 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单地将该元素删去即可 答:C
【解析】若数据结构中存在关键字和K 值相等的记录，则必定在不需要进行比
较便可直接取得所查记录。在此，称这个对应关系f 为哈希（Hash ）函数，哈希函数的选择要视具体情况而定。
偏移量有32-8-4-4=16位
的存储位置上，由此，
8． 站点A 、B 、C 通过CDMA 共享链路，A 、B 、C 的码片序列（chipping sequence
）分别是
和
C 收到A 发送的数据是（ ）
A.000 B.101 C.110 D.111 答:B
【解析】用A 的码片与信息做内积运算
9． 将线性表的数据元素进行扩充，允许带结构的线性表是（ ）。
A. 串 B. 树 C. 广义表 D. 栈 答:C
【解析】串、树、栈中的数据元素都是属于非结构的原子类型，元素的值是不可分解的。数组和广义表都是允许带结构的线性表。
10．求整数阶乘的算法如下，其时间复杂度是（ ）。
A.
B. C. D. 答:B 。
【解析】设fact （n ）的运行时间函数是T （n ）。
该函数中语句①的运行时间是0（1）, 语句②的运行时间是法运算的时间。
因此，
当
时
，
当
即fact （n
）的时间复杂度为
时
，
则
，
若C 从链路上收到的序列是
则
其中O （1）为乘
相关内容
相关标签