武汉软件工程职业学院软件技术专业大二2019数据结构二测

➢教学重点：二叉树的定义、二叉树的性质➢教学难点：二叉树的性质➢授课内容4.1 树的定义和基本术语前面讨论线性结构的表示及其应用实例。

然而，线性结构在许多实际应用中不能明确、方便地表示数据元素之间的复杂关系。

树型结构是一种应用十分广泛的非线性结构，其中以二叉树最为常用，它是以分支定义的层次结构。

树型结构在客观世界中广泛存在，如家族的家谱、各种社会组织机构，一般都可以用树来形象地表示。

在计算机领域中，编译系统中源程序的语法结构、数据库系统中信息的组织形式也用到树形结构。

本章重点讨论二叉树的存储结构、各种操作及其应用实例。

4.1.1 树的定义1. 定义树（tree）是由n（n＞0）个结点组成的有限集合T且满足以下条件。

1）有且仅有一个特定的结点被称为该树的根（Root）。

2）除根结点之外的其余结点可分为m（m ＞0）个互不相交的集合T1，T2，...，Tm，且其中每个集合又是一棵树，并称之为根的子树（Subtree）。

这是一个递归的定义，即在定义中又用到了树的概念，这也反映了树的固有特性。

图4-1-1是两棵树的示例。

（a）是只有一个根结点A的树。

（b）是一棵由11个结点组成的树T，其中A是根结点，其余结点分为三个互不相交的子集：T1={B，E，F，G，K}，T2＝{C，H}，T3＝{D，I，J}。

T1，T2，T3也都是树，且是根A的子树，这三棵子树的根结点分别为B、C、D，每棵子树还可以继续划分。

第十二讲树和二叉树(a) 一棵树结构 (b)一个非树结构 (c)一个非树结构 (d)一个非树结构图4-1-1（b ）所示的树，还可以用图4-1-2所示的方法表示。

树的基本术语 树的结点 树的结点包含一个数据元素及若干个指向其子树的分支。

结点的度和树的度 结点的度是结点的子树的个数。

树的度是树中结点度的最大值。

例如图4－1－1（b ）中，结点A 和B 的度为3，结点D 的度为2；而树T 的度为3。

叶子和分支结点 度为零的结点称为叶子或终端结点。

武汉软件工程职业学院软件技术专业大二2019年数据结构--13.14.15单元测试题1. 串是一种特殊的线性表，其特殊性体现在（） [单选题] *A. 可以顺序存储B. 数据元素是一个字符(正确答案)C. 可以链接存储D. 数据元素可以是多个字符2. 某串的长度小于一个常数，则采用（）存储方式最节省空间 [单选题] *A. 链式B. 堆结构C. 顺序(正确答案)D. 无法确定3. 若串S="ABCD"，其子串的数目最多是：（） [单选题] *A. 11(正确答案)B. 9C. 10D. 84. S1="good"，S2="morning"，执行串连接函数ConcatStr(S1,S2)后的结果为（）[单选题] *A. "GOOD MORNING"B. "good morning"C. "GOODMORNING"D. "goodmorning"(正确答案)5. 有如下代码char s[]="interesting";则s数组的的长度是（） [单选题] *A. 12(正确答案)B. 11C. 13D. 106. 设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（） [单选题] *A. 求子串B. 联接C. 匹配(正确答案)D. 求串长7. 串的表示方式有（） *A. 定长顺序存储表示(正确答案)B. 堆分配存储表示(正确答案)C. 块链存储表示(正确答案)D. 栈式存储表示8. 以下字符串处理函数中，返回值是char*的是（） *A. Strcat--字符串连接(正确答案)B. Strcmp--字符串比较 1 -1 0 intC. Strcpy--字符串拷贝(正确答案)D. Strlen--求字符串长度9. 以下字符串处理函数中，参数是两个的是（） *A. strcat(正确答案)B. strcmp(正确答案)C. strcpy(正确答案)D. Strlen10. 以下字符串处理函数中，参数是一个的是（） *A. strcatB. puts(正确答案)C. gets(正确答案)D. Strlen(正确答案)11. 以下论述错误的是（） *A. 空串与空格串是相同的(正确答案)B. "ton"是"Teleptone"的子串C. 空格串是有空格的串(正确答案)D. 空串的长度等于1(正确答案)12. strcat的参数个数不是（） *A. 1(正确答案)B. 3(正确答案)C. 2D. 0(正确答案)13. char s[100]="abc"; 则执行strcpy(s,strcat(s,"123"));后s的结果不是（） *A. 123abc(正确答案)B. abc(正确答案)D. abc12314. 函数strlen的返回值类型与函数strcmp相同。

武汉软件工程职业学院软件技术专业大二2019年数据结构期末测试(1)下列数据结构，( )属于线性结构。

（） [单选题] *A.图B.栈与队列(正确答案)C.集合D.树(2)非线性结构中的每个结点( )。

（） [单选题] *A.无直接前趋结点B.无直接后继结点C.只有一个直接前趋结点和一个直接后继结点D.可能有多个直接前趋结点和多个直接后继结点(正确答案)(3)以下任何两个结点之间都没有逻辑关系的是( )（） [单选题] *A.图形结构B.线性结构C.树形结构D.集合(正确答案)(4)顺序存储结构的最大优点是( )。

（） [单选题] *A.便于随机存取(正确答案)B.存储密度底C.无需预分配空间D.便于进行插入和删除操作(5)链式存储设计时，结点内的存储单元地址()。

（） [单选题] *A.一定连续(正确答案)B.—定不连续C.不一定连续D.部分连续，部分不连续(1)算法能正确的实现预定功能的特性称为算法的( )。

（） [单选题] *A.正确性(正确答案)B.易读性C.健壮性D.高效性(2)算法的描述便于阅读，以利于后续对算法的理解和修改称为算法的( )。

（） [单选题] *A.正确性B.易读性(正确答案)C.健壮性D.高效性(3)下列算法的时间复杂度是( )（）x=0;y=0;s=0;for(i=1;i<=n;++i)for(k=1;k<=n;++k)for(j=1;j<=n;++j){++y; s+=y;}for(k=1;k<=n;++k){++x; s+=x;} [单选题] *A.O(n)B. O(n2)C. O(n3)(正确答案)D. O(1)(4)下列算法的时间复杂度是( )。

（）x=0;y=0;s=0;++y; s+=y;++x; s+=x; [单选题] *A.O(n)B. O(n2)C. OO(n3)D. O(1)(正确答案)(5)下列算法的时间复杂度是( )。

武汉软件工程职业学院软件技术专业大二2019数据结构第六单元测试题您的姓名： [填空题] *_________________________________1. 下列选项中符合线性表的特点是（）。

[单选题] *一对多一对一(正确答案)多对多多对一2. 数据结构中线性表的链式存储结构也被称为（） [单选题] *图表顺序表集合表链表(正确答案)3. 在n个元素的顺序表的第i个位置插入元素需要移动几个元素值（） [单选题] * n-2nn-i+1(正确答案)n-14. 顺序表的一个存储结点仅存储线性表的一个（） [单选题] *数据项数据元素(正确答案)数据数据结构5. 线性表是（） [单选题] *一个有限序列，可以为空(正确答案)一个有限序列，不能为空一个无限序列，可以为空一个无限序列，不能为空6. 在数据结构中，线性表是（） [单选题] *算法图形结构n个元素的有限序列(正确答案)二叉树7. 以下关于算法的存储量高低用（）来衡量正确的是 [单选题] *时间复杂度算法的步骤数空间复杂度(正确答案)算法的长度8. (专基)空间复杂度记作：（）。

[单选题] *T(n)=O(f(n))S(n)=O(f(n))(正确答案)T(n)=f(n)S(n)=f(n)9. 下面代码段的时间复杂度正确的是（）void f1（int n）{ int i=1,k=0; while( i<n ) { k+=10*i; i++; }} [单选题] *O（1）O（ n*n）O(n)(正确答案)O(log2n)10. 数据项和数据元素分别是数据的（）和（） [单选题] *基本单位最大单位最小单位基本单位(正确答案)最大单位基本单位都不对11. 以下哪个选项属于算法的五大特性之一（） [单选题] *有穷性(正确答案)可读性正确性无二义性12. 数据结构是指互相之间存在一种或多种特定关系的（）的集合 [单选题] *集合数据数据项数据元素(正确答案)13. 数据元素与数据项的关系正确的是（） [单选题] *数据元素>数据项(正确答案)数据元素<数据项数据项>数据元素都不对14. 以下选项属于逻辑结构的是（） [单选题] *索引结构链式结构图形结构(正确答案)顺序结构15. 在下面的程序段中，时间复杂度为（）。

武汉软件工程职业学院软件技术专业大二《java程序设计》期末考试基本信息：[矩阵文本题] *1. 下面说法正确的是（）。

[单选题]A、Java程序的main()方法必须都写在类里面(正确答案)B、Java程序中可以有多个main()方法C、Java程序的类名必须与文件名一样D、Java程序的main()方法中如果只有一条语句，可以不用{}括起来2. Java源代码文件的扩展名为（）。

[单选题]A、.txtB、.classC、.docD、.java(正确答案)3. 在控制台显示消息的语句正确的是（）。

[单选题]A、System.out.println（我是一个Java程序员了！）；B、System.out.println（”我是一个Java程序员了！”）；(正确答案)C、system.out.println（”我是一个Java程序员了！”）；D、System.Out.Println（”我是一个Java程序员了！”）；4. 开发Java程序的步骤正确的是（） [单选题]A、编译—>编写源程序—>运行B、运行—>编译—>编写源程序C、编写源程序—>运行—>编译D、编写源程序—>编译—>运行(正确答案)5. 以下说法不正确的是（） [单选题]A、按照市场需求Sun公司对Java技术进行了划分，使用最广泛的是JavaSE和JavaEEB、JavaSE是Java技术的核心，提供基础Java开发工具，执行环境和应用程序接口C、JavaEE主要用于桌面应用程序的开发，而JavaSE主要用于网络程序和企业级应用的开发(正确答案)D、JavaEE是在JavaSE的基础上扩展的6. 选出在Java中无效的注释声明（）。

[单选题]A、／／这是注释B、／**这是注释*／C、／这是注释(正确答案)D、／*这是注释*／7. 以下（）不是合法的标识符。

[单选题]A、double123B、3x(正确答案)C、sumD、de2sf8. 下列语句中，（）正确完成整型变量的声明和赋值。

第一讲数据结构的基本概念和术语教学重点：数据结构与算法的基本概念的理解。

教学难点：抽象数据类型及其操作。

授课内容计算机科学是一门研究数据表示和数据处理的科学。

数据是计算机化的信息，它是计算机可以直接处理的最基本和最重要的对象。

无论是进行科学计算或数据处理、过程控制以及对文件的存储和检索及数据库技术等计算机应用领域中，都是对数据进行加工处理的过程。

因此，要设计出一个结构好效率高的程序，必须研究数据的特性及数据间的相互关系及其对应的存储表示，并利用这些特性和关系设计出相应的算法和程序。

1．1 数据结构的基本概念和术语数据结构是计算机科学与技术专业的专业基础课，是十分重要的核心课程。

所有的计算机系统软件和应用软件都要用到各种类型的数据结构。

因此，要想更好地运用计算机来解决实际问题，仅掌握几种计算机程序设计语言是难以应付众多复杂的课题的。

要想有效地使用计算机、充分发挥计算机的性能，还必须学习和掌握好数据结构的有关知识。

打好“数据结构”这门课程的扎实基础，对于学习计算机专业的其他课程，如操作系统、编译原理、数据库管理系统、软件工程、人工智能等都是十分有益的。

1.1.1 引言在计算机发展的初期，人们使用计算机的目的主要是处理数值计算问题。

当我们使用计算机来解决一个具体问题时，一般需要经过下列几个步骤：首先要从该具体问题抽象出一个适当的数学模型，然后设计或选择一个解此数学模型的算法，最后编出程序进行调试、测试，直至得到最终的解答。

例如，求解梁架结构中应力的数学模型的线性方程组，该方程组可以使用迭代算法来求解。

由于当时所涉及的运算对象是简单的整型、实型或布尔类型数据，所以程序设计者的主要精力是集中于程序设计的技巧上，而无须重视数据结构。

随着计算机应用领域的扩大和软、硬件的发展，非数值计算问题越来越显得重要。

据统计，当今处理非数值计算性问题占用了90%以上的机器时间。

这类问题涉及到的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。

武汉工程职业学院软件技术专业大二2019数据结构与算法测试题第十九单元2（多选+判断）您的姓名： [填空题] *_________________________________1、以下字符串中，是回文字符串的是（）。

*A abcba(正确答案)B 12321(正确答案)C 1221(正确答案)D abcdef2、回文字符串的判断可以使用的方法有（）。

*A 递归方式(正确答案)B 非递归方式利用循环解决(正确答案)C 非递归方式用系统函数解决(正确答案)D 以上答案都正确(正确答案)3、判断字符串a和b是否相等使用错误的方式是（）。

*A if (a==b)(正确答案)B if (a=b)(正确答案)C if (strcpy(a,b))(正确答案)D if (strcmp(a,b)==0)4、以下C语言字符串处理函数(系统函数)是在string.h的头文件中声明的是（）。

*A strlen(正确答案)B strcat(正确答案)C strcpy(正确答案)D strcmp(正确答案)5、回文字符串存储方式一般采用字符数组，则关于字符数组描述正确的是（）。

*A 只能存放字符型数据(正确答案)B 数组是定长的，定义后不可改变(正确答案)C 数组元素占有一片连续的存储单元(正确答案)D 数组元素可以存放不同类型的数据6、下面关于数组概念描述说法正确的是( )一维数组的定义的形式始下：类型说明符数组名[常量表达式]。

[多选题]*A 数组名应符合标识符的命名规则，正式应用中第一个字符应为英文。

(正确答案)B 一维数组就是用一个下标定义的数组,可以存同类型也可以存不同类型数据。

C 常量表达式定义了数组元素的个数(正确答案)D 数组下标从0开始(正确答案)7、有以下程序main(){int a[2][4]={1,12,3,4,5,6,7,8};printf("%d",a[1][3]);}则程序的输出结果不可能是（）。

武汉软件工程职业学院软件技术专业大二2019数据结构第十一单元您的姓名： [填空题] *_________________________________1. (专基)下列选项中关于链表是线性表的哪种存储结构正确的是（）。

[单选题] *链式结构(正确答案)顺序结构散列结构索引结构2. 数据结构中单链表是含有（）个指针域的链表 [单选题] *两三零一(正确答案)3. 在单链表p结点之后插入s结点，正确的操作是（） [单选题] *p->next=s; s->next=p->next;s->next= p->next; p->next=s;(正确答案)p->next=s; p->next= s->next;p->next=s; p->next= s->next;4. (专基)单链表中修改第i个元素的时间复杂度是（）。

[单选题] *O（1）O（n）(正确答案)O（n*n）都不对5. 单链表中删除p指针指向结点的后继则时间复杂度是（假设存在）（） [单选题] *O（n）O（1）(正确答案)O（n*n）都不对6. (专基)线性表L在（）情况下适用于使用链式结构实现。

[单选题] *需不断对L进行删除插入(正确答案)需经常修改L中的结点值L中结点结构复杂L中含有大量的结点7. 带头结点的单链表H为空的条件应该是下面描述正确的是( ) [单选题] *next==NULLH==NULLH->next==NULL(正确答案)以上都不对8. （专基)顺序表和链表分别指（）。

[单选题] *线性表的顺序存储结构和链式存储结构(正确答案)线性表的顺序存储结构和随机存储结构线性表的顺序存储结构和索引存储结构线性表的顺序存储结构和散列存储结构9. 在一个具有n个结点的单链表中修改一个结点数据域的值，时间复杂度是（）[单选题] *O(1)O(n)(正确答案)O(n*n)O(nlog2n)10. 在双向链表的一个结点中有（）个指针 [单选题] *2(正确答案)1311. (专基)单链表中删除p指针指向结点的后继（假设存在）的语句序列是[单选题] *p->next=p->next;p->next=p->next->next;(正确答案)p->next=p;p=p->next;12. 单链表的结点包含两部分：( )域和指针域 [单选题] *指针域链域数据域(正确答案)散列域13. 带头结点的单链表head为空的判断条件是（） [单选题] * head==NULLhead->next ==NULL(正确答案)head->next ==headhead!=NULL14. 顺序表与链表的区别在于（） [单选题] *存储方式不同(正确答案)元素个数不同逻辑关系不一样都不对15. 顺序表与链表的相同点在于（） [单选题] *存储方式相同元素个数不同逻辑关系相同(正确答案)都不对16. 不带头结点的单链表head为空的判断条件是（） [单选题] * head==NULL(正确答案)head->next ==NULLhead->next ==headhead!=NULL17. 单链表插入的时间复杂度（） [单选题] *O（1）(正确答案)O（log2n）O（n）O（n2）18. 删除p结点的后继结点并回收空间，错误的语句序列是（） *p->next= p->next->next;(正确答案)p->next= p->next->next free(p);(正确答案)q=p->next p->next= p->next->next; free(q);q=p->next->next; p->next->next= p->next->next; free(q);(正确答案)19. 对于只在表的首、尾两端进行插入操作的线性表，不宜采用的存储结构为（）*顺序表(正确答案)有头指针的单向链表(正确答案)有头指针和尾指针的双向链表有头指针的单向循环链表(正确答案)20. 在单链表的开始结点之前附加一个结点，不是（） *头指针(正确答案)头结点尾指针(正确答案)尾结点(正确答案)21. 在具有n个结点的单链表中，实现（）的操作，其时间复杂度为O(n) *遍历链表(正确答案)找链表的第i个结点(正确答案)在p指针的结点之后插入一个结点删除p指向结点的后继结点22. L是线性表，已知表长度length的值是5，经过一次插入运算后，length的值不是（） *4(正确答案)7(正确答案)5(正确答案)623. 有关链式存储的存储结构所占存储空间说法错误的是（） *分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针只有一部分，存放结点的值(正确答案)只有一部分，存储表示结点间关系的指针(正确答案)分两部分，一部分存放结点的值，另一部分存放结点所占单元素(正确答案)24. 每一个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式不是（）存储方式 *顺序(正确答案)链式索引(正确答案)散列(正确答案)25. 在单链表中，增加头结点的目的不是（） *使单链表至少有一结点(正确答案)标志表中首结点位置(正确答案)方便运算的实现说明单链表是线性表的链式存储实现(正确答案)26. 两个指针P和Q，分别指向单链表的两个元素，P是Q前驱的条件错误的是（） *P->next==Q->next(正确答案)Q->next== P(正确答案)P->next== QP== Q(正确答案)27. 在一个单链表中，q是p的前驱，若在q、p之间插入s结点，则不能执行（）操作 *s->next=p->next; p->next=s;(正确答案)q->next=s; s->next=p;p->next= s->next; s->next=p;(正确答案)p->next=s; s->next=q;(正确答案)28. 单链表中，p是待删除的结点的前驱结点，则需要执行的操作为：p->next=p->next->next。

武汉软件工程职业学院软件技术专业大二2019年6月度数据结构综合考试您的姓名： [填空题] *_________________________________1. 数据结构里，实参和形参的关系（）。

*A: 实参传给形参(正确答案)B: 实参的类型要与形参一致(正确答案)C: 实参的个数要与实参一致(正确答案)D: 实参的名称要与形参的一致2. (专基)数据结构中，下列时间复杂度复杂度高低比较正确的是（）。

*A: O(2^n)< O(n!)其中2^n表示2的n次幂(正确答案)B: O(n)< O(nlogn)(正确答案)C: O(n)>O(logn)(正确答案)D: O(n!)<O(n^n)其中n^n表示n的n次幂(正确答案)3. 数据结构里，算法的设计要求应包括（）。

*A: 正确性(正确答案)B: 可读性(正确答案)C: 可行性D: 健壮性(正确答案)4. 数据结构里，算法的设计要求不应该包括（）。

*A: 可行性(正确答案)B: 正确性C: 有穷性(正确答案)D: 确定性(正确答案)5. 数据结构里，下列选项中是算法设计要求的是（）。

*A: 正确性(正确答案)B: 健壮性(正确答案)C: 可读性(正确答案)D: 有穷性6. 数据结构里，时间复杂度低于平方阶的是（）。

*A: O(1)(正确答案)B: O(n)(正确答案)C: O(log2n)(正确答案)D: O(nlog2n)(正确答案)7. (专基)下列选项中是算法设计要求的是（）。

*A: 正确性(正确答案)B: 健壮性(正确答案)C: 可读性(正确答案)D: 有穷性8. 数据结构里，函数调用是，形参传给实参，是单向传递的。

（） [单选题] *A:对B:错(正确答案)9. (专基)算法的特性包括：输入、输出、有穷性、确定性、可行性。

（） [单选题] *B:错10. (专基)算法可以没有输出。

（） [单选题] *A:对B:错(正确答案)11. (专基)算法的设计要求中包括算法的有穷性。

湖北工程学院17级软件工程专业大二2019年数据结构与算法模拟题您的姓名： [填空题] *_________________________________1.关于素数描述正确的是（）。

[单选题] *A: 素数就是合数B: 素数不能被本身整除C: 素数又称为质数只能被1和它本省整除(正确答案)D: 素数不仅能被1和它本身整除，还能被其它数整除2.for循环的(表达式1;表达式2;表达式3)中表达式3的作用是（）。

[单选题] * A: 循环的增量表达式(正确答案)B: 循环的条件C: 循环的初值D: 循环体3.哪一种排序，可能存在这种情况：“最后一趟开始之前，所有记录均不在其最终位置上”（）。

[单选题] *A:快速排序B:冒泡排序C:直接插入排序(正确答案)D:简单选择排序4简单选择排序，按照从小到大排序，原始序列是：19 11 17 18 16 15，则经过一趟排序后的结果是（）。

[单选题] *A:11 19 17 18 16 15(正确答案)B:11 15 16 17 18 19C:11 17 18 16 15 19D:19 11 17 18 16 155、关于查找的效率问题，下面说法中正确的是（）。

[单选题] *A:顺序查找一定没有折半查找快B:顺序查找比折半查找快C:折半查找不一定比顺序查找快(正确答案)D:就平均效率而言，顺序查找的效率更高6.青蛙过河案例中，如果河中没有石柱，有y片荷叶的话，那么从左岸到右岸可以过去（）只青蛙。

[单选题] *A: y+1只(正确答案)B: y+2只C: y+3只D: y+4只7.青蛙过河案例中，如果河中有1根石柱，问最少有几片荷叶就能过4只青蛙（）。

[单选题] *A: 1片(正确答案)B: 3片C: 0片D: 2片8.某些排序存在不相邻记录之间的交换，因此是不稳定排序，以下是不稳定的排序是（）。

[单选题] *A: 快速排序(正确答案)B: 冒泡排序C: 直接插入排序D: 都不对9.从算法的时间复杂度来看，O(nlog2n)是哪种排序的时间复杂度（）。

武汉软件工程职业学院软件技术专业大二2019数据结构第十单元您的姓名： [填空题] *_________________________________1. 数据是被计算机识别、存储、处理用于描述客观事物的（） [单选题] *图像符号(正确答案)文字数字2. 在逻辑上可以把数据结构分成：（） [单选题] *动态结构和静态结构紧凑结构和非紧凑结构线性结构和非线性结构(正确答案)内部结构和外部结构3. 数据对象：是性质相同的数据元素的集合，是数据的（） [单选题] *父集等级子集(正确答案)以上都不对4. 数据的逻辑结构：是指数据元素之间的（） [单选题] *相互关系(正确答案)存储关系无关系以上都不对5. 不是顺序表特点的是（） [单选题] *插入、删除需要移动元素能随机访问任一元素事先估计存储空间所需空间与线性表长度成反比(正确答案)6. 线性表L=(a,b,c,d,e),定位查找第三个数据元素，结果为（） [单选题] *abcdbcc(正确答案)cd7. (专基)下列选项中关于链表是线性表的哪种存储结构正确的是（）。

[单选题] *链式结构(正确答案)顺序结构散列结构索引结构8. 用链表存储的线性表，其特点是（） [单选题] *便于随机存取花费的存储空间比顺序表少花费的存储空间比顺序表多(正确答案)数据元素的物理顺序与逻辑顺序相同9. (专基)以下是单链表的优点的是（）。

[单选题] *存取方便，直接可以获得任何一个元素插入、删除元素方便，避免移动大量的元素。

(正确答案)在内存里结点与结点之间是连续的以上都不是10. (专基)线性表L在（）情况下适用于使用链式结构实现。

[单选题] *需不断对L进行删除插入(正确答案)需经常修改L中的结点值: L中结点结构复杂L中含有大量的结点11. 单链表中删除p指针指向结点的后继（假设存在）的语句序列正确的是（）。

[单选题] *p->next=p->next;p->next=p->next->next;(正确答案)p->next=p;p=p->next;12. 无需为表中的元素之间的逻辑关系而增加额外的存储空间是（）的优点 [单选题] *顺序表(正确答案)链表结构体指针13. 在数据结构中，线性结构是（） [单选题] *一对一关系(正确答案)一对多关系多对多关系没有关系14. 常用的数据的存储结构有（） *顺序存储结构(正确答案)链式存储结构(正确答案)花式存储结构随机存储结构15. 下列有关于线性表的叙述中正确的内容是（） *线性表采用链接存储，可以占用一片连续的存储单元。

武汉软件工程职业学院软件技术专业大二2019数据结构第十二单元测试您的姓名： [填空题] *_________________________________1. 单链表中删除p指针指向结点的后继则时间复杂度是（假设存在）（） [单选题] *O（n）O（1）(正确答案)O（n*n）都不对2. 在一个具有n个结点的单链表中修改一个结点数据域的值，时间复杂度是（）[单选题] *O(1)O(n)(正确答案)O(n*n)O(nlog2n)3. 在双向链表的一个结点中有（）个指针 [单选题] *2(正确答案)134. (专基)单链表中删除p指针指向结点的后继（假设存在）的语句序列是 [单选题] *p->next=p->next;p->next=p->next->next;(正确答案)p->next=p;p=p->next;5. 下列选项中代表链表定位查找第i个元素的时间复杂度是（） [单选题] *O(1）O(n)(正确答案)O(n*n)O(0)6. 单链表的结点包含两部分：( )域和指针域 [单选题] *指针域链域数据域(正确答案)散列域7. 带头结点的单链表head为空的判断条件是（） [单选题] *head==NULLhead->next ==NULL(正确答案)head->next ==headhead!=NULL8. 顺序表与链表的区别在于（） [单选题] *存储方式不同(正确答案)元素个数不同逻辑关系不一样都不对9. 顺序表与链表的相同点在于（） [单选题] *存储方式相同元素个数不同逻辑关系相同(正确答案)都不对10. 不带头结点的单链表head为空的判断条件是（） [单选题] * head==NULL(正确答案)head->next ==NULLhead->next ==headhead!=NULL11. 单链表插入的时间复杂度（） [单选题] *O（1）(正确答案)O（log2n）O（n）O（n2）12. 以下论断正确的是( )。

武汉软件工程职业学院软件技术专业大二2019数据结构第一单元检测题您的姓名： [填空题] *_________________________________1. 定义了一个结构体类型的普通变量，要使用其成员，则应该在变量和成员之间加（）。

[单选题] *.(正确答案)><&2. 在定义结构体时会有一对{ }，在{ }后不能省略的符号是下列哪一项（）。

[单选题] *;(正确答案),"":3. (专基)下列选项中关于什么是结构体描述正确的是（）。

[单选题] *结构体是高级语言中的一种构造类型(正确答案)结构体是汇编语言中的一种指针类型结构体是高级语言中的一种指针类型结构体是C语言中的基本类型4. struct的作用是（） [单选题] *定义整型变量定义结构体类型(正确答案)定义浮点类型定义字符型变量5. 定义了一个学生结构体，其中一个成员变量是年龄，应该使用（）类型。

[单选题] *int(正确答案)float小数浮点数6. p是一个结构体指针变量，它有一个成员变量叫sex，则使用格式正确的是（）。

[单选题] *p->sex(正确答案)p%sexp#sexp&sex7. 下列选项中是用来定义结构体的关键字是（）。

[单选题] *struct(正确答案)functionstaticstack8. product属于结构体类型，要定义这种类型的变量pro定义正确的是（）。

[单选题] *struct product pro;(正确答案)pro product;struct pro;以上都不对9. 数据结构里，树形关系是（）。

[单选题] *一对一关系一对多关系(正确答案)多对多关系没有关系10. 数据结构里，线性结构是（）。

[单选题] *一对一关系(正确答案)一对多关系多对多关系没有关系11. 数据结构里，顺序存储是指（）。

[单选题] *逻辑上相邻的元素物理上也紧邻(正确答案)逻辑上相邻的元素物理上不一定紧邻逻辑上相邻的元素物理上一定不紧邻以上都不对12. 数据结构里，数据结构是相互之间存在一种或多种特定关系的（）的集合。

湖北工程学院软件工程专业大二2016-2017数据结构期中测试1.下面关于线性表的叙述中，错误的是（） [单选题] *A.线性表采用顺序储存，必须占用一片连续的储存单元。

B.线性表采用顺序储存，便于进行插入和删除操作。

(正确答案)C.线性表采用链接储存，不必占用一片连续的储存单元。

D.线性表采用链接储存，便于出入和删除操作。

2. 在有n个结点顺序表上做插入，删除结点运算的时间复杂度为（）。

[单选题] *A.O(1)B.O(n)(正确答案)C.O(n^2)D.O(log2n)3.两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素前驱条件是（） [单选题] *A.P->next==Q->nextB.P->next==Q(正确答案)C.Q->next==PD.P==Q4.在单链表中，增加头结点的目的（） [单选题] *A.使单链表至少有一个结点B.标志表中首结点的位置C.方便运算实现(正确答案)D.说明该单链表是线性表的链式储存结构5.在顺序表中，只要知道（）就可以求出任意一个结点的存储地址 [单选题] * A。

，基地址B．结点大小C．向量大小D.基地址和结点大小(正确答案)6.链表不具备的特点是（） [单选题] *A随机访问(正确答案)B不必事先估计存储空间C插入删除时不需移动元素D所需空间与线性表成正比7.在（）的运算中，使用顺序表比链表好 [单选题] *A插入B根据序号查找(正确答案)C删除D根据元素查找8.在单链表指针为P的节点之后插入指针为S的结点，正确的查找条件是（） [单选题] *A,p->next=s;s->next=p->nextB,s->next=p->next;p->next=s(正确答案)C,p->next=s;p->next=s->nextA,p->next=s->next;p->next=s9.用链表表示线性表的优点（） [单选题] *A便于进行插入和删除操作(正确答案)B便于随机存储C占用的存储空间较顺序表少D元素的物理顺序与与逻辑顺序一致10在一个长度为n的顺序表中，若要删除第i(1≤i≦n)个元素，则需向前移动（）个元素 [单选题] *An-i+1Bn-i-1Cn-i(正确答案)Di11在一个长度为n的顺序表中，若要在第i(1≤i≤n)个元素之前插入一个元素，则需向后移动（）个元素 [单选题] *An-i+1(正确答案)Bn-i-1Cn-iDi12设P为指向单循环链表上某结点的指针，则*p的直接前驱（） [单选题] *A找不到B查找时间复杂度为O(1)C查找时间复杂度为O(n)(正确答案)D查找结点的次数约为n13.等概率情况下，在有n个结点的顺序表上做插入结点运算，需平均移动结点的数目为（）。

武汉职业技术学院软件技术专业大二2019数据结构与算法第十三单元测试题(多选+判断)您的姓名： [填空题] *_________________________________1.快速排序的特性描述正确的是（）。

[多选] *A.快速排序是稳定排序B.快速排序不稳定排序(正确答案)C.快速排序的时间复杂度是O(nlog2n)(正确答案)D.快速排序的时间复杂度是O(n*n)2.冒泡排序是稳定的排序，原因是（）。

[单选] [单选题] *A.不存在不相邻的记录的交换(正确答案)B.存在不相邻的记录的交换C.晓得记录放在前面，大的记录放在后面D.以上答案都不对3.下列排序中是不稳定排序的是（）。

[多选] *A.希尔排序(正确答案)B.快速排序(正确答案)C.冒泡排序D.直接插入排序4.N个记录的待排序列，采用冒泡排序，总共比较次数可能是（）。

[多选] *A.N-2B.N-1(正确答案)C.N*(N-1)/2(正确答案)D.N*(N+1)/25.根据选项的描述，冒泡排序是（）。

[多选] *A.内排序(正确答案)B.稳定排序(正确答案)C.交换排线(正确答案)D.插入排序6.关于冒泡排序的比较次数和排序趟数描述正确的是（）。

[多选] *A.N个记录最多N-1趟排序即可完成(正确答案)B.N个记录最少比较N-1次，可完成排序，这是记录完全有序的情况(正确答案)C.N个记录最多比较N*(N-1)/2次可完成排序，这是记录完全逆序的情况。

(正确答案)D.在一趟排序中若无记录交换，就会停止排序。

(正确答案)7.冒泡排序的时间复杂度最好情况和最坏情况分别是（）。

[多选] *A.O(n)(正确答案)B.O(n*n)(正确答案)C.O(1)D.O(log2n)8.冒泡排序的时间复杂度不是（）。

[多选] *A.O(n*n)B.O(n)(正确答案)C.O(1)(正确答案)D.O(log2n)(正确答案)9.递归算法需要有下列哪三项条件（）。

武汉软件工程职业学院软件技术专业大二2019年6月度数据结构日考综合3您的姓名： [填空题] *_________________________________1. 在队列这章中，循环队列解决了普通队列遇到的（）问题。

[单选题] *A: 空间不足B: 假溢出(正确答案)C: 元素过多D: 分配不出空间2. 数据结构里，n个元素的顺序表,删除元素平均需要移动（）个元素。

[单选题] * A: (n-1)/2(正确答案)B: n/2C: n-1D: n-23. 数据结构里，栈是后进先出的线性表，后进先出英文是（）。

[单选题] *A: Last In First Out(正确答案)B: First In First OutC: 不确定D: 都不对4. 链表与线性表的关系是（）。

[单选题] *A: 链表是线性表采用链式存储结构。

(正确答案)B: 链表是线性表采用顺序存储结构。

C: 链表等价于线性表D: 链表和顺序表都不是线性表5. 线性结构中，线性表采用链式存储的好处是（）。

[单选题] *A: 可以随机访问任何一个元素B: 元素都存在一片连续的存储空间C: 无需预估存储空间的大小(正确答案)D: 插入删除需要移动大量元素6. 树若不是空树，则有一个结点叫做什么，它没有前驱（）。

[单选题] * A: 叶子B: 根结点(正确答案)C: 树叉D: 终端结点7. 数据结构里，结点的度是指（）。

[单选题] *A: 结点挂接的子树的数目B: 零C: 叶子的个数树是( A )的逻辑关系。

A: 一对多B: 一对一C: 二对一D: 多对多(正确答案)8. 度为0的结点又称为（）。

[单选题] *A: 叶子(正确答案)B: 根结点C: 分支结点D: 内部结点9. 在树的概念中，下列选项中关于树的兄弟描述正确的是（） [单选题] *A: 双亲是同一个结点(正确答案)B: 双亲是不同的结点C: 在树中不同的层D: 都不对10. 数据结构里，C结点有3个堂兄弟(不算自己)，B是C的双亲，则B的度是（）。

武汉软件工程职业学院软件技术专业大二2019数据结构第一周测试1.数据结构里，输入、输出、有穷性、确定性、可行性是算法的五大特性（）。

[单选题] *A 对(正确答案)B 错2.数据结构里，算法具有模糊性，相同的情况可能产生不同的结果（）。

[单选题] *A 对B 错(正确答案)3.数据元素与数据项的关系是（）。

[单选题] *A: 数据元素<数据项B: 数据元素>数据项(正确答案)C: 数据元素=数据项D: 数据元素与数据项没有关系4.数据项：一个数据元素可以由若干个数据项组成。

数据项是数据不可分割的（）。

[单选题] *A: 基本单位B: 最小单位(正确答案)C: 最大单位D: 都不对5.数据结构是相互之间存在一种或多种特定关系的（）的集合。

[单选题] * A: 数据元素(正确答案)B: 图像C: 数据项D: 文字6.存储结构也称为物理结构是指（）。

[单选题] *A: 是指数据元素之间的相互关系。

B: 是指数据之间逻辑关系。

C: 是指逻辑结构本身。

D: 指数据的逻辑结构在计算机中的存储形式。

(正确答案)7.集合结构是一种逻辑结构，它的元素之间存在（）关系。

[单选题] *A: 多对多的关系B: 数据元素除了同属于一个集合外，它们之间没有其他关系(正确答案) C: 一对多的关系D: 一对一的关系8.int query(int x){x+=2;return x;}void main(){int z=6;printf("%d%d",query(z),z);}该程序的运行结果是（）。

[单选题] [单选题] *A: 86(正确答案)B: 68C: 88D: 6611.void swap(int a,int b){int t;t=a;a=b;b=t;}void main(){int x=9,y=3;swap(x,y);printf("%d%d",x,y);}该程序运行的结果是（）。