2013广西壮族自治区数据结构(C++)理论考试试题及答案

数据结构c考研试题及答案数据结构C考研试题及答案1. 选择题1.1 以下哪个选项不是线性表的顺序存储结构的特点？A. 存储空间连续B. 存储空间不连续C. 可以随机访问D. 插入和删除操作效率低答案：B1.2 在二叉树的遍历中，先访问根节点，然后遍历左子树，最后遍历右子树，这种遍历方式称为：A. 前序遍历B. 中序遍历C. 后序遍历D. 层序遍历答案：A2. 填空题2.1 在一个长度为n的数组中，使用二分查找法查找一个元素，最坏情况下需要比较的次数为______。

答案：log2(n+1)-12.2 哈希表的冲突解决方法有多种，其中一种方法是______。

答案：链地址法3. 简答题3.1 请简述图的深度优先搜索（DFS）算法的步骤。

答案：深度优先搜索算法的步骤如下：1. 访问起始顶点；2. 对于起始顶点的每一个邻接顶点，如果未被访问，则递归地进行深度优先搜索；3. 继续对未访问的邻接顶点进行步骤2，直到所有邻接顶点都被访问；4. 回溯到上一个顶点，继续访问未访问的邻接顶点，直到所有顶点都被访问。

3.2 什么是堆排序算法？请简要描述其工作原理。

答案：堆排序算法是一种基于二叉堆的比较排序算法。

其工作原理如下：1. 将待排序的序列构造成一个大顶堆；2. 将堆顶元素，即当前最大值，与序列末端元素进行交换，然后将序列长度减一；3. 对新的堆顶元素调整为新堆的堆顶；4. 重复步骤2和3，直到堆的大小为1或0。

4. 编程题4.1 编写一个函数，实现单链表的反转。

答案：```cstruct ListNode {int val;struct ListNode *next;};struct ListNode* reverseList(struct ListNode* head) {struct ListNode* prev = NULL;struct ListNode* curr = head;struct ListNode* next = NULL;while (curr != NULL) {next = curr->next;curr->next = prev;prev = curr;curr = next;}head = prev;return head;}```4.2 给定一个二叉搜索树的根节点，请实现一个函数，返回树中任意两个节点的值的差的绝对值的最小值。

c语言版数据结构试题及答案在学习数据结构的过程中，掌握相关的试题及答案是非常重要的。

本文将为你提供一份C语言版的数据结构试题及答案，帮助你更好地掌握这门学科。

以下是一些常见的数据结构试题及详细的答案解析。

一、单项选择题1. 下列哪个不是数据结构中的逻辑数据结构？A. 栈B. 数组C. 队列D. 链表答案：B解析：数组是一种物理数据结构，用于存储一组相同类型的元素，而不是逻辑上的数据结构。

逻辑上的数据结构指的是在操作时需要考虑元素之间的逻辑关系，如栈、队列和链表。

2. 下列关于栈的叙述中，错误的是：A. 栈是一种后进先出（LIFO）的数据结构B. 栈的插入操作称为入栈C. 栈可以通过数组或链表来实现D. 栈的删除操作称为弹栈或出栈答案：C解析：栈可以通过数组或链表来实现，因此选项C是正确的。

二、填空题1. 将下列序列按照栈的顺序进行入栈，并给出每一步的栈的状态：5, 3, 8, 4, 2答案：- 入栈5，栈的状态：5- 入栈3，栈的状态：5, 3- 入栈8，栈的状态：5, 3, 8- 入栈4，栈的状态：5, 3, 8, 4- 入栈2，栈的状态：5, 3, 8, 4, 2三、简答题1. 请简要解释树的遍历算法中的前序遍历、中序遍历和后序遍历分别是如何进行的？答案：- 前序遍历：先访问当前节点，然后递归地遍历左子树，最后递归地遍历右子树。

- 中序遍历：先递归地遍历左子树，然后访问当前节点，最后递归地遍历右子树。

- 后序遍历：先递归地遍历左子树，然后递归地遍历右子树，最后访问当前节点。

四、编程题1. 请编写一个C语言函数，用于计算给定二叉树的节点个数。

答案：```c#include <stdio.h>struct TreeNode {int value;struct TreeNode* left;struct TreeNode* right;};int countNodes(struct TreeNode* root) {if (root == NULL) {return 0;}else {return 1 + countNodes(root->left) + countNodes(root->right);}}int main() {// 构建二叉树struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));struct TreeNode* node1 = (struct TreeNode*)malloc(sizeof(struct TreeNode));struct TreeNode* node2 = (struct TreeNode*)malloc(sizeof(struct TreeNode));root->value = 1;node1->value = 2;node2->value = 3;root->left = node1;root->right = node2;node1->left = NULL;node1->right = NULL;node2->left = NULL;node2->right = NULL;int nodeCount = countNodes(root);printf("节点个数为：%d\n", nodeCount);return 0;}```解析：上述代码中，通过递归的方式计算二叉树的节点个数。

数据结构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 图的基本概念与术语图是由顶点的有穷非空集合和边的有穷集合组成的。

1 绪论数据结构复习题：绪论单选题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个______的有限序列。

绝密★考试结束前全国2013年10月高等教育自学考试数据结构试题课程代码：02331请考生按规定用笔将所有试题的答案涂、写在答题纸上。

选择题部分注意事项：1. 答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。

2. 每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。

如需改动，用橡皮擦干净后，再选涂其他答案标号。

不能答在试题卷上。

一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。

错涂、多涂或未涂均无分。

1．算法的时间复杂度表征的是A．算法的可读性B．算法的难易程度C．执行算法所耗费的时间D．执行算法所耗费的存储空间2．对需要频繁插入和删除结点的线性表，适合的存储方式是A．顺序储存B．链式存储C．索引存储D．散列存储3．在头指针为head的循环链表中，判断指针变量P指向尾结点的条件是A．p->next->next==head B．p->next==headC．p->next->next==NULL D．p->next==NULL4．迪杰斯特拉(Dijkstra)算法的功能是A．求图中某顶点到其他顶点的最短路径B．求图中所有顶点之间的最短路径C．求图的最小生成树D．求图的拓扑排序序列5．若栈的进栈序列为1，2，3，4，5，则经过出入栈操作不可能．．．获得的出栈序列是A．4，5，3，2，1 B．4，3，5，1，2C．1，2，3，4，5 D．5，4，3，2，16．A是7×4的二维数组，按行优先方式顺序存储，元素A[0][0]的存储地址为1 000，若每个元素占2个字节，则元素A[3][3]的存储地址为A．1015 B．1016C．1028 D．10307．深度为4的完全二叉树的结点数至少为A．4 B．8C．13 D．158．若采用邻接矩阵A存储有向图G，则结点k的入度等于A中A．结点k对应行元素之和B．结点k对应列元素之和C．结点k对应行和列元素之和D．非零元素之和9．无向图G的邻接矩阵一定是A．对称矩阵B．对角矩阵C．三角矩阵D．单位矩阵10．下列关于有向带权图G的叙述中，错误．．的是A．图G的任何一棵生成树都不含有回路B．图G生成树所含的边数等于顶点数减1C．图G含有回路时无法得到拓扑序列D．图G的最小生成树总是唯一的11．在下列排序算法中，关键字比较次数与初始排列次序无关的是A．冒泡排序B．希尔排序C．直接插入排序D．直接选择排序1 2．对下图进行拓扑排序，可以得到的拓扑序列是A．a b c d e B．b a c d eC．b c a d e D．a b d c e13．下列线性表中，能使用二分查找的是A．顺序存储(2,12,5,6,9,3,89,34,25) B．链式存储(2,12,5,6,9,3,89,34,25) C．顺序存储(2,3,5,6,9,12,25,34,89) D．链式存储(2,3,5,6,9,12,25,34,89) 14．在下列查找方法中，平均查找长度与结点数量无直接关系的是A．顺序查找B．分块查找C．散列查找D．基于B树的查找15．下列排序算法中，时间复杂度为O(nlog2 n)的算法是A．快速排序B．冒泡排序C．直接选择排序D．直接插入排序非选择题部分注意事项：用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。

“数据结构”期末考试试题一、单选题(每小题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．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。

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．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。

数据结构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、有一种简单的排序算法，叫做计数排序（count sorting）。

这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。

必须注意的是，表中所有待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。

(1) (3分)给出适用于计数排序的数据表定义;(2) (7分)使用Pascal或C语言编写实现计数排序的算法；(3) (4分)对于有n个记录的表，关键码比较次数是多少?(4) (3分)与简单选择排序相比较，这种方法是否更好?为什么?2、4、void LinkList_reverse(Linklist &L)//链表的就地逆置;为简化算法,假设表长大于2{p=L->next;q=p->next;s=q->next;p->next=NULL;while(s->next){q->next=p;p=q;q=s;s=s->next; //把L的元素逐个插入新表表头}q->next=p;s->next=q;L->next=s;}//LinkList_reverse3、#define maxsize 栈空间容量void InOutS(int s[maxsize])//s是元素为整数的栈，本算法进行入栈和退栈操作。

{int top=0; //top为栈顶指针，定义top=0时为栈空。

for(i=1; i<=n; i++) //n个整数序列作处理。

{scanf(“%d”,&x); //从键盘读入整数序列。

if(x!=-1) // 读入的整数不等于-1时入栈。

if(top==maxsize-1){printf(“栈满\n”);exit(0);}else s[++top]=x; //x入栈。

2013年广西计算机二级c语言试题及答案一、选择题（共40题，每题1.5分，共60分）1. 下列不是C语言的特点的是（）A. 结构化B. 面向对象C. 高效D. 易移植答案：B2. C程序的程序块由（）组成。

A. 语句B. 字符C. 符号D. 数字答案：A3. 下列代码中，错误的是（）A. int a = 10;B. float b = 3.14;C. char c = 'A';D. bool d = true;答案：D4. C语言中的注释方式有（）。

A. //B. /* */C. #D. //答案：B5. 下列关于C语言的函数声明错误的是（）A. int sum(int a, int b);B. double average();C. void printMessage();D. string getName();答案：D二、编程题（共4题，每题20分，共80分）1. 编写一个程序，从键盘输入两个整数，然后计算它们的和并输出结果。

答案：#include <stdio.h>int main() {int num1, num2, sum;printf("请输入两个整数：");scanf("%d%d", &num1, &num2);sum = num1 + num2;printf("两个整数的和为：%d\n", sum);return 0;}2. 编写一个程序，从键盘输入一个华氏温度，然后将其转换为摄氏温度并输出结果。

转换公式为：C = (F - 32) * 5 / 9。

答案：#include <stdio.h>int main() {int fahrenheit, celsius;printf("请输入华氏温度：");scanf("%d", &fahrenheit);celsius = (fahrenheit - 32) * 5 / 9;printf("摄氏温度为：%d\n", celsius);return 0;}3. 编写一个程序，判断一个正整数是否为素数。

数据结构（c 语言版）习题集答案第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 和imDestroyCmoplex(&C)操作结果：销毁复数CGet(C,k,&e) 操作结果：用e 返回复数C 的第k 元的值 Put(&C,k,e) 操作结果：改变复数C 的第k 元的值为e IsAscending(C) 操作结果：如果复数C 的两个元素按升序排列，则返回1，否则返回0 IsDescending(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，否则返回0 IsDescending(R)操作结果：若有理数R的两个元素按降序排列，则返回1，否则返回0 Max(R,&e)操作结果：用e返回有理数R的两个元素中值较大的一个Min(R,&e)操作结果：用e返回有理数R的两个元素中值较小的一个}ADT RationalNumber1.5 试画出与下列程序段等价的框图。

数据结构C语言版部分习题及标准答案————————————————————————————————作者：————————————————————————————————日期：第二章习题与解答一判断题1．线性表的逻辑顺序与存储顺序总是一致的。

2．顺序存储的线性表可以按序号随机存取。

3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。

4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。

5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。

6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。

7．线性表的链式存储结构优于顺序存储结构。

8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。

9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。

10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

二单选题 (请从下列A，B，C，D选项中选择一项)1．线性表是( ) 。

(A) 一个有限序列，可以为空；(B) 一个有限序列，不能为空；(C) 一个无限序列，可以为空；(D) 一个无序序列，不能为空。

2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。

插入一个元素时平均要移动表中的（）个元素。

(A) n/2 (B) n+1/2 (C) n -1/2 (D) n3．线性表采用链式存储时，其地址( ) 。

(A) 必须是连续的；(B) 部分地址必须是连续的；(C) 一定是不连续的；(D) 连续与否均可以。

4．用链表表示线性表的优点是（）。

(A)便于随机存取(B)花费的存储空间较顺序存储少(C)便于插入和删除(D)数据元素的物理顺序与逻辑顺序相同5．某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。

1、请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。

二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。

分析你的算法的时、空复杂度。

2、我们用l代表最长平台的长度，用k指示最长平台在数组b中的起始位置（下标）。

用j 记住局部平台的起始位置，用i指示扫描b数组的下标，i从0开始，依次和后续元素比较，若局部平台长度（i-j）大于l时，则修改最长平台的长度k（l=i-j）和其在b中的起始位置（k=j），直到b数组结束，l即为所求。

void Platform (int b[ ], int N)//求具有N个元素的整型数组b中最长平台的长度。

{l=1;k=0;j=0;i=0;while(i<n-1){while(i<n-1 && b[i]==b[i+1]) i++;if(i-j+1>l) {l=i-j+1;k=j;} //局部最长平台i++; j=i; } //新平台起点printf(“最长平台长度%d，在b数组中起始下标为%d”，l，k)；}// Platform3、将顶点放在两个集合V1和V2。

对每个顶点，检查其和邻接点是否在同一个集合中，如是，则为非二部图。

为此，用整数1和2表示两个集合。

再用一队列结构存放图中访问的顶点。

int BPGraph (AdjMatrix g)//判断以邻接矩阵表示的图g是否是二部图。

{int s[]; //顶点向量，元素值表示其属于那个集合（值1和2表示两个集合）int Q[];//Q为队列，元素为图的顶点，这里设顶点信息就是顶点编号。

int f=0,r,visited[]; //f和r分别是队列的头尾指针,visited[]是访问数组for (i=1;i<=n;i++) {visited[i]=0;s[i]=0;} //初始化，各顶点未确定属于那个集合Q[1]=1; r=1; s[1]=1;//顶点1放入集合S1while(f<r){v=Q[++f]; if (s[v]==1) jh=2; else jh=1;//准备v的邻接点的集合号if (!visited[v]){visited[v]=1; //确保对每一个顶点，都要检查与其邻接点不应在一个集合中for (j=1,j<=n;j++)if (g[v][j]==1){if (!s[j]) {s[j]=jh; Q[++r]=j;} //邻接点入队列else if (s[j]==s[v]) return(0);} //非二部图}//if (!visited[v])}//whilereturn(1); }//是二部图[算法讨论] 题目给的是连通无向图，若非连通，则算法要修改。

数据结构题集c语言版考试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，线性表的顺序存储结构是指（）。

A. 用一组地址连续的存储单元依次存储线性表的元素B. 用一组地址不连续的存储单元依次存储线性表的元素C. 用数组来存储线性表的元素D. 用链表来存储线性表的元素答案：A2. 在一个长度为n的顺序表中，删除第i个元素（1≤i≤n）时，需要移动（）个元素。

A. i-1B. n-iC. n-i+1D. i答案：B3. 对于一个有n个结点的线性表，采用链式存储结构时，进行查找第i个元素（1≤i≤n）的时间复杂度为（）。

A. O(1)B. O(n)C. O(log2n)D. O(n^2)答案：B4. 在二叉树的遍历过程中，若一个结点的左子树为空，则该结点的右子树（）。

A. 一定为空B. 一定不为空C. 可能为空，也可能不为空D. 以上说法都不对答案：C5. 在二叉排序树中，若某结点的左子树非空，则左子树中的所有结点的值（）。

A. 都小于该结点的值B. 都大于该结点的值C. 都等于该结点的值D. 都大于等于该结点的值答案：A6. 一个具有n个顶点的连通图，其边数最少为（）。

A. n-1B. nC. n+1D. 2n答案：A7. 在图的遍历中，深度优先搜索算法所对应的数据结构是（）。

A. 栈B. 队列C. 链表D. 数组答案：A8. 哈希表的冲突解决方法中，开放定址法的特点是（）。

A. 装填因子较大B. 装填因子较小C. 装填因子不受限制D. 以上说法都不对答案：B9. 快速排序算法的时间复杂度为（）。

A. O(n)B. O(nlogn)C. O(n^2)D. O(logn)答案：B10. 用链表表示线性表的优点是（）。

A. 插入和删除操作不需要移动元素B. 节省存储空间C. 可以方便地随机访问D. 可以动态分配存储空间答案：A二、填空题（每题2分，共20分）1. 在顺序表中，若p是指向第i个元素的指针，则p+5表示指向第（）个元素的指针。