数据结构（本）期末综合练习-王春凤

数据结构（本）期末综合练习练习一一、单项选择题1．栈和队列的共同特点是（）。A.元素都可以随机进出B.都是先进先出C.都是先进后出D.都是操作受限的线性结构2.数据的存储结构包括数据元素的表示和（）。A.数据处理的方法B.数据元素间的关系的表示C.相关算法D.数据元素的类型3．对一个栈顶指针为top的链栈进行入栈操作，通过指针变量p生成入栈结点，则执行：p=(structnode*)malloc(sizeof(structnode);p->data=a;和（）。A.top->next=p;p=top;B.p->nex=top;top=p;C.top=top->next;p=top;D.p->next=top;p=top;4．树状结构中数据元素的位置之间存在（）的关系。A．每一个元素都有一个直接前驱和一个直接后继B．一对一C．多对多D．一对多5．设头指针为head的非空的单向链表,指针p指向尾结点,则通过以下操作()可使其成为单向循环链表。A．p->next=NULL;B．head=p;C．p->next=head;D．p=head;6．设有一个长度为26的顺序表，要插入一个元素,并使它成为新表的第6个元素,需移动元素的个数为（）。A．21B．22C．20D．197．一种逻辑结构（）。A．只能有唯一的存储结构B．可以有不同的存储结构C．与存储该逻辑结构的计算机相关D．是指某一种数据元素的性质8．头指针为head的带头结点的单向循环链表，p所指向尾结点，要使该链表成为不带头结点的单向循环链表,可执行head=head->nex;和（）。A．p=head->nextB．head->next=pC．head->next=p->nextD．p->next=head;9．把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（）。A．存储结构B．逻辑结构C．数据元素的存储D.给数据元素分配存储空间10．元素111，113，115，117按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。A．117，115，113，111B．111，113，115，117C．117，115，111，113D．113，111，117，11511．图状结构中数据元素的位置之间存在（）的关系。A．一对一B．一对多C．多对多D．每一个元素都有一个且只有一个直接前驱和一个直接后继12．以下说法正确的是（）。A．栈的特点是先进先出B．栈的特点是先进后出C．队列的特点是先进后出D.栈和队列的特点都是后进后出13．一个单链表中,在p所指结点之后插入一个s所指的结点时，可执行:s->next=p->next;和（）。A．s=p->next;B．p->next=s->next;C．p=s->next;D．p->next=s;14.设有一个20阶的对称矩阵A(第一个元素为a1,1)，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵元素a6,2在一维数组B中的下标是（）。A．21B．28C．17D．2315．元素12，14，16，18顺序依次进栈，则该栈的不可能输出序列是（）。（进栈出栈可以交替进行）。A．18，16，14，12B．12，14，16，18D．14，12，18，16D．18，16，12，1416．设有串p1=”ABADF”,P2=”ABAFD”，P3=”ABADFA”,P4=”ABAF”,以下四个串中最大的是()。A．p3B．p2C．p1D．p417．设有一个30阶的对称矩阵A(第一个元素为a1,1)，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a9,2在一维数组B中的下标是（）。A．41B．32C18.数组a经初始化chara[]=“English”;a[7]中存放的是（）。A.字符串的结束符B.字符hC.〝h〞D.变量h19．设有一个长度为32的顺序表，要删除第8个元素需移动元素的个数为（）。A．15B．22C．14D．2420.设主串为“ABcCDABcdEFaBc”，以下模式串能与主串成功匹配的是（）。A.BcdB.BCdC.ABCD.Abc21.在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（）。A．2iB．2i-1C22．在一棵二叉树中，若编号为i的结点存在左孩子，则左孩子的顺序编号为（）。A．2i+1B．2i-1C．2i23．一棵具有16个结点的完全二叉树，共有（）层。(设根结点在第一层)A．7B．6C．4D．524．如图1所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。A．abecdfB．aebcfdC．aecbdfD．aedfcbbdbdfeca图125．如图2所示，若从顶点a出发，按图的深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。A．abecdfgB．acfebgdC．aebcfgdD．aedfcgbbbdfecag图226．线性表以（）方式存储，能进行折半查找。A．链接B．顺序C．关键字有序的顺序D．二叉树27.字符串“DABcdabcd321ABC”的子串是()。A.“cd32”B.“ABcD”C.“aBcd”D.“321a”28．一棵具有38个结点的完全二叉树，最后一层有（）个结点。A．7B．5C．6D．829．如图3所示，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。A．abcdfgeB．abcdfegC．acbfedgD．abcfgdeggfabdec图330.下图4的拓扑序列是()。A．52346B．23645C．56234D.23564 2234543465图4二、填空题1.对稀疏矩阵进行压缩存储,可采用三元组表，一个有10行的稀疏矩阵A共有97个零元素，其相应的三元组表共有3个元素。该矩阵A有列。2．结构中的数据元素存在多对多的关系称为________结构。3．在单向链表中，q指向p所指结点的直接后继结点，要删除q所指结点，可以用操作______=q->next;。4.n个元素进行冒泡法排序，第j趟冒泡要进行______次元素间的比较。5.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的行下标、列下标和_______三项信息。6．中序遍历________树可得到一个有序序列。7.队列的操作特点是后进________。8.待排序的序列为8,3,4,1,2,5,9,采用直接选择排序算法,当进行了两趟选择后,结果序列为()。9．n个元素进行冒泡法排序，通常需要进行________趟冒泡。10广义表((a,b),d,e,((i,j),k))的长度是________。11．中序遍历二叉排序树可得到一个________的序列。12.广义表的(c，a,(a,b),d,e,((i,j),k))深度是________。13.广义表(c,a,(a,b),d,e,((i,j),k))的长度是________。14.对稀疏矩阵进行压缩存储,可采用三元组表，一个有10行10列的稀疏矩阵A共有95个零元素，其相应的三元组表共有个元素。15.广义表的(c,a,(a,b),d,e,((i,j),k))深度是________。16．在对一组记录(50,49,97,22,16,73,65,47,88)进行直接插入排序时，当把第7个记录65插入到有序表时，为寻找插入位置需比较_________次。17.循环队列在规定少用一个存储空间的情况下，队空的判定条件为________。18.一棵有5个叶结点的哈夫曼树,该树中总共有_____个结点。19.c语言中,字符串“E”存储时占个字节。20.设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有_______个结点。（根所在结点为第1层）。21．一棵二叉树中有n个非叶结点，每一个非叶结点的度数都为2，则该树共有_______个叶结点。22．设有一个长度为40的顺序表，要删除第8个元素需移动元素的个数为_______。23．在对一组记录(55,39,97,22,16,73,65,47,88)进行直接插入排序时，当把第7个记录65插入到有序表时，为寻找插入位置需比较_________次。24.有以下程序段chara[]=“English”;char*p=a;intn=0;while(*p!=‘\0’){n++;p++;}结果中，n的值是_______。三、综合题1．设查找表为(1,10,11,14,23,27,29,55,68),元素的下标依次为1,2,3,……，9。（1）画出对上述查找表进行折半查找所对应的判定树（树中结点用下标表示）。（2）说明成功查找到元素14,需要依次经过与哪些元素的比较？共几次比较？（3）求在等概率条件下，成功查找的平均比较次数？.2．有一个长度为11的有序表(1,2,11,15,24,28,30,56,69,70,80),元素的下标依次为1,2,3,……,11，按折半查找对该表进行查找。(1）画出对上述查找表进行折半查找所对应的判定树。（2）说出成功查找到元素56,,需要依次经过与哪些元素的比较？（3）说出不成功查找元素72,需要进行元素比较的次数？3．(1)以3，4，5，8，9，作为叶结点的权，构造一棵哈夫曼树。(2)给出相应权重值叶结点的哈夫曼编码。(3)n个叶结点的哈夫曼树，总共有多少个结点？4.(1)一组记录的关键字序列为（57，90，67，50，51，56），利用堆排序（堆顶元素是最小元素）的方法建立初始堆（要求以完全二叉树描述）。(2)对关键字序列(56,51,71,54,46,106)利用快速排序，以第一个关键字为分割元素，给出经过一次划分后结果。(3)一组记录的关键字序列为（60,47，80，57，39，41，46,30），利用归并排序的方法,分别给出(1,1)归并、(2,2)归并、(4,4)归并的结果序列。四、程序填空题1．以下是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。avoidInorder(structBTreeNode*BT)a{cbif(BT!=NULL){cb（1）;ed（2）;edInorder(BT->right);}f}f利用上述程序对右图进行遍历，结果是（3）;图图52.设线性表为（16，20，26，24），以不带头结点的单向链表存储，链表头指针为head,以下程序的功能是输出链表中各结点中的数据域data。structnode{intdata;structnode*next;};typedefstructnodeNODE;#defineNULL0voidmain(){NODE*head,*p;p=head;/*p为工作指针*/do{printf(“%d\n”,___(1)_____);___(2)_____;}while(___(3)_____);}3．以下冒泡法程序对存放在a[1]，a[2]，……，a[n]中的序列进行排序，完成程序中的空格部分，其中n是元素个数，要求按升序排列。voidbsort(NODEa[],intn){NODEtemp;inti,j,flag;for(j=1;（1）;j++);{flag=0;for(i=1;（2）;i++)if(a[i].key>a[i+1].key){flag=1;temp=a[i];（3）;（4）;}if(flag==0)break;}}设有序列6，4，5，8，2，1，给出由该程序经过两趟冒泡后的结果序列（5）4.以下函数为直接选择排序算法，对a[1],a[2],…a[n]中的记录进行直接选择排序，完成程序中的空格typedefstruct{intkey;……}NODE;voidselsort(NODEa[],intn){ inti,j,k; NODEtemp; for(i=1;i<=___(1)_____;i++) { k=i; for(j=i+1;j<=(2)_____;j++) if(a[j].key<a[k].key)(3)______; if(i!=k) { temp=a[i]; (4)_____; (5)____; } }}练习一答案一、单项选择题1．C2．B3．B4．D5．C6．A7．B8．D9．A10．C11．C12．B13．D14．C15．D16．B17．D18．A19．D20．A21.C22．C23.D24．C25.D26．C27.A28．A29.A30．C二、填空题1．102．图状3．p->next;4．n-j5．数组元素6．二叉排序树7．后出8．1，2，4，8，3，5，99．n-110．411．有序12．313．614．515．316．317.front==rear18．919.220.1221.n+122．3223.324．7三、综合题1．63639481275图6(2)按序号5,2,3,4。按元素23，10，11，144次(3)ASL=(1+2*2+3*4+4*2)/9=25/92．30158030158056662427011169286图7(2)28,69,30,56(3)4次3.8181221222517529187349图8(2)3:0004:0015:018:109:11(3)2n-14．(1)50505156579067图9(2)46,51,54,56,71,106(3)(47,60)(57,80)(39,41)(30,46)(47,57,60,80)(30,39,41,46)(30,39,41,46,47,57,60,80)四、程序填空题1.（1）Inorder(BT->left)（2）printf(“%c”,BT->data)（3）dbfeac2．（1）p->data（2）p=p->next（3）p!=NULL3．（1）j<=n-1（2）i<=n-j（3）a[i]=a[i+1]（4）a[i+1]=temp（5）4,5,2,1,6,84．（1）n-1（2）n（3）k=j（4）a[i]=a[k](5)a[k]=temp练习二一、单项选择题1．下面关于线性表的叙述错误的是（）。A.线性表采用顺序存储必须占用一片连续的存储空间 B.线性表采用链式存储不必占用一片连续的存储空间C.线性表采用顺序存储便于插入和删除操作的实现D.线性表采用链式存储便于插入和删除操作的实现2．设有头指针为head的不带头结点的非空的单向循环链表,指针p指向其尾结点,要删除第一个结点,则可利用下述语句head=head->next;和（）。A．p=head;B．p=NULL;C．head=p;D．p->next=head;3.以下数据结构中是非线性结构的是()。A.队列B.栈C.二叉树D.线性表4.以下说法正确的是()。A.线性表的链式存储结构必须占用连续的存储空间B.一种逻辑结构可以有不同的存储结构C．一种逻辑结构只能有唯一的存储结构D．线性表的顺序存储结构不必占用连续的存储空间5．设有一个长度为18的顺序表，要删除第7个元素需移动元素的个数为（）。A．13B．12C．11D．106．把数据存储到计算机中，并具体体现()称为物理结构。A．数据的处理方法B．数据的性质C．数据的运算D.数据元素间的逻辑关系7.两个字符串相等的充要条件是（）。 A.两个字符串的长度相等 B.同时具备(A)和(C)两个条件C.两个字符串中对应位置上的字符相等D.以上答案都不对8．顺序表所具备的特点之一是（）。A．可以随机访问任一结点B．不需要占用连续的存储空间C．插入元素的操作不需要移动元素D．删除元素的操作不需要移动元素9.设某链表中最常用的操作是在链表的尾部插入或删除元素，在已知尾指针的条件下,选用下列（）存储方式最节省运算时间。A.单向链表 B.单向循环链表C.双向链表 D.双向循环链表10．图状结构中数据元素的位置之间存在（）的关系。A．一对一B．一对多C．多对多D．每一个元素都有一个直接前驱和一个直接后继11．元素13，15，19，20顺序依次进栈，则该栈的不可能输出序列是（）。进栈出栈可以交替进行）。A．20，19，15，13B．13，15，19，20C．19，13，15，20D．15，13，20，1912．元素20，14，16，18按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。A．18，16，14，20B．20，14，16，18C．18，16，20，14D．14，20，18，1613．设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，则在表中删除结点B的操作为（）。A.p->next；=q； B.q->next=p->next；C.p->next=q->next；； D.q->next=p；14．设有一个12阶的对称矩阵A(左上角第一个元素为a1,1)，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a5,4在一维数组B中的下标是（）。A．12B．14C．13D．1115.栈和队列的共同特点之一是()。A.都是先进后出B..都是先进先出C.只允许在端点处插入和删除元素D.没有共同点16．设有一个长度为22的顺序表，要删除第8个元素需移动元素的个数为（）。A．25B．14C．15D．2317.用链接方式存储的队列，在进行插入运算时()。A.需修改头指针B.头、尾指针都需要修改C.需修改尾指针D.头、尾指针都不需要修改18．在一棵二叉树中，若编号为5的结点存在右孩子，则右孩子的顺序编号为（）。A．12B．9C．11D．1019.字符串a1=“AEIJING“，a2=〝AEI“，a3=〝AEFANG〞a4=”AEFI“中最大的是（）。A.a1B.a2C.a3D.a420．一棵具有5层的完全二叉树，最后一层有4个结点，则该树总共有（）个结点。A．14B．15C．19D．1821．设有一个20阶的对称矩阵A(第一个元素为a1,1)，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a6,2在一维数组B中的下标是（）。A．23B．17C．21D．1822.如图1所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。A．abcdfgeB．abcedfgC．acbfedgD．abcfgdeggfabdec图123.以下说法正确的是()。A.若二叉树中左子树上所有结点的值均小于根结点的值，右子树上所有结点的值均大于根结点的值。则该树为二叉排序树。B.二叉树中任意一个非叶结点的值都大于其左子树上所有结点的值,小于其右子树上所有结点的值,则该树为二叉排序树。C.二叉树中任意一个结点的值均大于其左孩子的值，小于其右孩子的值。则该树为二叉排序树。D.前序遍历二叉排序树可得到一个有序序列。24.字符串〝abcd321ABCD〞的子串是（）。A.〝21ABC〞B.〝abcABCD〞C.abcDD.〝321a〞25.二叉树的第k层的结点数最多为()。A.2K-1B.2K+1C.2k-1D.2k-126.数组a经初始化chara[]=“English”;a[1]中存放的是（）。A.字符EB.字符nC.〝n〞D.〝E〞27.如图2所示，若从顶点6出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。A．6,9,3,2,8,7,4B．6,9,2,3,7,8,4C．6,2,7,9,8,4,3D．6,2,8,7,9,3,433289674图228．如图3所示，若从顶点a出发，按图的深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。A．abecdfB．acfebdC．aebcfdD．aedfcbbbdfeca图329.如图4所示，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。A．abcfegdB．acbfedgC．abcdfgeD．abcfgdeggfabdec图430.下图5的拓扑序列是()。A．52346B.23456C．56423D．523642234543465图5二、填空题1.设：chara[]=“AEIJING“;该字符串在计算机中存储时占________个字节。2.栈的特点之一是：元素进、出栈的次序是:先进_______。3．结构中的数据元素存在多对多的关系称为________结构。4．对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的三项信息是_______。5.对稀疏矩阵进行压缩存储,可采用三元组表，一个有8行的稀疏矩阵A共有92个零元素，其相应的三元组表共有4个元素。该矩阵A有________列。6．在对10个记录的序列(9，35,19,77,2,10,53,45,27,68)进行直接插入排序时，当把第6个记录10插入到有序表时，为寻找插入位置，元素间需比较_________次。（按升序排序）7.循环链队列中，设front和rear分别为队头和队尾指针，最大存储空间元素为MaxSize,采用少用一个存储空间的模式，则判断循环链队列为空的条件是______为真。8.字符串a1=〝beijing〞,a2=〝bef〞,a3=〝beifang〞,a4=“befi〞最小的是________。9.n个元素进行冒泡法排序，第j趟冒泡要进行______次元素间的比较。10．10个元素进行冒泡法排序，,其中第5趟冒泡共需要进行________次元素间的比较。11．设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有_______个结点。（根所在结点为第1层）12．________遍历一棵二叉排序树可得到一个有序序列。13．中序遍历一棵________树可得到一个有序序列。14.广义表(c,(a,b,c),(d,e,f),((i,j),k))的长度是_______。15.待排序的序列为9,4,5,1,2,6,10,采用直接选择排序算法,当进行了两趟选择后,结果序列为________。16.广义表的(c,(b,a,b),f,e,((i,j),k))深度是________。17.广义表((a,b),d,e,((i,j),k))的长度是________。18.序列4,2,5,3,8,6,采用冒泡排序算法(升序),经一趟冒泡后,结果序列是________。19.广义表的(c，a,(a,b),d,e,((i,j),k))深度是________。20.待排序的序列为8,3,4,1,2,5,9,采用直接选择排序算法,当进行了两趟选择后,结果序列为________。21.线性表用________方式存储需要占用连续的存储空间。22.线性表用________方式存储可以随机访问。23.线性表用关键字________的顺序方式存储，可以用二分法排序。24.顺序表,,6，5，1,2,4,3,8，7经过一趟(1,1)归并后的结果序列为________。三、综合题1．（1）设有数据集合{40，29，7，73，101，4，55，2，81，92，39}，依次取集合中各数据构造一棵二叉排序树。(2)在上述二叉排序树上进行查找，给出成功查找到元素92的查找路径,其中共经过了多少次元素间的的比较。(3)有一个长度为10的有序表，按折半查找对该表进行查找，给出在等概率情况下查找成功的平均比较次数为。2．设查找表为序号1234567891011序列8162223415969818990121（1）画出对上述查找表进行折半查找所对应的判定树。（2）说明成功查找到元素90需要经过多少次比较？（3）说明不成功查找元素82，依次与哪些元素进行了比较，需要经过多少次比较？3.(1)以2，3，4，7，8，9作为叶结点的权，构造一棵哈夫曼树，(2)给出相应权重值叶结点的哈夫曼编码。(3)一组记录的关键字序列为（47，80，57，39，41，46），利用堆排序的方法建立的初始堆（堆顶元素是最小元素,以树的形式给出）。4.(1)一组记录的关键字序列为（36，69，46，28，30，35），给出利用堆排序（堆顶元素是最小元素）的方法建立的初始堆（要求以完全二叉树描述）。(2)对关键字序列(36,69,46,28,30,74)采用快速排序，给出以第一个关键字为分割元素，经过一次划分后的结果。(3)设有数据集合{30,73,101,4,8,9,2,81}，依次取集合中各数据构造一棵二叉排序树。程序填空题1.设线性表为（1,3,7,5），以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。structnode{intdata;structnode*next;};typedefstructnodeNODE;#defineNULL0voidmain(){NODEa,b,c,d,*head,*p;a.data=6;b.data=10;c.data=16;d.data=4;/*d是尾结点*/head=（1）;a.next=&b;b.next=&c;c.next=&d;（2）;/*以上结束建表过程*/p=head;/*p为工作指针，准备输出链表*/do{printf(“%d\n”,（3）);（4）;}while(p!=NULL);}画出按该程序建立的单向链表的示意图，说明程序运行结束后p的指向。（5）2．设查找表为序号1234567891011序列8162223415969818990121（1）画出对上述查找表进行折半查找所对应的判定树。（2）说明成功查找到元素90需要经过多少次比较？（3）说明不成功查找元素82，依次与