答案-数据结构与算法

1．若要对1000个元素排序，要求既快又稳定，则最好采用（ ）方法。 A．直接插入排序 B．归并排序 C．堆排序 D．快速排序

2．在平均情况下速度最快的排序方法为（ ） A．直接选择排序B．归并排序 C．堆排序 D．快速排序

3．散列法的主要问题在于( ) A．散列函数难以计算 B．散列表的存取速度慢 C．会发生冲突

D．散列表占很多内存

4．下面关于折半查找的叙述，正确的是( )。

A．表必须有序，表可以顺序方式存储，也可以链表方式存储 B．表必须有序且表中数据必须是整型、实型或字符型 C．表必须有序，而且只能从上到大排列 D．表必须有序，而且只能以顺序方式存储

5．有如下程序

long int fib(int n) { long int f;

if (n==1 || n==0) f=1; else

f=fib(n-1)+fib(n-2); return(f); }

fib(5)程序执行后输出结果是( ) A．5 B． 8 C． 13 D． 21

6．若要从1000个元素中得到10个最小值元素，最好采用（ ）方法。 A．直接插入排序 B．直接选择排序 C．堆排序 D．快速排序

7．散列查找时，解决冲突的方法有( ) A．除留余数法 B．数字分析法

C．直接地址法 D．再散列法

8．具有12条边的有向完全图有多少个顶点： A．1 B．2 C．3 D．4

9．若一个元素序列基本有序，则选用（ ）方法较快。 A．直接插入排序 B．简单选择排序 C．堆排序 D．快速排序

10．对于一个无向图，下列说法正确的是( )。 A．每个顶点的入度大于出度；

B．每个顶点的度等于其入度与出度之和； C．无向图的邻接矩阵一定是对称矩阵；

D．有向图中所有顶点的入度之和大于所有顶点的出度之和；

11．对于一个有向图，若一个顶点的入度为k1,、出度为k2，则该顶点的度是： A．k1 B．k2 C．k1-k2 D．k1+k2

12．在一个无向图中，若两顶点之间的路径长度为k，则该路径上的顶点数为( )。 A．k B．k+1 C．k+2 D．2k

13．已知一条路径上有k个顶点数，则该路径长度为： A．k B．k-1 C．k+1 D．2 k

14．关键路径是事件结点网络中（ ）。 A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C． 最长的回路

D．最短的回路

15．在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为( )。 A．n B．n*e C．e D．2*e

16．将｛50,40,60,45,41,48｝按顺序插入至一棵AVL树中，当插入元素48时，要执行什么类型的旋转变换使树成为平衡树。 A．左单旋转 B．右单旋转

C．先左后右双旋转 D．先右后左双旋转

17．最短路径的生成算法可用（ ）。 A．普里姆算法 B．克鲁斯卡尔算法 C．迪杰斯特拉算法 D．哈夫曼算法

18．在有ｎ个结点的二叉链表中有（＿＿＿＿）个空链域。 A．n+1 B．n-1 C．2n+1 D．2n-1

19．假设有6个权值分别为{3，6，9，10，7，11}，构造哈夫曼树其带权路径 A．117 B．158 C．177 D．118

20．12个结点组成的完全二叉树，按层序遍历方式进行编号，根结点为1，则编号为8的结点深度为（ ） A．0 B．3 C．4 D．1

21．在一棵深度为5（设根深度为1）的完全二叉树中，至少含有（ ）个节点。 A．4

B．5 C．31 D．32

22．(线性)表是一个（）。

A．有限序列，可以为空 B．有限序列，不能为空 C．无限序列，可以为空 D．无限序列，不能为空

23．计算机算法必须具备输入、输出和（ ）等5个特性。 A．可行性、可移植性和可扩充性 B．可行性、确定性和有穷性 C．确定性、有穷性和稳定性 D．易读性、稳定性和安全性

24．二叉搜索树重新平衡算法中常用的工具为( ) A．结点的旋转变换 B．将结点插入到堆栈中 C．将结点插入到队列中 D．散列技术

25．设循环队列A[0..n-1]中头尾指针分别为：front，rear，其中front总是指在队列中第一个元素所在的位置，rear总是指在队列中最后一个元素的下一个位置(顺时针)，那么以下哪个语句可以用来成功取读队尾元素（ ） A．A[rear] B．A[rear-1]

C．A[(rear-1)%n] D．A[(rear+n-1)%n]

26．对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为:( ) A．顺序表

B．用头指针表示的单循环链表 C．用尾指针表示的单循环链表 D．单链表

27．要表示高校校、系、班级的有关数据及其关系，选择( )比较合适。 A．线性结构 B．树结构 C．图结构 D．集合结构

28．设依次进入一个队列的元素有5个,可得到出队的元素序列有（ ）种。 A．1