沈阳航空航天大学 2012 年818/数据结构专业综合考研真题

贡献者： xzllxls

　　 一、选择题(每题 2 分，共 30 分）
1 从逻辑上可以把数据结构分为( )两大类。
A.人动态结构、静态结构
B.顺序结构、链式结构
C.线性结构、非线性结构
D.初等结构、构造型结构

　　 2.在下面程序段中，对 x 的赋值语句的频度为()

for(k=1;k<n;k++)
{
    for(j=k; j<=n; j++)
    {
        x=x+1;
    }
}

　　 3. 算法的时间复杂度与( )有关。
A.问题规模 $\qquad$ B.计算机硬件的运行速度
C.源程序的长度 $\qquad$ D.编译后可执行程序的质量

　　 4. 在下列关于线性表的叙述中，正确的是()
A. 上线性表的逻辑顺序和物理顺序总是一致的. B. 线性表的顺序存储结构优于链式存储结构 C. 就线性表的查找效率而言，链式存储结构比顺序存储结构高。 D. 就线性表的插入效率而言，链式存储结构比顺序存储结构高。

　　 5. 已如循环链表的最后一个结点由 $p$ 指针指向，若要在该结点后插入 $s$ 指针指向的新结点，则应执行下列( ) 操作。
A. p->next *s; s->next=NULL;
B. p->next *s; s->next-p;
C. s->next *p->next; p->next *s;
D. s->next *p->next; p=s;

　　 6.一个核的入找序列是 a，b. c, d. e，则栈的不可能的输出序列是( )。
A edcbe $\qquad$ B. decba $\qquad$ C. dceab $\qquad$ D. abede

　　 7.若用一个大小为 6 的数组来实现循环队列，且当前 rear 和 front 的值分别为 10 和 3，当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为多少？
A.1 和 5 $\qquad$ B.2 和 4 $\qquad$ C.4 和 2 $\qquad$ D.5 和 1

　　 8.以下说法错误的是()
λ.树型结构的特点是一个结点可以有多个直接前驱。
B.线性结构中一个结点只能有一个直接后继
C.树型结构可以比线性结构表达更复杂的数据关系。
D.树是一种层次结构。

　　 9.在含有 $n$ 个结点的二叉链表中有( )个空指针。
A. n-1 $\qquad$ B. n+1 $\qquad$ C.n $\qquad$ D. n+2

　　 10.如果从无向图的任一项点出发进行一次深度优先遍历即可访问所有顶点，则该图一定是
A. 强连通图 $\qquad$ B. 连通图
C. 有回路 $\qquad$ D. 一棵树

　　 12.在一个无向图中，所有顶点的度数之和等于所有边数( ) 倍。
A. $1/2$ $\qquad$ B. $2$
C. $1$ $\qquad$ D. $4$

　　 13.下列有关图的说法不正确的是( )。
A.图的遍历是从某一项点出发使每个项点仅被访问一次的过程。
B.图的广度遍历算法不是一个递归的过程。
C.图的基本遍历算法有深度优先和广度优先两种。
D.图的深度优先遍历不适用于有向图。

　　 14.对线性表进行折半查找时，要求线性表的存储方式必须是( )。
A.顺序无序表 $\qquad$ B. 链式无序表
C. 顺序有序表 $\qquad$ D. 链式有序表

　　 15.对序列(5, 19, 27, 18, 10, 1. 4)进行排序，进行一趟排序操作后数据的排列变为(S, 19，18，10, 1, 4, 27};则采用的是( ) 排序。
A.选择 $\qquad$ B.快速 $\qquad$ C.希尔 $\qquad$ D、冒泡

　　 16.已知一完全二叉树共有 500 个结点，请回答下列问题(要求给出计算过程):
1.设根结点为第一层，则该二叉树有多少层? (3 分)
2.它有多少个叶子结点? (4 分)
3.它有多少个度为 2 的结点? (3 分)

　　 二、已知一完全二叉树共有 500 个结点，请回答下列问题(要求给出计算过程):
1.设根结点为第一层，则该二叉树有多少层? (3 分)
2.它有多少个叶子结点? (4 分)
3.它有多少个度为 2 的结点? (3 分)

　　 三、已知某二叉树的中序遍历结果为 ECBDAXYZ，后序遍历结果为 ECDBZYXA。
1.请画出该二叉树，并给出该二叉树的先序遍历序列(6 分)
2.请对该二叉树进行先序线索化(7 分)

　　 四，已知待排序序列为(27, 46,5,18,16,51.32.26). 请给出以下排序算法的一趟排序结果(按非递减顺序):
1. 希尔排序(d=3) (4 分)
2. 起泡排序(2 分)
3. 快速排序，(以 27 为枢轴) (4 分)
4. 堆排序(4 分)

　　 五、已知某有向图的顶点集为{V1, V2,V3,V4,VS,V6,V7,V8 )，弧集为 K1,4>.<V1, v3>, <V1,V2>, <V2, vs>,<V2, V4>, <V3, V6>, <V3, V4>, <V4, V8>，<14,v7, <V4, V6>, <Vs, V7>, <V6, V8>, <V6, V8>, <V7, V8>).
1. 画出其对应的邻接表，要求邻接表中的结点都按序号从大到小有序(2 分)
2. 根据 1 写出从项点 V1 出发的深度优先遍历序列、深度优先生成树(6 分)
3. 根据 1 写出从项点 V1 出发的广度优先遍历序列、广度优先生成树(6 分)

　　 六、对于如图所示的有向网。请用 Dijkstra 方法求顶点 A 到图中其它顶点的最短路径。(12 分)

　　 七、已知一数据域为整数的带头 单链表有效结点个数至少为 3 个，请编写一算法判断该链表存储的整数序列是否为等差数列，(12 分)

　　 八、设以数组 Q.clem[maxSize]存放循环队列的元素(存储结构如下所示)，同时以 0. rear 和 Q. length 分别指示循环队列中队尾位置和队列中所含元素的个数。试给出该循环队列的对空条件和队满条件，并写出相应的入队和出队操作(15 分)

typedef struct{
    QElemType *base; // 动态分配存储空间
    int rear; //尾指针，若队列不空，指向队列尾元素的下一个位置
    int length;
) SqQueue;

　　 九、已知一棵采用三叉链表作为存储结构的二叉树的树根指针 T,请设计一算法查找树中值为 K 的结点(该结点不是树根)，若找到，在 K 结点的双亲结点和双亲的左子树之间插入一数据元素为 X 的结点。(15 分)

　　 十、设计一算法以实现对无向图 G 的深度遍历，要求:将每一个连通分量中的项点以一个表的形式输出。例如，下图的输出结果为: (1，3) (2, 6, 7, 4,5, 8) (9，10) (15 分) .

　　 注:获取项点 v 第一个邻接点操作: int FirstAdjVex(G, v);
获取 v 下一个邻接点操作: int NextAdjVex (G,v, w);