《2017年南昌航空大学软件学院817数据结构考研冲刺密押题.doc》由会员分享，可在线阅读，更多相关《2017年南昌航空大学软件学院817数据结构考研冲刺密押题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年南昌航空大学软件学院817数据结构考研冲刺密押题一、填空题1 在一个具有n 个单元的顺序栈中，假定以地址高端（即下标为n 的单元）作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top=_。【答案】 【解析】由于栈底在地址高端，栈中压入一个元素时，栈顶向地址底端移动一个单位，所以2 组成串的数据元素只能是_。【答案】字符 3 串是一种特殊的线性表，其特殊性表现在_; 串的两种最基本的存储方式是_、_; 两个串相等的充分必要条件是_。【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等4 假定有k 个关键字互为同义词，若用
2、线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_次探测。【答案】 【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测 的次数最小。总次数为 5 G 是一个非连通无向图，共有28条边，则该图至少有_个顶点。【答案】9【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。 6 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_，在给定值为x 的结点后插入一个新结点的时间复杂度为_。【答案】 【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。 7 已知链队列的头尾指针
3、分别是f 和r , 则将值x 入队的操作序列是_。【答案】【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。8 对于给定的元素，可以构造出的逻辑结构有_，_，_，_四种。【答案】集合；线性结构；树形结构；图状结构（网状结构） 9 对n 个记录的表rl.n进行简单选择排序，所需进行的关键字间的比较次数为_。【答案】n （n-1）/2【解析】第一次需要n-1次比较，第i 此需要n-i 此比较，所以共需要、n-l+n-2+.+l=n（n-l ）/2。 10在哈希函数 中，P 值最好取_。【答案】小于等于表长的最大素数或不包含小于20的质因子的合数【解析】在使用除留余数法时，对
4、除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。 二、选择题11设系统缓冲区和用户工作均采单，从外读入1个数据块到系统缓冲区的时间为100, 从系统缓冲区读入1个数据块到用户工作区的时间为5, 对用户工作区中的1个数据块行分析的时间为90 （如下图所示）。进程从外设读入并分析2个数据块的最短时间是（ ） A.200B.295 C.300 D.390 【答案】C【解析】数据块1从外设到用户工作区的总时间为105, 在这段时间中数据块2没有进行操作。在数据块1进行分析处理时, 数据块2从外设到用户工作区的总时间为105, 这段时间是
5、并行的。再加上数据块2进行处理的时间90, 总共是300, 故答案为C 。12串是一种特殊的线性表，其特殊性体现在（ ）。A. 数据元素是一个字符 B. 可以顺序存储C. 数据元素可以是多个字符 D. 可以链接存储 【答案】A13若串A.8 B.37 C.36 D.9【答案】B其子串的数目是（ ）。【解析】子串的定义是：串中任意个连续的字符组成的子序列，并规定空串是任意串的子串，任意串是其自身的子串。若字符串长度为长为为： 14组记录的关键码为准得到的一次划分结果为（ ）。 【答案】C【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。第一次比较：46比84小，不交换； 第二次比较：40比46小，交换，此时为第三次比较：46比79小，交换，此时为第四次比较：38比46小，交换，此时为第五次比较：56比46大，交换，此时为 故选B 。则利用快速排序的方法，以第一个记录为基长为n 的子串有1个，长为的子串有2个，的子串有3个，长为1的子串有n 个。由于空串是任何串的子串，所以本题的答案一次划分结束。15对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（ ）。 A.4一、填空题考研试题
