数据结构复习题及答案(12级)

1、、选择题。 (每小题 2 分，共 40分)(1) 计算机识别 . 存储和加工处理的对象被统称为 AA. 数据 B. 数据元素C. 数据结构 D. 数据类型(2)数据结构通常是研究数据的及它们之间的联系。A. 存储和逻辑结构B.存储和抽象C.理想和抽象D.理想与逻辑(3)不是数据的逻辑结构是A. 散列结构B.线性结构C. 树结构D.图结构B. 静态结构与动态结构D. 紧凑结构与非紧凑结构 B 方面的内容。并行性时空复杂度_。B. 正确性和简明性数据复杂性和程序复杂性的有限序列(nz 0)B.字符D. 数据项 数据结构被形式地定义为D,R,其中D是B的有限集，R是C的有限集。A. 算法B.数据元素

2、C. 数据操作D.逻辑结构(5) 组成数据的基本单位是 A 。A. 数据项B.数据类型C. 数据元素D.数据变量 设数据结构 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) 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为_ CA. 存储结构B.逻辑结构C. 顺序存储结构D.链式存储结构(8) 在数据结构的讨论中把数据结构从逻辑上分为 _ AA. 内部结构与外部结构C.线性结构与非线性结构(9) 对一个算法的评价，不包括如下A. 健壮性和可读性B.C.

3、正确性D.(10) 算法分析的两个方面是 _ AA. 空间复杂性和时间复杂性C. 可读性和文档性D.(11) 线性表是具有 n 个_ C _A. 表元素C. 数据元素(12) 线性表的存储结构是一种 B 的存储结构。A. 随机存取B.顺序存取C. 索引存取D.HASH存取A.n-iB.n-i+1C.n-i-1D.i链表是一种采用A. 顺序 B 存储结构存储的线性表；B.链式C. 星式D.网状(14)(15)(16) 结点(17)(18)(19)(20)(21)(22)(23)(13) 在一个长度为个元素。的顺序表中，向第i个元素(K i < n +1)之前插入一个新元素时， 需要向后移动

4、面关于线性表的叙述错误的是 _ D 。A. 线性表采用顺序存储必须占用一片连续的存储空间B. 线性表采用链式存储不必占用一片连续的存储空间C. 线性表采用链式存储便于插入和删除操作的实现D. 线性表采用顺序存储便于插入和删除操作的实现设指针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-&g

5、t;next=p ；D. p->next=s ；s->next=q ；设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为_ AA. p->n ext=p->n ext- >nextB. p=p->nextC. p=p->next->nextD. p->next=p下列说法哪个正确？ D _A. 堆栈是在两端操作、先进后出的线性表B. 堆栈是在一端操作、先进先出的线性表C. 队列是在一端操作、先进先出的线性表D. 队列是在两端操作、先进先出的线性表栈和队列的共同点是 C 。A. 都是先进后出B.都是先进先出pl, p2, p3

6、,pn，若 p1=n，则 pi 为C. 只允许在端点处插入和删除元素 D. 没有共同点A、兀素个数B、兀素类型C 、逻辑结构D、插入、删除元素的位置链栈与顺序栈相比,比较明显的优点是D。A、插入操作更加方便B删除操作更加方便C不会出现下溢的情况D不会出现上溢的情况以下数据结构中哪一个是非线性结构_ D 。A. 队列B. 栈C. 线性表D. 二叉树栈与一般线性表的区别主要在 D若已知一个栈的入栈序列是1, 2, 3,，n,其输出序列为oA. iB. B. n=iC. n-i+1D.不确定(24) 当利用大小为 N 的一维数组顺序存储一个栈时，假定用top=N 表示栈空,则向这个栈插入一个元素时,

7、首先应执行语句修改 top 指针。A. top+B. top-C. top=0D. top(25)A. AB. BC. CD. D4 个元素进 S 栈的顺序是 A,B,C,D ，经运算 POP(S) 后，栈顶元素是(26)A. edcbaB. decbaC. dceabD. abcde(27)设输入序列是1、2、3、n,经过栈的作用后输出序列的第一个元素是n,则输出序列中第i个输出元素A. n-iB. n-1-iC. n+1-iD. 不能确定(28) 字符 A 、B、 字符串？C、D 依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成B _个不同的A. 15B. 14C. 16D.

8、 21(29) 设指针变量top 指向当前链式栈的栈顶，则删除栈顶元素的操作序列为A. top=top+1;B. top=top-1;C. top->next=top;D. top=top->next;一个栈的输入序列是a,b,c,d,e,则栈的不可能的输出序列是(30)设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是 C。A. 6B. 4C. 3D. 2(31) 若用一个大小为6 的数组来实现循环队列,且当前rear和front的值分别为0和

9、3。当从队列中删除一个兀素,再加入两个元素后,rear和front的值分别为_ B _。A. 1 和 5B. 2 和 4C. 4 和 2D. 5 和 1(32) 设顺序循环队列Q0 : M-1的头指针和尾指针分别为F和R,头指针F总是指向队头兀素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为C。A. R-FB. F-RC. (R-F+M)%MD. (F-R+M)%M(33) 设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为_A. front->next=s ； front

10、=s ；C. rear->next=s ； rear=s ；(34) 如下陈述中正确的是 _ A A. 串是一种特殊的线性表C. 串中元素只能是字母(35) 下列关于串的叙述中,正确的是 _A. 串长度是指串中不同字符的个数_ C 。B. s->next=rear ； rear=s ；D. s->next=front；front=s ；B. 串的长度必须大于零D. 空串就是空白串D 。B. 串是 n 个字母的有限序列C. 如果两个串含有相同的字符,则它们相等D. 只有当两个串的长度相等,并且各个对应位置的字符都相符时才相等字符串的长度是指 _ C 。A. 串中不同字符的个数C

11、. 串中所含字符的个数B. 串中不同字母的个数D. 串中不同数字的个数(37) 两个字符串相等的充要条件是A. 两个字符串的长度相等 C 。B. 两个字符串中对应位置上的字符相等C. 同时具备 (A) 和 (B) 两个条件D. 以上答案都不对(38) 串是一种特殊的线性表，其特殊性体现在 B A. 可以顺序存储B. 数据元素是一个字符C. 可以链接存储D. 数据元素可以是多个字符(39) 设有两个串p和q,求q在p中首次出现的位置的运算称作 B。A. 连接B. 模式匹配C. 求子串D. 求串长(40) 设串sl="ABCDEFG",s2="PQRST",

12、函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，贝U con(subs(s1,2,1en(s2)，subs(sl,len(s2)，2)的结果串是 _DA. BCDEFB. BCDEFGC. BCPQRSTD. BCDEFEF(41) 函数 substr(“DATASTRUCTURE ”, 5, 9)的返回值为 _ A 。A. “ STRUCTUR”EB. “ DATA”C. “ASTRUCTU”RD. “DATASTRUCTU”RE(42) 设串 S=”l AM A TEACHER! ”,其长度是 D

13、 。A. 16B. 11C. 14D. 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),按照依次插入结

14、点的方法生成一棵二叉排序树后,最后两层上的结点总数为 B 。A. 1B. 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的子结点(K i < m)。A. 互不相交B.可以相交C. 叶结点可以相交D.树枝结点可以相交(50) 如果结点 A 有三个兄弟,而且 B 是 A 的双亲,贝 B 的出度是 B 。A. 3 B. 4

15、C. 5 D. 1(51) 在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的B 倍。A. 1/2 B. 1 C. 2 D. 4(52) 具有 n 个顶点的无向完全图，边的总数为 D条。A. n-1B. nC. n+1D. n*(n-1)/2(53) 在无向图 G 的邻接矩阵 A 中，若 Ai,j 等于 1，则 Aj,i 等于C 。A. i+jB. i-jC. 1D. 0(54) 图的深度优先或广度优先遍历的空间复杂性均为 A 。 (访问标志位数组空间 )A. O(n) B. O(e) C. O(n-e) D. O(n+e)(55) 请指出在顺序表 2 、 5、 7、10、 14、15

16、、 18、23、 35、 41、 52中，用折半法查找关键码 12需做 C次关键码比较。A.2 B.3 C.4 D.5(56) 对线性表进行折半查找时，必须要求线性表 C 。A. 以顺序方式存储 B. 以链接方式存储C. 以顺序方式存储，且结点按关键字有序排列D. 以链接方式存储，且结点按关键字有序排列(57) 设二叉排序树中有 n 个结点，则在二叉排序树的平均查找长度为_ B 。2A. O(1)B. O(log 2n)C. O(n) D. O(n 2)(58) 依次插入序列 (50，72，43，85，75，20，35，45，65，30)后建立的二叉搜索树中， 查找元素 35 要进行 _A 元

17、素间的比较。A.4 次B.5 次C.7(59)设散列表中有m 个存储单元，散列函数H(key)=A.小于等于B.小于等于m的最大奇数C.小于等于m的最大偶数D.小于等于(60)_ D 是 HASH 查找的冲突处理方法。A.求余法 B. 平方取中法C. 二分法 D.(61)当a的值较小时，散列存储通常比其他存储方式具有A.较慢B. 较快C. 相同m的最大素数m的最大合数开放地址法对线性表进行折半查找最方便的存储结构是(62)次D. 不确定key % p ，则 p 最好选择 _ BD.10 次的查找速度。A.顺序表有序的顺序表C.链表.有序的链表(63) 如果要求一个线性表既能较快的查找，又能适应

18、动态变化的要求，可以采用 D 查找方法。A分块 B .顺序 C .折半 D .散列(64) 散列函数有一个共同性质，即函数值应按 _ C 取其值域的每一个值。A.最大概率 B .最小概率C .同等概率D .平均概率(65) 下述排序算法中，稳定的是 _ B 。A.直接选择排序B.直接插入排序C.快速排序 D.堆排序(66) 下列排序算法中， A 需要的辅助存储空间最大。A. 快速排序 B. 插入排序C. 希尔排序D. 基数排序(67) 下列各种排序算法中平均时间复杂度为0( n2)是_ D。A. 快速排序B. 堆排序C. 归并排序 D. 冒泡排序(68)在基于关键码比较的排序算法中,.算法在最

19、坏情况下，关键码比较次数不高于O(nlog2n)。(69)(70)(71)(72)(73)A.起泡排序B.直接插入排序C.二路归并排序D.快速排序一组记录为46， 79,A. 46,79,56,38,40,84C. 38,40,46,56,84,7956 , 38, 84, 40，则采用冒泡排序法按升序排列时第一趟排序结果是B. 46,56,38,79,40,84D. 38,46,79,56,40,84每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做A.插入 B.堆 C. 快速D. 归并排序。每次从无序表中挑选出一个最小或最大元素,把它交换到有序表的一端，此种排序方法

20、叫做排序。A.插入 B.C. 快速D. 归并设一组初始记录关键字序列A. 2 ， 3， 5,C. 3， 2， 5,F列排序方法中,8，66，8(5，2，6,B. 3，D. 2，8)，以第一个记录关键字 5为基准进行一趟快速排序的结果为5，8，66，5，8哪一种方法的比较次数与纪录的初始排列状态无关A.直接插入排序B.起泡排序c快速排序D.直接选择排序(74)是采用C.以第一元素为分界元素的快速排序D .基数排序设有关键码初始序列Q , H , C, Y , P, A,M,S,R,D,F,X，新序列F , H , C, D, P, A , M , Q, R, S, Y,X 方法对初始序列进行第一

21、趟扫描的结果。二路归并排序A.直接插入排序(75)A.直接插入排序B.直接选择排序在待排序文件已基本有序的前提下，下述排序方法中效率最咼的是归并排序C. 快速排序(76)若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选排序方法是A.快速排序B . 堆排序C.归并排序D直接插入排序(77)(78)A.n B2n-1 C2n Dn-1F列排序算法中,算法可能会出现下面情况：初始数据有序时，花费的间反而最多。A. 堆排序B.冒泡排序C.快速排序D . SHELL 排序将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是二、填空题。(每空1分，共10分)(1) 数

22、据结构是一门研究非数值计算的程序设计问题中计算机的 数据以及它们之间的关系和运算等的学科。数据结构包括数据的 逻辑结构 结构和 物理结构 结构。(3)数据结构从逻辑上划分为三种基本类型:线性数据结构树型结构图结构(4)数据的物理结构被分为 存储顺序存储链式存储索引存储.散列表(Hash)四种。(5) 一种抽象数据类型包括变量的取值范围和操作的类别两个部分。(6)数据的逻辑结构是指数据元素间的逻辑关系，数据的存储结构是指数据元素存储方式或者数据元素的物理关系(7)数据结构是指数据及其相互之间的关系。当结点之间存在 M对N (M : N )的联系时，称这种结构为网状结构。当结点之间存在1对N( 1

23、 :N)的联系时，称这种结构为树结构(8)对算法从时间和空间两方面进行度量，分别称为空间复杂度和时间复杂度分析。(9)算法的效率可分为空间效率和时间效率。(10) for(i=1 , t=1 , s=0; i<=n ; i+) t=t*i ; s=s+t; 的时间复杂度为 O (n)(11) 线性表是n个元素的有限序列(12)线性表的存储结构有顺序存储和链式存储(13)设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为 式存储结构上实现顺序查找的平均时间复杂度为o (n)，在链0(n)(14)设顺序线性表中有n个数据元素，则第删除第i个位置上的数据元素需要移动表中

24、i个位置上插入一个数据元素需要移动表中n-i+1.个数据元素;n-i个元素。(15)若频繁地对线性表进行插入与删除操作，该线性表应采用链式存储结构。(16)链式存储结构中的结点包含数据域和指针域。对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为(17)时间复杂度为O(n)0(1),在表尾插入元素的(18)栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为FILOFIFO表。(19)s= ” I am a man ” 长度为10(20)s1=” hello “ ,s2=” b

25、oy” ,s1,s2 连接后为:hello boy(21)s= ” this is the main string ” ，sub=” string ” ,strindex(s,sub)是:13(22)(23)int a1010,已知 a=1000,sizeof(int)=2,求 a33地址：_设有两个串p和q，求q在p中首次出现的位置的运算称为1066模式匹配(24)在树型结构中，树根结点没有前趋结点，其余每个结点有且仅有表；队个前驱结点；树叶结点没有后继.结点，其余每个结点的后继结点数不受限制。(25)在一棵二叉树中，度为0的结点的个数为n0，度为2的结点的个数为n2，则：n0 =n2 +1

26、(26)由分别带权为3,9,6,2,5的共五个叶子结点构成一棵哈夫曼树，则带权路径长度为55在图G的邻接表表示中，每个顶点邻接表中所含的结点数， 对于无向图来说等于该 顶点的 出度数(27)对于有向图来说等于该顶点的度数(28) 假定一个图具有n个顶点和e条边，则采用邻接矩阵表示的空间复杂性为 0(n2 ),采用邻接表表示的空间复杂性为 0(n+e)。(29) 对于长度为n的线性表，若进行顺序查找，则时间复杂度为 0(n) ;若采用折半法查找，则时间复杂度为O(log 2n)。(30) 假设在有序线性表 A1.2O上进行折半查找，则比较一次查找成功的结点数为 1，则比较二次查找成功的结点数为

27、2，则比较三次查找成功的结点数为4，则比较四次查找成功的结点数为8，则比较五次查找成功的结点数为 5，平均查找长度为 log+1)-1 。(31) 在一棵二叉排序树中，每个分支结点的左子树上所有结点的值一定小于该结点的值，右子树上所有结点的值一定 大于该结点的值。(32) 对一棵二叉排序树进行中序遍历时，得到的结点序列是一个 增序序列 。(33) 对于线性表(70, 34，55, 23，65, 41，20)进行散列存储时，若选用H ( K)=K %7作为散列函数，则散列地址为0的元素是 70，散列地址为 6的是34,20,55 。(34) 在线性表的散列存储中，装填因子：又称为装填系数，若用m

28、表示散列表的长度，n表示待散列存储的元素的个数，则 a等于n/m 。(35) 散列表中解决冲突的两种方法是 开放地址法和链地址法。(36) 在散列存储中，装填因子a的值越大，则产生冲突的可能性就越大 ； a的值越小，则产生冲突的可能性就越小 。(37) 散列法存储的基本思想是由 关键码直接决定数据的存储地址。(38) 构造哈希函数的方法有(写二个)直接定址法，数字分析法，平方取中法，折叠法，除留余数法，随机数法。(39) 在分块查找中首先查找 索引，然后再查找相应的 块。(40) 散列表的查找效率主要取决于散列表造表时选择的 哈希函数 和装填因子 。(41) 对两棵具有相同关键字集合而形状不同

29、的二叉排序树，中序 遍历它们得到的序列的顺序是一样的。(42) 当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用快速排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用 归并排序。(43) 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为O(log 2n)，整个堆排序过程的时间复杂度为 O(nlog 2n)。(44) 当向一个大根堆插入一个具有最大值的元素时，需要逐层 向上调整，直到被调整到 根结点位置为止。(45) 对一组初始关键字序列(40，50，95，20，15，70，60，45，10)进行冒泡排序，则第一趟需要进行相邻记录的比较的次数为_8，在整个排

30、序过程中最多需要进行 8趟排序才可以完成。(46) 在在插入排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是_快速，需要内存容量最多的是 3并。(47) 堆排序是不稳定，空间复杂度为 0(1)。在最坏情况下，其时间复杂度也为O(nlog 2n)。(48) 若待排序的文件中存在多个关键字相同的记录，经过某种排序方法排序后，具有相同关键字的记录间的相对位置保持不变，则这种排序方法是 稳定的排序方法。(49) 在对一组记录 (50,40,95，20，15,70,60,45,80)进行直接插入排序时， 当把第 7 个记录 60插入到有序表时， 为寻 找插入位置需比较 3

31、次。(50) 二路归并排序的时间复杂度是 _ O(nlog 2n) 。(51) 对于 n 个记录的集合进行归并排序，所需的附加空间消耗是 _ O(n) 。(52) 设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其仍按递增 顺序进行排序，则 冒泡排序 最省时间， 快速排序 最费时间。三、判断题。 (每小题 1 分，共 10分)(X )1 数据元素是数据的最小单位。(x )2 数据项是数据的基本单位。(V )3 .顺序存储的线性表可以随机存取。(V )4 线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此，是属于同一数据对象。( X

32、)5 在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点查找任何一个元素。(X )6 .在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。(X )7 链表的每个结点中，都恰好包含一个指针。(X )8 数组是同类型值的集合。(V )9 使用三元组表示稀疏矩阵的元素，有时并不能节省存储时间。( V )10. 线性表可以看成是广义表的特例，如果广义表中的每个元素都是原子，则广义表便成为线性表。( V)11.由树转换成二叉树，其根结点的右子树总是空的。( X)12.后序遍历树和中序遍历与该树对应的二叉树，其结果不同。( X)13.若有一个结点是

33、某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。( V )14.若一个树叶是某子树的中序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。( X )15. 已知二叉树的前序遍历和后序遍历序列并不能唯一地确定这棵树，因为不知道树的根结点是哪一个。( X )16. 在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理。( V )17. 有回路的图不能进行拓扑排序。( X )18. 连通分量是无向图中的极小连通子图。( V )19. 散列法存储的基本思想是由关键码的值决定数据的存储地址。( V )20. 散

34、列表的查找效率取决于散列表造表时选取的散列函数和处理冲突的方法。(V )21. m阶B-树每一个结点的子树个数都小于或等于m。( V )22. 中序遍历二叉排序树的结点就可以得到排好序的结点序列。( V )23. 在二叉排序树上插入新的结点时，不必移动其它结点，仅需改动某个结点的指针，由空变为非空即可。( V )24. 当待排序的元素很多时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂性的主 要因素。O(nlog2 n) 。(V )25.对于n个记录的集合进行快速排序，所需要的平均时间是(V )26.对于n个记录的集合进行归并排序，所需要的平均时间是0(nlog2 n)。(V

35、 )27.堆中所有非终端结点的值均小于或等于(大于或等于)左右子树的值。(X )28.磁盘上的顺序文件中插入新的记录时，必须复制整个文件。(X )29.在索引顺序文件中插入新的记录时，必须复制整个文件。( X )30. 索引顺序文件是一种特殊的顺序文件，因此通常存放在磁带上。四、简答题。 (共 6小题，每小题约 5分，共 32分)1. 简述下列术语：数据、数据项、数据元素、数据逻辑结构、数据存储结构、数据类型和算法。数据： 数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。 数据项： 数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。数据元素：

36、数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由若 干个数据项组成。数据逻辑结构： 数据的逻辑结构就是指数据元素间的关系。数据存储结构： 数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。数据类型： 是指变量的取值范围和所能够进行的操作的总和。算法： 是对特定问题求解步骤的一种描述，是指令的有限序列。2. 简述栈和线性表的区别。答：一般线性表使用数组来表示的。线性表一般有插入、删除、读取等对于任意元素的操作。 而栈只是一种特殊的线性表。栈只能在线性表的一端插入(称为入栈,push )或者读取栈顶元素或者称为“弹出、出栈” (pop) 。3. 简

37、述栈和队列这两种数据结构的相同点和不同点。答：相同点：栈和队列都是特殊的线性表，只在端点处进行插入，删除操作。 不同点：栈只在一端(栈顶)进行插入，删除操作；队列在一端(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，

38、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=“G00D”， q=“W0RKER ”。求：StrLength (s), StrLength (

39、t) , SubStr( s, 8, 7), SubStr(t, 2, 1), Strlndex(s, “A ), Strlndex (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 )= ”0”,Strlndex(s,“ A”)=3, Strlndex (s, t)=0, StrRep(s , “S

40、TUDEN”T, q)=” l AM A W0RKER”,7. 简述下列每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。 答：空串：不含任何字符；空格串：所含字符都是空格。串变量和串常量：串常量在程序的执行过程中只能引用不能改变；串变量的值在程序执行过程中是可以改变和重新 赋值的。主串与子串：子串是主串的一个子集。串变量的名字与串变量的值：串变量的名字表示串值的标识符。8. 设有二维数组 A(6 X 8),每个元素占6个字节存储，顺序存放， A的起地址为1000,计算:(1) 数组A的体积(即存储量)；(2) 数组的最后一个元素 A的起地址；(3) 按行优先

41、存放时，元素 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=13689. 分别画出含三个结点的无序树与二叉树的所有不同形态。答：无序树形态如下：二叉树形态如下：10. 分别写出图1中所示二叉树的先序遍历、中序遍历、后序遍历的结点访问序列。ABCDE FGHIJ图1答：先序遍历序列：ABDEHICFJG中序遍历序列：DBHEIAFJCG后序遍历序列：DHIEBJFGCA11. 试找出分别满足下列条件的所有二叉树。(1) 先序序列与中序序

42、列相同。(2) 后序序列与中序序列相同。(3) 先序序列与后序序列相同。答：(1)先序序列和中序序列相同：空树或缺左子树的单支树；(2) 后序序列和中序序列相同：空树或缺右子树的单支树；(3) 先序序列和后序序列相同：空树或只有根结点的二叉树。12. 已知一棵二叉树的中序序列和后序序列分别为BDCEAFH和DECBHG，试画出这棵二叉树。答：这棵二叉树为：13. 分别写出图2中所示二叉树的先序遍历、中序遍历、后序遍历的结点访问序列。ABDE.FGH图2答：先序遍历序列:ABDGCEHF中序遍历序列:DGBAEHCF后序遍历序列:GDBHEFCA14. 给定权值(7,18,3,32,5,26,1

43、2,8)，构造的哈夫曼树。答：哈夫曼树为：7,19,2,6,32,3,21,10，试为这 815. 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为个设计哈夫曼编码。答：哈夫曼树为：111在上述哈夫曼树的每个左分支上标以0，右分支上标以1,并设这8个字母分别为AB、CD、E、F、G和H,则它们的哈夫曼树为分别为：A： 0000 B : 10 C : 00110 D : 0010 E : 01 F : 00111 G : 11 H : 000116. 画出无向图G1的邻接矩阵和邻接表示意图，并写出每个顶点的度。答：(1 )邻接矩阵0111o'100111000111001

44、01110_(2)邻接链表:(3)每个顶点的度：顶点度V1 3V2 3V3 2V4 3V5 3答：（1）邻接链表:邻接表和逆邻接表示意图，并写出每个顶点的入度和出度。（2）逆邻接链表:VIV2V-1V5553/X1/X34,_-一T1八23/X2/（3）顶点入度出度V130V222V312V413V521V62318. 对应图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

45、 V4 V3 V2 V519. 何谓二叉排序树？答：一棵二叉排序树(又称二叉查找树)或者是一棵空树，或者是一棵同时满足下列条件的二叉树：(1) 若它的左子树不空，则左子树上所有结点的键值均小于它根结点键值。(2) 若它的右子树不空，则右子树上所有结点的键值均大于它根结点键值。(3) 它的左、右子树也分别为二叉排序树。20. 顺序查找时间为 0(n)，二分查找时间为 O(log2n)，散列查找时间为 0(1)，为什么有高效率的查找方法而不放 弃低效率的方法？答：衡量算法的标准有很多，时间复杂度只是其中之一。尽管有些算法时间性能很好，但是其他方面可能就存在着 不足。比如散列查找的时间性能很优越，但

46、是需要关注如何合理地构造散列函数问题，而且总存在着冲突等现象， 为了解决冲突，还得采用其他方法。二分查找也是有代价的，因为事先必须对整个查找区间进行排序，而排序也是费时的，所以常应用于频繁查找 的场合。对于顺序查找，尽管效率不高，但却比较简单，常用于查找范围较小或偶而进行查找的情况。21. 简述多重散列法解决冲突的基本思想。答：此法要求设立多个散列函数H, i=1，k。当给定值 K与闭散列表中的某个键值是相对于某个散列函数H的同义词因而发生冲突时，继续计算该给定值K在下一个散列函数 H+1下的散列地址，直到不再产生冲突为止。22. 简述公共溢出区法解决冲突的基本思想。答：散列表由两个一维数组组成。一个称为基本表，另