2017年中国民航大学电子信息工程学院833算法与数据结构考研冲刺密押题一、填空题1 实现字符串拷贝的函数strcpy 为： 【答案】 2 已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_。 【答案】【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。 3 建立索引文件的目的是_。【答案】提高查找速度 4 有向图G=（V ，E ）, 其中V （G ）=0, 1，2，3，4, 5, 用三元组表示弧及弧上的权d 。 E （G ）为 E （G= , , ， ，则从源点0到顶点3的最短路径长度是_，经过的中间顶点是_。【答案】50; 4 5 在单链表L 中，指针P 所指结点有后继结点的条件是_ 【答案】【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。6 高度为h 的堆中，最多有_元素，最少有_个元素。 【答案】当最后一层只有【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为一个元素时，此时堆的元素个数最少，元素个数为 7 关键码序列（Q ，H ，C ，Y ，Q ，A ，M ，S ，R ，D ，F ，X ），要按照关键码值递增的次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是_; 若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是_。【答案】（Q ，A ，C ，S ，Q ，D ，F ，R ，H ，M ，Y ）; （F ，H ，C ，D ，a ，A ，M ，Q ，R ，S ，Y ，X ）【解析】希尔排序的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 8 N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_个非零元素。【答案】2（N-1）【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N-1条边就可 以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2（N-1）个非零元素。 9 有五个数据依次入栈：1，2, 3, 4, 5。在各种出栈的序列中，以3, 4先出栈的序列有_。（3在4之前出栈）【答案】3个【解析】以3, 4先出栈的序列有34521、34215、34251共3个。 10串是一种特殊的线性表，其特殊性表现在_; 串的两种最基本的存储方式是_、_; 两个串相等的充分必要条件是_。【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等 11在一个无向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_条。【答案】m/2【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。 12在一棵m阶树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是_。 【答案】【解析】m阶树除根结点和叶子结点外，结点中关键字个数最多是最少13文件可按其记录的类型不同而分成两类，即_和_文件。【答案】操作系统文件；数据库 14假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_次探测。 【答案】【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测 的次数最小。总次数为 15遍历图的过程实质上是_，广度优先遍历图的时间复杂度_; 深度优先遍历图的时间复杂度_, 两者不同之处在于_, 反映在数据结构上的差别是_。【答案】查找顶点的邻接点的过程；0（n+e）; 0（n+e）; 访问顶点的顺序不同；队列和栈【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。二、选择题16下列选项中，属于多级页表优点的是（ ）A .加快地址变换速度B. 减少缺页中断次数C. 减少页表项所占字节数D. 减少页表所占的连续内存空间【答案】D【解析】多级页表避免了把所有的页表一直保存在内存中 17下列程常段的时间复杂度是（ ） A.B.C.D.【答案】C【解析】外部循环的退出条件是内部循环的退出条件是段的时间复杂度为O即选C 。 而对于k ，每次循环都执行所以循环次数为对于j ，每次循环都执行所以每次循环次数为n 次。所以此程序一、填空题考研试题