《2017年浙江理工大学理学院965软件基础之数据结构考研导师圈点必考题汇编.doc》由会员分享，可在线阅读，更多相关《2017年浙江理工大学理学院965软件基础之数据结构考研导师圈点必考题汇编.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年浙江理工大学理学院965软件基础之数据结构考研导师圈点必考题汇编一、填空题1 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，请在算法，其空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag ，lcft ，data ，right ，rflag ）中：lflag=0，lcft 指向其左孩子，lflag=1，left 指向其前驱：rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。Prior （node , x ） if（node !=null）If （ （1） ） *x=node-right；else * x-nod
2、e-left;next （bt , node, x ）/*bt是二叉树的树根*/ （2） ; if （node-rflag）（3）; else do t=*x；;while （*x=node ）; *x=t; 【答案】nodc-rflag=O; *x=ht; *x=nodc-right; prior （t , X ）2 组成串的数据元素只能是_。【答案】字符 3 已 求REPLACE （S ，V , m ）=_。【答案】 4 栈是_的线性表，其运算遵循_的原则。【答案】操作受限（或限定仅在表尾进行插入和删除操作）；后进先出5 文件由_组成；记录由_组成。【答案】记录；数据项第 2 页，共 56
3、 页知6 已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_。【答案】 【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。7 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_次；当使用监视哨时，若查找失败，则比较关键字的次数为_。【答案】 【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。 8 在有n 个顶点的有向图中，每个顶点的度最大可达。【答案】2（n-l ）【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n-1。9 n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序
4、算法，试补充完整。注：（1）图的顶点号从0开始计；（2）indegree 是有n 个分量的一维数组，放顶点的入度， （3）函数crein 用于记算顶点入度；（4）有三个函数push （data ）, pop（ ）, check（ ）其含义为数据data 入浅，出栈和测试栈是否空（不空返回1, 否则0）。 ） . 【答案】0; j; i; 0; indegreei=0; vexi; k=l; indegreei=0【解析】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的所有元素之和。拓扑排序过程：首先将入度 为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度 减一，然
5、后判断这些顶点的 入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。第 3 页，共 56 页 ；（“图有回路”） 10外排序的基本操作过程是_和_。；归并 【答案】生成有序归并段（顺串）二、选择题11假定主存地址为32位，按字节编址，主存和Cache 之间采用直接映射方式，主存块大小为4个字，每字32位，采用回写（WriteBack ）方式，则能存放4K 字数据的Cache 的总容量的位数至少是（ ）。A.146k B.147K C.148K D.158K 【答案】B【解析】Cache 和主存直接映射方式的规则为：主存储器分为若干区，每个区与缓存容量相同；每个区分为若干数据块，每个
6、块和缓存块容量相同；主存中某块只能映象到Cache 的一个特定的块中。本题中，Cache 总共存放4K 字数据，块大小为4个字，因此cache 被分为4K/4 = 1K 个块，由10位表示。块内共16字节，所以由4位表示，于是标记位为32-10-14= 18位。所以，Cache 的每一行需要包含所存的数据4个字，每个字32位，18位标记位和一个有效位，因此总容=147K。 量为： 12下列有关总线定时的叙述中，错误的是（ ）。A. 异步通信方式中，全互锁协议最慢 B. 异步通信方式中，非互锁协议的可靠性最差 C. 同步通信方式中，同步时钟信号可由多设备提供 D. 半同步通信方式中，握手信号的采样由同步时钟控制 【答案】C【解析】A 项正确，异步通信方式中，全互锁协议最慢，主从模块都需要等待确认后才能撤销其信号；B 项正确，异步通信方式中，非互锁协议没有相互确认机制，因此可靠性最差；C 项错误，同步通信要遵循统一的时钟信号，不能由多设备提供；D 项正确，半同步通信方式中，握手信号的采样由同步时钟控制。 第 4 页，共 56 页一、填空题考研试题
