数据结构考试题
- 格式:doc
- 大小:110.50 KB
- 文档页数:20
数据结构考试题及答案一、选择题(每题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 B.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.操作对象B.计算方法C.逻辑结构D.数据映象②A.存储结构B.关系C.运算D.算法2.以下数据结构中, D 是线性结构。
A.广义表B.二叉树C.稀疏矩阵D.串3.从逻辑上可以把数据结构分为 C 两大类。
A.动态结构和静态结构B.顺序结构和链式结构C.线性结构和非线性结构D.初等结构和构造型结构4.以下数据结构中, D 是线性结构。
A.广义表B.二叉树C.稀疏矩阵D.串5.以下数据结构中, D 是非线性结构。
A.栈B.二叉树C.队列D.字符串6.数据结构DS(Data Struct)可以被形式地定义为DS=(D,R),其中D是① B 的有限集合,R是D上的② D 有限集合。
①A.算法B.数据元素C.数据操作D.数据对象②A.操作B.映象C.存储D.关系7.线性表的顺序存储结构是一种① A 的存储结构, 线性表的链式存储结构是一种的② B 存储结构。
A.随机存取B.顺序存取C.索引存取D.散列存取.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.在双链表中,每个结点有两个指针域,一个指向_前驱结点__,另一个指向__后继结点_ __。