在线作业一：一、单选题（共16 道试题，共48 分。

）1. 已知指针p和q分别指向某单链表中第一个结点和最后一个结点。

假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（）。

A. q->next=s->next；s->next=pB. s->next=p；q->next=s->nextC. p->next=s->next；s->next=qD. s->next=q；p->next=s->next正确答案：A2. 高度为5的完全二叉树中含有的结点数至少为（）。

A. 16B. 17C. 31D. 32正确答案：A3. 设有两个串T和P，求P在T中首次出现的位置的串运算称作（）。

A. 联接B. 求子串C. 字符定位D. 子串定位正确答案： D4. 对于哈希函数H(key)=key%13,被称为同义词的关键字是（）。

A. 35和41B. 23和39C. 15和44D. 25和51正确答案：D5. 算法分析的目的是（）。

A. 辨别数据结构的合理性B. 评价算法的效率C. 研究算法中输入与输出的关系D. 鉴别算法的可读性正确答案：B6. 在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=head,则（）。

A. p 指向头结点B. p 指向尾结点C. *p 的直接后继是头结点D. *P 的直接后继是尾结点正确答案：D7. 数据结构是（）A. 一种数据类型B. 数据的存储结构C. 一组性质相同的数据元素的集合D. 相互之间存在一种或多种特定关系的数据元素的集合正确答案：D8.采用两类不同存储结构的字符串可分别简称为（）。

A. 主串和子串B. 顺序串和链串C. 目标串和模式串D. 变量串和常量串正确答案：B9.已知函数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″正确答案：A10.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next= head,则（）。

A. p 指向头结点B. p 指向尾结点C. *p 的直接后继是头结点D. *P 的直接后继是尾结点正确答案：D11.若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是（）。

A. 10B. 11C. 12D. 不确定的正确答案：A12.下面程序段的时间复杂度是（）。

for(i=0;i<n;i++) for(j=1;j<m;j++) A[i][j]=0；A. O(n)B. O(m+n+1)C. O(m+n)D. O(m*n)正确答案：D13.在线性表的下列运算中，不改变数据元素之间结构关系的运算是（）。

A. 插入B. 删除C. 排序D. 定位正确答案： D14. 在计算机内实现递归算法时所需的辅助数据结构是（）。

A. 栈B. 队列C. 树D. 图正确答案：A15. 在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（）。

A. 数据元素的相邻地址表示B. 数据元素在表中的序号表示C. 指向后继元素的指针表示D. 数据元素的值表示正确答案： C16. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（）。

A. 顺序表B. 用头指针表示的单循环链表C. 用尾指针表示的单循环链表D. 单链表正确答案：C二、多选题（共 2 道试题，共8 分。

）1. 算法以下几种特性（）。

A. 有穷性B. 确定性C. 可行性D. 输入和输出正确答案：ABCD2. 一个好的算法有（ABCD ）设计要求。

A. 正确性B. 可读性C. 健壮性D. 效率与低存储量要求正确答案：ABCD三、判断题（共22 道试题，共44 分。

）1. 二叉树中的叶子结点就是二叉树中没有左右子树的结点。

A. 错误B. 正确正确答案：B2. 在队列中，允许进行删除操作的一端称为队尾。

A. 错误B. 正确正确答案： B3. 假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为a b b c c d d e d c。

A. 错误B. 正确正确答案：A4. 空串的长度是0 A. 错误B. 正确正确答案：B5. 数据的逻辑结构在计算机存储器内的表示，称为数据的逻辑结构。

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

A. 错误B. 正确正确答案：A7. 如果入栈序列是1，3，5，…，97，99，且出栈序列的第一个元素为99，则出栈序列中第30 个元素为47。

A. 错误B. 正确正确答案：B8. 字符串“sgabacbadfgbacst” 中存在有6个与字符串“ba”相同的子串 A. 错误B. 正确正确答案：A9. 假设以行优先顺序存储三维数组A[5][6][7]，其中元素A[0][0][0]的地址为1100，并且每个元素占2个存储单元，则A[4][3][2]的地址是1264。

A. 错误 B. 正确正确答案：A10. 当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的时间复杂度。

A. 错误B. 正确正确答案：B11. 一棵含999个结点的完全二叉树的深度为12 A. 错误B. 正确正确答案：A12. 在队列中，允许进行插入操作的一端称为队头。

A. 错误B. 正确正确答案：B13.若一棵满三叉树中含有121个结点，则该树的深度为6。

A. 错误B. 正确正确答案： A14. 产生冲突现象的两个关键字称为该散列函数的同义字。

A. 错误B. 正确正确答案：B15. 在二叉树的第i层上至多可以有2i个结点。

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

A. 错误B. 正确正确答案：A17. 已知指针p指向某单链表中的一个结点，则判别该结点有且仅有一个后继结点的条件是p->next->next==null。

A. 错误B. 正确正确答案：B18. 若进栈序列为a，b，c，且进栈和出栈可以穿插进行，则可能出现6个不同的出栈序列。

A. 错误B. 正确正确答案：A19. 在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为O(n)。

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

A. 错误B. 正确正确答案： A21. 二叉树中最多只有两棵子树，并且有左右之分。

A. 错误B. 正确正确答案： B22. 不含任何字符的串称为空串。

A. 错误B. 正确正确答案：B在线作业二：一、单选题（共16 道试题，共48 分。

）1. 高度为5 的完全二叉树中含有的结点数至少为（）。

A. 16B. 17C. 31D. 32正确答案：A2. 二叉树中第5 层上的结点个数最多为（）。

A. 8B. 15C. 16D. 32正确答案：C3. 在一个具有n 个顶点的有向图中，所有顶点的出度之和为Dout ，则所有顶点的入度之和为（）。

A. DoutB. Dout-1C. Dout+1D. n正确答案：A4. 在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（）。

A. 数据元素的相邻地址表示B. 数据元素在表中的序号表示C. 指向后继元素的指针表示D. 数据元素的值表示正确答案：C5. 已知栈的最大容量为4。

若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行, 则可能出现的出栈序列为（）。

A. 5，4，3，2，1，6B. 2，3，5，6，1，4C. 3，2，5，4，1，6D. 1，4，6，5，2，3正确答案：C6. 若算法中语句的最大频度为T(n)=2006n+6n ㏒n+29 ㏒2n,则其时间复杂度为（）。

A. O(㏒n)B. O(n)C. O(n ㏒n)D. O(㏒2n)正确答案：C7. 下面程序段的时间复杂度为（）。

for (i=0; i<m; i++) for (j=0; j<n; j++) A[i][j]=i*j;A. O (m2)B. O (n2)C. O (m*n)D. O (m+n)正确答案：C8.采用两类不同存储结构的字符串可分别简称为（）。

A. 主串和子串B. 顺序串和链串C. 目标串和模式串D. 变量串和常量串正确答案：B9.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（）。

A. 顺序表B. 用头指针表示的单循环链表C. 用尾指针表示的单循环链表D. 单链表正确答案：C10.一棵含18个结点的二叉树的高度至少为（）。

A. 3B. 4C. 5D. 6正确答案：C11.判断两个串大小的基本准则是（）。

A. 两个串长度的大小B. 两个串中首字符的大小C. 两个串中大写字母的多少D. 对应的第一个不等字符的大小正确答案：B12.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（）。

A. 0B.1C. 48D. 49正确答案：D13.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next= head,则（）。

A. p 指向头结点B. p 指向尾结点C. *p 的直接后继是头结点D. *P 的直接后继是尾结点正确答案：D14. 与线性表相比，串的插入和删除操作的特点是（）。

A. 通常以串整体作为操作对象B. 需要更多的辅助空间C. 算法的时间复杂度较高D. 涉及移动的元素更多正确答案：A15. 抽象数据类型的三个组成部分分别为（）。

A. 数据对象、数据关系和基本操作B. 数据元素、逻辑结构和存储结构C. 数据项、数据元素和数据类型D. 数据元素、数据结构和数据类型正确答案：A16. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（）。

A. 3，2，6，1，4，5B. 3，4，2，1，6，5C. 1，2，5，3，4，6D. 5，6，4，2，3，1正确答案：B二、多选题（共 2 道试题，共8 分。

）1. 构造最小生成树的两个基本算法是（）。

A. 普里姆算法B. 克鲁斯卡尔算法C. 迪杰斯特拉算法D. 哈希算法正确答案：AB2. 由于排序过程中涉及的存储器不同，可以将排序方法分为（）。