电子科技大学《数据结构》14春在线作业答案
电子科技大学《数据结构》14春在线作业1试卷总分：100 测试时间：--
一、单选题（共16道试题，共48分。）
1.下面程序段的时间复杂度是（ ）。 for(i=0;i<n;i++) for(j=1;j<m;j++) A=0；
A. O(n)
B. O(m+n+1)
C. O(m+n)
D. O(m*n)
满分：3分
2.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=head,则（ ）。
A. p指向头结点
B. p指向尾结点
C. *p的直接后继是头结点
D. *P的直接后继是尾结点
满分：3分
3.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（ ）。
A. 栈
B. 队列
C. 树
D. 图
满分：3分
4.一棵含18个结点的二叉树的高度至少为（ ）。
A. 3
B. 4
C. 5
D. 6
满分：3分
5.在计算机内实现递归算法时所需的辅助数据结构是（ ）。
A. 栈
B. 队列
C. 树
D. 图
满分：3分
6.对于哈希函数H(key)=key%13,被称为同义词的关键字是（ ）。
A. 35和41
B. 23和39
C. 15和44
D. 25和51
满分：3分
7.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为（ ）。
A. 4
B. 5
C. 6#7
满分：3分
8.在数据结构中，数据的逻辑结构可以分成（ ）。
A. 内部结构和外部结构
B. 线性结构和非线性结构
C. 紧凑结构和非紧揍结构
D. 动态结构和静态结构
满分：3分
9.队和栈的主要区别是（ ）。
A. 逻辑结构不同
B. 存储结构不同
C. 所包含的运算个数不同
D. 限定插入和删除的位置不同
满分：3分
10.无向图中一个顶点的度是指图中（ ）。
A. 通过该顶点的简单路径数
B. 与该顶点相邻接的顶点数
C. 通过该顶点的回路数
D. 与该顶点连通的顶点数
满分：3分
11.在目标串T［0..n-1］=″xwxxyxy″中，对模式串P［0..m-1］=″xy″进行子串定位操作的结果是（ ）。
A. 0
B. 2
C. 3
D. 5
满分：3分
12.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（ ）。
A. 顺序表
B. 用头指针表示的单循环链表
C. 用尾指针表示的单循环链表
D. 单链表
满分：3分
13.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是（ ）。
A. O(1)
B. O(n)
C. O(n㏒n)
D. O(n2)
满分：3分
14.二叉树中第5层上的结点个数最多为（ ）。
A. 8
B. 15
C. 16
D. 32
满分：3分
15.采用两类不同存储结构的字符串可分别简称为（ ）。
A. 主串和子串
B. 顺序串和链串
C. 目标串和模式串
D. 变量串和常量串
满分：3分
16.计算机识别、存储和加工处理的对象被统称为（ ）。
A. 数据
B. 数据元素
C. 数据结构
D. 数据类型
满分：3分
二、多选题（共2道试题，共8分。）
1.假设按照12345的进栈顺序，下面哪些是可能的出栈顺序（ ）。
A. 12345
B. 54321
C. 43215
D. 14325
满分：4分
2.由于排序过程中涉及的存储器不同，可以将排序方法分为（ ）。
A. 稳定排序
B. 不稳定排序
C. 内部排序
D. 外部排序
满分：4分
三、判断题（共22道试题，共44分。）
1.在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为O(n)。
A. 错误
B. 正确
满分：2分
2.一棵含999个结点的完全二叉树的深度为6。
A. 错误
B. 正确
满分：2分
3.已知完全二叉树T的第5层只有7个结点，则该树共有15个叶子结点。
A. 错误
B. 正确
满分：2分
4.数据的逻辑结构在计算机存储器内的表示，称为数据的逻辑结构。
A. 错误
B. 正确
满分：2分
5.若一棵满三叉树中含有121个结点，则该树的深度为6。
A. 错误
B. 正确
满分：2分
6.二叉树是度为2的有序树。
A. 错误
B. 正确
满分：2分
7.在链表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作存储密度。
A. 错误
B. 正确
满分：2分
8.在无向图中，若从顶点a到顶点b存在通路，则称a与b之间是连通的。
A. 错误
B. 正确
满分：2分
9.假设以行优先顺序存储三维数组A，其中元素A的地址为1100，且每个元素占2个存储单元，则A的地址是1264。
A. 错误
B. 正确
满分：2分
10.队列的修改是按先进先出的原则进行的。
A. 错误
B. 正确
满分：2分
11.在文本编辑程序中查找某一特定单词在文本中出现的位置，可以利用串的定位操作。
A. 错误
B. 正确
满分：2分
12.已知指针p指向某单链表中的一个结点，则判别该结点有且仅有一个后继结点的条件是p->next->next==null。
A. 错误
B. 正确
满分：2分
13.空串的长度是0。
A. 错误
B. 正确
满分：2分
14.若链串结点中的指针占4个字节，每个字符占1个字节，则结点大小为2的链串的存储密度为2/6。
A. 错误
B. 正确
满分：2分
15.在有向图中，以顶点v为终点的边的数目称为v的入度。
A. 错误
B. 正确
满分：2分
16.在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是归并排序。
A. 错误
B. 正确
满分：2分
17.如果入栈序列是1，3，5，…，97，99，且出栈序列的第一个元素为99，则出栈序列中第30个元素为47。
A. 错误
B. 正确
满分：2分
18.空格串的长度是空格的个数。
A. 错误
B. 正确
满分：2分
19.结点数为20的二叉树可能的最大高度为4。
A. 错误
B. 正确
满分：2分
20.栈下溢是指在栈空时进行出栈操作
A. 错误
B. 正确
满分：2分
21.在含100个结点的完全二叉树中，叶子结点的个数为36。
A. 错误
B. 正确
满分：2分
22.两个串相等的充分必要条件是两个串的长度相等且字母相同。
A. 错误
B. 正确
《数据结构》14春在线作业2
试卷总分：100 测试时间：--
一、单选题（共16道试题，共48分。）
1.若算法中语句的最大频度为T(n)=2006n+6n㏒n+29㏒2n,则其时间复杂度为（ ）。
A. O(㏒n)
B. O(n)
C. O(n㏒n)
D. O(㏒2n)
满分：3分
2.栈和队列都是（ ）。
A. 限制存取位置的线性结构
B. 顺序存储的线性结构
C. 链式存储的线性结构
D. 限制存取位置的非线性结构
满分：3分
3.抽象数据类型的三个组成部分分别为（ ）。
A. 数据对象、数据关系和基本操作
B. 数据元素、逻辑结构和存储结构
C. 数据项、数据元素和数据类型
D. 数据元素、数据结构和数据类型
满分：3分
4.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（ ）。
A. 3，2，6，1，4，5
B. 3，4，2，1，6，5
C. 1，2，5，3，4，6
D. 5，6，4，2，3，1
满分：3分
5.数据结构是（ ）。
A. 一种数据类型
B. 数据的存储结构
C. 一组性质相同的数据元素的集合
D. 相互之间存在一种或多种特定关系的数据元素的集合
满分：3分
6.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（ ）。
A. 0
B. 1
C. 48
D. 49
满分：3分
7.在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ ）。
A. 插入
B. 删除
C. 排序
D. 定位
满分：3分
8.下面程序段的时间复杂度为（ ）。 for (i=0; i<m; i++) for (j=0; j<n; j++) A=i*j;
A. O (m2)
B. O (n2)
C. O (m*n)
D. O (m+n)
满分：3分
9.算法分析的目的是（ ）。
A. 辨别数据结构的合理性
B. 评价算法的效率
C. 研究算法中输入与输出的关系
D. 鉴别算法的可读性
满分：3分
10.n个顶点的有向完全图中含有向边的数目最多为（ ）。
A. n-1
B. n
C. n(n-1)/2
D. n(n-1)
满分：3分
11.设串sl=″Data Structures with Java″,s2=″it″，则子串定位函数index(s1,s2)的值为（ ）。
A. 15
B. 16
C. 17
D. 18
满分：3分
12.对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为（ ）。
A. 求一个顶点的邻接点
B. 求一个顶点的度
C. 深度优先遍历
D. 广度优先遍历
满分：3分
13.若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是（ ）。
A. 10
B. 11
C. 12
D. 不确定的
满分：3分
14.在一个具有n个顶点的有向图中，所有顶点的出度之和为Dout ，则所有顶点的入度之和为（ ）。
A. Dout
B. Dout-1
C. Dout+1
D. n
满分：3分
15.执行下列程序段后，串X的值为（ ）。 S=〞abcdefgh〞; T=〞xyzw〞; substr (X,S,2,strlen(T)); substr (Y,S, stelen(T),2); strcat (X,Y);
A. 〞cdefgh〞
B. 〞cdxyzw〞
C. 〞cdefxy〞
D. 〞cdefef〞
满分：3分
16.在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（ ）。
A. 数据元素的相邻地址表示
B. 数据元素在表中的序号表示
C. 指向后继元素的指针表示
D. 数据元素的值表示
满分：3分
二、多选题（共2道试题，共8分。）
1.构造最小生成树的两个基本算法是（ ）。
A. 普里姆算法
B. 克鲁斯卡尔算法
C. 迪杰斯特拉算法
D. 哈希算法
满分：4分
2.算法以下几种特性（ ）。
A. 有穷性
B. 确定性
C. 可行性
D. 输入和输出
满分：4分
三、判断题（共22道试题，共44分。）
1.二叉树中的叶子结点就是二叉树中没有左右子树的结点。
A. 错误
B. 正确
满分：2分
2.给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。
A. 错误
B. 正确
满分：2分
3.二叉树中必有度为2的结点。
A. 错误
B. 正确
满分：2分
4.对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
A. 错误
B. 正确
满分：2分
5.在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是堆排序。
A. 错误
B. 正确
满分：2分
6.字符串“sgabacbadfgbacst” 中存在有6个与字符串“ba”相同的子串.
A. 错误
B. 正确
满分：2分
7.抽象数据类型是指数据逻辑结构及与之相关的操作。
A. 错误
B. 正确
满分：2分
8.有向图用邻接矩阵表示后，顶点i的入度等于邻接矩阵中第i列的元素个数。
A. 错误
B. 正确
满分：2分
9.不含任何字符的串称为空串。
A. 错误
B. 正确
满分：2分
10.串S=”I am a worker″的长度是10。
A. 错误
B. 正确
满分：2分
11.产生冲突现象的两个关键字称为该散列函数的同义字。
A. 错误
B. 正确
满分：2分
12.一棵树可以只有1个结点。
A. 错误
B. 正确
满分：2分
13.当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的时间复杂度。
A. 错误
B. 正确
满分：2分
14.队列的修改是按照先进先出的原则进行的。
A. 错误
B. 正确
满分：2分
15.在对链队列作出队操作时，不会改变front指针的值。
A. 错误
B. 正确
满分：2分
16.由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。
A. 错误
B. 正确
满分：2分
17.深度为k的二叉树至多有2k-1个结点。
A. 错误
B. 正确
满分：2分
18.二叉树中最多只有两棵子树，并且有左右之分。
A. 错误
B. 正确
满分：2分
19.二叉树中结点只有一个孩子时无左右之分。
A. 错误
B. 正确
满分：2分
20.假设三维数组A按行优先顺序存储，若每个元素占3个存储单元，并且首地址为100，则元素A的存储地址是501。
A. 错误
B. 正确
满分：2分
21.删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。
A. 错误
B. 正确
满分：2分
22.在二叉树的第i层上至多可以有2i个结点。
A. 错误
B. 正确
《数据结构》14春在线作业3
试卷总分：100 测试时间：--
一、单选题（共16道试题，共48分。）
1.栈是一种操作受限的线性结构，其操作的主要特征是（ ）。
A. 先进先出
B. 后进先出
C. 进优于出
D. 出优于进
满分：3分
2.已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（ ）。
A. q->next=s->next；s->next=p
B. s->next=p；q->next=s->next
C. p->next=s->next；s->next=q
D. s->next=q；p->next=s->next
满分：3分
3.设有两个串T和P，求P在T中首次出现的位置的串运算称作（ ）。
A. 联接
B. 求子串
C. 字符定位
D. 子串定位
满分：3分
4.若线性表的插入和删除操作频繁地在表头或表尾位置进行，则更适宜采用的存储结构为（ ）。
A. 无头结点的双向链表
B. 带尾指针的循环链表
C. 无头结点的单链表
D. 带头指针的循环链表
满分：3分
5.高度为5的完全二叉树中含有的结点数至少为（ ）。
A. 16
B. 17
C. 31
D. 32
满分：3分
6.与线性表相比，串的插入和删除操作的特点是（ ）。
A. 通常以串整体作为操作对象
B. 需要更多的辅助空间
C. 算法的时间复杂度较高
D. 涉及移动的元素更多
满分：3分
7.已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为（ ）。
A. 5
B. 8
C. 11
D. 18
满分：3分
8.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是（ ）。
A. p=p->next
B. p->next=p->next->next
C. p->next=p
D. p=p->next->next;
满分：3分
9.已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到（ ）。
A. P=″SCIENCE″
B. P=″STUDY″
C. S=″SCIENCE″
D. S=″STUDY″
满分：3分
10.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next= head,则（ ）。
A. p指向头结点
B. p指向尾结点
C. *p的直接后继是头结点
D. *P的直接后继是尾结点
满分：3分
11.通常将链串的结点大小设置为大于1是为了（ ）。
A. 提高串匹配效率
B. 提高存储密度
C. 便于插入操作
D. 便于删除操作
满分：3分
12.已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（ ）。
A. 5，4，3，2，1，6
B. 2，3，5，6，1，4
C. 3，2，5，4，1，6
D. 1，4，6，5，2，3
满分：3分
13.已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度为（ ）。
A. 7
B. 8
C. 9
D. 10
满分：3分
14.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为（ ）。
A. n-i+1
B. n-i
C. i
D. i-1
满分：3分
15.判断两个串大小的基本准则是（ ）。
A. 两个串长度的大小
B. 两个串中首字符的大小
C. 两个串中大写字母的多少
D. 对应的第一个不等字符的大小
满分：3分
16.逻辑上通常可以将数据结构分为（ ）。
A. 动态结构和静态结构
B. 顺序结构和链式结构
C. 线性结构和非线性结构
D. 初等结构和组合结构
满分：3分
二、多选题（共2道试题，共8分。）
1.数据的逻辑结构通常包括（ ）。
A. 集合
B. 线性
C. 树
D. 图
满分：4分
2.数据类型按其值能否分解,通常可分为（ ）和（ ）两种类型。
A. 抽象数据类型
B. 原子类型
C. 结构类型
D. 聚合类型
满分：4分
三、判断题（共22道试题，共44分。）
1.一个具有4个顶点的无向完全图有6条边。
A. 错误
B. 正确
满分：2分
2.若进栈序列为a，b，c，且进栈和出栈可以穿插进行，则可能出现6个不同的出栈序列。
A. 错误
B. 正确
满分：2分
3.在队列中，允许进行插入操作的一端称为队头。
A. 错误
B. 正确
满分：2分
4.两个空串联接得到的串的长度为0。
A. 错误
B. 正确
满分：2分
5.在一个长度为100的顺序表中删除第10个元素时，需移动90个元素。
A. 错误
B. 正确
满分：2分
6.假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为 a b b c c d d e d c 。
A. 错误
B. 正确
满分：2分
7.队列的队尾位置通常是随着入队操作而变化的。
A. 错误
B. 正确
满分：2分
8.对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为98。
A. 错误
B. 正确
满分：2分
9.已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为k。
A. 错误
B. 正确
满分：2分
10.假设为循环队列分配的向量空间为Q，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为15。
A. 错误
B. 正确
满分：2分
11.若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为 O(n)。
A. 错误
B. 正确
满分：2分
12.一棵含999个结点的完全二叉树的深度为12。
A. 错误
B. 正确
满分：2分
13.深度为15的满二叉树上，第11层有2^11个结点。
A. 错误
B. 正确
满分：2分
14.假设以行优先顺序存储三维数组A，其中元素A的地址为1100，并且每个元素占2个存储单元，则A的地址是1264。
A. 错误
B. 正确
满分：2分
15.假设三维数组A按行优先顺序存储，若每个元素占3个存储单元，且首地址为100，则元素A的存储地址是501。
A. 错误
B. 正确
满分：2分
16.在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为 O(n)。
A. 错误
B. 正确
满分：2分
17.在队列中，允许进行删除操作的一端称为队尾。
A. 错误
B. 正确
满分：2分
18.设S1="good",S2=" ",S3="book"，则S1，S2和S3依次联接后的结果是”good book” 。
A. 错误
B. 正确
满分：2分
19.数据的逻辑结构描述数据元素之间的逻辑关系，与存储方式无关。
A. 错误
B. 正确
满分：2分
20.在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是基数排序。
A. 错误
B. 正确
满分：2分
21.含n个顶点的无向连通图中至少含有n条边。
A. 错误
B. 正确
满分：2分
22.假设一棵完全二叉树含1000个结点,则其中度为2的结点数为512个。
A. 错误
B. 正确
满分：2分
页:
[1]