数据结构考试试卷(C语言版)

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