ncut数据结构复习题

数据结构复习题及答案5篇第一篇：数据结构复习题及答案、数据结构复习题及答案中南大学现代远程教育课程考试（专科）复习题及参考答案数据结构一、判断题：1．数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。

（）2．链式存储在插人和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。

（）3．在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。

（）4．折半搜索只适用于有序表，包括有序的顺序表和有序的链表。

（）5．如果两个串含有相同的字符，则这两个串相等。

（）6．数组可以看成线性结构的一种推广，因此可以对它进行插入、删除等运算。

（）7．在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。

（）8．通常递归的算法简单、易懂、容易编写，而且执行的效率也高。

（）9．一个广义表的表尾总是一个广义表。

（）10．当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。

（）11．对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（h）。

（）12．存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。

（）13．直接选择排序是一种稳定的排序方法。

（）14．闭散列法通常比开散列法时间效率更高。

（）15．有n个结点的不同的二叉树有n!棵。

（）16．直接选择排序是一种不稳定的排序方法。

（）17．在2048个互不相同的关键码中选择最小的5个关键码，用堆排序比用锦标赛排序更快。

（）18．当3阶B_树中有255个关键码时,其最大高度(包括失败结点层)不超过8。

（）19．一棵3阶B_树是平衡的3路搜索树,反之,一棵平衡的3路搜索树是3阶非B_树。

（）20．在用散列表存储关键码集合时，可以用双散列法寻找下一个空桶。

《数据结构-C语言版》第一章绪论单项选择题1．在数据结构中，数据的基本单位是_____ ____。

A. 数据项B. 数据类型C. 数据元素D. 数据变量2．数据结构中数据元素之间的逻辑关系被称为__ ____。

A. 数据的存储结构B. 数据的基本操作C. 程序的算法D. 数据的逻辑结构3．在数据结构中，与所使用计算机无关的是数据的____ ___。

A. 存储结构B. 逻辑和物理结构C. 逻辑结构D. 物理结构4．在链式存储结构中，数据之间的关系是通过____ ____体现的。

A. 数据在内存的相对位置B. 指示数据元素的指针C. 数据的存储地址D. 指针5．计算算法的时间复杂度是属于一种____ ___。

A. 事前统计的方法B. 事前分析估算的方法C. 事后统计的方法D. 事后分析估算的方法6．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是____ __。

A. n2B. nlognC. nD. logn7．设使用某算法对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为____ ___。

A. O(1)B. O(n)C. O(200n)D. O(nlog2n)CDCBBDD第二章线性表单项选择题1．链表不具有的特点是____ ____。

A. 可随机访问任一元素B. 插入和删除时不需要移动元素C. 不必事先估计存储空间D. 所需空间与线性表的长度正比2．设顺序表的每个元素占8个存储单元。

第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为。

A. 139B. 140C. 147D. 1483．在线性链表存储结构下，插入操作算法。

A. 需要判断是否表满B. 需要判断是否表空C. 不需要判断表满D. 需要判断是否表空和表满4．在一个单链表中，若删除p所指结点的后继结点，则执行。

A. p->next = p->next->next;B. p->next = p->next;C. p = p->next->next;D. p = p->next; p->next = p->next->next;5．将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为。

（完整版）数据结构复习题（附答案）⼀、算法设计题（每题15分，共60分）答题要求：①⽤⾃然语⾔说明所采⽤算法的思想；②给出每个算法所需的数据结构定义，并做必要说明；③写出对应的算法程序，并做必要的注释。

1、有⼀个带头结点的单链表，每个结点包括两个域，⼀个是整型域info，另⼀个是指向下⼀个结点的指针域next。

假设单链表已建⽴，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保留⼀个。

3、约瑟夫环问题（Josephus问题）是指编号为1、2、…，n的n（n>0）个⼈按顺时针⽅向围坐成⼀圈，现从第s个⼈开始按顺时针⽅向报数，数到第m个⼈出列，然后从出列的下⼀个⼈重新开始报数，数到第m的⼈⼜出列，…，如此重复直到所有的⼈全部出列为⽌。

现要求采⽤循环链表结构设计⼀个算法，模拟此过程。

4、编程实现单链表的就地逆置。

23．在数组 A[1..n]中有n个数据，试建⽴⼀个带有头结点的循环链表，头指针为h，要求链中数据从⼩到⼤排列，重复的数据在链中只保存⼀个.5、设计⼀个尽可能的⾼效算法输出单链表的倒数第K个元素。

3、假设以I和O分别表⽰⼊栈和出栈操作。

栈的初态和终态均为空，⼊栈和出栈的操作序列可表⽰为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为⾮法序列。

（15分）（1）下⾯所⽰的序列中哪些是合法的？A. IOIIOIOOB. IOOIOIIOC. IIIOIOIOD. IIIOOIOO（2）通过对（1）的分析，写出⼀个算法，判定所给的操作序列是否合法。

若合法，返回true，否则返回false（假定被判定的操作序列已存⼊⼀维数组中）。

5、设从键盘输⼊⼀整数的序列：a1, a2, a3，…，an,试编写算法实现：⽤栈结构存储输⼊的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。

算法应对异常情况（⼊栈满等）给出相应的信息。

设有⼀个背包可以放⼊的物品重量为S，现有n件物品，重量分别为W1，W2，...，W n。

《数据结构》复习提纲第一章数据结构的概念及基本结构，数据结构在计算机中的表示方法及其存储结构算法的特性，会计算时间复杂度第二章线性表的顺序存储表示，掌握插入和删除操作，线性表的链式存储表示，掌握单链表的插入和删除操作第三章栈的定义及特点，栈的顺序存储表示队列的定义及特点，链队列的插入和删除，循环队列的判空判满条件第四章串的概念及常用操作，掌握模式串next函数的求法第五章特殊矩阵的存储表示，稀疏矩阵的三元组表示，会求广义表的头部和尾部第六章树的定义和基本概念，二叉树的性质，二叉树的链式存储结构――二叉链表二叉树的先序，中序，后序, 层次遍历操作会对二叉树进行先序，中序，后序线索化操作树的存储结构――－孩子兄弟表示法树，森林，二叉树三者之间的转换方法，以及它们遍历的对应关系掌握哈夫曼树的构造，会求树的带权路径长度WPL第七章图的定义和术语，图的邻接矩阵表示法，邻接表，逆邻接表掌握图的深度优先搜索算法，广度优先搜索算法最小生成树――普里姆算法和克鲁斯卡尔算法，会对AOV网进行拓扑排序会求AOE网的关键路径，关键活动第九章顺序查找表，有序表的折半查找，索引查找表及其平均查找长度ASL二叉排序树的建立和删除操作，会计算其平均查找长度ASL掌握将二叉排序树转换成平衡二叉树的旋转处理方法，哈希表的概念，掌握哈希函数的构造方法――除留余数法掌握处理冲突的方法――线性探测再散列及平均查找长度ASL――二次探测再散列及平均查找长度ASL第十章直接插入排序，希尔排序，快速排序，简单选择排序，堆排序，归并排序会写上述排序算法每趟排序的结果，并对其进行排序性能分析（稳定性，时间复杂度等）期末考试题型：选择题，填空题，综合题练习题一、单选题1.一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列？（c）A. 1，3，2，4B. 2，3，4，1C. 4，3，1，2D. 3，4，2，12.下列排序方法中，关键字的比较次数与记录的初始排列状态无关？（ c ）A. 直接插入排序B. 起泡排序C. 快速排序D. 直接选择排序3.对n个记录的文件进行二路归并排序，总的时间代价为（ d）A. O（nlogn）B. O（n2）C. O（logn）D. O（n）4.若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是（b ）A. 9B. 11C. 12D. 不确定5．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（d）A．q一>next＝p一>next；p一>next＝q；B．p一>next＝q一>next；q＝p；C．q一>next＝p一>next；p一>next＝q；D．p一>next＝q一>next； q一>next＝p；6.广义表A=（a,b,(c,d),(e,(f,g))）,则式子Head(Tail(Head(Tail(Tail(A)))))的值为 d ；A．（g） B.(d) C.c D.d7. 直接插入排序在最好情况下的时间复杂度为（d）。

《数据结构C语言》考研复习题库一、选择题1、在一个具有 n 个单元的顺序栈中，假定以地址低端（即 0 单元）作为栈底，以 top 作为栈顶指针，当做出栈处理时，top 变化为（）。

A top 不变B top ＝ 0C topD top+＋答案：C解释：在顺序栈中，出栈操作会使栈顶指针 top 减 1，即 top。

2、一个队列的入队序列是 1，2，3，4，则队列的输出序列是（）。

A 4，3，2，1B 1，2，3，4C 1，4，3，2D 3，2，4，1答案：B解释：队列是先进先出的数据结构，入队顺序为 1，2，3，4，那么出队顺序也为 1，2，3，4。

3、串是一种特殊的线性表，其特殊性体现在（）。

A 可以顺序存储B 数据元素是一个字符C 可以链式存储D 数据元素可以是多个字符答案：B解释：串的数据元素是字符，这是它与一般线性表的区别。

4、设有一个 10 阶的对称矩阵 A，采用压缩存储方式，以行序为主存储，a11 为第一元素，其存储地址为 1，每个元素占一个地址空间，则 a85 的地址为（）。

A 33B 32C 18D 40答案：A解释：对于对称矩阵，只存储其下三角或上三角部分。

对于一个 n阶对称矩阵，若以行序为主存储下三角部分，aij 的存储位置为 i(i 1)／2 ＋ j 1。

所以 a85 的地址为 8(8 1)／2 ＋ 5 1 ＝ 33。

5、一棵完全二叉树共有 700 个结点，则在该二叉树中有（）个叶子结点。

A 350B 349C 351D 不确定答案：C解释：根据完全二叉树的性质，度为 1 的结点个数最多为 1 个。

设n0 为叶子结点个数，n1 为度为 1 的结点个数，n2 为度为 2 的结点个数。

则 n ＝ n0 ＋ n1 ＋ n2 ，n 1 ＝ 2n2 ＋ n1 。

因为 n ＝ 700 ，且 n1 为 0或 1 ，通过计算可得 n0 ＝ 351 。

二、填空题1、数据的逻辑结构被分为_____、＿____、＿____和_____四种。

1.如下为二分查找的非递归算法，试将其填写完整。

Int Binsch(ElemType A[ ],int n,KeyType K){int low=0;int high=n-1;while (low<=high){int mid=_______________________________；if (K==A[mid].key) return mid; //查找成功，返回元素的下标else if (K<A[mid].key)______________________________________; //在左子表上继续查找else __________________________________; //在右子表上继续查找}return -1; //查找失败，返回-1}(low+high)/2 high=mid-1 low=mid+12.int Prime(int n){int i=1;int x=(int) sqrt(n);while (++i<=x)if (n%i==0) break;if (i>x) return 1;else return 0;}(1)指出该算法的功能；(2)该算法的时间复杂度是多少？2.(1) 判断n是否是素数（或质数）n（2）O（）3.已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6, 7)25}. 用克鲁斯卡尔（Kruskal）算法和prim算法得到最小生成树，试写出在最小生成树中依次得到的各条边。

3.用克鲁斯卡尔算法得到的最小生成树为：(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)204.LinkList mynote(LinkList L){//L是不带头结点的单链表的头指针if(L&&L->next){q=L；L=L－>next；p=L；S1：while(p－>next) p=p－>next；S2：p－>next=q；q－>next=NULL；}return L；}请回答下列问题：（1）说明语句S1的功能；（2）说明语句组S2的功能；（3）设链表表示的线性表为（a1,a2, …,a n）,写出算法执行后的返回值所表示的线性表。

2022年南昌理工学院数据科学与大数据技术专业《计算机系统结构》科目期末试卷B（有答案）一、选择题1、直接执行微指令的是( )A.汇编程序B.编译程序C.硬件D.微指令程序2、对汇编语言程序员透明的是（）A.I/O方式中的DMA访问B.浮点数据表示C.访问方式保护D.程序性中断3、以下说法不正确的是( )A.线性流水线是单功能流水线B.动态流水线是多功能流水线C.静态流水线是多功能流水线D.动态流水线只能是单功能流水线4、计算机系统多级层次中，从下层到上层，各级相对顺序正确的应当是（）。

A.汇编语言机器级，操作系统机器级，高级语言机器级B.微程序机器级，传统机器语言机器级，汇编语言机器级C.传统机器语言机器级，高级语言机器级，汇编语言机器级D.汇编语言机器级，应用语言机器级，高级语言机器级5、"从中间开始"设计的"中间"目前多数是在( )。

A.传统机器语言级与操作系统机器级之间B.传统机器语言级与微程序机器级之间C.微程序机器级与汇编语言机器级之间D.操作系统机器级与汇编语言机器级之间6、高级语言程序经（）的（）成汇编语言程序。

A.编译程序，翻译B.汇编程序，翻译C.汇编程序，解释D.编译程序，解释7、在流水机器中，全局性相关是指( )。

A.先写后读相关B.先读后写相关C.指令相关D.由转移指令引起的相关8、对系统程序员不透明的应当是（）A.CACHE 存储器B.系列机各档不同的数据通路宽度C.指令缓冲寄存器D.虚拟存储器9、开发并行的途径有（），资源重复和资源共享。

A.多计算机系统B.多道分时C.分布式处理系统D.时间重叠10、浮点数尾数基值rm=8，尾数数值部分长6位，可表示的规格化最小正尾数为( )A.0.5B.0.25C.0.125D.1/64二、填空题11、并行性概念包含________性和________性。

12、基于存储器-存储器的向量指令是指________来自________，两种结或把而且把操作后的结果直接写入存储器。

2022年南昌大学数据科学与大数据技术专业《计算机系统结构》科目期末试卷A(有答案）一、选择题1、在计算机系统设计中，比较好的方法是( )A.从上向下设计B.从下向上设计C.从两头向中间设计D.从中间开始向上、向下设计2、下列关于虚拟存贮器的说法，比较正确的应当是( )A.访主存命中率随页面大小增大而提高B.访主存命中率随主存容量增加而提高C.更换替换算法能提高命中率D.在主存命中率低时，改用堆栈型替换算法，并增大主存容量，可提高命中率3、多处理机的各自独立型操作系统（）。

A.要求管理程序不必是可再入的B.适合于紧耦合多处理机C.工作负荷较平衡D.有较高的可靠性4、1TFLOPS计算机能力，1TBYTE/S的I/O带宽和（）称为计算机系统的3T性能目标。

A，1TBYTE 硬盘容量B.1TBYTE 软盘容量C.1TBYTE 主存容量D.A和B5、下列关于标量流水机的说法不正确的是（）A.可对标量数据进行流水处理B.没有向量数据表示C.不能对向量数据进行运算D.可以对向量、数组进行运算6、直接执行微指令的是( )A.汇编程序B.编译程序C.硬件D.微指令程序7、微指令由（）直接执行。

A.微指令程序B.硬件C.汇编程序D.编译程序8、在计算机系统设计中，比较好的方法是（）。

A.从上向下设计B.从下向上设计C.从两头向中间设计D.从中间开始向上、向下设计9、程序员编写程序时使用的地址是( )。

A.有效地址B.逻辑地址C.辅存实地址D.主存地址10、下列说法正确的是( )A.Cache容量一般不大，命中率不会很高B.Cache芯片速度一般比CPU的速度慢数十倍C.Cache本身速度很快。

但地址变换的速度很慢D.Cache存贮器查映象表和访问物理Cache其间可以流水，使速度与CPU匹配二、填空题11、向量指令可分为________和________12、Cache存贮器对应用程序员是________的。

对系统程序员是________的（填“透明”或“不透明”）13、Cache存贮器地址映象大多采用________映象或________映象，以利于实现。

数据构造试题一、单项选择题1、在数据构造的讨论中把数据构造从逻辑上分为〔〕A 部构造与外部构造B 静态构造与动态构造C 线性构造与非线性构造D 紧凑构造与非紧凑构造。

2、采用线性链表表示一个向量时，要求占用的存储空间地址〔〕A 必须是连续的B 局部地址必须是连续的C 一定是不连续的D 可连续可不连续3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为〔〕。

A nB n/2C (n-1)/2D (n+1)/24、在一个单链表中，假设q结点是p结点的前驱结点，假设在q与p之间插入结点s，那么执行〔〕。

A s→link = p→link;p→link = s;B p→link = s;s→link = q;C p→link = s→link;s→link = p;D q→link = s;s→link = p;5、如果想在4092个数据中只需要选择其中最小的5个，采用〔〕方法最好。

A 起泡排序B 堆排序C 锦标赛排序D 快速排序6、设有两个串t和p，求p在t中首次出现的位置的运算叫做〔〕。

A 求子串B 模式匹配C 串替换D 串连接7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。

所有数组元素相继存放于一个连续的存储空间中，那么存放该数组至少需要的存储字数是〔〕。

A 80B 100C 240D 2708、将一个递归算法改为对应的非递归算法时，通常需要使用〔〕。

A 栈B 队列C 循环队列D 优先队列9、一个队列的进队列顺序是1, 2, 3, 4，那么出队列顺序为〔〕。

10、在循环队列中用数组A[0..m-1]存放队列元素，其队头和队尾指针分别为front 和rear，那么当前队列中的元素个数是〔〕。

A( front - rear + 1) %m B ( rear - front + 1) %mC (front - rear + m) %mD ( rear - front + m) %m11、一个数组元素a[i]与〔〕的表示等价。

数据结构(本)(网教)202301-模拟卷注：找到所考试题直接看该试题所有题目和答案即可。

查找按键：Ctrl+F超越高度一、单选题(共10题，20分)1、设循环队列中数组的下标范围是l~n,其头尾指针分别尾f、r,则队列中元素的个数为().A、r-fB、r-f+1C、(r-f+1)modnD、(r-f+n)modn正确答案：D2、以下哪一个不是队列的基本运算？A、从队尾插入一个新元素B、从队列中删除第i个元素C、判断一个队列是否为空D、读取队头元素的值正确答案：B3、有一个有序表｛1,3,9,12,32,41,62,75,77,86,95,100),当二分查找值为86的关键字时,需要比较的次数是()。

A、2B、3C、4D、5正确答案：C4、栈S最多能容纳4个元索。

现有6个元索按A、B、C、D、E、F的顺序进栈,问下列哪一个序列是可能的出栈序列？Λ.E、D、C、B、A、FB.B、C、E、F、A、DC.C、B、E、D、A、FD.A、D、F、E、B、C正确答案：C5、n个顶点的无向连通图至少有()条边。

A、n-1B、nC、n+1D、2n正确答案：A6、设有IOOOO个无序元索,希望用较快速度挑选出其中前15个最大元素,采用()方法最好.A、直接插入排序B、堆排序C、快速排序D、归并排序正确答案：B7、已知一棵二叉排序树,通过()可以得到结点的有序序列。

A、前序遍历B、中序遍历C、后序遍历D、线索化正确答案：B8、S="A;/document/Mary.doc",则的字符定位的位置为().A、2B、3C、12D、11正确答案：B9、假设有60行70列的二维数组a[b∙∙60,1…70]以列序为主序顺序存储,其基地址为10000,每个元索占2个存储单元,那么第32行第58列的元素a[32,58]的存储地址为()。

(无第。

行第0列元素)A、16902B、16904C、14454D、答案A,B,C均不对正确答案：A10、具有36个结点的完全二叉树的深度为()。

一、选择题(单选)1. 关于数据元素，下列描述不正确的是（D）。

A. 数据元素可以包含多个数据项。

B. 数据结构的算法大多以数据元素为基本操作单位。

C. 数据元素一般代表某种现实世界中的对象。

D. 数据元素必须有一个关键字。

2. 循环链表head的尾结点指针p的特点是（A）。

A. p->next=headB. p->next=head->nextC. p=headD. p=head->next3. 设一个栈的输入序列是a,b,c,d,e，则下列序列是栈的合法输出序列的是（D）。

A. e a b c dB. d e a c bC. d c a b eD. c b a e d4. 循环队列存储在数组A[0..m]中，则入队时的队尾指针操作为（D）。

A. rear=rear+1B. rear=(rear+1)%(m-1)C. rear=(rear+1)%mD. rear=(rear+1)%(m+1)5. 在单链表中指针p所指的结点后插入新结点s有下列3个步骤：① s->data=x （赋值）② p->next=s③ s->next=p->next正确的步骤顺序为（B）。

A. ①②③B. ③②①C. ②①③D. 无正确答案6. 对于先序遍历和后序遍历结果相同的二叉树为（B）。

A. 一般二叉树B. 只有根结点的二叉树C. 根结点无左孩子的二叉树D. 根结点无右孩子的二叉树7. 若图的邻接矩阵是对称阵，则此图必然为（B）。

A. 有向图B. 无向图C. 连通图D. 有向图或无向图8. 关于哈夫曼树，下列描述正确的是（D）。

A. 一定是二叉排序树B. 是一棵完全二叉树C. 是一棵平衡二叉树D. 以上三种说法都不对9. 长度为12的按关键字有序的待查找序列，采用顺序存储，若用二分查找，则在等概率情况下，查找成功的ASL是（A ）。

A. 37/12B. 62/13C. 39/12D. 49/1210. 在数据管理技术的发展过程中，经理了人工管理阶段、文件系统阶段和数据库系统阶段。

2022年南京理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。

A.60B.66C.18000D.332、下列排序算法中，占用辅助空间最多的是（）。

A.归并排序B.快速排序C.希尔排序D.堆排序3、以下数据结构中，（）是非线性数据结构。

A.树B.字符串C.队D.栈4、动态存储管理系统中，通常可有（）种不同的分配策略。

A.1B.2C.3D.45、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。

A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)6、下列选项中，不能构成折半查找中关键字比较序列的是（）。

A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4507、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（）。

A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，198、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（）。

A.CBEFDAB.FEDCBAC.CBEDFAD.不定9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。

A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个10、下列二叉排序树中查找效率最高的是（）。

A.平衡二叉树B.二叉查找树C.没有左子树的二叉排序树D.没有右子树的二叉排序树二、填空题11、对单链表中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。

一、选择题1.SQL的数据操纵语言包括__D__。

（数据查询与数据更新合称为数据操纵）A. ROLLBACK ,COMMITB. CREATE,DROP,ALTERC. SELECT,JOIN,PROJECT,UNIND. SELECT,INSERT,DELETE,UPDATE2.数据库DB,数据库系统DBS,数据库管理系统DBMS这三者之间的关系是___A____。

A. DBS包括DB和DBMSB. DBMS包括DB和DBSC. DB包括DBS和DBMS C. DBS就是DB也就是DBMS3、以下关于二维表的论述， B 不正确。

A.表中的每一个元组都是不可再分的B.表中行的次序不可以任意交换，否则会改变关系的性质C.表中各列取自同一个域，且性质相同D.表中的每一行通常称为一个元组4.一个数据库有___B___内模式A. 多个B.一个C. 最多二个D. 多个5、在数据库的三级模式结构中___B__是数据库中全体数据的结构和特征的描述。

A. 外模式B. 模式C. 内模式D. 物理模式6、E-R图是数据库设计的工具之一,它一般适用于建立数据库的___A___。

A. 概念模型B. 结构模型C. 物理模型D. 逻辑模型7、数据库系统中，数据独立性是指 B 。

A．数据之间相互独立 B.应用程序与数据库的结构之间相互独立C.数据的逻辑结构与物理结构相互独立D.数据与磁盘之间相互独立8、基本关系代数运算是 AA. ∪，－，×，π和σB. ∪，－，∞，π和σC.∪，∩，x，π和σD. ∪，∩，∞，π和σ9、关系模型是目前最重要的一种数据模型，它的三个要素分别是 B 。

A.实体完整性、参照完整性、用户自定义完整性B.关系结构、关系操作、完整性约束C.数据增加、数据修改、数据查询D.外模式、模式、内模式10、数据库中的投影操作是指从关系中 A 。

A.抽出特定记录B.抽出特定字段C.建立相应的影像D.建立相应的图形11、设两个关系R（A，B）和S（B，C），与下列SELECT语句SELECT A，BFROM RWHERE B NOT IN（SELECT BFROM SWHERE C='C56'）；等价的关系代数表达式是CA．πA，B （σC≠'C56'（R⋈S））B．πA，B（R ⋈ S）C．R－πA，B （σC= 'C56'（R⋈S））D．R－πA，B（σC≠'C56'（R⋈S））12、关系模式R（A，B，C，D），F是R上成立的函数依赖集，F={ B→D，AD→C }，那么分解C≠'C56'A．是无损联接分解，也是保持FD的分解B．是无损联接分解，但不保持FD的分解C．不是无损联接分解，但保持FD的分解D．既不是无损联接分解，也不保持FD的分解13、12个实体类型，并且它们之间存在着15个不同的二元联系，其中4个是1:1联系类型，5个是1:N联系类型，6个M:N联系类型，那么根据转换规则，这个ER结构转换成的关系模式至少有 B。

2022年南昌理工学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。

A.60B.66C.18000D.332、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

A.13B.33C.18D.403、静态链表中指针表示的是（）。

A.下一元素的地址B.内存储器的地址C.下一元素在数组中的位置D.左链或右链指向的元素的地址4、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l5、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。

A.543612B.453126C.346521D.2341566、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（）。

A．只有e B．有e、b C．有e、c D．无法确定7、下列关于无向连通图特性的叙述中，正确的是（）。

Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ8、在下述结论中，正确的有（）。

①只有一个结点的二叉树的度为0。

②二叉树的度为2。

③二叉树的左右子树可任意交换。

④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A.①②③B.⑦③④C.②④D.①④9、有关二叉树下列说法正确的是（）。

A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为210、对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（）。