列出该二叉树的所有叶子结点。 请写出该二叉树的先序遍历序列、中序遍历序列、后序遍历序列。 请写出该二叉树的按层次遍历序列。
将该二叉树调整成 AVL 树。
若该图为“左孩子－右兄弟”的二叉存储结构，请画出该图所对应的树（森林）。
10、无向图的邻接矩阵是一个（） 。 A ．对角矩阵 B．对称矩阵 C．上三角矩阵 D．零矩阵
第2 页
西安建筑科技大学
2018 年攻读硕士学位研究生招生考试试题
（ 答案书写在本试题纸上无效。考试结束后本试题纸须附在答题纸内交回 ） 共 4
页
考试科目 :    （835）数据结构
适用专业 : 计算机科学与技术、计算机技术、控制工程
一、单项选择题（共 10 题，每小题 2 分，共 20 分）。
1、算法分析的目的是（） 。
A．出数据结构的合理性    B．研究算法中的输入和输出关系
C．分析算法的效率以求改进    D．分析算法的可读性和简明性
2、若一个顺序表中第一个元素的存储地址为    1000，每个元素占 4 个地址单元，那么，第 6 个元素
的存储地址应是（） 。 A． 1020 B． 1010 C．1016 D．1024
3、带头结点的单链表（以 head 为头指针）为空的判断条件是（） 。
A． head!=NULL B． head->next==head C． head->next==NULL D．head==NULL
4、在一个单链表中，已知 q 指向 p 所指结点的前驱结点，若在 p、q 所指结点之间插入一个 s 所指 向的新结点，则执行的操作是（） 。
A． q->next=s; s->next=p;    B．p->next=s; s->next=q;
C．s->next=p->next; p->next=s;    D． p->next=s->next; s->next=p;
5、在一个单链表中，若删除 p 指向结点的后继结点，则执行的操作为（） 。
A． q=p->next; p->next= p->next->next; free（q）;
B． p=p->next; q=p->next; p=q->next;    free（q）;
C． q=p->next->next; p = p->next->next; free（q）;
D． p=p->next->next; q = p->next->next; free（q）;
6、栈的操作原则是（） 。
A． 顺序进出 B．后进后出 C．后进先出 D．先进先出
7、一个队列的入队序列是 1，3，5，7，9，则出队的输出序列只能是（） 。 A ．9，7，5，
3，1    B．1，3，5， 7，9    C．1，5，9， 3，7    D． 9，5，1，7，3
8、将一棵有 100 个结点的完全二叉树从根开始，每一层从左到右依次对结点进行编号，根结点的
编号为 0，则编号为 49 的结点的左孩子编号为（） 。    A．99 B．98 C．50 D．48
9、以二叉链表作为二叉树的存储结构， 在具有 n 个结点的二叉链表中（ n>0），空链域的个数为（） 。 A．2n-1 B． n+1 C．n-1 D．2n+1
二、填空题（共 20 空，每空 1 分，共 20 分）。
1、数据结构一般包括    、 和数据运算
三个方面的内容。
2、数据的存储结构（物理结构）可以用    、 存储方法表示。设
有一批数据元素，为了最快地存取某元素，宜用 结构存储；为了方便地插入一个 元素，宜用 结构存储。
3、在长度为 n 的顺序表的第 i 个位置上插入一个元素， i 的合法范围是 ，元素的 移动次数为 ；删除表中第 i 个元素， i 的合法范围是 ，需要向前移 动 个元素。
4、栈和队列都是 结构；对于栈，只能在 插入和删除元素；对于队列，只 能在 插入 元素 ， 在 删除元素。
5、假设以 S 和 X 分别表示进栈和退栈操作，则对输入序列 a，b，c，d，e进行一系列栈操作 SSXSXSSXX 之后，得到的输出序列为 。
6、对于一个具有 n 个顶点和 e 条边的无向图，若采用邻接表表示，则表头向量的大小为 ， 所有邻接表中的结点总数是 。
7、二分查的存储结构仅限于    ，且是 。
8、对于二叉排序树上的查，若结点元素的关键字值大于被查元素的关键字值，则应该在该二 叉树的 继续查。
三．解答题（共 7 题，共 59 分）。
1、（14 分）已知二叉树如右图所示。请按要求回答问题： （1）
（2）
（3）
（4）
（5）
2、（15 分）已知图 G 的邻接表如右图所示。
（ 1）请画出该存储结构对应的图。
（ 2）请写出该图的邻接矩阵。
（ 3）请写出该图的逆邻接表。
（ 4）请写出该图从顶点 1 出发的深度优先搜索序列。 （ 5）请写出该图从顶点 1 出发的广度优先搜索序列。
西安建筑科技大学
2018 年攻读硕士学位研究生招生考试试题
（ 答案书写在本试题纸上无效。考试结束后本试题纸须附在答题纸内交回 ） 共 4 页
考试科目 :    （ 835）数据结构
适用专业 : 计算机科学与技术、计算机技术、控制工程
3、（3 分）有一组记录的关键字序列为 46，79，56，38，40，84，利用快速排序的方法，写出以第 一个记录为基准得到的一趟排序结果。
4、（6 分）对于给定的一组关键字 41，62，13，84，35，96，57，39，79，61，15，83，写出执行 希尔排序算法的第一趟排序结果，增量为    5。
5、（4 分）对于给定的一组关键字 26，18，60，14，7，45，13，32，写出执行堆排序算法的第一 趟排序结果。
6、（8 分）已知带权图如下图所示。 （1）请用普里姆（ 数据结构与算法考研真题Prim）算法求出该图的最小生成树。 （ 2）请用克鲁斯卡尔（ Kruskal）算法求出该图的最小生成树。
7、（9 分）试分析以下 3 个程序片段的时间复杂度。

四、算法设计题（共 5 题，共 51 分）。
1、（15 分）求两个正整数的最大公约数可以使用欧几里德算法。该算法的基本思想如下：两个正    整
数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。
（1）请设计递归版本的欧几里德算法。
int EuclideanRecursive （int a, int b） {
}
（2）请设计非递归版本的欧几里德算法。
int EuclideanIterative （int a, int b） {
}
2、（10 分）设二叉树的根指针为 bt，设计算法求二叉树的高度。
int HeightTree（BTreeNode *bt） {
}
3、（8分）已知数组 R 中存储的 m 项数据是乱序的（即没有按照从小到大的顺序排列好），请设计    算
法判断待查元素 x 是否在数组中出现。
int Search（int R[], int m, int x） {
}
4、（8 分）设二叉排序树的根指针为 bt，设计算法求二叉排序树中最大的关键字值。
int Maximum（BSTreeNode *bt） {
}
5、（10 分）基于合理的有向图存储结构，设计算法判定给定连通有向图    G 是否存在回路。
bool ExistCyclePath（Graph G）{
}