电子科大17春《数据结构》在线作业1

2017秋17春电子科大17春《数据结构》在线作业1

一、单选题（共 16 道试题，共 48 分。）

1. 从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需（ ）。 A. 前移一个位置 B. 后移一个位置 C. 不动

D. 视情况而定 正确答案：

2. 已知栈的最大容量为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. 逻辑上通常可以将数据结构分为（ ）。 A. 动态结构和静态结构 B. 顺序结构和链式结构 C. 线性结构和非线性结构 D. 初等结构和组合结构 正确答案：

4. 执行下列程序段后，串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〞 正确答案：

5. 在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是（ ）。 A. p=p->next

B. p->next=p->next->next C. p->next=p

D. p=p->next->next; 正确答案：

6. 已知指针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 正确答案：

7. 算法分析的目的是（ ）。 A. 辨别数据结构的合理性 B. 评价算法的效率

C. 研究算法中输入与输出的关系 D. 鉴别算法的可读性 正确答案：

8. 与线性表相比，串的插入和删除操作的特点是（ ）。 A. 通常以串整体作为操作对象 B. 需要更多的辅助空间 C. 算法的时间复杂度较高 D. 涉及移动的元素更多 正确答案：

9. 若线性表的插入和删除操作频繁地在表头或表尾位置进行，则更适宜采用的存储结构为（ ）。

A. 无头结点的双向链表 B. 带尾指针的循环链表 C. 无头结点的单链表 D. 带头指针的循环链表 正确答案：

10. 下面程序段的时间复杂度为（ ）。 for (i=0; i11. 设串sl=″Data Structures with Java″,s2=″it″，则子串定位函数index(s1,s2)的值为（ ）。 A. 15 B. 16 C. 17 D. 18

正确答案：

12. 在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（ ）。 A. 数据元素的相邻地址表示 B. 数据元素在表中的序号表示 C. 指向后继元素的指针表示 D. 数据元素的值表示 正确答案：

13. n个顶点的有向完全图中含有向边的数目最多为（ ）。 A. n-1 B. n

C. n(n-1)/2 D. n(n-1) 正确答案：

14. 栈和队列都是（ ）。 A. 限制存取位置的线性结构 B. 顺序存储的线性结构 C. 链式存储的线性结构

D. 限制存取位置的非线性结构 正确答案：

15. 计算机识别、存储和加工处理的对象被统称为（ ）。 A. 数据 B. 数据元素 C. 数据结构 D. 数据类型 正确答案：

16. 无向图中一个顶点的度是指图中（ ）。 A. 通过该顶点的简单路径数 B. 与该顶点相邻接的顶点数 C. 通过该顶点的回路数 D. 与该顶点连通的顶点数 正确答案：

17春《数据结构》在线作业1

二、多选题（共 2 道试题，共 8 分。）

1. 假设按照12345的进栈顺序，下面哪些是可能的出栈顺序（ ）。 A. 12345 B. 54321 C. 43215 D. 14325 正确答案：

2. 数据的逻辑结构通常包括（ ）。 A. 集合 B. 线性

C. 树 D. 图

正确答案：

17春《数据结构》在线作业1

三、判断题（共 22 道试题，共 44 分。）

1. 在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是堆排序。 A. 错误 B. 正确 正确答案：

2. 二叉树中必有度为2的结点。 A. 错误 B. 正确 正确答案：

3. 二叉树中的叶子结点就是二叉树中没有左右子树的结点。 A. 错误 B. 正确 正确答案：

4. 假设为循环队列分配的向量空间为Q[20]，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为15。 A. 错误 B. 正确 正确答案：

5. 对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为98。 A. 错误 B. 正确 正确答案：

6. 有向图用邻接矩阵表示后，顶点i的入度等于邻接矩阵中第i列的元素个数。 A. 错误 B. 正确 正确答案：

7. 在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为 O(n)。 A. 错误 B. 正确 正确答案：

8. 二叉树中结点只有一个孩子时无左右之分。 A. 错误 B. 正确 正确答案：

9. 深度为15的满二叉树上，第11层有2^11个结点。 A. 错误 B. 正确 正确答案：

10. 在链表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作存储密度。 A. 错误 B. 正确 正确答案：

11. 给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。 A. 错误 B. 正确 正确答案：

12. 数据的逻辑结构描述数据元素之间的逻辑关系，与存储方式无关。 A. 错误 B. 正确 正确答案：

13. 设S1=\"good\，则S1，S2和S3依次联接后的结果是”good book” 。 A. 错误 B. 正确 正确答案：

14. 在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是归并排序。 A. 错误 B. 正确 正确答案：

15. 二叉树是度为2的有序树。 A. 错误 B. 正确 正确答案：

16. 若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为 O(n)。 A. 错误 B. 正确 正确答案：

17. 假设以行优先顺序存储三维数组A[5][6][7]，其中元素A[0][0][0]的地址为1100，且每个元素占2个存储单元，则A[4][3][2]的地址是1264。 A. 错误 B. 正确 正确答案：

18. 在文本编辑程序中查找某一特定单词在文本中出现的位置，可以利用串的定位操作。 A. 错误

B. 正确 正确答案：

19. 在队列中，允许进行插入操作的一端称为队头。 A. 错误 B. 正确 正确答案：

20. 抽象数据类型是指数据逻辑结构及与之相关的操作。 A. 错误 B. 正确 正确答案：

21. 含n个顶点的无向连通图中至少含有n条边。 A. 错误 B. 正确 正确答案：

22. 两个串相等的充分必要条件是两个串的长度相等且字母相同。 A. 错误 B. 正确 正确答案：