2018年江苏省培养单位南京天文光学技术研究所864程序设计之数据结构考研基础五套测试题-一、单项选择题1 下列文件物理结构中，适合随机访问且易于文件扩展的是（ ）.A. 连续结构B. 索引结构C. 链式结构且磁盘块定长D. 链式结构且磁盘块变长【答案】B【解析】连续结构的优点是结构简单，缺点是不易于文件扩展，不易随机访问. 链式结构的优点是文件易于扩展，缺点是不易随机访问. 索引结构的优点是具有链式结构的优点并克服了它的缺点，可随机存取，易于文件扩展. 2 以下数据结构中，（ ）是非线性数据结构。A. 树B. 字符串C. 队D. 栈【答案】A【解析】非线性结构是指存在一对多或者多对一的关系。常见的非线性结构有树结构和图结构。 3 假定下列指令已装入指令寄存器。则执行时不可能导致CPU 从用户态变为内核态(系统态) 的是（ ）。 A.B. ; 产生软中断 C. ; 寄存器R0的内容取非 D.MOVRO , addr ; 把地址处的内存数据放入寄存器RO 中【答案】C【解析】A 项, 除法操作出现除数为零的情况时, 会产生内中断, CPU 切换为内核态进行中断处理; B 项, 直接产生中断, 会切换到内核态; D 项, addr 出现非法地址, 会出现中断, 进而切换到内核态。 4 若一个栈以向量 存储，初始栈顶指针top 为n+1，则下面X 入栈的正确操作是（ ）。A.top :top l ；Vtop:xB.Vtop:x ；top :top lC.top :top l ；Vtop:xD.Vtop:x ；top :top l【答案】C【解析】题中初始栈顶指针top 为n 1，而栈顶指针又位于最大下标以上，此时入栈应进行先减一操作。 5 下列关于闪存(FlashMemory)的叙述中, 错误的是（ ）。A. 信息可读可写, 并且读、写速度一样快B. 存储元由MOS 管组成, 是一种半导体存储器C. 掉电后信息不丢失, 是一种非易失性存储器D. 采用随机访问方式, 可替代计算机外部存储器【答案】A 。【解析】考查闪存的特性, 闪存是EEPROM 的进一步发展, 可读可写, 用MOS 管的浮栅上有无电荷来存储信息, 它依然是ROM 的一种, 故写速度比读速度要慢不少。闪存是一种非易失性存储器, 它采用随机访问方式, 现在常见的SSD 固态硬盘就是由flash 芯片组成的, 故答案为A 。 6 在文件的索引节点中存放直接索引指针10个, 一级二级索引指针各1个, 磁盘块大小为1KB 。每个索引指针占4个字节。若某个文件的索引节点已在内存中, 到把该文件的偏移量(按字节编址) 为1234和307400处所在的磁盘块读入内存。需访问的磁盘块个数分别是（ ）。A.1, 2B.1, 3C.2, 3D.2, 4【答案】B【解析】文件的索引结点的直接索引指针有10个, 因此直接索引的偏移量范围是0?2559, 一级索引的偏移量范围是2560?65791, 二级索引访问的偏移量范围是65792?45183907。偏移量1234可以通过直接索引得到在磁盘块的地址, 因此需要一次访问, 307400需要通过二级索引查找其在磁盘的位置, 需要分别访问存放二级索引的两个索引块以及对应的数据块。 7 下列说法不正确的是（ ）。A. 图的遍历是从给定的源点出发每个顶点仅被访问一次B. 遍历的基本方法有两种:深度遍历和广度遍历C. 图的深度遍历不适用于有向图D. 图的深度遍历是一个递归过程【答案】C【解析】图的遍历是指从图中的某一个顶点出发，按照某种搜索算法沿着图中的边对图中的所有顶点访问一次且仅访问一次。图的深度遍历类似于树的先序遍历，不仅适合无向图，也适合于有向图。 8 下列线索二叉树中(用虚线表示线索) , 符合后序线索树定义的是（ ）。 【答案】D【解析】线索二叉树利用二叉链表的空链域来存放结点的前驱和后继信息, 解题思路较简单。题中所给二叉树的后序序列为dbca 。结点d 无前驱和左子树, 左链域空, 无右子树, 右链域指向其后继结点b ; 结点b 无左子树, 左链域指向其前驱结点d ; 结点c 无左子树, 左链域指向其前驱结点b , 无右子树, 右链域指向其后继结点a 。所以正确选项为D 。 9 向一个栈顶指针为h 的带头结点的链栈中插入指针S 所指的结点时，应执行（ ）。A.h next s ；B.s next h ；C.s next h ；h next s ；D.s next h next ；h next s ；【答案】D【解析】本题是向一个链栈中插入结点，可从头结点后插入。先将s 结点指向第一个头结点之后的结点之前，再将头结点指向s 结点。 10若一棵二叉树的前序遍历序列为a , e , b , d , c , 后序遍历序列为b , c , d , e , a , 则根结点的孩子结点（ ）。A. 只有eB. 有e 、bC. 有e 、cD. 无法确定-一、单项选择题-考研试题-