2018年天津城建大学825工程信息技术硕士研究生入学考试试题.pdf
2018 年天津城建大学攻读硕士学位 研究生入学考试试题( A)卷 考试科目 代码 : 825 考试科目名称 工程信息技术 招生专业: 建筑与土木工程 - - A 卷 试题 第 1 页 共 5 页 一、 单项选择题 (本题共 20 小题,每题 2 分,共 40 分) 1. 计算机所处理的数据一般具有某种内在联系,这是指( )。 A. 数据和数据之间存在某种联系 B. 数据项和数据项之间存在某种联系 C. 元素内部具有某种结构 D. 元素和元素之间存在某种联系 2. 在计算机中表示数据时,数据的物理地址和逻辑地址相同并且连续,称其为( )。 A. 链式存储结构 B. 顺序存储结构 C. 顺序存取 结构 D. 随机存取 结构 3. 循环单链表的主要优点是( )。 A. 不再需要头指针 B. 已知某个结点的位置后,能容易找到它的直接前驱 C. 从表中任一结点出发都能扫描到整个链表 D. 在进行插入、删除操作时,能更好保证链表不断开 4. 从一个具有 n 个结点的单链表中 查找其值等于 x 结点时,在查找成功的情况下,需要比较( )个结点。 A. n B. n/2 C. (n-1)/2 D. (n+1)/2 5. 若一个栈的输入序列是 1,2,3, ,n,其输出序列是 p1,p2, , pn,若 p1=5,则 p2的值( )。 A. 一定是 4 B. 一定是 6 C. 不可能是 3 D. 以上都不对 6. 循环队列 sq 中,用数组 a 40存放数据元素, sq.front 指示队头元素的前一个位置, sq.rear 指示队尾元素的当前位置,设当前 sq.front 为 20, sq.rear 为 12,则当前队列中的元素个数为( )。 A. 30 B. 31 C. 32 D. 33 7. 设串 s1=“ABCDEFGH“, s2=“2018“,函数 con(x,y)返回 x 和 y串的连接串, subs(s, i, j)返回串 s的从序号 i开始的 j个字符组成的子串, len(s)返回串 s的长度, replace(s, t, m)返回更新后的串 s,其中串 s 中子串 t 被串 m 替换,则 con(replace(s1, subs(s1, 2, len(s2), s2), subs(s1, len(s2), len(s2)的结果串是:( )。 A. AB2018GHDEFG B. A2018FGHDEFG C. AB2018GHEFGH D. A2018FGHEFGH 8. 二维数组 A 的元素都是 6 个字符组成的串,行下标 i 的范围从 08,列下标 j的范围从 110。若 A按行存放,元素 A85的起始地 址与 A按列存放时元素 ( )2018 年天津城建大学攻读硕士学位 研究生入学考试试题( A)卷 考试科目 代码 : 825 考试科目名称 工程信息技术 招生专业: 建筑与土木工程 - - A 卷 试题 第 2 页 共 5 页 的起始地址一致。 A. A85 B. A310 C. A58 D. A09 9. 深度为 k的完全二叉树至少有 m个结点,至多有 n个结点, m和 n分别为( )。 A. 2k-1 和 2k -1 B. 2k-1 -1 和 2k C. 2k-1-1 和 2k -1 D. 2k-1 和 2k 10. 一棵完全二叉树上有 1001 个结点,其中叶子结点个数是( )。 A. 501 B. 500 C. 250 D. 251 11. 用 邻接矩阵 表示图进行 广 度优先遍历时,通常是采用 ( ) 来实现算法。 A. 队列 B. 栈 C. 线性表 D. 串 12. 连通图 G 中有 n 个顶点 k 条边, G 的生成树是包含( )的连通子图。 A. n 个顶点 k 条边 B. n 个顶点 k-1 条边 C. n-1 个顶点 k 条边 D. n-1 个顶点 k-1 条边 13. G 是一个非连通无向图,共有 28 条边,则该图至少有( )个顶点。 A. 7 B. 8 C. 9 D. 10 14. 下述几种排序方法中,不稳定的是( )。 A. 直接插入排序 B. 快速排序 C. 归并排序 D. 起泡排序 15. 对关键字值序列 74, 73, 71, 26, 99, 16, 5, 68, 76, 100,构建初始堆,必须从关键字为( )的结点开始 。 A. 100 B. 74 C. 99 D. 26 16. 散列法存储中,处理冲突的两类主要方法是( ) 。 A. 线性探查法和双散列函数法 B. 建溢出区法和不建溢出区法 C. 除余法和折叠法 D. 拉链法和开放地址法 17. 长度为 12 的有序表采用顺序存储结构,运用折半查找技术,等概率情况下,查找失败的平均查找长度为( )。 A. 37/12 B. 62/13 C. 39/12 D. 49/13 18. 对一组记录( 68, 10, 96, 45, 26, 66, 52, 46, 84)进行直接插入排序,当把第 6 个记录 66 插入到有序表时,为寻找插入位置需比较( )次。 A. 1 B. 2 C. 3 D. 4 19. 按关键码集合 5, 3, 7, 1, 2, 9, 8, 10, 4, 6建立二叉排序树,然后查找 2,成功时比较次数为( )。 A. 1 B. 2 C. 3 D. 4 20. 利用快速排序对下列数据序列进行排序,速度最快的是( )。 A. 21, 25, 5, 17, 9, 23, 30 B. 25, 23, 30, 17, 21, 5, 9 C. 21, 9, 17, 30, 25, 23, 5 D. 5, 9, 17, 21, 23, 25, 30 2018 年天津城建大学攻读硕士学位 研究生入学考试试题( A)卷 考试科目 代码 : 825 考试科目名称 工程信息技术 招生专业: 建筑与土木工程 - - A 卷 试题 第 3 页 共 5 页 二、 填空 题(本题共 10 题,每题 3 分,共 30 分) 1. 下列程序段中 S 语句的执行频度为 。 for(i=2; i=n; +i) for(j=2; ji; +j) S; 2. 已知一个图的邻接表, 根据深度优先遍历在邻接表存储结构下的实现算法,写出从顶点 V0 出发按深度优先遍历的顶点序列是 。 3. 已知广义表 A=(9, 7, (8, 10,(99), 16),用求表头 head()和表尾 tail()操作将原子元素 16 从 A 中取出,其操作序列为 。 4. 假设 矩阵元素下标从 1 开始,一个 15 阶的上三角矩阵 A 按行优先顺序压缩存储在一维数组 B 中,则非零元素 A99在 B 中的 下标 k= 。 5. 完全二叉树有 130 个结点,则该二叉树深度为 。 6. n 个结点的线索二叉树上含有的线索数为 。 7. 对有序表 (8,12,25,30,32,38,47,54,62,68,90,95)用折半查找法查找 68,则所需的比较次数为 。 8. 在各种查找方法中,平均查找长度与结点个数无关的查找方法为 。 9. 快速排序在平均情况下的 时 间复杂度为 。 10. 已知一棵二叉树的前序遍历结果为 ABDGCEFH ,中序遍历结果为DGBAECHF,则后序遍历的结果为 。 2018 年天津城建大学攻读硕士学位 研究生入学考试试题( A)卷 考试科目 代码 : 825 考试科目名称 工程信息技术 招生专业: 建筑与土木工程 - - A 卷 试题 第 4 页 共 5 页 三、解答题(本题共 5 小题,每题 10 分,共 50 分) 1. 选取散列函数 H( key) =( key) %11,用线性探测法处理冲突,对关键码序列 1, 47, 7, 29, 11, 3, 8, 10,构造一个散列地址空间为 0 10,表长为 11的散列表,并求查找成功时平均查找长度。 2. 已知无向连通网的顶点数组 vertex6和按权排序的边集数组 edges9 vertex6= edges9=from 1 0 4 2 1 1 2 1 0 to 5 4 5 5 2 4 3 3 3 weight 1 3 4 5 6 6 8 9 10 (1) 顶点分布如下,构造无向连通网。 (2) 根据 Kruskal算法构造最小生成树。 v3v2v4v0v5v13. 已知数据序列为( 13, 2, 6, 20, 5, 9, 18, 10, 1),运用下面算法实现其升序排序 (1) 快速排序的第一趟排序结果(选第一个数据作为轴值)。 (2) 堆排序建立的初始大根堆。 4. 已知 森林 如图所示。 (1) 将森林转为二叉树 , 画图表示 。 (2) 求该 二叉 树的 前 序、中序和后序遍历序列 。 v0 v1 v2 v3 v4 v5 v0 v1 v2 v3 v4 v5 2018 年天津城建大学攻读硕士学位 研究生入学考试试题( A)卷 考试科目 代码 : 825 考试科目名称 工程信息技术 招生专业: 建筑与土木工程 - - A 卷 试题 第 5 页 共 5 页 5. 已知某字符串 S 为“ abcdefgacedaeadcedabadadaeaaddc”,对该字符串用 0, 1进行前缀编码,问该字符串的编码至少有多少位,且每个字符的编码是什么。 在构造哈夫曼树 时,要求 左子树根结点的权小于 等于右子树根结点的权。 四、算法设计题( 本题共 2 小题, 每小题 15 分, 共 30 分 ) 1. ( 15 分) 设计算法求二叉树的度为 1 的结点个数。 typedef struct BiTreeNode /二叉树的结点结构 int data; struct BiTreeNode *lchild, *rchild; *BiTree; 2. ( 15 分)编写算法,利用原有空间,将带头结点的单链表 head 就地逆置。 typedef struct node /单链表的结点结构 int data; struct node *next; LinkList;