《2017年北京服装学院计算机信息中心917程序设计与算法考研强化模拟题.doc》由会员分享，可在线阅读，更多相关《2017年北京服装学院计算机信息中心917程序设计与算法考研强化模拟题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年北京服装学院计算机信息中心917程序设计与算法考研强化模拟题一、填空题1 当两个栈共享一存储区时，栈利用一维数组当栈1空时，【答案】为_，栈2空时， 表示，两栈顶指针为则为_，栈满时为_。【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。2 对于给定的元素，可以构造出的逻辑结构有_，_，_，_四种。【答案】集合；线性结构；树形结构；图状结构（网状结构）3 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。 【答案】 【解析】快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可
2、分别对这两部分记录继续进行排序，以达到整个序列有序。 4 从平均时间性能而言，_排序最佳。【答案】快速【解析】快速算法的平均时间复杂度为nlogn 。5 已知一循环队列的存储空间为其中队头和队尾指针分别为front 和rear , 则此循环队列判满的条件是（ ）【答案】 6 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_和_; 而又根据指针的连接方式，链表又可分成_和_。【答案】单链表；双链表；（动态）链表；静态链表【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根
3、据指针的连接方式，链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号，动态链表的指针指向下一个元素的物理位置。7 N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_个非零元素。【答案】2（N-1）【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N-1条边就可 以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2（N-1）个非零元素。 8 对n 个记录的表rl.n进行简单选择排序，所需进行的关键字间的比较次数为_。【答案】n （n-1）/2【解析】第一次需要n-1次比较，第i 此需要n-i 此比较，所以共需要、n-l+
4、n-2+.+l=n（n-l ）/2。 9 已知如下程序段： 语句1执行的时间复杂度为_；语句2执行的时间复杂度为_；语句3执行的时间复杂度为_；语句4执行的时间复杂度为_。【答案】（1）n 1 （2）n（3）n （n 3）/2（4）n （n l ）/2【解析】语s 句1执行到不符合条件情况下，执行了n 1次。当语句1不符合条件了是不会执行语句2的，所以语句2被执行了n 次。语句3每次都要执行到不符合条件，故为234. （n l ）加起来就是n （n 3）/2。语句3不符合条件了是不会执行语句4的。所以语句4被执行了123. n 即n （n l ）/2。 10设有一个空找，栈顶指针为1000H
5、（十六进制），现有输入序列为1，2，3, 4, 5，经过PUSH ，PUSH , POP , PUSH , POP ，PUSH ，PUSH 之后，输出序列是_，而栈顶指针值是_。设栈为顺序栈，每个元素占4个字节。【答案】23; 100CH11深度为H 的完全二叉树至少有_个结点; 至多有_个结点; H 和结点总数N 之间的关系是_。【答案】 12有五个数据依次入栈：1，2, 3, 4, 5。在各种出栈的序列中，以3, 4先出栈的序列有_。（3在4之前出栈）【答案】3个【解析】以3, 4先出栈的序列有34521、34215、34251共3个。 二、选择题13假定下列指令已装入指令寄存器。则执行时不可能导致CPU 从用户态变为内核态（系统态）的是（ ）。A. B. 产生软中断D. 【答案】C【解析】A 项，除法操作出现除数为零的情况时，会产生内中断，CRJ 切换为内核态进行中断处理；B 项，直接产生中断，会切换到内核态；D 项，addr 出现非法地址，会出现中断，进而切换到内核态。14在一棵具有15个关键字的4阶B 树中，含关键字的结点数最多是（ ）A.5 B.6 C.10 D.15【答案】D C.NOTRO ；寄存器R0的内容取非把地址处的内存数据放入寄存器R0中一、填空题考研试题
