西交16年5月清考《数据结构》作业考核试题

李老师

西交16年5月清考《数据结构》作业考核试题
试卷总分：100   测试时间：--
一、单选题（共30道试题，共60分。）
1.设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。
A. 99
B. 100
C. 101
D. 102
满分：2分
2.设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（）个元素。
A. n-i
B. n+l-i
C. n-1-i
D. i
满分：2分
3.设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（）
A. R-F
B. F-R
C. (R-F+M)％M
D. (F-R+M)％M
满分：2分
4.设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。
A. 20
B. 256
C. 512
D. 1024
满分：2分
5.设某棵三叉树中有40个结点，则该三叉树的最小高度为（）。
A. 3
B. 4
C. 5
D. 6
满分：2分
6.设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（）
A. 20
B. 30
C. 40
D. 45
满分：2分
7.设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（）。
A. 第i行非0元素的个数之和
B. 第i列非0元素的个数之和
C. 第i行0元素的个数之和
D. 第i列0元素的个数之和
满分：2分
8.执行一趟快速排序能够得到的序列是（）。
A. [41，12，34，45，27]55[72，63]
B. [45，34，12，41]55[72，63，27]
C. [63，12，34，45，27]55[41，72]
D. [12，27，45，41]55[34，63，72
满分：2分
9.时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（）。
A. 堆排序
B. 冒泡排序
C. 希尔排序
D. 快速排序
满分：2分
10.下面关于线性表的叙述错误的是（）。
A. 线性表采用顺序存储必须占用一片连续的存储空间
B. 线性表采用链式存储不必占用一片连续的存储空间
C. 线性表采用链式存储便于插入和删除操作的实现
D. 线性表采用顺序存储便于插入和删除操作的实现
满分：2分
11.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（）=K%9作为散列函数，则散列地址为1的元素有（）个
A. 1
B. 2
C. 3
D. 4
满分：2分
12.设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（）。
A. head==0
B. head->next==0
C. head->next==head
D. head!=0
满分：2分
13.设有6个结点的无向图，该图至少应有（）条边才能确保是一个连通图
A. 5
B. 6
C. 7
D. 8
满分：2分
14.设输入序列1、2、3、、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。
A. n-i
B. n-1-i
C. n+l-i
D. 不能确定
满分：2分
15.设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（）。
A. 2，3，5，8，6
B. 3，2，5，8，6
C. 3，2，5，6，8
D. 2，3，6，5，8
满分：2分
16.设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（）。
A. s->next=p->next；p->next=-s；
B. q->next=s；s->next=p；
C. p->next=s->next；s->next=p；
D. p->next=s；s->next=q；
满分：2分
17.设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（）。
A. 空或只有一个结点
B. 高度等于其结点数
C. 任一结点无左孩子
D. 任一结点无右孩子
满分：2分
18.设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（）。
A. head==0
B. head->next==0
C. head->next==head
D. head!=0
满分：2分
19.两个字符串相等的充要条件是（）。
A. 两个字符串的长度相等
B. 两个字符串中对应位置上的字符相等
C. 同时具备(A)和(B)两个条件
D. 以上答案都不对
满分：2分
20.设某完全无向图中有n个顶点，则该完全无向图中有（）条边。
A. n(n-1)/2
B. n(n-1)
C. n
D. n-1
满分：2分
21.设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（）。
A. 8
B. 7
C. 6
D. 5
满分：2分
22.对5个不同的数据元素进行直接插入排序，最多需要进行（）次比较。
A. 8
B. 10
C. 15
D. 25
满分：2分
23.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置（）？脚注(10)表示用10进制表示。
A. 688
B. 678
C. 692
D. 696
满分：2分
24.建立一个长度为n的有序单链表的时间复杂度为（）
A. O(n)
B. O(1)
C. O(n)
D. O(log2n)
满分：2分
25.程序段s=i=0；do{i=i+1；s=s+i；}while(i<=n)；的时间复杂度为（）。
A. O(n)
B. O(nlog2n)
C. O(n)
D. O(n/2)
满分：2分
26.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（）
A. O（1）
B. O（n）
C. O（m）
D. O（m+n）
满分：2分
27.设某无向图有n个顶点，则该无向图的邻接表中有（）个表头结点。
A. 2n
B. n
C. n/2
D. n(n-1)
满分：2分
28.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。
A. 2m-1
B. 2m
C. 2m+1
D. 4m
满分：2分
29.设一组初始记录关键字的长度为8，则最多经过（）趟插入排序可以得到有序序列。
A. 6
B. 7
C. 8
D. 9
满分：2分
30.设顺序表的长度为n，则顺序查找的平均比较次数为（）。
A. n
B. n/2
C. (n+1)/2
D. (n-1)/2
满分：2分
二、判断题（共20道试题，共40分。）
1.二维数组是数组元素为一维数组的线性表，因此它是线性结构。
A. 错误
B. 正确
满分：2分
2.由树转化成二叉树，该二叉树的右子树一定为空。
A. 错误
B. 正确
满分：2分
3.对链表进行插入和删除操作时不必移动链表中结点。
A. 错误
B. 正确
满分：2分
4.不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O（n）。
A. 错误
B. 正确
满分：2分
5.快速排序是排序算法中平均性能最好的一种排序。
A. 错误
B. 正确
满分：2分
6.先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。
A. 错误
B. 正确
满分：2分
7.完全二叉树中的叶子结点只可能在最后两层中出现。
A. 错误
B. 正确
满分：2分
8.用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。
A. 错误
B. 正确
满分：2分
9.设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。
A. 错误
B. 正确
满分：2分
10.设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。
A. 错误
B. 正确
满分：2分
11.向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。
A. 错误
B. 正确
满分：2分
12.先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。
A. 错误
B. 正确
满分：2分
13.线性表中的所有元素都有一个前驱元素和后继元素。
A. 错误
B. 正确
满分：2分
14.如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。
A. 错误
B. 正确
满分：2分
15.有向图的邻接表和逆邻接表中表结点的个数不一定相等。
A. 错误
B. 正确
满分：2分
16.子串“ABC”在主串“AABCABCD”中的位置为2。
A. 错误
B. 正确
满分：2分
17.哈夫曼树中没有度数为1的结点。
A. 错误
B. 正确
满分：2分
18.稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。
A. 错误
B. 正确
满分：2分
19.顺序表用一维数组作为存储结构，因此顺序表是一维数组。
A. 错误
B. 正确
满分：2分
20.冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。
A. 错误
B. 正确
满分：2分
>>操作完成!