数据结构期末试题

数据结构课后练习题一、填空题（第二章）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==head。（第三章）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*+/+6.在操作序列push（1）；push（2）;pop(2);push（3）；push（4）；push（5）；push（6）；push（7）；pop(7)之后栈顶元素和栈底元素分别是6和1。7.在操作序列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个或多个字符组成的序列。2.不包含任何字符串称为空串；由一个或多个空格组成的串称为空格串。3.子串的定位运算称为串的模式匹配；被匹配的主串称为目标串，子串称为模式。（第五章）1.广义表的深度是等于括号嵌套的最大层数。2.在广义表的存储结构中，每个结点均包含3个域。3.一个广义表的深度等于括号嵌套的最大层数。4.对矩阵压缩是为了节省存储空间。5.当广义表中的每个元素都是原子时，广义表便成了线性表。6.广义表的表尾是指除第一个元素之外，其余元素组成的表。7.广义表的深度定义为广义表中括弧的重数。8.设广义表L=（（），（）），则hesd（L）是（）；tail（L）是（（））；L的长度是2；深度是2。9.广义表（a，（a,b）,d,e,((i,j),k)）的长度是5，深度是3。（第六章）1.对于一棵具有n个结点的树，该树中所有结点的度数之和为n-1。2.一颗=棵深度为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和6个。5.假定一棵树的广义表表示为A（B(C,D(E,F,G),H(I,J))），则结点H的双亲结点为B，孩子结点为I和J。6.在哈夫曼编码中，若编码长度只允许小于等于4，则除了已对两个字符编码为0和10外，还可以最多对4个字符编码。7.对于一棵二叉树，若一个结点的编码为i，则它的左孩子结点的编号为2i，右孩子结点的编号为2i+1，双亲结点编号为i/2。8.在一棵二叉树中，第5层上的结点数最多为16。9.假定一棵二叉树的结点树为18，则它的最小深度为5，最大深度为18。10.假定一棵二叉树顺序存储在一维数组a中，则a[i]元素的左孩子元素为a[2i]，右孩子元素为a[2i+1]，双亲元素（i-1）为a[i/2]。11.假定一棵二叉树顺序存储在一维数组a中，但让编号为1的结点存入a[0]元素中，让编号为2的结点存入a[1]元素中，其余类推，则编号为i结点的左孩子结点对应的存储位置为2i-1。12.对于一棵具有n个结点的二叉树，对应二叉链接表中指针总数为2n个，其中n-1个用于指向孩子结点，n+1个指向空闲着。13.一棵二叉树广义表表示为a(b(d(h)),c(e,f(g,i(k)))),该树的结点数为10个，深度为5。14.假定一棵二叉树广义表表示为a（b(c),d((e,f))）,则对它进行的先序遍历结果为abcdef,中序遍历结果为cbaedf，后续序遍历结果为cbefda。（第七章）1.有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的出度。2.图的逆邻接表存储结构之适用于有向图。3.图的深度优先遍历序列不是唯一的。4.图的BFS生成树的树高比DFS生成树的树高矮或相当。5.拓扑排序输出的顶点数小于有向图的顶点数，则该图一定存在环。6.若要求一个稀疏图G的最小生成树，最好用Kruskal算法来求解。（第八章）1.关键字是数据元素（或记录）中某个属性,用它的标识(或识别)一个查找表中的数据元素（或记录）。并且，在一个查找表中，能够唯一标识一个数据元素（或记录）的关键字称为主关键字。2.查找又称为（检索），它是根据给定的某个值，在查找表中确定是否有元素或记录的关键字等于给定值的操作。若操作之后确定表中存在这样的记录，则称为查找是成功的，否则称为不成功（或失败）。3.平均查找长度是指为确定所查找的记录在查找表中的位置，需要与给定值进行比较的关键字个数的平均值（或期望值）。4.采用顺序查找法查找长度为n大的线性表时，假设查找成功与查找不成功的概率对等，对每个记录的查找概率也相等，则平均查找长度为3（n+1）/4。5.折半查找又称为二分查找，其查找思路是：每次将给定值与查找表中所要查找区域中间位置的关键字进行比较，而不是查找表中的第一条或最后一条。6.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是哈希表查找法。7.哈希表的查找小绿主要取决于哈希表建表时选择的哈希函数和装填因子。8.构造哈希函数的方法有直接定址法、数字分析法、平方取中法、折叠法和除留余数法。9.假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入哈希表中，至少要进行（K/1）K/2次探测。10.二叉排序树又称为二叉查找树，它或者是一棵空树，或者是具有下列性质的一棵二叉树；（1）若左子树不空，则左子树上所有结点的值小于根结点的值。（2）若右子树不空，则左子树上所有结点的值大于根结点的值。（3）左、右子树又分别是一棵二叉排序树。11.平衡二叉树是有Abelson-Velskil和Landis提出的一种附加一定限制条件的二叉树。又称为AVL树。平衡二叉树定义为：它或者是一棵空树；或者是具有这样性质的二叉树；它的左子树和右子树都是一棵平衡二叉树，且左子树和右子树的深度之差绝对值不大于1。12.在向哈希表中存储关键字的时候，有时会出现一个待插入关键字的记录已经被占用的情况，这种对不同关键字得到同一地址的现象称为冲突（或碰撞），相应的把这些具有相同哈希函数值得关键字称为同义词。13.构造哈希函数应当尽量减少冲突，但是还是无法避免冲突的发生，一旦冲突发生了，就必须讯企鹅合适的方法来解决冲突。常用开放地址法和链地址法两种方法来解决冲突。14.对长度n=50的有序表进行折半查找，则对应的判定树高度为6，判定树前5层的结点树是31，最后一层的结点树为9。二、单选题（第二章）1、线性表L=（a1,a2,…,ai,…,an），下列说法正确的是（D）A、每个元素都有一个直接前驱和直接后继B、线性表中至少有一个元素C、表中诸元素的排列顺序必须是从小到大或由大到小D、除第一个元素和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。2、对于顺序表，以下说法错误的是（A）A、顺序表是一维数组实现的线性表，数组的下标可以看成是元素的绝对地址B、顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C、顺序表的特点是逻辑结构中相邻的结点在存储结构中仍相邻D、顺序表的特点是逻辑上相邻的元素，存储在物理位置也相邻的单元中3、对顺序表上的插入、删除、算法的时间复杂度分析来说，通常以（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)/2D、(n+1)/27、带头结点的单链表head为空的条件是（B）A、head=NULLB、head-next=NULLC、head-next=headD、head!=NULL8、非空循环单链表head的尾结点*p满足（C）A、p-next=NULLB、p=NULLC、p-next=headD、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-next-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的不同排列个数为（B）。A.4B5C6D72.和顺序栈相比，链栈有一个比较明显的优势是（A）。A通常不会出现栈满的情况B通常不会出现栈空的情况C插入操作更容易实现D删除操作更容易实现3.若一个栈的输入序列是1、2、3、4……、n，输出序列第一个元素是n，则第i个输出元素是(C)。A不确定Bn-iCn-i+1Dn-i-14.一个栈的入栈序列是a、b、c、d、e，则栈的不可能输出序列是（C）Ae、d、c、b、aBd、e、c、b、aCd、c、e、a、bDa、b、c、d、e5.一个队列的入队列是1、2、3、4，则队列的可能输出序列是（B）A.4、3、2、1B.1、2、3、4C.1、4、3、2D.3、2、4、16.顺序列队的出队操作为（B）Asq.front=(sq.front+1)%maxsizeBsq.front=sq.front+1Csq.rear=(sq.rear+1)maxsizeDsq.rear=sq.rear+17.循环队列q的出队操作为（A）Aq,front=(q.front+1)%maxsizeBq.front=q.front+1Cq.rear=(q.rear+1)%maxisizeDq.rear=q.rear+18.循环队列用数组A[0，m-1]存放其元素值，已知其头、尾指针分别是front和rear，则当前队列中的元素个数是（A）。A.(rear-front+m)%mBread-front+1C.read-front-1D.read-front9.在一个链队中，假设f和r分别为队首和队尾指针，则删除一个结点的运算是（C）。A,r=f-nextB.r=r-nextC.f=f-nextDf=r-next（第四章）1.串是（D）A.一些符号构成的序列B.一些字母构成的序列C