40875][东北大学]20年7月考试《数据结构Ⅱ》考核作业(答案)

东北大学22春“计算机科学与技术”《数据库技术及应用Ⅱ》作业考核题库高频考点版（参考答案）一.综合考核(共50题)1.当数据的全局逻辑结构改变时，数据的局部逻辑结构可以不变，从而应用程序也不用改变这就是数据与程序的()。

A.逻辑独立性B.物理独立性C.完整性D.一致性参考答案：A2.进行表拷贝操作，新表与被拷贝表的列名和列数可以不同，但是数据类型必须一致。

()A.正确B.错误参考答案：A3.下列语句中不是语句权限命令的是()A.createdatabaseB.createtableC.insertD.backuplog参考答案：C4.在关系模式R(A，B，C)中，有函数依赖集F={(A，B)→C，(B，C)→A}，则R最高达到()A.INFB.2NFC.3NFD.BCNF5.数据库的并发操作可能带来的问题包括()A.丢失更新B.数据独立性会提高C.非法用户的使用D.增加数据冗余度参考答案：A6.SQL Server的语句权限表示对数据库特定对象的操作权限。

()A.正确B.错误参考答案：B7.关系中的投影运算是选择出满足条件的列构成新的关系。

()A.正确B.错误参考答案：A8.Web数据库的结构第二层是实现业务逻辑的Web服务器。

()A.正确B.错误参考答案：A9.利用日志文件恢复事务时，对尚未结束的事务，应()。

A.重新执行已登记的操作B.进行UNDO处理C.进行REDO处理参考答案：B10.数据库中“关系”这个术语来自于数学中的集合概念。

()A.正确B.错误参考答案：A11.一个事务中所有对DB操作是一个不可分割的操作序列，这个性质称为事务的()A.隔离性B.串行性C.永久性D.原子性参考答案：D12.数据库系统的主要特点之一是整体数据的结构化。

()A.正确B.错误参考答案：A13.触发器是一种特殊类型的存储过程。

()A.正确B.错误参考答案：A14.在SQL语言中，能够实现关系参照完整性规则的子句是()。

（完整版）数据结构试题及答案《数据结构》⾃考复习思考试题○10⼀、单项选择题(本⼤题共15⼩题，每⼩题2分，共30分)在每⼩题列出的四个备选项中只有⼀个是符合题⽬要求的，请将其代码填写在题后的括号内。

错选、多选或未选均⽆分。

1. 若将数据结构形式定义为⼆元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合C. 类型的有限集合D. 关系的有限集合2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( )A. n-i+1B. iC. i+1D. n-i3. 若不带头结点的单链表的头指针为head，则该链表为空的判定条件是( )A. head==NULLB. head->next==NULLC. head!=NULLD. head->next==head4. 引起循环队列队头位置发⽣变化的操作是( )A. 出队B. ⼊队C. 取队头元素D. 取队尾元素5. 若进栈序列为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，46. 字符串通常采⽤的两种存储⽅式是( )A. 散列存储和索引存储B. 索引存储和链式存储C. 顺序存储和链式存储D. 散列存储和顺序存储7. 设主串长为n，模式串长为m(m≤n)，则在匹配失败情况下，朴素匹配算法进⾏的⽆效位移次数为( )A. mB. n-mC. n-m+1D. n8. ⼆维数组A［12］［18］采⽤列优先的存储⽅法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A［9］［7］的地址为( )A. 429B. 432.C. 435D. 4389. 对⼴义表L=((a,b),(c,d),(e,f))执⾏操作tail(tail(L))的结果是( )A. (e,f)B. ((e,f))C. (f)D. ( )10. 下列图⽰的顺序存储结构表⽰的⼆叉树是( )11. n个顶点的强连通图中⾄少含有( )A. n-1条有向边B. n条有向边C. n(n-1)/2条有向边D. n(n-1)条有向边12. 对关键字序列(56，23，78，92，88，67，19，34)进⾏增量为3的⼀趟希尔排序的结果为( )A. (19，23，56，34，78，67，88，92)B. (23，56，78，66，88，92，19，34)C. (19，23，34，56，67，78，88，92)D. (19，23，67，56，34，78，92，88)13. 若在9阶B-树中插⼊关键字引起结点分裂，则该结点在插⼊前含有的关键字个数为( ) A. 4 B. 5C. 8D. 914. 由同⼀关键字集合构造的各棵⼆叉排序树( )A. 其形态不⼀定相同，但平均查找长度相同B. 其形态不⼀定相同，平均查找长度也不⼀定相同C. 其形态均相同，但平均查找长度不⼀定相同.D. 其形态均相同，平均查找长度也都相同15. ISAM⽂件和VSAM⽂件的区别之⼀是( )A. 前者是索引顺序⽂件，后者是索引⾮顺序⽂件B. 前者只能进⾏顺序存取，后者只能进⾏随机存取C. 前者建⽴静态索引结构，后者建⽴动态索引结构D. 前者的存储介质是磁盘，后者的存储介质不是磁盘⼆、填空题(本⼤题共10⼩题，每空2分，共20分)16. 数据的逻辑结构在计算机存储器内的表⽰，称为数据的____________。

东北大学继续教育学院软件工程与UML建模试卷（作业考核线上1） A 卷学习中心：奥鹏远程教育沈阳学习中心（直属）[32] 院校学号：C09024011930344 姓名何家强（共 4 页）一、单选题（30分，共15题，每题2分）1． D 是在系统之外，透过系统边界与系统进行有意义交互的任何事物A).相关系统B).Use Case C).Class D).Actor2.软件工程是以 D 为核心A).过程B).面向对象C).软件开发D).质量3.“系统开发过程和可交付文档将遵照ZCo-SP0STAN-95中相关规定”，这属于 DA).功能性需求B).客观需求C).主观需求D).非功能性需求4.“系统每天晚上自动生成进货报表”，Actor是： CA).系统B).其它系统C).时间D).报表审阅者5.数据流程图是一个分层的概念模型，分三个层次： C ，分别描述系统的不同特征A).总体图、二级图、三级图B).总体图、二级图、细节图C).总体图、零级图、细节图D).总体图、次级图、细节图6.以下用例命名中，最合理的是 DA).进行宠物搜索B).查询宠物C).宠物查询D).进行宠物查询7.某系统中有两个用例：一个用例的参与者是用户，用例是“注册”；另一个用例的参与者是系统管理员，用例是“审核用户注册”。

这两个用例之间是什么关系？ BA).包含关系B).没有关系C).扩展关系D).泛化关系8.在软件的层次结构中，“一个模块被其他模块直接调用的调用者的数量”是指 BA).深度B).扇入 C).扇出 D).耦合9.设C(X)定义问题X的复杂性函数，E(X)定义解决问题X所需要工作量的函数，对于两个问题p1和p2，一般情况下如果C(p1)<C(p2) 则 DA).E(p1)>E(p2) B).C(p1+p2)=C(p1)+C(p2)C).E(p1+p2)>E(p1)+E(p2) D).E(p1+p2)<E(p1)+E(p2)10.以下各种图不是UML使用的图是 CA).用例图B).类图C).数据流程图D).顺序图11.模块尺寸太大时，应 AA).分解以提高内聚B).分解以提高耦合C).合并以提高内聚D).分解以降低内聚12.以下类的命名中，最合理的是 AA). BusVehicle B). Routes C). passenger D). Stop13.在软件过程中，下列活动属于辅助活动的是 DA).设计B).集成C).退役D).风险管理14.下面用例模型体现了用例间的 A 关系A).泛化、包含和扩展B).包含和扩展C).分解、包括和扩充D).分解、包含和扩展15.下图体现了面向对象中类的 CA).复杂性B). 可传递性 C).自反关联D). 继承关系二、简答题（40分，共4题，每题10分）1.请解释软件工程的含义。

东北大学智慧树知到“计算机科学与技术”《数据结构Ⅱ》网课测试题答案（图片大小可自由调整）第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。

数据结构试卷（一）王彬一、单选题（每题2 分，共20分）1.栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时( ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？( )A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

cA．688 B．678 C．692 D．6965.树最适合用来表示( )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( d ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O（1）B. O（n）C. O（1og2n）D. O（n2）9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ c d）个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

A.5B.6C.7D.8二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：____ ____、________、________和_______。

2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。

数据结构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．应用回溯与分支限界法解决实际问题时，在搜索过程中利用判定函数，也称为（）。

东北师范大学“计算机科学与技术”《数据结构》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为()。

第二套数据库笔试题及答案1. 以下数据结构中不属于线性数据结构的是______。

A、队列B、线性表C、二叉树D、栈2. 在结构化方法中，用数据流程图(DFD)作为描述工具的软件开发阶段是______。

A、可行性分析B、需求分析C、详细设计D、程序编码3. 结构化程序设计主要强调的是______。

A、程序的规模B、程序的易读性C、程序的执行效率D、程序的可移植性4. 在软件生命周期中，能准确地确定软件系统必须做什么和必须具备哪些功能的阶段是______。

A、概要设计B、详细设计C、可行性分析D、需求分析5. 下列关于栈的叙述中正确的是______。

A、在栈中只能插入数据B、在栈中只能删除数据C、栈是先进先出的线性表D、栈是先进后出的线性表6. 下面不属于软件设计原则的是______。

A、抽象B、模块化C、自底向上D、信息隐蔽7. 对长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为______。

A、N+1B、NC、(N+1)/2D、N/28. 视图设计一般有3种设计次序，下列不属于视图设计的是______。

A、自顶向下B、由外向内C、由内向外D、自底向上9. 下列有关数据库的描述，正确的是______。

A、数据库是一个DBF文件B、数据库是一个关系C、数据库是一个结构化的数据集合D、数据库是一组文件10. 下列说法中，不属于数据模型所描述的内容的是______。

A、数据结构B、数据操作C、数据查询D、数据约束11. 在下面的Visual FoxPro表达式中，运算结果是逻辑真的是______。

A、EMPTY(.NULL.)B、LIKE( acd , ac )C、AT( a , 123abc )D、EMPTY(SPACE(2))12. 表达式VAL(SUBS( 奔腾586 ,5,1))*Len( visual foxpro )的结果是______。

A、13.00B、14.00C、45.00D、65.0013. 以下关于自由表的叙述，正确的是______。

数据结构试题及答案(10套最新)(总49页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--一、单选题（每题 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)选择题 (2)第一章绪论. (2)第二章线性表. (4)第三章栈和队列. (6)第四章串. (7)第五章数组和广义表 (8)第六章树和二叉树 (8)第七章图. (11)第八章查找. (13)第九章排序. (14)简答题 (19)第一章绪论. (19)第二章线性表. (24)第三章栈和队列. (26)第四章串. (28)第五章数组和广义表 (29)第六章树和二叉树 (31)第七章图. (36)第八章查找. (38)第九章排序. (39)编程题 (41)第一章绪论. (41)第二章线性表. (41)第三章栈和队列. (52)第四章串. (52)第五章数组和广义表 (52)第六章树和二叉树 (52)第七章图. (52)第八章查找. (52)第九章排序. (57)选择题第一章绪论1. 数据结构这门学科是针对什么问题而产生的？（ A ）A、针对非数值计算的程序设计问题 B 、针对数值计算的程序设计问题C、数值计算与非数值计算的问题都针对D、两者都不针对2. 数据结构这门学科的研究内容下面选项最准确的是（ D ）A、研究数据对象和数据之间的关系 B 、研究数据对象C、研究数据对象和数据的操作D、研究数据对象、数据之间的关系和操作3. 某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那么下面关于数据对象、数据元素、数据项描述正确的是（ C ）A、某班级的学生成绩表是数据元素，90 分是数据项B、某班级的学生成绩表是数据对象，90 分是数据元素C、某班级的学生成绩表是数据对象，90 分是数据项D、某班级的学生成绩表是数据元素，90 分是数据元素4. *数据结构是指（A ）。

A、数据元素的组织形式B、数据类型C、数据存储结构D、数据定义5. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。

A、存储结构B、逻辑结构C、链式存储结构D、顺序存储结构6. 算法分析的目的是（ C ）A、找出数据的合理性B、研究算法中的输入和输出关系C、分析算法效率以求改进D、分析算法的易懂性和文档型性7. 算法分析的主要方法（ A ）。

一、单选题（每题 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、研究数据结构就是研究（ D ）。

A. 数据的逻辑结构B. 数据的存储结构C. 数据的逻辑结构和存储结构D. 数据的逻辑结构、存储结构及其基本操作2、算法分析的两个主要方面是（ A ）。

A. 空间复杂度和时间复杂度B. 正确性和简单性C. 可读性和文档性D. 数据复杂性和程序复杂性3、具有线性结构的数据结构是（ D ）。

A. 图B. 树C. 广义表D. 栈4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（ B ）等5个特性。

A. 可执行性、可移植性和可扩充性B. 可执行性、有穷性和确定性C. 确定性、有穷性和稳定性D. 易读性、稳定性和确定性5、下面程序段的时间复杂度是（ C ）。

for(i=0;i<m;i++)for(j=0;j<n;j++)a[i][j]=i*j;A. O(m2)B. O(n2)C. O(m*n)D.O(m+n)6、算法是（ D ）。

A. 计算机程序B. 解决问题的计算方法C. 排序算法D. 解决问题的有限运算序列7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（ C ）。

A. O(n)B. O(nlog2n)C. O(n2)D. O(log2n)8、下面程序段的时间复杂度为（ C ）。

i=1;while(i<=n)i=i*3;A. O(n)B. O(3n)C. O(log3n)D. O(n3)9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。

A. 结构B. 关系C. 运算D. 算法10、下面程序段的时间复杂度是（A ）。

i=s=0;while(s<n){i++;s+=i;}A. O(n)B. O(n2)C. O(log2n)D. O(n3)11、抽象数据类型的三个组成部分分别为（ A）。

A. 数据对象、数据关系和基本操作B. 数据元素、逻辑结构和存储结构C. 数据项、数据元素和数据类型D. 数据元素、数据结构和数据类型12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量，以下解释错误的是（）。

东北大学继续教育学院数据结构II 试卷（作业考核线上1） A 卷学习中心：院校学号：姓名（共 6 页）一、单选题（共30题，每题2分）[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)任何一棵二叉树的叶子结点在种遍历中的相对次序不变。

计算机二级考试数据结构题库及答案一、选择题1.1 单选题1.数据结构是计算机存储、组织数据的方式。

以下哪个不属于数据结构的基本类型？A. 线性结构B. 树状结构C. 图形结构D. 字符串答案：D2.以下哪种数据结构的时间复杂度为 O(1)？A. 链表查找B. 数组查找C. 二叉树查找D. 广度优先搜索答案：B1.2 多选题3.以下哪些是常见的基本数据结构？A. 数组B. 链表C. 栈D. 队列E. 散列表答案：A、B、C、D、E二、填空题4.在计算机科学中，数据结构是一种用于存储和组织数据的方式，以____（填空）和____（填空）的方式进行数据的访问和管理。

答案：高效、方便三、判断题5.链表是一种线性数据结构，其特点是每个元素都有一个指向下一个元素的指针。

答案：正确6.深度优先搜索和广度优先搜索都是用于图遍历的算法，它们的区别在于遍历的顺序不同。

答案：正确四、简答题7.请简要介绍栈和队列的特点及应用场景。

答案：栈是一种后进先出（LIFO）的数据结构，常见应用场景有函数调用栈、表达式求值等。

队列是一种先进先出（FIFO）的数据结构，常见应用场景有任务调度、缓冲区等。

8.请简要介绍散列表的特点及优缺点。

答案：散列表是一种通过哈希函数将关键字映射到表中一个位置来访问记录的数据结构。

其优点是平均查找速度快，插入和删除操作也较为高效。

缺点是可能会发生哈希冲突，需要额外的处理措施，同时内存利用率可能不高。

五、编程题9.编写一个函数，实现单链表的插入排序。

答案：class ListNode:def __init__(self, val=0, next=None): self.val = valself.next = nextdef insertion_sort_list(head):dummy = ListNode(0)cur = headwhile cur:next_node = cur.nextpre = dummywhile pre.next and pre.next.val < cur.val: pre = pre.nextcur.next = pre.nextpre.next = curcur = next_nodereturn dummy.next。

东大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。

东北师范大学22春“计算机科学与技术”《数据结构》期末考试高频考点版（带答案）一.综合考核(共50题)1.在执行某个排序算法过程中，出现了排序码朝着它最终排序位置相反的方向移动，则该算法是不稳定的。

()A.错误B.正确参考答案：A2.归并排序的辅助存储空间代价为O(1)。

()A.正确B.错误参考答案：B3.在链队列中，假设f和r分别为队首和队尾指针，则删除一个结点的操作是()。

A.r=r->nextB.r=f->nextC.f=r->nextD.f=f->next参考答案：D4.空串与空格串是相同的。

()A.错误B.正确参考答案：AA.正确B.错误参考答案：B6.数据的存储结构是数据的逻辑结构在计算机存储器上的实现，它是依赖于计算机的。

()A.正确B.错误参考答案：A7.有一个100*90的稀疏矩阵，非零元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是()。

A.60B.66C.18000D.33参考答案：A8.在中序线索二叉树中，每一非空的线索均指向其祖先结点。

()A.错误B.正确参考答案：B9.串是一种数据对象和操作都特殊的线性表。

()A.错误B.正确参考答案：B在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关?()A.直接选择排序B.直接插入排序C.快速排序D.冒泡排序参考答案：A11.二叉树中除叶结点外，任一结点X，其左子树根结点的值小于该结点X的值﹔其右子树根结点的值大于等于该结点X的值，则此二叉树一定是二叉排序树。

()A.错误B.正确参考答案：A12.二叉树中每个结点至多有两个子结点，而对一般的树则无此限制。

因此，二叉树是树的特殊情形。

()A.错误B.正确参考答案：A13.将一个A[1..100，1..100]的三对角矩阵，按行优先次序存入一维数组B[1..298]中，A中元素A[66，65]在数组B中的位置K为()。

A.199B.197C.195D.193参考答案：C14.B+树应用在()文件系统中。