天大20春《数据结构》在线作业一[答案]满分答案
《数据结构》在线作业一
试卷总分: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;
