重庆邮电大学

Size: px

Start display at page:

Download "重庆邮电大学"

忘髦谈
4 years ago
Views:

1 机密启用前重庆邮电大学 2019 年攻读硕士学位研究生入学考试试题科目名称 : 数据结构 (A) 科目代码 : 802 考生注意事项 1 答题前, 考生必须在答题纸指定位置上填写考生姓名报考单位和考生编号 2 所有答案必须写在答题纸上, 写在其他地方无效 3 填 ( 书 ) 写必须使用 0.5mm 黑色签字笔 4 考试结束, 将答题纸和试题一并装入试卷袋中交回 5 本试题满分 150 分, 考试时间 3 小时注 : 所有答案必须写在答题纸上, 试卷上作答无效! 第 1 页 ( 共 8 页 )

2 一选择题 ( 本大题共 10 小题, 每小题 2 分, 共 20 分 ) 1. 对于双向循环链表, 每个结点有两个指针域 next 和 prior, 分别指向前驱和后继在 p 指针所指向的结点之后插入 s 指针所指结点的操作应为 ( ) A. p->next = s; s->prior = p; p->next->prior = s; s->next = p->next; B. p->next = s; p->next->prior = s; s->prior = p; s->next = p->next; C. s->prior = p; s->next = p->next; p->next = s; p->next->prior = s; D. s->prior = p; s->next = p->next; p->next->prior = s; p->next = s; 2. 由 abc,3 个结点可以构造出多少种不同的二叉树?( ) A. 2 B. 3 C. 4 D 设有数组 A[i,j], 数组的每个元素长度为 3 字节,i 的值为 1 到 8,j 的值为 1 到 10, 数组从内存首地址 BA 开始顺序存放, 当用以列为主存放时, 元素 A[5, 8] 的存储首地址为 ( ) A. BA+141 B. BA+180 C. BA+222 D. BA 一个栈的输入序列为 1 2 3, 则下列序列中不可能是栈的输出序列的是 ( ) A B C D 下述编码中哪一个不是前缀码 ( ) A.(00,01,10,11) C.(0,10,110,111) B.(0,1,00,11) D.(1,01,000,001) 6. 当一棵有 n 个结点的二叉树按层次从上到下, 同层次从左到右将数据存放在一维数组 A[l..n] 中时, 数组中第 i 个结点的左孩子为 ( ) A. A[2i](2i=<n) B. A[2i+1](2i+1=< n) C. A[i/2] D. 无法确定 7. 假设一个有 n 个顶点和 e 条弧的有向图用邻接表表示, 则删除与某个顶点 vi 相关的所有弧的时间复杂度是 ( ) A. O(n) B. O(e) C. O(n+e) D. O(n*e) 注 : 所有答案必须写在答题纸上, 试卷上作答无效! 第 2 页 ( 共 8 页 )

3 8. 串的长度是指 ( ) A. 串中所含不同字母的个数 B. 串中所含字符的个数 C. 串中所含不同字符的个数 D. 串中所含非空格字符的个数 9. 循环队列存储在数组 A[0..m] 中, 则入队时的操作为 ( ) A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 10. 关键路径是事件结点网络中 ( ) A. 从源点到汇点的最长路径 B. 从源点到汇点的最短路径 C. 最长回路 D. 最短回路二填空题 ( 本大题共 15 小题, 每空 2 分, 共 40 分 ) 1. 中缀算式 (3+4X)-2Y/3 对应的后缀算式为 2. 在完全二叉树中, 编号为 i 和 j 的两个结点处于同一层的条件是 3. 构造 n 个结点的强连通图, 至少有条弧 4. 设有一个空栈, 栈顶指针为 1000H( 十六进制 ), 现有输入序列为 a,b,c,d, e. 经过 PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH 之后, 输出序列是, 而栈顶指针值是 H 设栈为顺序栈, 每个元素占 4 个字节 5. 若串 S1= ABCDEFG, S2= 9898,S3= ###,S4= , 执行 concat(replace(s1,substr(s1,length(s2),length(s3)),s3),substr(s4,index(s2, 8 ),lengt h(s2))), 其结果为 6. 若一组记录的排序码为 (46,79,56,38,40,84), 则利用堆排序的方法建立的初始堆为 7. 在有序表 (12,24,36,48,60,72,84) 中二分查找关键字 72 时所需进行的关键字比较次数为 8. 有向图的边集为 {<a, c>,<a, e>, <e, b>, <e, d>, <b, d>, <d, c), <c, f>, 该图的一注 : 所有答案必须写在答题纸上, 试卷上作答无效! 第 3 页 ( 共 8 页 )

4 个拓扑排序为 : 9. 当输入序列局部有序或元素个数较小时, 在快速排序选择排序插入排序归并排序堆排序中, 最佳的排序方法是 10. 假设两个队列共享一个循环向量空间 ( 参见右图 ), 其类型 Queue2 定义如下 : typedef struct{ DateType data[maxsize]; int front[2],rear[2]; Queue2; 对于 i=0 或 1,front[i] 和 rear[i] 分别为第 i 个队列的头指针和尾指针请对以下算法填空, 实现第 i 个队列的入队操作 int EnQueue (Queue2 *Q, int i, DateType x) {// 若第 i 个队列不满, 则元素 x 入队列, 并返回 1; 否则返回 0 if( i<0 i>1 ) return 0; if( Q->rear[i] == Q->front[ ] ) return 0; Q->data[ ] = x; Q->rear[i] = [ ]; return1; 11. 高度为 8 的平衡二叉树的结点数至少有个 12. 文件由组成 ; 记录由组成 13. 对于一个具有 n 个结点的单链表, 在已知的结点 *p 后插入一个新结点的时间复杂度为, 在给定值为 x 的结点后插入一个新结点的时间复杂度为 14. 在 n 个记录的有序顺序表中进行折半查找, 最大比较次数是注 : 所有答案必须写在答题纸上, 试卷上作答无效! 第 4 页 ( 共 8 页 )

5 15. 求从某源点到其余各顶点的 Dijkstra 算法在图的顶点数为 10, 用邻接矩阵表示图时计算时间约为 10ms, 则在图的顶点数为 40, 计算时间约为 ms 三问答题 ( 本大题共 6 小题, 每小题 10 分, 共 60 分 ) 1. 一个线性表为 B=(12,23,45,57,20,03,78,31,15,36), 设散列表为 HT[0..12], 散列函数为 H(key)= key % 13 并用线性探查法解决冲突, 请画出散列表, 并计算等概率情况下查找成功的平均查找长度 2. 已知二叉树的存储结构为二叉链表, 阅读下面算法 typedef struct node { DateType data; Struct node * next; ListNode; typedef ListNode * LinkList; LinkList Leafhead = NULL; Void Inorder (BinTree T) { LinkList s; If(T){ Inorder(T->lchild); If ((!T->lchild)&&(!T->rchild)) { s=(listnode*)malloc(sizeof(listnode)); s->data=t->data; s->next=leafhead; Leafhead=s; Inorder(T->rchild); 注 : 所有答案必须写在答题纸上, 试卷上作答无效! 第 5 页 ( 共 8 页 )

6 对于如下所示的二叉树 (1) 画出执行上述算法后所建立的结构 (2) 说明该算法的功能 3. 假设以 I 和 O 分别表示入栈和出栈操作栈的初态和终态均为空, 入栈和出栈的操作序列可表示为仅由 I 和 O 组成的序列, 称可以操作的序列为合法序列, 否则称为非法序列 (1) 下面所示的序列中哪些是合法的? A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO (2) 通过对 (1) 的分析, 写出一个算法, 判定所给的操作序列是否合法 ( 假定被判定的操作序列已存入一维数组 char A[ ] 中, 若操作序列合法, 返回 true, 否则返回 false) 4. 已知一个连通图如下图所示, 试给出图的邻接矩阵和邻接表存储示意图, 若从顶点 v1 出发对该图进行遍历, 分别给出一个按深度优先遍历和广度优先遍历的顶点序列. (1) 图的邻接矩阵 (2) 邻接表存储示意图 (3) 从 v1 开始的深度优先遍历的顶点序列 (4) 分析在深度遍历过程中, 分别使用邻接矩阵和邻接表存储的算法复杂度 (5) 讨论在图遍历问题中, 这两种存储方式的优劣 5. 一棵二叉树的先序序列为 ABCDGEF, 中序序列为 CBDGAFE (1) 请画出该二叉树注 : 所有答案必须写在答题纸上, 试卷上作答无效! 第 6 页 ( 共 8 页 )

7 (2) 将二叉树转换为相应的森林 6. 请阅读下列算法, 回答问题 sort(r, n) { for (i=2; i<=n; i++) { x=r(i); r(0)=x; j=i-1; while( x<r(j) ) { r(j+1)=r(j); j=j-1; r(j+1)=x; (1) 这是什么类型的排序算法, 该排序算法稳定吗? (2) 设置 r(0) 的作用是什么? (3) 若将 while 语句中判断条件改为 x<=r(j), 该算法将会有什么变化? (4) 若将 while 语句中判断条件改为 x<=r(j), 该算法是否还能正确工作? 四程序设计题 ( 本大题共 2 小题, 每小题 15 分, 共 30 分 ) 1. 设有大小不等的 n 个数据组, 其数据总量为 m, 顺序存放在空间区 D 内, 每个数据占一个存储单元, 数据组的首地址由数组 S 给出,( 如下图所示 ), 试编写将新数据 x 插入到第 i 个数据组的末尾且属于第 i 个数据组的算法, 插入后, 空间区 D 和数组 S 的相互关系仍保持正确注 : 所有答案必须写在答题纸上, 试卷上作答无效! 第 7 页 ( 共 8 页 )

8 2. 快速排序算法中, 如何选取一个界值 ( 又称为轴元素 ), 影响着快速排序的效率, 而且界值也并不一定是被排序序列中的一个元素例如, 我们可以用被排序序列中所有元素的平均值作为界值用 C 语言编写算法实现以平均值为界值的快速排序方法 ( 注 : 待排序数据存储在数组 R[ ] 中, 数组最小下标为 S, 数组最大下标为 T) 注 : 所有答案必须写在答题纸上, 试卷上作答无效! 第 8 页 ( 共 8 页 )

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

2018 年天津城建大学攻读硕士学位研究生入学考试试题 (A) 卷考试科目代码 :825 考试科目名称工程信息技术招生专业 : 建筑与土木工程一单项选择题 ( 本题共 20 小题, 每题 2 分, 共 40 分 ) 1. 计算机所处理的数据一般具有某种内在联系, 这是指 ( ) A. 数据和数据之间存在某种联系 B. 数据项和数据项之间存在某种联系 C. 元素内部具有某种结构 D. 元素和元素之间存在某种联系 2. 在计算机中表示数据时, 数据的物理地址和逻辑地址相同并且连续, 称其为 ( ) A. 链式存储结构 B. 顺序存储结构 C.

重 庆 邮 电 大 学

重庆邮电大学