当前位置：问答库＞考研试题

一、填空题

1． 用循环链表表示的队列长度为n ，若只设头指针，则出队和入队的时间复杂度分别是_____和_____；若只设尾指针，则出队和入队的时间复杂度分别是_____和_____。

【答案】

【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一个结点或者下下个结点删除即可，入队时，只要在尾指针的后面插入新的结点，并更新尾结点即可。

2． 对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。

【答案】集合；线性结构；树形结构；图状结构（网状结构）

3． 深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。

【答案】

4． 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n

个顶点

用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。

（1）若

是边，则

的值等于_____，若

不是边，则

的值是一个比任

何边的权，矩阵的对角线元素全为0。

（2）构造最小生成树过程中，若顶点Vi 已包括进生成树，就把相邻矩阵的对角线元素A （i , i ）置成若

【答案】（1）

已包括进生成树，就把矩阵元素A （i ，j ）置成。 边上的权值；都大的数；（2）1; 负值；（3）为负；边

（3）算法结束时，相邻矩阵中的元素指出最小生成树的

5． 设T 是一棵结点值为整数的二叉排序树，A 是一个任意给定的整数。free_tree在下面的算法中，（T ）在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点；

首

先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下处理：（1）若找不到值为A 的结点，则返回根结点的地址（2）若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返否则返回根结点的地址。

【答案】

6． —个字符串中_____称为该串的子串。

【答案】任意个连续的字符组成的子序列

7． 在基于关键字比较且时间为O （nl 〇g2n ）的排序中，若要求排序是稳定的，则可选用_____，则可选用_____排序。 排序；若要求就地排序（及辅助空间为0（1））

【答案】归并；堆

8． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。

【答案】

【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。

9． 组成串的数据元素只能是_____。

【答案】字符

10．数组的存储结构采用_____存储方式。

【答案】顺序存储结构

【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。

11．设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称 增量序列）依次是4，2，1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。

【答案】3; （10，7，-9，0，47，23，1，8，98，36）

12．已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_____。

【答案】

【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。

二、选择题

13．某机器有一个标志寄存器，其中有进位/借位标志CF 、零标志ZF 、符号标志SF 和溢出标志OF ，条件转移指令bgt （无符号整数比较大于时转移）的转移条件是（ ）。

A.CF+OF=0 B.SF+ZF=0 C.CF+ZF=0 D.CF+SF=0 【答案】C

【解析】判断无符号整数A>B成立，满足的条件是结果不等于0, 即零标志ZF=0, 且不发生进位，即进位/借位标志CF=0。所以正确选项为C 。其余选项中用到了符号标志SF 和溢出标志OF , 显然可以排除掉。

14．主机甲和主机乙间已建立一个TCP 连接，主机甲向主机乙发送了两个连续的TCP 段，分别包含300字节和500字节的有效载荷，第一个段的序列号为200, 主机乙正确接收到两个段后，发送给主机甲的确认序列号是（ ）。

A.500 B.700 C.800 D.1000 【答案】D

【解析】TCP 使用滑动窗口流控协议，窗口大小的单位是字节，本题中分别包含300字节和500字节的有效载荷，第一个段的序列号为200, 那么确认序列号为200+300+500=1000。

15．下列选项中，不可能是快速排序第2趟排序结果的是（ ）

A.2, 3, 5, 4, 6, 7, 9 B.2, 7, 5, 6, 4, 3, 9 C.3, 2, 5, 4, 7, 6, 9 D.4, 2, 3, 5, 7, 6, 9

【答案】C

【解析】对于快速排序，每一趟都会使一个元素位于有序时的位置，而有序序列为2, 3, 4, 5, 6, 7, 9, 与C 进行对比，只有9位于它有序的时候的位置，显然不是第二趟快速排序的结果