清华大学数据结构试题及答案

2010年《数据结构》期终考试试卷（A）班级学号姓名一、简答题（每小题6分，共30分）(1) 假设一个线性链表的类名为linkedList，链表结点的类名为ListNode，它包含两个数据成员data和link。

data存储该结点的数据，link是链接指针。

下面给定一段递归打印一个链表中所有结点中数据的算法：void PrintList (ListNode *L) {if ( L != NULL ) {cout << L->data << endl;PrintList ( L->link );}}试问此程序在什么情况下不实用？给出具体修改后的可实用的程序？(1) 此程序在内存容量不足时不适用。

因为需要一个递归工作栈。

当链表越长，递归工作栈的深度越深，需要的存储越多。

可采用非递归算法节省存储。

void PrintList (ListNode *L) {while ( L != NULL ) {cout << L->data << endl;L = L->link;}}(2) 如果每个结点占用2个磁盘块因而需要2次磁盘访问才能实现读写，那么在一棵有n个关键码的2m阶B树中，每次搜索需要的最大磁盘访问次数是多少？(2) 在2m阶B树中关键码个数n与B树高度h之间的关系为h≤log m ((n+1)/2)+1，那么每次搜索最大磁盘访问次数为2h max = 2log m ((n+1)/2)+2。

(3) 给定一棵保存有n 个关键码的m 阶B 树。

从某一非叶结点中删除一个关键码需要的最大磁盘访问次数是多少？(3) 在m 阶B 树中关键码个数n 与B 树最大高度h 的关系为h = log ⎡m/2⎤((n+1)/2)+1。

若设寻找被删关键码所在非叶结点读盘次数为h ’，被删关键码是结点中的k i ，则从该结点的p i 出发沿最左链到叶结点的读盘次数为h -h ’。

第1章绪论1.1 解：数据是对客观事物的符号表示。

在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据对象是性质相同的数据元素的集合，是数据的一个子集。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

存储结构是数据结构在计算机中的表示。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。

是对一般数据类型的扩展。

1.2解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。

一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。

抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。

在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。

1.3 解：1.4 解：ADT Complex{数据对象：D={r,i|r,i为实数}数据关系：R={<r,i>}基本操作：InitComplex(&C,re,im)操作结果：构造一个复数C，其实部和虚部分别为re和imDestroyCmoplex(&C)操作结果：销毁复数CGet(C,k,&e)操作结果：用e返回复数C的第k元的值Put(&C,k,e)操作结果：改变复数C的第k元的值为eIsAscending(C)操作结果：如果复数C的两个元素按升序排列，则返回1，否则返回0IsDescending(C)操作结果：如果复数C的两个元素按降序排列，则返回1，否则返回0Max(C,&e)操作结果：用e返回复数C的两个元素中值较大的一个Min(C,&e)操作结果：用e返回复数C的两个元素中值较小的一个}ADT ComplexADT RationalNumber{数据对象：D={s,m|s,m为自然数，且m不为0}数据关系：R={<s,m>}基本操作：InitRationalNumber(&R,s,m)操作结果：构造一个有理数R，其分子和分母分别为s和mDestroyRationalNumber(&R)操作结果：销毁有理数RGet(R,k,&e)操作结果：用e返回有理数R的第k元的值Put(&R,k,e)操作结果：改变有理数R的第k元的值为eIsAscending(R)操作结果：若有理数R的两个元素按升序排列，则返回1，否则返回0IsDescending(R)操作结果：若有理数R的两个元素按降序排列，则返回1，否则返回0Max(R,&e)操作结果：用e返回有理数R的两个元素中值较大的一个Min(R,&e)操作结果：用e返回有理数R的两个元素中值较小的一个}ADT RationalNumber1.6解：(1)exit常用于异常错误处理，它可以强行中断程序的执行，返回操作系统。

清华大学数据结构试题及答案以下是清华大学数据结构试题及答案：试题一：1. 请解释什么是数据结构。

答案：数据结构是计算机科学中研究数据的组织、存储和管理方式的学科。

它涉及到数据的表示、操作以及与之相关的算法的设计和实现。

2. 请列举常见的数据结构类型。

答案：常见的数据结构类型包括数组、链表、栈、队列、树、图等。

3. 请解释什么是算法。

答案：算法是一系列解决特定问题的指令和计算步骤。

它描述了在给定输入的情况下，如何进行计算并产生所需输出。

4. 请列举一些常见的算法。

答案：常见的算法包括排序算法（如冒泡排序、插入排序、快速排序）、查找算法（如二分查找、哈希查找）、图算法（如深度优先搜索、广度优先搜索）等。

5. 请解释什么是时间复杂度和空间复杂度。

答案：时间复杂度是描述算法执行时间与输入规模之间的关系。

空间复杂度是描述算法所需内存空间与输入规模之间的关系。

试题二：1. 请给出数组和链表的区别。

答案：数组是一块连续的内存空间，元素在内存中按照索引顺序排列。

链表是由节点组成的数据结构，每个节点包含数据和指向下一个节点的指针。

2. 请解释什么是栈和队列。

答案：栈是一种后进先出（LIFO）的数据结构，只允许在栈顶进行插入和删除操作。

队列是一种先进先出（FIFO）的数据结构，允许在队尾插入数据，在队头删除数据。

3. 请给出树和图的区别。

答案：树是一种由节点和边组成的数据结构，每个节点可以有多个子节点。

图是一种由节点和边组成的数据结构，节点之间的关系可以是任意的，包括有向和无向边。

4. 请解释什么是哈希表。

答案：哈希表是一种通过哈希函数将键映射到特定位置的数据结构。

它能够快速地进行插入、删除和查找操作。

5. 请解释什么是递归。

答案：递归是一种通过调用自身的方法或函数来解决问题的编程技巧。

在递归过程中，问题会被拆分成一个或多个规模较小的子问题，直到达到基本情况。

以上就是清华大学数据结构试题及答案，希望对您有所帮助。

一、单选题（每题 2 分，共20分）1.对一个算法的评价，不包括如下（）方面的内容。

A．健壮性和可读性 B．并行性 C．正确性 D．时空复杂度2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。

A. p->next=HL->next; HL->next=p;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=HL;3对线性表，在下列哪种情况下应当采用链表表示？( )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35. AOV网是一种（）。

A．有向图 B．无向图 C．无向无环图 D．有向无环图6采用开放定址法处理散列表的冲突时，其平均查找长度（）。

A．低于链接法处理冲突 B. 高于链接法处理冲突C．与链接法处理冲突相同 D．高于二分查找7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。

A．值 B．函数 C．指针 D．引用8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。

A．行号 B．列号 C．元素值 D．非零元素个数9.快速排序在最坏情况下的时间复杂度为（）。

A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。

A. O(n)B. O(1)C. O(log2n)D. O(n2)二、运算题（每题6 分，共24分）1.数据结构是指数据及其相互之间的______________。

当结点之间存在M对N（M：N）的联系时，称这种结构为_____________________。

第1 章绪论课后习题讲解1. 填空⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

【解答】数据元素⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。

【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。

⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。

【解答】集合，线性结构，树结构，图结构⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。

【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。

【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。

【解答】自然语言，程序设计语言，流程图，伪代码，伪代码⑺在一般情况下，一个算法的时间复杂度是（）的函数。

【解答】问题规模⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。

【解答】Ο(1)，Ο(nlog2n)【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。

2. 选择题⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。

A 线性结构B 非线性结构C 存储位置D 指针【解答】C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。

则表示该遗产继承关系的最合适的数据结构应该是（）。

数据结构（C语言版）清华大学出版社课后题1-5章答案第一章选择题1.A2.B3.C4.D5.B6.C第二章选择题1.A2.D3.D4.C5.A6.C7.B8.B9.D 10.D应用题1．应该选用链接存储表示。

如果才用顺序表示法，必须在一个连续的可用空间中为这N 个表分配空间。

初始时候因为不知道哪个表增长得快，必须平均分配空间。

在程序运行过程中，有的表占用的空间增长得快，有的表占用空间增长得慢，有的表很快就使用完了分配给它的空间，有的表才占用了少许空间，在进行元素的插入时候就必须成片的移动其他表的空间，以空出位置进行插入；在元素删除时为填补空白，也可能移动许多元素。

这个处理过程及其繁琐和低效。

如果采用链接存储，一个表的空间可以连续也可以不连续。

表的增长通过动态分配内存得以解决，只要存储器未满，就不会发生表溢出；表的收缩可以通过动态存储释放实现，释放的空间还可以在以后动态分配给其他的存储需求，非常灵活方便。

对于N个表（包括表的总数可能变化）共存的情形，处理十分简单快捷，插入、删除时间复杂度为O（1）。

所以才用链接存储表示较好。

2．一般来说，链式存储结构克服了顺序存储结构的三个缺点。

首先，插入、删除操作不需要移动元素，只修改指针；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受到内存空间的限制。

其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储的缺点。

3.顺序结构时ai与ai+1的物理位置相邻，链表结构时两者的位置不要求一定相邻。

7.在顺序表中插入和删除一个节点需平均移动全表一半的节点。

具体的移动次数取决于所插入和删除的节点的位置i和全表的长度n这两个因素。

算法设计题1.分析：遍历整个顺序表，用k记录在x~y之间元素的个数，k的初始值为0。

对于当前遍历到的元素，若其值在x~y之间，则前移k个位置；否则执行++k。

这样每个不在x~y之间的元素仅仅移动一次，所以效率较高。

第1 章绪论课后习题讲解1. 填空⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

【解答】数据元素⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。

【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。

⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。

【解答】集合，线性结构，树结构，图结构⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。

【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。

【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。

【解答】自然语言，程序设计语言，流程图，伪代码，伪代码⑺在一般情况下，一个算法的时间复杂度是（）的函数。

【解答】问题规模⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。

【解答】Ο(1)，Ο(nlog2n)【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。

2. 选择题⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。

A 线性结构B 非线性结构C 存储位置D 指针【解答】C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。

则表示该遗产继承关系的最合适的数据结构应该是（）。

第八章选择题1. C2.A3.B4.C5.D6.B7.B8.A9.D 10.D 11.C 12.C填空题1.n、n+12. 43.8.25( 折半查找所在块 )4.左子树、右子树5.266.顺序、(n+1)/2、O(log2n)7.m-1、[m/2]-18.直接定址应用题1.进行折半查找时，判定树是唯一的，折半查找过程是走了一条从根节点到末端节点的路径，所以其最大查找长度为判定树深度[log2n]+1.其平均查找长度约为[log2n+1]-1.在二叉排序树上查找时，其最大查找长度也是与二叉树的深度相关，但是含有n个节点的二叉排序树不是唯一的，当对n个元素的有序序列构造一棵二叉排序树时，得到的二叉排序树的深度也为n，在该二叉树上查找就演变成顺序查找，此时的最大查找长度为n；在随机情况下二叉排序树的平均查找长度为1+4log2n。

因此就查找效率而言，二分查找的效率优于二叉排序树查找，但是二叉排序树便于插入和删除，在该方面性能更优。

3. 评价哈希函数优劣的因素有：能否将关键字均匀的映射到哈希表中，有无好的处理冲突的方法，哈希函数的计算是否简单等。

冲突的概念：若两个不同的关键字Ki和Kj，其对应的哈希地址Hash(Ki) =Hash(Kj)，则称为地址冲突，称Ki和K,j为同义词。

（1）开放定址法（2）重哈希法（3）链接地址法4.（1）构造的二叉排序树，如图（2）中序遍历结果如下：10 12 15 20 24 28 30 35 46 50 55 68（4）平均查找长度如下：ASLsucc = （1x1+2x2+3x3+4x3+5x3）/12 = 41/128.哈希地址如下：H(35) = 35%11 = 2H(67) = 67%11 = 1H(42) = 42%11 = 9H(21) = 21%11 = 10H(29) = 29%11 = 7H(86) = 86%11 = 9H(95) = 95%11 = 7H(47) = 47%11 = 3H(50) = 50%11 = 6H(36) = 36%11 = 3H(91) = 91%11 = 3第九章选择题1. D2.C3.B4.D5.C6.B7.A8.A9.D 10.D填空题1.插入排序、交换排序、选择排序、归并排序2.移动（或者交换）3.归并排序、快速排序、堆排序4.保存当前要插入的记录，可以省去在查找插入位置时的对是否出界的判断5.O(n)、O(log2n)6.直接插入排序或者改进了的冒泡排序、快速排序7.Log2n、n8.完全二叉树、n/29.1510.{12 38 25 35 50 74 63 90}应用题11.（1）Shell排序(步长为5 3 1)每趟的排序结果初始序列为100 87 52 61 27 170 37 45 61 118 14 88 32步长为5的排序14 37 32 61 27 100 87 45 61 118 170 88 52步长为3的排序结果14 27 32 52 37 61 61 45 88 87 170 100 118步长为1的排序结果14 27 32 37 45 52 61 61 87 88 100 118最后结果14 27 32 37 45 52 61 61 87 88 100 118 170（2）快速排序每趟的排序结果如图初始序列100 87 52 61 27 170 37 45 61 118 14 88 32第一趟排序[32 87 52 61 27 88 37 45 61 14]100[118 170]第二趟排序[14 27]32[61 52 88 37 45 61 87]100 118[170]第三趟排序14[27]32[45 52 37]61[88 61 87]100 118[170]第四趟排序14[27]32[37]45[52]61[87 61]88 100 118[170]第五趟排序14[27]32[37]45[52]61[87 61]88 100 118[170]最后结果14[27]32[37]45[52]61[61]87 88 100 118[170]（3）二路归并排序每趟的排序结果初始序列[100][87][52][61][27][170][37][45][61][118][14][88][32]第一趟归并[87 100][52 61][27 170][37 45][61 118][14 88][32]第二趟归并[52 61 87 100][27 37 45 170][14 61 88 118][32]第三趟归并排序[27 37 45 52 61 87 100 170][14 32 61 88 118]第四趟归并排序[14 27 32 37 45 52 61 61 87 88 100 118 170]最后结果14 27 32 37 45 52 61 61 87 88 100 118 17012.采用快速排序时，第一趟排序过程中的数据移动如图：算法设计题1.分析：为讨论方便，待排序记录的定义为（后面各算法都采用此定义）：#define MAXSIZE 100 /* 顺序表的最大长度，假定顺序表的长度为100 */ typedef int KeyType; /* 假定关键字类型为整数类型 */typedef struct {KeyType key; /* 关键字项 */OtherType other; /* 其他项 */}DataType; /* 数据元素类型 */typedef struct {DataType R[MAXSIZE+1]; /* R[0]闲置或者充当哨站 */int length; /* 顺序表长度 */}sqList; /* 顺序表类型 */设n个整数存储在R[1..n]中，因为前n-2个元素有序，若采用直接插入算法，共要比较和移动n-2次，如果最后两个元素做一个批处理，那么比较次数和移动次数将大大减小。

清华大学模拟题一一．单项选择题（2分/题）1．一个栈的输入序列为12345，则下列序列中是栈的输出序列的是（）。

知道这题的解题思路吗？A.23415B.54132C.31245D.142532．设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素个数为（）。

A.r-fB.r-f+1C.(r-f) mod n +1D.(r-f+n) mod n3．二叉树在线索化后，仍不能有效求解的问题是（）。

这题是线索化问题，可能你没看过。

可以等我去给你讲。

A.先序线索二叉树中求先序后继B. 中序线索二叉树中求中序后继C.中序线索二叉树中求中序前驱D. 后序线索二叉树中求后序后继4．求最短路径的FLOYD算法的时间复杂度为（）。

（那Djstla的时间复杂度呢？）A.O(n)B.O(n+e)C.O(n2)D.O(n3)5．一棵左右子树不空的二叉树在先序线索化后，其空指针域数为（）。

（知道是哪个指针域吗？就是最后一个访问的节点的右指针，因为它没有后继节点。

）A.0B.1C.2D.不确定6．数组A[1..5,1..6]的每个元素占5个单元，将其按行优先顺序存储在起始地址为1000的连续的内存单元中，则元素A[5,5]的地址为（）。

这题可要会哟@A.1140B.1145C.1120D.11257．在下列排序算法中，在待排序的数据表已经为有序时，花费时间反而最多的是（）。

(要知道为什么，这个我跟你讲过)A.快速排序B.希尔排序C.冒泡排序D.堆排序8．对有18个元素的有序表做折半查找，则查找A[3]的比较序列的下标依次为（）。

（这题的数组下标应该说明一下是A[1..18]）A.1-2-3B.9-5-2-3C.9-5-3D. 9-4-2-39．下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（）。

这些题出的都不错！A.堆排序B.冒泡排序C.快速排序D.直接插入排序10．在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点为A，并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则做（）型调整以使其平衡。

第1章 绪论1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

解：数据是对客观事物的符号表示。

在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据对象是性质相同的数据元素的集合，是数据的一个子集。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

存储结构是数据结构在计算机中的表示。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。

是对一般数据类型的扩展。

1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。

一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。

抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。

在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。

1.3 设有数据结构(D,R)，其中{}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r =试按图论中图的画法惯例画出其逻辑结构图。

解：1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。

解：ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={<r,i>} 基本操作： InitComplex(&C,re,im)操作结果：构造一个复数C ，其实部和虚部分别为re 和im DestroyCmoplex(&C)操作结果：销毁复数C Get(C,k,&e) 操作结果：用e 返回复数C 的第k 元的值 Put(&C,k,e) 操作结果：改变复数C 的第k 元的值为eIsAscending(C)操作结果：如果复数C 的两个元素按升序排列，则返回1，否则返回0IsDescending(C)操作结果：如果复数C的两个元素按降序排列，则返回1，否则返回0 Max(C,&e)操作结果：用e返回复数C的两个元素中值较大的一个Min(C,&e)操作结果：用e返回复数C的两个元素中值较小的一个}ADT ComplexADT RationalNumber{数据对象：D={s,m|s,m为自然数，且m不为0}数据关系：R={<s,m>}基本操作：InitRationalNumber(&R,s,m)操作结果：构造一个有理数R，其分子和分母分别为s和mDestroyRationalNumber(&R)操作结果：销毁有理数RGet(R,k,&e)操作结果：用e返回有理数R的第k元的值Put(&R,k,e)操作结果：改变有理数R的第k元的值为eIsAscending(R)操作结果：若有理数R的两个元素按升序排列，则返回1，否则返回0 IsDescending(R)操作结果：若有理数R的两个元素按降序排列，则返回1，否则返回0 Max(R,&e)操作结果：用e返回有理数R的两个元素中值较大的一个Min(R,&e)操作结果：用e返回有理数R的两个元素中值较小的一个}ADT RationalNumber1.5 试画出与下列程序段等价的框图。

附录习题参考答案习题1参考答案1.1.选择题(1). A. (2). A. (3). A. (4). B.,C. (5). A. (6). A. (7). C. (8). A. (9). B. (10.)A.1.2.填空题(1). 数据关系(2). 逻辑结构物理结构(3). 线性数据结构树型结构图结构(4). 顺序存储链式存储索引存储散列表（Hash）存储(5). 变量的取值范围操作的类别(6). 数据元素间的逻辑关系数据元素存储方式或者数据元素的物理关系(7). 关系网状结构树结构(8). 空间复杂度和时间复杂度(9). 空间时间(10). Ο(n)1.3 名词解释如下：数据：数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。

数据项：数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。

数据元素：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由若干个数据项组成。

数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。

数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。

数据类型：是指变量的取值范围和所能够进行的操作的总和。

算法：是对特定问题求解步骤的一种描述，是指令的有限序列。

1.4 语句的时间复杂度为：(1) Ο(n2)(2) Ο(n2)(3) Ο(n2)(4) Ο(n-1)(5) Ο(n3)1.5 参考程序：main(){int X,Y,Z；scanf(“%d, %d, %d”,&X,&Y,Z)；if (X>=Y)if(X>=Z)if (Y>=Z){ printf(“%d, %d, %d”,X,Y,Z);}else{ printf(“%d, %d, %d”,X,Z,Y);}else{ printf(“%d, %d, %d”,Z,X,Y);}elseif(Z>=X)if (Y>=Z){ printf(“%d, %d, %d”,Y,Z,X);}else{ printf(“%d, %d, %d”,Z,Y,X);}else{ printf(“%d, %d, %d”,Y,X,Z);}}1.6 参考程序：main(){int i,n;float x,a[],p;printf(“\nn=”);scanf(“%f”,&n);printf(“\nx=”);scanf(“%f”,&x);for(i=0;i<=n;i++)scanf(“%f ”,&a[i]);p=a[0];for(i=1;i<=n;i++){ p=p+a[i]*x;x=x*x;}printf(“%f”,p)’}习题2参考答案2.1选择题(1). C. (2). B. (3). B. (4). B. 5. D. 6. B. 7. B. 8. A. 9. A. 10. D.2.2.填空题(1). 有限序列(2). 顺序存储和链式存储(3). Ｏ(n) O(n)(4). n-i+1 n-i(5). 链式(6). 数据指针(7). 前驱后继(8). Ο(1) Ο(n)(9). s->next=p->next; p->next=s ;(10). s->next2.3. 解题思路：将顺序表A中的元素输入数组a，若数组a中元素个数为n,将下标为0，1,2,…,（n-1）/2的元素依次与下标为n,n-1,…, （n-1）/2的元素交换，输出数组a的元素。

一、单选题（每题 2 分，共20分)1.1.对一个算法的评价，不包括如下（B )方面的内容。

A．健壮性和可读性 B．并行性 C．正确性 D．时空复杂度2.2.在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结点，则执行（）。

A。

p—>next=HL->next； HL—>next=p; B。

p—〉next=HL； HL=p；C. p—>next=HL; p=HL；D. HL=p； p—〉next=HL；3.3。

对线性表，在下列哪种情况下应当采用链表表示？( )A.经常需要随机地存取元素 B。

经常需要进行插入和删除操作C。

表中元素需要占据一片连续的存储空间 D.表中元素的个数不变4.4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )A。

2 3 1 B. 3 2 1C。

3 1 2 D。

1 2 35.5。

AOV网是一种( ）.A．有向图 B．无向图 C．无向无环图 D．有向无环图6.6.采用开放定址法处理散列表的冲突时,其平均查找长度( ）。

A．低于链接法处理冲突 B。

高于链接法处理冲突C．与链接法处理冲突相同 D．高于二分查找7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。

A．值 B．函数 C．指针 D．引用8.8。

在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点都具有相同的( ）。

A．行号 B．列号 C．元素值 D．非零元素个数9.9。

快速排序在最坏情况下的时间复杂度为( ).A．O（log2n) B．O（nlog2n) C．0(n） D．0（n2)10.10.从二叉搜索树中查找一个元素时,其时间复杂度大致为（）。

A。

O(n） B。

O(1) C. O(log2n） D。

O（n2)二、二、运算题（每题 6 分，共24分）1.1。

数据结构是指数据及其相互之间的______________.当结点之间存在M对N（M：N)的联系时，称这种结构为_____________________。

《数据结构与算法》（清华）典型例题-图文6.3典型例题一、单项选择题[例6-1]数据结构用集合的观点可以表示为一个二元组DS＝(D，R)。

其中，D是(①)的有穷集合，R是D上(②)的有限集合。

①A.算法B.数据元素C.数据操作D.逻辑结构②A.操作B.映像C.存储D．关系解析：由数据结构的集合形式化定义可知，本题答案为：①B；②D。

[例6-2]数据的常用存储结构中不包括()。

A．顺序存储结构B．线性结构C．索引存储结构D．散列存储结构解析：数据通常有四种基本的存储方法，即顺序存储方法、链式存储方法、索引存储方法和散列存储方法。

由此可知，本题答案为：B。

[例6-3]算法指的是(①)，它必须具备(②)这三个特性。

①A．计算方法B．排序方法C．解决问题的步骤序列D．调度方法②A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性C．确定性、有穷性、稳定性D．易读性、稳定性、安全性解析：算法是对特定问题求解步骤的一种描述，是由若于条指令组成的有限序列。

它必须满足以下性质：输人性、输出性、有穷性、确定性、无二义性和可行性。

由此可知，本题答案为：①㈠②B。

[例6-4]在下面的程序段中，对某的赋值语句的执行频度为()。

for(i=0；ifor(j=0；j某=某+l：A．O(2n)B．O(n)C．O(n2)D．O(1bn)解析：语句的执行频度即语句重复执行的次数，属于算法的时间复杂度类题目。

本题中对某的赋值语句为一个二重循环的循环体，外层循环循环n次，内层循环也循环n次，显然此语句的执行次数为n某n＝n2次。

由此可知，本题答案为：C。

二、填空题[例6-5]是数据的基本单位，通常由若干个组成，是数据的最小单位。

解析：本题是基本概念题，知识点为数据结构的相关概念。

本题答案为：数据元素；数据项；数据项。

三、应用题[例6-6]简述数据结构的定义。

解析：数据结构是指数据元素之间的相互关系，即数据的组织形式。

数据结构通常包括三个方面的内容，分别是数据的逻辑结构、数据的存储结构(物理结构)和在这些数据上定义的运算。