奥鹏作业网《数据结构》在线作业一
试卷总分:100 得分:87.5
一、单选题 (共 40 道试题,共 100 分)
1.在一非空二叉树的中序遍历序列中，根结点的右边（）。
A.只有左子树上的部分结点
B.只有左子树上的所有结点
C.只有右子树上的部分结点
D.只有右子树上的所有结点
2.用链接方式存储的队列，在进行插入运算时().
A.头、尾指针都要修改
B.头、尾指针可能都要修改
C.仅修改尾指针
D.仅修改头指针
3.带头结点的单链表head为空的判定条件是（）。
A.head= =NULL
B.head->next= =head
C.head->next= =NULL
D.head!=NULL
4.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为( )
A.O（n2）
B.O（n）
C.O（1og2n）
D.O（1）
5.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( c d )
A.9，5，3
B.9，5，2，3
C.9，4，2，3
D.1，2，3
判定一个顺序栈ST（最多元素为m0）为空的条件是（）。
A.top= =m0-1
B.top= =0
C.top!=m0
D.top!=0
二叉树的第k层的结点数最多为( ).
A.2k-1
B.2k-1
C.2K-1
D.2K+1
8.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（）。
A.gdbehfca
B.gdbecfha
C.bdgcefha
D.bdgaechf
下列四种排序中（ ）的空间复杂度最大。
A.插入排序
B.归并排序
C.堆排序
D.冒泡排序
10.设无向图G中有n个顶点，则该无向图的最小生成树上有（ ）条边。
A.n-1
B.n
C.2n-1
D.2n
11.以下叙述中正确的是（）。
A.空串就是空白串
B.串的长度必须大于零
C.串是一种特殊的线性表
D.串中无素只能是字母
设一棵二叉树的深度为k，则该二叉树中最多有（ ）个结点。
A.2k-1
B.2k-1
C.2k -1
D.2k
设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ ）个空指针域。
A.4m
B.2m-1
C.2m+1
D.2m
14.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。
A.部分地址必须是连续的
B.连续或不连续都可以
C.必须是连续的
D.一定是不连续的
15.二维数组M的成员是6个字符（每个字符占一个存储单元，即一个字节）组成的串，行下标i的范围从0到8，列下标j的范围从0到9，则存放M 至少需要（）个字节。
A.90
B.540
C.240
D.180
16.一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是（）。
A.edcba
B.decba
C.dceab
D.abcde
在一棵具有5层的满二叉树中结点数为（ ）
A.33
B.32
C.31
D.31
在双向循环链表的p所指结点之后插入s所指结点的操作是（）。
A.s->left=p;s->right=p->right;p->right=s;p->right->left=s;
B.s->left=p;s->right=p->right;p->right->left=s;p->right=s;
C.p->right=s;s->left=p;p->right->left=s;s->right=p->right;
D.p->right=s;p->right->left=s;s->left=p;s->right=p->right;
假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（）个。
A.47
B.17
C.16
D.15
20.在以下的叙述中，正确的是（）。
A.线性表的顺序存储结构适用于频繁插入/删除数据元素的情况
B.线性表的顺序存储结构优于链表存储结构
C.线性表的链表存储结构适用于频繁插入/删除数据元素的情况
D.线性表的链表存储结构优于顺序存储结构
设某强连通图中有n个顶点，则该强连通图中至少有（ ）条边。
A.n+1
B.n(n-1)
C.n(n+1)
D.n
22.串是一中特殊的线性表，其特殊性体现在（）。
A.数据元素是一个字符
B.数据元素可以是多个字符
C.可以顺序存储
D.可以链接存储
23.从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行（）。(不带空的头结点)
A.x=HS—＞data;HS= HS—＞next;
B.x=HS—＞data;
C.x=HS;HS= HS—＞next;
D.HS=HS—＞next;x=HS—＞data;
24.设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是（）。
A.BCPQRST
B.BCDEFG
C.BCDEFEF
D.BCDEF
25.具有五层结点的二叉平衡树至少有（）个结点。
A.17
B.15
C.12
D.10
26.深度为5的二叉树至多有（）个结点。
A.32
B.31
C.16
D.10
27.对一个满二叉树，m个树叶，n个结点，深度为h，则（）。
A.n=h+m
B.n=2的h次方-1
C.m=h-1
D.h+m=2n
28.设无向图的顶点个数为n，则该图最多有（ ）条边。
A.n-1
B.n(n-1)/2
C.n(n+1)/2
D.0
29.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不 超过（ ）。
A.log2n-1
B.log2n+1
C.log2n
D.log2(n+1)
30.在一个单链表中，若删除p所指结点的后续结点，则执行（）。
A.p=p->next;p->next=p->next->next;
B.p=p->next->next；
C.p->next=p->next->next;
D.p->next=p->next;
31.二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A[7][4]的起始地址为（）。
A.SA+225
B.SA+222
C.SA+144
D.SA+141
32.按照二叉树的定义，具有3个不同数据结点的不同的二叉树有（）种。
A.6
B.5
C.32
D.30
33.如果只想得到1024个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ ）方法最快。
A.起泡排序
B.简单选择排序
C.快速排序
D.堆排序
34.设某棵二叉树中有2000个结点，则该二叉树的最小高度为（ ）。
A.9
B.12
C.11
D.10
设用链表作为栈的存储结构则退栈操作（ ）。
A.必须判别栈是否为空
B.必须判别栈是否为满
C.对栈不作任何判别
D.判别栈元素的类型
36.设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（ ）。
A.3，2，5，8，6
B.3，2，5，6，8
C.2，3，6，5，8
D.2，3，5，8，6
37.设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（ ）。
A.n
B.e
C.2n
D.2e
38.栈结构通常采用的两种存储结构是（）。
A.顺序存储结构和链式存储结构
B.链表存储结构和数组
C.线性存储结构和非线性存储结构
D.散列方式和索引方式
39.判定一个顺序栈ST（最多元素为m0）为栈满的条件是（）。
A.top！=m0
B.top！=0
C.top= =m0-1
D.top= =0
40.下面关于线性表的叙述错误的是（ ）。
A.线性表采用顺序存储必须占用一片连续的存储空间
B.线性表采用顺序存储便于插入和删除操作的实现
C.线性表采用链式存储便于插入和删除操作的实现
D.线性表采用链式存储不必占用一片连续的存储空间
