2017年北方民族大学软件工程832C语言程序设计与数据结构之数据结构考研导师圈点必考题汇编

目录

2017年北方民族大学软件工程832C语言程序设计与数据结构之数据结构考研导师圈点必考题汇编（一） (2)

2017年北方民族大学软件工程832C语言程序设计与数据结构之数据结构考研导师圈点必考题汇编（二） (10)

2017年北方民族大学软件工程832C语言程序设计与数据结构之数据结构考研导师圈点必考题汇编（三） (18)

2017年北方民族大学软件工程832C语言程序设计与数据结构之数据结构考研导师圈点必考题汇编（四） (25)

2017年北方民族大学软件工程832C语言程序设计与数据结构之数据结构考研导师圈点必考题汇编（五） (31)

第1 页，共38 页

第 2 页，共 38 页 2017年北方民族大学软件工程832C 语言程序设计与数据结构之数据结构考研导师圈

点必考题汇编（一）

说明：①本资料为VIP 学员内部使用，整理汇编了历届导师圈点的重点试题及常考试题。

——————————————————————————————————————————

一、填空题

1． 循环队列的引入，目的是为了克服_____。

【答案】假溢出时大量移动数据元素

【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。

2． 实现字符串拷贝的函数strcpy 为：

【答案】

3． G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。

【答案】9

【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。

4． 设数组的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素

的存储地址为_____；若以列序为主序顺序存储，则元素的存储地址为_____。

【答案】9174；8788

【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，

则它的存储地址为

若以列序为主存储顺序，则它的存储地址为

5． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。

【答案】物理上相邻；指针

【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。

6． 在哈希函数中，P 值最好取_____。

【答案】小于等于表长的最大素数或不包含小于20的质因子的合数

【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。

第 3 页，共 38 页 一般情况下，可以选P 为质数或不包含小于20的质因素的合数。

7． 设有两个算法在同一机器上运行，其执行时闻分别为要使前者快于后者，n 至少为_____。

【答案】15

【解析】当时，而

，时，

8． 用循环链表表示的队列长度为n ，若只设头指针，则出队和入队的时间复杂度分别是_____和_____；若只设尾指针，则出队和入队的时间复杂度分别是_____和_____。 【答案】

【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一个结点或者下下个结点删除即可，入队时，只要在尾指针的后面插入新的结点，并更新尾结点即可。

9． 当广义表中的每个元素都是原子时，广义表便成了_____。

【答案】线性表

【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。

10．串是一种特殊的线性表，其特殊性表现在_____;串的两种最基本的存储方式是_____、_____;两个串相等的充分必要条件是_____。

【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等

二、判断题

11．最小生成树的Krusakl 算法是一种贪心法。（ ）

【答案】√

【解析】在构建最小生成树常见的有三种贪心算法：kruskal ,prim ,soilion 。

12．两个长度不相同的串有可能相等。（ ） 【答案】

【解析】两个字符串相等，只有当两个字符串的长度相等，并且各个对应位置的字符相等才相等。

13．若一个有向图无环，则它一定有唯一的拓扑序列。（）

【答案】×

【解析】有向图无环说明它一定有拓扑序列，但这个拓扑序列不唯一。如果在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，在做拓扑排序时，则排序的结果是唯一的，即它有唯一的拓扑序列。

14．直接访问文件也能顺序访问，只是一般效率不高。（）

【答案】×

【解析】直接访问文件不能进行顺序访问，只能按关键字随机存取。在ISAM文件上检索记录时，先从主索引出发找到相应的柱面索引，再从柱面索引找到记录所在柱面的磁道索引，最后从磁道索引找到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直至找到为止。

15．对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。（）【答案】√

【解析】查找成功的情况下，顺序表和无序表的平均查找长度是相同的，对于查找失败，无序表需要查找到表尾，而顺序表不需要查到表尾就能确定，所以顺序表的查找长度小于无序表的查找长度。

16．内排序要求数据一定要以顺序方式存储。（）

【答案】×

【解析】由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为两大类：一类是内部排序；另一类是外部排序。因此，内部排序没有要求数据一定是以顺序方式存储。

17．—个排序算法是否稳定，是指该算法在各种情况下的时间效率是否相差不大。（）【答案】×

【解析】排序的稳定性指：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

18．倒排序文件的优点是维护简单。（）

【答案】×

【解析】倒排文件的优点是检索记录较快。特别是对某些询问，不用读取记录，就可得到解答。

第4 页，共38 页

本文来源：https://www.bwwdw.com/article/6t9e.html