太原理工大学数据结构试题库及答案.pdf

该【太原理工大学数据结构试题库及答案 】是由【小屁孩】上传分享，文档一共【62】页，该文档可以免费在线阅读，需要了解更多关于【太原理工大学数据结构试题库及答案 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..数据结构试题库及答案第一章概论一、选择题1、、存储结构及其基本操作2、、、、某算法的语句执行频度为3n+nlogn+n2+8,、、、、:..元素、数据结构和数据类型二、填空题三、综合题1、将数量级O1,ON,ON2,ON3,ONLOGN,OLOGN,:O1OlogNONONlogNON2ON3O2N22一、,R,其中D是数据元素的有限集合,、,,它们分别是顺序、链式、索引、,它们分别是插入、删除、修改、查找、、,与所使用的计算机无关的是数据的结构;A存储B物理C逻辑D物:..理和存储三、:简单地说,,:线性结构反映结点间的逻辑关系是一对一的,、=0;(i=0;i<n;for(i=0;i<n;i++)i++)=0;=1;for(i=1;i<n;i++)while(i<=n)Mnnnnnlog3n五、设有数据逻辑结构S=D,R,试按各小题所给条件画出这些逻辑结构的图示,={d1,d2,d3,d4}R={d1,d2,d2,d3,d3,d4}:..={d1,d2,…,d9}R={d1,d2,d1,d3,d3,d4,d3,d6,d6,d8,d4,d5,d6,d7,d8,d9}={d1,d2,…,d9}R={d1,d3,d1,d8,d2,d3,d2,d4,d2,d5,d3,d9,d5,d6,d8,d9,d9,d7,d4,d7,d4,d6}第二章线性表一、选择题1、若长度为n的线性表采用顺序存储结构,、若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素,、在双向循环链表中,在p指针所指的结点后插入一个指针q所指向的新结点,->next=q;q->prior=p;p->next->prior=q;q->next=q;->next=q;p->next->prior=q;q->prior=p;q->next=p->next;->prior=p;q->next=p->next;p->next->prior=q;p->next=q;->next=p->next;q->prior=p;p->next=q;p->next=q;:..10、、从表中任一结点出发,、在具有n个结点的单链表上查找值为x的元素时,-115、在线性表的下列存储结构中,、在一个单链表中,若删除p所指向结点的后续结点,->next=p->next->next;=p->next;p->next=p->next->next;=p->next;=p->next->next;17、+n18、、顺序表中,-1/++1/211、==->next==NULL:..->next===NULL12、在下列对顺序表进行的操作中,<i??i??i?、,->next=s->next;s->next=p;->next=p;q->next=s->next;->next=s->next;s->next=q;->next=q;p->next=s->next;15、在表长为n的顺序表中,当在任何位置删除一个元素的概率相同时,-1/+1/、填空题1、设单链表的结点结构为data,,q指向新结点,欲将q插入到p结点之后,则需要执行的语句:;.答案:q->next=p->nextp->next=q3、:L->prior==L->next==L:..5、在一个单链表中删除p所指结点的后继结点时,应执行以下操作:q=p->next;p->next=_q->next___;三、判断题3、用循环单链表表示的链队列中,可以不设队头指针,、、在线性表的顺序存储结构中,、、程序分析填空题1、函数GetElem实现返回单链表的第i个元素,,inti,Elemtypee{LinkListp;intj;p=L->next;j=1;whilep&&j<i{p=p->next;++j;}ifp||j>ireturnERROR;:..e=p->data;returnOK;}2、函数实现单链表的插入算法,,inti,ElemTypee{LNodep,s;intj;p=L;j=0;whilep=NULL&&j<i-1{p=p->next;j++;}ifp==NULL||j>i-1returnERROR;s=LNodemallocsizeofLNode;s->data=e;s->next=p->next;p->next=s;returnOK;}/ListInsert/3、函数ListDelete_sq实现顺序表删除算法,,inti{intk;ifi<1||i>L->lengthreturnERROR;fork=i-1;k<L->length-1;k++L->slistk=L->slistk+1;:..--L->Length;returnOK;}4、函数实现单链表的删除算法,,inti,ElemTypes{LNodep,q;intj;p=L;j=0;whilep->next=NULL&&j<i-1{p=p->next;j++;}ifp->next==NULL||j>i-1returnERROR;q=p->next;p->next=q->next;s=q->data;freeq;returnOK;}/listDelete/5、{nodehead;intn=0;:..nodep;p=head;whilep=NULL{p=p->next;n++;}returnn;}答案:求单链表head的长度五、综合题1、编写算法,:voidinventLnodehead{Lnodep,q;ifhead->nextreturnERROR;p=head->next;q=p->next;p->next=NULL;whileq{p=q;q=q->next;p->next=head->next;head->next=p;}}2、有两个循环链表,链头指针分别为L1和L2,要求写出算法将L2链表链到L1链表之后,:voidmergeLnodeL1,LnodeL2{Lnodep,q;:..whilep->next=L1p=p->next;whileq->next=L2q=q->next;q->next=L1;p->next=L2;}3、设一个带头结点的单向链表的头指针为head,设计算法,将链表的记录,:voidassendingLnodehead{Lnodep,q,r,s;p=head->next;q=p->next;p->next=NULL;whileq{r=q;q=q->next;ifr->data<=p->data{r->next=p;head->next=r;p=r;}else{whilep&&r->data>p->data{s=p;p=p->next;}r->next=p;s->next=r;}p=head->next;}}4、编写算法,将一个头指针为head不带头结点的单链表改造为一个单向:..循环链表,:voidlinklist_cLnodehead{Lnodep;p=head;ifpreturnERROR;whilep->next=NULLp=p->next;p->next=head;}设单链表的长度数据结点数为N,则该算法的时间主要花费在查找链表最后一个结点上算法中的while循环,、已知head为带头结点的单循环链表的头指针,链表中的数据元素依次为a1,a2,a3,a4,…,an,,并回答问题:1写出执行下列程序段后的顺序表A中的数据元素;->next=head{p=head->next;A->length=0;whilep->next=head{:..p=p->next;A->dataA->length++=p->data;ifp->next=headp=p->next;}}答案:1a2,a4,…,2将循环单链表中偶数结点位置的元素值写入顺序表A6、,将x插入到顺序表的适当位置上,:voidInsert_sqSqlistva,ElemTypex{inti,j,n;n=lengthva;ifx>=vaivan=x;else{i=0;whilex>vaii++;forj=n-1;j>=I;j--vaj+1=vaj;vai=x;}:..n++;}7、假设线性表采用顺序存储结构,,设顺序表L=3,7,3,2,1,1,8,7,3,写出执行算法f2后的线性表L的数据元素,{inti,j,k;k=0;fori=0;i<L->length;i++{forj=0;j<k&&L->datai=L->dataj;j++;ifj==k{ifk=iL->datak=L->datai;k++;}}L->length=k;}答案:3,7,2,1,8删除顺序表中重复的元素8、已知线性表中的元素以值递增有序排列,,删除表中所有大于x且小于y的元素若表中存在这样的元素同时:..:voidDelete_listLnodehead,ElemTypex,ElemTypey{Lnodep,q;ifheadreturnERROR;p=head;q=p;whilep{ifp->data>x&&p->data<y}i++;ifp==head{head=p->next;freep;p=head;q=p;}else{q->next=p->next;freep;p=q->next;}else{q=p;p=p->next;}}}9、在带头结点的循环链表L中,结点的数据元素为整型,,且a<b,编写算法删除链表L中元素值大于a且小于b的所有结点.:..第三章栈和队列一、选择题2、->rear==Q->->rear==Q->front+->front==Q->rear+1%->front==Q->rear-1%n3、设计一个判别表达式中括号是否配对的算法,、==->next==->next==NULL5、一个栈的输入序列为:1,2,3,4,、若用一个大小为6的数组来实现循环队列,且当rear和front的值分别为0,,再加入两个元素后,、:..8、循环队列的队头和队尾指针分别为front和rear,=======rear+19、一个顺序栈S,其栈顶指针为top,->top=e;S->top++;->top++;S->top=e;->top=->top=e;10、表达式ab+c-+-+d-+d-D.-+abcd11、将递归算法转换成对应的非递归算法时,、、五节车厢以编号1,2,3,4,5顺序进入铁路调度站栈,,4,5,1,,4,1,3,,5,4,2,,3,5,2,414、->top==->top=->top==->top=n:..15、在一个链队列中,front和rear分别为头指针和尾指针,=front->->next=rear;rear=->next=s;rear=s;->next=front;front=s;16、一个队列的入队序列是1,2,3,4,,2,3,,3,2,,4,3,,4,1,217、依次在初始为空的队列中插入元素a,b,c,d以后,紧接着做了两次删除操作,、正常情况下,删除非空的顺序存储结构的堆栈的栈顶元素,==top+=top-119、->front==Q->->rear-Q->front-1==->front+1=Q->->rear+1=Q->front20、设计一个判别表达式中左右括号是否配对出现的算法,、当用大小为N的数组存储顺序循环队列时,+--2:..22、、若让元素1,2,3依次进栈,,2,,1,,1,,3,224、循环队列用数组A0,m-1存放其元素值,已知其头尾指针分别是front和rear,-front+m%-front+-front--front25、在解决计算机主机和打印机之间速度不匹配问题时,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,、、在一个链队列中,假定front和rear分别为队头指针和队尾指针,=front->=rear->->next=->next=rear28、:..同二、填空题1、设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5,e6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出队的序列是e2,e4,e3,e6,e5,e1,:32、一个循环队列Q的存储空间大小为M,其队头和队尾指针分别为front和rear,则循环队列中元素的个数为:.答案:rear-front+M%M3、在具有n个元素的循环队列中,:n-14、设循环队列的容量为70,现经过一系列的入队和出队操作后,front为20,rear为11,:615、已知循环队列的存储空间大小为20,且当前队列的头指针和尾指针的值分别为8和3,、判断题1、、在单链表中,要访问某个结点,只要知道该结点的地址即可;因此,、以链表作为栈的存储结构,出栈操作必须判别栈空的情况.:..四、程序分析填空题1、已知栈的基本操作函数:intInitStackSqStackS;、广义表a,、、、数组A0..5,0..6的每个元素占5个字节,将其按列优先次序存储在起始地址为1000的内存单元中,、广义表G=a,bc,d,e,f,、采用稀疏矩阵的三元组表形式进行压缩存储,若要完成对三元组表进行转置,只要将行和列对换,这种说法B.:..、广义表a,b,,cB..、、、设有一个10阶的对称矩阵A,采用压缩存储方式,以行序为主存储,a11为第一个元素,其存储地址为1,每元素占1个地址空间,、设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分按行序存放在一维数组B1,nn-1/2中,对下三角部分中任一元素ai,ji>=j,-1/2+j--1/2++1/2+j-+1/2+j13、广义表A=a,:..14、稀疏矩阵一般的压缩存储方法有两种,、假设以三元组表表示稀疏矩阵,则与如图所示三元组表对应的4×5的稀疏矩阵是注:矩阵的行列下标均从1开始B.?0?8060??0?8060??????70000??70003?.????00000?50400??????????50400??00000??0?8060??0?8060??????00003??70000?.????70000?50403??????????50400??00000?16、以下有关广义表的表述中,、对广义表L=a,b,c,d,e,,f二、判断题1、、一个稀疏矩阵采用三元组表示,若把三元组中有关行下标与列下标的值互换,并把mu和nu的值进行互换,则完成了矩阵转置.√3、稀疏矩阵压缩存储后,、广义表的长度是指广义表中括号嵌套的层数.:..√5、广义表是一种多层次的数据结构,、填空题1、已知二维数组Amn采用行序为主方式存储,每个元素占k个存储单元,并且第一个元素的存储地址是LOCA00,则Aij的地址是___LocA00+iN+、广义表运算式HEADTAILa,b,c,x,y,z的结果是:x,y,、二维数组,、稀疏矩阵的压缩存储方式有:、综合题1、现有一个稀疏矩阵,请给出它的三元组表.?0310???1000???0210????00?20?答案:ijv12313121132233143-2第六章树一、选择题1、二叉树的深度为k,则二叉树最多有C个结点.:..---12、用顺序存储的方法,将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R1..N中,若结点Ri有右孩子,-+、设a,b为一棵二叉树上的两个结点,在中序遍历时,、设一棵二叉树的中序遍历序列:badce,后序遍历序列:bdeca,、、、某二叉树的中序序列为ABCDEFG,后序序列为BDCAFGE,、若以{4,5,6,7,8}作为权值构造哈夫曼树,、将一棵有100个结点的完全二叉树从根这一层开始,每一层上从左到右:..依次对结点进行编号,根结点的编号为1,、表达式ab+c-+-+d-+d-D.-+abcd11、对某二叉树进行先序遍历的结果为ABDEFC,中序遍历的结果为DBFEAC,、、表达式AB+C/D-E++C/D-E++D/E-F++DE-F+/+/-+14、在线索二叉树中,->left==->ltag==->ltag==1&&t->left==、任何一棵二叉树的叶结点在先序、、假定在一棵二叉树中,度为2的结点数为15,度为1的结点数为30,则叶:..、在下列情况中,、用顺序存储的方法,将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R1..n中,若结点Ri有左孩子,-+、,且度不超过2的树是二叉树20、、按照二叉树的定义,、由权值为3,6,7,2,5的叶子结点生成一棵哈夫曼树,:..二、判断题1、存在这样的二叉树,对它