《数据结构》1.在二叉排序树中插入一个结点的时间复杂度...

17春天大《数据结构》在线作业一
一、单选题：
1.在二叉排序树中插入一个结点的时间复杂度为(    )。          (满分:2.5)
    A. O(1)
    B. O(n)
    C. O(log2n)
    D. O(n2 )
2.非空的循环单链表head的尾结点（由p所指向）满足(    )。          (满分:2.5)
    A. p->next= =NULL
    B. p= =NULL
    C. p->next= =head
    D. p= =head
3.二维数组M的成员是6个字符（每个字符占一个存储单元，即一个字节）组成的串，行下标i的范围从0到8，列下标j的范围从0到9，则存放M 至少需要(    )个字节。          (满分:2.5)
    A. 90
    B. 180
    C. 240
    D. 540
4.线性表的顺序存储结构是一种(    )的存储结构。          (满分:2.5)
    A. 随机存取
    B. 索引存取
    C. 顺序存取
    D. 散列存取
5.一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是(    )。          (满分:2.5)
    A. edcba
    B. decba
    C. dceab
    D. abcde
6.设串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))的结果串是(    )。          (满分:2.5)
    A. BCDEF
    B. BCDEFG
    C. BCPQRST
    D. BCDEFEF
7.设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为(    )。          (满分:2.5)
    A. R-F
    B. F-R
    C.(R-F+M)％M
    D.(F-R+M)％M
8.在一个单链表中，若删除p所指结点的后续结点，则执行(    )。          (满分:2.5)
    A. p->next=p->next->next;
    B. p=p->next;p->next=p->next->next;
    C. p->next=p->next;
    D. p=p->next->next；
9.设一棵二叉树的深度为k，则该二叉树中最多有(    )个结点。          (满分:2.5)
    A. 2k-1
    B. 2k
    C. 2k-1
    D. 2k -1
10.如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为(    )。          (满分:2.5)
    A. uwvts
    B. vwuts
    C. wuvts
    D. wutsv
11.在数据结构中，从逻辑上可以把数据结构分成(    )。          (满分:2.5)
    A. 动态结构和静态结构
    B. 紧凑结构和非紧凑结构
    C. 线性结构和非线性结构
    D. 内部结构和外部结构
12.在一棵具有5层的满二叉树中结点数为(    )          (满分:2.5)
    A. 33
    B. 32
    C. 31
    D. 31
13.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行(    )。          (满分:2.5)
    A. s->next=p;p->next=s;
    B. s->next=p->next;p->next=s;
    C. s->next=p->next;p=s;
    D. p->next=s;s->next=p;
14.判定一个循环队列QU（最多元素为m0, m0= =Maxsize-1）为满队列的条件是(    )。          (满分:2.5)
    A.((rear- front)+ Maxsize)% Maxsize = =m0
    B. rear-front-1= =m0
    C. front= =rear
    D. front= = rear+1
15.实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用(    )存储结构。          (满分:2.5)
    A. 二叉链表
    B. 广义表存储结构
    C. 三叉链表
    D. 顺序存储结构
16.在线索化二叉树中，t所指结点没有左子树的充要条件是(    )。          (满分:2.5)
    A. t—＞left=NULL
    B. t—＞ltag=1
    C. t—＞ltag=1且t—＞left=NULL
    D. 以上都不对
17.在一非空二叉树的中序遍历序列中，根结点的右边(    )。          (满分:2.5)
    A. 只有右子树上的所有结点
    B. 只有右子树上的部分结点
    C. 只有左子树上的部分结点
    D. 只有左子树上的所有结点
18.一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是(    ) 。          (满分:2.5)
    A. 4，3，2，1
    B. 1，2，3，4
    C. 1，4，3，2
    D. 3，2，4，1
19.线性表若采用链式存储结构时，要求内存中可用存储单元的地址(    )。          (满分:2.5)
    A. 必须是连续的
    B. 部分地址必须是连续的
    C. 一定是不连续的
    D. 连续或不连续都可以
20.链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。          (满分:2.5)
    A. 正确
    B. 错误
21.二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A[7][4]的起始地址为(    )。          (满分:2.5)
    A. SA+141
    B. SA+144
    C. SA+222
    D. SA+225
22.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为(    )个。          (满分:2.5)
    A. 15
    B. 16
    C. 17
    D. 47
23.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行(    )。          (满分:2.5)
    A. s->next=p->next;p->next=s;
    B. p->next=s->next;s->next=p;
    C. q->next=s;s->next=p;
    D. p->next=s;s->next=q;
24.判定一个顺序栈ST（最多元素为m0）为空的条件是(    )。          (满分:2.5)
    A. top!=0
    B. top= =0
    C. top!=m0
    D. top= =m0-1
25.设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为(    )。          (满分:2.5)
    A. n
    B. e
    C. 2n
    D. 2e
26.不带头结点的单链表head为空的判定条件是(    )。          (满分:2.5)
    A. head= =NULL
    B. head->next= =NULL
    C. head->next= =head
    D. head!=NULL
27.设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是(    )。          (满分:2.5)
    A. a在b的右方
    B. a在b的左方
    C. a是b的祖先
    D. a是b的子孙
28.设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有(    )条有向边。          (满分:2.5)
    A. n
    B. n-1
    C. m
    D. m-1
29.设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为(    )。          (满分:2.5)
    A. O(n)
    B. O(nlog2n)
    C. O(1)
    D. O(n2 )
30.按照二叉树的定义，具有3个不同数据结点的不同的二叉树有(    )种。          (满分:2.5)
    A. 5
    B. 6
    C. 30
    D. 32
31.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为(    )。          (满分:2.5)
    A. i
    B. n=i
    C. n-i+1
    D. 不确定
32.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。          (满分:2.5)
    A. 正确
    B. 错误
33.从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行(    )。(不带空的头结点)          (满分:2.5)
    A. x=HS;HS= HS—＞next;
    B. x=HS—＞data;
    C. HS=HS—＞next;x=HS—＞data;
    D. x=HS—＞data;HS= HS—＞next;
34.以下数据结构中哪一个是非线性结构？(    )          (满分:2.5)
    A. 队列
    B. 栈
    C. 线性表
    D. 二叉树
35.常对数组进行的两种基本操作是(    )。          (满分:2.5)
    A. 建立与删除
    B. 索引和修改
    C. 对数据元素的存取和修改
    D. 查找与索引
36.设某强连通图中有n个顶点，则该强连通图中至少有(    )条边。          (满分:2.5)
    A. n(n-1)
    B. n+1
    C. n
    D. n(n+1)
37.栈结构通常采用的两种存储结构是(    )。          (满分:2.5)
    A. 顺序存储结构和链式存储结构
    B. 散列方式和索引方式
    C. 链表存储结构和数组
    D. 线性存储结构和非线性存储结构
38.设串的长度为n，则它的子串个数为(    )。          (满分:2.5)
    A. n
    B. n(n+1)
    C. n(n+1)/2
    D. n(n+1)/2+1
39.具有五层结点的二叉平衡树至少有(    )个结点。          (满分:2.5)
    A. 10
    B. 12
    C. 15
    D. 17
40.设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为(    )。          (满分:2.5)
    A. BADC
    B. BCDA
    C. CDAB
    D. CBDA