长沙理工大学《850数据结构》考研专业课真题试卷

长沙理工大学数据结构模拟试卷2一、填空题（每空1分，共10分）1．顺序存储结构中数据元素之间的逻辑关系是由存储位置表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。

2．非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（）。

3．n个顶点的连通图用邻接矩阵表示时，该矩阵至少有（）个非零元素。

4．（）可作为实现递归函数调用的一种数据结构。

5．由权值为{3, 8, 6, 2, 5}的叶子结点生成一棵哈夫曼树，其带权路径长度为（）。

6．设S="I_ am_ a_ teacther"，其长度为（）。

7．稀疏矩阵一般压缩存储方法有两种，分别是（）和（）。

8．分块有序是指将文件划分为若干块，（）无序，（）有序。

二、判断题（你认为正确的请打对，错误的打错。

每题2分，共10分）1．线性表的顺序存储结构优于链接存储结构。

2．B—树是一种动态索引结构，它既适用于随机查找，也适用于顺序查找。

3．在线索二叉树中，任一结点均有指向其前趋和后继的线索。

4．用一维数组存储二叉树时，总是以前序遍历存储结点。

5．在索引顺序表上采用分块查找，在等概率情况下，其平均查找长度不仅与子表个数有关，而且与每一个子表中的对象个数有关。

三、单选题（请把你认为正确的答案填入括号内，每小题1分，共10分）1．假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。

则表示该遗产继承关系的最合适的数据结构应该是（）。

A 树B 图C 线性表D 集合2．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（）结构。

A 栈B队列 C 数组D线性表3．若某线性表经常的操作是取第i 个元素和找第i个元素的前趋，则采用（）存储方法最节省时间。

A 顺序表B 单链表C 双链表D 单循环链表4．广义表(a, b, (c, (d)))的表尾是（）。

长沙理工大学数据结构模拟试卷3一、填空题（每空1分，共10分）1.（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

2.已知线性表A采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144，则第一个元素的地址是（）。

3.数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为（）。

4.设有一个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其存储地址为d，每个元素占1个存储单元，则元素A[8][5]的存储地址为（）。

5.已知广义表LS=(a，(b，c，d)，e)，用Head和Tail函数取出LS中原子b的运算是（）。

6.设高度为h的二叉树上只有度为0和度为2的结点，该二叉树的结点数可能达到的最大值是（），最小值是（）。

7.某二叉树的前序遍历序列是ABCDEFG，中序遍历序列是CBDAFGE，则其后序遍历序列是（）。

8.对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（）。

9.快速排序在（）情况下最不利于发挥其长处。

二、选择题（每题1分，共10分）1.算法指的是（）。

A对特定问题求解步骤的一种描述，是指令的有限序列。

B计算机程序C解决问题的计算方法D数据处理2.链表不具有的特点是（）。

A可随机访问任一元素B插入、删除不需要移动元素C不必事先估计存储空间D所需空间与线性表长度成正比3.设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（）。

A6B4C3D24.设二叉树有n个结点，则其深度为（）。

A n-1B nC log2n+1D不能确定5.一个高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有（）成立。

A n=h+mB h+m=2nC m=h-1D n=2m-16.下面关于工程计划的AOE网的叙述中，不正确的是（）。

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)*((A+B)／/A)，至少需要顶点的数目为（）。

A.5B.6C.8D.93、链表不具有的特点是（）。

A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比4、下列关于AOE网的叙述中，不正确的是（）。

A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动若提前完成，那么整个工程将会提前完成5、已知串S='aaab'，其next数组值为（）。

A.0123B.1123C.1231D.12116、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。

下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。

Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ7、下列叙述中，不符合m阶B树定义要求的是（）。

A．根结点最多有m棵子树 B．所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。

A.107B.108C.214D.2159、有关二叉树下列说法正确的是（）。

A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为210、对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（）。

一、单项选择题：1-40题,每题20分共80分;在每个小题给出的四个选项中选正确答案;1、若元素a、b、c、d、e、f依次进栈,允许进栈、退栈操作交替进行,但不允许连续三次进行退栈工作,则不可能得到的出栈序列是A、dcebfaB、cbdaefC、bcaefdD、afedcb2、某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作,则不可能得到的顺顺序是A、bacdeB、dbaceC、dbcaeD、ecbad3、下列线索二叉树中用虚线表示线索,符合后序线索树定义的是4、在下列所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树,在新平衡二叉树中,关键字37所在结点的左、右子结点中保存的关键字分别是A、13,48B、24,48C、24,53D、24,905、在一棵度数为4的树T中,若有20个度为4的结点,10个度为3的结点,1个度为2的结点,10个度为1的结点,则树T的叶结点个数是A、41B、82C、113D、1226、对nn>=2个权值均不相同的字符构成哈弗曼树,关于该树的叙述中,错误的是A、该树一定是一棵完全二交叉B、树中一定没有度为1的结点C、树中两个权值最小的结点一定是兄弟结点D、树中任一非叶结点的权值一定不小于下一层任一结点的权值7、若无向图G=中含7个顶点,则保证图G在任何情况下都是连通的,则需要的边数最少是A、6B、15C、16D、218、对下图进行拓扑排序,可以得到不同的拓扑序列的个数是A、4B、3C、2D、19、已知一个长度为16的顺序表L,其元素按关键字有序排列,若采用折半查找法查找一个不存在的元素,则比较次数最多的是A、4B、5C、6D、710、采用递归方式对顺序表进行快速排序,下列关于递归次数的叙述中,正确的是A、递归次数于初始数据的排列次数无关B、每次划分后,先处理较长的分区可以减少递归次数勤思考研C、每次划分后,先处理较短的分区可以减少递归次数D、递归次数与每次划分后得到的分区处理顺序无关11、对一组数据2,12,16,88,5,10进行排序,若前三趟排序结果如下：第一趟：2,12,16,5,10,88第二趟：2,12,5,10,16,88第三趟：2,5,10,12,16,88则采用的排序方法可能是A.冒泡排序法B.希尔排序法C.归并排序法D.基数排序法12.下列选项中,能缩短程序执行时间的措施是1.提高CPU时钟频率2.优化通过数据结构3.优化通过程序A.仅1和2B.仅1和3C,仅2和3,2,313.假定有4个整数用8位补码分别表示r1=FEH,r2=F2H,r3=90H,r4=F8H,若将运算结果存放在一个8位寄存器中,则下列运算会发生益处的是A. r1 x r2B. r2 x r3C. r1 x r4D. r2 x r414.假定变量i,f,d数据类型分别为int, float, doubleint用补码表示,float 和double用IEEE754单精度和双精度浮点数据格式表示,已知i=785,f=,d=,若在32位机器中执行下列关系表达式,则结果为真的是I i==intfloatIIIf==floatintfIIIf==floatdoublefIVd+f-d==fA. 仅I和IIB. 仅I和IIIC. 仅II和IIID. 仅III和IV15.假定用若干个2K x 4位芯片组成一个8K x 8为存储器,则0B1FH所在芯片的最小地址是16.下列有关RAM和ROM得叙述中正确的是I RAM是易失性存储器,ROM是非易失性存储器II RAM和ROM都是采用随机存取方式进行信息访问III RAM和ROM都可用做CacheIV RAM和ROM都需要进行刷新A. 仅I和IIB. 仅II和IIIC. 仅I ,II, IIID. 仅II,III,IV17.下列命令组合情况,一次访存过程中,不可能发生的是未命中,Cache未命中,Page未命中未命中,Cache命中,Page命中命中,Cache未命中,Page命中命中,Cache命中,Page未命中18.下列寄存器中,反汇编语言程序员可见的是A.存储器地址寄存器MARB.程序计数器PCC.存储区数据寄存器MDRD.指令寄存器IR19.下列不会引起指令流水阻塞的是A.数据旁路B.数据相关C.条件转移D.资源冲突20.下列选项中的英文缩写均为总线规范的是A. PCI、CRT、USB、EISAB. ISA、CPI、VESA、EISAC. ISA、SCSI、RAM、MIPSD. ISA、EISA、PCI、PCI-Express21、单级中断系统中,中断服务程序执行顺序是I保护现场II开中断III关中断IV保存断点V中断事件处理VI恢复现场VII中断返回A、I->V->VI->II->VIIB、III->I->V->VIIC、III->IV->V->VI->VIID、IV->I->V->VI->VII22、假定一台计算机的显示存储器用DRAM芯片实现,若要求显示分辨率为16001200,颜色深度为24位,帧频为85HZ,现实总带宽的50%用来刷新屏幕,则需要的显存总带宽至少约为A、245MbpsB、979MbpsC、1958MbpsD、7834Mbps23、下列选项中,操作S提供的给应程序的接口是A、系统调用B、中断C、库函数D、原语24、下列选项中,导制创进新进程的操作是I用户登陆成功 II设备分配 III启动程序执行A、仅I和IIB、仅II和IIIC、仅I和IIID、I、II、III25、设与某资源相关联的信号量初值为3,当前值为1,若M表示该资源的可用个数,N表示等待该资源的进程数,则M,N分别是A、0,1B、1,0C、1,2D、2,026、下列选项中,降低进程优先权级的合理时机是A、进程的时间片用完B、进程刚完成I/O,进入就绪列队C、进程长期处于就绪列队D、进程从就绪状态转为运行状态27、进行PO和P1的共享变量定义及其初值为booleam flag2;int turn=0;flag0=false; flag1=false;若进行P0和P1访问临界资源的类C代码实现如下：void p0 33KBB. 519KBC. 1057KBD. 16513KB31. 设当前工作目录的主要目的是A. 节省外存空间B. 节省内存空间C. 加快文件的检索速度D. 加快文件的读写速度32.本地用户通过键盘登陆系统是,首先获得键盘输入信息的程序时A. 命令解释程序B. 中断处理程序C. 系统调用程序D. 用户登录程序33. 下列选项中,不属于网络体系结构中所描述的内容是A.网络的层次B.每一层使用的协议C.协议的内部实现细节D.每一层必须完成的功能34.在下图所表示的采用”存储-转发”方式分组的交换网络中所有的链路的数据传输速度为100Mbps,分组大小为1000B,其中分组头大小为20B若主机H1向主机H2发送一个大小为980000的文件,则在不考虑分组拆装时间和传播延迟的情况下,从H1发送到H2接受完为止,需要的时间至少是B.C.D.35.某自治系统采用RIP协议,若该自治系统内的路由器R1收到其邻居路由器R2的距离矢量中包含的信息<net1,16>,则可能得出的结论是A. R2可以经过R1到达net1,跳数为17B. R2可以到达net1,跳数为16C. R1可以经过R2到达net1,跳数为17不能经过R2到达net136.若路由器R因为拥塞丢弃IP分组,则此时R可向发出该IP分组的源主机的ICMP报文件的类型是A. 路由重定向B. 目的不可达C. 源抑制D. 超时37、某网络的IP地址空间为/24采用长子网划分,子网掩码为,则该网络的最大子网个数、每个子网内的最大可分配地址个数为A、32,8B、32,6C、8,32D、8,3038、下列网络设备中,能够抑制网络风暴的是I中断器II集线器III网桥IV路由器A、仅I和IIB、仅IIIC、仅III和IVD、仅IV39、主机甲和主机乙之间建立一个TCP连接,TCP最大段长度为1000字节,勤思考研若主机甲的当前拥塞窗口为4000字节,在主机甲向主机乙连续发送2个最大段后,成功收到主机乙发送的第一段的确认段,确认段中通告的接收窗口大小为2000字节,则此时主机甲还可以向主机乙发送的最大字节数是A、1000B、2000C、3000D、400040、如果本地域名服务无缓存,当采用递归方法解读另一网络某主机域名时,用户主机本地域名服务器发送的域名请求条数分别为A、1条,1条B、1条,多条C、多条,1条D、多条,多条二、综合应用题：41-47小题,共70分41.10分将关键字序列7、8、30、11、18、9、14散列存储到散列表中,勤思考研散列表的存储空间是一个下标从0开始的一个一维数组散列,函数为：Hkey=key x 3MODT,处理冲突采用线性探测再散列法,要求装载因子为问题：1.请画出所构造的散列表;2.分别计算等概率情况下,查找成功和查找不成功的平均查找长度;42.13分设将nn>1个整数存放到一维数组R中;设计一个在时间和空间两方面尽可能高效的算法;将R中的序列循环左移P0<P<n个位置,即将R中的数据由X0, X1, ……Xn-1变换为Xp, Xp-1 …Xn-1,X0, X1……Xp-1要求：1、给出算法的基本设计思想;2、根据设计思想,采用C或C++或JAVA语言描述算法,关键之处给出注释;3、说明你所设计算法的时间复杂度和空间复杂度;43、11分某计算机字节长为16位,主存地址空间大小为128KB,按字编址;采用字长指令格式,指令名字段定义如下：1512 116 50源操作数目的操作数转移指令采用相对寻址,相对偏移是用补码表示,寻址方式定义如下：注：X表示有存储地址X或寄存器X的内容,请回答下列问题：1、该指令系统最多可有多少指令该计算机最多有多少个通用寄存器勤思教育存储地址寄存器MAR和存储数据寄存器MDR至少各需多少位2、转移指令的目标地址范围是多少3、若操作码0010B表示加法操作助记符为add,寄存器R4和R5得编号分别为100B 何101B,R4的内容为1234H,R5的内容为5678H,地址1234H中的内容为5678H,5678H中的内容为1234H,则汇编语言为addR4,R5 逗号前为源操作符,逗号后目的操作数对应的机器码是什么用十六进制该指令执行后,勤思教育哪些寄存器和存储单元的内容会改变改变后的内容是什么44、12分某计算机的主存地址空间大小为256M,按字节编址;指令Cache分离,均有8个Cache行,每个Cache行大小为64MB,数据Cache采用直接映射方式,勤思教育现有两个功能相同的程序A和B,其伪代码如下：程序A:int a256256; ......int sum_array1{int i, j, sum = 0;for i = 0; i < 256; i++ for j= 0; j < 256; j++ sum += aij;return sum;}程序B:int a256256; ......int sum_array2{int i, j, sum = 0;for j = 0; j < 256; j++ for i= 0; i < 256; i++ sum += aij;return sum;}假定int类型数据用32位补码表示,程序编译时i,j,sum均分配在寄存器中,数组a按行优先方式存放,其地址为320十进制;请回答,要求说明理由或给出计算过程;1、若不考虑用于Cache一致维护和替换算法的控制位,则数据Cache的总容量为多少2、数组元素a031和a11各自所在的主存块对应的Cache行号分别是多少Cache 行号从0开始3、程序A和B得数据访问命中率各是多少哪个程序的执行时间短45、7分假设计算机系统采用CSCAN循环扫描磁盘调度策略,使用2KB的内存空间记录16384个磁盘的空闲状态1、请说明在上述条件如何进行磁盘块空闲状态的经管;2、设某单面磁盘的旋转速度为每分钟6000转,勤思教育每个磁道有100个扇区,相临磁道间的平均移动的时间为1ms.若在某时刻,磁头位于100号磁道处,并沿着磁道号增大的方向移动如下图所示,磁道号的请求队列为50,90,30,120对请求队列中的每个磁道需读取1个随机分布的扇区,则读完这个扇区点共需要多少时间需要给出计算过程;46.8分设某计算机的逻辑地址空间和物理地址空间均为64KB,按字节编址;勤思教育某进程最多需要6页数据存储空间,页的大小为1KB,操作系统采用固定分配局部置换策略为此进程分配4个页框;页号页框号装入时间访问位0 7 130 11 4 230 12 2 200 13 9 160 1当该进程执行到时刻260时,要访问逻辑地址为17CAH的数据;请回答下列问题：1、该逻辑地址对应的页号时多少2、若采用先进先出FIFO置换算法,该逻辑地址对应的物理地址要求给出计算过程;3、采用时钟Clock置换算法,该逻辑地址对应的物理地址是多少要求给出计算过程;设搜索下一页的指针按顺时针方向移动,且指向当前2号页框,示意图如下47、9分某局域网采用CSMA/CD协议实现介质访问控制,数据传输率为100M/S,主机甲和主机已的距离为2KM,信号传播速速时200000M/S请回答下列问题,并给出计算过程;1、若主机甲和主机已发送数据时发生冲突,则从开始发送数据时刻起,到两台主机均检测到冲突时刻为止,最短经过多长时间最长经过多长时间假设主机甲和主机已发送数据时,其它主机不发送数据2、若网络不存在任何冲突与差错,主机甲总是以规范的最长以太数据帧1518字节向主机已发送数据,主机已每成功收到一个数据帧后,立即发送下一个数据帧,勤思教育此时主机甲的有效数据传输速率是多少不考虑以太网帧的前导码答案1-5 D C B C B6-10 A A B A D11-15 A D C B D16-20 A D B A D21-25 A D A C B26-30 A A B B C31-35 C B C A A36-40 C B C A A41、1因为装填因子为,数据总数为7,所以存储空间长度为L = 7/ = 10因此可选T=10,构造的散列函数为Hkey = key3 MOD 10线性探测再散列函数为：Hi = Hkey+ di MOD 10 , di = 1,2,3 (9)因此,各数据的下标为H7 = 73 MOD 10 = 1H8 = 83 MOD 10 = 4H30 = 303 MOD 10 = 0H11 = 113 MOD 10 = 3H18 = 183 MOD 10 = 4H1 = H18 +1 MOD 10 = 5H9 = 93 MOD 10 = 7H14 = 143 MOD 10 = 2所构造的散列表如下：2查找成功的平均查找长度为：ASL1 = 1+1+1+1+2+1+1/7 = 8/7查找不成功的平均查找长度为：ASL2 =7+6+5+4+3+2+1+2+1+1 =42、1建立一个可以放下p个整数的辅助队列,将数组R中的前p个整数依次进入辅助队列,将R中后面的n-p个整数依次前移p个位置,将辅助队列中的数据依次出队,依次放入R中第n-p个整数开始的位置;2使用c语言描述算法如下：void Shiftint pR, int n, int p 题思路：1cache总容量等于cache每一行的容量乘以cache的行数;大家需要注意的是,本题cache总容量分别等于数据cache和指令cache的总和;2分别计算出A031A11的地址的值,然后根据直接映射方式除以cache行的大小,与cache行数求余,所得的余数就是所映射的cache块;3cache的命中率等于访问cache的次数除以cache的次数加上访问内存的次数;本题通过计算得知,命中率高的计算速度快;45、12KB = 210248bit = 16384bit;因此可以使用位图法进行磁盘块空闲状态经管,每1bit表示一个磁盘块是否空闲;2每分钟6000转,转一圈的时间为,通过一个扇区的时间为;根据CSCAN算法,被访问的磁道号顺序为100 à120 à 30à 50 à 90,因此,寻道用去的总时间为：20 + 90 + 20 + 40 1ms = 170ms总共要随机读取四个扇区,用去的时间为： + 4 = = 所以,读完这个扇区点共需要 170ms + = ;46、117CAH 转换为二进制为：0001 0111 1100 1010, 页的大小为1KB,所以页内偏移为10位,于是前6位是页号,所以其页号为0001 01,转换为10进制为5,所以,17CA对应的页号为5;2若采用先进先出置换算法,则被置换出的页号对应的页框号是7,因此对应的二进制物理地址为：0001 1111 1100 1010,转换为16进制位的物理地址为1FCAH;3若采用时钟算法,且当前指针指向2号页框,则第一次循环时,访问位都被置为0,在第二次循环时,将选择置换2号页框对应的页,因此对应的二进制物理地址为：0000 1011 1100 1010,转换为16进制物理地址为0BCAH;47、1当甲乙两台主机同时向对方发送数据时,两台主机均检测到冲突的时间最短：Tmin = 1KM/200000KM/S2 = 10us当一台主机发送的数据就要到达另一台主机时,另一台主机才发送数据,两台主机均检测到冲突的时间最长：Tmax = 2KM/200000KM/S2 = 20us2主机甲发送一帧数据所需的时间为：T1 = 1518B/10Mbps =数据在传输过程中所需的时间：T2 = 2KM/200000KM/S =因此,主机甲的有效数据传输速率为：V= 10MbpsT1/T1+T2 = 10Mbps+ =。

长沙理工大学计算机与通信工程学院2014-2015学年一学期数据结构期末考试试卷(A卷)班级:___________学号:___________姓名:___________得分:___________题号一二三四五六七八九十成绩复核得分阅卷题目部分，(卷面共有32题,100分,各大题标有题量和总分)一、应用题(2小题,共16分)1．已知关键码序列为（Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec），散列表的地址空间为0~16，设散列函数为H(x)=，其中i为关键码中第一个字母在字母表中的序号，采用线性探测法处理冲突构造散列表，并求等概率情况下查找成功的平均查找长度。

2．分析下面各程序段的时间复杂度（1）for (i=0;i<n;i++)for (j=0;j<m;j++)A[i][j]（2）s=0;for (i=0;i<n;i++)for (j=0;j<n;j++)s+=B[i][j];sum=s;（3）T=A；A=B；B=T；二、判断正误(10小题,共20分)1．在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。

2．线性表中的所有元素都有一个前驱元素和后继元素。

（）3．线性表的顺序存储结构比链式存储结构更好。

（）4．线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。

5．在循环队列中无溢出现象。

6．一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D。

7．串的堆分配存储是一种动态存储结构。

8．稀疏矩阵压缩存储后，必会失去随机存取功能。

9．一个有向图的邻接表和逆邻接表中的结点个数一定相等。

10．调用一次深度优先遍历可以访问到图中的所有顶点。

（）三、单项选择题(10小题,共20分)1．在下列链表中不能从当前结点出发访问到其余各结点的是（）。

A．双向链表B．单循环链表 C．单链表D．双向循环链表2．若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为( )。

长沙理工大学计算机与通信工程学院2013-2014学年二学期数据结构期末考试试卷(B卷)班级:___________学号:___________姓名:___________得分:___________题目部分，(卷面共有32题,100分,各大题标有题量和总分)一、应用题(2小题,共16分)1．已知一个AOV网如图所示，写出所有拓扑序列。

2．一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT[0..12]，散列函数为H（key）= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。

二、判断正误(7小题,共14分)1．对链表进行插入和删除操作时不必移动链表中结点。

( )2．非空的双向循环链表中任何结点的前驱指针均不为空。

（）3．顺序队和循环队关于队满和队空的判断条件是一样的。

4．稀疏矩阵压缩存储后，必会失去随机存取功能。

5．如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。

（）6．向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。

（）7．数据的逻辑结构和数据的存储结构是相同的。

三、单项选择题(10小题,共20分)1．在C或C++语言中，一个顺序栈一旦被声明，其占用空间的大小（）。

A．已固定B．不固定C．可以改变D．动态变化2．设用链表作为栈的存储结构则出栈操作（）。

A 必须判别栈是否为满B 必须判别栈是否为空C 判别栈元素的类型D 对栈不作任何判别3．线索二叉树中某结点R没有左孩子的充要条件是（）。

A R.lchild=NULLB R.ltag=0C R.ltag=1D R.rchild=NULL4．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（）。

A 空或只有一个结点B 高度等于其结点数C 任一结点无左孩子D 任一结点无右孩子5．在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( )A．e B．2e C．n2－e D．n2－2e6．G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。

2022年长沙理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。

A.插入B.选择C.希尔D.二路归并2、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为（）。

A.j=r[j].nextB.j=j+lC.j=j->nextD.j=r[j]->next3、以下与数据的存储结构无关的术语是（）。

A.循环队列B.链表C.哈希表D.栈4、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。

A.543612B.453126C.346521D.2341565、下列关于AOE网的叙述中，不正确的是（）。

A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动若提前完成，那么整个工程将会提前完成6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。

A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝27、下列关于无向连通图特性的叙述中，正确的是（）。

Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。

A.107B.108C.214D.2159、每个结点的度或者为0或者为2的二叉树称为正则二叉树。

n个结点的正则二叉树中有（）个叶子。

A.log2nB.（n－1）/2C.log2n+1D.（n＋1）/210、分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（）。

长春理工大学2022年全国硕士研究生统一入学考试自命题试题回忆版学科与专业名称：计算机科学技术学院所有专业考试科目代码与名称：809数据结构一.选择题(每题2分，共40分)1.下列那个存储方式最适合在删除最后一个结点和删除最后一个结点（）。

A.单链表B.循环链表C.双链表D.带尾指针的单链表2.根据⼆叉树的定义可知⼆叉树共有（）种不同的形态。

（）。

A.4B.5C.6D．73.设二叉排序树中有 n 个结点，则在二叉排序树的平均平均查找⼆度为（）。

A.O(n2）B.O(nlog2n）C.O(1）D.O(log2n）4.设某有向图的邻接表中有 n 个表头结点和 m 个表结点，则该图中有（）条有向边。

A.nB.n-1C.mD.m-15.哈夫曼编码6.求时间复杂度7.双向链表指针前插8.选择后缀表达式9.三个结点的二叉树有几种10.循环队列队满条件11. 折半查找的平均查找长度12. 广义表的表尾13. 判断哪一个出栈序列是错误的14. 二叉树的遍历（根据遍历结果求另一种遍历结果）15.冒泡排序交换次数选择题甚至有王道原题，一定要刷好王道的选择题！二.填空题1.稀疏矩阵的压缩存储方法2.完全二叉树最多有多少个结点3.删除节点的操作代码4.求关键活动，注意不要写成关键路径5.四种逻辑结构，两种存储结构6.n个结点二叉链表空链域个数7.带头结点的循环单链表L为空的条件8.评价散列函数优劣的两个条件9.连通图的最小生成树10.加权路径长度填空题，也不难。

三.简答题（60分）1.散列查找，构造哈希表，求查找成功平均查找长度2.根据二叉树的前中遍历序列，画出二叉树并转化为森林。

3. Dijkstra（迪杰斯特拉）算法求最短路径。

4.每一趟的希尔排序结果5. Prime构造最小生成树过程简答题很基础，做好王道习题。

四.编写算法1．求在链表L中L->data的最大值，并返回其值。

（10分）2．设计在链式存储结构上交换⼆叉树中所有结点左右⼆树的算法。

长沙理工考研试题题库及答案模拟试题：长沙理工大学研究生入学考试模拟题一、选择题（每题2分，共20分）1. 下列哪项不是计算机病毒的特征？A. 传染性B. 破坏性C. 免疫性D. 潜伏性答案：C2. 在C语言中，一个整数变量x的声明语句是：A. int x;B. float x;C. double x;D. char x;答案：A3. 根据题目所给的题目信息，以下哪项不是数据库系统的特点？A. 数据共享B. 数据独立性C. 数据安全性D. 数据冗余度高答案：D4. 在操作系统中，进程和程序的区别在于：A. 进程是动态的，程序是静态的B. 进程是静态的，程序是动态的C. 进程和程序没有区别D. 进程是程序的集合答案：A5. 在网络协议中，TCP和UDP的主要区别在于：A. TCP是面向连接的，UDP不是B. TCP不是面向连接的，UDP是C. TCP和UDP都是面向连接的D. TCP和UDP都不是面向连接的答案：A6. 在HTML中，用于插入图片的标签是：A. <img>B. <image>C. <picture>D. <photo>答案：A7. SQL语言中的“GROUP BY”子句用于：A. 对数据进行分组B. 对数据进行排序C. 对数据进行筛选D. 对数据进行连接答案：A8. 在Java中，用于定义类和方法修饰符的是：A. public, private, protectedB. int, float, doubleC. if, else, switchD. try, catch, finally答案：A9. 下列哪个不是面向对象编程的三大基本特征？A. 封装B. 继承C. 多态D. 过程化答案：D10. 在Linux系统中，查看当前路径的命令是：A. pwdB. lsC. cdD. mkdir答案：A二、简答题（每题10分，共30分）1. 请简述网络拓扑结构的分类及其特点。