数据结构期末考试

1、数据结构期末考试作者:日期:12数据结构课后练习题一、填空题(第二章)1、顺序表中逻辑上相邻元素的物理位置世范，单链表中逻辑上相邻的元素物理位置可以相邻，也可以不相邻。一2、在一个长度为n的顺序表中删除第i个元素，平均要移动 n-i个元素，如果在第i个元素之前插入一个元素，平均要移动 n-i+1个元素。3、在一个单链表中，若 p所指的结点不是最后结点，在p之后插入s结点，则执行s->next=p->next;p->next=s。4、在一个长度为n的顺序表的表尾插入一个新元素的时间负责度为O。5、非空的单循环链表head的尾结点(由指针 P所指)满足p->next=hea

2、d。(第三章)1 .栈和队列都是线性结构，对于栈来说，它的插入和删除操作智能在栈顶进行,而队列的插入操作是在队星进行，删除元素的操作是在队首进行。2 .设有一顺序栈s,元素s1,s2,s3,s4,s5,s6吃入栈，如果六个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是3。3 .在具有n个单元的循环队列中，队满时共有n-1个元素。4 .从栈顶指针为Top的链栈中删除一个结点，并将结点值保存在X中，进行的操作是x=Top->data;Top=Top->next。5 .中缀表达式(A+B ) *D+E/(F+A*D)对应的后缀表达式为 AB+D*EFAD*+/+

3、6 .在操作序歹U push (1); push (2) ;pop (2);push (3); push (4); push (5); push (6); push (7); pop 之后栈顶元素和栈底元素分别是6和1。7 .在操作序歹U Qinsert(1);Qinsert(2);Qdelete(1);Qdelete(2);Qinsert(3);Qinsert(4);Qinsert (5); Qinsert(6);Qinsert(7);Qdelete(3);Qdelete(4);Qinsert(8);Qinsert(9);之后队头元素和队尾元素分别是 5_和9。(第四章)1 .串是由0个或多

4、个字符组成的序列。2 .不包含任何字符串 称为空串:由一个或多个空格组成的串 称为空格串。3 .子用的定位运算 称为串的模式匹配;被匹配的主串称为目标串,子串称为模式。(第五章)1 .广义表的深度是等于括号嵌套的最大层数。2 .在广义表的存储结构中，每个结点均包含3个域。3 .一个广义表的深度等于 括号!嵌套的最大层数。4 .对矩阵压缩是为了 节省存储空间。5 .当广义表中的每个元素都是原子时，广义表便成了线性表。6 .广义表的表尾是指除第一个元素之外，其余元素组成的表。7 .广义表的 深必定义为广义表中括弧的重数。8 .设广义表L=(), (),则hesd (L)是 ();tail (L)是

5、();L的长度是2；深度是2。9 .广义表(a, (a,b) ,d,e,(i,j),k)的长度是5,深度是3。(第六章)1 .对于一棵具有n个结点的树，该树中所有结点的度数之和为nzlo2 .一颗二棵深度为5的满二叉树中的结点树为31个。3 .假定一棵树的广义表表示为A (B(C,D(E,F,G),H(I,J),则树种所含的结点数为 10个，树的深度为四个，树的度为3.4 .假定一棵树的广义表表示为A ( B(C,D(E,F,G),H(I,J)，则度为3, 2, 1, 0的结点树分别为 2、1、1和§个。5 .假定一棵树的广义表表示为A ( B(C,D(E,F,G),H(I,J),则

6、结点H的双亲结点为 B，孩子结点为I和J。6 .在哈夫曼编码中，若编码长度只允许小于等于4,则除了已对两个字符编码为0和10外，还可以最多对4个字符编码。7 .对于一棵二叉树，若一个结点的编码为i,则它的左孩子结点的编号为2i,右孩子结点的编号为2i+1,双亲结点编号为i/2 o8 .在一棵二叉树中，第 5层上的结点数最多为 16。9 .假定一棵二叉树的结点树为18,则它的最小深度为 5,最大深度为18。10 .假定一棵二叉树顺序存储在一维数组a中，则ai元素的左孩子元素为a2i,右孩子元素为 a2i+1,双亲元素(i-1)为ai/2。11 .假定一棵二叉树顺序存储在一维数组a中，但让编号为1

7、的结点存入a0元素中，让编号为 2的结点存入a1元素中，其余类推，则编号为i结点的左孩子结点对应的存储位置为2i-1。12 .对于一棵具有n个结点的二叉树，对应二叉链接表中指针总数为2n个，其中n-1个用于指向孩子结点，n+1个指向空闲着。13 .一棵二叉树广义表表示为a(b(d(h),c(e,f(g,i(k),该树的结点数为10个，深度为5O14 .假定一棵二叉树广义表表示为a (b(c),d(e,f)，则对它进行的先序遍历结果为a b c d e f,中序遍历结果为c b a e d f,后续序遍历结果为 c b e f d a。(第七章)1 .有向图G用邻接矩阵存储，其第i行的所有元素之

8、和等于顶点i的出度。2 .图的逆邻接表存储结构之适用于有向图。3 .图的深度优先遍历序列 不是唯一的。4 .图的BFS生成树的树高比 DFS生成树的树高 矮或相当。5 .拓扑排序输出的顶点数小于有向图的顶点数，则该图一定存在 如。6 .若要求一个稀疏图 G的最小生成树，最好用 Kruskal算法来求解。1 .关键字是数据元素(或记录)中某个属性，用它的标识(或识别)一个查找表中的 数据元素(或记录)。并且，在一个查找表中，能够唯一标识一个数据元素(或记录)的关键字称为主关键字。2 .查找又称为(检索),它是根据给定的某个值，在查找表中确定是否有元素或记录的关键字等于给定值的操作。若操作之后确定

9、表中存在这样的记录，则称为查找是成功的，否则称为不成功(或失败)。3 .平均查找长度是指为确定所查找的记录在查找表中的位置，需要与给定值进行比较的关键字个数的平均伯(或期望值)。4 .采用顺序查找法查找长度为n大的线性表时，假设查找成功与查找不成功的概率对等，对每个记录的查找概率也相等，则平均查找长度为3 (n+1) /4。5 .折半查找又称为 二分杳找,其查找思路是：每次将给定值与查找表中所要查找区域中间位置的关键字进行比较，而不是查找表中的第一条或最后一条。6 .在各种查找方法中，平均查找长度与结点个数n无关的查找方法是哈希表杳找法。7 .哈希表的查找小绿主要取决于哈希表建表时选择的哈希函

10、数 和装埴因子。8 .构造哈希函数的方法有 直接岸址法、数字分析法、平方取中法、折叠法和除留余数法。9 .假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入哈希表中，至少要进行(K/1 )82_次探测。10 .二叉排序树又称为 二叉杳找树，它或者是一棵空树，或者是具有下列性质的一棵二叉树；(1)若左子树不空，则左子树上所有结点的值小于根结点的值。(2)若右子树不空，则左子树上所有结点的值大干根结点的俏。(3)左、右子树又分别是一棵二叉排序树。11 .平衡二叉树是有 Abelson-Velskil和Landis提出的一种附加一定限制条件的二叉树。又称为AVL树。平衡二叉树定义为：它或者

11、是一棵空树；或者是具有这样性质的二叉树；它的左子树和右子树都是一棵平衡二叉树,且左子树和右子树的深度之差绝对值不大于112.在向哈希表中存储关键字的时候，有时会出现一个待插入关键字的记录已经被占用的情况，这种对不同关键字得到同一地址的现象称为冲突（或碰撞），相应的把这些具有相同哈希函数值得关键字称为同义而。 13.构造哈希函数应当尽量减少冲突，但是还是无法避免冲突的发生，一旦冲突发生了，就必须讯企鹅合适的方法来解决冲突。常用开放地址法和链地址法两种方法来解决冲突。 14.对长度n=50的有序表进行折半查找，则对应的判定树高度为6,判定树前5层的结点树是31,最后一层的结点树为9。二、单选题（第

12、二章）1、线性表L= （ ai,a2,，a，a）,下列说法正确的是（ D） A、每个元素都有一个直接前驱和直接后继 B、线性表中至少有一个元素C、表中诸元素的排列顺序必须是从小到大或由大到小D、除第一个元素和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。2、对于顺序表，以下说法错误的是（ A）A、顺序表是一维数组实现的线性表，数组的下标可以看成是元素的绝对地址 B、顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列 C、顺序表的特点是逻辑结构中相邻的结点在存储结构中仍相邻 D、顺序表的特点是逻辑上相邻的元素，存储在物理位置也相邻的单元中 3、对顺序表上的插入、

13、删除、算法的时间复杂度分析来说，通常以（ B）对标准操作。 A、条件判断 B、结点移动C、算术表达式D、赋值语句4、对于顺序表的优、缺点，以下说法错误的是（ C） A、无须为表示结点间的逻辑关系而增加额外的存储空间 B、可以方便的随机存储表中任一结点 C、插入和删除操作较方便D、由于顺序表要求占用连续的空间，存储分配只能预先进行（静态分配）5、在含有n个结点的顺序存储的线性表中，在任一结点前插入一个结点所需移动的点的平均次数为（B）A、nB、n/2C、（n-1）/2D、（n+1）/26、在含有n个结点的顺序存储的线性表中，删除一个结点所需移动结点的平均次数为（C）A、nB、n/2C、（n-1）

14、/2D、（n+1）/27、带头结点的单链表head为空的条件是（B）A、head=NULL B、head->next=NULL C、head->next=head D、head!=NULL8、非空循环单链表 head的尾结点*p满足（C）A、p->next=NULLB、p=NULL C、p->next=head D、p=head9、在循环双链表的*p结点之后插入*s满足（D）A、p->next=s;s->prior=p;p->next->prior=s;s->next=p->next; B、p->next=s;p->nex

15、t->prior=s;s->prior=p;s->next=p->next; C、s->prior=p;s->next=p->next;p->next=s;p->next->prior=s; D、s->prior=p;s->next=p->next;p->next->prior=s;p->next=s; 10、在线性表的下列存储结构中，读取元素花费时间最少的是（ D） A、单链表 B、双链表C、循环列表D、顺序表（第三章）1.有一栈的输入序列是a、b、c,则通过入栈、出栈操作可能得到a、b、c的不同

16、排列个数为（B）。A. 42 .和顺序栈相比，链栈有一个比较明显的优势是(A通常不会出现栈满的情况C插入操作更容易实现3 .若一个栈的输入序列是1、2、A不确定 B n-i4 .一个栈的入栈序列是a、b、c、A e、d、c、b、a B d、e、c、5 .一个队列的入队列是1、2、3、A. 4、3、2、1B. 1、2、6 .顺序列队的出队操作为(B)A sq.front=(sq.front+1)%maxsizeCsq.rear=(sq.rear+1)maxsize7 .循环队列q的出队操作为(A)A q,front=(q.front+1)%maxsizeC q.rear=(q.rear+1)%m

17、axisize8 .循环队列用数组A0 则当前队列中的元素个数是A.(rear-front+m)%mC.read-front-19 .在一个链队中，假设A)。B通常不会出现栈空的情况D删除操作更容易实现3、4、n,输出序列第一个元素是C n-i+1D n-i-1d、e,则栈的不可能输出序列是( b、a C d、c、e、a、b D a、4,则队列的可能输出序列是(B)4C.1、4、3、2B sq.front=sq.front+1D sq.rear=sq.rear+1B q.front=q.front+1Dq.rear=q.rear+13、n,则第i个输出元素是(C)。C)b、 c、 d、 eD

18、.3、2、4、1m-1存放其元素值，已知其头、尾指针分别是(A)。B read-front+1D.read-frontf和r分别为队首和队尾指针，则删除一个结点的运算是(front 和 rear,C)。A,r=f->next B.r=r->next(第四章)1 .串是(D)A. 一些符号构成的序列C. 一个以上的字符构成的序列C.f=f->next D f=r->nextB.一些字母构成的序列D.任意有限个字符构成的序列2.S1= " abcd "S2= " cd,” 贝U S2 在 S1 中的位置是(C)。A.1B.2C.3D.43 .下

19、列为空串的是(C)。A. " B. ”“ C.” "D "4 .朴素模式匹配算法在最好的情况下的运行时间是(以一次内循环为单位)(C)。A.M B.NC.MXN D.M+N(第五章)1 .已知广义表LS= (a,b,c), (d,e,f),运用head和tail函数取出LS中元素e的运算是(C)A.head(tail(LS)B.tail(head(LS)C.head(tail(head(tail(LS)D.head(tail(tail(head(LS)2 .将一个A1100,110曲三对角矩阵，按行优先存入一维数组 B1 298中，A中元素a66, 65 (即该元

20、 素下标i=66,j=65 )在B数组中白位置 K为(B)A.198B.195C.197D.1963 .若广义表 A满足Head (A) =Tail (A),则A为(B)。A.()B.()C.(),()D.(),(),()4 .广义表 A= (a,b,(c,d),(e,(f,g)，则下面式子 Head (Tail(Head(Tail(Tail(A)的值为(D)。A.(g) B. (d) C.cD.d5 .二维数组A的每个元素是由6个字符组成的串，其行下标 i=0,1, 丁 8,列下标j=1,2,，10.若A按行先 存储，元素A8,5的起始地址与当 A按列先存储时的元素(B)的起始地址相同。设每

21、个字符占一个字节。A. A8 , 5B.A3 , 10C,A5 , 8D.A0 , 96 .在以下的叙述中，正确的是（ B）A.线性表的线性存储结构优于链表存储结构B.二维数组是其数据元数为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出7二维数组SA中，每个元素的长度为3个字节，行下标i从07,歹U下标j从09,从首地址SA开始连续存放在存储器内，该数组按列存放时，元素 SA47的起始地址为（B）。A.SA+141B.SA+180C.SA+222D.SA+2258 .下面结论正确的是（B）。A. 一个广义表的表头肯定不是一个广义表。B. 一个广义表的表尾肯定是一个广义表。

22、C.广义表L=（）,（A,B）的表头为空表D.广义表中原子个数即为广义表的长度9 .下面说法不正确的是（A）A.广义表的表头总是一个广义表B.广义表的表尾总是一个广义表C.广义表难以用顺序存储结构D,广义表可以是一个多层次的结构（第六章）1 .一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（C）。A.所有的结点均无左孩子B.所有的结点均无右孩子C.只有一个叶子结点D.是任意一棵二叉树2 .一棵完全二叉树上有1001个结点，其中椰子结点个数是（ D）。A.250B.500C.254D.以上答案都不对3 .任何一棵二叉树的叶结点在前（先）序、中序、后序遍历序列中的相对次序

23、（A）。A不发生变化B.发生变化C.不能确定4 .设A,B为一棵二叉树上的两个结点，在中序遍历时， A在B前面的条件是（B）。.A在B的右方B. A在B的左方C.A是B的祖先D.A是B的子孙5 .在一棵具有n个结点的完全二叉树中，数值结点最大编号为（D）A. （n+1）/2B.（n-1）/2C. n/2D. n/26 .在N个结点的线索二叉树中，线索的数目为（C）。A.N-1B.NC.N+1 D.2N7 .设深度为K的二叉树上只有度为 0和度为2的结点，则这类二叉树上所含的结点总数为（ C）A.K+1B.2KC. 2K 1D, 2K+18 .下列有关二叉树的说法，正确的是（B）。A.二叉树的度

24、为2B. 一棵二叉树度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任意个结点的度都为29.在一棵深度为 H的完全二叉树中,A.2HB.2 H-1C.2H-1所含结点的个数不小于（D.2H+1D）。10.在一棵具有N个结点的二叉树第I层上，最多具有（C）个结点。A. 2IB. 2H-1C. .2H -1D.2N11 .在下列情况下，可称为二叉树的是（A.每个结点至多有两棵子树的树C.每个结点至多有两棵子树的有序树12 .树最适合用来表示（C）。A.有序数据元素C.元素之间具有分支层次关系的数据A）。B.哈夫曼树D.每个结点只有一棵右子树B.无序数据元素D.元素之间无联系的数据A）的二

25、叉树。13 .某二叉树的前序序列和后序序列正好相反，则二叉树A.空或只有一个结点B.任一结点无左子树C.高度等于其结点数D.任一结点无右子树14 .按照二叉树的定义，具有3个结点的二叉树有（C）种。.A.3B.4C.5D.615 .对一个满二叉树，m个树叶，n个结点，深度为h,则（D）。A.n=h+mB.h+m=2nC.m=h-1D.n=2h-116 .在一非空二叉树的中序遍历序列中，根结点的右边（ A）。A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的部分结点D.只有左子树上的所有结点17 .任何一棵二叉树的结点在先序、中序、后序遍历中的相对次序（ A）。A.不发生改变

26、B.发生改变C.不能确定D.以上都不对D)18 .已知某二叉树的后序遍历序列是dabec,中序遍历序列是 debac,它的前序遍历序列是（A.acbedB.decabC.deabc D.cedba19 .由带权为8、2、5、7的4个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（ DA.23B.37C.46D.4320 .对二叉排序树进行（B）遍历，可以得到该二叉树所有结点构成的排序序列。A.前序 B.中序C.后序D.按层次（第七章）1 .在一个有向图中，所有顶点的入度和等于所有顶点的出度之和的（ B）倍。A 1/2B.1C.2D.42 .用邻接表表示图进行广度优先遍历时，通常采用（ B）来实

27、现算法。A.栈B.队列C.树D.图3 .具有n个顶点的无向完全图，边的总数为（D）。A,nB.n+1C.2n-1D.n （n-1） /24 .有n个顶点的连通 G的最小生成树有（C）条边。A.n-1B.nC.n+1D.不确定5 .一个有向无环图的拓扑序列个数是（B）。A.1个 B.1个或多个 C.0个 D.多个6 .在AOE网中，入度为0的顶点称为（B）A.起点 B.源点C.终点D.汇点7 .Prim算法的时间复杂度是（B）A.O （n） B.O （n2）C.O （e） D.O（eloge）8 .在无向图的邻接矩阵 A中，若Aij=1 ,则A皿i的值为（C）A.i+jB.i-jC.1D.0（第

28、八章）1 .静态查找表与动态查找表的根本区别在于（ B）A.它们的逻辑结构不一样B.施加在其上的操作不一样C.所包含的数据元素类型不一样D.存储实现不一样2 .顺序查找适用于存储结构为（C）的线性表。A.哈希表B.压缩存储C.顺序存储或链接存储D.索引存储3 .对线性表进行折半查找最方便的存储结构是（B）。A.顺序表B.有序的顺序表C.链表D,有序的链表4 .对一个排好序的线性表，用折半查找法检索表中的元素，被检索的表应当采用（A）。A.顺序存储B.链接存储C.散列法存储D.存储表示不受限制5 .若在线性表中采用折半查找法查找元素，该线性表应该（ C）。A.元素按值有序B.采用顺序存储结构C.

29、元素按值有序，且采用顺序存储结构D.元素按值有序，且采用链式存储结构6 .在顺序表(3,6,8,10,12,15,16,18,21,25,30)中，用折半查找法查找关键码值11,所需的关键码比较次数为(C)。A.2B.3C.4D.57 .用折半查找法查找一个长度为10的、排好序的线性表，查找不成功时，最多需要比较(C)次。A.5B.2C.4D.18 .采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为( C)。A.nB.n/2 C. (n+1) /2D.(n-1)/29 .有一个长度为12的有序表，按折半查找法对该表进行查找，在表内每个元素等概率情况下查找成功时所需的平均比较次数

30、是(B)A.35/12B.37/12C.39/12D.41/1210 .设有100个元素，用折半查找法进行查找时，最小比较次数是( D)。A.1B.2C.4D.711 .利用逐点插入法建立序列(50,72,43,85,75,20,35,45,65,30)对应的二叉排序树以后，查找元素35要进行(A)次元素间的比较。A.4B.5C.6D.712 .在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度与(B)量级相当。A顺序查找B折半查找C分块查找D以上都不正确13 .如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用(C)查找方法。A顺序B折半C散列D以上都不正确14

31、 .一棵平衡二叉树，其每个非终端节点的平衡因子均为0,则该树共有(D)个结点。A.2 k-1-1B.2k-1C2k-1+1D.2k-115 .设哈希表上 m=14,哈希表函数 H(key尸key%11。表中已有 4 个结点：addr(15)=4 ; addr(38)=5 ; ;addr(61)=6 ; addr(84)=7;其余地址为空，如果用二次探测再散列处理冲突，关键字为49的结点的地址是(D)A.9B.8C.5D.316 .在哈希查找中，平均查找长度主要与(C)有关。A.哈希表长度B哈希元素的个数C装填因子 D处理冲突方法17 .在采用线性探测法处理冲突的散列表上，假定装填因子”的值为0

32、.5,则查找任一元素的平均查找长度约为(B)A 1B 1.5C2D3.518 .在采用链接法处理冲突的散列表上，假定装填因子 a的值为4,则查找任一元素的平均查找长度约为(A)A 3B 3.5C2D 419 .若对一组关键字(23,44,36,48,52,73,64,58)建立散列表，采用 H (K) =K%7计算散列地址，则同义词 元素的个数最多为(B)个A 2 B 3 C 4 D 520 .若对一组关键字(23,44,36,48,52,73,64,58)建立散列表，采用 H(K)=K%13计算散列地址，并采用链接 法处理冲突，则元素 64的初始散列地址(C)A.2B.8C.12D.13三、

33、简答题(第二章)(1)简述合适选用顺序表或链表作为线性表的存储结构为宜。答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常 有以下几方面的考虑。基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储 结构为宜；反之，若需要对线性表进行频繁地插入或删除等操作时，宜采用链表做存储结构。并且，若链 表的插入和删除主要发生在表的首、尾两端，则采用尾指针表示

34、循环单链表为宜。(2)为什么在循环单链表中设置尾指针比设置头指针更好？答：尾指针是指向终端节点的指针，用它来表示循环单链表可以使得查找链表的开始节点和终端节点 都很方便，设一带头结点的单循环链表，其尾指针为rear,则开始节点和终端节点的位置分别是rear->next->next 和 rear,查找时间者B是 O (1)。(第三章)1 .链栈中为何不设置头结点？答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结 点之后的结点进行操作，反而使算法更加复杂。所以只要有链表的头指针就可以了。2 .循环队列的优点是什么？如何判别它的空和满？答：循环列队

35、的优点是：它可以克服顺序列队的假上溢”现象，能够使存储队列的向量空间得到充分利用。判别循环队列的空”或 满”不能以头尾指针是否相等来确定，一般是通过以下几种方法：一个是另设一个布尔变量来区别队列的空和满；二是少用一个元素的空间，每次入队前测试入队后头尾指针是否会 重合，如果会重合就认为队列已满；三是设置一个计数器记录队列中元素总数，不仅可判别空或满，还可 以得到队列中元素的个数。(第四章)1 .试回答空串与空格串有何区别？答：空串是不含任何字符的串，长度为0,空格串是有空格字符组成的串，串的长度为空格的个数。2 .试找出分别满足下面条件的所有二叉树(1)前序序列和中序序列相同。答：空二叉树或没有左子树的二叉树(右单支树)(2)中序序列和后序序列相同。答：空二叉树或没有右子树的二叉树(左单支树)(3)前序序列和后序序列相同。答：空二叉树或只有根的二叉树。(4)前序、中序、后序序列相同。答：空树或只有根结点的二叉树3