数据结构试题A

数据结构试题（A）姓名__________学号__________班级__________分数____________一、选择填空（每空1分，共20分）1_____是数据的不可分割的最小单位。(A)结点(B)数据元素(C)数据类型(D)数据项2若线性表最常用的操作是存取第i个元素及其前趋的值，则采用______存储方式节省时间。(A)单链表(B)双向链表(C)单循环链表(D)顺序表3对长度为14的表作2路归并，共需移动_____次记录。(A)42(B)56(C)91(D)1824n个顶点的无向图的的邻接表中结点总数最多有______个。(A)2n(B)n(C)n/2(D)n(n-1)5设连通图G的顶点数为n，则G的生成树的边数为______。(A)n-1(B)n(C)2n(D)2n-16在建立邻接表或逆邻接表时，若输入的顶点信息即为顶点的编号，则建立图的算法的时间复杂度为______。(A)O(n+e)(B)O(n2)(C)O(n×e)(D)O(n3)7使用监视哨，对表（25，20，10，42，28）作直接插入排序，共需比较____次。(A)10(B)6(C)8(D)答案A，B，C都不对8以知一棵二叉树的前序和中序序列分别为ABDEGCFH和DBGEACHF则该二叉树的后序序列为______。(A)GEDHFBCA(B)DGEBHFCA(C)ABCDEFGH(D)ACBFEDHG9深度为K的满二叉树有_____个叶结点。(A)K2-1(B)2K-1-1(C)2K-1(D)2K-110下列算法中，某一轮结束后未必能选出一个元素放在其最终位置上的是______。(A)堆排序(B)冒泡排序(C)直接插入排序(D)快速排序11将新元素插入到链式队列中时，新元素只能插入到______。A链头B链尾C链中D第i个位置（i=1且i=表长加1）12假如只想得到1000个元素组成的序列中第4个最小元素之前的部分排序的序列，用_____方法最好。A冒泡排序B快速排序C堆排序D选择排序13______是不稳定的排序方法。A冒泡排序B归并排序C插入排序D选择排序14线性表是具有n(n=0)个_____的有限序列。A字符B表元素C数据元素D数据项15从逻辑上，可以将数据结构分为_____两类。A动态表和静态表B顺序结构和链式结构C线性结构和非线性结构D动态结构和静态结构16设无向图的顶点个数为n，则该图最多有_____条边。An-1Bn(n-1)/2Cn(n+1)/2Dn17有8个叶子结点的二叉树有_____个度为2的结点。A7B16C64D918深度为5的满二叉树有_____个结点。A32B15C31D1619二分查找有序表（16，20，30，35，40，46，60，78），若查找元素78，需依次与表中的______进行比较。A40，60B35，46，60，78C40，60，78D35，46，7820算法应具的特点不包括_____。A确定性B可行性C一一对应性D有输入、输出二问题求解（每小题6分，共30分）1给定下列网络G：1）求最小生成树，画出逻辑图；2）画出G的邻接矩阵和邻接表。2依次输入元素：10，6，8，3，42，25，7，30，27，60试生成一棵二叉排序树，（1）画出生成之后的二叉排序树；（2）写出中序遍历该二叉排序树的序列；（3）假定每个元素的查找概率相等，计算查找成功时的平均查找长度。ABCEF22049683如何对有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的1都集中到对角线以上？试举一例加以说明。4找出所有二叉树，其结点在下述两种次序之下，恰好都以同样的顺序出现：a)前序和中序；b)前序和后序5对下列关键字序列用快速排序法排序，哪一种情况速度最快？哪一种情况速度最慢？为什麽？A（19，23，3，15，7，21，28）B（23，21，28，15，19，3，7）C（3，7，15，19，21，23，28）三简述下述算法的功能（每小题6分，共18分）1写出以下程序段的输出结果。voidmain(){queueq;charx='e';chary='c';initqueue(q);//构造一个空队列qenqueue(q,'h');//将元素h到队q的尾部enqueue(q,'r');enqueue(q,y);dequeue(q,x);//删除队q的队首元素xenqueue(q,x);dequeue(q,x);enqueue(q,'a');while(!queueempty(q))//当队q非空{dequeue(q,y);printf(y);}printf(x);}2简述以下算法的功能。(1)voida3(queue&q){stacks;intd;initstack(s);//构造一个空栈swhile(!queueempty(q))//当队q非空时{dequeue(q,d);//从队q删除一个元素保存在d中push(s,d);}//将d中的元素插入到栈s里while(!stackempty(s))//当栈s非空{pop(s,d);//弹出栈s的顶元保存在d中enqueue(q,d);}//将d插入到队q的尾部}(2)voidchange(linklist&head)//head是无表头结点的单链表{linklistq,p;if(head&&head-next){q=head;head=head-hext;p=head;while(p-next)p=p-next;p-next=q;q-next=NULL;}}四、算法设计（每题16分，共32分）1编写一个算法交换单链表中p所指位置上和其后继位置上的两个结点，head为头指针，设该链表没有表头结点，p指向该链表中任意结点。结点的结构如下：typedefstructnode{elementypedata;structnode*next;}node;2已知线性表中的元素以递增的顺序排列并以向量作存储结构，试编写一高效算法删除表中所有值大于mink且小于maxk的元素（注意:mink可和maxk是给定的两个参数，它们的值可以和表中的元素相同，也可以不同）。假设向量中的元素分别为（1，2，3，4，5，6，7，8，9，10），欲删除值大于等于3而小于等于7的元素，请统计算法中元素的移动数。参考答案一选择填空1D2D3B4D5A6A7C8B9D10C11B12C13D14C15C16B17A18C19B20C二问题求解12ABCEFA02040中序序列：3，6，7，8，10，25，27，30，42，60B202089平均查找长度：3C020000E48006F09060ABCEF123453使得有向图中每条边始顶点的编号小于终顶点的编号。4前序和中序空树和具有所有的左链为空的二叉树。前序和后序具有0个或1个结点的二叉树。5A（19，23，3，15，7，21，28）-------最快，2轮B（23，21，28，15，19，3，7）C（3，7，15，19，21，23，28）-------最慢，7轮最快的情况是每次将第一个元素放到正确位置后，将整个文件分为两个等长的子表，其时间复杂度为对数阶，最慢的情况是每次只能得到左子表或右子表其时间复杂度为平方阶。ABCEF20462000100110T1211131064287272530603三简述下述算法的功能1输出结果是char2算法的功能是：利用栈s作辅助结构，将队列q中的元素进行逆置。3当单链表的长度大于等于2时，删除表中第一个结点并将它插入到表尾。四、1如果p存在后继结点，则看它是否是第一个结点。如果是，则交换后须改变该链表的头指针head的值，否则直接交换即可。voidswap(linklist&head,linklistp){linklistq,r,s;q=p-next;if(q!=NULL)//若p存在后继，则进行处理{if(p==head)//若p指向第一个结点，则前两个结点交换位置{head=head-next;s=head-next;head-next=p;p-hext=s;}else//若p指向第二个或第二个以后的结点{r=head;//从第一个结点开始查找p的直接前趋结点while(r-next!=p)r=r-next;r-next=q;//交换p,q结点的顺序p-next=q-next;q-next=p;}printf(succ);}elseprintf(NULL);//p所指结点没有后继}2本算法的思想是从表的第一个元素开始依次向后扫描，找到第一个值大于等于mink的元素和第一个小于等于maxk的元素则分别记下它们位置，然后一次性删除这些元素。此方法元素移动量最小。intdel_3(inta[],intmink,maxk,n){inti,m,j,k;i=0;while(i=n-1&&a[i]mink)i++;if(in-1)return(0);elsem=i;while(i=n-1&&a[i]maxk)i++;if(in-1)j=n-1;for(i=m;i=n-1-k;i++)a[i]=a[i+k];n=n-k;return(1);}假设向量中的元素分别为（1，2，3，4，5，6，7，8，9，10），欲删除值大于等于3而小于等于7的元素，则元素移动数为：3次。