长春理工大学数据结构2017年真题

数据结构测试（长春理工大学精品课）第9章排序一、选择题1．某内排序方法的稳定性是指( )。

查看答案A．该排序算法不允许有相同的关键字记录B．该排序算法允许有相同的关键字记录C．平均时间为0（n log n）的排序方法D．以上都不对正确答案是D解释：稳定的排序方法指的是若有相同关键字的记录，待排序时在前面的记录排序后仍然排在前面的排序方法。

收起2．下面给出的四种排序法中( )排序法是不稳定性排序法。

查看答案A. 插入B. 冒泡C. 二路归并D. 堆正确答案是D解释：堆排序是不稳定的，交换时有可能把后面的排在前面。

收起3．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。

( )查看答案A．选择排序法 B. 插入排序法 C. 快速排序法 D. 堆排序法正确答案是A解释：简单选择排序是在待排记录中找到最小的和第一个相交换，再在除了第一个排完的以外找个最小的和第二个相交换，依此类推，n个记录的待排序列需要比较（n-1）+（n-2）+......+0=（n-1）*n/2收起4. 对序列{15，9，7，8，20，-1，4，} 用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是查看答案( )A. lB. 4C. 3D. 2正确答案是B 收起5．下列四个序列中，哪一个是堆（）。

查看答案A. 75,65,30,15,25,45,20,10B. 75,65,45,10,30,25,20,15C. 75,45,65,30,15,25,20,10D. 75,45,65,10,25,30,20,15正确答案是C解释：这是一个大根堆，每个结点都比左右孩子小。

收起6．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序是( )。

2022年长春理工大学数据科学与大数据技术专业《计算机组成原理》科目期末试卷B（有答案）一、选择题1、主存储器主要性能指标有（）。

1.存储周期Ⅱ.存储容量Ⅲ.存取时间Ⅳ.存储器带宽A.I、IⅡB.I、IⅡ、IVC. I、Ⅲ、lVD.全部都是2、某SRAM芯片，其容量为512×8位，除电源和接地端外，该芯片引出线的最小数目应该是（）。

A.23B.25C.50D.193、十进制数-0.3125的8位移码编码为（）。

A.D8HB.58HC.A8HD.28H4、假设机器字长为8位（含两位符号位），若机器数DA日为补码，则算术左移一位和算术右移一位分别得（）。

A.B4H EDHB.F4H 6DHC.B5H EDHD.B4H 6DH5、下列关于浮点数加减法运算的叙述中，正确的是（）。

I.对阶操作不会引起阶码上溢或下溢Ⅱ.右归和尾数舍入都可能引起阶码上溢Ⅲ.左归时可能引起阶码下溢IV.尾数溢出时结果不一定溢出A.仅Ⅱ、ⅢB. 仅I、Ⅱ、ⅢC.仅I、Ⅲ、IⅣD. I、Ⅱ、Ⅲ、Ⅳ6、系统总线中的数据线、地址线、控制线是根据（）来划分的。

A.总线所处的位置B.总线的传输方向C.总线传输的内容D.总线的材料7、在（）结构中，外部设备可以和主存储器单元统一编址。

A.单总线B.双总线C.三总线D.以上都可以8、已知计算机A的时钟频率为800MHz，假定某程序在计算机A上运行需要12s。

现在硬件设计人员想设计计算机B，希望该程序在B上的运行时间能缩短为8s，使用新技术后可使B的时钟频率大幅度提高，但在B上运行该程序所需要的时钟周期数为在A上的1.5倍。

那么，机器B的时钟频率至少应为（）能运到所希望的要求。

A.800MHzB.1.2 GHzC.1.5GHzD.1.8GHz9、冯·诺依曼型计算机的设计思想主要有（）。

1.存储程序Ⅱ.二进制表示Ⅲ.微程序方式Ⅳ.局部性原理A. I，ⅢB.Ⅱ，ⅢC.IⅡ，IⅣD.I，IⅡ10、某计算机系统中，假定硬盘以中断方式与处理器进行数据输入/输出，以16位为传输单位，传输率为50KB/s，每次传输的开销（包括中断）为100个CPU时钟，处理器的主频为50MHz，请问硬盘数据传送时占处理器时间的比例是（）。

数据结构测试（长春理工大学精品课）第2章线性表一、选择题1．下述( )是顺序存储结构的优点？查看答案A．存储密度大 B．插入运算方便C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示正确答案为A解释：插入运算和删除运算对于顺序存储结构需要移动大量的数据元素，顺序存储结构对于非线性的逻辑结构表示比较复杂，顺序存储结构中只需要存储数据元素，不像链式结构除了存数据元素还要存储关系，因此顺序存储结构的存储密度比较大。

收起2．下面关于线性表的叙述中，错误的是哪一个？（ )查看答案A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

正确答案是B解释：顺序存储不利于插入删除，需要移动近一半的数据元素。

收起3．线性表是具有n个（）的有限序列（n>0）。

查看答案A．表元素 B．字符C．数据元素 D．数据项解释：根据线性表的定义。

收起4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

查看答案A．顺序表 B．双链表C．带头结点的双循环链表 D．单循环链表正确答案是A解释：顺序存储结构做相应的操作时间复杂度分别为O(1)，O(1)，O(1)因此是最节省时间的。

收起5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

查看答案A．单链表 B．仅有头指针的单循环链表C．双链表 D．仅有尾指针的单循环链表正确答案是D解释：在仅有尾指针的单循环链表做相应操作的时间复杂度为O(1)，O(1)收起6. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。

查看答案A. O(0)B. O(1)C. O(n)D. O(n2)解释：在顺序表的第i个位置插入一个元素平均需移动的元素的个数是[n+(n-1)+......+0]/(n+1)=n/2，因此算法时间复杂度为O（n）。

数据结构测试（长春理工大学精品课）第7章图一、选择题1．设无向图的顶点个数为n，则该图最多有（）条边。

查看答案A．n-1 B．n(n-1)/2C．n(n+1)/2 D．n2正确答案是B解释: n个顶点相互都有关系，即边数最多。

边数=（n-1）+（n-2）+......+0=n(n-1)/2收起2．要连通具有n个顶点的有向图，至少需要（）条边。

查看答案A．n-l B．nC．n+l D．2n正确答案是B解释:有向图要连通边数最少为n条，形成环。

收起3．一个有n个结点的图，最少有（）个连通分量查看答案A．0 B．1C．n-1 D．N正确答案是B解释:图是连通图连通分量最少，即1个。

收起4．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是（）。

查看答案A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7正确答案是A收起5. 关键路径是事件结点网络中（）。

查看答案A．从源点到汇点的最长路径 B．从源点到汇点的最短路径C．最长回路 D．最短回路正确答案是A解释:关键路径是由关键顶点和关键活动组成的。

收起6. 求解最短路径的Floyd算法的时间复杂度为( )。

查看答案A．O（n） B. O（n+c）C. O（n*n）D. O（n*n*n）正确答案是D收起7. 下列说法不正确的是（）。

查看答案A．图的遍历是从给定的源点出发每一个顶点仅被访问一次C．图的深度遍历不适用于有向图B．遍历的基本算法有两种：深度遍历和广度遍历D．图的深度遍历是一个递归过程正确答案是B解释:图的深度遍历同样适用于有向图，算法中每个顶点均出发一次。

数据结构综合测试（⼀）（长春理⼯⼤学精品课）数据结构测试（长春理⼯⼤学精品课）综合测试⼀⼀、选择1.数据结构中,与所使⽤的计算机⽆关的是数据的（）结构。

查看答案A 顺序B 物理C 逻辑D 物理和存储正确答案为C解释：与计算机⽆关的结构是逻辑结构，是⽤户对数据的组织形式，存储时的物理结构才与计算机有关。

收起2.在长度为n的顺序表中插⼊⼀个元素时,等概率情况下的平均移动元素的次数是（）查看答案A （n-1）/2B n/2C n*(n-1)/2D (n+1)/2正确答案为B解释：在往长度为n的线性表中插⼊元素时，位置可以是1,2,3.......n+1，因此移动元素个数为[n+(n-1)+......+0]/ (n+1)=n/2收起3.对于⼀个头指针为H的带头结点的单链表，判定该表为空表的条件是（）。

查看答案A H==NULLB H!=NULLC H→next ==HD H→next==NULL解释：A答案是不带头结点的单链表H为空的判定条件B答案是不带头结点的单链表H不为空的判定条件C答案是带头结点的循环单链表H为空的判定条件收起4.在⼀个顺序表中，若表的第⼀个元素的存储地址是210，每⼀个元素的长度为3，则第5个元素的存储地址是（）。

查看答案A 219B 222C 225D 228正确答案为B解释：第5个元素之前有4个元素，因此地址为210+（4*3）=222收起5.栈S最多能容纳4个元素,现有6个元素按a,b,c,d,e,f的顺序进栈,下⾯序列（）是可能的出栈序列。

查看答案A edcbafB bcefadC cbedafD adfebc正确答案为C解释：堆栈的特点是后进先出，⽽且最多⼊栈4个元素收起6.循环队列⽤数组A[M]存放元素，已知其头尾指针分别为front和rear，则当前队列中的元素个数是（）。

查看答案A rear-front+1B rear-front-1解释：若rear>=front 则元素个数为rear-front 若rear7.已知⼀棵⼆叉树的有35个叶⼦结点，则该⼆叉树⾄少有（）个结点。

数据结构测试（长春理工大学精品课）综合测试二一、选择1.链表不具有的特点是（）查看答案A 可随机访问任一元素B 插入删除不需要移动元素C 不必事先估计存储空间D 所需空间与线性表的长度成正比正确答案为A解释：单链表不能随机访问某个元素，这种存储结构必须采用顺序访问的方式，根据头指针依此才能找到后继元素的地址，以便访问。

收起2.非空的循环单链表head的尾结点p满足（）查看答案A p->next==NULLB p==NULLC p->next==headD p==head正确答案为C解释：循环链表的尾结点的后继应是头结点。

收起3.对稀疏矩阵进行压缩存储是为了（）。

查看答案A 便于进行矩阵运算B 便于输入和输出C 节省存储空间D 降低运算的时间复杂度解释：矩阵采用压缩存储，相同的元素存一次，零元素不存，主要目的是为了节约内存空间，在很多时候为了找到相应元素，需要找到元素和存储位置的对应关系，反而增大了时间复杂度。

收起4.具有15个结点的二叉树的最小深度是（）。

查看答案A 4B 5C 3D 6正确答案为A解释：n个结点的二叉树最小深度应是完全二叉树的深度logn+1，因此n=15时，最小深度是4。

收起5.在有n个叶子结点的哈夫曼树中，其结点总数为（）查看答案A 不确定B 2nC 2n+1D 2n-1正确答案为D解释：赫夫曼树只有度为0和度为2的结点，叶子结点有n个，那么度为2的结点有n-1个，即总结点个数为2n-1个。

收起6.不带权的无向图的邻接矩阵（）。

查看答案A 不一定是对称矩阵B 是对角线元素非零的对称矩阵C 是上三角矩阵D 是对角线元素为零的对称矩阵正确答案为D解释：无向图的邻接矩阵为对称矩阵，又因图中各顶点不包含到自身的关系，因此对角线上元素为0。

收起7.下列排序算法中，（）算法可能会出现下面情况：初始数据有序，化费时间反而最多.查看答案A 堆排序B 冒泡排序C 快速排序D Ｓhell排序正确答案为C解释：对于快速排序每次找到枢轴的位置基本将待排集合对分是最好的情况，如果待排集合基本有序，快速排序算法就退化了，时间复杂度可达到O（n*n）。

1、3个结点可构成棵不同形态的树。

2、利用直接选择排序算法对n个记录进行排序，最坏的情况下，记录交换的次数为。

3、一个图的_______表示法是唯一的，而______表示法是不唯一的。

4、一棵深度为h的满二叉树上的结点总数为，一棵深度为h的完全二叉树上的结点总数的最小值为，最大值为。

5、在一棵完全二叉树中有n个结点，对这些结点按层序编号，若一个结点编号为69，则其双亲编号为，有左孩子的条件是，其左孩子编号为。

6、二维数组M的成员是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要________个字节；M的第8列和第5行共占___________个字节；若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的________元素的起始地址一致。

7、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是________。

8、在线性表的顺序存储中，元素之间的逻辑关系是通过决定的；在线性表的链式存储中，元素之间的逻辑关系是通过_________决定的。

9、n个顶点的连通图的生成树有n-1条边。

10、通常数组只有______给定一组有定义的下标，存取相应的数据__和___给定一组有定义的下标，修改相应数据元素的值_____两种运算，因此常采用__顺序_______来存储数组。

11、3个节点可以构成 5 棵不同形态的二叉树。

12、对于一棵具有n个结点的二叉树，当它为一棵完全二叉树时具有最小高度，即为∟log2n」+1，当它为一棵单支树时具有最大高度，即为n 。

13、在一棵有n个结点的完全二叉树中，对这些结点按层序编号，若一个结点编号为59，则其双亲编号为，若一个结点编号为23，则其有右孩子的条件是。

14、数组M中每个元素的长度是3个字节，行下标i从1到8，列下标j从1到10，从首地址EA开始连续存放在存储器中。

一、选择题（共20分，每题1分）1．从逻辑上可以把数据结构分为两大类,分别是（）。

A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构2.下面给出的四种排序法中( )排序法是不稳定的排序法。

A. 插入B. 冒泡C. 二路归并D. 堆排序3.线性表是具有n个（）的有限序列（n>0）。

A．表元素 B．字符 C．数据元素 D．数据项4.在下面的程序段中，对x的赋值语句的频度为（）FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+50;A． O(2n) B．O(n) C．O(n2) D．O(log2n)5.下述哪一条是顺序存储结构的优点？（）A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示6. 栈是一种（）的线性表。

A. 先进先出B. 后进先出C. 后进后出D. 不分顺序7. 设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。

A. 4，3，1，2，B. 2，1，3，4，C. 1，4，3，2，D. 1，2，4，3，8.双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（）A. p＾.llink:=q; q＾.rlink:=p; p＾.llink＾.rlink:=q; q^.llink:=p^.llink;B. q＾.llink:=p^.llink; p＾.llink^.rlink:=q; q＾.rlink:=p; p^.llink:=q^.rlink;C. q^.rlink:=p; p^.rlink:=q; p^.llink^.rlink:=q; q^.rlink:=p;D. p^.llink^.rlink:=q; q^.rlink:=p; q^.llink:=p^.llink; p^.llink:=q;9．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。

2017《数据结构》期末考试试题及答案2017《数据结构》期末考试试题及答案《数据结构》期末考试试题及答案1 (2)试题1答案 (7)《数据结构》期末考试试题及答案2 (9)试题2答案 (14)《数据结构》期末考试试题及答案3 (16)试题3答案 (21)《数据结构》期末考试试题及答案1⼀、单选题（每题 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进制表⽰。

A．688 B．678 C．692 D．6965.树最适合⽤来表⽰( )。

A.有序数据元素B.⽆序数据元素C.元素之间具有分⽀层次关系的数据D.元素之间⽆联系的数据6.⼆叉树的第k层的结点数最多为( ).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的元素有（）个，A．1 B．2 C．3 D．410.设有6个结点的⽆向图，该图⾄少应有( )条边才能确保是⼀个连通图。

数据结构测试（长春理工大学精品课）第5 章数组和广义表一、选择题1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

查看答案A. 13B. 33C. 18D. 40正确答案是B解释：[i，j]到k的对应关系是k=（i-1）*i/2+j (i>=j)或k=（j-1）*j/2+i (i<j)，将i=8,j=5带入即得答案。

收起2. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（）。

查看答案A. 808B. 818C. 1010D. 1020正确答案是B解释：二维数组是m行n列，行下标和列下标都从1开始，loc[i，j]=首地址+（（i-1）*n+（j-1））*每个数据元素的大小。

收起3. 数组A[0..4,-1..-3,5..7]中含有元素的个数（）。

查看答案A. 55B. 45C. 36D. 16正确答案是B解释：第1维是5，第2维是3，第3维是3。

收起4. 已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（）。

查看答案A. head（tail（tail（L）））B. tail（head（head（tail（L））））C. head（tail（head（tail（L））））D. head（tail(head（tail（tail（L）））)）正确答案是D解释：表头是广义表中第一个元素，表尾是除了表头外剩下元素组成的表。

收起5. 广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（）。

查看答案Head(Tail(Head(Tail(Tail(A)))))A. (g)B. (d)C. cD. d正确答案是D解释：tail（A）=(b,(c,d),(e,(f,g))),再取表尾=（(c,d),(e,(f,g))）再取表头=(c,d)，再取表尾=（d）再取表头=d。

2022年长春理工大学数据科学与大数据技术专业《数据库系统原理》科目期末试卷A（有答案）一、填空题1、在设计局部E-R图时，由于各个子系统分别有不同的应用，而且往往是由不同的设计人员设计，所以各个局部E-R图之间难免有不一致的地方，称为冲突。

这些冲突主要有______、______和______3类。

2、在SELECT命令中进行查询，若希望查询的结果不出现重复元组，应在SEL ECT语句中使用______保留字。

3、关系代数运算中，基本的运算是______________、______________、______________、______________和______________。

4、若事务T对数据对象A加了S锁，则其他事务只能对数据A再加______，不能加______，直到事务T释放A上的锁。

5、在VB 6.0中，已经用Adobel连接到数据库，并已绑定到数据库中的某个关系表，现要通过此控件向表中插入数据，需要用到Adobel.Recordset的_____方法和Update方法，使用Adobel.Recordset的_____方法可以使当前行指针在结果集中向前移动一行。

6、在SQL Server 2000中，某数据库用户User在此数据库中具有对T 表数据的查询和更改权限。

现要收回User对T表的数据更改权，下述是实现该功能的语句，请补全语句。

_____UPDATE ON T FROM User；7、数据仓库是______、______、______、______的数据集合，支持管理的决策过程。

8、数据库系统是利用存储在外存上其他地方的______来重建被破坏的数据库。

方法主要有两种：______和______。

9、数据仓库主要是供决策分析用的______，所涉及的数据操作主要是______，一般情况下不进行。

10、如图所示的关系R的候选码为；R中的函数依赖有；R属于范式。

一个关系R二、判断题11、数据模型的核心构成要素是数据结构。

吉林省专升本考试数据结构分章习题及参考答案———选择题（第一章）1、计算机算法必须具备（）这三个特性。

A、可执行性、可移植性、可扩充性B、可执行性、确定性、有穷性C、确定性、有穷性、稳定性D、易读性、稳定性、安全性2、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。

A、结构B、关系C、运算D、算法3、具有线性结构的数据结构是（）。

A、图B、树C、广义表D、栈4、设数据结构A=(D, R)，其中D={1, 2, 3, 4}，R={r}, r={<I, 2>, <2, 3>,<3,4>, <4,1>}，则数据结构A是( )。

A、线性结构B、树结构C、图D、集合5、数据结构是指()。

A、数据元素的组织形式B、数据类型C、数据存储结构D、数据定义6、给定有n个元素的向量，建立一个有序单链表的时间复杂度是( )。

A、O(1)）B、O(n)C、O(n2)D、O(n*log2n)7、下列程序段的时间复杂度为（）。

x=n;y=0;while(x>=(y+1)*(y+1))y=y+1;A、O(n)B、O(根号n)C、O(1)D、O(n2)8、计算机算法指的是（）.A、计算方法B、排序方法C、解决问题的步骤序列D、调度方法9、（）是具有相同特性数据元素的集合，是数据的子集。

A、数据符号B、数据对象C、数据D、数据结构10、数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为( )。

A、存储结构B、逻辑结构C、链式存储结构D、顺序存储结构11、算法分析的两个主要方面是：A、空间复杂性和时间复杂性B、正确性和简明性C、可读性和文档性D、数据复杂性和程序复杂性12、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：A、存储结构B、逻辑结构C、顺序存储结构D、链式存储结构13、数据结构是一门研究非数值计算的程序设计问题中,数据元素的逻辑结构，数据信息在计算机中的()以及一组相关的运算等的课程。

数据结构（本）期末综合练习期末综合练习一一、单项选择题1．数据的物理结构（ D）。

A．与数据的逻辑结构无关 B．仅仅包括数据元素的表示C．只包括数据元素间关系的表示 D．包括数据元素的表示和关系的表示2．数据元素是数据的基本单位，它（C ）。

A．只能有一个数据项组成B．至少有二个数据项组成C．可以是一个数据项也可以由若干个数据项组成D．至少有一个数据项为指针类型3．从n个数中选取最大元素，（ C ）。

A．基本操作是数据元素间的交换B．算法的时间复杂度是O(n2)C．算法的时间复杂度是O(n) D．需要进行(n+1)次数据元素间的比较4．线性表的顺序结构中，（ C ）。

A．逻辑上相邻的元素在物理位置上不一定相邻B．数据元素是不能随机访问的C．逻辑上相邻的元素在物理位置上也相邻D．进行数据元素的插入、删除效率较高5．以下表中可以随机访问的是（ D ）。

A．单向链表 B．双向链表C．单向循环链表D．顺序表6．带头结点的单向链表为空的判断条件是（ B ）（设头指针为head）。

A．head = =NULL B．head->next= =NULLC．head->next= =head D．head!=NULL7 .设顺序存储的线性表长度为n，对于删除操作，设删除位置是等概率的，则删除一个元素平均移动元素的次数为（ A ）。

A．(n+1)/2 B．n C．2n D．n-i8．线性结构中数据元素的位置之间存在（A ）的关系。

A．一对一B．一对多C．多对多D．每一个元素都有一个直接前驱和一个直接后继9．设top是一个链栈的栈顶指针，栈中每个结点由一个数据域data和指针域next组成，设用x接收栈顶元素，则出栈操作为（A ）。

A．x=top->data;top=top->next; B．top=top->next;x=top->data;C．x=top-> next;top=top-> data; D．top->next =top; x=top->data;10．设顺序存储的线性表长度为n，要删除第i个元素，按课本的算法，当i=（ C ）时，移动元素的次数为3 A．3 B．n/2 C．n-3 D．411．以下说法正确的是（ C ）。

年4月高等教育自学考试全国统一命题考试数据结构试卷（课程代码02331）一、单项选择题（本大题共15小题，每小题2分，共30分）1．下列叙述中，不正确的是A.算法解决的只能是数值计算问题B．同一问题可以有多种不同算法C．算法的每一步操作都必须明确无歧义D.算法必须在执行有限步后结束2．下列关于栈中逻辑上相邻的两个数据元素的叙述中，正确的是A.顺序存储时不一定相邻，链式存储时一定相邻B．顺序存储时不一定相邻，链式存储时也不一定相邻C．顺序存储时一定相邻，链式存储时也一定相邻D.顺序存储时一定相邻，链式存储时不一定相邻3．对带头结点的单循环链表从头结点开始遍历(head为头指针，p=head->next)。

若指针p指向当前被遍历结点，则判定遍历过程结束的条件是A. p=NULLB. Head=HNULLC.p=head D．head!=p4．设栈的入栈序列为1，2，3，4，5，经过入、出栈操作后，可能得到的出栈序列是A.2,3,5,1,4B.4,2,1,3,5C.3,4,1,2,5D.3,4,2,1,5 5．数组A【2][3]按行优先顺序存放，A的首地址为10。

若A中每个元素占用一个存储单元，则元素A[1】[2]的存储地址是A. 10B. 12 C．14 D．156．广义表《a，b)，(c，d》的表尾是A.bB.dC.(c,d)D.((c,d))7.若完全二叉树T包含20个终端结点，则T的结点数最多是A．38 B．39 C．40 D．41f的右指针指向的结点是8A.aB.bC.cD.e9.如图G 是一个含有n 个顶点的强连通有向图，则G 的边数至少是A.n-1B.nC.n*(n+1)/2D.n*(n+1)10.如从顶点a 开始对下图进行广度优先遍历，则不可能得到的遍历序列是A. a,b ，c ，e ，f,dB. a, c, b, e, f, dC ．a ，c ，e ，b ，d ，f D. a, e, b, c, f, d11.下列排序算法中，稳定的是A.堆排序 B ．直接选择排序C ．冒泡排序 D.希尔排序12.下列排序算法中，比较操作的次数与待排序序列初始排列状态无关的是A.快速排序B.直接选择排序C ．冒泡排序 D.直接插入排序13.若对二叉排序树进行遍历，则下列遍历方式中，其遍历结果为递增有序的是A.前序遍历 B ．中序遍历C ．后序遍历 D.按层遍历14.设一组记录的关键字为{12，22，10，20，88，27，54，11}，散列函数为H(key)=key%11， 用拉链法解决冲突，则散列地址为0的链中结点数是A.1B.2C.3D.415.在下面3阶B 树中插入关键字65后，其根结点内的关键字是A. 53 90B. 53C. 90D. 65二、填空题（本大题共10小题，每小题2分，共20分）16.散列方法的基本思想是根据元素的关键字直接计算出该元素的____。

2021年数据结构期末考试题及答案一、选择题(共计50分，每题2分，共25题)1．在数据结构中，从逻辑上可以把数据结构分为 C 。

A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．内部结构和外部结构2．数据结构在计算机内存中的表示是指 A 。

A．数据的存储结构B．数据结构C．数据的逻辑结构 D．数据元素之间的关系3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。

A．逻辑B．存储C．逻辑和存储D．物理4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C 。

A．数据的处理方法B．数据元素的类型C．数据元素之间的关系D．数据的存储方法5．在决定选取何种存储结构时，一般不考虑 A 。

A．各结点的值如何B．结点个数的多少C．对数据有哪些运算D．所用的编程语言完成这种结构是否方便。

6．以下说法正确的选项是 D 。

A．数据项是数据的根本单位B．数据元素是数据的最小单位C．数据结构是带结构的数据项的集合D．一些外表上很不相同的数据可以有相同的逻辑结构7．在以下的表达中，正确的选项是 B 。

A．线性表的顺序存储结构优于链表存储结构B．二维数组是其数据元素为线性表的线性表C．栈的操作方法是先进先出D．队列的操作方法是先进后出8．通常要求同一逻辑结构中的全部数据元素具有相同的特性，这意味着B 。

A．数据元素具有同一特点B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等9．链表不具备的特点是 A 。

A．可随机访问任一结点B．插入删除不需要移动元素C．不必事先估量存储空间D．所需空间与其长度成正比10．假设某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采纳 D 存储方法最节约运算时间。

A．单链表 B．给出表头指针的单循环链表C．双链表 D．带头结点的双循环链表11．需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。

2017《数据结构》期末考试一试题及答案《数据结构》期末考试一试题及答案1..................................... .. (2)试题1答案............................................. ............................................... (7)《数据结构》期末考试一试题及答案2..................................... .. (9)试题2答案............................................. ............................................... (14)《数据结构》期末考试一试题及答案3..................................... (16)试题3答案............................................. ............................................... (21)第1页共23页《数据结构》期末考试一试题及答案 1一、单项选择题（每题2分，共20分）1. 栈和行列的共同特色是( )。

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

4.已知关键字为2,3,5,7,11,13,17,19,23,29，31，37，41，画出平衡二叉树(10分)
4.依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序树。(10分)
5.已知一颗二叉树的层次序列为ABCDEFGH，中序序列为BADCEFHG，求该树的先序遍历和后序线索二叉树。（10）
考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。
一．选择题(每题2分，共30分)
1.以下数据结构中，（ ）是非线性数据结构
A．树 B．字符串 C．队 D．栈
2.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。
A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表
（2） 处理冲突的方法为链地址法。(6分)
2.对下面数据表，写出采用堆排序算法排序的每一趟的结果，并标出数据移动情况。（125，11，22， 34，15，44，76，66，100，8，14，20，2，5，1）。(10)
3.给定一组权值2,3,5,7,11,13,17,19,23,29，31，37，41，试画出用Huffman算法建造的Huffman树。(10)
A．top:=top+1; V [top]:=x B. V [top]:=x; top:=top+1
C. top:=top-1; V [top]:=x D. V [top]:=x; top:=top-1
20.在完全二叉树中，若一个结点是叶结点，则它没（ ）。
A．左子结点 B．右子结点
C．左子结点和右子结点 D．左子结点，右子结点和兄弟结点
A. O(1) B. O（nlog2n） C. O（n） D. O（n2） E. O（n(log2n)2） F. O（log2n）