下载文档原格式
数据结构考试题及答案一、选择题（每题2分，共20分）1. 以下哪个不是线性数据结构？A. 数组B. 链表C. 树D. 图2. 在一个单链表中，删除一个节点的操作需要知道该节点的：A. 地址B. 值C. 索引D. 前驱节点的引用3. 栈（Stack）是一种：A. 线性表B. 树状结构C. 图结构D. 散列表4. 哈希表解决冲突最常用的方法是：A. 排序B. 链地址法C. 再散列D. 除留余数法5. 以下哪个排序算法是稳定的？A. 快速排序B. 冒泡排序C. 选择排序D. 堆排序二、简答题（每题10分，共30分）1. 简述数组和链表的区别。
2. 解释二叉搜索树的基本概念及其优势。
3. 什么是递归？请给出一个简单的递归算法例子。
三、计算题（每题25分，共50分）1. 给定一个无序数组，请写出一个时间复杂度为O(n log n)的排序算法，并说明其工作原理。
2. 描述如何使用队列来实现一个简单的文本编辑器的撤销和重做功能。
四、编程题（共30分）编写一个函数，该函数接受一个整数数组作为参数，返回数组中所有元素的和。
如果数组为空，返回0。
答案一、选择题1. 答案：C（树和图都是非线性结构）2. 答案：D（需要前驱节点的引用来删除节点）3. 答案：A（栈是一种后进先出的特殊线性表）4. 答案：B（链地址法是解决哈希冲突的常用方法）5. 答案：B（冒泡排序是稳定的排序算法）二、简答题1. 数组和链表的区别：- 数组是连续的内存空间，链表是非连续的。
- 数组的索引访问速度快，链表需要遍历。
- 数组的大小固定，链表动态可变。
2. 二叉搜索树的基本概念及其优势：- 二叉搜索树是一种特殊的二叉树，左子树上所有节点的值小于它的根节点的值，右子树上所有节点的值大于它的根节点的值。
- 优势：支持快速的查找、插入和删除操作。
3. 递归是函数自己调用自己的过程。
例如，计算n的阶乘的递归算法： ```cint factorial(int n) {if (n <= 1) return 1;return n * factorial(n - 1);}```三、计算题1. 快速排序算法：- 选择一个元素作为“基准”（pivot）。
数据结构试题及答案⼀、选择题（共10题，每题1分，共10分）1．下⾯关于线性表的叙述中，错误的是哪⼀个？（）A．线性表采⽤顺序存储，必须占⽤⼀⽚连续的存储单元B．线性表采⽤顺序存储，便于进⾏插⼊和删除操作C．线性表采⽤链接存储，不必占⽤⼀⽚连续的存储单元D．线性表采⽤链接存储，便于插⼊和删除操作2．在⼀个单链表中，已知q所指结点是p所指结点的前驱，若在p和q之间插⼊s所指结点，则执⾏的操作是（）。
A. s->next=p->next;p->next=s;B. q->next=s;s->next=p;C. p->next=s->next;s->next=p;D. p->next=s;s->next=q;3．设有三个元素X，Y，Z顺序进栈，下列得不到的出栈排列是( )。
A．XYZ B. YZX C. ZXY D. ZYX4．若⽤⼀个长度为6的数组来实现循环队列，且当前rear和front的值分别为0和3，则从队列中删除⼀个元素，再增加两个元素后，rear和front的值分别是( )。
A．1和5 B．2和4 C．4和2 D. 5和15．下列说法中正确的是（）。
A．⼆叉树就是度为2的树 B．⼆叉树中不存在度⼤于2的结点C．⼆叉树中⾄少有⼀个结点的度为2 D．⼆叉树中任何⼀个结点的度都为2 6．在具有n个结点的⼆叉链表中，共有（）个空指针。
A. nB. n-1C. n+1D. 不确定7．根据⼆叉树与树的转换关系可知，深度为h的满⼆叉树对应的森林由（）棵树构成。
A．1 B．log2n C. h/2 D. h8．在⼀个⽆向图中，所有顶点的度数之和等于所有边数的（）倍。
A．1/2 B．1 C. 2 D. 49．对17个元素的查找表做折半查找，则查找长度为5的元素下标依次是（）。
A．8,17 Ｂ．5,10,12 C．9,16 D．9,1710．关于排序，下列说法中正确的是（）。
一、单选题（每题 2 分，共20分）1. 1.对一个算法的评价，不包括如下（B ）方面的内容。
A．健壮性和可读性B．并行性C．正确性D．时空复杂度2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行(A )。
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.对线性表，在下列哪种情况下应当采用链表表示？( B )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35. 5.AOV网是一种（ D ）。
A．有向图B．无向图C．无向无环图D．有向无环图6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（B ）。
A．低于链接法处理冲突 B. 高于链接法处理冲突C．与链接法处理冲突相同D．高于二分查找7.7.若需要利用形参直接访问实参时，应将形参变量说明为（D ）参数。
A．值B．函数C．指针D．引用8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（A ）。
A．行号B．列号C．元素值D．非零元素个数9.9.快速排序在最坏情况下的时间复杂度为（D ）。
A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。
A. O(n)B. O(1)C. O(log2n)D. O(n2)二、二、运算题（每题 6 分，共24分）1. 1.数据结构是指数据及其相互之间的______联系______。
数据结构考试试题题库一、选择题1. 在数据结构中，线性表是按照什么顺序存储数据的？A. 随机B. 无序C. 有序D. 连续2. 栈（Stack）是一种遵循哪种原则的数据结构？A. 先进先出（FIFO）B. 先进后出（LIFO）C. 后进先出（LILO）D. 随机访问3. 哈希表（Hash Table）的主要优点是什么？A. 存储空间大B. 访问速度快C. 易于排序D. 易于扩展二、简答题1. 请简述数组和链表的区别。
2. 什么是二叉树？请描述二叉树的几种遍历方法。
三、计算题1. 给定一个单链表，编写一个算法来删除链表中的重复元素。
2. 假设有一个数组，其中包含n个元素，编写一个算法来找到数组中的第k小的元素。
四、应用题1. 描述如何使用队列来实现一个打印任务调度系统。
2. 请解释二叉搜索树（BST）的插入操作，并给出相应的算法实现。
五、编程题1. 编写一个C++函数，实现对一个给定的整数数组进行排序。
2. 编写一个Python函数，实现对一个二叉树进行层次遍历。
六、论述题1. 讨论图的两种存储结构：邻接矩阵和邻接表，并比较它们的优缺点。
2. 解释什么是递归，并给出一个使用递归解决实际问题的例子。
结束语数据结构的学习不仅仅是对概念的理解，更重要的是能够将这些概念应用到实际问题的解决中。
通过本题库的练习，希望能够加深你对数据结构的理解和应用能力。
请注意，这只是一个示例题库，实际的考试题库可能会包含更多的题目和不同的题型。
考生应根据具体的课程内容和考试要求来准备。
数据结构考试试题一、选择题（每题2分，共20分）1. 在数据结构中，队列是一种______。
A. 线性结构B. 非线性结构C. 树形结构D. 图结构2. 对于长度为n的线性表，在顺序存储结构中，从第i个元素（1≤i≤n）开始，连续做m（1≤m≤n-i+1）个元素的删除操作，需要进行的移动元素次数为______。
A. mB. n-mC. i+m-1D. m+n-m-13. 在二叉树的遍历中，先序遍历的顺序是______。
A. 根左右B. 左右根C. 左根右D. 左右根4. 哈希表的冲突可以通过多种方式解决，其中不是解决冲突的方法是______。
A. 开放寻址法B. 链地址法C. 建立一个公共溢出区D. 二分查找法5. 排序算法中，时间复杂度为O(nlogn)的算法是______。
A. 选择排序B. 冒泡排序C. 快速排序D. 插入排序6. 在图的遍历中，深度优先搜索（DFS）使用的是______。
A. 栈B. 队列C. 哈希表D. 数组7. 堆排序算法中，将堆中的最后一个元素和第一个元素交换，然后重新调整堆的过程称为______。
A. 堆调整B. 堆缩小C. 堆替换D. 堆重建8. 一个长度为n的链表，删除已知第k个元素的时间复杂度是______。
A. O(1)B. O(n)C. O(k)D. O(nk)9. 字符串“Knuth”在一棵二叉查找树中，按照K->n->u->t->h的顺序插入后，使用中序遍历得到的结果是______。
A. hKnuctB. hnKutC. hKnutD. hnuct10. 对于长度为n的数组，如果使用归并排序算法进行排序，其时间复杂度为______。
A. O(n)B. O(n^2)C. O(nlogn)D. O(logn)二、简答题（每题5分，共30分）11. 请简述什么是时间复杂度，并给出最好、最坏和平均时间复杂度的定义。
12. 解释一下什么是平衡二叉树，并说明它在数据结构中的重要性。
数据结构考试题及答案一、选择题1. 下列哪个不属于线性数据结构？A. 栈B. 队列C. 数组D. 链表答案：C2. 在单链表中，删除一个节点的时间复杂度是多少？A. O(1)B. O(n)C. O(logn)D. O(nlogn)答案：A3. 以下哪种数据结构的插入和删除操作都具有O(logn)的时间复杂度？A. 树B. 堆C. 栈D. 队列答案：B二、填空题1. 栈是一种__________（后进先出）的数据结构。
答案：后进先出2. 在链表中，头节点的前驱指针指向__________。
答案：空指针或者NULL3. 哈希表中冲突解决的方法有__________和开放地址法。
答案：链地址法三、简答题1. 请简述树与图的区别。
答案：树是一种特殊的图，它们的主要区别在于图中任意两个节点之间都可能存在边，而树中任意两个节点之间只有一条路径。
此外，树是无环图，而图可以有环。
2. 请解释栈的应用场景，并举例说明。
答案：栈常用于函数调用和表达式求值等场景。
例如，在编程中，当一个函数被调用时，相关的信息会被压入栈中，执行完毕后再弹出。
另外，栈还可以用于实现撤销操作，在文本编辑器中，当我们进行一系列操作后，可以将每一步的操作记录在栈中，需要撤销时，只需要依次弹出栈顶元素即可。
四、编程题请使用C语言实现一个栈的数据结构，并实现栈的基本操作（入栈、出栈、判空、获取栈顶元素等）。
答案略。
结语本文包含了数据结构考试题及答案，从选择题到填空题再到简答题和编程题，涵盖了数据结构的各个方面。
希望能对你的学习和复习有所帮助。
数据结构是计算机科学的基础，掌握好数据结构对于编程能力的提升至关重要。
加油！。
数据结构考试题⽬数据结构49道题1. 数据结构是⼀门研究什么内容的学科？2. 数据元素之间的关系在计算机中有⼏种表⽰⽅法？各有什么特点？3. 数据类型和抽象数据类型是如何定义的。
⼆者有何相同和不同之处，抽象数据类型的主要特点是什么？使⽤抽象数据类型的主要好处是什么？5．评价⼀个好的算法，您是从哪⼏⽅⾯来考虑的？8．对于⼀个数据结构，⼀般包括哪三个⽅⾯的讨论？9. 当你为解决某⼀问题⽽选择数据结构时，应从哪些⽅⾯考虑？11．数据结构与数据类型有什么区别？15. 在编制管理通讯录的程序时, 什么样的数据结构合适? 为什么?18．设计⼀数据结构，⽤来表⽰某⼀银⾏储户的基本信息：账号、姓名、开户年⽉⽇、储蓄类型、存⼊累加数、利息、帐⾯总数。
19. 请在下列算法的横线上填⼊适当的语句。
FUNCTION inclusion(ha,hb:linklisttp):boolean;{以ha 和hb 为头指针的单链表分别表⽰有序表A 和B，本算法判别表A 是否包含在表B 内，若是，则返回“true”，否则返回“false”}BEGINpa:=ha^.next; pb:=hb^.next; （1） ;WHILE（2） DOIF pa^.data=pb^.data THEN（3） ELSE（4） ;（5）END;20．完善算法：已知单链表结点类型为：TYPE ptr=^node；node=RECORDdata：integer； next：ptrEND；过程create 建⽴以head 为头指针的单链表。
PROCEDURE create ( (1) )；VAR p,q：ptr； k：integer；BEGINnew（head）； q:=head；read（k）；WHILE k>0 DOBEGIN(2); (3); (4); (5);read（k）END;q^.next：=NIL;END;22．假设链表p 和链表q 中的结点值都是整数,且按结点值的递增次序链接起来的带表头结点的环形链表。
数据结构考试题及答案一、选择题1. 以下哪种数据结构在实现栈时最为高效？A. 链表B. 数组C. 树D. 图答案：B2. 快速排序算法的时间复杂度在最坏情况下是多少？A. O(n)B. O(nlogn)C. O(n^2)D. O(n^3)答案：C3. 在二叉搜索树中，若要查找给定值的节点，应该按照以下哪种方式进行？A. 从根节点开始，向左或向右子树交替进行B. 从根节点开始，始终向左子树进行C. 从根节点开始，始终向右子树进行D. 从最底层节点开始向上进行答案：A4. 哈希表的主要优点是什么？A. 有序存储数据B. 高效的查找、插入和删除操作C. 动态扩容D. 消耗内存小答案：B5. 下面哪种数据结构通常用于实现高效的多对一映射？A. 数组B. 链表C. 哈希表D. 树答案：C二、填空题1. 在平衡树中，AVL树通过_________来保持树的平衡。
答案：旋转2. 堆数据结构通常用来实现_________等优先队列。
答案：最大/最小3. 拓扑排序是针对有向无环图(DAG)的一种排序算法，它能够反映出任务间的_________关系。
答案：依赖4. 广度优先搜索(BFS)算法使用_________数据结构来实现。
答案：队列5. 斐波那契数列可以通过递归算法、动态规划以及_________等方法来计算。
答案：矩阵快速幂三、简答题1. 请简述链表和数组的区别及各自的优缺点。
答案：链表由一系列节点组成，每个节点包含数据和指向下一个节点的指针。
它的优点是能够在常数时间内在任意位置插入或删除元素，但随机访问效率较低。
数组是一段连续的内存空间，可以存储一系列相同类型的元素。
它的优点是支持高效的随机访问，但插入和删除操作通常需要移动大量元素，且大小固定或调整大小成本较高。
2. 描述二分查找的工作原理及其适用条件。
答案：二分查找是一种在有序数组中查找特定元素的算法。
它的工作原理是将数组分为两半，比较中间元素与目标值，如果相等则查找结束；如果目标值较小，则在左半部分继续查找；如果目标值较大，则在右半部分继续查找。
数据结构考试试题题库一、选择题1. 在数据结构中，栈（Stack）是一种特殊的线性表，其特点是：A. 允许在表的任意位置插入和删除元素B. 只能在表的一端进行插入和删除操作C. 只能在表的两端进行插入和删除操作D. 只能在表的中间进行插入和删除操作答案：B2. 假设有一个单链表，头结点的指针域为head，链表中每个结点包含一个数据域data和指向下一个结点的指针域next。
若要删除指针p所指向的结点，以下哪个操作是正确的？A. p = p->nextB. p->next = p->next->nextC. p = p->next->nextD. p = NULL答案：B3. 在二叉树的遍历算法中，先序遍历的顺序是：A. 先访问根节点，然后遍历左子树，最后遍历右子树B. 先遍历左子树，然后访问根节点，最后遍历右子树C. 先遍历右子树，然后访问根节点，最后遍历左子树D. 同时遍历左子树和右子树答案：A4. 哈希表的冲突可以通过多种方式解决，以下哪种不是解决哈希表冲突的方法？A. 链地址法B. 开放地址法C. 再哈希法D. 排序法答案：D5. 快速排序算法的时间复杂度在最好、最坏和平均情况下分别是：A. O(n log n), O(n^2), O(n)B. O(n), O(n log n), O(n^2)C. O(n log n), O(n), O(n log n)D. O(n^2), O(n log n), O(n)答案：A二、简答题1. 请简述什么是图，并说明图的两种基本表示方法。
答案：图是一种数据结构，由顶点（或称为节点）和边组成。
图可以表示为有向图或无向图。
图的两种基本表示方法为邻接矩阵和邻接表。
邻接矩阵是一个二维数组，其元素表示顶点之间的连接关系；邻接表则使用链表存储每个顶点的邻接点。
2. 什么是二叉搜索树（BST）？请简述其特点。
答案：二叉搜索树是一种特殊的二叉树，其中每个节点的值都大于或等于其左子树中所有节点的值，并且小于或等于其右子树中所有节点的值。
一、单项选择1.数据结构是一门研究非数值计算的程序设计问题中,数据元素的①C 、数据信息在计算机中的② A 以及一组相关的运算等的课程。
①A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象②A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法2.以下数据结构中, D 是线性结构。
A．广义表Ｂ．二叉树Ｃ．稀疏矩阵Ｄ．串3.从逻辑上可以把数据结构分为 C 两大类。
A．动态结构和静态结构Ｂ．顺序结构和链式结构Ｃ．线性结构和非线性结构Ｄ．初等结构和构造型结构4.以下数据结构中, D 是线性结构。
A．广义表Ｂ．二叉树Ｃ．稀疏矩阵Ｄ．串5.以下数据结构中, D 是非线性结构。
A．栈Ｂ．二叉树Ｃ．队列Ｄ．字符串6.数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是① B 的有限集合，R是D上的② D 有限集合。
①A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象②A．操作Ｂ．映象Ｃ．存储Ｄ．关系7.线性表的顺序存储结构是一种① A 的存储结构, 线性表的链式存储结构是一种的② B 存储结构。
A．随机存取Ｂ．顺序存取Ｃ．索引存取Ｄ．散列存取.8.线性表的逻辑顺序与存储顺序总是一致的，这种说法__B _。
A. 正确B. 不正确9.下面那一条是顺序存储结构的优点? (A)A . 存储密度大 B. 插入运算方便 C. 删除运算方便D. 可以方便的用于各种逻辑结构的存储表示10.线性表采用链式存储结构时, 要求内存中可用的存储单元的地址.A . 必须是连续的 B. 部分地址必须是连续的 C. 一定不连续D. 连续和不连续都可以11.表长为n的顺序存储的线性表, 当在任何位置上插入和删除一个元素的概率相等时, 插入一个元素所需要移动元素的平均次数为E , 删除一个元素所需要移动元素的平均次数为 AA. (n-1)/2B.nC. n+1D. n-1E. n/2F. (n+1)/2G. (n-2)/212.带头结点的单链表head为空的判定条件是_B___。
A. head= =NULLB. head->next= =NULLC. head->next= =headD. head!=NULL13.在一个单链表中, 若删除p所指向结点的后继结点, 则执行_A___。
A. p->next= p->next->nextB. p=p->next; p->next= p->next->nextC. p= p->next->nextD. p= p->next14.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为_C___。
A. iB. n=iC. n-i+1D. 不确定.15.设栈的输入次序为: 1 , 2, 3, 4, 5, 则不可能是其出栈序列.A. 54321B. 45321C. 43512D. 1234516.一个递归算法必须包括 BA. 递归部分B. 终止条件和递归部分C. 迭代部分D. 终止条件和迭代部分17.用链接方式存储的队列, 在进行删除操作时 DA 仅修改头指针 B. 仅修改尾指针C. 头尾指针都要修改D. 头尾指针可能都要修改18.数组A[m]存放循环队列的元素, 其头尾指针分别是front和rear, 则当前队列的元素个数是__A__。
A. (rear-front+m)%mB. (front-rear+m)%mC. front-rear+1D. rear-front+119.栈和队列的共同特点__C__。
A. 都是先进先出B. 都是先进后出C. 允许在端点插入和删除元素D. 没有共同点20.一个栈的入栈序列a，b，c，d，e，则栈的输出序列是__A__。
A. edcbaB. decbaC. dceabD. abcde21.栈的特点是__B__，队列的特点是__A__。
A. 先进先出B. 先进后出22.从一个栈顶指针HS的链表中删除一个结点, 用x保存被删除的结点值,执行的语句为__C__。
A. x=HS; HS=HS->nextB. HS=HS->next; x=HS->data.C. x=HS->data; HS=HS->nextD. HS->next=HS; x=HS->data23.在链队列Q中, 插入s所指向的结点执行的语句为__C__。
A. Q.front->next=s;B. Q.rear->next=s; Q.rear=sC. s->next=Q.rear;Q.rear=sD. s->next=Q.front;Q.front=s24.空串与空格串是相同的，这种说法__B__。
A. 正确B. 不正确25.下面关于串的叙述, 哪一个是不正确的__B__。
A. 串是字符的有限序列B. 空串是由空格构成的串C. 匹配模式是串的一种重要运算D. 串可以采用链式存储结构26.设有两个串p和q，求q在p中首次出现的位置的运算称作__B__。
A. 连接B. 模式匹配C. 求子串D. 求串长27.若串s='software', 其子串的数目为 BA. 8B. 37C. 36D. 928.二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A[7][4]的起始地址为__C__。
A. SA+141B. SA+144C. SA+222D. SA+22529.对稀疏矩阵进行压缩存储的目的是__C__.A. 便于进行矩阵运算B. 便于输入输出.C 节省存储空间 D. 降低运算的时间复杂度30.在以下叙述中正确的是 BA.线性表的线性存储结构优于链表存储结构B.二维数组可以看成是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出31.广义表((a),a)的表头为 C , 表尾为 C .A. ()B. aC. (a)D. ((a))32.已知广义表L=((x,y,z),a,(u,t,w)), 从L中取出原子项t的运算为__D__。
A. Head(Tail(Tail(L)))B. Tail(Head(Head(Tail(L))))C. Head(Tail(Head(Tail(L))))D. Head(Tail(Head(Tail(Tail(L)))))33.树最适合用来表示 BA. 有序的数据元素B. 数据之间具有分支层次关系的数据C. 无序的数据元素D. 无太多关系的数据元素34.如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为__B__。
A. uwvtsB. vwutsC. wuvtsD. wutsv35.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是__D__。
A. bdgcefhaB. gdbecfhaC. bdgaechfD. gdbehfca36.在一非空二叉树的中序遍历序列中，根结点的右边__A__。
.A. 只有右子树上的所有结点B. 只有右子树上的部分结点C. 只有左子树上的部分结点D. 只有左子树上的所有结点37.设m和n是一棵二叉树上的两个结点, 在中序遍历, n在m前的条件是CA. n在m的右方B. n是m的祖先C. n在m的左方D. n是m的子孙38.深度为5的二叉树至多有__C__个结点。
A. 16B. 32C. 31D. 1039.由权(8,2,5,7)的四个叶子结点构造一棵哈夫曼树, 该树的带权路径长度为DA. 23B. 37C. 46D. 4340.利用二叉链表存储树, 则根结点的右指针是 CA. 指向最左孩子B. 指向最右孩子C. 空D. 非空41.下列存储方式中, 哪一个不是树的存储形式? DA. 双亲表示法B. 孩子链表表示法C. 孩子兄弟表示法D. 顺序存储表示法42.在一个无向图中，所有顶点的度数之和等于所有边数的__C__倍。
A. 1/2B. 1C. 2D. 443.具有n个顶点和多于n-1条边的无向图 B .A. 有可能是树B. 一定不是树C. 一定是树D. 以上答案都不对44.具有6个顶点的无向图至少应有__A__条边才能确保是一个连通图。
.A. 5B. 6C. 7D. 845.无向图G=(V,E), 其中: V={a,b,c,d,e,f}, E={(a,b),(a,e),(a,c), (b,e),(c,f),(f,d),(e,d)}, 则对该图进行深度优先遍历, 得到的序列为: DA. abecdfB. acfebdC. aebcfdD. aedfcb46.下述几种排序方法中，要求内存量最大的是__D__。
A. 插入排序B. 选择排序C. 快速排序D. 归并排序47.排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为__C__。
A. 希尔排序B. 起泡排序C. 插入排序D. 选择排序48.在待排序的元素序列基本有序的前提下，效率最高的排序方法是__A_。
A.插入排序B. 选择排序C. 快速排序D. 归并排序49.下列排序算法中, 哪一个是稳定的排序算法? BA. 直接选择排序B. 二分法插入排序C. 希尔排序D. 快速排序50.将两个各有n个元素的有序表归并成一个有序表, 其最少的比较次数 AA. nB. 2n-1C. 2nD. n-1二、填空题1.算法的五个重要特性是有穷性,确定性,可行性,输入和输出.2.数据的树型结构和图(网)状结构合称非线性结构.3.抽象数据类型的定义仅取决于它的一组逻辑特性, 而与数据在计算机中的表示和实现无关.4.评价算法质量的指标是正确性,易读性,健壮性,高效性..5.数据结构中评价算法的两个重要指标是: 时间复杂度和空间复杂度.6.分析下面算法（程序段），的时间复杂度是__ O (mn) __。
s=0;for (i=0;i<n;i++)for (j=0;j<m;j++)s+=B[i][j];7.当线性表元素的总数基本稳定, 且很少进行删除和插入操作时, 但是要求以最快的速度存取线性表中的元素, 应该采取顺序存储结构.8.顺序表中逻辑上相邻的元素的物理位置必定相邻, 而单链表中逻辑上相邻的元素的物理位置不一定相邻.9.在各个结点查找概率相等的情况下, 从n个结点的单链表中查找一个结点, 平均要访问n/2 个结点.10.在单链表中设置头指针的作用是: 简化操作, 减少边界条件的判断.11.在单链表中, 除首元结点外, 任一结点的存储位置由其直接前驱的指针域指示.12.对于一个具有n个结点的单链表, 在已知p所指向结点后插入一个新结点的时间复杂度是O(1) , 在值域为给定值的结点后插入一个新结点的时间复杂度为O(n).13.在双链表中，每个结点有两个指针域，一个指向_前驱结点__，另一个指向__后继结点_ __。
