数据结构考试试卷(C语言版)_第1页
数据结构考试试卷(C语言版)_第2页
数据结构考试试卷(C语言版)_第3页
数据结构考试试卷(C语言版)_第4页
数据结构考试试卷(C语言版)_第5页
已阅读5页,还剩3页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、*学院学期期末试题数据结构(C语言) 一选择题(102分):共10小题,请将答案填入题中的括号中,每小题只有一个正确答案,错选或不选均不给分。1组成数据的基本单位是( )数据项 数据类型C数据元素 D数据变量2下面程序段的时间复杂度为( )。 for(i=1;i=n;i+) for(j=i;jnext=p-next-next Bp=p-nextCp=p-next-next Dp-next=p5若让元素1,2,3依次进栈,则出栈次序不可能出现( )种情况。 A、3,2,1 B、2,1,3 C、3,1,2 D、1,3,26在一个循环顺序队列中,队首指针指向队首元素的( )位置。A、当前 B、后面

2、C、前一个 D、后一个7假定一个链队的队首和队尾指针分别为front和rear,则判断队空的条件是( )。A、front=NULL B、front!=NULL C、rear!=NULL D、front=rear8二叉树第i(i1)层最多有( )个结点。 A2i B 2i-1 C2i D2i -19如果结点A有3个兄弟,而且B为A的双亲,则B是度为( )4 3C5 D110当待排序序列的关键码是随机分布时,下列哪种排序算法的平均时间复杂度最优( )。A直接插入排序 B直接选择排序C快速排序 D冒泡排序二填空题(30分):每空2分1. 数据的逻辑结构被分为 、 、 和 四种。2在一个长度为n的顺序

3、表中插入一个元素,最少需移动 个元素,最多需移动_个元素。3双向循环链表的优点是 4队列的原则是 。5顺序存储的队列如果不采用循环方式,则会出现 问题。6具有64个结点的完全二叉树的深度为 。7设一颗完全二叉树共有50个叶子结点,则它共有_个度为2的结点。8二叉树采用_序遍历可以得到结点的有序序列。9在一个具有n个顶点的无向完全图中,包含有 条边,在一个具有n个顶点的有向完全图中,包含有 条边。 10快速排序算法在最差的情况下其时间复杂度是 。三判断题(52分)1任意一棵满二叉树一定也是完全二叉树。( )2进栈操作时,必须判断栈是否已满。( )3一个程序的时间复杂度是指该程序运行时间与问题规模

4、的对应关系。( )4采用链式结构存储线性表时,其地址可以是不连续的。( )5折半查找法的前提之一是线性表有序。( ) 四应用题(45分)1 试比较顺序存储和链式存储的优缺点。(5分)2 简述栈和队列这两种数据结构的相同点和不同点。(5分)3 已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA,试画出这棵二叉树。(5分)4 对于给定的一组关键码:83,40,63,13,84,35,画出用冒泡排序对上述序列进行操作的各趟结果。(5分)五算法设计题(20分)1编写算法,将任意十进制数转换成其他进制,要求写出完整代码,可采用顺序栈或链栈实现。(12分)2编写一算法完成瑟夫生死者

5、游戏。(8分)瑟夫生死者游戏的描述:N个旅客同乘一条船,因为严重超载,加上风浪大,危险万分;因此船长告诉乘客,只有将全船一半的旅客投入海中,其余人才能幸免遇难。无奈,大家只得同意这种办法,并拟定N个人围成一圈,由第一个人数起,依次报数,数到第r人,便把他投入海中,然后再从他的下一个人数起,数到第r人,再将他仍进海里,如此循环的进行,直到剩下N/2个乘客为止。问哪些位置是将被扔下大海的位置。8答案及评分标准:数据结构(C语言)答案及评分标准一选择题(102分):每小题只有一个正确答案,错选或不选均不给分。12345678910CDBACCDBAC二填空题(30分):每空2分。1集合 线性结构 树

6、型结构 图型结构 20 n3既可以方便的找到后继结点又可以方便的找到前驱结点。4先进先出5假溢出677498中9n(n-1)/2 n(n-1)10O(n2)。三判断题(52分)1;2;3;4;5四应用题(45分)1顺序存储查找效率高,插入和删除效率低;链式存储插入和删除效率高,查找效率低。2栈和队列都是操作受限的线性表。栈是先进后出,操作在一端进行;队列是先进先出,插入在一端,删除在另一端进行。3HBFCADEA4 83 40 63 13 84 35 13 83 40 63 35 84 13 35 83 40 63 84 13 35 40 83 63 84 13 35 40 63 83 84

7、13 35 40 63 83 84五算法设计题(20分)1(12分)#define Maxsize 100typedef struct int dataMaxsize; int top;SeqStack;SeqStack *Init_SeqStack() SeqStack *s; s=(SeqStack *)malloc(sizeof(SeqStack); s-top=-1; return s;/*入栈*/int Push_Seqstack(SeqStack *s,int x) if(s-top=Maxsize-1)return 0; else s-top+; s-datas-top=x; r

8、eturn 1; /*出栈*/int Pop_SeqStack(SeqStack *s,int *x) if(Empty_SeqStack(s) return 0; else *x=s-datas-top; s-top-; return 1; /*判空栈*/int Empty_SeqStack(SeqStack *s) if(s-top=-1) return 1; else return 0;void conversion(int N,int r) SeqStack *p; int y; p=Init_SeqStack(); while(N) if(Push_Seqstack(p,N%r)=1

9、) N=N/r; else break; while(!Empty_SeqStack(p) Pop_SeqStack(p,&y); printf(%d,y); void main() int M,t; printf(please input a number:n); scanf(%d,&M); printf(please input t:n); scanf(%d,&t); conversion(M,t); getch();2(8分)typedef struct node int data; struct node *next;ListNode,*LinkList;LinkList Create

10、List(int n);void DeleteNode(LinkList L,int n,int k);void PrintList(LinkList L);main() int n,k; LinkList H; printf(请输入总人数:); scanf(%d,&n); printf(请输入报数上限:); scanf(%d,&k); H=CreateList(n); DeleteNode(H,n,k); PrintList(H); getch(); LinkList CreateList(int n) int i; LinkList L=NULL; ListNode *s,*R=NULL; for(i=1;idata=i; if(L=NULL) L=s; else R-next=s; R=s; if(L!=NULL) R-next=L; return L;void DeleteNode(LinkList L,int n,int k) int i,j=0; ListNode *q,*p=L; printf(不幸投入大海的有:); for(i=1;i=n/2;i+) for(j=1;jnext; q=p-next; p-next=q-next; printf(%4d,q-data); if(i%10=0) printf(n); free(q); p=p-next

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论