2018 年天津城建大学攻读硕士学位研究生入学考试试题 (A) 卷考试科目代码 :825 考试科目名称工程信息技术招生专业 : 建筑与土木工程

Size: px

Start display at page:

Download "2018 年天津城建大学攻读硕士学位研究生入学考试试题 (A) 卷考试科目代码 :825 考试科目名称工程信息技术招生专业 : 建筑与土木工程"

讨绫家
4 years ago
Views:

1 一单项选择题 ( 本题共 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 设串 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 的范围从 0~8, 列下标 j 的范围从 1~10 若 A 按行存放, 元素 A[8][5] 的起始地址与 A 按列存放时元素 ( ) A 卷试题第 1 页共 5 页

2 的起始地址一致 A. A[8][5] B. A[3][10] C. A[5][8] D. A[0][9] 9. 深度为 k 的完全二叉树至少有 m 个结点, 至多有 n 个结点,m 和 n 分别为 ( ) A. 2 k-1 和 2 k -1 B. 2 k-1-1 和 2 k C. 2 k-1-1 和 2 k -1 D. 2 k-1 和 2 k 10. 一棵完全二叉树上有 1001 个结点, 其中叶子结点个数是 ( ) A. 501 B. 500 C. 250 D 用邻接矩阵表示图进行广度优先遍历时, 通常是采用 ( ) 来实现算法 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 下述几种排序方法中, 不稳定的是 ( ) A. 直接插入排序 B. 快速排序 C. 归并排序 D. 起泡排序 15. 对关键字值序列 {74, 73, 71, 26, 99, 16, 5, 68, 76, 100}, 构建初始堆, 必须从关键字为 ( ) 的结点开始 A. 100 B. 74 C. 99 D 散列法存储中, 处理冲突的两类主要方法是 ( ) A. 线性探查法和双散列函数法 B. 建溢出区法和不建溢出区法 C. 除余法和折叠法 D. 拉链法和开放地址法 17. 长度为 12 的有序表采用顺序存储结构, 运用折半查找技术, 等概率情况下, 查找失败的平均查找长度为 ( ) A. 37/12 B. 62/13 C. 39/12 D. 49/ 对一组记录 (68,10,96,45,26,66,52,46,84) 进行直接插入排序, 当把第 6 个记录 66 插入到有序表时, 为寻找插入位置需比较 ( ) 次 A. 1 B. 2 C. 3 D 按关键码集合 {5, 3, 7, 1, 2, 9, 8, 10, 4, 6} 建立二叉排序树, 然后查找 2, 成功时比较次数为 ( ) A. 1 B. 2 C. 3 D 利用快速排序对下列数据序列进行排序, 速度最快的是 ( ) 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 A 卷试题第 2 页共 5 页

3 二填空题 ( 本题共 10 题, 每题 3 分, 共 30 分 ) 1. 下列程序段中 S 语句的执行频度为 for(i=2; i<=n; ++i) for(j=2; j<i; ++j) S; 2. 已知一个图的邻接表, 根据深度优先遍历在邻接表存储结构下的实现算法, 写出从顶点 V0 出发按深度优先遍历的顶点序列是 3. 已知广义表 A=(9, 7, (8, 10,(99)), 16), 用求表头 head() 和表尾 tail() 操作将原子元素 16 从 A 中取出, 其操作序列为 4. 假设矩阵元素下标从 1 开始, 一个 15 阶的上三角矩阵 A 按行优先顺序压缩存储在一维数组 B 中, 则非零元素 A[9][9] 在 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, 则后序遍历的结果为 A 卷试题第 3 页共 5 页

4 三解答题 ( 本题共 5 小题, 每题 10 分, 共 50 分 ) 1. 选取散列函数 H(key)=(key)%11, 用线性探测法处理冲突, 对关键码序列 1,47,7,29,11,3,8,10, 构造一个散列地址空间为 0~10, 表长为 11 的散列表, 并求查找成功时平均查找长度 2. 已知无向连通网的顶点数组 vertex[6] 和按权排序的边集数组 edges[9] vertex[6]= v0 v1 v2 v3 v4 v5 edges[9]=from to weight (1) 顶点分布如下, 构造无向连通网 (2) 根据 Kruskal 算法构造最小生成树 v5 v4 v1 v0 v2 v3 3. 已知数据序列为 (13,2,6,20,5,9,18,10,1), 运用下面算法实现其升序排序 (1) 快速排序的第一趟排序结果 ( 选第一个数据作为轴值 ) (2) 堆排序建立的初始大根堆 4. 已知森林如图所示 (1) 将森林转为二叉树, 画图表示 (2) 求该二叉树的前序中序和后序遍历序列 A 卷试题第 4 页共 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; A 卷试题第 5 页共 5 页

Microsoft Word - 专升本练习5：图.doc

Microsoft Word - 专升本练习5：图.doc 第五章图一选择题 1. 关键路径是事件结点网络中的 ( ) A. 从源点到汇点的最长路径 B. 从源点到汇点的最短路径 C. 最长的回路 D. 最短的回路 2. 一个具有 n 个顶点和 e 条边的无向图, 采用邻接表表示, 表向量的大小为 ( 1 ), 所有顶点邻接表的结点总数为 ( 2 ) 1A. n B. n+1 C. n-1 D. n+e 2A. e/2 B. e C. 2e D. n+e

2018 年天津城建大学攻读硕士学位研究生入学考试试题 (A) 卷 考试科目代码 :825 考试科目名称工程信息技术 招生专业 : 建筑与土木工程

2018 年天津城建大学攻读硕士学位研究生入学考试试题 (A) 卷考试科目代码 :825 考试科目名称工程信息技术招生专业 : 建筑与土木工程