《数据结构2264》15秋在线作业2
《数据结构2264》15秋在线作业2试卷总分：100 测试时间：--
单选题 多选题 判断题
一、单选题（共 25 道试题，共 50 分。）V 1.有n个记录的文件，如关键字位数为d，基数为r，则基数排序共要进行（ ）遍分配与收集。
A. n
B. d
C. r
D. n - d
满分：2分
2.对一棵有100个结点的完全二叉树按层编号，根结点编号为1，则编号为49的结点的父结点的编号为（ ）。
A. 24
B. 5
C. 98
D. 99
满分：2分
3.采用开放定址法处理散列表的冲突时，其平均查找长度（ ）。
A. 低于链接法处理冲突
B. 高于链接法处理冲突
C. 与链接法处理冲突相同
D. 高于二分查找
满分：2分
4.如表r有100000个元素，前99999个元素递增有序，则采用（ ）方法比较次数较少。
A. 直接插入排序
B. 快速排序
C. 归并排序
D. 选择排序
满分：2分
5.下面关于图的存储的叙述中正确的是（ ）。
A. 用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。
B. 用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关
C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。
D. 用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。
满分：2分
6.若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（ ）。
A. 图中每个顶点的入度
B. 图中每个顶点的出度
C. 图中每个顶点的度
D. 图中连通分量的数目
满分：2分
7.对于关键字序列（ ）进行散列存储时，若选用H（ ）=K%7作为散列函数，则散列地址为0的元素有（ ）个。
A. 1
B. 2
C. 3
D. 4
满分：2分
8.设有6个结点的无向图，该图至少应有（ ）条边才能确保是一个连通图。
A. 5
B. 6
C. 7
D. 8
满分：2分
9.在线性表的下列运算中，不改变数据元素之间的结构关系的运算是（ ）。
A. 插入
B. 删除
C. 排序
D. 查找
满分：2分
10.对广义表L=（ ）,（ ）,（ ）执行操作tail（ ）的结果是（ ）。
A. (e,f)
B. ((e,f))
C. (f)
D. ( )
满分：2分
11.若某二叉树结点的中序遍历的序列为A、B、C、D、E、F、G，后序遍历的序列为B、D、C、A、F、G、E。则该二叉树结点的前序遍历的序列为（ ）。
A. E、G、F、A、C、D、B
B. E、A、G、C、F、B、D
C. E、A、C、B、D、G、F
D. E、G、A、C、D、F、B
满分：2分
12.中缀表达式2+X*（ ）的后缀形式是（ ）。
A. 3 Y X 2 + * +
B. Y 3 + X * 2 +
C. 2 X Y 3 * + +
D. 2 X Y 3 + * +
满分：2分
13.设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树上的结点个数为n，森林F中第一棵树的结点个数是（ ）。
A. m-n-1
B. n+1
C. m-n+1
D. m-n
满分：2分
14.在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（ ）。
A. HL=p; p->next=HL;
B. p->next=HL->next; HL->next=p;
C. p->next=HL; p=HL;
D. p->next=HL; HL=p;
满分：2分
15.队列的特点是（ ）。
A. 先进后出
B. 先进先出
C. 任意位置进出
D. 前面都不正确
满分：2分
16.下面关于广义表的叙述中，不正确的是（ ）。
A. 广义表可以是一个多层次的结构
B. 广义表至少有一个元素
C. 广义表可以被其他广义表所共享
D. 广义表可以是一个递归表
满分：2分
17.在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中元素的个数为（ ）。
A. i
B. i+1
C. n-i
D. n-i+1
满分：2分
18.树最适合用来表示（ ）。
A. 有序数据元素
B. 无序数据元素
C. 元素之间具有分支层次关系的数据
D. 元素之间无联系的数据
满分：2分
19.从L=（ ）,（ ）)中，取出banana元素的表达式为（ ）。
A. head(tail(L))
B. head(head(tail(L)))
C. tail(head(tail(L)))
D. head(tail(head(tail(L))))
满分：2分
20.设Huffman树的叶子结点数为m，则结点总数为（ ）。
A. 2m
B. 2m-1
C. 2m+1
D. m+1
满分：2分
21.对线性表进行二分法查找，其前提条件是（ ）。
A. 线性表以链接方式存储，并且按关键码值排好序
B. 线性表以顺序方式存储，并且按关键码值的检索频率排好序
C. 线性表以顺序方式存储，并且按关键码值排好序
D. 线性表以链接方式存储，并且按关键码值的检索频率排好序
满分：2分
22.k层（ ）二叉树的结点总数最多为（ ）。
A. 2k-1
B. 2K+1
C. 2K-1
D. 2k-1
满分：2分
23.假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行（ ）次探测。
A. K-1次
B. K次
C. K＋l次
D. K(K+1)/2次
满分：2分
24.从二叉搜索树中查找一个元素时，其时间复杂度大致为（ ）。
A. O(n)
B. O(1)
C. O(log2n)
D. O(n2)
满分：2分
25.若有序表为（ ），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（ ）。
A. f,c,b
B. f,d,b
C. g,c,b
D. g,d,b
页:
[1]