《2016年大连海事大学交通运输管理学院数据结构(同等学力加试)复试笔试最后押题五套卷.doc》由会员分享，可在线阅读，更多相关《2016年大连海事大学交通运输管理学院数据结构(同等学力加试)复试笔试最后押题五套卷.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2016年大连海事大学交通运输管理学院数据结构(同等学力加试)复试笔试最后押题五套卷一、选择题1 设被排序的结点序列共有N 个结点，在该序列中的结点已十分接近排序的情况下，用直接插入法、归并法和一般的快速排序法对其排序，这些算法的时间复杂性应为（ ）。 答:C【解析】因为该序列中的结点已经十分接近排序的情况，对于直接插入法，大部分结点只需要直接插入后面即可，因此时间复杂度为的时间复杂度为对于采用归并法，它是一种稳定的排序方法，它对于一般的快速排序法，序列越接近有序，所需要的比较次数越多，此时的时间复杂度为 2 某机器有一个标志寄存器，其中有进位/借位标志CF 、零标志ZF 、符号标志SF 和溢
2、出标志OF ，条件转移指令bgt （无符号整数比较大于时转移）的转移条件是（ ）。A.CF+OF=0 B.SF+ZF=0 C.CF+ZF=0 D.CF+SF=0 答:C【解析】判断无符号整数AB成立，满足的条件是结果不等于0, 即零标志ZF=0, 且不发生进位，即进位/借位标志CF=0。所以正确选项为C 。其余选项中用到了符号标志SF 和溢出标志OF , 显然可以排除掉。 3 将两个各有N 个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。A.N B.2N-1 C.2N D.N-1 答:A【解析】归并排序基本思想：归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并
3、是直接将两个有序的子表合并成一个有序的表。归并排序最好情况下的复杂 度为 4 若线性表最常用的操作是存取第I 个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（ ）。A. 单链表B. 双向链表 C. 单循环链表 D. 顺序表 答:D【解析】线性表采用顺序表，便于进行存取任一指定序号的元素。5 当字符序列作为图输入时，输出长度为3的且可用作C 语言标识符的序列的有（ ） 。A.4个 B.5个 C.3个 D.6个 图答:C【解析】首先需要明白C 语言标识符的命名规则。数字不能作为标识符的开头，因此第一个字符只能为t 或者下划线。若首字符为t , 有两种结果若首字符为则只有一种结果因此总共有
4、3种结果。 6 float 类型（即IEEE754单精度浮点数格式）能表示的最大正整数是（ ）。A.B. C. D. 答:D 。【解析】IEEE754单精度浮点数尾数采用隐藏位策略的原码表示，且阶码用移码表示的浮点数。规格化的短 浮点数的真值为：故float 类型能表示的最大整数是 7 数组通常具有的两种基本操作是（ ）。A. 查找和修改 B. 查找和索引 C. 索引和修改 D. 建立和删除 答:A【解析】数组中的元素是顺序存放的，通过下标可以很好地查找数组元素，同时通过对应的 S 为符号位，E 的取值为 f 为23位；指针可以修改数组元素的值，因此数组通常具有的两种基本操作是查找和修改。根据
5、数组的性质，数组通常具有的两种基本运算是排序和查找。 8 静态链表中指针表示的是（ ）。A. 下一元素的地址 B. 内存储器的地址 C. 下一元素在数组中的位置 D. 左链或右链指向的元素的地址 答:C【解析】静态链表的一般结构为： 这种结构是预先分配一个较大的空间，类似于一次申请一个较大的数组，但是元素的增删操作都不会移动元素，只需要移动next 成员就行。因此，静态链表中的指针实际上表示的就是下一个元素在数组中的位置。 9 处理外部中断时，应该由操作系统保存的是（ ）。A. 程序计数器（PC ）的内容 B. 通用寄存器的内容 C. 快表（TLB ）的内容 D.Cache 中的内容 答:B【
6、解析】外部中断处理过程首先要保护现场，使得中断处理完后能够恢复程序的状态继续执；由中断服务程序保行。保护现场有两个含义：由中断隐指令保存程序的断点（程序计数器）存通用寄存器和状态寄存器的内容。中断服务程序是操作系统的一部分。10主机甲向主机乙发送一个的TCP 段，期望与主机乙建立TCP 连接，若主机乙接受该连接请求，则主机乙向主机甲发送的正确的TCP 段可能是（ ）。A. （SYN=0, ACK=0, seq=11221, ack=11221） B. （SYN=1, ACK=1, seq=11220, ack=11220） C. （SYN=1，ACK=1, seq= 11221，ack= 11221） D. （SYN=0, ACK=0, seq= 11220, ack= 11220） 答:C【解析】TCP 是面向连接的，所谓面向连接，就是当计算机双方通信时必需先建立连接，然后数据传送，最后拆除三个过程，也就是客户主动打开TCP 传输，服务器被动打开。第一次握手：客户发送SYN=1，seq=x 给服务器，即客户的TCP 向服务器发出连接请求报文段，其首部中的同步位SYN=1，并选择序号seq=x，表明传送数据时的第一个数据字节的序号是X 。第二次握手：服务器发送SYN=1, ACK=1, Seq=y, ack=X+l给客户，即服务器的TCP 收到连接请求报文段后，一、选择题考研试题
