《2018年天津职业技术师范大学信息技术工程学院813程序设计基础之数据结构考研仿真模拟五套题.doc》由会员分享，可在线阅读，更多相关《2018年天津职业技术师范大学信息技术工程学院813程序设计基础之数据结构考研仿真模拟五套题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2018年天津职业技术师范大学信息技术工程学院813程序设计基础之数据结构考研仿真模拟五套题一、填空题1 循环队列的引入，目的是为了克服_。【答案】假溢出时大量移动数据元素【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。 2 设有一个空枝，栈顶指针为1000H(十六进制) ，现有输入序列为1，2，3，4，5，经过PUSH ，PUSH ，POP ，PUSH ，POP ，PUSH ，PUSH 之后，输出序列是_，而栈顶指针值是_。设栈为顺序找，每个元素占4个字节。
2、【答案】23；100CH 3 索引顺序文件既可以顺序存取，也可以 _存取。【答案】随机 4 VSAM(虚拟存储存取方法) 文件的优点是:动态地_，不需要文件进行_，并能较快地_进行查找。【答案】分配和释放存储空间；重组；对插入的记录 5 起始地址为480，大小为8的块，其伙伴块的起始地址是_；若块大小为32, 则其伙伴块的起始地址为_; 。【答案】480+8=488，48032=448【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下: 根据上述公式起始地址就为488。 6 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_，在给定值为x
3、 的结点后插入一个新结点的时间复杂度为_。【答案】O(1)；O(n)【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。 7 设有N 个结点的完全二叉树顺序存放在向量【答案】 中，其下标值最大的分支结点为_。【解析】最大的分支结点是最后一个叶子结点的父结点。 8 设二维数组A 的行和列的下标范围分别为0:8和0:10，每个元素占2个单元，按行优先顺序存储，第一个元素的存储起始位置为b ，则存储位置为b+50处的元素为_。【答案】A23【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是(ll*ij l l)*2b 。当其值为b 50时，则i 2，j 3。
4、 9 设广义表L (（ ），（ ）) ，则head(L)是_tail(L)是_L的长度是_；深度是_。【答案】（ ）；(（ ）) ；2；2【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。 10若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 _和记录的_。【答案】比较；移动 二、单项选择题11某同步总线的时钟频率为100MHz , 宽度为32位, 地址/数据线复用, 每传输一个地址或数据占用一个时钟周期。若该总线支持突发(猝发) 传输方式, 则一次“主存写”总线事务传输128位数据所需
5、要的时间至少是（ ）。A.20nsB.40nsC.50nsD.80ns【答案】C 。【解析】总线的时钟频率为100MHz , 则时钟周期为10ns 。数据是128位, 总线宽度是32位, 所以需要4个时钟周期, 而传输地址还需要一个周期, 所以传输一个128位的数据至少需要5个时钟周期, 所以至少需要。 12下述二叉树中，哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ ）。A. 二叉排序树B. 哈夫曼树C.A VL 树D. 堆【答案】D【解析】堆的定义:n 个关键字序列K 1，K 2，. ，K n 称为堆，当且仅当该序列满足如下性质(简称为堆性质) :(1)(2)且
6、且或 满足第(1)种情况的堆，称为小顶堆；满足第(2)种情况的堆，称为大顶堆。由堆的定义可知堆可以满足上述性质。 13若对如下无向图进行遍历, 则下列选项中, 不是广度优先遍历序列的是（ ） A.h , c , a , b , d , e , g , fB.e , a , f , g , b , h , c , dC.d , b , c , a , h , e , f , gD.a , b , c , d , h , e , f , g【答案】D【解析】根据广度优先遍历的定义, 可知选项A 、B 、C 都为广度优先遍历, 而选项D 是深度优先遍历而不是广度优先遍历, 故答案为D 。 14下列排序算法中，其中（ ）是稳定的。A. 堆排序，起泡排序B. 快速排序，堆排序C. 直接选择排序，归并排序D. 归并排序，起泡排序【答案】D 15对（ ）。A. 该树一定是一棵完全二叉树B. 树中一定没有度为1的结点C. 树中两个权值最小的结点一定是兄弟结点个权值均不相同的字符构成哈夫曼树。下列关于该哈夫曼树的叙述中, 错误的是一、填空题考研试题
