数据结构练习题

数据构造练习题：1．下面有关线性表的论述错误的是（D）。(A)线性表采用次序存储必须占用一片持续的存储空间 (B)线性表采用链式存储不必占用一片持续的存储空间(C)线性表采用链式存储便于插入和删除操作的实现(D)线性表采用次序存储便于插入和删除操作的实现2．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储构造，则该哈夫曼树中总共有（B）个空指针域。 (A)2m-1 (B)2m (C)2m+1 (D)4m3．设次序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的目前位置，则该循环队列中的元素个数为（C）。 (A)R-F (B)F-R (C)(R-F+M)％M (D)(F-R+M)％M4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（A）。 (A)BADC (B)BCDA (C)CDAB (D)CBDA5．设某完全无向图中有n个顶点，则该完全无向图中有（A）条边。 (A)n(n-1)/2 (B)n(n-1) (C)n2 (D)n2-16．设某棵二叉树中有个结点，则该二叉树的最小高度为（C）。 (A)9 (B)10 (C)11 (D)127．在数据构造中，从逻辑上可以把数据构造分为(D)A.动态构造和静态构造B.紧凑构造和非紧凑构造C.内部构造和外部构造D.线性构造和非线性构造8．已知图的邻接表如下所示，根据算法，则从顶点V0出发按广度优先遍历的结点序列是(A)A．0321B.0123C.0132D.03129．若进栈序列为a,b,c,d,e,则栈的不也许的输出序列是(B)A.edcbaB.dceabC.decbaD.abcde10．把一棵树转换为二叉树后，这棵二叉树的形态是(A)。A.唯一的B.有多种C.有多种，但根结点都没有左孩子D.有多种，但根结点都没有右孩子11.为查找某一特定单词在文本中出现的位置，可应用的串运算是(

D

)

A.插入

B.删除

C.串联接

D.子串定位12.ALV树是一种平衡的二叉树，树中任一结点的(

B

)

A.左、右子树的高度均相似

B.左、右子树高度差的绝对值不超过1

C.左子树的高度均不小于右子树的高度

D.左子树的高度均不不小于右子树的高度13.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储构造为(

C

)

A.次序表

B.用头指针表达的单循环链表

C.用尾指针表达的单循环链表

D.单链表14.二叉树是非线性数据构造，因此(C)。Ａ.它不能用次序存储构造存储;B.它不能用链式存储构造存储;C.次序存储构造和链式存储构造都能存储;D.次序存储构造和链式存储构造都不能使用15.用邻接表表达图进行广度优先遍历时，一般是采用(B)来实现算法的。A．栈B.队列C.树D.图16．数据的最小单位是（A）。 (A)数据项 (B)数据类型 (C)数据元素 (D)数据变量17．设某棵二叉树中有个结点，则该二叉树的最小高度为（C）。 (A)9 (B)10 (C)11 (D)1218．函数substr(“DATASTRUCTURE”，5，9)的返回值为（A）。 (A)“STRUCTURE” (B)“DATA” (C)“ASTRUCTUR” (D)“DATASTRUCTURE”19．设某完全无向图中有n个顶点，则该完全无向图中有（A）条边。 (A)n(n-1)/2 (B)n(n-1) (C)n2 (D)n2-120．深度为k的完全二叉树中至少有（B）个结点。 (A)2k-1-1 (B)2k-1 (C)2k-1+1 (D)2k-121．设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（B）。 (A)abedfc (B)acfebd (C)aebdfc (D)aedfcb22．设输入序列是1、2、3、……、n，通过栈的作用后输出序列的第一种元素是n，则输出序列中第i个输出元素是（C）。 (A)n-i (B)n-1-i (C)n+1-i (D)不能确定23.为查找某一特定单词在文本中出现的位置，可应用的串运算是(

D

)

A.插入

B.删除

C.串联接

D.子串定位24．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（B）次。 (A)25(B)10(C)7(D)125.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储构造为(

C

)

A.次序表

B.用头指针表达的单循环链表

C.用尾指针表达的单循环链表

D.单链表26.把一棵树转换为二叉树后，这棵二叉树的形态是(A)。A.唯一的B.有多种C.有多种，但根结点都没有左孩子D.有多种，但根结点都没有右孩子27.已知图的邻接表如下所示，根据算法，则从顶点V0出发按广度优先遍历的结点序列是(A)A．0321B.0123C.0132D.031228.二叉树是非线性数据构造，因此(C)。Ａ.它不能用次序存储构造存储;B.它不能用链式存储构造存储;C.次序存储构造和链式存储构造都能存储;D.次序存储构造和链式存储构造都不能使用29.数组Ｑ［ｎ］用来表达一种循环队列，ｆ为目前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数不不小于ｎ，计算队列中元素的公式为(D)。A.r－f;B.（n＋f－r）%n;C.n＋r－f;D.（n＋r－f）%n30.用邻接表表达图进行广度优先遍历时，一般是采用(B)来实现算法的。A．栈B.队列C.树D.图31．1．for(i=1，t=1，s=0；i<=n；i++){t=t*i；s=s+t；}的时间复杂度为O（n）。32．下面程序段的功能是实现冒泡排序算法，请在下划线处填上对的的语句。voidbubble(intr[n]){for(i=1;i<=n-1;i++){for(exchange=0,j=0;j<n-i;j++)if(r[j]>r[j+1]){temp=r[j+1];r[j+1]=r[j];r[j]=temp;exchange=1;}if(exchange==0)return；}}33．中序遍历二叉排序树所得到的序列是有序序列（填有序或无序）。34．迅速排序的最坏时间复杂度为O(n2)，平均时间复杂度为O(nlog2n)。35．设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中度数为2的结点数为N0-1；若采用二叉链表作为该二叉树的存储构造，则该二叉树中共有2N0+N1个空指针域。36．设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=d/2。37．设一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，则运用筛选法建立的初始堆为(31，38，54，56，75，80，55，63)。38．设F和R分别表达次序循环队列的头指针和尾指针，则判断该循环队列为空的条件为F==R。39．下面程序段的功能是实现二分查找算法，请在下划线处填上对的的语句。structrecord{intkey;intothers;};intbisearch(structrecordr[],intk){intlow=0,mid,high=n-1;while(low<=high){mid=(low+high)/2;if(r[mid].key==k)return(mid+1);elseif(r[mid].key>k)high=mid-1;elselow=mid+1;}return(0);}40．若次序表每个元素长度均为5，其中第一种元素的存储地址为30，则第6个元素的存储地址为55。41．栈的插入和删除只能在栈的栈顶进行，后进栈的元素必然先出栈，因此又把栈称为先进后出表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必然先出队列，因此又把队列称为先进先出表。42．次序表中逻辑上相邻的元素的物理位置必然紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。（对）43．设一棵完全二叉树有128个结点，则该完全二叉树的深度为8，有64个叶子结点。（对）44．满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（对）45．设一棵二叉树的先序序列和后序序列，则可以唯一确定出该二叉树的形状。（错）46.栈和链表是两种不一样的数据构造。（错）47.具有12个结点的完全二叉树有5个度为2的结点。（对）48.关键途径是事件结点网络中的从源点到汇点的最短途径。（错）49.由树转化成二叉树，该二叉树的右子树不一定为空。（错）50.堆排序是不稳定的排序措施。（对）51．调用一次深度优先遍历可以访问到图中的所有顶点。（错）52．分块查找的平均查找长度不仅与索引表的长度有关，并且与块的长度有关。（对）53．冒泡排序在初始关键字序列为逆序的状况下执行的互换次数最多。（对）54．已知一棵二叉树的先序序列是ABCDEFGHIJK，中序序列是CDBGFEAHJIK，请构造出该二叉树55．设给定权集W={5,7,2,3,6,8,9},请构造画出有关W的一棵赫夫曼树，并求出其加权途径长度WPL。9985671051323172340加权途径长度：WPL=2*4+3*4+5*3+6*3+7*3+8*2+9*2=10856．对如下所示的带权图：77v2v6v5v3v7v8v121113212241312v422(1)分别按照克鲁斯卡尔算法和普里姆算法，从顶点v1出发，生成最小生成树，按生成次序依次写出各条边；(2)画出该图最小生成树，并求出它的权值之和。57、下图所示的森林：(1)求树（a）的先根序列和后根序列；(2)求森林先序序列和中序序列；(3)将此森林转换为对应的二叉树；(1)先根序列：ABCDEF;后根序列：BDEFCA；(2)先序序列：ABCDEFGHIJK;中序序列：BDEFCAIJKHG(3)森林转换为对应的二叉树；58．设一组初始记录关键字序列为(15，17，18，22，35，51，60)，规定计算出使用折半查找查找成功时的平均查找长度。59.编写递归算法，计算二叉树中叶子结点的数目。intLeafCount_BiTree(BitreeT)//求二叉树中叶子结点的数目{if(!T)return0;//空树没有叶子elseif(!T->lchild&&!T->rchild)return1;//叶子结点elsereturnLeaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加上右子树的叶子数}//LeafCount_BiTree61．假设正读和反读都相似的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’则不是回文。试写一种算法鉴别读入的一种以‘@’为结束符的字符序列与否是“回文”。intPalindrome_Test()//鉴别输入的字符串与否回文序列,是则返回1,否则返回0

{

InitStack(S);InitQueue(Q);

while((c=getchar())!='@')

{

Push(S,c);EnQueue(Q,c);//同步使用栈和队列两种构造

}

while(!StackEmpty(S))

{

Pop(S,a);DeQueue(Q,b));

if(a!=b)returnERROR;

}

returnOK;

}//Palindrome_Test62．设计两个有序单链表的合并排序算法。voidmergelklist(lklist*ha,lklist*hb,lklist*&hc){lklist*s=hc=0;while(ha!=0&&hb!=0)if(ha->data<hb->data){if(s==0)hc=s=ha;else{s->next=ha;s=ha;};ha=ha->next;}else{if(s==0)hc=s=hb;else{s->next=hb;s=hb;};hb=hb->next;}if(ha==0)s->next=hb;elses->next=ha;}63．设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简朴选择排序和第4趟直接插入排序后的成果。（22,40,45,48,80,78），（40,45,48,80,22,78）64．已知一棵二叉树的先序序列是ABCDEFGHIJK，中序序列是CDBGFEAHJIK，请构造出该二叉树65．设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找措施用二分查找(折半查找)，规定计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。2,ASL=91*1+2*2+3*4+4*2)=25/966、已知散列函数为H(key)=keymod7，散列表长度为7(散列地址空间为0.....6)，待散列序列关键字依次为：(25，48，32，50，68)。规定(1)根据以上条件构造一散列表，并用“线性探测再散列法”处理有关地址冲突（规定写出构造过程）；(2)若要用该散列表查找元素68，试给出所需的比较次数和依次被比较的关键字。(1)散列表如图所示：01234566850253248{H(25)=25mod7=4;没有地址冲突，故填入表中4号位置；H(48)=48mod7=6;没有地址冲突，故填入表中6号位置；H(32)=32mod7=4;出现地址冲突，使用线性探测：H(32)=（4＋1）mod7＝5；没有地址冲突，故填入表中5号位置；H(50)=50mod7=1;没有地址冲突，故填入表中1号位置；H(68)=68mod7=5;出现地址冲突，使用线性探测：H(68)=（5＋1）mod7＝6；仍有地址冲突，故再次线性探测H(68)=（5＋2）mod7＝0；此时已没有地址冲突，故填入表中0号位置；散列表所有构造完毕！}//以上为注释，供参照使用！//(2)共需要比较3次；依次分别和：32，48，68进行比较。68．已知一棵二叉树的中序序列：CBEDAHGIJF,后序序列为：CEDBHJIGFA，请画出该二叉树并写出其先序序列。AABFACDGEHIJ69．已知散列函数为H(key)=keymod7，散列表长度为7(散列地址空间为0.....6)，待散列序列关键字为：(32，55，39，57，75)。规定：(1)根据以上条件构造一散列表，并用“线性探测再散列法”处理有关地址冲突（规定写出构造过程）；(2)若要用该散列表查找元素75，试给出所需的比较次数和依次被比较的关键字。①散列表如图所示：32，55，39，57，7501234567557393255{H(32)=32mod7=4;没有地址冲突，故填入表中4号位置；H(55)=55mod7=6;没有地址冲突，故填入表中6号位置；H(39)=39mod7=4;出现地址冲突，使用线性探测：H(39)=（4＋1）mod7＝5；没有地址冲突，故填入表中5号位置；H(57)=57mod7=1;没有地址冲突，故填入表中1号位置；H(75)=75mod7=5;出现地址冲突，使用线性探测：H(75)=（5＋1）mod7＝6；仍有地址冲突，故再次线性探测H(75)=（5＋2）mod7＝0；此时已没有地址冲突，故填入表中0号位置；散列表所有构造完毕！}//以上为注释，供参照使用！//②共需要比较3次。依次分别和：32，55，75进行比较。70．希尔排序、简朴选择排序、迅速排序和堆排序是不稳定的排序措施,试举例阐明。【解答】 (1)希尔排序 {512 275 275* 061}增量为2 {275* 061 512 275} 增量为1 {061 275*275 512} (2)直接选择排序 {275 275*512 061}i=1 {061 275*512 275}i=2 {061 275*512 275}i=3 {061 275*275 512} (3)迅速排序 {512 275 275*} {275* 275 512} (4)堆排序 {275275*061170}已经是最大堆，互换275与170 {170275*061275}对前3个调整 {275*170061275}前3个最大堆，互换275*与061 {061170275*275}对前2个调整 {170061275*275}前2个最大堆，互换170与061 {061170275*275}71.设给定一种权值集合W=(3，5，7，9，11)，规定根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权途径长度WPL。11119385715203573．设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找措施用二分查找(折半查找)，规定计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。2,ASL=91*1+2*2+3*4+4*2)=25/974．已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序和中序线索二叉树。后序线索二叉树如下图：中序线索自己画75．请画出下图的邻接矩阵和邻接表。(1)邻接矩阵：(2)邻接表：78．设一组初始记录关键字序列为(15，17，18，22，35，51，60)，规定计算出使用折半查找查找成功时的平均查找长度ASL=(1*1+2*2+3*4)/7=17/7。79．已知一棵二叉树的中序序列：CBEDAHGIJF,后序序列为：CEDBHJIGFA，请画出该二叉树并写出其先序序列。AABFACDGEHIJ先序序列为：ABCDEFGHIJ80．设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简朴选择排序和第4趟直接插入排序后的成果。(22，40，45，48，80，78)，(40，45，48，80，22，78)81、编写算法实现将单链表就地逆置，即不此外开辟结点空间，而将链表元素翻转次序。思绪：从链上依次取下结点，按照逆序建表的措施重新建表。voidReverse(LinkList&L){p=L->next; //原链表L->next=NULL; //新表(空表)while(p){//从原链表中取下结点ss=p;p=p->next;//插入L新表表头s->next=L->next;L->next=s;}}82、设计在链式构造上实现简朴选择排序算法。{lklist*p,*q,*s;intmin,t;if(head==0||head->next==0)return;for(q=head;q!=0;q=q->next){min=q->data;s=q;for(p=q->next;p!=0;p=p->next)if(min>p->data){min=p->data;s=p;}if(s!=q){t=s->data;s->data=q->data;q->data=t;}}}83．二叉树结点定义如下：typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;请用递归的措施设计算法，先序、中序、后序遍历各结点输出结点值。StatusPreorder(BiTreeT)（5分）{//先序遍历二叉树if(T){visit(T->data);//访问结点Inorder(T->lchild,visit);//遍历左子树Inorder(T->rchild,visit);//遍历右子树}}StatusInorder(BiTreeT)（5分）{//中序遍历二叉树if(T){Inorder(T->lchild,visit);//遍历左子树visit(T->data);//访问结点Inorder(T->rchild,visit);//遍历右子树}}StatusPostorder(BiTreeT)（5分）{//后序遍历二叉树if(T){Inorder(T->lchild,visit);//遍历左子树Inorder(T->rchild,visit);//遍历右子树visit(T->data);//访问结点}}供同学们练习用，考试以最终一次课讲课为主，如：二叉排序树，练习题没有出，但考试是有的。练习题中给出的答案，只供参照，由于诸多题是没有原则答案的。59.#include<iostream>

usingnamespacestd;

typedefstructTNode//二叉树构造

{

charnodeValue;//结点的值

TNode*left;//左子树

TNode*right;//右子树

}*BiTree;

voidCreateBiTree(BiTree&T)//中序遍历方式创立二叉树,输入#代表该结点为空

{

charnodeValue;

cin>>nodeValue;

if(nodeValue!='#')//结点非空

{

T=newTNode;

T->nodeValue=nodeValue;

CreateBiTree(T->left);

CreateBiTree(T->right);

}

elseT=NULL;

}

intCountLeaf(BiTreeT)

{

staticintLeafNum=0;//叶子初始数目为0，使用静态变量

if(T)//树非空

{

if(T->left==NULL&&T->right==NULL)//为叶子结点

LeafNum++;//叶子数目加1

else//不为叶子结点

{

CountLeaf(T->left);//递归记录左子树叶子数目

CountLeaf(T->right);//递归记录右子树叶子数目

}

}

returnLeafNum;

}

//用来测试的main函数，

intmain()

{

BiTreeT;

intleafNum;

cout<<"请输入中序遍历的二叉树序列(#号代表该结点为空)：如(ABC##DE#G##F###)"<<endl;

CreateBiTree(T);

leafNum=CountLeaf(T);

cout<<"该二叉树中叶子结点数为："<<leafNum<<endl;

return0;

}60.voidLevelOrder(BiTreebt,char*ss)

/*travelBiTreebtbylevel,Returnresultbyss.*/

{

QueueQ;

InitQueue(Q);

EnQueue(Q,bt);

inti=0;

while(!QueueEmpty(Q))

{

DeQueue(Q,bt);

ss[i]=bt->data;

if(bt->lchild)

{

EnQueue(Q,bt->lchild);

}

if(bt->rchild)

{

EnQueue(Q,bt->rchild);

}

i++;

}

}62.structnode*sorted_merge(structnode*a,structnode*b){structnoderesult;//使用一种结点用于保留成果structnode*tail=&result;if(a==NULL)returnb;//特殊状况处理elseif(b==NULL)returna;while(a&&b){if(a->data<=b->data){//a链表结点值小，加入到链表尾部，并更新tail，遍历a链表下一种结点tail->next=a;tail=a;a=a->next;}else{//b链表结点值小，加入到链表尾部，更新tail，遍历b链表下一种结点tail->next=b;tail=b;b=b->next;}}if(a)//a结点未遍历完，则加入到尾部tail->next=a;if(b)//b结点未遍历完，加入到尾部tail->next=b;returnresult.next;}84.#include<stdio.h>

#include<stdlib.h>

#definem100

typedefstruct

{

charstack[m];

inttop;

}stackstru;//定义栈

typedefstruct{

charqueue[m];

intfront;

intrear;

}queuestru;//定义队列

voidmain()

{

//函数申明

intstinit(stackstru*s);//初始化次序栈

intstempty(stackstru*s);//判断栈与否为空

intstpush(stackstru*s,charx);//入栈

charstpop(stackstru*s);//出栈

intquinit(queuestru*q);//初始化循环队列

intquempty(queuestru*q);//判断队列与否为空

intenqueue(queuestru*q,chare);//入队

chardequeue(queuestru*q);//出队

//

charc;

intflag=0;

stackstru*s=(stackstru*)malloc(sizeof(stackstru));//为次序栈申请空间

queuestru*q=(queuestru*)malloc(sizeof(queuestru));//为队列申请空间

stinit(s);//初始化栈

quinit(q);//初始化队列

printf("Inputastring:\n");//输入字符串，输入@标示输入结束。

while((c=getchar())!='@')//将输入的字符串入栈和队列

{

putchar(c);//输出输入的字符

stpush(s,c);//字符进栈

enqueue(q,c);//字符进队列

}

printf("\n");

printf("Endinput!\n");//提醒信息

while(stempty(s))//栈中尚有元素

{

if(stpop(s)==dequeue(q))//出栈的字符与出队列的字符匹配

{

flag=1;//将标志设置为1

continue;//继续从栈和队列中区字符

}

else//字符不匹配

{

flag=0;

break;//跳出循环，将标志设置为0

}

}

if(flag==1)

printf("Thisstringispalindrome!\n");//标志位为1，完全匹配，是回文

else

printf("Thisstringisn'tpalindrome!\n");//标志位为0，不完全匹配，不是回文

}

intstinit(stackstru*s)

{

s->top=0;

return1;

}//初始化栈

intstempty(stackstru*s)

{

if(s->top==0)//栈顶为空

{

return0;

}

else

{

return1;

}

}//判断栈与否空

intstpush(stackstru*s,charx)

{

if(s->top==m)