数据结构II A卷 东北大学(答案)

《数据结构》课后习题答案(第2版)数据结构课后习题答案（第2版）第一章：基本概念1. 什么是数据结构？数据结构是指数据元素之间的关系，以及相应的操作。

它研究如何组织、存储和管理数据，以及如何进行高效的数据操作。

2. 数据结构的分类有哪些？数据结构可以分为线性结构和非线性结构。

线性结构包括数组、链表、栈和队列；非线性结构包括树和图。

3. 什么是算法？算法是解决特定问题的一系列有序步骤。

它描述了如何输入数据、处理数据，并产生期望的输出结果。

4. 算法的特性有哪些？算法具有确定性、有限性、输入、输出和可行性这五个特性。

5. 数据结构和算法之间的关系是什么？数据结构是算法的基础，算法操作的对象是数据结构。

第二章：线性表1. 顺序表的两种实现方式是什么？顺序表可以通过静态分配或动态分配的方式实现。

静态分配使用数组，动态分配使用指针和动态内存分配。

2. 单链表的特点是什么？单链表由节点组成，每个节点包含数据和一个指向下一个节点的指针。

它的插入和删除操作效率高，但是查找效率较低。

3. 循环链表和双向链表分别是什么？循环链表是一种特殊的单链表，在尾节点的指针指向头节点。

双向链表每个节点都有一个指向前一个节点和后一个节点的指针。

4. 链表和顺序表的区别是什么？链表的插入和删除操作效率更高，但是查找操作效率较低；顺序表的插入和删除操作效率较低，但是查找操作效率较高。

第三章：栈和队列1. 栈是什么？栈是一种特殊的线性表，只能在表的一端进行插入和删除操作。

后进先出（LIFO）是栈的特点。

2. 队列是什么？队列是一种特殊的线性表，只能在表的一端进行插入操作，在另一端进行删除操作。

先进先出（FIFO）是队列的特点。

3. 栈和队列的应用有哪些？栈和队列在计算机科学中有广泛的应用，例如浏览器的前进后退功能使用了栈，操作系统的进程调度使用了队列。

4. 栈和队列有哪些实现方式？栈和队列可以使用数组或链表来实现，还有更为复杂的如双端队列和优先队列。

东北大学继续教育学院数据结构II 试卷（作业考核线上1） A 卷学习中心：院校学号：姓名（共 6 页）[A ]1．抽象数据类型的三个组成部分分别为A．数据对象、数据关系和基本操作B．数据元素、逻辑结构和存储结构C．数据项、数据元素和数据类型D．数据元素、数据结构和数据类型[B ]2．要求相同逻辑结构的数据元素具有相同的特性，其含义为A. 数据元素具有同一的特点B. 不仅数据元素包含的数据项的个数相同，而且其对应数据项的类型要一致C. 每个数据元素都一样D. 仅需要数据元素包含的数据项的个数相同[D ]3．下列各式中，按增长率由小至大的顺序正确排列的是A．，n！，2n ，n3/2B．n3/2，2n，n logn，2100C．2n，log n，n logn，n3/2D．2100，logn, 2n, n n[B ]4. 在下列哪种情况下，线性表应当采用链表表示为宜A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变[C ]5．设指针p指向双链表的某一结点，则双链表结构的对称性是A. p->prior->next=p->next->next;B. p->prior->prior=p->next->prior;C. p->prior->next=p-> next->prior;D. p->next->next= p->prior->prior;[ D]6. 已知指针p和q分别指向某带头结点的单链表中第一个结点和最后一个结点。

假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为A. s->next=q；p->next=s->next；B. s->next=p；q->next=s->next；C. p->next=s->next；s->next=q；D. q->next=s->next；s->next=p；[A ]7. 栈和队列的共同特点是A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点[D ]8. 对于链队列，在进行插入运算时.A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改[B ]9．设有一个顺序栈的入栈序列是1、2、3，则3个元素都出栈的不同排列个数为A．4 B．5 C. 6 D. 7[D ]10．设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是A．A，B，C，D B．D，C，B，AC. A，C，D，BD. D，A，B，C[C ]11．表达式a*(b+c)-d的后缀表达式是A．abcd*+- B．abc*+d- C．abc+*d- D．-+*abcd[B ]12．某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是A. 空或只有一个结点B.高度等于其结点数C. 任一结点无左孩子D.任一结点无右孩子[B ]13．下面的说法中正确的是(1)任何一棵二叉树的叶子结点在种遍历中的相对次序不变。

《数据结构》期终考查试卷（A 卷）适用专业：一、单项选择题（每题2分，共40分）1、．算法的时间复杂度是指( )A ．执行算法程序所需要的时间B ．算法程序的长度C ．算法执行过程中所需要的基本运算次数D ．算法程序中的指令条数2、以下说法正确的是A ．线性结构的数据元素之间存在一对多的线性关系B ．图形结构和树型结构是线性结构C ．时间复杂度是用算法执行过程中所需要的基本运算次数来度量D ．时间复杂度总是与空间复杂度成正比3、在一个单链表HL 中，若要删除由指针q 所指向结点的后继结点，则执行（ ）。

A ．p = q->next ; p->next = q->next;B ．p = q->next ; q->next = p;C ．q->next = q->next->next; q->next = q;D ． p = q->next ; q->next = p->next 4、下列叙述中正确的是( ) A ．线性表是线性结构 B. 栈与队列是非线性结构 C ．线性链表是非线性结构 D. 二叉树是线性结构 5、图的广度优先搜索类似于树的（ ）次序遍历。

A ．先根 B ．中根 C ．后根 D ．层次 6、下列存储形式中，（ ）不是树的存储形式。

A、双亲表示法B、左子女右兄弟表示法C、广义表表示法D、顺序表示法7、栈的插入和删除操作都在（）进行。

A、栈顶B、栈底C、任意位置D、指定位置8、按照“后进先出”原则组织数据的数据结构是A．队列B．栈C．双向链表D．二叉树9、假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为( )。

A．front==NULL B．front!=NULL C．rear!=NULL D．front= =rear10、关于字符串的说法中，错误的是A、字符串是零个或多个字符组成的有限序列B、串中字符的个数称为串的长度C、长度为零的串称为空串D、由空格组成的字符串称为空串11、有关二叉树的下列说法正确的是A、任何一棵二叉树中至少有一个结点的度为2B、一棵二叉树的度可以小于2C、二叉树中任何一个结点的度都为2D、二叉树的度为212、对如下二叉树进行后序遍历的结果为A．ABCDEF B．DBEAFC C．ABDECF D．DEBFCA13、求图的最小生成树采用的算法是A．普里姆算法和克鲁斯卡尔算法B．迪杰斯特拉算法C．弗洛伊德算法D．深度优先算法14、设G1=(V1,E1)和G2=(V2,E2)为两个图，如果V2包含V1，E2包含E1，则称( )。

东北大学考试试卷（A卷）2010—2011 学年第 2 学期课程名称：图论与代数结构┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄总分一二三四五六七八九学院班级学号姓名……………○……………密……………○……………封……………○…………线………………得分一．(15分) 填空1.设A={2, 4, 6, 8}，A上的二元运算*定义为：a*b=max{a, b}，则在独异点<A,*>中，单位元是 2 ，零元是8 。

2.设a是12阶群的生成元，则a2是 6 阶元素，a5是12 阶元素。

3.设〈G, *〉是一个群，G中的幂等元是 e 。

若G={a,b,c}，a*x=b，则x=a-1*b ；设a是幺元，则b*c= a 。

4.小于5个元素的格都是有补分配（布尔）格。

5.有n个结点的树，其结点度数之和是2(n-1)。

6.一个无向图有生成树的充分必要条件是该图是连通图__。

7.n阶无向完全图Kn 的边数是n(n-1)/2 ，每个结点的度数是n-1 。

若Kn为欧拉图，则n的取值为奇数。

8.具有6 个顶点，12条边的连通简单平面图中，每个面都是由 3 条边围成。

9.无向树T有8片树叶，2个3度分支结点，其余的分支结点都是4度顶点，则 2 个4度分支结点。

得分二． (26分)判断题4.（6分）判断下列集合和运算能否构成半群、独异点和群。

如果不能，简单说明理由。

（1）a是正整数，G={a n|n∈Z，Z为整数集}, 运算是普通乘法。

是半群、独异点和群。

（2分）（2）Q+是正有理数集，运算为普通加法。

（2分）是半群，不是独异点和群。

满足封闭、结合，但没有幺元。

（3）设Z为整数集，∀ x,y∈Z, 运算x*y=x+y-2。

是半群、群和独异点。

（2分）1.（6分）设V1=<Z,+>, V2=<Z, •>，其中Z为整数集合，+和•分别代表普通加法和乘法。

判断下述集合S能否构成V1和V2的子半群和子独异点。

东北大学“计算机科学与技术”《数据结构Ⅱ》23秋期末试题库含答案第1卷一.综合考核(共20题)1.对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用遍历方式是A.后序B.先序C.从根开始的层次遍历D.中序2.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是()。

A.栈B.队列C.树D.图3.4.树有先根遍历和后根遍历，树可以转化为对应的二叉树。

下面的说法正确的是A.树的后根遍历与其对应的二叉树的后根遍历相同B.树的后根遍历与其对应的二叉树的中根遍历相同C.树的先根遍历与其对应的二叉树的中根遍历相同D.以上都不对5.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为()。

A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA6.下列序列中，不构成堆的是()。

A.(1，2，5，3，4，6，7，8，9，10)B.(10，5，8，4，2，6，7，1，3)C.(10，9，8，7，3，5，4，6，2)D.(1，2，3，4，10，9，8，7，6，5)7.在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系()。

A.不一定相同B.都相同C.都不相同D.互为逆序8.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为A.n-i+1B.n-iC.i-1D.i9.下列陈述中正确的是A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中最多只有两棵子树，并且有左右之分D.二叉树中必有度为2的结点10.连通图是指图中任意两个顶点之间()。

A.都连通的无向图B.都不连通的无向图C.都连通的有向图D.都不连通的有向图11.判断两个串大小的基本准则是()。

A.两个串长度的大小B.两个串中首字符的大小C.两个串中大写字母的多少D.对应的第一个不等字符的大小12.若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的()。

东北大学智慧树知到“计算机科学与技术”《数据结构Ⅱ》网课测试题答案（图片大小可自由调整）第1卷一.综合考核(共15题)1.一个有向无环图的拓扑排序序列是()。

A.一定唯一的B.一定不唯一的C.不一定唯一的D.都不对2.在下列各种文件中，不能进行顺序查找的文件是()。

A.顺序文件B.索引文件C.散列文件D.多重表文件3.顺序存储设计时，存储单元的地址A.部分连续，部分不连续B.不一定连续C.一定连续D.一定不连续4.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则节省时间的存储方式是()。

A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表5.若要在O(1)的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向()。

A.各自的头结点B.各自的尾结点C.各自的第一个元素结点D.一个表的头结点，另一个表的尾结点6.栈是一种操作受限的线性结构，其操作的主要特征是()。

A.先进先出B.后进先出C.进优于出D.出优于进7.已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={,,,,,,,,},G的拓扑序列是已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={,,,,,,,,},G的拓扑序列是A.V1,V3,V4,V6,V2,V5,V7B.V1,V3,V4,V5,V2,V6,V7C.V1,V3,V2,V6,V4,V5,V7D.V1,V2,V5,V3,V4,V6,V78.在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为A.O(n+e)B.O(n3)C.O(n2)D.O(n)9.已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于()。

A.1.0B.2.9C.3.4D.5.510.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为A.DEFBCAB.DEBFCAC.DEBCFAD.DEBAFC11.按排序过程中依据的原则分类，快速排序属于A.选择类的排序方法B.插入类的排序方法C.归并类的排序方法D.交换类的排序方法12.下列说法正确的是：(1)二叉树按某种方式线索化后，任一节点均有指向前趋和后继的线索;(2)二叉树的前序遍历序列中，任意一个节点均处于在子孙节点前;(3)二叉排序树中任一节点的值大于其左孩子的值，小于右孩子的值。

一、单选题（共 20 道试题，共 100 分。

）1. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是A. 2，4，3，1，5，6B. 3，2，4，1，6，5C. 4，3，2，1，5，6D. 2，3，5，1，6，4正确答案：D2. 已知广义表LS=((a，b，c)，(d，e，f))，运算head和tail函数取出元素e的运算是A. head(tail(LS))B. tail(head(LS))C. head(tail(head(tail(LS))))D. head(tail(tail(head(LS))))正确答案：C3. 有关二叉树下列说法正确的是A. 二叉树的度为2B. 一棵二叉树的度可以小于2C. 二叉树中至少有一个结点的度为2D. 二叉树中任何一个结点的度都为2正确答案：B4. 假设以数组A[m]存放循环队列的元素。

已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为A. (rear-length+m+1)％mB. (rear-length+m)％mC. (rear-length+m-1)％mD. (rear-length)％m正确答案：B5. 若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为A. 4B. 5C. 8D. 9正确答案：C6. 已知一个有向图如右所示，则从顶点a出发进行深度优先偏历，不可能得到的DFS序列为A. a d b e f cB. a d c e f bC. a d c b f eD. a d e f c b正确答案：A7. 假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。

若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为A. (rear-front-1)％nB. (rear-front)％nC. (front-rear+1)％nD. (rear-front+n)％n正确答案：D8. 一个具有1025个结点的二叉树的高h为A. 11B. 10C. 11至1025之间D. 10至1024之间正确答案：C9. 在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是A. p=p->next;B. p->next=p->next->next;C. p->next=p;D. p=p->next->next;正确答案：B10. 下面的叙述不正确的是A. 线性表在链式存储时，查找第i个元素的时间同i的值成正比B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成反比D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关正确答案：B11. 如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是A. 有向完全图B. 连通图C. 强连通图D. 有向无环图正确答案：D12. 在VSAM文件的控制区间中，记录的存储方式为A. 无序顺序B. 有序顺序C. 无序链接D. 有序链接正确答案：B13. 对关键字序列（5，1，4，3，7，2，8，6）进行快速排序时，以第一个元素5为基准的一次划分的结果为A. （1，2，3，4，5，6，7，8）B. （1，4，3，2，5，7，8，6）C. （2，1，4，3，5，7，8，6）D. （8，7，6，5，4，3，2，1）正确答案：C14. 深度为h的满m叉树的第k层的结点(1=<k=<h)数有A. mk-1B. mk-1C. mh-1D. mh-1正确答案：A15. 多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为A. 数组的元素处在行和列两个关系中B. 数组的元素必须从左到右顺序排列C. 数组的元素之间存在次序关系D. 数组是多维结构，内存是一维结构正确答案：D16. 用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为A. n-1B. nC. n+lD. 2n正确答案：C17. 已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为A. 0B. 1C. 48D. 49正确答案：D18. 若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的A. 层次遍历算法B. 前序遍历算法C. 中序遍历算法D. 后序遍历算法正确答案：C19. 在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next= head,则A. p指向头结点B. p指向尾结点C. p的直接后继是头结点D. P的直接后继是尾结点正确答案：D20. 若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为A. n-1B. ën/mû-1C. é(n-1)/(m-1)ùD. én/(m-1)ù-1正确答案：C。

数据结构II试题期末考试备战题集（线上）一、单选题（每小题2分，共6分）1．抽象数据类型的三个组成部分分别为A．数据对象、数据关系和基本操作B．数据元素、逻辑结构和存储结构C．数据项、数据元素和数据类型D．数据元素、数据结构和数据类型2．下列各式中，按增长率由小至大的顺序正确排列的是A．n，n！，2n ，n3/2 B．n3/2，2n，n logn，2100C．2n，log n，n logn，n3/2 D．2100，logn, 2n, n n 3. 已知指针p和q分别指向某单链表中第一个结点和最后一个结点。

假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为A. q->next=s->next；s->next=p；B. s->next=p；q->next=s->next；C. p->next=s->next；s->next=q；D. s->next=q；p->next=s->next；参考正确选项：1、A2、D3、A二、填空题（每小题1分，共10分）1.下面程序段中带下划线的语句的执行次数的数量级是( )。

i=1；WHILE(i<n)i=i*2;2．假设带头结点的非空单循环链表中仅设尾指针L，则在第1个结点之前插入指针s所指结点的语句依次是（）。

3．无表头结点的链队列Q为空的条件是（）。

4．设Q[0..N-1]为循环队列，其头、尾指针分别为P和R，则队Q中当前所含元素个数为（）。

5．一棵含999个结点的完全二叉树的深度为（）。

6．在 AOV网中，存在环意味着某项活动以自己为先决条件；对程序的数据流图来说，它表明存在（）。

7. 有向图G可拓扑排序的判别条件是( )。

8．如果结点A有 3个兄弟，而且B是A的双亲，则B的度是（）。

9．应用回溯与分支限界法解决实际问题时，在搜索过程中利用判定函数，也称为（）。

数据结构II+A卷答案+XXX(2)1.抽象数据类型由数据对象、数据关系和基本操作三个组成部分组成。

2.要求相同逻辑结构的数据元素具有相同的特性，即不仅数据元素包含的数据项的个数相同，而且其对应数据项的类型也要一致。

3.按增长率由小至大的顺序排列的是：2n，nlogn，n3/2，2100.4.当经常需要进行插入和删除操作时，宜采用链表表示线性表。

5.设指针p指向双链表的某一结点，则双链表结构的对称性是p->r->next=p->next->r。

6.已知指针p和q分别指向某带头结点的单链表中第一个结点和最后一个结点。

假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为s->next=p->next；p->next=s。

7.栈和队列的共同特点是都只允许在端点处插入和删除元素。

8.对于链队列，在进行插入运算时，头、尾指针可能都要修改。

定义：typedef struct ArcNode{int adjvex。

//邻接点struct XXX指向下一个邻接点的指针ArcNode;typedef struct VNode{int data。

//顶点信息XXX指向第一个邻接点的指针int in。

//入度VNode,AdjList[MAXV];typedef struct{AdjList vertices。

//邻接表int vexnum,um。

//顶点数和弧数ALGraph;拓扑排序的基本思想是：每次选择一个入度为0的顶点输出，并将该顶点从图中删除，同时更新其它顶点的入度。

直到所有顶点都输出为止。

算法的实现如下：void TopSort(ALGraph G){int i,k,count=0;int *stack,*top;ArcNode *p;stack=(int*)malloc(G.vexnum*sizeof(int));top=stack;for(i=0;i<G.vexnum;i++)if(!G.vertices[i].in) *(++top)=i。

东北师范大学“计算机科学与技术”《数据结构》23秋期末试题库含答案第1卷一.综合考核(共20题)1.在下列情况中，可称为二叉树的是()。

A.每个结点至多有两棵子树的树B.哈夫曼树C.每个结点至多有两棵子树的有序树D.每个结点只有一棵右子树2.下列描述中正确的是()。

A.选择合适的数据结构是解决应用问题的关键步骤B.线性表的逻辑顺序与存储顺序总是一致的C.每种数据结构都具备查找、插入和删除三种基本运算D.数据结构实质上包括逻辑结构和存储结构两方面的内容3.在排序方法中，从未排序序列中挑选记录，并将其依次放入已排序序列(初始时为空)的一端的方法，称为()。

A.希尔排序B.插入排序C.归并排序D.选择排序4.最佳二叉排序树是AVL树(平衡二叉排序树)。

()A.正确B.错误5.在二叉树中插入结点，则此二叉树便不再是二叉树了。

()A.正确B.错误6.连通分量是无向图中的极大连通子图。

()A.错误B.正确7.稀疏矩阵压缩存储后，必会失去随机存取功能。

()A.正确B.错误8.无向图的邻接矩阵可用一维数组存储。

()A.正确B.错误9.栈和队列都是限制存取点的线性结构。

()A.正确B.错误10.设散列地址空间为0~m-1，key为关键字，用p去除key，将得到的余数作为key的散列地址，即h(key)=key%p。

为了减少发生冲突的频率，一般取p为()。

A.小于等于m的最大奇数B.小于等于m的最大偶数C.小于等于m的最大素数D.小于等于m的最大合数11.12.邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。

()A.正确B.错误13.所谓取广义表的表尾就是返回广义表中最后一个元素。

()A.错误B.正确14.任何一棵二叉树的叶结点在前序、中序和后序遍历序列中的相对次序()。

A.稍有改变B.发生改变C.不能确定D.不发生改变15.将一个A[1..100，1..100]的三对角矩阵，按行优先次序存入一维数组B[1..298]中，A中元素A[66，65]在数组B中的位置K为()。

数据结构(第二版)课后习题答案第一章：数据结构概述数据结构是计算机科学中非常重要的一个概念，它用于组织和管理计算机内部存储的数据。

数据结构的设计直接影响到程序的运行效率和对真实世界问题的建模能力。

第二版的《数据结构》教材旨在帮助读者更好地理解和应用数据结构。

为了提高学习效果，每章节后都附有一系列习题。

本文将为第二版《数据结构》教材中的部分习题提供详细的答案和解析。

第二章：线性表2.1 顺序表习题1：请问如何判断顺序表是否为空表？答案：当顺序表的长度为0时，即为空表。

解析：顺序表是用一块连续的内存空间存储数据元素的线性结构。

当顺序表中没有元素时，长度为0，即为空表。

习题2：如何求顺序表中第i个元素的值？答案：可以通过访问顺序表的第i-1个位置来获取第i个元素的值。

解析：顺序表中的元素在内存中是连续存储的，通过下标访问元素时，需要将下标减1，因为数组是从0开始编号的。

2.2 链表习题1：请问链表中的结点包含哪些信息？答案：链表的结点一般包含两部分信息：数据域和指针域。

解析：数据域用于存储数据元素的值，指针域用于存储指向下一个结点的指针。

习题2：如何删除链表中的一个结点？答案：删除链表中的一个结点需要将其前一个结点的指针指向其后一个结点，然后释放被删除结点的内存空间。

解析：链表的删除操作相对简单，只需要通过修改指针的指向即可。

但需要注意释放被删除结点的内存空间，防止内存泄漏。

第三章：栈和队列3.1 栈习题1：如何判断栈是否为空？答案：当栈中没有任何元素时，即为空栈。

解析：栈是一种先进后出（Last In First Out，LIFO）的数据结构，栈顶指针指向栈顶元素。

当栈中没有元素时，栈顶指针为空。

习题2：请问入栈和出栈操作的时间复杂度是多少？答案：入栈和出栈操作的时间复杂度均为O(1)。

解析：栈的入栈和出栈操作只涉及栈顶指针的改变，不受栈中元素数量的影响，因此时间复杂度为O(1)。

3.2 队列习题1：请问队列可以用哪些方式实现？答案：队列可以用数组或链表来实现。

1.在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为()。

[答案：B]A.O(n)B.O(n+e)C.O(n2)D.O(n3)2.已知一组关键字为{25，48，36，72，79，82，23，40，16，35}，其中每相邻两个为有序子序列。

对这些子序列进行一趟两两归并的结果是()。

[答案：D]A.{25，36，48，72，23，40，79，82，16，35}B.{25，36，48，72，16，23，40，79，82，35}C.{25，36，48，72，16，23，35，40，79，82}D.{16，23，25，35，36，40，48，72，79，82}3.连通图是指图中任意两个顶点之间()。

[答案：A]A.都连通的无向图B.都不连通的无向图C.都连通的有向图D.都不连通的有向图4.数据元素及其关系在计算机存储器内的表示，称为数据的()。

[答案：B]A.逻辑结构B.存储结构C.线性结构D.非线性结构5.设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。

若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为()。

[答案：C]B.23C.41D.626.在待排关键字序列基本有序的前提下，效率最高的排序方法是()。

[答案：A]A.直接插入排序B.快速排序C.直接选择排序D.归并排序7.已知广义表LS=((a，b，c)，(d，e，f))，运算head和tail函数取出元素e的运算是()。

[答案：C]A.head(tail(LS))B.tail(head(LS))C.head(tail(head(tail(LS))))D.head(tail(tail(head(LS))))8.用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是()。

[答案：A]A.逆拓扑有序B.拓扑有序C.无序的D.A和B9.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是()。

数据结构第2版习题答案第1章：引言数据结构是计算机科学中非常重要的一个领域，它关注如何以高效的方式组织和存储数据，以及如何在数据集合中进行操作和处理。

本章将回答《数据结构第2版》中的习题，帮助读者更好地理解和掌握数据结构。

第2章：算法分析习题1：算法复杂度问题描述：给定一个算法中的递归函数，分析其时间复杂度。

解答：对于递归算法的时间复杂度分析，可以使用递归树或者递推关系式来求解。

根据习题中给出的递归函数具体形式，我们可以推导出其递归关系式，并通过求解递推关系式确定时间复杂度。

习题2：渐进符号问题描述：给定两个函数f(n)和g(n)，证明f(n)的渐进复杂度小于等于g(n)的渐进复杂度。

解答：为了证明f(n)的渐进复杂度小于等于g(n)的渐进复杂度，我们需要使用大O符号进行形式化的证明。

通过定义和性质的证明，可以得出结论。

第3章：线性表习题3：线性表的实现问题描述：实现一个线性表的数据结构，并给出相关操作的算法。

比如插入元素、删除元素、查找元素等。

解答：一个线性表可以通过数组或链表来实现。

我们可以定义一个包含元素和相关操作的类来表示线性表。

在插入、删除、查找元素等操作中，可以通过遍历或者索引等方式来实现。

习题4：线性表的应用问题描述：举例介绍线性表的应用场景，并分析其对应的实现方法和复杂度。

解答：线性表的应用场景非常广泛，比如数组、链表、队列、栈等。

我们可以通过具体的案例，如存储学生成绩、处理任务队列、实现表达式求值等，来说明线性表的应用和对应的实现方法。

第4章：栈和队列习题5：栈和队列的实现问题描述：实现一个栈和队列的数据结构，并给出相关操作的算法。

解答：栈和队列可以通过数组或链表来实现。

我们可以定义相应的类来表示栈和队列，并实现相关操作，如入栈、出栈、入队、出队等。

习题6：栈和队列的应用问题描述：举例介绍栈和队列的应用场景，并分析其对应的实现方法和复杂度。

解答：栈和队列的应用非常广泛，比如表达式求值、括号匹配、图的深度优先搜索等。

东北师范大学22春“计算机科学与技术”《数据结构》作业考核题库高频考点版（参考答案）一.综合考核(共50题)1.一个有向图的邻接表和逆邻接表中结点的个数可能不等。

()A.错误B.正确参考答案：A2.后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。

()A.错误B.正确参考答案：B3.健壮的算法不会因非法的输人数据而出现莫名其妙的状态。

()A.正确B.错误参考答案：A4.一个队列的入队序列是a、b、c、d，则队列的输出序列是()。

A.dcbaB.cbdaC.adcbD.abcd参考答案：D5.B.物理C.逻辑和存储D.线性参考答案：B6.假定有k个关键字互为同义词，若采用线性探查法把这k个关键字存入散列表中，至少需要进行多少次探测?()A.k-1次B.k次C.k+1次D.k(k+1)/2次参考答案：D7.任何一个递归过程都可以转换成非递归过程。

()A.正确B.错误参考答案：A8.在k叉树中，度为0的结点称为()。

A.祖先B.根C.子孙D.叶参考答案：D9.n个结点的线索二叉树上含有的线索数为()。

A.n-1B.n+1C.n10.广义表(a，b，c，d)的表头是()。

A.(b，c，d)B.(a，b，c，d)C.aD.(a)参考答案：B11.在指定结点之前插入新结点时，双链表比单链表更方便。

()A.正确B.错误参考答案：A12.对一棵二叉树进行层次次序遍历时，应借助于一个栈。

()A.错误B.正确参考答案：A13.就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是()。

A.堆排序B.堆排序C.堆排序>归并排序>快速排序D.堆排序>快速排序>归并排序参考答案：A14.数组是同类型值的集合。

()A.正确15.“堆积”问题是由于()引起的。

A.同义词之间发生冲突B.散列函数C.不同的同义词子表结合在一起D.散列表“溢出”参考答案：C16.在完全二叉树中，若一个结点没有左子女，则它必是树叶。

东大19秋学期《数据结构Ⅱ》在线平时作业2
试卷总分:100 得分:100
一、单选题 (共 20 道试题,共 100 分)
1.数据的四种基本存储结构是指
A.顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构
B.顺序存储结构、链式存储结构、树型存储结构、图型存储结构
C.顺序存储结构、索引存储结构、链式存储结构、散列存储结构
D.顺序存储结构、索引存储结构、直接存储结构、倒排存储结构
【运用所学知识，完成上述题目】
参考选择:C
2.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是
A.4，3，2，1，5，6
B.3，2，4，1，6，5
C.2，4，3，1，5，6
D.2，3，5，1，6，4
【运用所学知识，完成上述题目】
参考选择:D
3.有关二叉树下列说法正确的是
A.二叉树的度为2
B.二叉树中至少有一个结点的度为2
C.二叉树中任何一个结点的度都为2
D.一棵二叉树的度可以小于2
【运用所学知识，完成上述题目】
参考选择:D
4.算法分析的目的是
A.鉴别算法的可读性
B.辨别数据结构的合理性
C.评价算法的效率
D.研究算法中输入与输出的关系
【运用所学知识，完成上述题目】
参考选择:C
5.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为
A.X的左子树中最右结点
B.X的左子树中最右叶结点
C.X的右子树中最左的结点
D.X的双亲
【运用所学知识，完成上述题目】
参考选择:A。

2022年东北大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、已知广义表LS=（（a，b，c），（d，e，f）），用head和tail数取出LS中原子e的运算是（）。

A.head（tail（LS））B.tail（head（LS））C.head（tail（head（tail（LS））））D.head（tail（tail（head（LS））））2、下列说法不正确的是（）。

A.图的遍历是从给定的源点出发每个顶点仅被访问一次B.遍历的基本方法有两种：深度遍历和广度遍历C.图的深度遍历不适用于有向图D.图的深度遍历是一个递归过程3、静态链表中指针表示的是（）。

A.下一元素的地址B.内存储器的地址C.下一元素在数组中的位置D.左链或右链指向的元素的地址4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。

A.（rear+1）MOD n=frontB.rear=frontC.rear+1=frontD.（rear-1）MOD n=front5、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（）。

A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front6、下列关于无向连通图特性的叙述中，正确的是（）。

Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1 A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ7、下列叙述中，不符合m阶B树定义要求的是（）。

A．根结点最多有m棵子树 B．所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接8、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。

A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个9、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）。