2014年数据结构考研真题答案及解析（一）

本文提供2014年数据结构考研真题答案及解析，以下为具体内容

1、下列程序段的时间复杂度为（ ）。

A、O(n^1/2)

B、O(n^1/3)

C、O(n)

D、O(n²)

2、链表不具有的特点是（ ）。

A、可随机访问任一个结点。

B、插入和删除不需要移动元素。

C、不必事先估计储存空间。

D、所需空间与线性表的长度成正比。

3、已知栈的输入序列为abcd，不可能得到的输出系列为（ ）。

A、abcd

B、dcba

C、acdb

D、cabd

4、设指针变量front表示链式的队头指针，指针变量rear表示链式队伍的队尾指针，指针变量s指向将要入队伍的结点X，则入队伍的操作序列为（ ）。

A、front->next=s; front=s ;

B、s->next-rear; rear=s;

C、rear->next=s; rear=s;

D、s->next=front; front=s;

5、先序遍历二叉树与中序遍历二叉树所得序列相同的二叉树为（ ）。

A、根结点无左子树的二叉树。

B、根结点无右子树的二叉树。

C、只有根结点的二叉树或非叶子结点只有左子树的二叉树。

D、只有根结点的二叉树或非叶子结点只有右子树的二叉树。

6、一组记录的关键码为{46，79，56，38，40，84}，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。

A、38，40，46，56，79，84

B、40，38，46，79，56，84

C、40，38，46，56，79，84

D、40，38，46，84，56，79

7、折半查找有序表（1，5，8，15，21，30，50，70，88，100），若查找元素58，则它将依次与表中_________元素比较。（查找结果是失败）

A、21，70，30，50

B、30，88，70

C、21，50

D、30，88，50，70

8、用数组表示的循环序列的最小标号为1，最大标最为MAXISIZE，则队空与队满的判断条件是_________。

A、front==(rear+1)%MAXISIZE与front==rear

B、front==rear+1 与front==rear

C、front==rear与front==rear+1

D、front=rear与(rear+1 )%MAXISIZE

9、无向图G= (V，E)：其中V={a，b，c，d，e，f}，E = {(a，b)，(a，e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}，对该图进行深度优先遍历，下面不能得到的序列是（ ）。

A、acfdeb

B、aebdfc

C、aedfcb

D、abecdf

10、二维数组A的每个元素是由六个字符组成的串，其行下标i的范围从0到8，列下标j的范围从1到10。若A按行优先存储，元素A[8，5]的起始地址与当A按列优先存储时的元素（ ）的起始地址相同，设每个字符占一个字节。（注：A无第0列）

A、A[8,5]

B、A[3,10]

C、A[5,8]

D、A[0,9]

1、试题答案：A

试题解析：

【考点】本题考查时间复杂度的计算。
【解析】显然n表示规模，第一次循环s₀=0，第二次循环s₂=0+1，第三次循环s₃=0+1+2，第四次循环s₄=0+1+2+3，…，第k次循环s_k=0+1+2+3+…+(k-1)=k(k-1)/2。由k(k-1)/2<n，可得T(n)= O(n^1/2)。故本题选A。

2、试题答案：A

试题解析：

【考点】本题考查链表的特点。
【解析】链表中各个结点的地址随机分配的，不一定连续，所以不可以随机访问任一结点。故本题选A。

3、试题答案：D

试题解析：

【考点】本题考查栈的正确输出顺序。
【解析】栈的特点是“先进后出”。题干给栈的出输入序列为abcd，可知a先于b入栈，所以出栈时a在b的后面。而选项D的序列“cabd”中，a先于b出栈，所以该序列不可能为出栈序列。故本题选D。

4、试题答案：C

试题解析：

【考点】本题考查链队的入队操作。
【解析】队列的特点是“先进先出”，队头出队，队尾入队。入队操作示意图如下所示，由此易知入队伍的操作序列为“rear->next=s; rear=s;”。故本题选C。

5、试题答案：D

试题解析：

【考点】本题考查二叉树的遍历。
【解析】二叉树中，先序遍历遵循“根左右”原则，中序遍历遵循“左根右”原则。若有根结点的二叉树，则这两种遍历次序均遵循“根”的原则，此时两者的遍历序列相同。若非叶子结点只有右子树的二叉树，则这两种遍历次序均遵循“根右”的原则，此时两者的遍历序列也相同。故本题选D。

6、试题答案：C

试题解析：

【考点】本题考查快速排序的手动过程。
【解析】在快速排序中，附设两个指针 left 和 right，它们初始分别指向待排序序列的左端和右端，此外还要附设一个基准，一般选择第一个元素46为基准。

7、试题答案：A

试题解析：

【考点】本题考查折半查找中的元素比较。
【解析】（0+9）/2=4，第一比较的元素是21，且21<58，故在21的右边继续折半查找；（5+9）/2=7，第二次比较的元素是70，且70>58，故继续在21的右边、70的左边继续折半查找；（5+6）/2=5，第三次比较的元素是30，且30<58，故继续在30的右边、70的左边继续折半查找；（6+6）/2=6，第四次比较的元素50，50<58，此时折半查找完成，查找元素58失败。综上所述，若查找元素58，则它将依次与表中21、70、30、50比较。故本题选A。

8、试题答案：D

试题解析：

【考点】本题考查循环队列的对空和队满判断。
【解析】在队列中，队头出队元素，队尾进队元素。循环队列中留出一个空位，用于判断队列是否已满。当某一元素入队时，队尾指针需要向后移动一位，若此时满足条件(rear+1 )%MAXISIZE则说明队列已满。队列为空时，队头指针与队尾指针指向同一个位置，即front=rear。

9、试题答案：D

试题解析：

【考点】本题考查图的深度优先遍历。
【解析】根据题干所给信息画出图G如下所示。深度优先遍历的思想是从一个顶点出发，沿着一条路走访问未被访问过的结点，直到该路径走不通的时候再回溯。看选项D，从顶点a出发，可以访问顶点b，接着访问顶点e，此时e路径上还有顶点d未被访问，应该接着访问顶点d、顶点f、顶点c，而不是直接访问顶点c。因此，对图G进行深度优先遍历时不可能得到选项D中的序列abecdf。故本题选D。

10、试题答案：B

试题解析：

【考点】本题考查二维数组的存储地址。
【解析】根据题意知，元素A[8，5]位于第9行第5列。因此，按行优先存储时，A[8，5]是第8*10+5=85个元素。由85/9的商为9，余数为4可知，按列优先存储时，A[3，10]是第85个元素。所以当A按行优先存储时的元素A[8，5]的起始地址，与当A按列优先存储时的元素A[3，10]的起始地址相同。故本题选B。