下载文档原格式
数据结构c语言期末考试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，线性结构和非线性结构的区别在于（）。
A. 结构中元素的个数B. 结构中是否包含子结构C. 结构中元素之间是否有一对一关系D. 结构中元素之间是否有一对多关系答案：C2. 线性表的顺序存储结构和链式存储结构相比，其优点是（）。
A. 存储密度高B. 存储密度低C. 插入和删除操作快D. 存储空间可以动态分配答案：A3. 在一个长度为n的顺序表中，删除第i个元素（1≤i≤n）时，需要移动的元素个数为（）。
A. i-1B. n-iC. n-i+1D. n-i-1答案：B4. 栈的运算遵循（）原则。
A. 先进先出B. 先进后出C. 后进先出D. 后进后出答案：C5. 在二叉树的前序遍历中，访问顺序为（）。
A. 根-左-右B. 左-根-右C. 左-右-根D. 右-左-根答案：A6. 哈希表的冲突解决方法中，链地址法是（）。
A. 将所有元素存储在同一个存储单元B. 将所有元素存储在同一个链表中C. 将所有元素存储在同一个数组中D. 将所有元素存储在同一个链表的同一个位置答案：B7. 在图的遍历中，深度优先搜索（DFS）和广度优先搜索（BFS）的主要区别在于（）。
A. 遍历的顺序不同B. 遍历的起点不同C. 遍历的路径不同D. 遍历使用的存储结构不同答案：D8. 快速排序算法的时间复杂度为（）。
A. O(n)B. O(nlogn)C. O(n^2)D. O(logn)答案：B9. 归并排序算法的时间复杂度为（）。
A. O(n)B. O(nlogn)C. O(n^2)D. O(logn)答案：B10. 在二叉搜索树中，查找一个元素的时间复杂度为（）。
A. O(n)B. O(logn)C. O(n^2)D. O(1)答案：B二、填空题（每题2分，共20分）1. 在数据结构中，一个算法的时间复杂度通常用______来描述。
答案：大O符号2. 线性表的两种基本操作是插入和______。
序号项目名称任务描述设计要求每组学生人数1．订票系统任务：通过此系统可以实现如下功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：确定航班是否满仓）；可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，可以输入起飞抵达城市，查询飞机航班情况；订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；退票：可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。
修改航班信息：当航班信息改变可以修改航班数据文件根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；2．用Haffman编码压缩文件准备一个文件，统计该文件中各种字符的频率，对各字符进行Huffman编码，将该文件翻译成Huffman编码文件，再将Huffman编码文件翻译成源文件。
3．统计C程序中关键字的频率扫描一个C源程序，用Hash表存储该程序中出现的关键字，并统计该程序中的关键字出现频度。
用线性探测法解决Hash冲突。
设Hash函数为：Hash(key)=[(key的第一个字母序号)*100+(key的最后一个字母序号)] MOD 374．商品管理系统以链表结构的有序表表示某商场家电部的库存模型，当有提货或进货时需要对该链表及时进行维护，每个工作日结束以后，将该链表中的数据以文件形式保存，每日开始营业之前，须将文件形式保存的数据恢复成链表结构的有序表。
链表结构的数据域包括家电名称、品牌、单价和数量，以单价的升序体现链表的有序性。
程序功能包括：初始化、创建表、插入、删除、更新数据、查询及链表数据与文件之间的转换等。
5．排序算法效率比较编程实现插入、希尔、快速、堆排序、归并排序算法，并计算每种算法的比较、交换次数。
将待排数据从磁盘文件读入，实施排序后将数据写入另一个文件中。
《数据结构-C语言版》第一章绪论单项选择题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. 事后分析估算的方法6．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是____ __。
A. n2B. nlognC. nD. logn7．设使用某算法对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为____ ___。
A. O(1)B. O(n)C. O(200n)D. O(nlog2n)CDCBBDD第二章线性表单项选择题1．链表不具有的特点是____ ____。
A. 可随机访问任一元素B. 插入和删除时不需要移动元素C. 不必事先估计存储空间D. 所需空间与线性表的长度正比2．设顺序表的每个元素占8个存储单元。
第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为。
A. 139B. 140C. 147D. 1483．在线性链表存储结构下，插入操作算法。
A. 需要判断是否表满B. 需要判断是否表空C. 不需要判断表满D. 需要判断是否表空和表满4．在一个单链表中，若删除p所指结点的后继结点，则执行。
A. p->next = p->next->next;B. p->next = p->next;C. p = p->next->next;D. p = p->next; p->next = p->next->next;5．将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为。
![数据结构（C语言版）1800道题及答案[完整版]](https://img.taocdn.com/s1/m/9bcf54fe59f5f61fb7360b4c2e3f5727a5e9240e.png)
数据结构（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语言程序设计答案一.是非题（2’⨯10）（⨯）1、队列逻辑上是一个表头和表尾既能插入又能删除的线性表。
（√）2、任何一个递归过程都可以转换成非递归过程。
（⨯）3、与n个键值的集合{k1,k2,…,kn}相对应的堆是唯一的。
（⨯）4、在索引顺序表上实现分块查找，在等概率查找情况下，其查找长度只与表中元素个数有关，而与每块中元素个数无关。
（⨯）5、所谓加权无向图G的最小生成树T就是将G中各结点间的最短路径作为边所构造出来的G的子图。
（⨯）6、在10万个随机排列的数据中，要选出5个最小的数，采用快速排序比采用Shell排序、堆排序及各种直接排序法都快。
（⨯）7、B树查找算法的时间复杂性为O（n）。
（⨯）8、哈希表查找无需进行关键字的比较。
（⨯）9、在执行某个排序过程中，出现排序码朝着最终位置相反方向移动，则该算法是不稳定的。
（⨯）10、任何有向图的顶点都可以按拓扑序排序。
二.填空题（2’⨯6）1．假设用于通信的电文由8个字母组成，其频率分别为0.07，0.19,0.02,0.06, 0.32,0.03,0.21,0.10, 为这8个字母设计哈夫曼编码，其中编码长度最大的字母的编码是 5 位。
2．已知二叉树按中序遍历所得到的结点序列为DCBGEAHFIJK，按后序遍历所得到的结点序列为DCEGBFHKJIA，按先序遍历所得到的结点序列为ABCDGEIHFJK 。
3. 设哈希表长度为11，哈希函数 H(k)=k MOD 11, 若输入顺序为（18,10,21,9,6,3,16,25,7）,处理冲突方法为线性探测再散列，请构造哈希表。
0 1 2 3 4 5 6 7 8 9 1021 3 25 16 6 18 7 9 10440，第一个记录为枢轴)第一趟排序结果7,4,2,5,16,18,20,29,33,40,34 。
5．已知模式匹配的KMP算法中模式串t=’a dabbadada’，其next函数的值为 0112112343 。
数据结构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. 链表相比于数组有哪些优点？答案：链表的优点包括动态大小，可以灵活地插入和删除节点，不需要预先知道数据的大小。
一、单项选择题1．有下列程序段落:int i,a[5]；for(i=0;i<5;i++)scanf(“%d”,&a[i]);若要使数组元素的值分别为1，2，3，4，5，应从键盘输入（B）。
Ａ．1,2,3,4,5↙Ｂ．1 2 3 4 5↙Ｃ．12345↙Ｄ．1;2;3;4;5↙2．数组名作为函数参数进行传递时，形参获得的是（D）。
A．该数组第一个元素的值B．该数组所有元素的值C．该数组所有元素的地址D．该数组的首地址3.设有如下宏定义:#define A 3+2#define B A*A则表达式“B*B”的值为（ A ）。
Ａ．23Ｂ．5 Ｃ．25Ｄ．6254．在下列说明中，结构类型变量x 所占用内存字节数为（D）。
struct exp{ int i;float j;double k;}x;Ａ．8个Ｂ．7个Ｃ．14个Ｄ．随计算机而定5．设有定义：int k=3,*p=&k; 则表达式*p的值是（D）。
Ａ．1 Ｂ．0 Ｃ．2 Ｄ．36．下列程序的输出结果为（A）。
main（）{ int i=3，b；b=(i--)+(i--)；printf（“%d”，b）；}Ａ．6 Ｂ．2 Ｃ．3 Ｄ．47．当c的值不为0时，在下列选项中能正确将c的值赋给变量a、b的是（D）。
Ａ．c=b=a Ｂ. (a=c)||(b=c) Ｃ. a=c=b Ｄ. (a=c)&&(b=c)8．下列叙述不正确的是（ A ）。
Ａ．函数定义可以嵌套Ｂ．宏定义可以嵌套Ｃ．函数调用可以嵌套Ｄ．循环结构可以嵌套9．设char *p=“abcde”，则printf(“%s”, p ) 的输出结果为（ D ）。
Ａ．c Ｂ．cde Ｃ．b Ｄ．abcde10．p1,p2 为指向浮点的指针变量，下列运算没有意义的是（D）。
Ａ．*p1－*p2 Ｂ．p1++ Ｃ．*p1+*p2 Ｄ．p1+p211．设有int i=010,j=10; 则printf( “%d,%d\n”,++i,j--);的输出是（B）。
《c语言程序设计》试题库及答案一、选择题1. 下列哪个选项是C语言的标准库函数？A. printfB. scanfC. mainD. All of the above答案：D2. C语言中，用于定义字符串的字符数组的语法是什么？A. char str[] = "Hello";B. char str[] = {"Hello"};C. char str = "Hello";D. char str[] = 'Hello';答案：A3. 在C语言中，以下哪个关键字用于定义一个函数？A. intB. functionC. defD. void答案：A二、填空题1. 在C语言中，定义一个整型变量的正确方式是：________。
答案：int variable_name;2. C语言中，用于计算两个数的和的运算符是：______。
答案：+3. 如果要在C语言中声明一个指向整型的指针，应该使用：________。
答案：int *pointer_name;三、简答题1. 请简述C语言中数组和指针的区别。
答案：数组是一组相同类型的元素的集合，可以通过索引访问每个元素。
指针是一个变量，它存储了另一个变量的内存地址。
数组名可以被用作指向数组首元素的指针，但数组本身是一个固定大小的实体，而指针可以被重新赋值为其他地址。
2. 解释C语言中的结构体（struct）是什么？答案：结构体是一种用户定义的数据类型，它允许将不同的数据类型组合成一个单一的数据结构。
它使得可以创建包含多种数据类型的复杂数据结构。
四、编程题1. 编写一个C语言程序，实现计算两个整数的和，并输出结果。
```c#include <stdio.h>int main() {int num1, num2, sum;printf("Enter two integers: ");scanf("%d %d", &num1, &num2);sum = num1 + num2;printf("The sum is: %d\n", sum);return 0;}```2. 编写一个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（log3n） .i ＝0;while(i〈=n）i = i ＊3；11．在以下的叙述中，正确的是 B 。
A．线性表的顺序存储结构优于链表存储结构B．二维数组是其数据元素为线性表的线性表C．栈的操作方式是先进先出D．队列的操作方式是先进后出12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 B .A．数据元素具有同一特点B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等13．链表不具备的特点是 A 。
《数据结构》Part1一．选择1. 组成数据的基本单位是（）A）数据项 B）数据类型 C）数据元素 D）数据变量2．算法分析的目的是（）A）找出数据结构的合理性 B）研究算法的输入/输出关系C）分析算法的效率以求改进 D）分析算法的易读性3．在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（） A）O(1) B）0(n) C）O(n^2) D）O(nlog2n)4．若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为100，则第12个元素的存储地址是（）A）112 B）144 C）148 D）4125．下面关于线性表的叙述中，错误的是（）A）顺序表使用一维数组实现的线性表 B）顺序表必须占用一片连续的存储单元.C）顺序表的空间利用率高于链表 D）在单链表中,每个结点只有一个链域. 6．在需要经常查找结点的前驱与后继的情况下，使用（）比较合适A）单链表 B）双链表 C）顺序表 D）循环链表7．队列通常采用的两种存储结构是（）A）顺序存储结构和链式存储结构 B）散列方式和索引方式C）链表存储结构和线性存储结构 D）线性存储结构和非线性存储结构8．在一个单链表中，若删除p所指结点的后继结点，则执行（）A）p->next=p->next->next；B）p=p->next；p->nex=p->next->next；C）p->next=p->next； D）p=p->next->next；9．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间A）单链表 B）仅有头指针的单循环链表 C）双链表 D）仅有尾指针的单循环链表10．按二叉树的定义，具有三个结点的二元树共有（）种形态。
A）3 B）4 C）5 D）611．任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）A）发生改变 B）不发生改变 C）不能确定 D）以上都不对12．深度为5的二叉树至多有（）个结点A）16 B）32 C）31 D）1013．在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，那么度为0的结点数为（）个。
A）4 B）5 C）6 D）714．对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组(顶点表)的大小为（）A）n B）n+1 C）n-1 D）n/215．静态查找表和动态查找表二者的根本差别在于（）A）它们的逻辑结构不同 B）施加在其上的操作不同C）所包含的数据元素的类型不一样 D）存储实现不一样二．填空1．某程序的时间复杂性为(3n+nlog2n+n2+8),其数量级表示为________。
2．线性表L=(a1,a2,…,an)采用顺序结构存储,假定在不同的位置上插入的概率相同，则插入一个新元素平均需要移动的元素个数是_________ 。
3. 对于一株具有n个结点的树，该树中所有结点的度数之和为______。
4. 在一个图中,所有顶点的度数之和等于所有边数的______________倍。
5. 一棵二叉树有67个结点,这些结点的度要么是0，要么是2。
这棵二元树中度数为2的结点有______________个。
6．在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是_____。
7．采用堆排序、快速排序、冒泡排序，对初态有序的表，最省时间的是______ 。
8．设二叉树结点的先根序列为ABDECFGH，中根序列为DEBAFCHG,则二元树中叶结点是_________.9．一个哈夫曼(Huffman)树有19个结点，则其叶结点的个数是______。
10.栈S和队列Q的初始状态皆为空,元素a1,a2,a3,a4,a5和a6依次通过S栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3,a5,a4,a6,a2,a1，则栈S至少应该容纳_______ 个元素。
三．判断1．线性表的链式存储结构优于顺序行储结构。
（）2．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。
（）3．对于n个记录的集合进行归并排序，存最坏的情况下所需要的时间是O(n^2)。
（）4．表中的每一个元素都有一个前驱和后继元素。
（）5．进栈操作push(x，s)作用于链接栈时，无须判满。
（）6．只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。
（）7．在索引顺序表查找方法中，对索引顺序表可以使用顺序表查找方法，也可以使用二分查找方法。
（）8．数据元素是数据的最小单位。
（）9．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
（）10．按中序遍历一棵二叉排序树所得到的中序遍历序列是一个递增序列。
（）四．简答1. 对于下图所示的树：(1) 写出先序遍历得到的结点序列；(2) 画出转换后得到的二叉树。
2．请画出与下列二元树对应的森林。
五．算法设计1．已知一个int类型的数组arra，其长度为n，要求用冒泡排序算法对其从小到大排序，请实现该算法，（要求后面开始循环，大的数值下沉）。
2．利用一个栈实现以下递归函数的非递归计算：P n (x)=⎪⎩⎪⎨⎧>==----11)()1(2)(22121nnnxPnxxPxnnPart2一、单项选择1、在数据结构的讨论中把数据结构从逻辑上分为（）A）内部结构与外部结构 B）静态结构与动态结构C）线性结构与非线性结构 D）紧凑结构与非紧凑结构。
2、算法分析的目的是（）A）找出数据结构的合理性 B）研究算法中输入和输出的关系C）分析算法的效率以求改进 D）分析算法的易懂性和文档性3、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（）A）s→link = p→link; p→link = s; B）p→link = s; s→link = q;C）p→link = s→link; s→link = p; D）q→link = s; s→link = p;4、如果想在4092个数据中只需要选择其中最小的5个，采用（）方法最好。
A）起泡排序 B）堆排序C）锦标赛排序 D）快速排序5、设有两个串t和p，求p在t中首次出现的位置的运算叫做（）。
A）求子串B）模式匹配 C）串替换 D）串连接6、将一个递归算法改为对应的非递归算法时，通常需要使用（）。
A）栈B）队列C）循环队列D）优先队列7、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（）。
A）( front - rear + 1) % m B）( rear - front + 1) % mC）( front - rear + m) % m D）( rear - front + m) % m8、下面程序段的时间复杂度为（）for (int i=0;i<m;i++)for (int j=0;j<n;j++)a[i][j]=i*j;A）O(m2) B）O(n2) C）O(m*n) D）O(m+n)9、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行( )。
A）s->link=p;p->link=s; B）s->link=p->link;p->link=s;C）s->link=p->link;p=s; D）p->link=s;s->link=p;10、当利用大小为n 的数组顺序存储一个队列时，该队列的最大长度为（）A）n-2 B）n-1 C）n D）n+111、某二叉树的前序和后序序列正好相反，则该二叉树一定是（）的二叉树。
A）空或只有一个结点B）高度等于其结点数C）任一结点无左孩子 D）任一结点无右孩子12、对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点为n2，则( )A）n0= n2+1 B）n2= n0+1 C）n0= 2n2+1 D）n2=2n0+113、由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A）24 B）73 C）48 D）5314、对线性表进行折半搜索时，要求线性表必须（）A）以链接方式存储且结点按关键码有序排列 B）以数组方式存储C）以数组方式存储且结点按关键码有序排列 D）以链接方式存储15、顺序搜索算法适合于存储结构为（）的线性表。
A）散列存储 B）顺序存储或链接存储C）压缩存储 D）索引存储二、填空1、数据的存储结构被分为、、、四种。
2、一种抽象数据类型包括和两个部分。
3、栈、队列逻辑上都是结构。
4、栈中存取数据的原则，队列中存取数据的原则。
5、设目标串T=”abccdcdccbaa”,模式P=”cdcc”则第次匹配成功。
三、判断1、数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。
( )2、线性表的逻辑顺序与物理顺序总是一致的。
（）3、每种数据结构都应具备三种基本运算：插入、删除、搜索。
（）4、深度为h的非空二叉树的第h层最多有2h-1个结点。
（）5、完全二叉树就是满二叉树。
（）6、最优二叉搜索树一定是平衡的二叉搜索树。
（）7、线性表中所有结点的类型必须相同。
（）8、连通分量是无向图中的极小连通子图。
（）9、空串与由空格组成的串没有区别。
（）10、带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。
（）四、简答1、在结点个数为n(n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？2、将下面的森林变换成二叉树。
3、有图如下，请画出其邻接多重表。
五．算法设计1、编写算法实现链表的创建、遍历、销毁。
2、编写算法，实现快速排序。
Part3一．选择1、在数据结构的讨论中把数据结构从逻辑上分为（）A）内部结构与外部结构 B）静态结构与动态结构C）线性结构与非线性结构 D）紧凑结构与非紧凑结构。
2、下面程序段的时间复杂度为（）for (int i=0;i<m;i++)for (int j=0;j<n;j++)a[i][j]=i*j;A）O(m2) B）O(n2) C）O(m*n) D）O(m+n)3、采用线性链表表示一个向量时，要求占用的存储空间地址（）A）必须是连续的 B）部分地址必须是连续的C）一定是不连续的 D）可连续可不连续4、已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为da1,则第I 个结点的地址为（）。
A）da1+(I-1)*m B）da1+I*m C）da1-I*m D）da1+(I+1)*m5．下面关于线性表的叙述中，错误的是（）A）顺序表使用一维数组实现的线性表 B）顺序表必须占用一片连续的存储单元C）顺序表的空间利用率高于链表 D）在单链表中,每个结点只有一个链域6、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（）A)s→link = p→link; p→link = s; B)p→link = s; s→link = q;C)p→link = s→link; s→link = p; D)q→link = s; s→link = p;7、设循环队列的结构如下：const int Maxsize=100;typedef int Data Type;typedef struct {Data Type data[Maxsize];Int front, rear;} Queue;若有一个Queue类型的队列Q，试问判断队列满的条件应是下列哪一个语句（）A)Q.front = = Q.rear; B)Q.front - Q.rear= = Maxsize;C)Q.front + Q.rear = = Maxsize; D)Q.front= = (Q.rear+1)% Maxsize;8、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（）。
