《2018年上海市培养单位上海高等研究院866计算机原理之数据结构考研基础五套测试题.doc》由会员分享，可在线阅读，更多相关《2018年上海市培养单位上海高等研究院866计算机原理之数据结构考研基础五套测试题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2018年上海市培养单位上海高等研究院866计算机原理之数据结构考研基础五套测试题一、填空题1 一棵有11个结点的满二叉树有_个度为1的结点、有_个分支(非终端) 结点和_个叶子，该满二叉树的深度为_。 【答案】或【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。 2 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_，又称P 为_。【答案】模式匹配；模式串 3 堆是一种有用的数据结构。堆排序是一种_排序，堆实质上是一棵_结点的层次序列。对含有N 个元素的序列进行排序时，堆排序的时间复杂度是_，所需的附加存储结点是_。关键码序列05, 23, 16, 68
2、, 94, 72, 71, 73是否满足堆的险质_ 。【答案】选择；完全二叉树；O(1)；满足堆的性质 4 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 _和记录的_。【答案】比较；移动 5 起始地址为480，大小为8的块，其伙伴块的起始地址是_；若块大小为32, 则其伙伴块的起始地址为_; 。【答案】480+8=488，48032=448【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下: 根据上述公式起始地址就为488。 6 设单链表的结点结构为(data，next) ，next 为指针域，已知指针px 指向单链表中data 为x 的结点，指针py
3、 指向data 为y 的新结点，若将结点y 插入结点x 之后，则需要执行以下语句: _；_；【答案】py next px next ；px next py 7 循环队列的引入，目的是为了克服_。【答案】假溢出时大量移动数据元素【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。 8 文件由_组成；记录由_组成。【答案】记录；数据项 9 在n 个顶点的非空无向图中，最多有_个连通分量。【答案】n【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。 1
4、0VSAM(虚拟存储存取方法) 文件的优点是:动态地_，不需要文件进行_，并能较快地_进行查找。【答案】分配和释放存储空间；重组；对插入的记录 11在拓扑分类中，拓扑序列的最后一个顶点必定是_的顶点。【答案】出度为0【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最后一个顶点的出度必定为零。 12在有n 个顶点的有向图中，每个顶点的度最大可达_。【答案】2(n1)【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n 1。 二、单项选择题13下列调整中, 不可能导致饥饿现象的是（ ）A. 时间片转移B. 静态优先及调度C. 非抢占式作业
5、优先D. 抢占式短作业优先【答案】A【解析】时间片转移方法能在一个周期内使每个进程都得到一个时间片的CPU 使用时间, 不会产生饥饿的现象, 其余三个都会产生饥饿。 14某计算机存储器按字节编址, 主存地址空间大小为64MB ,现用32MB 的主存储器, 则存储器地址寄存器MAR 的位数至少是（ ）。A.22位B.23位C.25位D.26位【答案】D 位的RAM 芯片组成【解析】虽然实际的主存储器(RAM区) 只有32MB , 但不排除还有ROM 区, 考虑到存储器扩展的需要, MAR 应保证能访问到整个主存地址空间。因为主存的地址空间大小为64MB , 所以MAR 的位数至少需要26位。 1
6、5循环队列A0.m1存放其元素值，用front 和rear 分别表示队头和队尾，则当前队列中的元素数是（ ）。A.(rearfront m)%mB.rear front 1C.rear front 1D.rear front【答案】A【解析】对于循环队列，需要深刻理解队头(font)和队尾(rear)的概念，在队头进行出队操作，在队尾进行进队操作。rear-front 可能为正也可能为负，为正时元素个数(rear-front)；如果为负则元素的个数(rear-front+m)，所以统一的公式就是(rear-front+m)%m。 16若下图为10BaseT 网卡接收到的信号波形, 则该比特串是（ ） A.00110110B.10101101C.01010010D.11000101【答案】A【解析】以太网采用曼彻斯特编码, 其将一个码元分成两个相等的间隔, 前一个间隔为高电平而后一个间隔为低电平表示1, 反之则表示0。故根据波形图, 可得答案为A 。 17下面关于串的叙述中，不正确的是（ ）。A. 串是字符的有限序列B. 空串是由空格构成的串一、填空题考研试题
