一、选择题。(每小题2分，共40分)
(1) 计算机识别.存储和加工处理的对象被统称为____A____。
A.数据
B.数据元素
C.数据结构 D.数据类型
(2) 数据结构通常是研究数据的____ A _____及它们之间的联系。
A.存储和逻辑结构 B.存储和抽象
C.理想和抽象 D.理想与逻辑
(3) 不是数据的逻辑结构是____ A ______。
A.散列结构 B.线性结构
C.树结构 D.图结构
(4) 数据结构被形式地定义为 A.算法 B.数据元素 C.数据操作 D.逻辑结构 (5) 组成数据的基本单位是____ A ______。 A.数据项 B.数据类型 C.数据元素 D.数据变量 (6) 设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构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) 算法分析的两个方面是__ A ____。 A.空间复杂性和时间复杂性 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 (11) 线性表是具有n个___ C _____的有限序列（n≠0)。 A.表元素 B.字符 C.数据元素 D.数据项 (12) 线性表的存储结构是一种____ B ____的存储结构。 A.随机存取 B.顺序存取 C.索引存取 存取 (13) 在一个长度为n 的顺序表中，向第i个元素（1≤ i≤ n＋１）之前插入一个新元素时，需要向后移动____ B ____个元素。 +1 (14) 链表是一种采用____ B ____存储结构存储的线性表； A.顺序 B.链式 C.星式 D.网状 (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->next=s；s->next=q； (17) 设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为___ A _____。 A. p->next=p->next->next B. p=p->next C. p=p->next->next D. p->next=p (18) 下列说法哪个正确？____ D ______ A. 堆栈是在两端操作、先进后出的线性表 B. 堆栈是在一端操作、先进先出的线性表 C. 队列是在一端操作、先进先出的线性表 D. 队列是在两端操作、先进先出的线性表 (19) 栈和队列的共同点是 _____ C _______。 A. 都是先进后出 B. 都是先进先出 C. 只允许在端点处插入和删除元素 D. 没有共同点 (20) 栈与一般线性表的区别主要在_____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表示栈空，则向这个栈插入一个元素时，首先应执行 ____ 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. 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、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) 设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为____ C _____。 A. R-F B. F-R C. (R-F+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. 串长度是指串中不同字符的个数 B. 串是n个字母的有限序列 C. 如果两个串含有相同的字符，则它们相等 D. 只有当两个串的长度相等，并且各个对应位置的字符都相符时才相等 (36) 字符串的长度是指___ C ______。 A. 串中不同字符的个数 B. 串中不同字母的个数 C. 串中所含字符的个数 D. 串中不同数字的个数 (37) 两个字符串相等的充要条件是____ C ______。 A. 两个字符串的长度相等 B. 两个字符串中对应位置上的字符相等 C. 同时具备(A)和(B)两个条件 D. 以上答案都不对 (38) 串是一种特殊的线性表，其特殊性体现在____ B _______。 A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链接存储 D. 数据元素可以是多个字符 (39) 设有两个串p和q，求q在p中首次出现的位置的运算称作 ____ B ______。 A. 连接 B. 模式匹配 C. 求子串 D. 求串长 (40) 设串sI=\"ABCDEFG\函数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. BCDEFEF (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. 18 (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 (m≥0)个____A ____的集合T1,T2,T3...Tm,每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点(1≤i≤m)。 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) 在无向图G的邻接矩阵A中，若A[i,j]等于1，则A[j,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 ___次关键码比较。 (56) 对线性表进行折半查找时，必须要求线性表 ____ C ____。 A. 以顺序方式存储 B. 以链接方式存储 C. 以顺序方式存储，且结点按关键字有序排列 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 ___元素间的比较。 次 次 次 次 (59) 设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择___ B _____。 A. 小于等于m的最大奇数 B. 小于等于m的最大素数 C. 小于等于m的最大偶数 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．最小概率 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，38，84，40}，则采用冒泡排序法按升序排列时第一趟排序结果是___ B _____ 。 A. 46,79,56,38,40,84 ,56,38,79,40,84 C. 38,40,46,56,84,79 ,46,79,56,40,84 (70) 每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做___ A _____ 排序。 A. 插入 B. 堆 C.快速 D.归并 (71) 每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做___ B _____排序。 A. 插入 B. 堆 C.快速 D.归并 (72) 设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为____ C ____。 A. 2，3，5，8，6 B. 3，2，5，8，6 C. 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) 在待排序文件已基本有序的前提下，下述排序方法中效率最高的是__ 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分，共10分) (1) 数据结构是一门研究非数值计算的程序设计问题中计算机的 数据 以及它们之间的 关系 和运算等的学科。 (2) 数据结构包括数据的 逻辑结构 结构和 物理结构 结构。 (3) 数据结构从逻辑上划分为三种基本类型：____线性数据结构_______、____树型结构______和_____图结构______。 (4) 数据的物理结构被分为___顺序存储______、___链式存储_____、____索引存储______和______散列表（Hash）存储_____四种。 (5) 一种抽象数据类型包括_____变量的取值范围_____和 ____操作的类别_____两个部分。 (6) 数据的逻辑结构是指 数据元素间的逻辑关系 ，数据的存储结构是指 数据元素存储方式或者数据元素的物理关系 。 (7) 数据结构是指数据及其相互之间的____关系__________。当结点之间存在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个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为_____Ｏ(n)______，在链式存储结构上实现顺序查找的平均时间复杂度为____ O(n)_______。 (14) 设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中___ n-i+1____个数据元素；删除第i个位置上的数据元素需要移动表中___ n-i ____个元素。 (15) 若频繁地对线性表进行插入与删除操作，该线性表应采用_____链式_________存储结构。 (16) 链式存储结构中的结点包含______数据__________域和_____指针__________域。 (17) 对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为___Ο(1)______，在表尾插入元素的时间复杂度为_____Ο(n)_______。 (18) 栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为____ 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 a[10][10],已知a=1000,sizeof(int)=2,求a[3][3]地址：_______1066___________ 。 (23) 设有两个串p和q，求q在p中首次出现的位置的运算称为________模式匹配________。 (24) 在树型结构中，树根结点没有______前趋______结点，其余每个结点有且仅有______一______个前驱结点；树叶结点没有______后继______结点，其余每个结点的______后继______结点数不受限制。 (25) 在一棵二叉树中，度为0的结点的个数为n0 ，度为2的结点的个数为n2 ，则：n0 =______n2 +1______。 (26) 由分别带权为3,9,6,2,5的共五个叶子结点构成一棵哈夫曼树，则带权路径长度为______ 55______。 (27) 在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该 顶点的 ______度数______，对于有向图来说等于该顶点的______出度数______。 (28) 假定一个图具有n个顶点和e条边，则采用邻接矩阵表示的空间复杂性为______O(n2 ) ______， 采用邻接表表示的空间复杂性为______ O(n+e) ______。 (29) 对于长度为n的线性表，若进行顺序查找，则时间复杂度为______ O(n)____；若采用折半法查找，则时间复杂度为______ O(log2n)____。 (30) 假设在有序线性表A[1..20]上进行折半查找，则比较一次查找成功的结点数为____1_______，则比较二次查找成功的结点数为____2_______，则比较三次查找成功的结点数为____4_______，则比较四次查找成功的结点数为_____8______，则比较五次查找成功的结点数为____5_______，平均查找长度为_____ log2(n+1)-1______。 (31) 在一棵二叉排序树中，每个分支结点的左子树上所有结点的值一定_____小于______该结点的值，右子树上所有结点的值一定____大于_______该结点的值。 (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的值越大，则_______产生冲突的可能性就越大____________；a的值越小，则_____产生冲突的可能性就越小___________。 (37) 散列法存储的基本思想是由________关键码直接______________决定数据的存储地址。 (38) 构造哈希函数的方法有(写二个)______________直接定址法，数字分析法，平方取中法，折叠法，除留余数法，随机数法_________________________________________。 (39) 在分块查找中首先查找 _____索引________，然后再查找相应的______块_________。 (40) 散列表的查找效率主要取决于散列表造表时选择的_____哈希函数________ 和______装填因子_________。 (41) 对两棵具有相同关键字集合而形状不同的二叉排序树，____中序_______ 遍历它们得到的序列的顺序是一样的。 (42) 当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用______快速_________排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用______归并_________排序。 (43) 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为___ O(log2n)_____，整个堆排序过程的时间复杂度为____ O(nlog2n)____。 (44) 当向一个大根堆插入一个具有最大值的元素时，需要逐层____向上_____调整，直到被调整到_____根结点_______位置为止。 (45) 对一组初始关键字序列（40，50，95，20，15，70，60，45，10）进行冒泡排序，则第一趟需要进行相邻记录的比较的次数为____8______，在整个排序过程中最多需要进行_____8_____趟排序才可以完成。 (46) 在在插入排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是___快速_______，需要内存容量最多的是____归并______。 (47) 堆排序是不稳定，空间复杂度为 ____ O(1)_____。在最坏情况下，其时间复杂度也为___ O(nlog2n)______。 (48) 若待排序的文件中存在多个关键字相同的记录，经过某种排序方法排序后，具有相同关键字的记录间的相对位置保持不变，则这种排序方法是____稳定_______的排序方法。 (49) 在对一组记录(50,40,95，20，15,70,60,45,80)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较____3_____次。 (50) 二路归并排序的时间复杂度是___ O(nlog2n)______。 (51) 对于n个记录的集合进行归并排序，所需的附加空间消耗是___ O(n)______。 (52) 设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其仍按递增顺序进行排序，则______冒泡排序_________最省时间，____快速排序________最费时间。 三、判断题。(每小题1分，共10分) ( × )1．数据元素是数据的最小单位。 ( × )2．数据项是数据的基本单位。 ( √ )3．顺序存储的线性表可以随机存取。 ( √ )4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性， 因此，是属于同一数据对象。 ( × )5．在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点查找任何一个元素。 ( × )6．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。 ( × )7．链表的每个结点中，都恰好包含一个指针。 ( × )8．数组是同类型值的集合。 ( √ )9．使用三元组表示稀疏矩阵的元素，有时并不能节省存储时间。 ( √ )10. 线性表可以看成是广义表的特例，如果广义表中的每个元素都是原子，则广义表便成为线性表。 ( √ )11. 由树转换成二叉树，其根结点的右子树总是空的。 ( × )12. 后序遍历树和中序遍历与该树对应的二叉树，其结果不同。 ( × )13. 若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子 树的前序遍历序列中的最后一个结点。 ( √ )14.若一个树叶是某子树的中序遍历序列中的最后一个结点，则它必是该子树的前序 遍历序列中的最后一个结点。 ( × )15. 已知二叉树的前序遍历和后序遍历序列并不能唯一地确定这棵树，因为不知道树 的根结点是哪一个。 ( × )16. 在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理。 ( √ )17. 有回路的图不能进行拓扑排序。 ( × )18. 连通分量是无向图中的极小连通子图。 ( √ )19. 散列法存储的基本思想是由关键码的值决定数据的存储地址。 ( √ )20. 散列表的查找效率取决于散列表造表时选取的散列函数和处理冲突的方法。 ( √ )21. m阶B-树每一个结点的子树个数都小于或等于m。 ( √ )22. 中序遍历二叉排序树的结点就可以得到排好序的结点序列。 ( √ )23. 在二叉排序树上插入新的结点时，不必移动其它结点，仅需改动某个结点的指针， 由空变为 非空即可。 ( √ )24. 当待排序的元素很多时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂性的主要因素。 ( √ )25. 对于n个记录的集合进行快速排序，所需要的平均时间是O(nlog2 n)。 ( √ )26. 对于n个记录的集合进行归并排序，所需要的平均时间是O(nlog2 n)。 ( √ )27. 堆中所有非终端结点的值均小于或等于（大于或等于）左右子树的值。 ( × )28. 磁盘上的顺序文件中插入新的记录时，必须复制整个文件。 ( × )29. 在索引顺序文件中插入新的记录时，必须复制整个文件。 ( × )30. 索引顺序文件是一种特殊的顺序文件，因此通常存放在磁带上。 四、简答题。(共6小题，每小题约5分，共32分) 1. 简述下列术语：数据、数据项、数据元素、数据逻辑结构、数据存储结构、数据类型和算法。 数据：数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。 数据项：数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。 数据元素：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由若干个数据项组成。 数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。 数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。 数据类型：是指变量的取值范围和所能够进行的操作的总和。 算法：是对特定问题求解步骤的一种描述，是指令的有限序列。 2. 简述栈和线性表的区别。 答：一般线性表使用数组来表示的。线性表一般有插入、删除、读取等对于任意元素的操作。 而栈只是一种特殊的线性表。栈只能在线性表的一端插入（称为入栈,push）或者读取栈顶元素或者称为“弹出、出栈”(pop)。 3. 简述栈和队列这两种数据结构的相同点和不同点。 答：相同点：栈和队列都是特殊的线性表，只在端点处进行插入，删除操作。 不同点：栈只在一端（栈顶）进行插入，删除操作；队列在一端（top）删除，一端(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(), pop(), push(6), pop()。 6. 设s=“I AM A STUDENT”,t=“GOOD”，q=“WORKER”。 求：StrLength (s)， StrLength (t)，SubStr( s，8，7)，SubStr(t，2，1)，StrIndex(s,“A”)，StrIndex (s，t)，StrRep(s，“STUDENT”，q)，SubStr (SubStr (s，6，2)，StrConcat (t，SubStr(s，7，8)))。 答：StrLength (s)=14, StrLength (t)=4, SubStr( s，8，7)=” STUDENT”, SubStr(t，2，1)=”O”, StrIndex(s,“A”)=3, StrIndex (s，t)=0, StrRep(s，“STUDENT”，q)=” I AM A WORKER”, 7. 简述下列每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。 答：空串：不含任何字符；空格串：所含字符都是空格。 串变量和串常量:串常量在程序的执行过程中只能引用不能改变；串变量的值在程序执行过程中是可以改变和重新赋值的。 主串与子串：子串是主串的一个子集。 串变量的名字与串变量的值:串变量的名字表示串值的标识符。 8. 设有二维数组A(6×8)，每个元素占6个字节存储，顺序存放，A的起地址为1000，计算： (1)数组A的体积(即存储量)； (2)数组的最后一个元素A的起地址； (3)按行优先存放时，元素A1,4的起地址； (4)按列优先存放时，元素A4,7的起地址。 (1)6*8*6=288 (2)1000+47*6=1282 (3)1000+(8+4)*8=1096 (4)1000+(6*7+4)*8=1368 9. 分别画出含三个结点的无序树与二叉树的所有不同形态。 答：无序树形态如下： 二叉树形态如下： 10. 分别写出图1中所示二叉树的先序遍历、中序遍历、后序遍历的结点访问序列。答：先序遍历序列:ABDEHICFJG 中序遍历序列:DBHEIAFJCG 列:DHIEBJFGCA 11. 试找出分别满足下列条件的所有二叉树。 (1) 先序序列与中序序列相同。 后序遍历序 (2) 后序序列与中序序列相同。 (3) 先序序列与后序序列相同。 答：(1) 先序序列和中序序列相同：空树或缺左子树的单支树； (2) 后序序列和中序序列相同：空树或缺右子树的单支树； (3) 先序序列和后序序列相同：空树或只有根结点的二叉树。 12. 已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，试画出这棵二叉树。 答：这棵二叉树为: 13. 分别写出图2中所示二叉树的先序遍历、中序遍历、后序遍历的结点访问序列。 答：先序遍历序列:ABDGCEHF 中序遍历序列:DGBAEHCF 后序遍历序列:GDBHEFCA 14. 给定权值(7,18,3,32,5,26,12,8)，构造的哈夫曼树。 答：哈夫曼树为: 15. 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7,19,2,6,32,3,21,10，试为这8个设计哈夫曼编码。 答：哈夫曼树为: 在上述哈夫曼树的每个左分支上标以0，右分支上标以1，并设这8个字母分别为A、B、C、D、E、F、 G和H，则它们的哈夫曼树为分别为: A：0000 B：10 C：00110 D：0010 E：01 F：00111 G：11 H：0001 16. 画出无向图G1的邻接矩阵和邻接表示意图，并写出每个顶点的度。 答：（1）邻接矩阵: （2）邻接链表： （3）每个顶点的度： 顶点 度 V1 3 V2 3 V3 2 V4 3 V5 3 17. 画出有向图G2的邻接矩阵、邻接表和逆邻接表示意图，并写出每个顶点的入度和出度。 答：（1）邻接链表： （2）逆邻接链表： （3） 顶点 入度 出度 V1 3 0 V2 2 2 V3 1 2 V4 1 3 V5 2 1 V6 2 3 18. 对应图G3，写出从v1出必的深度优先遍历序列和广度优先遍历序列各三个。 答：深度优先查找遍历序列：V1 V2 V3 V4 V5; V1 V3 V5 V4 V2; V1 V4 V3 V5 V2 广度优先查找遍历序列：V1 V2 V3 V4 V5; V1 V3 V2 V4 V5; V1 V4 V3 V2 V5 19. 何谓二叉排序树? 答：一棵二叉排序树(又称二叉查找树)或者是一棵空树，或者是一棵同时满足下列条件的二叉树： (1)若它的左子树不空，则左子树上所有结点的键值均小于它根结点键值。 (2)若它的右子树不空，则右子树上所有结点的键值均大于它根结点键值。 (3)它的左、右子树也分别为二叉排序树。 20. 顺序查找时间为O(n)，二分查找时间为O(log2n)，散列查找时间为O(1)，为什么有高效率的查找方法而不放弃低效率的方法? 答：衡量算法的标准有很多，时间复杂度只是其中之一。尽管有些算法时间性能很好，但是其他方面可能就存在着不足。比如散列查找的时间性能很优越，但是需要关注如何合理地构造散列函数问题，而且总存在着冲突等现象，为了解决冲突，还得采用其他方法。 二分查找也是有代价的，因为事先必须对整个查找区间进行排序，而排序也是费时的，所以常应用于频繁查找的场合。对于顺序查找，尽管效率不高，但却比较简单，常用于查找范围较小或偶而进行查找的情况。 21. 简述多重散列法解决冲突的基本思想。 答：此法要求设立多个散列函数Hi，i=1，…，k。当给定值K与闭散列表中的某个键值是相对于某个散列函数Hi的同义词因而发生冲突时，继续计算该给定值K在下一个散列函数Hi+1下的散列地址，直到不再产生冲突为止。 22. 简述公共溢出区法解决冲突的基本思想。 答：散列表由两个一维数组组成。一个称为基本表，另一个称为溢出表。插入首先在基本表上进行；假如发生冲突，则将信息存人溢出表。 23. 在结点个数为n(n>1)的各棵树中，高度最小的树的高度是多少?它有多少个叶结点?多少个分支结点?高度最大的树的高度是多少?它有多少个叶结点?多少个分支结点? 答：结点个数为n时，高度最小的树的高度为1，有两层，它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-l，有n层，它有1个叶结点，n-1个分支结点。 24. 什么是内部排序?什么是排序方法的稳定性? 答：假定给定含有n个记录的文件(r1，r2，…，rn)，其相应的关键字为(k1，k2，…，kn)，则排序就是确定文件的一个序列r1，r2，…，rn，使得k1≤k2≤…≤kn，从而使得文件中n个记录按其对应关键字有序排列。如果整个排序过程在内存中进行，则排序叫内部排序。 假设在待排序的文件中存在两个或两个以上的记录具有相同的关键字，若采用某种排序方法后，使得这些具有相同关键字的记录在排序前后相对次序依然保持不变，则认为该排序方法是稳定的，否则就认为排序方法是不稳定的。 五、分析题。(每小题4分，共8分) 1. 分析下面语句段执行的时间复杂度。 (1) for(i＝1；i<＝n；i++) for(j＝1；j<＝n；j++) s++； (2) for(i＝1；i<＝n；i++) for(j＝i；j<＝n；j++) s++； (3) for(i＝1；i<＝n；i++) for(j＝1；j<＝i；j++) s++； (4) i＝1； k＝0； while(i<＝n-1){ k+＝10*i； i++； } (5) for (i＝1；i<＝n；i++) for (j＝1；j<＝i ；j++) for (k＝1；k<＝j；k++) x=x+1； (1) Ο(n2) (2) Ο(n2) (3) Ο(n2) (4) Ο(n-1) 2. 写出下列程序段的运行结果(栈中的元素类型是char)：(5) Ο(n3) main( ) { SeqStack s，*p;； char x，y； p=&s; Init_Queue(p); x= ‘c’； y= ‘k’； push (p，x)； push (p，’a’)；push (p，y); x=pop (p); push (p，’t’); push (p，x)； x=pop (p)； push (p，’s’); while (!Empty_SeqStack(p)) { y=pop (p)； printf(“％c”，y)； } printf(“％c＼n”，x)； } 答：stack 3. 写出下列程序段的运行结果(队列中的元素类型是char)： main( ) { SeQueue a, *q; char x，y； q=&a； x=’e’； y=’c’; Init_Queue(q); In_Queue(q，’h’); In_Queue(q, ’r’); In_Queue(q, y); x=Out_Queue (q)； In_Queue(q，x)； x= Out_Queue (q); In_Queue(q，’a’ )； while (!Empty_SeqStack(q)) { y= Out_Queue(q)； printf(“%c”，y)； } printf(“%C\\n”，x)； } 答：char 因篇幅问题不能全部显示，请点此查看更多更全内容