爱考：2013年计算机专业数据结构考研模拟题及答案

1、计算机专业考研数据结构模拟练习题来源：爱考机构1.下面算法的吋间复朵度为。0(n) B. 0(2)C. 0(log2) D . 0(乔)2若耍在0(1)的吋间复朵度实现两个循环链衣头尾相接，则对应两个循环链衣各设置一个指针，分别指向各口的头节点C.各口的笫一个元索节点各口的尾节点D. 一个衣的头节点，一个衣的尾节点pn,设n个元索进栈序列足1, 2, 3,若Pl=3,则p2的值为。定是2 B.定是1，n,其输出序列足pl, p2, p3, 不可能足1 D.以匕都不止确设离度为h的二叉树只冇度为0和度为2的节点，则此类二叉树中所包含的节点数至 少为。A. 2hB. 2h+lC. 2hTD. h-

2、1对丁二叉排序树，下面的说法是止确的。二叉排序树是动态树表，查找不成功吋插入新结点吋，会引起树的重新分裂和组合对二叉排序树进行蜃序遍历可得到冇序序列用逐点插入法构造二叉排序树吋，若先后插入的关键字冇序，二叉排序树深度最人在二叉排序树中进行查找，关键字的比较次数不会超过结点数的1/2设X足树T中的个非根节点，B足T所对应的二叉树。在B中，X足其双亲的右孩了，下列结论止确的是。在树T中，X是其双亲的第个孩了在树T中，X M 定无右边兄弟在树T中，X 定是叶了结点在树T种，X 定冇左边兄弟若一个冇向图具冇拓扑排序序列，那么它的邻接矩阵必定为。A.对称矩阵B.稀疏矩阵C.二角矩阵D. 般矩阵判断个冇向

3、图是否存在回路的方法除了可以利用拓扑排序的方法外，还可以使用A.求关键路径的方法B.求最短路径的Dijikstra方法C.广度优先遍历算法D.深度优先遍历算法下列数据结构，查找效率最低的是。A.冇序顺序衣B.二叉排序树C.堆D . B-树10在基丁关键字比较的算法中,算法在最坏的情况下的吋间复朵度不高丁O(nlog2 n )。A.冒泡排序B.川并排序C.希尔排序D.快速排序11用肓接插入排序方法对下面四个序列进行排序(由小到人)，元索的比较次数戢少A. 94, 32, 40, 90,80, 46,21,69B. 32, 40, 21, 46,69, 94,90,80C. 21, 32, 46,

4、 40,80, 69,90,94D. 90, 69, 80, 46,2L 32,94,4012.已知加权冇向图G的邻接矩阵如下: 15 4 TOC o 1-5 h z 21268439510 画出该冇向图G,设顶点分别为a, b, c, d, e, f, g.。试用Dijkstra算法求G屮从顶点a到其他各顶点间的戢短路径，并给出求解过程13.设计一个算法，判断一个带头结点的双向循环链衣DL是否对称相等。(比如衣(25, 34, 34, 25)和农(25, 3, 25)为对称的)其中结点结构为：struct NodeElemType data; / ElemType代农某种数据类型Node *

5、Llink, Rlink;给出算法的基本设计思想。根据设计思想，采用C或C+或JAVA语言描述算法，关键之处给出注释。计算机专业考研数据结构模拟练习题答案111： DBCCC DCDCB C(2)sd0 path0dl pat hld2 path2d3 path3d4 path4d5 pat h5d6 patha0,-115,02,012,0 , _1 , _1 ,c0,-115,02,012,010,26,2 ,f0,-115,02,012,010,26,216, 5e0,-115,02,012,010,26,216,5d0,-115,02,012,010,26,215,3b0,-115,02,012,010,26,215,3f0,-115,02,012,010,26,215,313. (1)算法的基本思想如下：分别设置左右指针，从两边向中间移动，同时判断是否 对称，当左右两个指针碰头或者交叉时终止。(2)算法描述如下：bool isSym(Node *h)Node *l=h-Llink;Node fr=h-Rlink ;if (1=NULL | | r=NULL) return true; /链表为空while(l!