2018 年天津城建大学攻读硕士学位 研究生入学考试试题（ A）卷 考试科目 代码 ： 815 考试科目名称： 数据结构 招生专业： 081200 计 算机 科学与技术 - - A 卷 试题 第 1 页 共 5 页 【 提示 】 ：所有答案一律写在答题纸上！ 一、 单项选择题（本题共 15 小题，每题 2 分，共 30 分） 1.二叉树的第 K 层的结点数最多为 ( ). A、 2k-1 B、 2K+1 C、 2K-1 +1 D、 2k-1 2.字符串的长度是指（ ）。 A、串中不同字符的个数 B、 串中不同字母的个数 C、串中所含字符的个数 D、 串中不同数字的个数 3.栈和队列的共同特点是 ( )。 A、只允许在端点处插入和删除元素 B、都是先进后出 C、都是先进先出 D、没有共同点 4对于存储同样一组数据元素而言，（ ）。 A、顺序存储结构比链接结构多占空间 B、在顺序结构中查找元素的速度比在链接结构中查找要快 C、与链接结构相比，顺序结构便于安排数据元素 D、顺序结构占用整块空间而链接结构不要求整块空间 5已知一棵完全二叉树的第 6 层（设根为第 1 层）有 8 个叶结点，则完全二叉树的结点个数最多是（ ） A、 39 B、 52 C、 111 D、 119 6设指针变量 p 指向单链表中结点 A，若删除单链表中结点 A，则需要修改指针的操作序列为（ ）。 A、 q=p->next； p->data=q->data； p->next=q->next； free(q)； B、 q=p->next； q->data=p->data； p->next=q->next； free(q)； C、 q=p->next； p->next=q->next； free(q)； D、 q=p->next； p->data=q->data； free(q)； 7设输入序列 1、 2、 3、 、 n 经过栈作用后，输出序列中的第一个元素是 n，则输出序列中的第 i 个输出元素是（ ）。 A、 n-i B、 n-1-i C、 n+l -i D、 不能确定 8顺序表有 5 个元素，设在任何位置上插入元素是等概率的，则在该表中插入一个元素时所需移动元素的平均次数为（ ）。 A、 3 B、 2 C、 2.5 D、 5 2018 年天津城建大学攻读硕士学位 研究生入学考试试题（ A）卷 考试科目 代码 ： 815 考试科目名称： 数据结构 招生专业： 081200 计 算机 科学与技术 - - A 卷 试题 第 2 页 共 5 页 9线性表采用链式存储时，其地址（ ）。 A、 必须是连续的 B、 一定是不连续的 C、 部分地址必须是连续的 D、 连续与否均可以 10设某棵二叉树的中序遍历序列为 ABCD，前序遍历序列为 CABD，则后序遍历该二叉树得到序列为（ ）。 A、 BADC B、 BCDA C、 CDAB D、 CBDA 11设图的邻接矩阵为010100110 ，则该图为（ ）。 A、有向图 B、无向图 C、强连通图 D、完全图 12下列四种排序中（ ）的空间复杂度最大。 A、 快速排序 B、 冒泡排序 C、 希尔排序 D、 堆 13设有序顺序表中有 n 个数据元素，则利用二分查找法查找数据元素 X 的最多比较次数不超过（ ）。 A、 log2n+1 B、 log2n-1 C、 log2n D、 log2(n+1) 14设某无向图中有 n 个顶点 e 条边，则该无向图中所有顶点的入度之和为（ ）。 A、 n B、 e C、 2n D、 2e 15设散列表中有 m 个存储单元，散列函数 H(key)= key % p，则 p 最好选择（ ）。 A、 小于等于 m 的最大奇数 B、 小于等于 m 的最大素数 C、 小于等于 m 的最大偶数 D、 小于等于 m 的最大合数 二、填空题（本题共 10 题，每题 3 分，共 30 分） 1. 设有两个字符串 p 和 q，求 q 在 p 中首次出现的位置的运算称作 。 2. 快速排序算法的平均时间复杂度为 O(nlog2n)，直接插入排序算法的平均时间复杂度为 。 3. 设哈夫曼树中共有 99 个结点，则该树中有 个叶子结点 。 4. 设在长度为 20 的有序表中进行二分查找，则比较一次查找成功的结点数有 1个，比较两次查找成功有结点数有 个。 5. 设一棵 m叉树的结点数为 n，用多重链表表示其存储结构，则该树中有 个空指针域。 2018 年天津城建大学攻读硕士学位 研究生入学考试试题（ A）卷 考试科目 代码 ： 815 考试科目名称： 数据结构 招生专业： 081200 计 算机 科学与技术 - - A 卷 试题 第 3 页 共 5 页 6. 设 有一个二维数组 Amn，假设 A00存放位置在 644， A22存放位置在676。 每个元素占一个空间，则 A33存放在位置 。 7. 数据结构从逻辑上划分为三种基本类型： 、树型结构和图型结构。 8. 设无向图 G 中有 n 个顶点 e 条边，则用邻接矩阵作为图的存储结构进行深度优先或广度优先遍历时的时间复杂度为 O(n2)；用邻接表作为图的存储结构进行深度优先或广度优先遍历的时间复杂度为 。 9. 若要求一个稀疏图 G 的最小生成树，最适合用 算法求解。 10设一组初始关键字序列为 (38， 65， 97， 76， 13， 27， 10)，则第 3 趟冒泡排序结束后的结果为 。 三、解答题（本题共 5 小题，每题 10 分，共 50 分） 1 设一组初始记录关键字序列为 (45， 80， 48， 40， 22， 78)，则分别给出第 4 趟简单选择排序和第 4 趟直接插入排序后的结果。 2 设无向图 G 如下图： BA DCEGF试给出 : （ 1） 该图的邻接矩阵； （ 2） 从 A 出发的 “深度优先 ”遍历序列； 3. 已知待散列的线性表为（ 36， 15， 40， 63， 22），散列用的一维地址空间为 0.6，假定选用的散列函数是 H（ K） = K mod 7，若发生冲突采用线性探查法处理，试： 2018 年天津城建大学攻读硕士学位 研究生入学考试试题（ A）卷 考试科目 代码 ： 815 考试科目名称： 数据结构 招生专业： 081200 计 算机 科学与技术 - - A 卷 试题 第 4 页 共 5 页 （ 1）计算出每一个元素的散列地址并在下图中填写出散列表： 0 1 2 3 4 5 6 （ 2）求出在查找每一个元素概率相等情况下的平均查找长度。 4.设二叉树 BT 的存储结构如下： 1 2 3 4 5 6 7 8 9 10 Lchild 10 data Rchild （ 1）画出该树。 （ 2）写出该树的前序、中序、后序遍历序列。 5假设用于通讯的电文仅由 8 个字母 A、 B、 C、 D、 E、 F、 G、 H 组成，字母在电文中出现的频率分别为： 0.07， 0.19， 0.02， 0.06， 0.32， 0.03， 0.21， 0.10。 （ 1）请为这 8 个字母设计哈夫曼编码，并求平均编码长度。 （ 2）使用十进制 0 至 7 的三位二进制形式作为 8 个字母的定长编码，求平均编码长度。 （ 3）比较两种方案的优缺点。 四、算法设计题（本题共 3 小题，共 40 分） 1归并（亦称合并）排序是一种通过归并操作实现输出有序序列的排序方法，请试设计在链式存储结构实现归并排序的算法。要求：函数名称及参数请设定为void mergelklist(lklist *ha,lklist *hb,lklist * typedef struct node datatype data; struct node *next; lklist; void delredundant(lklist *&head) 3 设一棵二叉树的信息存储在对应的二叉链表结构中，根节点指针为 bt，试设计一种递归计算该二叉树中所有结点值之和的算法。要求：函数名称及参数请设定为 void sum(bitree *bt, int &s)；请用 C/C+语言描述，并加以适当注释说明。 （ 10 分）