《2018年浙江大学计算机科学与技术学院408计算机学科专业基础综合之数据结构考研核心题库.doc》由会员分享，可在线阅读，更多相关《2018年浙江大学计算机科学与技术学院408计算机学科专业基础综合之数据结构考研核心题库.doc（5页珍藏版）》请在金锄头文库上搜索。
1、2018年浙江大学计算机科学与技术学院408计算机学科专业基础综合之数据结构考研核心题库-一、算法设计题1 已知两个线性表A , B 均以带头结点的单链表作存储结构，且表中元素按值递增有序排列。设计算法求出A 与B 的交集C ，要求C 另开辟存储空间。，并同样以元素值的递增有序的单链表形式存储。【答案】算法如下: /线性表A 和B 以带头结点的单链表作为存储结构。本算法求A 和B 的交集C , C 另辟空间 /pa、pb 是两链表的工作指针 /监视哨 /pa指针后移 /pb指针后移 /处理交集元素 /删除重复元素 /交集元素并入结果表 /置结果链表尾 2 设从键盘输入一整数的序列:a 1，a
2、2，a 3，. ，a n ，试编写算法实现:用栈结构存储输入的整数，当时，将入栈；当时，输出栈顶整数并出栈。算法应对异常情况(入栈满等) 给出相应的信息。【答案】算法如下:栈空间容量 /s是元素为整数的栈，本算法进行入栈和出栈操作 /top为栈顶指针，定义top 0时为栈空 /n个整数序列进行处理/从键盘读入整数序列 /读入的整数不等于1时人栈 /读入的整数等于1时出栈 /算法结束。 3 试编写在带头结点的单链表中删除(一个) 最小值结点的(高效) 算法。delete(Linklist&L)【答案】算法如下: /L是带头结点的单链表，本算法删除其最小值结点 /P为工作指针。指向恃处理的结点。假
3、定链表非空 /pre指向最小值结点的前驱 /q指向最小值结点，初始假定第一元素结点是最小值结点 /查最小值结点 /指针后移 /从链表上刪除最小值结点 /释放最小值结点空间 /结束算法Delete 4 编写一算法，利用叶结点中的空指针域将所有叶结点链接为一个带有头结点的双链表，算法返回头结点的地址。【答案】算法如下:全局变量链表头指针将若bt 不空 中序遍历左子树 叶结点 第一个叶结点 生成头结点 头结点的左链空，右链指向第一个结点 第一个叶结点左链指向头结点，pre 指向当前叶结点 中序遍历右子树树中的所有叶结点链成带头结点的双链表当前叶结点链入双链表 最后一个叶结点的右链置空(链表结束标记)
4、 结束； 5 已知指针P 指向带表头的中根次序线索二叉树中的某结点，试写一算法FFA(P，q) , 该算法寻找结点P 的父亲结点q 。设线索二叉树的结点结构、表头结点结构和空树结构分别为(LTAG，LLINK ，INFO , RL1NK ，RTAG) ，且规定线索树的最左下结点的LLINK 域和最右下结点的RLINKt 域指向表头。【答案】算法如下: 在中序线索树t 上，求结点p 的双亲结点q暂存 找P 的中序最右下的结点 顺右线索找到q 的后继(P的袓先结点) 若后继是头结点，则转到根结点根结点无双亲 找最右结点的过程中回找到P结束FFA准备到左子树中找P 二、应用题6 某32位计算机, C
5、PU 主频为800MHz , Cache 命中时的CPI 为4, Cache 块大小为32字节; 主存采用8体交叉存储方式, 每个体的存储字长为32位、存储周期为40ns ; 存储器总线宽度为32位, 总线时钟频率为200MHz , 支持突发传送总线事务。每次读突发传送总线事务的过程包括:送首地址和命令、存储器准备数据、传送数据。每次突发传送32字节, 传送地址或32位数据均需要一个总线时钟周期。请回答下列问题, 要求给出理由或计算过程。(1)CPU和总线的时钟周期各为多少？总线的带宽(即最大数据传输率) 为多少？(2)Cache缺失时, 需要用几个读突发传送总线事务来完成一个主存块的读取？(3)存储器总线完成一次读突发传送总线事务所需的时间是多少？(4)若程序BP 执行过程中, 共执行了100条指令, 平均每条指令需进行为, 不考虑替换等开销, 则BP 的CPU 执行时间是多少？【答案】(1)因为CPU 主频为800MHz , 故CPU 的时钟周期为:总线时钟频率为200MHz , 故总线的时钟周期为:总线宽度为块。次访存, Cache 缺失率。 。 。 , 故总线带宽为(2)因为Cache 块大小为32B , 因此Cache 缺失时需要一个读突发传送总线事务读取一个贮存-一、算法设计题-考研试题-
