数据结构C语言期末考试试题附带复习资料

数据结构（C语言版）1800道题及答案[完整版]数据结构(C语言版)1800道题及答案[完整版]数据结构1800例题与答案第一章绪论一、选择题（每小题2分）1．算法的计算量的大小称为计算的（B ）。

【北京邮电大学2000 二、3 （20/8分）】A．效率 B．复杂性 C．现实性 D．难度2．算法的时间复杂度取决于（C）。

【中科院计算所 1998 二、1 （2分）】A．问题的规模 B．待处理数据的初态 C．A和B D．都不是3．计算机算法指的是（① C ），它必须具备（② B ）这三个特性。

① A．计算方法B．排序方法C．解决问题的步骤序列 D．调度方法② A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性C．确定性、有穷性、稳定性 D．易读性、稳定性、安全性【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（ B ）。

【中山大学 1998 二、1（2分）】A．程序 B．问题求解步骤的描述C．要满足五个基本特性 D．A和C.5．下面关于算法说法错误的是（ D ）【南京理工大学 2000 一、1（1.5分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（C ）【南京理工大学2000 一、2 （1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（ C ）两大类。

【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（D ）。

数据结构c语言版期末考试复习试题[1]《数据结构与算法》复习题一、选择题。

1．在数据结构中，从逻辑上可以把数据结构分为CA．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构2．数据结构在计算机内存中的表示是指AA．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系3．在数据结构中，与所使用的计算机无关的是数据的A结构。

A．逻辑B．存储C．逻辑和存储D．物理4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。

A．数据的处理方法B．数据元素的类型C．数据元素之间的关系D．数据的存储方法5．在决定选取何种存储结构时，一般不考虑A。

A．各结点的值如何B．结点个数的多少C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。

6．以下说法正确的是D。

A．数据项是数据的基本单位数据元素是数据的基本单位B．数据元素是数据的最小单位数据项是数据的最小单位C．数据结构是带结构的数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构7．算法分析的目的是C，算法分析的两个主要方面是A。

（1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进D．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度B．正确性和简明性C．可读性和文档性D．数据复杂性和程序复杂性8．下面程序段的时间复杂度是O(n2)。

=0;for(I=0;ium=;9．下面程序段的时间复杂度是O(n某m)for(i=0;i10．下面程序段的时间复杂度是O(log3n)i＝0；while（i<=n）i=i某3；11．在以下的叙述中，正确的是BA．线性表的顺序存储结构优于链表存储结构B．二维数组是其数据元素为线性表的线性表C．栈的操作方式是先进先出桟—先进后出队—先进先出D．队列的操作方式是先进后出12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B。

1 绪论沈阳理工大学应用技术学院信息与控制学院计算机科学与技术教研室2011-5-8数据结构复习题：绪论单选题1、在数据结构中，与所使用的计算机无关的数据叫_____结构。

A存储|B物理|C逻辑|D物理和存储2、在数据结构中，从逻辑上可以把数据结构分成______。

A动态结构和静态结构|B紧凑结构和非紧凑结构|C线性结构和非线性结构|D内部结构和外部结构图3、数据结构在计算机内存中的表示是指_______。

数据的存储结构|数据结构|数据的逻辑结构|数据元素之间的关系4、在数据结构中，与所使用的计算机无关的是数据的______结构。

逻辑|存储|逻辑和存储|物理5、在以下的叙述中，正确的是_____。

线性表的线性存储结构优于链表存储结构|二维数组是其数据元素为线性表的线性表|栈的操作方式是先进先出|队列的操作方式是先进后出6、在决定选取何种存储结构时，一般不考虑_______。

各结点的值如何|结束个数的多少|对数据有哪些运算|所用编程语言实现这种结构是否方便7、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储_______。

数据的处理方法|数据元素的类型|数据元素之间的关系|数据的存储方法8、下面说法错误的是_______。

(1)算法原地工作的含义是指不需要任何额外的辅助空间(2)在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法(3)所谓时间复杂度是指最坏情况下，估计算法执行时间的一个上界(4)同一个算法，实现语句的级别越高，执行效率越低(1)|(1)、(2)|(1)、(4)|(3)9、通常要求同一逻辑结构中的所有数据元素具有相同的特性。

这意味着______。

数据元素具有同一特点|不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致|每个数据元素都一样|数据元素所包含的数据项的个数要相等10、以下说法正确的是_______。

数据元素是数据的最小单位|数据项是数据的基本单位|数据结构是带结构的数据项的集合|一些表面上很不相同的数据可以有相同的逻辑结构11、____是数据的最小单元,_____是数据的基本单位.数据项|数据元素|信息项|表元素12、数据结构是指_____以及它们之间的_____.(1)数据元素(2)结构|(1)计算方法(2)关系|(1)逻辑存储(2)运算|(1)数据映像(2)算法13、计算机所处理的数据一般具备某种内在的关系,这是的指_____.数据和数据之间存在的某种关系|元素和元素之间存在某种关系|元素内部具有某种结构|数据项和数据项之间存在某种关系14、数据的逻辑结构可以分为_____两类.动态结构和表态结构|紧凑结构和非紧凑结构|线性结构和非线性结构|内部结构和外部结构15、数据的逻辑结构是指_____关系的整体.数据元素之间逻辑|数据项之间逻辑|数据类型之间|存储结构之间16、在存储数据时,通常不仅要存储各数据元素的值,而且还要存储_____.数据的处理方法|数据元素的类型|数据元素之间的关系|数据的存储方法17、在数据的存储结构中,一个存储结点存储一个_____.数据项|数据元素|数据结构|数据类型18、在计算机的存储器中表示时,物理地址和逻辑地址直接对应并且是连续的,称之为_____.逻辑结构|顺序存储结构|链式存储结构|以上都对19、数据采用链式存储结构时,要求_____.每个结点用占一片连续的存储区域|所有结点占用一片连续的存储区域|结点的最后一个数据域是指针类型|每个结点有多少个后继,就设多少个指针域20、数据的运算_____.效率与采用何种存储结构有关|是根据存储结构来定义的|有算术运算和关系运算两大类|必须用程序设计语言来描述21、下列说法中,不正确的是_____.数据元素是数据的基本单位|数据项是数据中不可分割的最小可标识单位|数据可由若干个数据元素构成|数据项可由若干个数据元素构成22、_____不是算法的基本特性.可行性|长度有限|在规定的时间内完成|确定性23、计算机中算法指的是解决某一问题的有限运算序列,它必须具备输入、输出、_____.可行性、可移植性和可扩充性|可行性、有穷性和确定性|确定性、有穷性和稳定性|易读性、稳定性和确定性24、以下不属于算法特性的是_____.可行性|有输入|确定性|健壮性25、下面关于算法的说法正确的是_____.算法最终必须由程序实现|算法的有穷性是对于任意的一组输入值必须在有穷步骤后结束|算法的可行性是指指令不能有二义性|以上几个都是错误的26、算法的时间复杂度与______有关问题规模|计算机硬件性能|编译程序质量|程序设计语言27、算法分析的主要任务是分析_____.算法是否具有较好的可读性|算法中是否存在语法错误|算法的功能是否符合设计要求|算法的执行时间和问题规模之间的关系28、某算法的时间复杂度为O(n2),表明该算法的_____.问题规模是n2|执行时间等于n2|执行时间与n2成正比|问题规模与n2成正比29、算法分析的目的是_____.找出数据结构的合理性|研究算法中输入和输出关系|分析算法的效率以求改进|分析算法的易读性和文档性30、线性表是具有n个______的有限序列。

数据结构c语言版试题大全(含答案)数据结构C语言版试题大全（含答案）第一章：基本概念与算法设计1.1 数据结构的定义与特点数据结构是指相互之间存在一种或多种特定关系的数据元素的集合，它包括了数据的存储、组织和管理方式。

数据结构的特点包括以下几个方面：- 数据元素之间存在某种关系，构成逻辑结构- 对数据元素的操作对应于对其逻辑结构的操作- 数据结构有存储结构，包括顺序存储结构和链式存储结构- 算法是对数据结构的操作步骤的描述和实现1.2 算法的基本概念算法是解决特定问题或完成特定任务的一系列操作步骤。

算法的基本概念包括以下几个方面：- 有穷性：算法必须能在有限步骤内完成- 确定性：算法的每一步骤必须有确定的含义和结果- 可行性：算法的每一步骤必须可行，能够通过执行有限次数实现- 输入：算法接受的输入数据是原始问题的实例- 输出：算法产生的输出数据与输入有明确的关系1.3 算法的描述方法算法可以用自然语言、伪代码或流程图来描述。

常用的伪代码描述方法包括结构化语言和算法描述语言，结构化语言包括顺序结构、分支结构和循环结构。

第二章：线性结构2.1 线性表的定义与基本操作线性表是n个数据元素的有限序列，其中相邻元素之间存在唯一的前驱和后继关系。

线性表的基本操作包括插入、删除、查找和修改等。

2.2 数组与广义表数组是指具有相同数据类型的一组数据元素的集合，可以通过下标访问元素。

广义表是线性表的推广，其中元素可以是基本数据类型或另一个广义表。

第三章：树与二叉树3.1 树的定义与基本术语树是n（n≥0）个结点的一个有限集合，其中满足以下条件：- 有且仅有一个特定的称为根的结点- 其余结点可分为m（m≥0）个互不相交的有限集合，每个集合本身又是一棵树3.2 二叉树的定义与性质二叉树是指每个结点最多有两个子结点的树结构。

二叉树的性质包括以下几个方面：- 深度为k的二叉树最多有2^k-1个结点- 一棵二叉树的第i层最多有2^(i-1)个结点- 在二叉树的第i层上至多有2^(n-i+1)-1个结点（n为树的深度）第四章：图4.1 图的基本概念与术语图是由顶点的有穷非空集合和边的有穷集合组成的。

数据结构c语言版试题及答案一、选择题（每题2分，共10分）1. 在C语言中，以下哪个关键字用于定义结构体？A. structB. unionC. enumD. typedef答案：A2. 若有一个结构体数组，下列哪个函数可以用来初始化数组中的每个元素？A. memsetB. memcpyC. strcpyD. bzero答案：A3. 在C语言中，以下哪个函数用于动态分配内存？A. mallocB. callocC. reallocD. all of the above答案：D4. 对于一个链表，以下哪个操作是正确的？A. 插入节点B. 删除节点C. 遍历链表D. all of the above答案：D5. 在C语言中，以下哪个函数用于释放动态分配的内存？A. freeB. mallocC. callocD. realloc答案：A二、填空题（每题3分，共15分）1. 结构体定义的关键字是______。

答案：struct2. 在C语言中，动态分配内存失败时，malloc函数返回______。

答案：NULL3. 单链表的头节点指针通常初始化为______。

答案：NULL4. 双向链表中，每个节点包含______个指针。

答案：两个5. 树的深度优先遍历包括______、中序遍历和后序遍历。

答案：前序遍历三、简答题（每题5分，共20分）1. 请简述C语言中结构体和联合体的区别。

答案：结构体（struct）可以包含不同类型的数据，并且可以有多个实例；联合体（union）可以包含不同类型的数据，但是只能有一个实例，即在任意时刻只能存储其中一个成员的值。

2. 动态内存分配的优点是什么？答案：动态内存分配允许程序在运行时根据需要分配内存，这样可以更有效地使用内存资源，并且可以创建大小不固定的数据结构。

3. 链表相比于数组有哪些优点？答案：链表的优点包括动态大小，可以灵活地插入和删除节点，不需要预先知道数据的大小。

数据结构c语言期末考试题库及详解答案数据结构C语言期末考试题库及详解答案一、选择题1. 在数据结构中，线性表的顺序存储结构被称为：A. 链式存储结构B. 栈C. 队列D. 数组答案：D2. 下列关于栈的描述，错误的是：A. 栈是一种特殊的线性表B. 栈的特点是后进先出C. 栈顶元素是最后插入的元素D. 栈的插入和删除操作都发生在栈顶答案：C二、填空题1. 在C语言中，定义一个具有10个元素的整型数组可以使用语句：________。

答案：int arr[10];2. 链表与数组相比，其优点是________。

答案：动态内存分配，不需要预先知道数据规模三、简答题1. 简述二叉树的遍历方法有哪些，并说明它们的特点。

答案：二叉树的遍历方法主要有前序遍历、中序遍历和后序遍历三种。

前序遍历首先访问根节点，然后递归地遍历左子树和右子树；中序遍历首先遍历左子树，然后访问根节点，最后遍历右子树；后序遍历首先遍历左子树和右子树，最后访问根节点。

每种遍历方法都可以用来对二叉树进行不同的操作和分析。

2. 什么是哈希表？它在实际应用中有哪些优点？答案：哈希表是一种通过哈希函数将键映射到表中一个位置来访问记录的数据结构。

它的优点包括：快速的数据访问速度，因为哈希表通常在常数时间内完成查找；动态的内存分配，可以根据需要调整存储空间；以及灵活的键值对存储方式。

四、编程题1. 编写一个C语言函数，实现单链表的逆序输出。

答案：```c#include <stdio.h>#include <stdlib.h>typedef struct Node {int data;struct Node *next;} Node;void reversePrint(Node *head) {if (head == NULL) return;reversePrint(head->next);printf("%d ", head->data);}int main() {Node *head = (Node *)malloc(sizeof(Node));head->data = 1;head->next = NULL;// 假设链表已经构建完毕reversePrint(head);return 0;}```2. 请实现一个C语言函数，用于计算一个字符串中不同字符的数量。

《数据结构与算法》复习题一、选择题。

20. 如果最常用的操作是取第i个结点及英前驱，则采用D存储方式最节省时间。

A. 单链表B.双链表C.单循环链表D.顺序表21. 在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是B_o)A. O (1)B. O (n)C. O (n2)D. O (nlog2n)27. 下述哪一条是顺序存储结构的优点CA插入运算方便B可方便地用于各种逻辑结构的存储表示C存储密度大D删除运算方便35.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是s->next=p->next : p->next=s;}41.以下 B 不是队列的基本运算A.从队尾插入一个新元素B.从队列中删除第i个元素C.判断一个队列是否为空D.读取队头元素的值47.在循环队列中，若front与rear分别表示对头元素和队尾元素的位置，则判断循环队列空的条件是_ .A. front==rear+lB. rear==front+lC. front==rearD. front==04.向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时,应执行s->next=h->next ;h->next=s50.若栈采用顺序存储方式存储，现两栈共享空间V[1 m], top[l]、top[2]分别代表第1和第2个栈的栈顶，栈1的底在V[l],栈2的底在V[m],则栈满的条件是____________________ oA. |top[2]-top[l]|=0B. top[l]+l=top[2]C. top[l]+top[2]=mD. top[l]=top[2]52.允许对队列进行的操作有—。

A.对队列中的元素排序B.取岀最近进队的元素C.在队头元素之前插入元素D.删除队头元素54.若用一个大小为6的数值来实现循环队列，且当前rear和front的值分别为0和3,当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为 B °A. 1 和5B. 2 和4C. 4 和2D. 5 和 156. 和顺序栈相比，链栈有一个比较明显的优势是通常不会出现栈满的情况57. 用不带头结点的单链表存储队列，其头指针指向队头结点，尾指针指向队尾结点，则在进行出队操作时C o C.队头、队尾指针都可能要修改64.若声明一个浮点数数组如卜一：froat average[]=new float[30];假设该数组的内存起始位置为200, average[15]的内存地址是C 。

数据结构c语言期末考试试题及答案一、选择题（每题2分，共20分）1. 在C语言中，以下哪个关键字用于定义结构体？A. structB. unionC. enumD. typedef答案：A2. 在C语言中，以下哪个函数用于创建链表节点？A. mallocB. callocC. reallocD. free答案：A3. 如果一个链表的头指针为NULL，这意味着什么？A. 链表为空A. 链表已满C. 链表正在使用中D. 链表已损坏答案：A4. 在C语言中，以下哪个数据结构允许快速随机访问？A. 链表B. 数组C. 栈D. 队列5. 在二叉树中，以下哪个术语描述了没有子节点的节点？A. 根节点B. 叶节点C. 内部节点D. 父节点答案：B6. 以下哪个算法用于在二叉搜索树中查找一个元素？A. 深度优先搜索B. 广度优先搜索C. 插入排序D. 二分查找答案：D7. 在C语言中，以下哪个关键字用于定义一个函数？A. intB. voidC. returnD. struct答案：A8. 以下哪个选项是正确的递归函数定义？A. int fact(int n) { if (n > 1) return n * fact(n-1); else return 1; }B. int fact(int n) { if (n > 1) return n * fact(n); else return 1; }C. int fact(int n) { if (n > 1) return n * fact(n+1); else return 1; }D. int fact(int n) { if (n > 1) return n; else return 1; }9. 在C语言中，以下哪个函数用于释放动态分配的内存？A. mallocB. callocC. reallocD. free答案：D10. 在C语言中，以下哪个关键字用于定义一个指针？A. intB. charC. *D. &答案：C二、填空题（每题2分，共20分）1. 在C语言中，结构体的成员可以通过其结构体变量名和______访问。

《数据结构与算法》复习题一、选择题。

1．在数据结构中，从逻辑上可以把数据结构分为 C 。

A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．内部结构和外部结构2．数据结构在计算机内存中的表示是指 A 。

A．数据的存储结构 B．数据结构 C．数据的逻辑结构 D．数据元素之间的关系3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。

A．逻辑 B．存储 C．逻辑和存储 D．物理4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。

A．数据的处理方法 B．数据元素的类型C．数据元素之间的关系 D．数据的存储方法5．在决定选取何种存储结构时，一般不考虑 A 。

A．各结点的值如何 B．结点个数的多少C．对数据有哪些运算 D．所用的编程语言实现这种结构是否方便。

6．以下说法正确的是 D 。

A．数据项是数据的基本单位B．数据元素是数据的最小单位C．数据结构是带结构的数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。

（1）A．找出数据结构的合理性 B．研究算法中的输入和输出的关系C．分析算法的效率以求改进 C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度 B．正确性和简明性C．可读性和文档性 D．数据复杂性和程序复杂性8．下面程序段的时间复杂度是 O(n2) 。

s =0;for( I =0; i<n; i++)for(j=0;j<n;j++)s +=B[i][j];sum = s ;9．下面程序段的时间复杂度是 O(n*m) 。

for( i =0; i<n; i++)for(j=0;j<m;j++)A[i][j] ＝ 0;10．下面程序段的时间复杂度是 O(logn) 。

3i ＝ 0；while（i<=n）i = i * 3；11．在以下的叙述中，正确的是 B 。

《数据结构与算法》复习题一、选择题。

1．在数据结构中，从逻辑上可以把数据结构分为 C 。

A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构2．数据结构在计算机内存中的表示是指 A 。

A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。

A．逻辑B．存储C．逻辑和存储D．物理4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。

A．数据的处理方法B．数据元素的类型C．数据元素之间的关系D．数据的存储方法5．在决定选取何种存储结构时，一般不考虑 A 。

A．各结点的值如何B．结点个数的多少C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。

6．以下说法正确的是 D 。

A．数据项是数据的基本单位B．数据元素是数据的最小单位C．数据结构是带结构的数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。

（1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度B．正确性和简明性C．可读性和文档性D．数据复杂性和程序复杂性8．下面程序段的时间复杂度是O(n2) 。

s =0;for( I =0; i<n; i++)for(j=0;j<n;j++)s +=B[i][j];sum = s ;9．下面程序段的时间复杂度是O(n*m) 。

for( i =0; i<n; i++)for(j=0;j<m;j++)A[i][j] ＝0;10．下面程序段的时间复杂度是O(log3n) 。

i ＝0；while（i<=n）i = i * 3；11．在以下的叙述中，正确的是 B 。

A．线性表的顺序存储结构优于链表存储结构B．二维数组是其数据元素为线性表的线性表C．栈的操作方式是先进先出D．队列的操作方式是先进后出12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 B 。

《数据结构与算法》复习题一、选择题。

1．在数据结构中，从逻辑上可以把数据结构分为 C 。

A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．内部结构和外部结构2．数据结构在计算机内存中的表示是指 A 。

A．数据的存储结构 B．数据结构 C．数据的逻辑结构 D．数据元素之间的关系3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。

A．逻辑 B．存储 C．逻辑和存储 D．物理4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。

A．数据的处理方法 B．数据元素的类型C．数据元素之间的关系 D．数据的存储方法5．在决定选取何种存储结构时，一般不考虑 A 。

A．各结点的值如何 B．结点个数的多少C．对数据有哪些运算 D．所用的编程语言实现这种结构是否方便。

6．以下说法正确的是 D 。

A．数据项是数据的基本单位B．数据元素是数据的最小单位C．数据结构是带结构的数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。

（1）A．找出数据结构的合理性 B．研究算法中的输入和输出的关系C．分析算法的效率以求改进 C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度 B．正确性和简明性C．可读性和文档性 D．数据复杂性和程序复杂性8．下面程序段的时间复杂度是 O(n2) 。

s =0;for( I =0; i<n; i++)for(j=0;j<n;j++)s +=B[i][j];sum = s ;9．下面程序段的时间复杂度是 O(n*m) 。

for( i =0; i<n; i++)for(j=0;j<m;j++)A[i][j] ＝ 0;10．下面程序段的时间复杂度是 O(log3n) 。

i ＝ 0；while（i<=n）i = i * 3；11．在以下的叙述中，正确的是 B 。

《数据结构与算法》复习题一、选择题。

1．在数据结构中，从逻辑上可以把数据结构分为 C 。

A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．内部结构和外部结构2．数据结构在计算机内存中的表示是指 A 。

A．数据的存储结构 B．数据结构 C．数据的逻辑结构 D．数据元素之间的关系3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。

A．逻辑 B．存储 C．逻辑和存储 D．物理4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。

A．数据的处理方法 B．数据元素的类型C．数据元素之间的关系 D．数据的存储方法5．在决定选取何种存储结构时，一般不考虑 A 。

A．各结点的值如何 B．结点个数的多少C．对数据有哪些运算 D．所用的编程语言实现这种结构是否方便。

6．以下说法正确的是 D 。

A．数据项是数据的基本单位B．数据元素是数据的最小单位C．数据结构是带结构的数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。

（1）A．找出数据结构的合理性 B．研究算法中的输入和输出的关系C．分析算法的效率以求改进 C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度 B．正确性和简明性C．可读性和文档性 D．数据复杂性和程序复杂性8．下面程序段的时间复杂度是 O(n2) 。

s =0;for( I =0; i<n; i++)for(j=0;j<n;j++)s +=B[i][j];sum = s ;9．下面程序段的时间复杂度是 O(n*m) 。

for( i =0; i<n; i++)for(j=0;j<m;j++)A[i][j] ＝ 0;10．下面程序段的时间复杂度是 O(log3n) 。

i ＝ 0；while（i<=n）i = i * 3；11．在以下的叙述中，正确的是 B 。

《数据结构与算法》复习题一、选择题。

1．在数据结构中，从逻辑上可以把数据结构分为 C 。

A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．内部结构和外部结构2．数据结构在计算机内存中的表示是指 A 。

A．数据的存储结构 B．数据结构 C．数据的逻辑结构 D．数据元素之间的关系3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。

A．逻辑 B．存储 C．逻辑和存储 D．物理4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。

A．数据的处理方法 B．数据元素的类型C．数据元素之间的关系 D．数据的存储方法5．在决定选取何种存储结构时，一般不考虑 A 。

A．各结点的值如何 B．结点个数的多少C．对数据有哪些运算 D．所用的编程语言实现这种结构是否方便。

6．以下说法正确的是 D 。

A．数据项是数据的基本单位B．数据元素是数据的最小单位C．数据结构是带结构的数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。

（1）A．找出数据结构的合理性 B．研究算法中的输入和输出的关系C．分析算法的效率以求改进 C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度 B．正确性和简明性C．可读性和文档性 D．数据复杂性和程序复杂性8．下面程序段的时间复杂度是 O(n2) 。

s =0;for( I =0; i<n; i++)for(j=0;j<n;j++)s +=B[i][j];sum = s ;9．下面程序段的时间复杂度是 O(n*m) 。

for( i =0; i<n; i++)for(j=0;j<m;j++)A[i][j] ＝ 0;10．下面程序段的时间复杂度是 O(logn) 。

3i ＝ 0；while（i<=n）i = i * 3；11．在以下的叙述中，正确的是 B 。

数据结构C语言版期末考试试题（有答案）2017-1-1218.14.59抢时间，抓基础，勤演练定有收获；树自信，誓拼搏，升大学回报父母。

"数据结构"期末考试试题一、单选题(每小题2分共12分)1．在一个单链表HL中若要向表头插入一个由指针p指向的结点则执行( )A． HL＝ps p一>next＝HLB． p一>next＝HL；HL＝p3C． p一>next＝Hl；p＝HL；D． p一>next＝HL一>next;HL一>next＝p；2．n个顶点的强连通图中至少含有( )A.n-l条有向边B.n条有向边C.n(n-1)／2条有向边D.n(n一1)条有向边3.从一棵二叉搜索树中查找一个元素时其时间复杂度大致为( )A.O(1)B.O(n)C.O(1Ogzn)D.O(n2)4．由权值分别为38625的叶子结点生成一棵哈夫曼树它的带权路径长度为( )A．24 B．48C． 72 D． 535．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时应最好把它说明为( )参数以节省参数值的传输时间和存储参数的空间A.整形B.引用型C.指针型D.常值引用型·6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )A．O(n) B．O(1)C．O(n2) D．O(10g2n)二、填空题(每空1分共28分)1．数据的存储结构被分为--、--、--和--四种2．在广义表的存储结构中单元素结点与表元素结点有一个域对应不同各自分别为--域和--域3．--中缀表达式 3十x*(2.4／5-6)所对应的后缀表达式为----4．在一棵高度为h的3叉树中最多含有--结点5．假定一棵二叉树的结点数为18则它的最小深度为--最大深度为--·6．在一棵二叉搜索树中每个分支结点的左子树上所有结点的值一定--该结点的值右子树上所有结点的值一定--该结点的值7．当向一个小根堆插入一个具有最小值的元素时该元素需要逐层--调整直到被调整到--位置为止8．表示图的三种存储结构为--、--和---9．对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时其时间复杂度为--对用邻接表表示的图进行任一种遍历时其时间复杂度为--10．从有序表(1218304356788295)中依次二分查找43和56元素时其查找长度分别为--和--·11．假定对长度n＝144的线性表进行索引顺序查找并假定每个子表的长度均为则进行索引顺序查找的平均查找长度为--时间复杂度为--·12．一棵B-树中的所有叶子结点均处在--上13．每次从无序表中顺序取出一个元素把这插入到有序表中的适当位置此种排序方法叫做--排序；每次从无序表中挑选出一个最小或最大元素把它交换到有序表的一端此种排序方法叫做--排序14．快速排序在乎均情况下的时间复杂度为--最坏情况下的时间复杂度为--三、运算题(每小题6分共24分)1．假定一棵二叉树广义表表示为a(b(cd)c(((8)))分别写出对它进行先序、中序、后序和后序遍历的结果先序：中序；后序：2．已知一个带权图的顶点集V和边集G分别为：V＝{012345}；E={(01)8(02)5(03)2(15)6(23)25(24)13(35)9(45)10}则求出该图的最小生成树的权最小生成树的权；3．假定一组记录的排序码为(4679563840845042)则利用堆排序方法建立的初始堆为--4．有7个带权结点其权值分别为378261014试以它们为叶子结点生成一棵哈夫曼树求出该树的带权路径长度、高度、双分支结点数带权路径长度：-- 高度：-- 双分支结点数：--四、阅读算法回答问题(每小题8分共16分)1．VOldAC(List&L){InitList(L)；InsertRear(L;25)；InsertFront(L50)；IntaL4]＝{58121536};for(inti＝0; i<5; i++)if (a[i]％2＝＝0)InsertFront(L a[i])；elselnsertRear(La[i])；}该算法被调用执行后得到的线性表L为：2．void AG(Queue&Q){InitQueue(Q)；inta[5]＝{6125158}；for(int i＝0;i<5; i++)QInsert(Q a[i])；QInsert(QQDelete(Q))；QInsert(Q20)；QInsert(QQDelete(Q)十16)；while(!QueueEmpty(Q))cout<<qdelete(q)<<"；< p="">}该算法被调用后得到的输出结果为：五、算法填空在画有横线的地方填写合适的内容(每小题6分共12分)1．从一维数组A[n)中二分查找关键字为K的元素的递归算法若查找成功则返回对应元素的下标否则返回一1IntBinsch(ElemTypeA[]Intlowint highKeyTypeK){if(low<＝high){int mid＝(low+high)／2；if(K＝＝A[mid].key)--；else if (K<a[mid].key)--；< p="">else ；}else return-l；}2．已知二叉树中的结点类型BinTreeNode定义为：structBinTreeNode{ElemType data；BinTreeNode*left*right}；其中data为结点值域left和right分别为指向左、右子女结点的指针域下面函数的功能是返回二叉树BT中值为x的结点所在的层号请在划有横线的地方填写合适内容Int NodeLevel(BinTreeNode * BTElemType X){if(BT：＝NULL)return 0；／／空树的层号为0else if(BT一>data＝＝X)return 1; ／／根结点的层号为1 ／／向子树中查找x结点else{int cl＝NodeLevel(BT一>leftX)；if(cl>＝1)return cl+1;int c2＝；if--；／／若树中不存在X结点则返回oelse return 0；}}六、编写算法(8分)按所给函数声明编写一个算法从表头指针为HL的单链表中查找出具有最大值的结点该最大值由函数返回若单链表为空则中止运行EIemType MaxValue(LNOde*HL);"数据结构"期末考试试题答案一、单选题(每小题2分共12分)评分标准；选对者得2分否则不得分1．B 2．B 3．C 4．D 5．B 6．A二、填空题(每空1分共28分)1．顺序结构链接结构索引结构散列结构(次序无先后) 2．值(或data) 子表指针(或sublist)3．3 x 2．4 5／6一*十4．(3h一1)／25． 5 186．小于大于(或大于等于)7．向上堆顶8．邻接矩阵邻接表边集数组(次序无先后) 9．O(n2) O(e)10． 1 311．13 O()12．同一层13．插人选择14．O(nlog2n) O(n2)三、运算题(每小题6分共24分)1．先序：abcdefe ／／2分中序：cbdaf8e ／／2分后序：cdbefea ／／2分2．最小生成树的权：31 ／／6分3．(8479564240465038) ／／6分4．带权路径长度：131 ／／3分高度：5 ／／2分双分支结点数：6 ／／1分四、阅读算法回答问题(每小题8分共16分)评分标准：每小题正确得8分出现一处错误扣4分两处及以上错误不得分1．(361285025515)2．5 15 8 6 20 28五、算法填空在画有横线的地方填写合适的内容(每小题6分共12分) 1．feturn mid ／／2分returnBinsch(Alowmid一1K) ／／2分returnBmsch(Amid+1highK) ／／2分2．NodeLevel(BT一>rightX) ／／3分(c2>=1)returnc2十1 ／／3分六、编写算法(8分)评分标准：请参考语句后的注释或根据情况酌情给分ElemType MaxValue(LNodeO* HL){if (HL＝=NUlL){ ／／2分cerr<<"Linked llst is empty!"<<="" p="">}ElemTypemax：HL一>data；／／3分LNOde*p=HI一>next；／／4分while(P!：NULL){ ／／7分if(maxdata)max＝p一>data；p＝p一>next；}returnmax；／／8分}数据结构复习资料一、填空题1. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科2. 数据结构被形式地定义为（DR）其中D是数据元素的有限集合R是D上的关系有限集合3. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容4. 数据结构按逻辑结构可分为两大类它们分别是线性结构和非线性结构5. 线性结构中元素之间存在一对一关系树形结构中元素之间存在一对多关系图形结构中元素之间存在多对多关系6．在线性结构中第一个结点没有前驱结点其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点其余每个结点有且只有1个后续结点7. 在树形结构中树根结点没有前驱结点其余每个结点有且只有 1 个前驱结点；叶子结点没有后续结点其余每个结点的后续结点数可以任意多个8. 在图形结构中每个结点的前驱结点数和后续结点数可以任意多个9．数据的存储结构可用四种基本的存储方法表示它们分别是顺序、链式、索引和散列10. 数据的运算最常用的有5种它们分别是插入、删除、修改、查找、排序11. 一个算法的效率可分为时间效率和空间效率12. 在顺序表中插入或删除一个元素需要平均移动表中一半元素具体移动的元素个数与表长和该元素在表中的位置有关13. 线性表中结点的集合是有限的结点间的关系是一对一的14. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时需向后移动 n-i+1 个元素15. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时需向前移动 n-i 个元素16. 在顺序表中访问任意一结点的时间复杂度均为 O(1)因此顺序表也称为随机存取的数据结构17. 顺序表中逻辑上相邻的元素的物理位置必定相邻单链表中逻辑上相邻的元素的物理位置不一定相邻18．在单链表中除了首元结点外任一结点的存储位置由其直接前驱结点的链域的值指示19．在n个结点的单链表中要删除已知结点*p需找到它的前驱结点的地址其时间复杂度为O（n）20. 向量、栈和队列都是线性结构可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素21. 栈是一种特殊的线性表允许插入和删除运算的一端称为栈顶不允许插入和删除运算的一端称为栈底</a[mid].key)--；<></qdelete(q)<<"；<>。