一、选择题
1.在用_B_表示的机器中零的表示是唯一的。
A．原码B．补码 C．反码 D．阶码
2.存储容量为4K×8位的静态RAM，其引脚的地址线与数据线之和为_C
A．１２ B．８ C．２０ D．１６
3.活动磁头磁盘存储器中，信息写入成读出磁盘是__B__进行的。
A．并行方式 B．串行方式Ｃ．串并方式Ｄ．不同的存储器有不同的方式4.DMA方式__B___
A．既然能用于高速外围设备的信息传送，也就能代替中断方式
B.不能取代中断方式。
C.不能向CPU请求中断处理。
D.采用该方式时，外设与主机处用于串行工作方式
5.采用规格化的浮点数量为3,目的是为了__D__
A.增加数据的表示范围
B.方便浮点运算
C.防止运算时数据溢出
D.增加数据的表示精度
6指令操作所需的数据不可能来自__A___
A.控制存储器
B.指令本身
C.寄存器
D.主存器
7.由于磁盘上的内部同小圆小于外部同心圆，则对外其所存储器的数据量而言，_____
A.内部同心圆大于外部的同心圆
B. 内部同心圆等于外部的同心圆
C.内部同心圆小于外部的同心圆
D.
8.相联存储器是控制____进行录址的存储器。
A.地址指定方式
B.堆栈存取方式
C.内容存取方式
D.地址指定存取方式和堆栈存取方式
9下列叙述中正确的是_____
A.微程序控制方式和硬布线控制方式相同，前者可以使指令的执行速度更快
B.采用微程序控制方式，UPC代替PC
C.控制存储器可用掩膜ROM,EPROM实况
D.控制器生产的所有控制信号号称为微指令
10.下列数中，最小的是___
A.（46）
10 B.(101111)
2
C.(45)
8
D.（01010101）
8421
11.下列存储器中，属于易失性存储器的是_____
A.ROM
B.EPROM
C.RAM
D.EEPROM
12.对表征磁盘存储器的技术指标有下列说法，正确的是_____
A.对于同一个磁盘来说，位密度处处相等。
B.对于同一个磁盘来说，靠近圆心处的位密度比远离圆心出的位密度大。
C.对于同一个磁盘来说，靠近圆心处的位密度比远离圆心出的位密度小。
D.对于同一个磁盘来说，位密度的大小取决于道密度。
13.在下列存储系统的说法中正确的是______
A.由于RAM为易失性存储器，因此在系统中一般不会选择RAM作为主存。
B.为了提高CPU对主存的存取效率，对主存储器的结构组织上可以用多体交叉存储器。
C.动态RAM的存取速率比静态RAM快，但集成度略低于静态RAM。
D.在CACAE和主存的地址映像方法中，直接映像是最灵活的但也是成本最高的一
种。
14.在下列有失中断方式和DMA方式的选择中，不正确的是_____
A.DMA方式和中断方式都是能对系统发生发生的异常情况作出响应，只不过DMA 方式的响应速度快一些。
B.DMA方式和中断方式都是可以完成外设和主机的数据传达的任务
C.CPU对中断的响应是在一条指令周期结束后而对DMA的响应优先级要高于中断方式。
D．中断类型可分为可屏蔽中断和不可屏蔽中断。
15.以下关于SRAM和DRAM的说法中，正确的是_____。
A.SRAM在工作时需要刷新，而DRAM则不需要刷新
B.SRAM的工作速度与DRAM的一样
C.DRAM可以进行容量扩展。而SRAM由于内部电路的原因无法进行容量扩展
D.SRAM和DRAM都是易失性存储器。
16.DMA方式时____之间建立一条直接数据通路
A.I/O设备和主存
B.两个I/O设备
C.I/O设备和CPU
D.CPU和主存
18.在双符号位判断溢出的方案中，出现正溢出时，双符号位应当为______
A.00
B.01
C.10
D.11
19.若用存储器为1K×4位的intel 2114 J构成16K×8位的存储系统，所需的芯片数为____
A.32
B.16
C.8
D.4
20.下列说法不正确的是______
A.变址寻址时，有效数据存放在主存中
B.堆栈是先进后出的随机存储器
C.堆栈指针SP的内容表示当前堆栈内所存储的数据的个数
D.内存中指令的寻址和数据的寻址时交叉进行的
21.操作数地址存放在寄存器的寻址方式称为_____
A.相对寻址方式
B.变址寄存器寻址方式
C.寄存器寻址方式
D.寄存器间接寻址方式
22.计算机所能认识的语言是_____
A.汇编语言
B.机器语言
C.编译语言
D.解释语言
23.1M字节=_____字节。
A.1024
B.10000000
C.210
D.220
24.地址OH是7FFH间的存储空间有____
A.8K
B.4K
C.2K
D.1K
25.16条地址线所需的寻址的范围是____
A.1K
B.128K
C.64K
D.32K
26.按材料分析存储器课分为磁盘存储器、___、程序存储器
A.内存
B.外存
C.半导体存储器
D.只读存储器
27.下列项中哪项不是硬件____
A.存储器
B.键盘
C.显示器
D.操作系统
28.“溢出”一般是指计算机在运算过程中产生的_____
A.数据量超过内存容量
B.文件个数超过磁盘目录区规定的范围
C.数据超过了机器的位所能表示的范围
D.数据超过了变量的表示范围
29.第三代计算机的逻辑原件为______
A.大规模集成电路
B.电子管
C.中小规模集成电路
D.晶体管
30.80286有24条地址线，其所能寻址的范围是____
A.4G
B.1M
C.16M
D.32M
34.下列说法正确的是_____
A.汇编语言就是机器语言
B.计算机的硬件档次对计算机系统的功能强弱有决定性作用
C.1010011进行奇校验后的编码为10100111
D.计算机中只要硬件设备完全，就可以正常工作
二、填空题
1.计算机中主机有两部分构成，他们是CPU和存储器_。
2.A=1010001001,则A对应的十进制数为649_，其所对应的8421码为_289_。
3.在寄存器间接寻址方式中，操作数应在__主存___里。
4.浮点数的右规则为:尾数每右移一位，阶码__加一______。
5.对存储器的容量扩展可分为_______和________
6.通常硬磁盘存储器上的平均寻址时间由两部分构成，为__平均找道时间_和_
平均等待时间 _。
7.在微程序控制中，微程序一般保存在__控制存储器___里。
8.衡量存储器有三个指标，他们分别为__容量，速度，价格___
9.在CPU中，保存当前正在执行的指令的寄存器为___IR___跟踪和保存下条指
令地址的寄存器为__PC__
10.某硬磁盘存储器的转速为3600转/分钟，则该磁盘的平均等待时间为
__1/120____秒。
11.在lache-主存层次结构中，信息传送的单位是_块__，而在主存虚层次中，
信息传送的单位有段和__页_。
12.某静态SRAM，其容量为32K×16位，则该SRAM的地址线有__15___根，数据
线有__16___根。
13.如果采用偶校验，当被校验的数据为011011010时，则所添加的校验位的值
为___0__，如果采用偶校验，则所添加的校验位的值为__1__
14.十进制数据253，其所对应的二进制数等于__11111101__，所对应的8421
码等于_001001010011_。
15.控制器的控制方式有__同步、异步__方式和联合控制方式。
16.设寄存器R中的数值为1000H，地址为1000H的主存单元中存储的内容为
2000H，地址为的主存地址单元中存储的内容为3000H，PC的值为4000H，则如果按照存储器间接寻址，则所访问到的操作数为___2000H___，而日过按照存储器间接寻址1000H，则所访问到的操作数为___3000H ___。
17.沿磁盘半径方向单位长度的磁道数称为___道密度_____，而单位长度磁道上
记录的二进制代码的数位称为___位密度____
18.某计算机采用直接映像lache，lache的命中率为90%，lache的存取时间为
50ns，主存的存取时间为500ns，则平均存取时间为_100ns__。
19.在浮点数中，当数的绝对值太大，以至于大于阶码能表示的数值时，称为浮
点数的_上溢__，当数的绝对值太小，以至于小于阶码所能表示的数值时，称为浮点的__下溢__。
20.寄存器直接寻址操作数在_寄存器__中，寄存器间接寻址操作数在__主存__
中，因此执行指令的速度前者比后者快。
21.在CPU中，保存当前正在执行的指令的寄存器为__IR___保存下条指令的寄
存器为____PC____。
22.信息码为10110011，若采用偶校验，则校验位的值为__0____。
23.一般来说，一条机器指令中包含有_操作码__和__地址码_____。
24.在计算机输入输出系统中。实现输入输出数据传送的方式有程序查询方式、
_DMA方式__、__中断方式_____，通道方式和外围处理机方式。
25.根据信息传送和管理单位不同，虚拟存储器可分为页式虚拟存储器，段式虚
拟存储器和段页虚拟存储器其中，页的长度是_相等__的，段的长度_不等__.
26.软件分为_系统__软件和___应用___软件两大类。
27.对于二进制10010011，如果它是8421码，对应的十进制是__93___如果它是
一整数的原码，对应的十进制值是_19_
28.(11001.0010)
2=( 25.125 )
10
29.1.1000011是整数的原码，它的反码为__1,0111100__,补码为
__1,0111101____，它的十进制真值为( -67 )
10
30.(520.75)
10=（ 1000001000.11 ）
2
=( 208.c )
16
31.(34.3)
16+(2d.1)
16
=( 97.25 )
10
32.一个整数的原码为0,1011010，它的反码为__0,1011010__，补码为
__0,1011010___，其十进制真值为（ 90）
10
，转化为八进制=（132 ）
8
33.美国标准信息交换码是__7__位二进制编码，共有__128___个优码。
34.___CPU____和__存储器_______，习惯上称为主机。
三、计算题
1.一个磁盘存储器共有8个盘片，每面有204条磁道，每条磁道有12个扇区，
每个扇区可存储512B，磁盘机的转速为7200转/分钟，平均找道时间为8ms （1）计算该磁盘存储器的存储容量。
（2）计算噶磁盘机的平均寻址时间。
12*512*204*（8*2-2）=
解；（1）存储容量=每磁道存储容量*磁道数*存储面数
每磁道存储数=512*12=6144
磁道数=204*（8*2-2）=2856
存储量=2856*6144=1.75*10^7B
（2）平均寻址时间=平均找道时间+平均等待时间
平均等待时间=7200/60=120转/秒
转一圈1/120S 半圈1/240S 即平均等待时间为1/240S
又 8ms=8*10^-3
所以平均寻址时间=8*10^-3+1/240=0.01211s
2．某计算机有变址寻址、间接寻址等寻址方式，设当前指令的地址码部分为001AH，正在执行的指令所在的地址为1F05H,变址寄存器中的内容为23AOH，其中代表16十制数，并已知存储器的部分地址及相应内容如下表
（1）假设当前指令为取数指令，若其为变址寻址方式，则取出的数为多少？（2）假设当前指令为取数指令，若其为一次间接寻址方式，则取出的数为多少？地址内容
001AH 23AOH
1F05H 2400H
1F1FH 2500H
23AOH 2600H
23BAH 1748H
解；（1）001AH+23A0H=23BAH
所以在变址方式中，取出的数为1748H
（2）一次间接寻址方式，则取出的数为2600H
3.已知【X】补=1,1101101，求【-X】补，【X】反，【X】原及真值X。
解；【X】原=1.0010011
【X】反=1.1101100
【X】真值=-0010011
【-X】补=0.0010011
5.已知X=0.1101，Y=-0.1011，试用双符号位补码运算方法，计算X+Y的结果，并判断结果是否溢出。
解；【X】补=0.1101 【Y】补=1.0101
由双符号位运算得 00.1101
+ 11.0101
100.0010
可得X+Y的结果为00.0010.没有溢出
四、简答题
简述冯·诺计算机的特点。
一、计算机由运算器，控制器，存储器，输入设备和输出设备与部分组成
二、采用存储程序的方式，程序和数据放在同一个存储器中，并以二进制码表示
三、指令由操作码和地址码组成
四、指令在存储器中按执行的指令所在的存储单元地址，一般按顺序递增，但可按运算结果或外界条件改变
五、机器以运算器为中心，输入输出设备与存储器间的数据传送都通过运算器。
一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结 点，则执行( )。 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.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具 有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题（每题 6 分，共24分） 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N（M：N）的联系时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度 为_________，在表尾插入元素的时间复杂度为____________。
第一章绪论 一、单项选择题 1．数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和操作等的学科。 ① A.操作对象 B．计算方法 C·逻辑存储 D.数据映象 ② A.结构 B．关系 C．运算． D.算法 2．数据结构被形式地定义为（D，R），其中D是①的有限集合，R是D上的②有限集合。 ① A.算法 B.数据元素 C．数据操作 D．逻辑结构 ② A.操作 B.映象 C、存储 D.关系 3．在数据结构中，从逻辑上可以把数据结构分成（）。 A.动态结构和静态结构 B．紧凑结构和非紧凑结构 C.线性结构和非线性结构 D．内部结构和外部结构 4·算法分析的目的是①，算法分析的两个主要方面是②。 ① A. 找出数据结构的合理性 B．研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ② A. 空间复杂性和时间复杂性 B．正确性和简明性 C．可读性和文档性 D．数据复杂性和程序复杂性 5．计算机算法指的是①，它必具备输入、输出和②等五个特性。 ① A. 计算方法 B．排序方法 C. 解决问题的有限运算序列 D．调度方法 ② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D．易读性、稳定性和安全性 6. 线性表的逻辑顺序与存储顺序总是一致的，这种说法（）。 A. 正确 B．不正确 7. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。 A. 必须是连续的 B．部分地址必须是连续的 C. 一定是不连续的 D. 连续或不连续都可以 8．数据结构通常是研究数据的（）及它们之间的相互联系。 A．存储和逻辑结构 B．存储和抽象 C．理想与抽象 D．理想与逻辑 9．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（）。
数据结构复习资料 一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。 2. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。 3. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。 5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 6．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。 7. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。 9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。 10. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。 11. 一个算法的效率可分为时间效率和空间效率。 12. 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。 13. 线性表中结点的集合是有限的，结点间的关系是一对一的。 14. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素。 15. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i 个元素。 16. 在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。 17. 顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的元素的物理位置不一定相邻。 18．在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。 19．在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。 20. 向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。
2017年数据结构期末考试题及答案 一、选择题（共计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. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点
1. 快速排序在最坏情况下的时间复杂度为（ D ）。 A．O(log 2n) B．O(nlog 2 n) C．O (n) D. O (n2) 2．设一棵二叉树的深度为k，则该二叉树中最多有（ D ）个结点。 A. 2k-1 B. 2k C.2k-1 D. 2k-1 3．二叉树中第i(i≥1)层上的结点数最多有（ C ）个。 A. 2i B. 2i C. 2i-1 D. 2i-1 4．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（ A ）。 A. p->next=p->next->next B. p=p->next C. p=p->next->next D. p->next=p 5．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（ C ）。 A. 6 B. 4 C. 3 D. 2 6.设有以下四种排序方法，则（ B ）的空间复杂度最大。 A. 冒泡排序 B. 快速排 C. 堆排序 D. 希尔排序7．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（ B ）。 A. 3 B. 4 C. 5 D. 1 8．根据二叉树的定义可知二叉树共有（ B ）种不同的形态。 A. 4 B. 5 C. 6 D. 7 9．对一个算法的评价，不包括如下（ A ）方面的内容。 A．并行性 B．健壮性和可读性 C．正确性 D．时空复杂度10．在二叉排序树中插入一个结点的时间复杂度为（ C ）。 A．O(1) B．O(n) C．O(log 2 n) D．O(n2)
复习一 一、填空： 1、抽象数据类型的三要素是，，。 2、队列是。 3、线索二叉树是 。 4、数据的逻辑结构是。 5、在大根堆中，关键值最大的元素是。 6、在记录集{2、5、 7、10、14、15、1 8、20、22}中，进行二分查找，若要查找 元素18，共需要比较次关键字。 7、分层依次将一棵有n个结点的完全二叉树的所有结点从1到n编号，那么树 的深度为。 8、在一个长度为 n 的顺序表中第 i 个位置插入新元素时，需向后移动元素个 数是。 9、在直接插入排序中使用监视哨的作用是。 10、在含n 个顶点和 e 条边的无向图的邻接矩阵中，零元素的个数为。 二、判断题（正确在题后括号内划“√”，错误划“×”） 1、在拓扑排序中，拓扑序列的第一个顶点必定是出度为零的顶点。（） 2、算法DFS应用于一个带权连通图时，所经过的边形成一棵最小生成树。（） 3、（101，88，46，70，34，39，45，58，66，10）是堆。（） 4、n个结点的树的各结点度数之和为n-1。（） 5、由二叉树的前序序列和中序序列能唯一确定一棵二叉树。（） 6、有向图中一个顶点i的出度等于其邻接矩阵中第i列的非0元素的个数。（） 7、哈夫曼树的带权路径长度WPL等于各叶子结点的带权路径长度之和（） 8、所谓冲突即是两个关键字的值不同的元素，其散列地址相同。（） 9、设一个9阶的上三角矩阵A 按列优先顺序压缩存储在一维数组B 中，其中 B[1] 存储矩阵中第一个元素a[1,1], 则B[5] 中存放的元素是a[2,3]。（） 10、在串S ="structure" 中，以 t 为首字符的子串有 8个。（） 三、求解与简答题： 1、以数据集{2，6，13，17，20，30}为叶子结点的权值。（1）构造一棵哈夫曼
复习提纲 第一章数据结构概述 基本概念与术语（P3） 1．数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科. 2．数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合 2．数据元素是数据的基本单位 3．数据对象相同性质的数据元素的集合 4．数据结构包括三方面内容:数据的逻辑结构.数据的存储结构.数据的操作. （1）数据的逻辑结构指数据元素之间固有的逻辑关系. （2）数据的存储结构指数据元素及其关系在计算机内的表示 ( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等. 5.时间复杂度分析 -------------------------------------------------------------------------------------------------------------------- 1、名词解释：数据结构、二元组 2、根据数据元素之间关系的不同，数据的逻辑结构可以分为 集合、线性结构、树形结构和图状结构四种类型。 3、常见的数据存储结构一般有四种类型，它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。 4、以下程序段的时间复杂度为___O(N2)_____。 int i,j,x; for(i=0;i
第二章算法分析 1.算法分析是计算机科学的基础 2.增长函数表示问题（n）大小与我们希望最优化的值之间的关系。该函数表示了该算法的时间复杂度或空间复杂度。增长函数表示与该问题大小相对应的时间或空间的使用 3.渐进复杂度：随着n的增加时增长函数的一般性质，这一特性基于该表达式的主项，即n 增加时表达式中增长最快的那一项。 4.渐进复杂度称为算法的阶次，算法的阶次是忽略该算法的增长函数中的常量和其他次要项，只保留主项而得出来的。算法的阶次为增长函数提供了一个上界。 5.渐进复杂度：增长函数的界限，由增长函数的主项确定的。渐进复杂度类似的函数，归为相同类型的函数。 6.只有可运行的语句才会增加时间复杂度。 7. O() 或者大O记法：与问题大小无关、执行时间恒定的增长函数称为具有O（1）的复杂度。 增长函数阶次 t(n)=17 O(1) t(n)=3log n O(log n) t(n)=20n-4 O(n) t(n)=12n log n + 100n O(n log n) t(n)=3n2+ 5n - 2 O(n2) t(n)=8n3+ 3n2O(n3) t(n)=2n+ 18n2+3n O(2n) 8.所有具有相同阶次的算法，从运行效率的角度来说都是等价的。 9.如果算法的运行效率低，从长远来说，使用更快的处理器也无济于事。 10.要分析循环运行，首先要确定该循环体的阶次n，然后用该循环要运行的次数乘以它。（n 表示的是问题的大小） 11.分析嵌套循环的复杂度时，必须将内层和外层循环都考虑进来。 12.方法调用的复杂度分析： 如：public void printsum(int count){ int sum = 0 ; for (int I = 1 ; I < count ; I++) sum += I ; System.out.println(sun); } printsum方法的复杂度为O（n）,计算调用该方法的初始循环的时间复杂度，只需把printsum方法的复杂度乘以该循环运行的次数即可。所以调用上面实现的printsum方法的复 杂度为O（n2）。 13指数函数增长> 幂函数增长> 对数函数增长
第5章数组与广义表 一、选择题（每小题1分，共10分） 1.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ A ）。 A.110 B.108 C.100 D.120 2.在数组A中，每一个数组元素A[i][j]占用3个存储字节，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字节数是（ C ）。 A.80 B.100 C.240 D.270 3.假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为（ C ）。（无第0行第0列元素） A.16902 B.16904 C.14454 D.答案A, B, C均不对 4.将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（ A ）。 A. 198 B. 195 C. 197 D.196
5.数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是（ A ）。 A. 1175 B. 1180 C. 1205 D. 1210 6.假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]= （ B ）。 A. 808 B. 818 C. 1010 D. 1020 7. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为（ B ）。 A. BA+141 B. BA+180 C. BA+222 D. BA+225 8.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ B ）。 A、 13 B、 33 C、 18 D、 40 9. 二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（ B ）的起始地址相同。设每个字符占一个字节。 A、 A[8,5] B、 A[3,10] C、 A[5,8] D、 A[0,9]
第一章数据结构概述 基本概念与术语 1．数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。 2.数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。 （补充：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。）3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。（有时候也叫做属性。） 4．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 （1）数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。 数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。 依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种： 1.集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。 2.线性结构：结构中的数据元素之间存在“一对一“的关系。若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。 3.树形结构：结构中的数据元素之间存在“一对多“的关系。若数据为非空集，则除了第一个元素（根）之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。 4.图状结构：结构中的数据元素存在“多对多”的关系。若结构为非空集，折每个数据可有多个（或零个）直接后继。 （2）数据的存储结构：数据元素及其关系在计算机的表示称为数据的存储结构。 想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为以下两种存储结构： 1.顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。 2.链式存储结构：借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物理位置上也相邻。 5.时间复杂度分析：1.常量阶：算法的时间复杂度与问题规模n无关系T(n)=O(1) 2.线性阶：算法的时间复杂度与问题规模n成线性关系T(n)=O(n) 3.平方阶和立方阶：一般为循环的嵌套，循环体最后条件为i++ 时间复杂度的大小比较： O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n ) 一．是非题 （正确的打“√”，错误的打“×”。） 1. 数据结构可用三元式表示（D，S，P）。其中：D是数据对象，S是D上的关系， P是对D的基本操作集。× 2. 线性表的链式存储结构具有可直接存取表中任一元素的优点。× 3. 字符串是数据对象特定的线性表。 4. 二叉树是一棵结点的度最大为二的树。× 5．邻接多重表可以用以表示无向图，也可用以表示有向图。× 6．可从任意有向图中得到关于所有顶点的拓扑次序。× 7．一棵无向连通图的生成树是其极大的连通子图。× 8．二叉排序树的查找长度至多为log2ｎ。× 9．对于一棵m阶的B-树.树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有┌m/2┐个关键字。× 10．对于目前所知的排序方法，快速排序具有最好的平均性能。 11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。× 12. 二维数组是其数据元素为线性表的线性表。 13. 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。× 14. 折半查找不适用于有序链表的查找。 15. 完全二叉树必定是平衡二叉树。 16. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。 17. 队列是与线性表完全不同的一种数据结构。× 18. 平均查找长度与记录的查找概率有关。 19. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。× 20. 算法的时间复杂性越好，可读性就越差；反之，算法的可读性越好，则时间复杂性就越差。× 二．选择题 1. 若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到 ( e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1 2. 递归程序可借助于( b )转化为非递归程序。 a:线性表 b: 栈 c:队列 d:数组 3. 在下列数据结构中( c )具有先进先出（FIFO）特性， ( b )具有先进后出(FILO）特性。 a:线性表 b:栈 c:队列 d:广义表 4. 对字符串s=’data-structure’ 执行操作replace(s,substring(s,6,8),’bas’) 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） 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） 9.对一组数据（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则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序 栈和队列 1.有5 个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即 C第一个且D第二个出栈）的次序有哪几个？ 2.栈S和队列Q的初始状态皆为空,元素a1,a2,a3,a4,a5和a6依次通过S栈，一个元素出栈后即进 入队列Q，若6个元素出队列的顺序是a3,a5,a6,a4,a2,a1，则栈S至少应该容纳个元素。 3.在作进栈运算时,应先判别栈是否(①),在作退栈运算时应先判别栈是否(②)。当栈中元素为n个, 作进栈运算时发生上溢,则说明该栈的最大容量为(③)。 为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的(④)分别设在这片内存空间的两端,这样,当⑤)时，才产生上溢。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶 D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点. B. 其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 4.若用一个大小为8的数组来实现循环队列，且当前rear和front的值分别为0和5，当从队列中删 除一个元素，再加入两个元素后，rear和front的值分别为多少？( ) 5.循环队列引入原因，循环队列如何判断队空队满 6.循环队列也存在空间溢出问题。 7.栈的特点是（①）,队列的特点是（②）,栈和队列都是（③）。若进栈序列为1,2,3,4 则（④）不可能是一个出栈序列（不一定全部进栈后再出栈）；若进队列的序列为1,2,3,4 则（⑤）是一个出队列序列。 ①, ②: A. 先进先出 B. 后进先出 C. 进优于出 D. 出优于进 ③: A.顺序存储的线性结构 B.链式存储的线性结构 C.限制存取点的线性结构 D.限制存取点的非线性结构 ④, ⑤: A. 3,2,1,4 B. 3,2,4,1 C. 4,2,3,1 D. 4,3,2,1 F. 1,2,3,4 G. 1,3,2,4 线性表 1.若有100个学生，每个学生有学号，姓名，平均成绩，采用什么样的数据结构最方便，写出这些结 构？ 2.线性表有两种存储结构：一是顺序表，二是链表。试问： （1）如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？ （2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？ 3.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为 （）(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 4.顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( ) 5.线性表的特点是每个元素都有一个前驱和一个后继。( ) 6.链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 广东创新科技职业学院期末考试试题（标明A 卷、B 或C 卷） 2018 —2019 学年第二学期考试科目：《数据结构》 (闭（开）卷 90分钟) 院系____________ 班级____________ 学号___________ 姓名 __________ 一、选择题（每小题 2 分，共 40 分） 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. 下述程序段①中各语句执行频度的和是（）。 s=0; ① for(i=1;i<=i;j++) s+=j; A ．n-1 B ．n C ．2n-1 D ．2n 7. 下面程序段的时间复杂度为（）。 for(i=0;i 一、选择题 1、一个n个顶点的无向连通图，其边的个数至少为（）。 A．n-1 B．n C．n+1 D．nlogn 2、以下数据结构中，（）是非线性数据结构。 A．树B．字符串C．队列D．栈 3、在长度为n的顺序表的第i个位置上插入一个元素（1≤i≤n+1），元素的移动次数为（）。 A．n –i+1 B．n –i C．i D．i-1 4、与线性表的链接存贮不相符合的特性是（）。 A．便于插、删运算B．需要连续的存贮空间 C．只能顺序查找D．存贮空间动态分配 5、顺序存放的循环队列的元素以数组A[m]存放,其头尾指针分别为front和rear，则当前队列中的元素个数 为（）。 A．(rear-front+m)%m B．rear-front+1 C．(front+rear+m)%m D．(rear-front)%m 6、一个有n个顶点的无向图最多有( )条边。 A．n(n-1)/2 B．n (n-1) C．n-1 D．n+1 7、设栈的入栈序列是1，2，3，4，则（）不可能是其出栈序列。 A．1，2，4，3 B．2，1，3，4 C．1，4，3，2 D．4，3，1，2， 8、从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构B．初等结构、构造型结构 C．线性结构、非线性结构D．树型结构、图型结构 9、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（） A．空或只有一个根结点B．高度等于其结点数 C．任一结点无左孩子D．任一结点无右孩子 10、已知一个有向图用邻接矩阵表示，要删除所有从第i个结点发出的边，应该（）。 A．将邻接矩阵的第i 行删除B．将邻接矩阵的第i 行元素全部置零 C．将邻接矩阵的第i 列删除D．将邻接矩阵的第i 列元素全部置零 11、算法分析的两个主要方面是（） A．空间复杂性和时间复杂性B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 12、线性表若采用链式存储结构时，要求内存中可用存储单元的地址( )。 A．必须是连续的B．部分地址必须是连续的 C．一定是不连续的D．连续或不连续都可以 13、具有6个顶点的无向连通图的生成树应有（）条边。 A．5 B．6 C．7 D．8 14、设栈的输入序列是A、B、C，则（）不可能是其出栈序列。 A．CBA B．CAB C．BCA D．ACB 15、有一个含头结点的单链表，头指针为head，则判断其是否为空的条件为（）。 A．head==NULL B．head->next==NULL C．head->next== head D．head ！=NULL 16、栈和队都是（） A．顺序存储的线性结构B．链式存储的非线性结构 C．限制存取点的线性结构D．限制存取点的非线性结构 17、在下述结论中，正确的是（） ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换; ④深度为K的完全二叉树结点个数小于或等于深度相同的满二叉树。 A．①②③B．②③④C．②④D．①④ 18、以下数据结构中，（）是非线性数据结构。 第一章概论 一、选择题 1、研究数据结构就是研究（Ｄ）。 Ａ. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D．数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是（Ａ）。 A．空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D．数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。(线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继)（链表、栈、队列、数组、串） A. 图Ｂ. 树??C．广义表(线性表的推广) D．栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、（ B ）等5个特性。 Ａ．可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C ）。 for(i=0；i 贵州大学理学院数学系信息与计算科学专业 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 一、单项选择题 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。 for(i=n-1；i>=0；i--) for(j=0；j 数据结构习题 一、名词解释 1. 数据、数据元素、数据项、数据结构、数据的逻辑结构、数据物理结构、顺序存储、链式存储、 算法、时间复杂度、空间复杂度。 2. 线性表、顺序表、单链表、双向链表、循环链表、双向循环链表、三个概念的区别：头 指针、头结点、首元结点（第1个元素结点）。 3. 栈（顺序栈、链栈）、队列（顺序队、链队）、循环队列、递归、稀疏矩阵、三元组。 4. 树、叶子结点、结点的度、树的度、树的高（深）度、二叉树、遍历、满二叉树、完全二叉树、哈夫曼树、WPL哈夫曼编码。 5. 图（有向、无向）、网、边、弧、度、入度、出度、完全图（有向、无向）、（强）连通图（分量）、 （最小）生成树、邻接矩阵、邻接表、DFS BFSO 6. 查找表、关键字、静态查找、动态查找、ASL、顺序查找、折半查找、分块查找、二叉排序树。 7. 排序、内（外）排序、稳定性、插入（直接、希尔），交换（起泡、快速），选择（直接、堆），2 路归并。 一、填空题 1. 数据结构是研究数据的 _逻辑结构_和—物理结构_ ,并在这种结构上定义相关的运算，设计实 现这些运算的算法，分析算法的效率。算法的效率包括时间和空间两个方面，分别称为—时间复杂度和空间复杂度—。 2. 数据的基本单位是数据元素，数据的最小单位是数据项。 3. 算法是对特定问题求解—步骤___的一种描述，是指令的有限序列。 4. 一个算法的时间复杂度为（3n3+2n — 7）,其数量级表示为_0 （ n3） __。 5. 一个算法具有5个特性：_确定性、—可行性_、_有穷性_、输入和输出。 6. 算法性能的分析和度量，可以从算法的时间复杂度一和—空间复杂度—来评价算法的优劣。 7. 数据的逻辑结构包括集合结构、_线性结构 _、—树形结构_和_图型结构—四种类型。 8. 数据结构在计算机中的表示称为数据的物理结构，它可以采用 _顺序存储_ 或_链式存储_ 两种存储方法。 9. 线性表有两种存储结构，分别为_顺序存储 _ 和___________ 链式存储_。 10. 链式存储的特点是利用指针—来表示数据元素之间的逻辑关系。 11. 若频繁地对线性表进行插入和删除操作，该线性表宜采用链式存储—存储结构。 12. 线性表中的数据元素之间具有 _一对一_的线性关系，除第一个和最后一个元素外，其他数据元素有且只有 一个_直接后继和直接前趋。 13. 在一个单链表中 P所指结点之后插入一个S所指结点时，应执行 s->next=_ p->next ___________ 和 p->next=_ S ________ 的操作。 《数据结构》试卷及答案 1．算法分析的目的是( )。 A.找出数据结构的合理性 B.研究算法中输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2．（）是具有相同特性数据元素的集合，是数据的子集。 A.数据符号 B.数据对象 C.数据 D.数据结构 3．用链表表示线性表的优点是( )。 A.便于随机存取 B.花费的存储空间比顺序表少 C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同 4．输入序列为（A,B,C,D）不可能的输出有（）。 A.(A,B,C,D) B. (D,C,B,A) C. (A,C,D,B) D . (C,A,B,D) 5．在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是( )。 A. front=maxSize B. (rear+1)%maxSize=front C. rear=maxSize D. rear=front 6．设有串t='I am a good student '，那么Substr(t,6,6)=（）。 A. student B. a good s C. good D. a good 7．设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则a85地址为（）。 A.23 B.33 C.18 D. 40 8．已知广义表LS=(A,(B,C,D),E)运用head和tail函数，取出LS中原子b的运算（）。 A. Gethead(Gethead(LS)) B. Gettail(Gethead(LS)) C. Gethead(Gethead(Gettail(LS))) D. Gethead(Gettail(LS)) 9．若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为( ) A. CDBGFEA B. CDBFGEA C. CDBAGFE D. BCDAGFE 10．下列存储形式中，( ) 不是树的存储形式。 A.双亲表示法 B.左子女右兄弟表示法 C.广义表表示法 D.顺序表示法 11．对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是( )。 A.直接选择排序 B.直接插入排序 C.快速排序 D.起泡排序 12．采用折半查找方法进行查找，数据文件应为（），且限于（）。数据结构试题(含答案)
《数据结构》期末考试题及答案
数据结构复习习题
《数据结构》期末考试试卷
数据结构复习题及答案
数据结构试题及答案
数据结构期末考试试题及答案
数据结构复习题及答案
数据结构试卷及答案压缩版
相关主题
文本预览