西交《数据结构》在线作业-00002
试卷总分:100 得分:100
一、单选题 (共 30 道试题,共 60 分)
1.用链表表示线性表的优点是（）
A.便于随机存取
B.花费的存储空间比顺序表少
C.便于插入与删除
D.数据元素的物理顺序与逻辑顺序相同
2.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（）
A.front=front+1
B.front=(front+1)%(m-1)
C.front=(front-1)%m
D.front=(front+1)%m
3.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用（ ）查找方法。
A.分块
B.顺序
C.二分
D.散列
4.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。
A.2m-1
B.2m
C.2m+1
D.4m
5.求字符串T在字符串S中首次出现的位置的操作称为( )。
A.串的模式匹配
B.求子串
C.求串的长度
D.串的连接
6.哈希表的平均查找长度是( )的函数。
A.哈希表的长度
B.表中元素的多少
C.哈希函数
D.哈希表的装满程度
7.设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（）
A.R-F
B.F-R
C.(R-F+M)％M
D.(F-R+M)％M
8.设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（）。
A.head==0
B.head->next==0
C.head->next==head
D.head!=0
9.设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（）。
A.n
B.e
C.2n
D.2e
10.设某完全无向图中有n个顶点，则该完全无向图中有（）条边。
A.n(n-1)/2
B.n(n-1)
C.n
D.n-1
11.一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，（ ）次比较后查找成功。
A.2
B.3
C.4
D.5
12.顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（）。
A.O(n)
B.O(n^2)
C.O(n^3)
D.O(1og2n)
13.执行一趟快速排序能够得到的序列是（）。
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
14.若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ）排序为宜。
A.直接插入
B.直接选择
C.堆
D.快速
15.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。
A.不确定
B.n-i+1
C.i
D.n-i
16.设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（）。
A.空或只有一个结点
B.高度等于其结点数
C.任一结点无左孩子
D.任一结点无右孩子
17.一个具有n个顶点的无向图最多有( )条边。
A.n×(n-1)/2
B.n×(n-1)
C.n×(n+1)/2
D.n2
18.设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）
A.BADC
B.BCDA
C.CDAB
D.CBDA
19.设一组初始记录关键字的长度为8，则最多经过（）趟插入排序可以得到有序序列。
A.6
B.7
C.8
D.9
20.存放循环队列元素的数组data有10个元素，则data数组的下标范围是（ ）。
A.0～10
B.0～9
C.1～9
D.1～10
21.空串与空格字符组成的串的区别是（ ）。
A.没有区别；
B.两串的长度不等；
C.两串的长度相等；
D.两串包含的字符不相同。
22.在二叉排序树中插入一个结点的时间复杂度为（）。
A.O(1)
B.O(n)
C.O(log2n)
D.O(n)
23.在序列（2，5，8，11，15，16，22，24，27，35，50）中采用折半查找（二分查找）方法查找元素24，需要进行（ ）次元素之间的比较。
A.3
B.4
C.8
D.11
24.设某棵三叉树中有40个结点，则该三叉树的最小高度为（）。
A.3
B.4
C.5
D.6
25.由两个栈共享一个向量空间的好处是：（）
A.减少存取时间，降低下溢发生的机率
B.节省存储空间，降低上溢发生的机率
C.减少存取时间，降低上溢发生的机率
D.节省存储空间，降低下溢发生的机率
26.时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（）。
A.堆排序
B.冒泡排序
C.希尔排序
D.快速排序
27.设用链表作为栈的存储结构则退栈操作（）
A.必须判别栈是否为满
B.必须判别栈是否为空
C.判别栈元素的类型
D.对栈不作任何判别
28.设顺序表的长度为n，则顺序查找的平均比较次数为（）。
A.n
B.n/2
C.(n+1)/2
D.(n-1)/2
29.在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，打印机依次从该缓冲区中取出数据打印，则该缓冲区的结构应该是（ ）。
A.线性表
B.数组
C.堆栈
D.队列
30.广度优先遍历类似于二叉树的（ ）。
A.先序遍历
B.中序遍历
C.后序遍历
D.层次遍历
二、判断题 (共 20 道试题,共 40 分)
31.中序遍历一棵二叉排序树可以得到一个有序的序列。
32.子串“ABC”在主串“AABCABCD”中的位置为3。
33.分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。
34.为度量一个搜索算法的性能，需要在时间和空间方面进行权衡。
35.在B+树中查找和在B-树中查找的过程完全相同。 ( )
36.栈的特点是“后进先出”。（ ）
37.不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O（n）。
38.设串S的长度为n,则S的子串个数为n(n+1)/2。
39.设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。（ ）
40.由树转化成二叉树，该二叉树的右子树不一定为空。（ ）
41.磁带是顺序存取的外存储设备。
42.调用一次深度优先遍历可以访问到图中的所有顶点。
43.希尔排序算法的时间复杂度为O(n2)。
44.二维数组和多维数组均不是特殊的线性结构。
45.层次遍历初始堆可以得到一个有序的序列。
46.从本质上看,文件是一种非线性结构。
47.设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。
48.{图}
49.对连通图进行深度优先遍历可以访问到该图中的所有顶点。
50.完全二叉树中的叶子结点只可能在最后两层中出现。（ ）
