《数据结构考试试卷》由会员分享，可在线阅读，更多相关《数据结构考试试卷（7页珍藏版）》请在金锄头文库上搜索。
1、学期期末试题数据结构（C语言）一.选择题（10X2）：共2小题，请将答案填入题中的括号中.每小题只有一个正确答案，错选或不选均不给分.1.组成数据的基本单位是（）A.数据项B.数据类型C.数据元素D.数据变量2.下面程序段的时间复杂度为（）。fbr(i=l;i=n;i-H-)for(j=i;jnext=p-next-nextE p=p-nextC. p=p-next-nextD p-next=p5.若让元素1, 2, 3依次进栈，则出栈次序不可能出现（）种情况。A、 3, 2, 1B. 2, 1, 3C、 3, b 2D. 1, 3, 26.在一个循环顺序队列中，队首指针指向队首元素的（）位置
2、。A、当前B.后面C、前一个D.后一个7.假定一个链队的队首和队尾指针分别为front和rear,则判断队空的条件是（）。A、 front=NULLB、 front!=NULLC、 rear!=NULLD. front二二rEar8.二叉树第层最多有（）个结点。A21E2口C21D 2l-l9.如果结点A有3个兄弟，而且E为A的双亲，则B是度为（）A. 4B3C5D110当待排序序列的关键码是随机分布时，下列哪种排序算法的平均时间复杂度最优（）。A.直接插入排序B直接选择排序C快速排序D冒泡排序二.填空题（30分）：每空2分1. 数据的逻辑结构被分为、和四种。2. 在一个长度为11的顺序表中插
3、入一个元素，最少需移动个元素，最多需移动个元素。3. 双向循环链表的优点是4. 队列的原则是。5. 顺序存储的队列如果不采用循环方式，则会出现问题。6. 具有64个结点的完全二叉树的深度为。7. 设一颗完全二叉树共有50个叶子结点，则它共有个度为2的结点。8. 二叉树采用遍历可以得到结点的有序序列。9. 在一个具有n个顶点的无向完全图中，包含有条边，在一个具有n个顶点的有向完全图中，包含有条边。10. 快速排序算法在最差的情况下其时间复杂度是o三.判断题（5X2分）1. 任意一棵满二叉树一定也是完全二叉树。（）2. 进栈操作时，必须判断栈是否已满。（）3. 一个程序的时间复杂度是指该程序运行时
4、间与问题规模的对应关系。（）4. 采用链式结构存储线性表时，其地址可以是不连续的。（）5. 折半查找法的前提之一是线性表有序。（）四.应用题（4X5分）1. 试比较顺序存储和链式存储的优缺点。（5分）2. 简述栈和队列这两种数据结构的相同点和不同点。（5分）3. 已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA,试画出这棵二叉树。（5分）4. 对于给定的一组关键码：83, 40, 63, 13, 84, 35,画出用冒泡排序对上述序列进行操作的各趟结果。（5分）五.算法设计题（20分）1. 编写算法，将任意十进制数转换成其他进制，要求写出完整代码，可采用顺序栈或链栈
5、实现。（12分）2. 编写一算法完成瑟夫生死者游戏。（8分）瑟夫生死者游戏的描述：N个旅客同乘一条船，因为严重超载，加上风浪人，危险万分；因 此船长告诉乘客，只有将全船一半的旅客投入海中，其余人才能幸免遇难。无奈，人家只得 同意这种办法，并拟定N个人I對成一圈，由第一个人数起，依次报数，数到第r人，便把他 投入海中，然后再从他的下一个人数起，数到第r人，再将他仍进海里，如此循坏的进行, 直到剩下N/2个乘客为止。问哪些位置是将被扔下大海的位置。答案及评分标准:数据结构（C语言）答案及评分标准一.选择题（10X2分）：每小题只有一个正确答案，错选或不选均不给分。12345678910CDBACC
6、DBAc二.填空题（30分）：每空2分。1. 集合 线性结构 树型结构图型结构2. 0 n3. 既可以方便的找到后继结点又可以方便的找到前驱结点。4. 先进先出5. 假溢出6. 77. 498. 中9. n（n-1）/2 n （n-1）10. 0 （n2） o=-判断题（5X2分）1. J ； 2 X； 3 J ； 4 V； 5 V四.应用题（4X5分）1. 顺序存储查找效率高，插入和删除效率低；链式存储插入和删除效率高，查找效率低。2. 栈和队列都是操作受限的线性表。栈是先进后出，操作在一端进行；队列是先进先出, 插入在一端，删除在另一端进行。4.83 40 631384 351383406
7、33584133583406384133540836384133540638384133540638384五.算法设计题(20分)1. (12 分)#define Maxsize 100tvpedef stmctmt data Maxsize;iiit top;JSeqStack;SeqStack *Init_SeqStack()SeqStack *s;s=(SeqStack *)malloc(sizeof(SeqStack); s-top=-l;return s;严入栈*/mt Push_Seqstack(SeqStack *s,int x)if(s-top=Maxsize-1 )retur
8、n 0;elses-top+;s-datas-top=x;return 1;/*出栈*/mt Pop_SeqStack(SeqStack *sjnt *x)if(Empty_SeqStack(s) return 0;else*x=s-datas-top;s-top;return 1;/*判空栈*/mt Emptv_SeqStack(SeqStack *s)if(s-top=-l) return 1;else return 0;void conversion(int N.iiit r)SeqStack *p;int y;p=Iiut_SeqStackQ;while(N)if(Push_Seqst
9、ack(p.N%r)= 1) N=N/r;elsebreak: while(!Empty_SeqStack(p) Pop_SeqStack(p,&y); pnntff%(T；y);void main()iiit M,t;printfCplease mput a numbernn); scanfC%cT,&M);printfCplease input scanfC%cT；&t); conveision(M,t);getchQ;2. (8 分)tvpedef stmct nodemt data;stmct node *next;ListNode,*LinkList;LinkList CreateL
10、ist(iiit n);void DeleteNode(LnikList L.iiit n.iiit k); void PriiitList(LuikList L);main()iiit n,k;LuikList H; piuitf(请输入总人数：”); scanf”d；&n);请输入报数上限:”)；scanf”d：&k);H=CreateList(n);DeleteNode(Hrn,k);PrmtList(H); getch();LinkList CreateList(iiit n)mt i;LuikList L=NULL;ListNode *s?*R=NULL: fbr(i=l;idata
11、=i;if(L=NULL) L=s;else R-next=s; R=s;if(L!=NULL) R-next=L; return L;void DeleteNode(LiiikList L.iiit n.iiit k)mt lj=O;ListNode *q.*p=L;不幸投入人海的有：”)；fbr(i=l ;i=n/2;i+) for(j=ljnext; q=p-next; pAnex t=q-next; printf(n%4d,q-data); if(i%10=0) pnntf(MnM); fiee(q);p=p-next;L=P；void PriiitList(LuikList L)ListNode *p=L;iiit i=l;pi-rntfC有幸逃生的有：”)； while(p-next !=L)prmtf(n%4d,p-data); if(i%10=0) pnntf(MnM); p=p-next;printf(,%4d,p-data);
