一组记录的关键码为(46,79,56,38,40,84)

作业题（一）一、单项选择题1. 从逻辑上可以把数据结构分为（）两大类。

A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构2. 链表不具有的特点是（）A．插入、删除不需要移动元素 B．可随机访问任一元素C．不必事先估计存储空间 D．所需空间与线性长度成正比3.下面程序段的时间复杂度的量级为（）。

For(i=1;i<=n;i++)For(j=1;j<=I;j++)For(k=1;k<=j;k++)X=x+1;A．O(1) B．O(n)C．O(n²) D．O(n³)4.在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。

A．2 B．3C．4 D．65、一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（）。

A．98 B．100C．102 D．1066、判定一个栈s（最多元素为m0）为空的条件是（）。

A．s-〉top! =0 B．s-〉top= =0C．s-〉top! =m0 D．s-〉top= =m07、循环队列用数组A[m]（下标从0到m-1）存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（）。

A．（rear-front+m）%m B．rear-front+1C．rear-front-1 D． rear-front8、设有两个串S1与S2，求串S2在S1中首次出现位置的运算称作（）。

A．连接 B．求子串C．模式匹配 D．判子串9、设串S1='ABCDEFG'，S2='PQRST'，函数con（x，y）返回x和y串的连接串，subs(s,i,j)返回串S的的从序号i的字符开始的j个字符组成的子串，len(s)返回串S的长度，则con(subs(S1,2,len(S2)),subs(S1,len(S2),2))的结果是（）。

习题九排序一、单项选择题1．下列内部排序算法中：A．快速排序 B.直接插入排序C. 二路归并排序D.简单选择排序E. 起泡排序F.堆排序（1）其比较次数与序列初态无关的算法是（）（2）不稳定的排序算法是（）（3）在初始序列已基本有序（除去n 个元素中的某 k 个元素后即呈有序， k<<n）的情况下，排序效率最高的算法是（）（4）排序的平均时间复杂度为O(n?logn)的算法是（）为 O(n?n) 的算法是（）2．比较次数与排序的初始状态无关的排序方法是( )。

A．直接插入排序B．起泡排序C．快速排序D．简单选择排序3．对一组数据（ 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则采用的排序是 ()。

A. 选择B.冒泡C.快速D.插入4．下列排序算法中 ( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。

A. 选择B.冒泡C.归并D.堆5．一组记录的关键码为（46，79，56， 38，40， 84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。

A． (38,40,46,56,79,84) B. (40,38,46,79,56,84)C． (40,38,46,56,79,84) D. (40,38,46,84,56,79)6．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是()排序。

A．冒泡 B. 希尔C. 快速D. 堆7.就平均性能而言，目前最好的内排序方法是() 排序法。

A. 冒泡B.希尔插入C.交换D.快速8.下列排序算法中，占用辅助空间最多的是：()A. 归并排序B.快速排序C.希尔排序D.堆排序9.若用冒泡排序方法对序列 {10,14,26,29,41,52}从大到小排序，需进行（）次比较。

数据结构测试（长春理工大学精品课）第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则采用的排序是( )。

第8 章排序技术课后习题讲解1. 填空题⑴排序的主要目的是为了以后对已排序的数据元素进行（）。

【解答】查找【分析】对已排序的记录序列进行查找通常能提高查找效率。

⑵对n个元素进行起泡排序，在（）情况下比较的次数最少，其比较次数为（）。

在（）情况下比较次数最多，其比较次数为（）。

【解答】正序，n-1，反序，n(n-1)/2⑶对一组记录（54, 38, 96, 23, 15, 72, 60, 45, 83）进行直接插入排序，当把第7个记录60插入到有序表时，为寻找插入位置需比较（）次。

【解答】3【分析】当把第7个记录60插入到有序表时，该有序表中有2个记录大于60。

⑷对一组记录（54, 38, 96, 23, 15, 72, 60, 45, 83）进行快速排序，在递归调用中使用的栈所能达到的最大深度为（）。

【解答】3⑸对n个待排序记录序列进行快速排序，所需要的最好时间是（），最坏时间是（）。

【解答】O(nlog2n)，O(n2)⑹利用简单选择排序对n个记录进行排序，最坏情况下，记录交换的次数为（）。

【解答】n-1⑺如果要将序列（50，16，23，68，94，70，73）建成堆，只需把16与（）交换。

【解答】50⑻对于键值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从键值为（）的结点开始。

【解答】60【分析】60是该键值序列对应的完全二叉树中最后一个分支结点。

2. 选择题⑴下述排序方法中，比较次数与待排序记录的初始状态无关的是（）。

A插入排序和快速排序B归并排序和快速排序C选择排序和归并排序D插入排序和归并排序【解答】C【分析】选择排序在最好、最坏、平均情况下的时间性能均为O(n2)，归并排序在最好、最坏、平均情况下的时间性能均为O(nlog2n)。

⑵下列序列中，（）是执行第一趟快速排序的结果。

A [da，ax，eb，de，bb] ff [ha，gc]B [cd，eb，ax，da] ff [ha，gc，bb]C [gc，ax，eb，cd，bb] ff [da，ha]D [ax，bb，cd，da] ff [eb，gc，ha]【解答】A【分析】此题需要按字典序比较，前半区间中的所有元素都应小于ff，后半区间中的所有元素都应大于ff。

2022年-2023年国家电网招聘之电网计算机题库及精品答案单选题（共40题）1、网络安全控制的主要工作不含（）。

A.定期关闭网络B.查找并消除病毒C.管理局域网外部权限和连接D.管理用户注册和访问权限【答案】 A2、以下关于奇偶校验的叙述中，正确的是（）。

A.奇校验能够检测出信息传输过程中所有出错的信息位B.偶校验能够检测出信息传输过程中所有出错的信息位C.奇校验能够检测出信息传输过程中一位数据出错的情况，但不能检测出是哪一位出错D.偶校验能够检测出信息传输过程中两位数据出错的情况，但不能检测出是哪两位出错【答案】 C3、下列有关 VR（虚拟现实）的描述正确的是（）。

A.所有看到的场景和人物全是假的，是将人的意识带入一个虚拟的世界B.通过合并现实和虚拟世界而产生的新的可视化环境C.通过互联网将现实世界的信息带入虚拟世界中形成的可视化环境D.所看到的场景和人物一部分是真一部分是假，是把虚拟的信息带入到现实世界中【答案】 A4、下列实体类型的联系中，属于一对一联系的是（）A.教研室对教师的所属联系B.父亲对孩子的联系C.省对省会的所属联系D.供应商与工程项目的供货联系【答案】 C5、若一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为()。

A.38，40，46，56，79，84B.40，38，46，79，56，84C.40，38，46，56，79，84D.40，38，46，84，56，79【答案】 C6、计算机的CPU每执行一个()，就完成一步基本运算。

A.程序B.指令C.软件D.算法【答案】 B7、下列四种排序中()的空间复杂度最大。

A.堆排序B.冒泡排序C.插入排序D.归并排序【答案】 D8、我们所说的个人台式商用机属于()A.巨型机B.中型机C.小型机D.微型机【答案】 D9、在下列查找的方法中，平均查找长度与结点个数n无关的查找方法是()。

绪论单元测试1.数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称这为( )。

A:顺序存储结构B:链式存储结构C:存储结构D:逻辑结构答案:A2.算法的时间复杂度取决于（）。

A:问题的可解性B:待处理数据的初态C:问题的复杂度D:问题的规模答案:BD3.从逻辑上可以把数据结构分为( )。

A:非线性结构B:物理结构C:线性结构D:静态结构答案:AC4.除了考虑存储数据结构本身所占用的空间外,实现算法所用辅助空间的多少称为算法的( )。

A:空间效率B:软件效率C:硬件效率D:时间效率答案:A5.链式存储的存储结构所占存储空间( )。

A:分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针B:只有一部分,存储表示结点间关系的指针C:分两部分,一部分存放结点值,另一部分存放指向下一结点的地址D:只有一部分,存放结点值答案:AC6.设语句X++的时间是单位时间,则语句。

for(I=1;I＜=n;I++)x++;的时间复杂度为( )A:O(n3)B:O(n2)C:O(n)D:O(1)答案:C7.对一个算法的评价，不包括如下（）方面的内容。

A:时空复杂度B:健壮性和可读性C:计算性D:并行性答案:CD8.以下数据结构中哪一个是非线性结构 ( )A:二叉树B:队列C:线性表D:栈答案:A9.逻辑结构与数据元素本身的内容和形式无关（）A:对B:错答案:A10.基于某种逻辑结构之上的基本操作，其实现是唯一的。

（）A:对B:错答案:B第一章测试1.非空的循环单链表head的尾结点（由p指向）满足（）。

A:p→next==headB:p==NULLC:p==headD:p→next==NULL答案:A2.带头结点head的单链表为空的判定条件是（）。

A:head-＞next==headB:head-＞next==NULLC:head!==NULLD:head==NULL答案:B3.在长度为n的顺序表的第i个位置上插入一个元素（1≤ i ≤n+1），元素的移动次数为（）。

押题宝典国家电网招聘之电网计算机通关题库(附带答案)单选题（共40题）1、DNS 可以采用的传输层协议是( )。

A.TCPB.UDPC.TCP 或UDPD.NCP【答案】 C2、以下说法不正确的是（）。

A.HTTP 是一种请求/响应式的协议B.HTTP 请求消息中 Accept 表示浏览器可接受的 MIME 类型C.HTTP 请求消息中 Aceept-Encoding 表示浏览器能够进行解码的数据编码方式D.HTTP 请求消息中 CSS 表示初始 URL 中的主机和端口【答案】 D3、克服网络故障问题的最有效的方法是（54）。

A.限制非法操作B.事务跟踪处理C.数据的备份D.数据的安全恢复【答案】 C4、一个查询的结果成为另一个查询的条件，这种查询被称为（）。

A.内查询B.连接查询C.自查询D.子查询【答案】 D5、哪一点不是 RISC 的特点（）A.减少指令的平均执行周期数B.重视编译优化技术C.减少指令和寻址方式的种类D.增加指令的功能【答案】 D6、对一个A类网络，如果指定的子网掩码为255.255.192.0，则该网络被划分为（）个子网。

如果一个公司有2000台主机，则必须给它分配（）个C类网络。

为了使该公司的网络在路由表中只占一行，给它指定的子网掩码必须是（31）。

A.255.192.0.0B.255.240.0.0C.255.255.240.0D.255.255.248.0【答案】 D7、某寄存器中的值有时是地址，这只有计算机的()才能识别它。

A.指令B.时序信号C.译码器D.判断程序【答案】 A8、有关定性风险评估和定量风险评估的区别，以下描述不正确的是（）。

A.定性风险评估比较主观，而定量风险评估更客观B.定性风险评估容易实施，定量风险评估往往数据准确性很难保证C.定性风险评估更成熟，定量风险评估还停留在理论阶段D.定性风险评估和定量风险评估没有本质区别，可以通用【答案】 D9、若一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为()。

第1章单元测试1、算法的时间复杂度取决于___。

答案：A和B2、数据在计算机内存中的表示是指（）答案：数据的存储结构3、算法指的是（）答案：求解特定问题的指令有限序列4、在数据结构中，与所使用的计算机无关的数据结构是（）答案：逻辑7、某线性表采用顺序存储结构,每个元素占4个存储单元,首地址为100,则第12个元素的存储地址为( )。

答案：1448、算法能正确地实现预定功能的特性称为算法的（）。

答案：正确性第2章单元测试1、链表不具备的特点是（）。

答案：可随机访问任意一个结点3、线性表的顺序存储表示优于链式存储表示。

答案：错4、顺序存储结构的缺点是不便于修改,插入和删除需要移动很多结点。

答案：对5、在设头、尾指针的单链表中,与长度n有关的操作是( )。

答案：删除最后一个结点6、设指针q指向单链表中结点A,指针p指向单链表中结点A的后继结点B,指针s指向被插入的结点X,则在结点A和结点B间插入结点X的操作序列为( )。

答案：q->next=s; s->next=p;7、对于只在表的首、尾两端进行插入操作的线性表,宜采用的存储结构为( )。

答案：用尾指针表示的循环单链表8、在一个单链表中,若p所指节点不是最后节点,在p之后插入s所指节点,则执行( )。

答案：s->link=p->link;p->link=s;9、在双向链表存储结构中，删除p所指的结点时须修改指针____。

答案：p->next->prior=p->prior; p->prior->next=p->next;10、若事先不知道线性表的长度,则处理线性表时较好的存储结构是( )。

答案：单链表11、向一个有127个元素的顺序表中插入一个新元素并保存,原来顺序不变,平均要移动( )个元素。

答案：63.512、某线性表采用顺序存储结构,每个元素占4个存储单元,首地址为100,则第12个元素的存储地址为( )。

数据结构查找与排序练习题答案一、选择题1.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/22.适用于折半查找的表的存储方式及元素排列要求为( )A．链接方式存储，元素无序 B．链接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序3.当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( )A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减4．有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（）。

A．35/12 B.37/12 C.39/12 D.43/125.折半查找的时间复杂性为（）A. O（n2）B. O（n）C. O（nlogn）D. O（logn）6.对有18个元素的有序表作折半查找，则查找A[3]的比较序列的下标为（）A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，37.设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找健值为84的结点时，经（）次比较后查找成功。

A.2B. 3C. 4D.128.用n个键值构造一棵二叉排序树，最低高度为（）A.n/2B.、nC.lognD.logn+19．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) A．（100，80， 90， 60， 120，110，130）B.（100，120，110，130，80， 60， 90）C.（100，60， 80， 90， 120，110，130）D.(100，80， 60， 90， 120，130，110)10.设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key% 13,散列地址为1的链中有（）个记录。

2023年国家电网招聘之电网计算机通关题库(附带答案)单选题（共30题）1、中断向量表中保存的是()。

A.被中断程序的返回地址B.中断服务程序入口地址C.中断服务程序入口地址的地址D.中断优先级【答案】 B2、（）是一种只能进行 P 操作和 V 操作的特殊变量。

A.调度B.进程C.同步D.信号量【答案】 D3、在数据系统中，对存取权限的定义称为（）。

A.命令B.授权C.定义D.审计【答案】 B4、以下加密算法中，不属于对称加密算法的是（）。

A.流密码B.IDEAC.DESD.量子密码【答案】 D5、要从某个已知的URL获得一个万维网文档时，若该万维网服务器的lP地址开始时并不知道，需要用到的应用层协议有()。

A.FIP和HTTPB.DNS协议和FTPC.DNS协议和HTTPD.TELNET协议和HTTP【答案】 C6、ARP协议的功能是()。

A.根据IP地址查询MAC地址B.根据MAC地址查询IP地址C.根据域名查询IP地址D.根据IP地址查询域名【答案】 A7、Telnet协议被封装在（请作答此空）协议中，服务端默认侦听的端口号是（）。

A.TCPC.ICMPD.ARP【答案】 A8、将用8位二进制补码表示的十进制数-121，扩展成16位二进制补码，结果用十六进制表示为()。

A.0087HB.FF87HC.8079HD.FFF9H【答案】 B9、IPv6地址长度为( )比特。

A.32B.48C.64D.128【答案】 D10、对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为：A.选择B.冒泡C.快速【答案】 A11、某二叉树的先序和后序序列正好相反，则该二叉树一定是()。

A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子【答案】 B12、表示事务执行成功的语句是（）。

MITB.RETURNC.ROLLBACKD.OK【答案】 A13、设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有 5 个长度为 2 的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（）。

《数据结构》在线作业二
试卷总分:100 得分:100
一、单选题 (共 40 道试题,共 100 分)
1.设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（）。

A.P，A，C，S，Q，D，F，X，R，H，M，Y
B.H，C，Q，P，A，M，S，R，D，F，X，Y
C.F，H，C，D，P，A，M，Q，R，S，Y，X
D.A，D，C，R，F，Q，M，S，Y，P，H，X
答案:B
2.设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（）。

A.5，3，4，6，1，2
B.3，2，5，6，4，1
C.3，1，2，5，4，6
D.1，5，4，6，2，3
答案:B
3.数组的逻辑结构不同于下列（??）的逻辑结构。

A.队列
B.线性表
C.树
D.栈
答案:C
4.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。

A.top=top->next;
B.top=top-1;
C.top=top+1;
D.top->next=top;
答案:A
5.一个有n个顶点的无向图最多有（）条边。

A.n(n-1)/2
B.n(n-1)
C.n
D.2n
答案:A
6.设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为( )。

A.A[7]，A[5] ，A[3]，A[4]
B.A[7]，A[3]，A[5]，A[4]
C.A[1]，A[2]，A[3]，A[4]。

2022年上海海洋大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、将线性表的数据元素进行扩充，允许带结构的线性表是（）。

A.串B.树C.广义表D.栈2、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。

A.NB.2N-1C.2ND.N-13、单链表中，增加一个头结点是为了（）。

A.使单链表至少有一个结点B.标识表结点中首结点的位置C.方便运算的实现D.说明单链表是线性表的链式存储4、下列关于AOE网的叙述中，不正确的是（）。

A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动若提前完成，那么整个工程将会提前完成5、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。

A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改6、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（）。

A．只有e B．有e、b C．有e、c D．无法确定7、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。

假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。

初始时为空，下列判断队空和队满的条件中，正确的是（）。

A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod MB．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1）C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod MD．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）8、每个结点的度或者为0或者为2的二叉树称为正则二叉树。

数据结构作业题作业题（一）一、单项选择题1. 从逻辑上可以把数据结构分为（ c ）两大类。

A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构2. 链表不具有的特点是（ b ）A．插入、删除不需要移动元素 B．可随机访问任一元素C．不必事先估计存储空间 D．所需空间与线性长度成正比3.下面程序段的时间复杂度的量级为（ d ）。

For(i=1;i<=n;i++)For(j=1;j<=I;j++)For(k=1;k<=j;k++)X=x+1;A．O(1) B．O(n)C．O(n²) D．O(n³)4.在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（c）个指针域的值。

A．2 B．3C．4 D．65、一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（ b ）。

A．98 B．100C．102 D．1066、判定一个栈s（最多元素为m0）为空的条件是（b）。

A．s-〉top! =0 B．s-〉top= =0C．s-〉top! =m0 D．s-〉top= =m07、循环队列用数组A[m]（下标从0到m-1）存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（ a ）。

A．（rear-front+m）%m B．rear-front+1C．rear-front-1 D． rear-front8、设有两个串S1与S2，求串S2在S1中首次出现位置的运算称作（c）。

A．连接 B．求子串C．模式匹配 D．判子串9、设串S1='ABCDEFG'，S2='PQRST'，函数con（x，y）返回x和y串的连接串，subs(s,i,j)返回串S的的从序号i的字符开始的j个字符组成的子串，len(s)返回串S的长度，则con(subs(S1,2,len(S2)),subs(S1,len(S2),2))的结果是（ d ）。

全国2018年1月高等教育自学考试数据结构导论试题课程代码：02142一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。

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

每小题2分，共30分)1.下列数据结构中，( )不都是线性结构。

A.栈和队列B.队列和数组C.数组和串D.文件和队列2.为了最快地对线性结构的数据进行某数据元素的读取操作，则其数据存储结构宜采用( )方式。

A.顺序存储B.链式存储C.索引存储D.散列存储3.设双链表中结点的前趋指针和后继指针的域名分别为t1和r1，则删除双链表中指针s所指结点的操作为( )A.s->t1->r1=s->t1;s->r1->t1=s->r1;B.s->t1->r1=s->r1;s->r1->t1=s->t1;C.s->r1=s->t1->r1;s->t1=s->r->t1;D.s->t1=s->t1->r1;s->r1=s->r->t1;4.假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针域，现要把一个指针s所指的新结点作为非空双链表中q所指地点(中间结点)的直接后继结点插入到该双向链表中，则下列算法段能正确完成上述要求的是( )A.q->right=s; s->left=q; q->right->left=s; s->right=q->right;B.s->left=q; q->right=s; q->right->left=s; s->right=q->right;C.s->left=q; s->right=q->right; q->right->left=s; q->right=s;D.以上都不对5.由下列三棵树组成转的森林换成一棵二叉树为( )6.具有100个结点的完全二叉树的深度为( )A.6B.7C.8D.97.已知一个稀疏矩阵的三元组表如下：(1，2，3)，(1，6，1)，(3，1，5)，(3，2，-1)，(4，5，4)，(5，1，-3)，则其转置矩阵的三元组表中第3个三元组为( )A.(2，1，3)B.(3，1，5)C.(3，2，-1)D.(2，3，-1)8.无向图的邻接矩阵是一个( )A.对称矩阵B.零矩阵C.上三角矩阵D.对角矩阵9.下列说法中正确的是( )A.一个具有n 个顶点的无向完全图的边数为n(n-1)B.连通图的生成树是该图的一个极大连通子图C.图的广度优先搜索是一个递归过程D.对于非连通图的遍历过程中每调用一次深度优先搜索算法都得到该图的一个连通分量10.顺序查找法与二分查找法对存储结构的要求是( )A.顺序查找与二分查找均只适用于顺序表B.顺序查找与二分查找既适用于顺序表，也适用于链表C.顺序查找只适用于顺序表D.二分查找只适用于顺序表11.在开散列表上，每个地址单元所链接的同义词表( )A.其键值相同B.其元素值相同C.其散列地址相同D.其含义相同12.散列文件中的记录通常成组存放，若干个记录组成一个存储单位，这个存储单位称为( )A.磁道B.块C.柱面D.桶13.索引非顺序文件中的索引表是( )A.非稠密索引B.稠密索引C.主索引D.多级索引14.对n 个记录的文件进行堆排序，最坏情况下的执行时间为( )A.O(log 2n)B.O(nlog 2n)C.O(n)D.O(n 2)15.一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序方法，以第一个记录为基准得到的一次划分结果为( )A.38，40，46，56，79，84B.40，38，46，79，56，84C.40，38，46，56，79，84D.40，38，46，84，56，79二、填空题（每小题2分，共26分）请在每小题的空格中填上正确答案。

试卷代号：1252中央广播电视大学2012-2013学年度第二学期“开放本科”期末考试一、单项选择题（每小题2分，共30分）1．在C语言中，顺序存储长度为3的字符串，需要占用( )个字节。

A．4 B．3 C．6 D．12 2。

串函数StrCat(a，b)的功能是进行串( )。

A．比较B．复制C．赋值D．连接3．-棵有n个结点采用链式存储的二叉树中，共有( )个指针域为空。

A．n+l B．n C．n-l D．n-2 4．设一棵哈夫曼树共有n个非叶结点，则该树有( )个叶结点。

A．n B．n+l C．n-l D．2n 5．从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结点的值，则执行( )。

A. x=top->data;top=top->next B.x=top->dataC. top= top->next; x=top->dataD.top=top->next;x=data6．一棵完全二叉树共有5层，且第5层上有六个结点，该树共有( )个结点。

A．30 B．20 C．21 D．237．在一个无向图中，所有顶点的度数之和等于边数的( )倍。

^A．O上；．B．3 C．1.5 D．2 8．已知如图1所示的一个图，若从顶点V，出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为( )。

9．已知如图2所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为( )。

A. abcedf B. abcefd C. aebcfd D. acfdeb10.对二叉排序树进行( )遍历，可以使遍历所得到的序列是有序序列。

A．按层次B．后序C．中序D．前序11．在有序表(2，4，7，14，34，43，47，64，75，80，90，97，120)中，用折半查找法查找值80 时，经( )次比较后查找成功。

A．4 B．2 C．3 D．512．有一个长度为9的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为( )。

《数据结构与算法》期末练习一选择题1．以下与数据的存储结构无关的术语是（ D ）。

A．循环队列 B. 链表 C. 哈希表 D. 栈2. 算法的时间复杂度取决于（ A ）A．问题的规模 B. 待处理数据的初态 C. A和B D. 计算机cpu3. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ B ）。

A. 2 3 4 1 5B. 5 4 1 3 2C. 2 3 1 4 5D. 1 5 4 3 24. 有关静态链表的叙述：(1) 静态链表既有顺序存储的优点，又有动态链表的优点。

所以，它存取表中第i个元素的时间与i无关。

(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。

(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。

以上错误的是（ B ）A．（1），（2） B．（1） C．（1），（2）,(3) D.（2）5．对于有n 个结点的二叉树, 其高度为（ D ）A．nlog2n B．log2n C．⎣log2n⎦|+1 D．不确定6．从下列有关树的叙述中,选出正确的叙述（ C ）A．二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。

B．当K≥1时高度为K的二叉树至多有2k-1个结点。

C．哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。

D．在二叉树中插入结点,该二叉树便不再是二叉树。

7．设无向图的顶点个数为n，则该图最多有（ B ）条边。

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n28．已知有向图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 ）。

《数据结构》习题库之一：选择题1.算法分析的目的是（）A.研究算法的输入与输出之间的关系B.找出数据结构的合理性C.分析算法的效率以求改进算法D.分析算法的可读性与可移植性2. 在由list所指的非空线性链表中删除由p指的链结点的下一个链结点的过程是依次执行q=p->link,（）,delete q。

A.p->link=qB.q->link=pC.q->link=p->linkD.p->link=q->link3.依次在初始为空的队列中插入元素为a,b,c,d以后，紧接着作了两次删除操作，此时的队头元素是（）A.aB.bC.cD.d4.若某堆栈的输入序列为 1，2，3，…，n-1，n，输出序列的第1个元素为n，则第i个输出元素为（）A.n-i+1B.n-1C.iD.哪个元素无所谓5.设计递归问题的非递归算法一般需要用到（）机制。

A.数组B.堆栈C.队列D.二叉树6.已知非空二叉树采用顺序存储结构，树中结点的数据信息依次存放在一个一维数组中，即 ABC □DEF□□G□□H□□该二叉树的中序列遍历序列为（）A.G,D,B,A,F,H.C,EB.G,B,D,A,F,H,C,EC.B,D,G,A,F,H,C,ED.B,G,D,A,F,H,C,E7.在一棵度为3的树中，度为3的结点有2个，度为2的结点有1个，度为1的结点有2个，那么，该树有（）个叶结点。

A.4B.5C.6D.78. 向具有n个结点的、结构均衡的二叉搜索树中插入一个元素的时间复杂度大致为（）。

A. O(1)B. O(log2n )C. O(n)D. O(nlog2n)9.在初始为空的散列表中依次插入关键字序列(MON,TUE,WED,THU,FRI,SAT,SUN),散列函数为H(k)=i MOD 7，其中，i为关键字k的第一个字母在英文字母表中的序号，地址值域为 [0:6] ，采用线性再散列法处理冲突。