天大21年春《数据结构》在线作业一[答案]答案
《数据结构》在线作业一
试卷总分:100 得分:100
一、单选题 (共 40 道试题,共 100 分)
1.以下数据结构中哪一个是非线性结构？( )
A.队列
B.栈
C.线性表
D.二叉树
专业答案:----
2.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ ）个空指针域。
A.2m-1
B.2m
C.2m+1
D.4m
正确答案:----
3.线性表的顺序存储结构是一种（）的存储结构。
A.随机存取
B.索引存取
C.顺序存取
D.散列存取
正确答案:----
4.如果只想得到1024个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ ）方法最快。
A.起泡排序
B.快速排序
C.简单选择排序
D.堆排序
专业答案:----
5.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。
A.i
B.n=i
C.n-i+1
D.不确定
专业答案:----
6.设有一个二维数组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
正确答案:----
7.以下叙述中正确的是（）。
A.串是一种特殊的线性表
B.串的长度必须大于零
C.串中无素只能是字母
D.空串就是空白串
正确答案:----
8.设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（ ）。
A.N0=N1+1
B.N0=Nl+N2
C.N0=N2+1
D.N0=2N1+l
正确答案:----
9.一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是（） 。
A.4，3，2，1
B.1，2，3，4
C.1，4，3，2
D.3，2，4，1
正确答案:----
10.一个向量（即一批地址连续的存储单元）第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。
A.110
B.108
C.100
D.120
专业答案:----
11.线性表是一个具有n个（ ）的有限序列
A.表元素
B.字符
C.数据元素
D.数据项
正确选项:----
12.在一个AOE网中，关键路径就是其中路径长度最短的路径。
A.正确
B.错误
13.按照二叉树的定义，具有3个不同数据结点的不同的二叉树有（）种。
A.5
B.6
C.30
D.32
正确答案:----
14.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。
A.正确
B.错误
15.设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（ ）。
专业答案:----
A.线性结构
B.树型结构
C.物理结构
D.图型结构
正确选项:----
16.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不 超过（ ）。
A.log2n+1
B.log2n-1
C.log2n
D.log2(n+1)
正确答案:----
17.当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。
A.正确
B.错误
18.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（）。
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;
专业答案:----
19.判定一个顺序栈ST（最多元素为m0）为空的条件是（）。
A.top!=0
B.top= =0
C.top!=m0
D.top= =m0-1
专业答案:----
专业答案:----
20.二维数组M的成员是6个字符（每个字符占一个存储单元，即一个字节）组成的串，行下标i的范围从0到8，列下标j的范围从0到9，则存放M 至少需要（）个字节。
A.90
B.180
C.240
D.540
专业答案:----
设有两个串p和q，求q在p中首次出现的位置的运算称作（）。
A.连接
B.模式匹配
C.求子串
D.求串长
正确答案:----
若让元素1,2,3,4,5,6依次进栈，则出栈次序不可能出现（ ）种情况
A.435612
B.325641
C.135426
D.123546
专业答案:----
23.设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ ）。
A.n，e
B.e，n
C.2n，e
D.n，2e
正确答案:----
24.一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是（）。
正确答案:----
A.edcba
正确选项:----
B.decba
正确答案:----
C.dceab
正确答案:----
D.abcde
专业答案:----
25.设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（ ）。
A.O(n)
B.O(nlog2n)
C.O(1)
D.O(n2 )
专业答案:----
专业答案:----
26.在一非空二叉树的中序遍历序列中，根结点的右边（）。
A.只有右子树上的所有结点
B.只有右子树上的部分结点
C.只有左子树上的部分结点
D.只有左子树上的所有结点
正确答案:----
27.设某无向图有n个顶点，则该无向图的邻接表中有（ ）个表头结点。
A.2n
B.n
C.n/2
D.n(n-1)
专业答案:----
28.设某棵二叉树中有2000个结点，则该二叉树的最小高度为（ ）。
A.9
B.10
C.11
D.12
专业答案:----
29.在双向循环链表的p所指结点之后插入s所指结点的操作是（）。
A.p->right=s;s->left=p;p->right->left=s;s->right=p->right;
B.p->right=s;p->right->left=s;s->left=p;s->right=p->right;
C.s->left=p;s->right=p->right;p->right=s;p->right->left=s;
D.s->left=p;s->right=p->right;p->right->left=s;p->right=s;
专业答案:----
30.判定一个循环队列QU（最多元素为m0）为空的条件是（）。
A.rear - front= =m0
B.rear-front-1= =m0
C.front= = rear
D.front= = rear+1
正确答案:----
31.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。
A.必须是连续的
B.部分地址必须是连续的
C.一定是不连续的
D.连续或不连续都可以
正确选项:----
32.判定一个顺序栈ST（最多元素为m0）为栈满的条件是（）。
A.top！=0
B.top= =0
C.top！=m0
D.top= =m0-1
33.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。
A.不发生改变
B.发生改变
C.不能确定
D.以上都不对
专业答案:----
34.对一个满二叉树，m个树叶，n个结点，深度为h，则（）。
A.n=h+m
B.h+m=2n
C.m=h-1
D.n=2的h次方-1
正确选项:----
35.设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（ ）。
正确选项:----
A.BADC
专业答案:----
B.BCDA
专业答案:----
C.CDAB
专业答案:----
D.CBDA
正确选项:----
36.设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（ ）条有向边。
A.n
B.n-1
C.m
D.m-1
专业答案:----
37.设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（ ）。
A.O(1)
B.O(log2n)
C.O(n4)
D.O(n2 )
38.设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（ ）。
A.q=p->next；p->data=q->data；p->next=q->next；free(q)；
正确选项:----
B.q=p->next；q->data=p->data；p->next=q->next；free(q)；
正确选项:----
C.q=p->next；p->next=q->next；free(q)；
D.q=p->next；p->data=q->data；free(q)
专业答案:----
39.设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是（）。
A.a在b的右方
B.a在b的左方
C.a是b的祖先
D.a是b的子孙
专业答案:----
