下载文档原格式
数据结构c期末考试题及答案一、选择题（每题2分，共20分）1. 在数据结构中，以下哪种数据结构可以有效地表示元素之间的“一对一”关系？A. 链表B. 栈C. 队列D. 哈希表答案：D2. 以下哪个算法的时间复杂度是O(n^2)？A. 冒泡排序B. 快速排序C. 二分查找D. 归并排序答案：A3. 在二叉树中，叶子节点是指？A. 没有子节点的节点B. 只有一个子节点的节点C. 有两个子节点的节点D. 包含子节点的节点答案：A4. 以下哪种排序算法是稳定的？A. 快速排序B. 冒泡排序C. 堆排序D. 选择排序答案：B5. 在图的遍历中，深度优先搜索（DFS）使用的是？A. 栈B. 队列C. 链表D. 哈希表答案：A6. 哈希表解决冲突的一种方法是？A. 链地址法B. 线性探测法C. 二次探测法D. 所有选项都是答案：D7. 以下哪种数据结构适合实现数据库索引？A. 树B. 链表C. 数组D. 队列答案：A8. 以下哪种排序算法的空间复杂度是O(1)？A. 插入排序B. 归并排序C. 快速排序D. 冒泡排序答案：A9. 在图的表示中，邻接矩阵适用于表示？A. 稠密图B. 稀疏图C. 无向图D. 有向图答案：A10. 以下哪种数据结构可以用于实现LRU缓存淘汰算法？A. 队列B. 栈C. 链表D. 哈希表答案：C二、填空题（每题2分，共20分）1. 在数据结构中，栈是一种______的数据结构，遵循后进先出的原则。
答案：线性2. 一个长度为n的数组，使用二分查找算法查找一个元素的时间复杂度是______。
答案：O(log n)3. 红黑树是一种______的二叉查找树。
答案：平衡4. 在图的遍历中，广度优先搜索（BFS）使用的是______。
答案：队列5. 哈希表的装载因子是指______与哈希表大小的比值。
答案：哈希表中已存元素数量6. 快速排序算法中，基准元素的选择会影响算法的______。
答案：性能7. 在图的表示中，邻接表适用于表示______。
第10章综合测试[能力要求]（1）计算机基础知识：掌握图的概念以及图的基本操作。
（2）分析问题：针对具体的问题，要能够运用图去进行分析，逐步找到解决问题的方法。
（3）具有概念化和抽象化能力：针对具体的应用和实际的问题，能够运用图对问题进行抽象，提取它的逻辑结构和存储结构。
（4）发现问题和表述问题：在具体的工程中，能够发现工程中涉及到图的问题，并能够明确表述。
（5）建模：在具体的工程中，能够使用图进行建模，设计合理的数据结构和相应的算法。
（6）解决方法和建议：在具体工程应用中，发现了关于图的问题，要能够解决问题，并提出合理的建议。
（7）定义功能，概念和结构：使用图这种逻辑结构处理一些具体问题，实现系统的功能。
（8）设计过程的分段与方法：采取不同的阶段去设计（概念设计、详细设计）一个具体的图的应用项目。
（9）软件实现过程：了解系统中各个模块中的关于图的设计；讨论算法（数据结构、控制流程、数据流程）；使用编程语言实施底层设计（编程）。
10.1综合测试题1一、判断题说明：共10题，每题1分，满分10分（）1① 有一批数据，经常用来进行插入和删除处理，这样的数据用顺序表存储最合适。
（）2① 栈用于实现子程序调用。
（）3① 队列可用于表达式的求值。
（）4① 队列在队头插入，队尾删除。
（）5② 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。
（）6② 完全二叉树的某结点若无左孩子，则它必是叶结点。
（）7② 将一棵树转换成二叉树后，根结点没有左子树。
（）8② 任一二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间。
（）9② 中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。
（）10③ 如果待排序的数据是有一定顺序的，那么冒泡和简单选择排序法中，简单选择最好。
二、填空题说明：共10空，每空1分，满分10分。
1① 栈的特点是 ，队列的特点是 。
2③ 深度为k 的完全二叉树的至少有 个节点， 至多有 节点。
数据结构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 语言）一.选择题（10X2分）：共10小题，请将答案壊入题中的括号中，毎小题惟独一个正确答案，错选或者不逸均不给分・ 1. 2.组成数据的基本单位是（） A.数据项 C.数据元素 下面程序段的时间复杂度为（ fbr （i=l;i<=n;i++） for （J=ij <=n;j++）s++, A. 0（1）B.数据类型 数据变量D.B. 0(n)C ・ O(nlog/)) D. O(n 2) 在一个长度为n 的顺序存储线性表中，向第1个兀素（1 WiWn+1）之前插入一个新兀素时, 需向后挪移（）个元素。
A. U-1 C. n-1-l 4.设单链表中指针p 指向结点A, 操作为（）» A. p->next=p->next->next C. p=p->next->next若让元素1, 2, 3挨次进栈， A 、 3, 2, 1 C, 3, 1, 23. 5. 6. 7. 8. 9. B. n-1+l D. 1 若要删除A 后的结点且该结点存在，则需要修改指针的 B ■ p=p ->next D . p->next=p则出栈次序不可,能浮现()种情况。
B, 2, 1, 3 D. 1, 3. 2在一个循环顺序队列中，队首指针指向队首元素的（）位置。
A 、当前 B 、后面 C 、前一个D 、后一个假定一个链队的队首和队尾指针分别为front 和A 、front=NULLC 、 rear!=NULL 二叉树第证二1）层最多有（ A. 21C. 21 rear.则判断队空的条件是（）。
B 、 front!=NULLD. front 二二rear）个结点。
B. 2时D ・ 2l -l 如果结点A 有3个兄弟，而且B 为A 的双亲，则B 是度为（） A. 4 B. 3 C. 5 D. 1 下列哪种排序算法的平均时间复杂度最优（）o 直接选择排序 冒泡排序 10.当待排序序列的关键码是随机分布时, A.直接插入排序 C.快速排序 B.D. 二.填空题（30分）：每空2分1.数据的逻辑结构被分为' 、和四种。
数据结构c语言版期末考试试题及答案一、选择题（每题2分，共20分）1. 在数据结构中，线性表的顺序存储结构通常使用（）。
A. 链式存储B. 连续存储C. 非连续存储D. 散列存储答案：B2. 下列关于栈的描述，正确的是（）。
A. 栈是一种后进先出（LIFO）的数据结构B. 栈是一种先进后出（FILO）的数据结构C. 栈只能进行插入操作D. 栈只能进行删除操作答案：A3. 在二叉树的遍历中，先访问左子树，再访问根节点，最后访问右子树的遍历方式称为（）。
A. 前序遍历B. 中序遍历C. 后序遍历D. 层次遍历答案：B4. 散列表的冲突解决方法中，开放定址法的特点是（）。
A. 冲突的元素存储在表外B. 冲突的元素存储在表内C. 冲突的元素存储在表的尾部D. 冲突的元素存储在表的头部答案：B5. 以下算法中，时间复杂度为O(nlogn)的是（）。
A. 快速排序B. 冒泡排序C. 插入排序D. 选择排序答案：A6. 在图的遍历算法中，深度优先搜索（DFS）使用的辅助数据结构是（）。
A. 队列B. 栈C. 链表D. 树答案：B7. 哈希表的装载因子是（）。
A. 表中已填入的元素个数与表的总容量的比值B. 表中已填入的元素个数与表的总容量的乘积C. 表中已填入的元素个数与表的总容量的差值D. 表中已填入的元素个数与表的总容量的商答案：A8. 以下关于链表的描述，错误的是（）。
A. 链表的每个节点包含数据和指向下一个节点的指针B. 链表的插入和删除操作的时间复杂度为O(n)C. 链表的查找操作的时间复杂度为O(n)D. 链表的存储空间利用比数组更灵活答案：B9. 在二叉搜索树中，若删除一个节点，那么其子树的调整方式是（）。
A. 用其左子树的最大值替换B. 用其右子树的最小值替换C. 用其左子树的最小值替换D. 用其右子树的最大值替换答案：A10. 以下排序算法中，时间复杂度为O(n)的是（）。
A. 快速排序B. 归并排序C. 堆排序D. 桶排序答案：D二、简答题（每题5分，共20分）1. 请简述什么是时间复杂度，并给出一个O(n)时间复杂度的算法例子。
数据结构c语言版试题及答案一、选择题（每题2分，共20分）1. 在C语言中，以下哪个关键字用于定义结构体？A. structB. unionC. enumD. typedef答案：A2. 若定义了一个结构体变量，下列哪个语句是正确的？A. struct Student stu;B. struct Student stu[];C. struct Student stu[10];D. Student stu;答案：A3. 在C语言中，下列哪个函数用于创建链表节点？A. mallocB. freeC. callocD. realloc答案：A4. 下列哪个选项不是线性表的顺序存储结构的特点？A. 存储空间连续B. 可以快速地存取任一元素C. 空间利用率高D. 插入和删除操作复杂答案：D5. 在C语言中，以下哪个函数用于释放动态分配的内存？A. mallocB. freeC. callocD. realloc答案：B6. 下列哪个选项不是栈的基本操作？A. pushB. popC. topD. clear答案：D7. 在C语言中，以下哪个关键字用于定义联合体？A. structB. unionC. enumD. typedef答案：B8. 下列哪个选项是二叉树的遍历方式？A. 前序遍历B. 中序遍历C. 后序遍历D. 所有选项答案：D9. 在C语言中，以下哪个关键字用于定义枚举类型？A. structB. unionC. enumD. typedef答案：C10. 下列哪个选项是队列的基本操作？A. enqueueB. dequeueC. peekD. 所有选项答案：D二、填空题（每题2分，共20分）1. 结构体定义的关键字是______。
答案：struct2. 动态内存分配的函数是______。
答案：malloc3. 在C语言中，链表的头节点通常定义为______类型。
答案：指针4. 顺序存储结构的存储空间是______的。
广东工业大学试卷用纸，共 6 页，第 1 页
广东工业大学试卷用纸，共 6 页，第 2 页
广东工业大学试卷用纸，共 6 页，第 3 页
广东工业大学试卷用纸，共 6 页，第 4 页
广东工业大学试卷用纸，共 6 页，第 5 页
广东工业大学试卷用纸，共 6 页，第 6 页
广东工业大学试卷用纸，共 6 页，第7 页
广东工业大学试卷用纸，共 6 页，第 8 页
1 （1分）；
NULL ；或者 0 ；
三、应用题：
1、 （4分，画对根结点1分，左子树正确1.5分，右子树正确1.5分）
后序序列为：DGJHEBKIFCA （2分）
2、前序序列补充完整为：ABCDEFGH （1分）
中序序列补充完整为：CBDEAGHF （1分）
后序序列补充完整为：CEDBHGFA （1分）
（3分，画对根结点1分，左子树正确1分，右子树正确1分）
（4分）画对各结点线索指针得2分，标志位正确得1分，表头结点正确得
3、 （4分，画对各树根结点2分， 画对各子树子女结点2分）
A B C
D E F G H I J K
A B F
C D G E H
广东工业大学试卷用纸，共 6 页，第9 页
广东工业大学试卷用纸，共 6 页，第10 页。
A BC D、下列函数中，时间复杂度最小的是＿＿＿＿＿＿＿＿。
A BC D、栈和队列属于＿＿＿＿＿＿＿＿逻辑结构。
A BC D一个算法所需时间由下述递归方程表示，该算法的时间复杂度是＿＿＿＿＿＿＿＿。
A BC D为正整数，下列程序段的时间复杂度是＿＿＿＿＿＿＿＿。
A BC DB、数据项是数据中不可分割的最小标识单位C、数据可由若干个数据元素组成D、数据项可由若干个数据元素组成3、算法分析的主要方面是＿＿＿＿＿＿＿＿。
A、时间复杂度B、空间复杂度C、数据复杂性D、程序复杂性4、一个"好"的算法应达到的目标有＿＿＿＿＿＿＿＿。
A、正确性B、可行性C、可读性D、健壮性E、高效与低存储量F、确定性5、研究数据结构就是研究＿＿＿＿＿＿＿＿。
A、数据的逻辑结构B、数据的物理结构C、数据在运算上的实现D、数据的复杂度第三题、判断题（每题1分，5道题共5分）1、任何数据结构都具备三个基本运算：插入、删除和查找。
（）正确错误2、数据元素可以由很多数据项组成。
（）正确错误正确错误、算法分析的目的是研究算法中输入和输出的关系。
（正确错误、在计算机科学中，数据的含义可以很广泛，图像、声音等都可以通过编码的形式而归之于数据的范畴。
正确错误第二章A BC D、在一个单链表中，在所指结点应执行＿＿＿＿＿＿＿＿。
A BC D个元素的单链表中插入或删除一个元素的算法的时间复杂度为＿＿＿＿＿＿＿＿。
A BC D个元素的单链表，其算法的时间复杂度为＿＿＿＿＿＿＿＿。
A BC D个元素的有序单链表，其算法的时间复杂度为＿＿＿＿＿＿＿＿。
A BC DB、顺序存取C、逻辑相邻的元素物理位置也相邻D、元素的物理位置可以相邻也可以不相邻2、单链表的特点是＿＿＿＿＿＿＿＿。
A、随机存取B、顺序存取C、逻辑相邻的元素物理位置也相邻D、元素的物理位置可以相邻也可以不相邻3、在双向循环链表（L为头指针）中，指针p所指结点为尾结点的条件是＿＿＿＿＿＿＿＿。
A、p＝＝LB、p->next＝＝LC、L->prior＝＝pD、L->next＝＝p4、一元多项式中非零项的系数指数对所成的线性表可用＿＿＿＿＿＿＿＿来表示。
A、顺序结构B、链式结构C、逻辑结构D、索引结构5、在双向循环链表中，若要在指针q所指结点的后面插入一个s所指结点，则须执行下列语句：s->prio r＝q;s->next＝q->next; ＿＿＿＿＿＿＿;q->next＝s;A、q->next->prior＝sB、s＝qC、s->next->prior＝sD、s->prior->next＝q第三题、判断题（每题1分，5道题共5分）正确错误、整个单链表的存取必须从头指针开始沿链表进行，因此单链表中的元素是可以进行随机存取的。
正确错误、一元多项式的链式存储结构优于顺序存储结构。
（）正确错误在双向循环链表中插入或删除元素时仅需要修改结点的指针，正确错误、用线性链表表示一元多项式时，其有序性是指链表中的结点按此项的系数由小到大有序排列。
正确错误A BC D若在线性表的任何位置上删除元素的概率是相等的，那么在长度为A BC D个元素的单链表中插入或删除一个元素的算法的时间复杂度为＿＿＿＿＿＿＿＿。
A BC D个元素的单链表，其算法的时间复杂度为＿＿＿＿＿＿＿＿。
A BC D个元素的有序单链表，其算法的时间复杂度为＿＿＿＿＿＿＿＿。
A BC、O(n*n)D、O(n*n*n)第二题、多项选择题（每题2分，5道题共10分）1、在双向循环链表中，若s是指向表中某结点的指针，则＿＿＿＿＿＿＿＿。
A、s->next＝＝sB、s->next->prior＝＝sC、s->prior->next ＝＝sD、s-> prior＝＝s2、顺序表的特点是＿＿＿＿＿＿＿＿。
A、随机存取B、顺序存取C、逻辑相邻的元素物理位置也相邻D、元素的物理位置可以相邻也可以不相邻3、单链表是用一组任意的存储单元来存储线性表的元素，这些存储单元之间＿＿＿＿＿＿＿＿。
A、必须不连续B、可以是连续的C、必须连续D、可以是不连续的4、在线性表的下列存储结构中，读取元素花费时间相同的是＿＿＿＿＿＿＿＿。
A、顺序表B、单链表C、循环链表D、双向链表5、在双向循环链表中，我们通常可设置＿＿＿＿＿＿＿＿来表示整个链表。
A、头指针B、尾指针正确错误、一元多项式的链式存储结构优于顺序存储结构。
（）正确错误在双向循环链表中插入或删除元素时仅需要修改结点的指针，正确错误、在循环链表中设尾指针比设头指针方便。
正确错误、用线性链表表示一元多项式时，其有序性是指链表中的结点按此项的系数由小到大有序排列。
正确错误第三章1、在顺序栈中，base、top分别为栈底、栈顶指针，则＿＿＿＿＿＿＿时表明栈空。
A、base＝＝NULLB、top＝＝ NULLC、base＝＝topD、2、非空顺序栈中的栈顶指针始终指向栈顶元素的＿＿＿＿＿＿＿位置上。
A、上一个B、当前C、下一个D、3、将递归算法转换成对应的非递归算法时，通常使用＿＿＿＿＿＿＿保存中间结果。
A、栈B、队列C、图D、树4、非空循环队列中的队尾指针始终指向队尾元素的＿＿＿＿＿＿＿位置上。
A、上一个B、当前C、下一个D、5、在循环队列中，设队列元素依次存放在Q[0..m]中，f、r分别指示队头元素位置和队尾元素的下一个位置，则队列空的判定方法是＿＿＿＿＿＿＿。
A、f＝＝rB、(f+1) ％ (m+1)＝＝rC、(r+1) ％ (m+1)＝＝fD、(r+1) ％ m＝＝f第二题、多项选择题（每题2分，5道题共10分）1、循环队列中，设队列元素依次存放在Q[0..m]中，f、r分别指示队头元素位置和队尾元素的下一个位置，此时队空、队满的判断条件都是f＝＝r,为解决此矛盾，通常可采用＿＿＿＿＿＿＿。
A、另设一个标志位来辅助判断队空还是队满B、牺牲一个元素空间，以Q中存放m个元素时认为队列满C、无法解决此矛盾，改用链队列表示2、一个栈的入栈序列是{1,2,3,4,5},则栈的不可能的输出序列是＿＿＿＿＿＿＿。
A、54321B、12345C、45231D、32514E、143253、一个队列的入队序列是{1,2,3,4},则队列不可能的输出序列是＿＿＿＿＿＿＿。
A、4321B、1234C、1432D、32414、下列叙述中，错误的是＿＿＿＿＿＿＿。
A、栈是一种FIFO的数据结构。
B、队列是一种LIFO的数据结构。
C、编程时，栈可以用静态或动态的数据类型实现。
D、编程时，队列可以用静态或动态的数据类型实现。
5、在链队列中，若插入一个元素，则＿＿＿＿＿＿＿。
正确错误、栈的一个重要应用是在程序设计语言中实现递归。
（正确错误、队列只能有一种输出序列，即队列中的元素只能按照进入队列的顺序依次出队。
（正确错误、在实际应用中，双端队列比栈和队列应用更广泛。
（正确错误、在循环队列中，设队列元素依次存放在中，f、正确错误第四章A BC D、空串是＿＿＿＿＿＿＿＿。
A BC D、空格串的长度为＿＿＿＿＿＿＿＿。
A BC D＝’I am a student.的长度为＿＿＿＿＿＿＿＿。
A、11B、12C、15D、165、设串s＝’student.’,t＝’good ’,则执行Strinserｔ(s,1,t)后，s为＿＿＿＿＿＿＿＿。
A、’good student.’B、’good student’C、’goodstudent’D、’ good teacher’第二题、多项选择题（每题2分，5道题共10分）1、两个串相等的充分必要条件是＿＿＿＿＿＿＿＿＿＿。
A、串长相等且各对应位置字符相等B、所含字符集合相同C、所含字符个数相同D、串值相等2、串用定长顺序存储方式表示时，有可能发生"截断"的操作有＿＿＿＿＿＿＿＿＿＿。
A、串连接B、求子串C、串替换D、插入串E、删除子串3、以下关于块链结构的说法正确的是＿＿＿＿＿＿＿＿＿＿。
A、结点大小小，则存储密度小B、结点大小小，则存储密度大C、结点大小小，则占用存储空间多D、结点大小小，则占用存储空间少4、文本编辑程序中要设立＿＿＿＿＿＿＿＿＿＿来指示当前操作的字符位置。
A、页指针B、行指针正确错误、串也有两种存储结构：顺序结构和链式结构。
）正确错误、串的链式结构优于其顺序存储结构。
正确错误、在串的块链存储结构中，设尾指针的目的是为了便于进行联结操作。
正确错误语言中，用动态分配函数进行管理的自由存储区称为正确错误第六章A BC D、在一个有向图中，所有顶点的入度之和等于所有边数的＿＿＿＿＿＿＿＿倍。
A BC、2D、43、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的＿＿＿＿＿＿＿＿倍。
A、1/2B、1C、2D、44、邻接表是图的一种＿＿＿＿＿＿＿＿。
A、顺序存储结构B、链式存储结构C、索引存储结构D、散列存储结构5、对一个以邻接表为存储结构、有n个顶点e条边的无向连通图，深度优先遍历图的时间复杂度是＿＿＿＿＿＿＿＿。
A、O(n)B、O(n*n)C、O(n+e)D、O(n*e)第二题、多项选择题（每题2分，5道题共10分）1、判断一个有向图是否存在回路，可以用＿＿＿＿＿＿＿＿。
A、深度优先遍历算法B、广度优先遍历算法C、拓扑排序方法D、求最短路径方法2、下列说法中正确的有＿＿＿＿＿＿＿＿。
A、图的遍历过程中每个顶点仅被访问一次B、图的深度优先遍历算法不适用于有向图C、图的深度优先遍历过程是一个递归过程D、遍历图的基本方法有深度优先遍历和广度优先遍历3、任何一个无向连通图的最小生成树＿＿＿＿＿＿＿＿。
A、只有一棵B、可能有多棵C、可能不存在D、可能有一棵4、在拓扑排序中，拓扑序列的第一个顶点一定是＿＿＿＿＿＿＿＿的顶点。
A、入度为0B、没有前驱C、出度为0D、没有后继5、有向图的拓扑有序序列＿＿＿＿＿＿＿＿。
A、可能存在B、一定存在C、可能有多个D、肯定有多个第三题、判断题（每题1分，5道题共5分）1、图结构中，每个结点的前驱结点数和后续结点数都可以有任意多个。
（）正确错误2、在n个顶点的无向图中，若边数大于n-1，则该图一定是连通图。
（）正确错误3、只要能提高关键活动的速度，就能缩短整个工程的工期。
（）正确错误4、从某顶点开始对有向图进行深度优先遍历，若所得的遍历序列唯一，则可断定其弧数为n-1（n为图中顶点数）。
（）正确错误5、若有向图的拓扑排序序列唯一，则图中必定仅有一个顶点的入度为0，一个顶点的出度为0。
（）正确错误第七A、10B、25C、6D、6252、有一个有序表{1，3，9，12，32，41，45，62，75，77，82，95，100}中折半查找值为82的结点时，＿＿＿＿＿＿＿次比较后查找成功。
