《2017年云南省培养单位云南天文台862计算机学科综合(非专业)之数据结构考研强化模拟题.doc》由会员分享，可在线阅读，更多相关《2017年云南省培养单位云南天文台862计算机学科综合(非专业)之数据结构考研强化模拟题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年云南省培养单位云南天文台862计算机学科综合(非专业)之数据结构考研强化模拟题一、填空题1 在单链表中设置头结点的作用是_。【答案】方便运算2 设单链表的结点结构为为指针域，已知指针px 指向单链表中data 为x 的结_；点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，贝懦要执行以下语句：_;【答案】 3 已知二叉排序树的左右子树均不为空，则_上所有结点的值均小于它的根结点值，_上所有结点的值均大于它的根结点的值。【答案】左子树；右子树 【解析】二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的
2、值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。 4 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_和记录的_，【答案】比较；移动5 无用单元是指_，例_【答案】用户不再使用而系统没有回收的结构和变量； 6 执行顺序查找时，存储方式可以是_，折半查找时，要求线性表_，分块查找时要求线性表_，而哈希表的查找，要求线性表的存储方式是_。【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储 7 在进行入栈运算时应先判别栈是否_:在进行出栈运算时应先判别栈是否_:当栈中元素为n 个，进行入栈运算时发生上溢
3、，则说明该栈的最大容量为_。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_分别设在内存空间的两端，这样只有当_时才产生溢出。【答案】满；空；n ; 栈底；两栈顶指针相邻（即值之差的绝对值为1）8 顺序存储结构是通过_表示元素之间的关系的；链式存储结构是通过_表示元素之间的关系的。【答案】物理上相邻；指针【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。 9 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。 【答案】 【解析】快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割
4、成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 10n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。注：（1）图的顶点号从0开始计；（2）indegree 是有n 个分量的一维数组，放顶点的入度， （3）函数crein 用于记算顶点入度；（4）有三个函数push （data ）, pop（ ）, check（ ）其含义为数据data 入浅，出栈和测试栈是否空（不空返回1, 否则0）。 ） . 【答案】0; j; i; 0; indegreei=0; vexi; k=l; indegree
5、i=0【解析】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的所有元素之和。拓扑排序过程：首先将入度 为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度 减一，然后判断这些顶点的 入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。 ；（“图有回路”） 二、选择题11采用指令Cache 与数据Cache 分离的主要目的是（ ）A. 减低Cache 的缺失损失 B. 提高Cache 的命中率 C. 减低CPU 平均访问时间 D. 减少指令流水线资源冲突 【答案】D【解析】指令流水线不会断流，预取过来的都是指令 12对序列用希尔排序方法排序，经一趟后序列变为则该次采用的增量是（ ）。A.1B.4 C.3 D.2【答案】B【解析】由所给的序列知，本序列要进行递增排序，经过一趟后15的位置没有变化，而给的序列中只有20比15大，20的位置和15的位置相差4。所以该次采用的増量是4。 一、填空题考研试题
