1、一、选择题。(每小题 2 分，共 40 分)(1) 计算机识别.存储和加工处理的对象被统称为_A_ 。A.数据 B.数据元素 C.数据结构 D.数据类型(2) 数据结构通常是研究数据的_ A _及它们之间的联系。A.存储和逻辑结构 B.存储和抽象 C.理想和抽象 D.理想与逻辑(3) 不是数据的逻辑结构是_ A _。A.散列结构 B.线性结构 C.树结构 D.图结构 (4) 数据结构被形式地定义为,其中 D 是_ B _的有限集，R 是_ C _的有限集。A.算法 B.数据元素 C.数据操作 D.逻辑结构(5) 组成数据的基本单位是_ A _。 A.数据项 B.数据类型C.数据元素 D.数据变
2、量(6) 设数据结构 A=(D，R)，其中 D=1，2，3，4，R=r，r=， ，则数据结构A 是_ A _。A.线性结构 B.树型结构 C.图型结构 D.集合(7) 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为_ C _。A.存储结构 B.逻辑结构 C.顺序存储结构 D.链式存储结构(8) 在数据结构的讨论中把数据结构从逻辑上分为_ A _。A.内部结构与外部结构 B.静态结构与动态结构C.线性结构与非线性结构 D.紧凑结构与非紧凑结构(9) 对一个算法的评价，不包括如下_ B _方面的内容。A.健壮性和可读性 B.并行性 C.正确性 D.时空复杂度(10) 算法分
3、析的两个方面是_ A _。A.空间复杂性和时间复杂性 B.正确性和简明性C.可读性和文档性 D.数据复杂性和程序复杂性(11) 线性表是具有 n 个_ C _的有限序列（n0)。A.表元素 B.字符 C.数据元素 D.数据项(12) 线性表的存储结构是一种_ B _的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.HASH 存取(13) 在一个长度为 n 的顺序表中，向第 i 个元素（1 i n）之前插入一个新元素时，需要向后移动_ B _个元素。A.n-i B.n-i+1 C.n-i-1 D.i(14) 链表是一种采用_ B _存储结构存储的线性表；A.顺序 B.链式 C.星式 D.
4、网状(15) 下面关于线性表的叙述错误的是_ D _。A.线性表采用顺序存储必须占用一片连续的存储空间B.线性表采用链式存储不必占用一片连续的存储空间C.线性表采用链式存储便于插入和删除操作的实现D.线性表采用顺序存储便于插入和删除操作的实现(16) 设指针 q 指向单链表中结点 A，指针 p 指向单链表中结点 A 的后继结点 B，指针 s 指向被插入的结点 X，则在结点 A 和结点 B 之间插入结点 X 的操作序列为_ B _。A. s-next=p-next；p-next=-s；B. q-next=s； s-next=p；C. p-next=s-next；s-next=p；D. p-nex
5、t=s；s-next=q；(17) 设指针变量 p 指向单链表结点 A，则删除结点 A 的后继结点 B 需要的操作为_ A _。A. p-next=p-next-next B. p=p-nextC. p=p-next-next D. p-next=p(18) 下列说法哪个正确？_ D _ A. 堆栈是在两端操作、先进后出的线性表B. 堆栈是在一端操作、先进先出的线性表C. 队列是在一端操作、先进先出的线性表D. 队列是在两端操作、先进先出的线性表(19) 栈和队列的共同点是 _ C _。A. 都是先进后出 B. 都是先进先出C. 只允许在端点处插入和删除元素 D. 没有共同点(20) 栈与一般
6、线性表的区别主要在_D _。A、元素个数 B、元素类型 C、逻辑结构 D、插入、删除元素的位置(21) 链栈与顺序栈相比，比较明显的优点是_D _。A、插入操作更加方便 B、删除操作更加方便C、不会出现下溢的情况 D、不会出现上溢的情况(22) 以下数据结构中哪一个是非线性结构_ D _ 。A.队列 B.栈 C.线性表 D.二叉树 (23) 若已知一个栈的入栈序列是 1，2，3，n，其输出序列为 p1，p2，p3，pn，若 p1=n，则 pi 为 _ C _。A. i B. B. n=i C. n-i+1 D.不确定(24) 当利用大小为 N 的一维数组顺序存储一个栈时，假定用 top=N 表
7、示栈空，则向这个栈插入一个元素时，首先应执行 _ B _语句修改 top 指针。A. top+ B. top- C. top=0 D. top(25) 4 个元素进 S 栈的顺序是 A,B,C,D，经运算 POP(S)后，栈顶元素是_ C _。A. A B. B C. C D. D(26) 一个栈的输入序列是 a,b,c,d,e,则栈的不可能的输出序列是_ C _。A. edcba B. decba C. dceab D. abcde(27) 设输入序列是 1、2、3、n，经过栈的作用后输出序列的第一个元素是 n，则输出序列中第 i 个输出元素是_ C _。A. n-i B. n-1-i C.
8、 n+1-i D.不能确定(28) 字符 A、 B、C、D 依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成_ B _个不同的字符串？A. 15 B. 14 C. 16 D. 21(29) 设指针变量 top 指向当前链式栈的栈顶，则删除栈顶元素的操作序列为_ D _。A. top=top+1; B. top=top-1; C. top-next=top; D. top=top-next; (30) 设栈 S 和队列 Q 的初始状态为空，元素 E1、E2、E3、E4、E5 和 E6 依次通过栈 S，一个元素出栈后即进入队列 Q，若 6 个元素出列的顺序为 E2、E4、E3、E6、
9、E5 和 E1，则栈 S 的容量至少应该是_ C _。A. 6 B. 4 C. 3 D. 2(31) 若用一个大小为 6 的数组来实现循环队列，且当前 rear 和 front 的值分别为 0 和 3。当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为 _ B _。A. 1 和 5 B. 2 和 4 C. 4 和 2 D. 5 和 1(32) 设顺序循环队列 Q0：M-1的头指针和尾指针分别为 F 和 R，头指针 F 总是指向队头元素的前一位置，尾指针 R 总是指向队尾元素的当前位置，则该循环队列中的元素个数为_ C _。A. R-F B. F-R C. (R-F+
10、M)%M D. (F-R+M)%M (33) 设指针变量 front 表示链式队列的队头指针，指针变量 rear 表示链式队列的队尾指针，指针变量 s 指向将要入队列的结点 X，则入队列的操作序列为 _ C _。A. front-next=s；front=s； B. s-next=rear；rear=s； C. rear-next=s；rear=s； D. s-next=front；front=s；(34) 如下陈述中正确的是_ A _。A. 串是一种特殊的线性表 B. 串的长度必须大于零 C. 串中元素只能是字母 D. 空串就是空白串(35) 下列关于串的叙述中，正确的是 _ D _。A.
11、串长度是指串中不同字符的个数 B. 串是 n 个字母的有限序列C. 如果两个串含有相同的字符，则它们相等 D. 只有当两个串的长度相等，并且各个对应位置的字符都相符时才相等(36) 字符串的长度是指_ C _。A. 串中不同字符的个数 B. 串中不同字母的个数 C. 串中所含字符的个数 D. 串中不同数字的个数 (37) 两个字符串相等的充要条件是_ C _。A. 两个字符串的长度相等 B. 两个字符串中对应位置上的字符相等C. 同时具备(A)和(B)两个条件 D. 以上答案都不对(38) 串是一种特殊的线性表，其特殊性体现在_ B _ 。A. 可以顺序存储 B. 数据元素是一个字符C. 可以
12、链接存储 D. 数据元素可以是多个字符(39) 设有两个串 p 和 q，求 q 在 p 中首次出现的位置的运算称作 _ B _。A. 连接 B. 模式匹配 C. 求子串 D. 求串长(40) 设串 sI=“ABCDEFG“,s2=“PQRST“,函数 con(x,y)返回 x 和 y 串的连接串,subs(s,i,j)返回串 s 的从序号 i 的字符开始的 j 个字符组成的子串， len(s)返回串 s 的长度，则 con(subs(s1,2,1en(s2)，subs(sl,len(s2) ，2)的结果串是_ D _。A. BCDEF B. BCDEFG C. BCPQRST D. BCDEF
13、EF (41) 函数 substr(“DATASTRUCTURE”，5，9) 的返回值为_ A _。A. “STRUCTURE” B. “DATA” C. “ASTRUCTUR” D. “DATASTRUCTURE”(42) 设串 S=”I AM A TEACHER!”，其长度是_ D _。A. 16 B. 11 C. 14 D. 15 (43) 假定在一棵二叉树中，双分支结点数为 15 个，单分支结点数为 32 个，则叶子结点数为_B_。 A. 15 B. 16 C. 17 D. 47(44) 假定一棵二叉树的结点数为 18 个，则它的最小高度 _B_。A. 4 B. 5 C. 6 D. 1
14、8(45) 在一棵二叉树中第五层上的结点数最多为_C_。A. 8 B. 15 C. 16 D. 32(46) 在一棵具有五层的满二叉树中，结点总数为_A_。A. 31 B. 32 C. 33 D. 16(47) 已知 8 个数据元素为(34 、76、45、18、26、54、92、65)，按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为_B_。A. 1 B. 2 C. D. 4(48) 由分别带权为 9、2、5、7 的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为 _C_。 A. 23 B. 37 C. 44 D. 46(49) 在树中除根结点外，其余结点分成 m (m0)
15、个_ A _的集合 T1,T2,T3.Tm,每个集合又都是树，此时结点 T 称为 Ti 的父结点， Ti 称为 T 的子结点(1im) 。A. 互不相交 B. 可以相交 C. 叶结点可以相交 D. 树枝结点可以相交(50) 如果结点 A 有三个兄弟，而且 B 是 A 的双亲，则 B 的出度是_B_。A. 3 B. 4 C. 5 D. 1(51) 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_B_倍。A. 1/2 B. 1 C. 2 D. 4(52) 具有 n 个顶点的无向完全图，边的总数为_ D _条。A. n-1 B. n C. n+1 D. n*(n-1)/2(53) 在无向
16、图 G 的邻接矩阵 A 中，若 Ai,j等于 1，则 Aj,i等于_C _。A. i+j B. i-j C. 1 D. 0(54) 图的深度优先或广度优先遍历的空间复杂性均为_ A_ 。(访问标志位数组空间)A. O(n) B. O(e) C. O(n-e) D. O(n+e)(55) 请指出在顺序表2、5、 7、10、14、15、18、23、 35、41、52中，用折半法查找关键码 12 需做_ C _次关键码比较。A.2 B.3 C.4 D.5 (56) 对线性表进行折半查找时，必须要求线性表 _ C _。A. 以顺序方式存储 B. 以链接方式存储C. 以顺序方式存储，且结点按关键字有序排
17、列D. 以链接方式存储，且结点按关键字有序排列(57) 设二叉排序树中有 n 个结点，则在二叉排序树的平均查找长度为 _ B _。A. O(1) B. O(log2n) C. O(n) D. O(n2)(58) 依次插入序列(50，72， 43，85，75，20，35，45，65，30)后建立的二叉搜索树中，查找元素 35 要进行_ A _元素间的比较。A.4 次 B.5 次 C.7 次 D.10 次(59) 设散列表中有 m 个存储单元，散列函数 H(key)= key % p，则 p 最好选择_ B _。A. 小于等于 m 的最大奇数 B. 小于等于 m 的最大素数C. 小于等于 m 的最
18、大偶数 D. 小于等于 m 的最大合数(60) _ D _是 HASH 查找的冲突处理方法。A.求余法 B. 平方取中法 C. 二分法 D. 开放地址法(61) 当 的值较小时，散列存储通常比其他存储方式具有_ B _的查找速度。A. 较慢 B. 较快 C. 相同 D. 不确定(62) 对线性表进行折半查找最方便的存储结构是_ B _。A顺序表 B有序的顺序表C链表 D有序的链表(63) 如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用_ D _查找方法。A分块 B顺序 C折半 D散列(64) 散列函数有一个共同性质，即函数值应按_ C _ 取其值域的每一个值。A最大概率 B
19、最小概率 C同等概率 D平均概率(65) 下述排序算法中，稳定的是_ B _。A.直接选择排序 B. 直接插入排序 C.快速排序 D.堆排序 (66) 下列排序算法中，_ A _需要的辅助存储空间最大。A.快速排序 B.插入排序 C.希尔排序 D.基数排序(67) 下列各种排序算法中平均时间复杂度为 O(n2)是_ D _。A. 快速排序 B. 堆排序 C. 归并排序 D. 冒泡排序(68) 在基于关键码比较的排序算法中，_ C _算法在最坏情况下，关键码比较次数不高于 O(nlog2n)。A. 起泡排序 B. 直接插入排序C. 二路归并排序 D. 快速排序(69) 一组记录为46，79，56
20、 ，38，84，40，则采用冒泡排序法按升序排列时第一趟排序结果是_ B _ 。A. 46,79,56,38,40,84 B.46,56,38,79,40,84C. 38,40,46,56,84,79 D.38,46,79,56,40,84(70) 每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做_ A _ 排序。A. 插入 B. 堆 C.快速 D.归并(71) 每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做_ B _排序。A. 插入 B. 堆 C.快速 D.归并(72) 设一组初始记录关键字序列(5 ，2，6，3，8)，以第一个记录
21、关键字 5 为基准进行一趟快速排序的结果为_ C _。A. 2，3，5，8，6 B. 3，2，5，8，6C. 3，2，5，6，8 D. 2，3，6，5，8(73) 下列排序方法中，哪一种方法的比较次数与纪录的初始排列状态无关_ D _。A. 直接插入排序 B. 起泡排序C. 快速排序 D. 直接选择排序(74) 设有关键码初始序列Q，H，C ，Y，P，A,M,S,R,D,F,X，新序列F，H， C，D ，P，A，M，Q ，R，S，Y,X是采用_ C _ 方法对初始序列进行第一趟扫描的结果。A. 直接插入排序 B二路归并排序C以第一元素为分界元素的快速排序 D基数排序(75) 在待排序文件已基本
22、有序的前提下，下述排序方法中效率最高的是_ C _。A. 直接插入排序 B. 直接选择排序C 快速排序 D 归并排序(76) 若需在 O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选排序方法是_ C _ 。A. 快速排序 B 堆排序C 归并排序 D 直接插入排序(77) 将两个各有 n 个元素的有序表归并成一个有序表，其最少的比较次数是 _ B _。A n B 2n-1 C 2n D n-1(78) 下列排序算法中，_ C _ 算法可能会出现下面情况：初始数据有序时，花费的间反而最多。A. 堆排序 B冒泡排序 C快速排序 D SHELL 排序二、填空题。(每空 1 分，共
23、 10 分)(1) 数据结构是一门研究非数值计算的程序设计问题中计算机的 数据 以及它们之间的 关系 和运算等的学科。(2) 数据结构包括数据的 逻辑结构 结构和 物理结构 结构。(3) 数据结构从逻辑上划分为三种基本类型：_线性数据结构 _、_树型结构_和_图结构_。(4) 数据的物理结构被分为_顺序存储_、_链式存储 _、_索引存储_和_散列表（Hash）存储_四种。(5) 一种抽象数据类型包括_变量的取值范围_和 _操作的类别_两个部分。(6) 数据的逻辑结构是指 数据元素间的逻辑关系 ，数据的存储结构是指 数据元素存储方式或者数据元素的物理关系 。(7) 数据结构是指数据及其相互之间的
24、_关系_ 。当结点之间存在 M 对 N（M：N）的联系时，称这种结构为_网状结构_。当结点之间存在 1 对 N（1：N ）的联系时，称这种结构为_树结构_。(8) 对算法从时间和空间两方面进行度量，分别称为 空间复杂度和时间复杂度 分析。(9) 算法的效率可分为_空间_效率和_ 时间_效率。(10) for(i=1，t=1 ，s=0 ；i=n；i+) t=t*i；s=s+t；的时间复杂度为_(n)_。(11) 线性表是 n 个元素的_有限序列_ 。(12) 线性表的存储结构有_顺序存储和链式存储 _。(13) 设线性表中有 n 个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为 _(
25、n)_，在链式存储结构上实现顺序查找的平均时间复杂度为_ O(n)_。(14) 设顺序线性表中有 n 个数据元素，则第 i 个位置上插入一个数据元素需要移动表中_ n-i+1_个数据元素；删除第 i 个位置上的数据元素需要移动表中 _ n-i _个元素。(15) 若频繁地对线性表进行插入与删除操作，该线性表应采用_链式_存储结构。(16) 链式存储结构中的结点包含_数据_域和 _指针_域。(17) 对于一个长度为 n 的单链存储的线性表，在表头插入元素的时间复杂度为 _(1)_，在表尾插入元素的时间复杂度为_(n)_。(18) 栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把
26、栈称为_ FILO _表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为 _ FIFO _表。(19) s=” I am a man” 长度为_10_ 。(20) s1=”hello “,s2=”boy”,s1,s2 连接后为：_ hello boy _ 。(21) s=”this is the main string”,sub=”string”,strindex(s,sub)是：_13_。(22) int a1010,已知 a=1000,sizeof(int)=2,求 a33地址：_1066_ 。(23) 设有两个串 p 和 q，求 q 在 p 中首次
27、出现的位置的运算称为 _模式匹配_。(24) 在树型结构中，树根结点没有_前趋_结点，其余每个结点有且仅有 _一_个前驱结点；树叶结点没有_后继_结点，其余每个结点的_后继_结点数不受限制。(25) 在一棵二叉树中，度为 0 的结点的个数为 n0 ，度为 2 的结点的个数为 n2 ，则：n0 =_n2 +1_。(26) 由分别带权为 3,9,6,2,5 的共五个叶子结点构成一棵哈夫曼树，则带权路径长度为 _ 55_。(27) 在图 G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该 顶点的 _度数_，对于有向图来说等于该顶点的_出度数_。(28) 假定一个图具有 n 个顶点
28、和 e 条边，则采用邻接矩阵表示的空间复杂性为_O(n2 ) _， 采用邻接表表示的空间复杂性为_ O(n+e) _。(29) 对于长度为 n 的线性表，若进行顺序查找，则时间复杂度为 _ O(n)_；若采用折半法查找，则时间复杂度为_ O(log 2n)_。(30) 假设在有序线性表 A1.20上进行折半查找，则比较一次查找成功的结点数为_1_，则比较二次查找成功的结点数为_2_，则比较三次查找成功的结点数为_4_，则比较四次查找成功的结点数为_8_，则比较五次查找成功的结点数为_5_，平均查找长度为_ log 2(n+1)-1_。(31) 在一棵二叉排序树中，每个分支结点的左子树上所有结点
29、的值一定_小于_该结点的值，右子树上所有结点的值一定_大于_该结点的值。 (32) 对一棵二叉排序树进行中序遍历时，得到的结点序列是一个_增序序列_。(33) 对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用 H（K）=K %7 作为散列函数，则散列地址为 0 的元素是_70_，散列地址为 6 的是_34,20,55_。(34) 在线性表的散列存储中，装填因子 又称为装填系数，若用 m 表示散列表的长度，n 表示待散列存储的元素的个数，则 等于_ n/m _。(35) 散列表中解决冲突的两种方法是_开放地址法_ 和_链地址法_。(36) 在散列存储中，装填因子 a
30、的值越大，则_产生冲突的可能性就越大_；a 的值越小，则_产生冲突的可能性就越小_。(37) 散列法存储的基本思想是由_关键码直接_ 决定数据的存储地址。(38) 构造哈希函数的方法有( 写二个)_直接定址法，数字分析法，平方取中法，折叠法，除留余数法，随机数法_。(39) 在分块查找中首先查找 _索引_，然后再查找相应的 _块_。(40) 散列表的查找效率主要取决于散列表造表时选择的_ 哈希函数_ 和_装填因子_。(41) 对两棵具有相同关键字集合而形状不同的二叉排序树，_中序_ 遍历它们得到的序列的顺序是一样的。(42) 当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用_快速
31、_排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用_归并_排序。(43) 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_ O(log 2n)_，整个堆排序过程的时间复杂度为_ O(nlog 2n)_。(44) 当向一个大根堆插入一个具有最大值的元素时，需要逐层_向上_调整，直到被调整到_根结点_位置为止。(45) 对一组初始关键字序列（40，50，95，20，15，70 ，60，45，10）进行冒泡排序，则第一趟需要进行相邻记录的比较的次数为_8_，在整个排序过程中最多需要进行_8_趟排序才可以完成。(46) 在在插入排序、选择排序、快速排序、堆排序、归并排序和基
32、数排序中，平均比较次数最少的排序是_快速_，需要内存容量最多的是_归并_。(47) 堆排序是不稳定，空间复杂度为 _ O(1)_。在最坏情况下，其时间复杂度也为 _ O(nlog2n)_。(48) 若待排序的文件中存在多个关键字相同的记录，经过某种排序方法排序后，具有相同关键字的记录间的相对位置保持不变，则这种排序方法是_稳定_的排序方法。(49) 在对一组记录(50,40,95 ，20，15,70,60,45,80)进行直接插入排序时，当把第 7 个记录 60 插入到有序表时，为寻找插入位置需比较_3_次。(50) 二路归并排序的时间复杂度是_ O(nlog 2n)_。(51) 对于 n 个
33、记录的集合进行归并排序，所需的附加空间消耗是_ O(n)_。(52) 设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其仍按递增顺序进行排序，则_冒泡排序_最省时间，_快速排序_最费时间。三、判断题。(每小题 1 分，共 10 分)( )1数据元素是数据的最小单位。( )2数据项是数据的基本单位。( )3顺序存储的线性表可以随机存取。( )4线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性， 因此，是属于同一数据对象。( )5在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点查找任何一个元素。( )6在单链表中，要取
34、得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。( )7链表的每个结点中，都恰好包含一个指针。( )8数组是同类型值的集合。 ( )9使用三元组表示稀疏矩阵的元素，有时并不能节省存储时间。( )10. 线性表可以看成是广义表的特例，如果广义表中的每个元素都是原子，则广义表便成为线性表。( )11. 由树转换成二叉树，其根结点的右子树总是空的。( )12. 后序遍历树和中序遍历与该树对应的二叉树，其结果不同。( )13. 若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子 树的前序遍历序列中的最后一个结点。( )14.若一个树叶是某子树的中序遍历序列中
35、的最后一个结点，则它必是该子树的前序 遍历序列中的最后一个结点。( )15. 已知二叉树的前序遍历和后序遍历序列并不能唯一地确定这棵树，因为不知道树 的根结点是哪一个。( )16. 在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理。( )17. 有回路的图不能进行拓扑排序。( )18. 连通分量是无向图中的极小连通子图。 ( )19. 散列法存储的基本思想是由关键码的值决定数据的存储地址。( )20. 散列表的查找效率取决于散列表造表时选取的散列函数和处理冲突的方法。( )21. m 阶 B-树每一个结点的子树个数都小于或等于 m。( )22. 中序遍历二叉排
36、序树的结点就可以得到排好序的结点序列。( )23. 在二叉排序树上插入新的结点时，不必移动其它结点，仅需改动某个结点的指针， 由空变为非空即可。( )24. 当待排序的元素很多时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂性的主要因素。( )25. 对于 n 个记录的集合进行快速排序，所需要的平均时间是 O(nlog2 n)。( )26. 对于 n 个记录的集合进行归并排序，所需要的平均时间是 O(nlog2 n)。( )27. 堆中所有非终端结点的值均小于或等于（大于或等于）左右子树的值。( )28. 磁盘上的顺序文件中插入新的记录时，必须复制整个文件。( )29. 在索
37、引顺序文件中插入新的记录时，必须复制整个文件。( )30. 索引顺序文件是一种特殊的顺序文件，因此通常存放在磁带上。四、简答题。(共 6 小题，每小题约 5 分，共 32 分)1. 简述下列术语：数据、数据项、数据元素、数据逻辑结构、数据存储结构、数据类型和算法。数据：数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。数据项：数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。数据元素：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由若干个数据项组成。数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。数据存
38、储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。数据类型：是指变量的取值范围和所能够进行的操作的总和。算法：是对特定问题求解步骤的一种描述，是指令的有限序列。2. 简述栈和线性表的区别。答：一般线性表使用数组来表示的。线性表一般有插入、删除、读取等对于任意元素的操作。而栈只是一种特殊的线性表。栈只能在线性表的一端插入（称为入栈,push）或者读取栈顶元素或者称为“弹出、出栈”(pop)。3. 简述栈和队列这两种数据结构的相同点和不同点。答：相同点：栈和队列都是特殊的线性表，只在端点处进行插入，删除操作。不同点：栈只在一端（栈顶）进行插入，删除操作；队列在一端（top）删除，
39、一端(rear)插入。4. 如果进栈的元素序列为 A，B，C，D，则可能得到的出栈序列有多少种? 写出全部的可能序列。答：可能序列有 14 种：ABCD; ACBD; ACDB; ABDC; ADCB; BACD; BADC; BCAD; BCDA; BDCA; CBAD; CBDA; CDBA; DCBA。5. 如果进栈的元素序列为 1，2，3，4，5，6，能否得到 4，3，5，6，1，2 和 1，3，5，4，2，6 的出栈序列?并说明为什么不能得到或如何得到。答：不能得到 4，3，5，6，1，2，最先出栈的是 4,则按 321 的方式出，不可能得到 1 在 2 前的序列，可以得到1，3，5，4，2，6，按如下方式进行 push(1), pop(), push(2), push(3), pop(), push(4), push(5), pop(), pop(), p
