湖北工业大学软件工程专业大二2027-2018学年数据结构周考

1、湖北工业大学软件工程专业大二2027-2018学年数据结构周考您的姓名： 填空题 *_1.数据结构中，算法要便于阅读、理解和交流；是指算法设计要求中的（）。 单选题 *A: 可读性(正确答案)B: 健壮性C: 正确性D: 时间效率高和存储量低2.在n个元素的顺序表中，删除第i个位置元素需要移动几个元素（）。 单选题 *A: n-i(正确答案)B: n-i+1C: n-1D: n-23.在n个元素的顺序表中，在第i个位置插入元素需要移动多少个元素（）。 单选题 *A: n-iB: n-i+1(正确答案)C: n-1D: n-24.顺序表中进行，插入删除需要（）。 单选题 *A: 交换若干元素B:

2、 插入大量元素C: 删除大量元素D: 移动大量元素(正确答案)5.选项中代表顺序表存取第i个元素的时间复杂度是（）。 单选题 *A: O(1)(正确答案)B: O(n)C: O(n*n)D: O(1*n)6.数据结构中，下列选项中代表顺序表插入元素的时间复杂度是（）。 单选题 *A: O(1)B: O(n)(正确答案)C: O(n*n)D: O(log2n)7.带头结点的单链表H为空的条件是（）。 单选题 *A: H->next=NULL(正确答案)B: H=NULLC: next=NULLD: 以上都不对8.在n个结点的单链表中，查找第i个元素，和修改第i个元素的时间复杂度都是（）。

3、单选题 *A: O(1)B: O(n)(正确答案)C: O(n*n)D: 都不对9单链表的结点包含两部分：数据域和（）。 单选题 *A: 指针域(正确答案)B: 索引域C: 散列域D: 数据域10.子串的定位操作通常称为串的（）。 单选题 *A: 模式匹配(正确答案)B: KMPC: 交叉连接D: 索引扫描11.模式匹配的改进算法是D.E.Knuth与V.R.Pratt和J.H.Morris同时发现的，因此人们称它为克努特-莫里斯-普拉特操作简称（）。 单选题 *A: KMP算法(正确答案)B: Prime算法C: 克鲁斯卡尔算法D: 迪杰斯特拉算法15.在单链表中P指针指向的结点后插入一个元

4、素的时间复杂度（）。 单选题 *A: O(n)B: O(1)(正确答案)C: O(n*n)D: O(log2n)17单链表中在删除p指针指向的结点后继结点并回收空间的语句是,指针域用next表示（）。 单选题 *A: p->next=p->next->next; free(p->next);B: q=p->next; p->next=p->next->next; free(q);(正确答案)C: p->next=p->next->next;D: q=p->next; p->next=p->next->ne

5、xt; free(p);18.在链表的创建过程中需要使用C语言的中什么语句为申请的结点分配存储空间（）。 单选题 *A: malloc(正确答案)B: freeC: structD: node20.一个顺序存储的表中为int类型的数据，按标准编译器int占4字节计算，第一个元素a1存在12080的地址单元格开始的存储空间中，则第11个元素a11存储在以（）开头的单元中。 单选题 *A: 12084B: 12120(正确答案)C: 12124D: 121321.数据结构中，算法要便于阅读、理解和交流；是指算法设计要求中的（）。 单选题 *A: 可读性(正确答案)B: 健壮性C: 正确性D: 时间

6、效率高和存储量低2.在n个元素的顺序表中，删除第i个位置元素需要移动几个元素（）。 单选题 *A: n-i(正确答案)B: n-i+1C: n-1D: n-23.在n个元素的顺序表中，在第i个位置插入元素需要移动多少个元素（）。 单选题 *A: n-iB: n-i+1(正确答案)C: n-1D: n-24.顺序表中进行，插入删除需要（）。 单选题 *A: 交换若干元素B: 插入大量元素C: 删除大量元素D: 移动大量元素(正确答案)5.下列选项中代表顺序表存取第i个元素的时间复杂度是（）。 单选题 *A: O(1)(正确答案)B: O(n)C: O(n*n)D: O(1*n)6.数据结构中，下

7、列选项中代表顺序表插入元素的时间复杂度是（）。 单选题 *A: O(1)B: O(n)(正确答案)C: O(n*n)D: O(log2n)7.带头结点的单链表H为空的条件是（）。 单选题 *A: H->next=NULL(正确答案)B: H=NULLC: next=NULLD: 以上都不对8.在n个结点的单链表中，查找第i个元素，和修改第i个元素的时间复杂度都是（）。 单选题 *A: O(1)B: O(n)(正确答案)C: O(n*n)D: 都不对10.子串的定位操作通常称为串的（）。 单选题 *A: 模式匹配(正确答案)B: KMPC: 交叉连接D: 索引扫描11.模式匹配的改进算法是

8、D.E.Knuth与V.R.Pratt和J.H.Morris同时发现的，因此人们称它为克努特-莫里斯-普拉特操作简称（）。 单选题 *A: KMP算法(正确答案)B: Prime算法C: 克鲁斯卡尔算法D: 迪杰斯特拉算法15.在单链表中P指针指向的结点后插入一个元素的时间复杂度（）。 单选题 *A: O(n)B: O(1)(正确答案)C: O(n*n)D: O(log2n)18.在链表的创建过程中需要使用C语言的中什么语句为申请的结点分配存储空间（）。 单选题 *A: malloc(正确答案)B: freeC: structD: node20.一个顺序存储的表中为int类型的数据，按标准编译

9、器int占4字节计算，第一个元素a1存在12080的地址单元格开始的存储空间中，则第11个元素a11存储在以（）开头的单元中。 单选题 *A: 12084B: 12120(正确答案)C: 12124D: 121321.n个元素的顺序表,删除元素平均需要移动几个元素（）。 单选题 *A: (n-1)/2(正确答案)B: n/2C: n-1D: n-22.数据结构中，顺序表的存储密度较为紧密，可以达到（）都存放数据。 单选题 *A: 1(正确答案)B: 0.8C: 0.5D: 03.顺序表可以实现的操作有（）。 单选题 *A: 随机获得第i个元素(正确答案)B: 不需要移动元素情况下，删除第i个元

10、素C: 不需要移动元素情况下，在第i个位置插入元素D: 起初不分配顺序表的所有空间，每插入一个元素现分配存储空间4.顺序表中插入、删除操作，需要移动元素，约移动表中（）的元素。 单选题 *A: 一半(正确答案)B: 三分之一C: 四分之一D: 全部5.两个非递增有序的顺序表可以（）成一个非递增有序的顺序表。 单选题 *A: 合并(正确答案)B: 插入C: 删除D: 修改6.下列选项中代表顺序表存取第i个元素的时间复杂度是（）。 单选题 *A: O(1)(正确答案)B: O(n)C: O(n*n)D: O(1*n)7.顺序表各种算法，都有其时间复杂度，在n个结点的顺序表中，删除第i(1in)个结

11、点的时间复杂度是（）。 单选题 *A: O(1)B: O(n)(正确答案)C: O(nlog2n)D: O(log2n2)8.下列选项中代表顺序表插入元素的时间复杂度是（）。 单选题 *A: O(1)B: O(n)(正确答案)C: O(n*n)D: O(log2n)10.下列选项中关于链表是线性表的哪种存储结构正确的是（）。 单选题 *A: 链式结构(正确答案)B: 顺序结构C: 散列结构D: 索引结构11.以下是单链表的优点的是（）。 单选题 *A: 存取方便，直接可以获得任何一个元素B: 插入、删除元素方便，避免移动大量的元素。(正确答案)C: 在内存里结点与结点之间是连续的D: 以上都不

12、是12.单链表中修改第i个元素的时间复杂度是（）。 单选题 *A: O(1)B: O(n)(正确答案)C: O(n*n)D: 都不对13.模式匹配通常是指（）。 单选题 *A: 子串的定位操作(正确答案)B: 字符串的拷贝操作C: 字符串的截取操作D: 字符串的比较操作14.KMP模式匹配算法的改进之处是（）。 单选题 *A: 主串指针不需要回溯(正确答案)B: 模式串的指针来回移动C: 主串的指针也会回到之前比较过的字符D: 时间复杂度可以达到O(n*m)1.算法的存储量高低用（）来衡量。 单选题 *A: 时间复杂度B: 空间复杂度(正确答案)C: 算法的步骤数D: 算法的长度2.算法应当满

13、足具体问题的需求，正确解决问题；是指算法设计要求中的（）。 单选题 *A: 正确性(正确答案)B: 可读性C: 健壮性D: 时间效率高和存储量低3.算法要便于阅读、理解和交流；是指算法设计要求中的（）。 单选题 *A: 可读性(正确答案)B: 健壮性C: 正确性D: 时间效率高和存储量低4.时间复杂度中，O(1)表示：（）。 单选题 *A: 常数阶(正确答案)B: 线性阶C: 平方阶D: 立方阶5.数据结构中，数据不可分割的的最小单位是（）。 单选题 *A: 数据本身B: 数据元素C: 数据项(正确答案)D: 以上都不对6.数据结构中，以下是算法的设计要求是（）。 单选题 *A: 正确性(正确

14、答案)B: 数据C: 数据元素D: 二义性7.数据结构中，算法的设计要求包括正确性、（）、健壮性、效率与时间效率高和存储量低。 单选题 *A: 二义性B: 可读性(正确答案)C: 连贯性D: 模糊性8.数据结构中，算法的设计要求中健壮性是指（）。 单选题 *A: 算法可以忽略特殊情况B: 算法应该能对输入数据不合法的情况做合适的处理(正确答案)C: 算法可以不关注不合法的数据D: 算法要便于阅读、理解和交流9.顺序表中进行，插入删除需要（）。 单选题 *A: 交换若干元素B: 插入大量元素C: 删除大量元素D: 移动大量元素(正确答案)10.顺序表的删除元素，从该元素之后所有元素都要（）。 单

15、选题 *A: 向前移动(正确答案)B: 向后移动C: 原地不动D: 删除这些元11.顺序表的逻辑结构属于（）。 单选题 *A: 线性结构(正确答案)B: 集合结构C: 树形结构D: 图形结构12.顺序表的存储结构属于（）。 单选题 *A: 顺序存储结构(正确答案)B: 链式存储结构C: 索引存储结构D: 散列存储结构13.顺序表的存储密度较为紧密，可以达到（）都存放数据。 单选题 *A: 1(正确答案)B: 0.8C: 0.5D: 014.顺序表是常用的数据结构，顺序表具有的特点是（）。 单选题 *A: 插入、删除不需要移动元素B: 可随机访问任一元素(正确答案)C: 不必事先估计存储空间D:

16、 所需空间与线性表长度成反比15.每种存储结构有其优缺点，下面是顺序存储结构的优点的是（）。 单选题 *A: 存储密度大(正确答案)B: 插入运算方便C: 删除运算方便D: 可方便地用于各种逻辑结构的存储表示16.顺序表各种算法，都有其时间复杂度，在n个结点的顺序表中，删除第i(1in)个结点的时间复杂度是（）。 单选题 *A: O(1)B: O(n)(正确答案)C: O(nlog2n)D: O(log2n2)17.以下是单链表的优点的是（）。 单选题 *A: 存取方便，直接可以获得任何一个元素B: 插入、删除元素方便，避免移动大量的元素。(正确答案)C: 在内存里结点与结点之间是连续的D:

17、以上都不是18.单链表中修改第i个元素的时间复杂度是（）。 单选题 *A: O(1)B: O(n)(正确答案)C: O(n*n)D: 都不对19.单链表中查找第i个元素的时间复杂度是（）。 单选题 *A: O(1)B: O(n)(正确答案)C: O(n*n)D: 都不对20.单链表中在p指针后插入元素的时间复杂度是（）。 单选题 *A: O(1)(正确答案)B: O(n)C: O(n*n)D: 都不对数据结构里，时间复杂度记作：（）。 单选题 *A: T(n)=O(f(n)(正确答案)B: S(n)=O(f(n)C: T(n)=f(n)D: S(n)=f(n)数据结构里，空间复杂度记作：（）。

18、 单选题 *A: T(n)=O(f(n)B: S(n)=O(f(n)(正确答案)C: T(n)=f(n)D: S(n)=f(n)数据结构里，时间复杂度高于O(n)的有（）。 *A: O(log2n)B: O(nlog2n)(正确答案)C: O(n*n)(正确答案)D: O(n!)(正确答案)21. KMP算法比较原始的模式匹配算法的优点在于（）。 *A: 每趟匹配过程出现字符比较不等时，不需要回溯指向主串指针(正确答案)B: 而是利用已经得到的“部分匹配”的结果将模式串向右“滑动”尽可能远的一段距离后，继续进行比较(正确答案)C: 指向主串的指针回溯到某一位置后继续进行模式匹配比较D: 时间复

19、杂可以达到O(m*n),m、n分别是主串和模式串的长度22. KMP模式匹配算法是由（）同时发现的，因此而得名。 *A: 莫里斯(正确答案)B: 克努特(正确答案)C: 普拉特(正确答案)D: 克鲁伊特23. C语言中字符串处理函数描述正确的是（） *A: strcmp是字符串比较函数(正确答案)B: strcat是字符串连接函数(正确答案)C: strlen是求字符串的长度的函数(正确答案)D: strcpy是字符串拷贝函数(正确答案)24. 定义字符数组正确的是（）。 *A: char s="Student"(正确答案)B: char s7="Student&

20、quot;C: char s7='S','t','u','d','e','n','t'(正确答案)D: char s="Student"(正确答案)25. 定义字符数组char s="database"问该数组s的长度不应该是（）。 *A: 8(正确答案)B: 9C: 7(正确答案)D: 6(正确答案)26.共有10个double型的元素(double占8字节)，存与顺序表中，第一个元素的首地址100开始的单元格，则第五个元素不可能在（）开头的

21、单元格。 *A: 132B: 140(正确答案)C: 148(正确答案)D: 124(正确答案)27. 顺序表插入、删除分别需要移动（）个元素。 *A: n-i(正确答案)B: n-i+1(正确答案)C: n-1D: n-228. 数据结构中，度量一个程序的执行时间通常有两种方法：（）。 *A: 事后统计方法(正确答案)B: 事前分析估算的方法(正确答案)C: 空间复杂度分析法D: 渐近式分析方法29.数据结构中，下列时间复杂度复杂度高低比较正确的是（）。 *A: O(2n)< O(n!)其中2n表示2的n次幂(正确答案)B: O(n)< O(nlogn)(正确答案)C: O(n)

22、>O(logn)(正确答案)D: O(n!)<O(nn)其中nn表示n的n次幂(正确答案)30.数据结构中，属于算法的设计要求的是（）。*B: 可读性(正确答案)C: 可行性D: 健壮性(正确答案)A：正确性(正确答案)21.共有10个double型的元素(double占8字节)，存与顺序表中，第一个元素的首地址100开始的单元格，则第五个元素不可能在（）开头的单元格。 *A: 132B: 140(正确答案)C: 148(正确答案)D: 124(正确答案)22. 关于顺序表、链表，以下描述错误的是（）。 *A: 链表中的头结点仅起到标识的作用。(正确答案)B: 顺序存储方式插入和删

23、除时效率太低，因此它不如链式存储方式好。(正确答案)C: 顺序存储方式只能用于存储线性结构。(正确答案)D: 线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。24.若线性表不空，关于线性结构的描述正确的是（）。 *A: 存在唯一的一个称为“第一个”的元素(正确答案)B: 存在唯一的一个称为“最后一个”的元素(正确答案)C: 除了首元素外，每个元素都有唯一的直接前驱(正确答案)D: 除了尾元素外，每个元素都有唯一的一个直接后继(正确答案)25.以下算法中时间复杂度是O(n)的是（）。 *A: 顺序表的删除算法(正确答案)B: 顺序表的插入算法(正确答案)C: 静态查找表的顺序查找算

24、法(查找的是某一个数值)(正确答案)D: 顺序表的修改算法26.下面关于线性表的叙述中，正确的是包括（）。 *A: 线性表采用顺序存储，必须占用一片连续的存储单元。(正确答案)B: 线性表采用顺序存储，便于进行插入和删除操作。C: 线性表是一对一的逻辑结构(正确答案)D: 线性表若不空，有且只有一个首元素。(正确答案)27. 在单链表中p是一个指针,指向某结点，next是结点的指针域，想获得p的后继结点(假设存在)，并用q指针指向其后继，则语句是（）。 *A: q=p->next;(正确答案)B: p=p->next;q=p;(正确答案)C: q=q->next;p=q;D:

25、 q=p->next->next;28. 链表具有的特点是（）。 *A: 插入、删除不需要移动元素(正确答案)B: 可随机访问任一元素C: 不必事先估计存储空间(正确答案)D: 所需空间与线性长度成正比(正确答案)29. KMP模式匹配算法是由（）同时发现的，因此而得名。 *A: 莫里斯(正确答案)B: 克努特(正确答案)C: 普拉特(正确答案)D: 克鲁伊29. 删除p指针指向结点的后继结点并回收空间，指针域为next，语句序列不正确的是：（）。 *A: p->next=p->next->next;(正确答案)B: p->next=p->next-&

26、gt;next;free(p);(正确答案)C: q=p->next;p->next=p->next->next;free(q);D: q=p->next->next;p->next->next=p->next->next;free(q);(正确答案)30. 在C语言描述的数据结构算法中，malloc的作用不应该是（）。 *A: 为指针变量分配空间B: 回收指针变量的空间(正确答案)C: 为普通变量分配空间(正确答案)D: 释放普通变量的空间(正确答案)23.数据结构中，顺序表具有的特点是（）。 *A: 插入、删除不需要移动元素B:

27、可随机访问任一元素(正确答案)C: 不必事先估计存储空间D: 所需空间与顺序表长度成正比(正确答案)24.数据结构中，以下顺序表算法中时间复杂度是O(1)的是（）。 *A: 顺序表的删除算法B: 顺序表的插入算法C: 顺序表的查找算法(正确答案)D: 顺序表的修改算法(正确答案)30.在C语言描述的数据结构算法中，malloc的作用不应该是（）。 *A: 为指针变量分配空间B: 回收指针变量的空间(正确答案)C: 为普通变量分配空间(正确答案)D: 释放普通变量的空间(正确答案)数据结构里，时间复杂度高于O(n)的有（）。 *A: O(log2n)B: O(nlog2n)(正确答案)C: O(

28、n*n)(正确答案)D: O(n!)(正确答案)31.单链表的查找很方便，直接可以获得任何一个元素。 判断题 *对错(正确答案)32.单链表的结点包含两部分：数据域和指针域。 判断题 *对(正确答案)错33.顺序存储结构的主要优点是不利于插入或删除操作。 判断题 *对错(正确答案)34.顺序表的修改操作较为困难，时间复杂度是O(n)。 判断题 *对错(正确答案)35. 线性表中除了头结点，每个结点只能有唯一的“直接前驱”。 判断题 *对(正确答案)错36. 线性表中可以有两个称为“最后一个”的元素 。 判断题 *对错(正确答案)37. 数据结构中，定义结构体类型的普通变量，引用其成员变量用.号。 判断题 *对(正确答案)错38. 数据结构中，定义结构体指针变量后，要引用其成员变量用->号。 判断题 *对(正确答案)错39.算法的设计要求中包括算法的可行性。 判断题 *对错(正确答案)40. 在算法时间复杂度中，O(n3)表示平方阶。(B) 填空题_31.顺序表的插入删除操作