当前位置：问答库＞考研试题

一、填空题

1． 数组的存储结构采用_____存储方式。

【答案】顺序存储结构

【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。

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

【答案】O(1)；O(n)；O(1)；O(1)

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

3． 在哈希函数中，p 值最好取_____。

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

【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。

4． 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长(也称增

量序列) 依次是4， 2， 1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。

【答案】3; (10，7，-9，0，47，23，1，8，98，36)

5． 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。

【答案】f ﹣＞next ＝p ﹣＞next ；f ﹣＞prior ＝p ；p ﹣＞next ﹣＞prior ＝f ；p ﹣＞next ＝f ；

6． 求最短路径的Dijkstra 算法的时间复杂度为_____。 【答案】

7． 设有一个10阶对称矩阵A 采用压缩存储方式(以行为主序存储:a 11＝l) ， 则a 85的地址为_____。

【答案】33

【解析】设存储的元素的行标为i ，列标为j 。若i ＞＝j ，则的地址为l ＋2＋... ＋i ﹣l ＋j ＝i(i﹣l)/2＋j 。若i ＜j 。则的地址为j(j﹣l)/2＋i 。将i ＝8，j ＝5代入得33。

8． 中缀式(c-d)对应的前缀式为_____，若a=l，b=2, c=3, d=4, 则后缀式

运算结果为_____。 【答案】

【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。

9． 在n 个顶点的非空无向图中，最多有_____个连通分量。

【答案】n 的

【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。

10．设数组的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45，68]的存储地址为_____；若以列序为主序顺序存储，则元素a[45，68]的存储地址为_____。

【答案】9174；8788

【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，则它的存储地址为2000＋((i﹣l)*80＋j ﹣

1) 2。若以列序为主存储顺序，则它的存储地址为2000＋((j﹣l)*50＋i ﹣l)*2。

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

【答案】15

2n 【解析】当时，100n2>2n，而，时，100n ＜2

12．高度为h 的堆中，最多有_____元素，最少有_____个元素。 【答案】

。当最后一层只有

。

中，其下标值最大的分支结点为_____。【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为一个元素时，此时堆的元素个数最少，元素个数为 13．设有N 个结点的完全二叉树顺序存放在向量

【答案】

【解析】最大的分支结点是最后一个叶子结点的父结点。

14．二叉树由_____，_____，_____三个基本单元组成。

【答案】根结点；左子树；右子树

15．有向图G=(V, E) ，其中

权d 。E(G)为

，用三元组表示弧及弧上的

，则从源点0到顶点3的最短路径长度是_____，经过的中间顶点是_____。

【答案】50；4

二、判断题

16．无环有向图才能进行拓扑排序。（ ）

【答案】√

【解析】在图论中，由一个有向无环图的顶点组成的序列，才能进行拓扑排序。

17．—个有向图的邻接表和逆邻接表中的结点个数一定相等。（ ）

【答案】√

【解析】图的邻接表表示法类似于树的孩子链表示法。对于图G 中的每个顶点，该方法把所以邻接于顶点

的链接成一个带头。在有向图中，为图中每个顶点建立一个入边表的方法称为逆邻接表示法。

18．树形结构中元素之间存在一对多的关系。（ ）

【答案】√

【解析】树形结构是非线性结构，存在一对多的关系。

19．一棵树中的叶子数一定等于与其对应的二叉树的叶子数。（ ）

【答案】 ×

【解析】一颗树的叶子树与它对一个的二叉树的叶子树没有直接联系。不妨举例:假设一个有三个结点的二叉树，层数为2。则它的叶结点数为2。将其按规则转为对应的二叉树时，则它的叶结点数为1。

20．串是一种数据对象和操作都特殊的线性表。（ ）

【答案】 √

【解析】串是一种操作特殊的线性表，其特殊性主要体现在数据元素是一个字符。在内存中，一份文本都可以看做是一个字符串，而每一行都可以看做是其子串。

21．在待排数据基本有序的情况下，快速排序效果好。（ ）

【答案】×

【解析】在待排数据基本有序的情况下，插入排序效果好。