《2017年中南民族大学计算机科学学院842数据结构考研仿真模拟题.doc》由会员分享，可在线阅读，更多相关《2017年中南民族大学计算机科学学院842数据结构考研仿真模拟题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年中南民族大学计算机科学学院842数据结构考研仿真模拟题一、填空题1 在进行入栈运算时应先判别栈是否_:在进行出栈运算时应先判别栈是否_:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_分别设在内存空间的两端，这样只有当_时才产生溢出。【答案】满；空；n ; 栈底；两栈顶指针相邻（即值之差的绝对值为1） 2 一个算法具有5个特性：_、_、_、有零个或多个输入、有一个或多个输出。【答案】有穷性；确定性；可行性3 顺序栈用【答案】存储数据，栈顶指针是top ，则值为x 的元素入栈的操
2、作是_。 【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。4 在循环队列中，队列长度为n ，存储位置从0到，编号，以rear 指示实际的队尾元素，现要在此队列中插入一个新元素，新元素的位置是（ ）。【答案】 5 对n 个记录的表rl.n进行简单选择排序，所需进行的关键字间的比较次数为_。【答案】n （n-1）/2【解析】第一次需要n-1次比较，第i 此需要n-i 此比较，所以共需要、n-l+n-2+.+l=n（n-l ）/2。 6 检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_检索。也可以按_检索；按_检索又可以有_检索和_检索。【答案】关键字；记录号；记录号
3、；顺序；直接 7 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。 【答案】 【解析】快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 8 设有一个空找，栈顶指针为1000H （十六进制），现有输入序列为1，2，3, 4, 5，经过PUSH ，PUSH , POP , PUSH , POP ，PUSH ，PUSH 之后，输出序列是_，而栈顶指针值是_。设栈为顺序栈，每个元素占4个字节。【答案】23; 100CH 9 索引顺序文件既可以顺
4、序存取，也可以_存取。【答案】随机10棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_个结点。【答案】树。故结点个数为 【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉二、选择题11对一组数据（2, 12, 16, 88, 5，10）进行排序，若前三趟排序结果如下：第一趟：2，12，16, 5，10，88第二趟：2，12，5，10，16, 88 第三趟：2，5，10，12，16, 88 则采用的排序方法可能是（ ）。 A. 起泡排序B. 希尔排序 C. 归并排序 D. 基数排序 【答案】A【解析】题目中所给的三趟排序过程，显然是使用起泡
5、排序方法，每趟排序时从前往后依次，待序列中的记录“基比较，使大值“沉底”。希尔排序的基本思想是：先对序列进行“宏观调整”本有序”时再进行直接插入排序。宏观调整的方法是：通过某种规则将大的待排序序列分割为若干小的待排序序列，再依次对这些小的序列直接插入排序。宏观调整可以多次，每次分割的序列数逐渐増多，而每个序列中所包含的元素数逐渐减少。归并排序的基本操作是将多个小的有序序，直至整个序列为有序为止。 基数排序是分配排列合并为一个大的有序序列，然后“逐趟归并”序的一种，这类排序不是通过关键字比较，而是通过“分配”和“收集”过程来实现排序的。 本，显然使用的是起泡排序法。 题中，很容易看出大值逐渐“沉
6、底” 12分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（ ）。 【答案】C【解析】二叉排序树：左右子树都是二叉排序树，且保证右子树都比根结点大，左子树都比根结点小。据以上两点建立二叉排序树。 13使用浏览器访问某大学Web 网站主页时，不可能使用的协议是（ ）A.PPP B.ARP C.UDP D.SMTP 【答案】D【解析】SMTP 是简单邮件传输协议，访问主页时并不涉及邮件相关协议。14已知一棵有2011个结点的树，其叶结点个数为116, 该树对应的二叉树中无右孩子的结点个数是（ ）。A.115 B.116 C.1895 D.1896 【答案】D【解析】每个非终端结点转换成二叉树后都对应一个无右孩子的结点（因为一个非终端结点，另外，树根结点转至少有一个孩子结点，其最右边的孩子结点转换成二叉树后一定没有右孩子）换成二叉树后也没有右孩子。题目中树的总结点数是2011，叶结点个数是116, 则非终端结点个数是2011-116=1895, 则该树对应的二叉树中 无右孩子的结点个数是1895+1=1896。 一、填空题考研试题
