数据结构C语言试卷2

1、成都东软信息技术学院200 200 学年第 学期期末试题数据结构(C语言) 题号一二三四五六总分分数本课程为闭卷考试，试卷共六道大题，试卷满分100分，考试时间120分钟。一选择题（10×2分）：共10小题，请将答案填入题中的括号中，每小题只有一个正确答案，错选或不选均不给分。1如果树的结点有4个兄弟，而且B为A的双亲，则B的度为（ ）3 4C5 D12设有一个栈，元素的进栈次序为A,B,C,D,E，则下列（ ）是不可能的出栈序列。 AA,B,C,D,E BB,C,D,E,A CE,A,B,C,D DE,D,C,B,A3在所有排序方法中，关键字的比较次数与记录的初始排列无关的是（ ）

2、。 A快速排序 B冒泡排序 C直接插入排序 D简单选择排序4设一棵二叉树共有20个度为2的结点，则叶子结点共有（ ）个。A40 B19C20 D215在具有N个单元的顺序存储循环队列中，假定front和rear分别为对头指针和对尾指针，则判断对满的条件为（ ）。Afront= rear B(rear+1)%MAXSIZE=frontCfront-rear=1 Drear%MAXSIZE=front6设有1000个元素，用二分法查找时，最小比较次数为（ ）0 1C10 D5007一个元素进入队列的时间复杂度是（ ）。 AO(1) BO(n) CO(n2) DO(log2n)8一棵完全二叉树中根结

3、点的编号为1，而且23号结点有左孩子但没有右孩子，则完全二叉树共有（ ）个结点。 A24 B45 C46 D479如某数据结构的数据元素的集合为S=A,B,C,D,E,F,G，数据元素间的关系为R=<A,D>,<A,G>,<D,B>,<D,C>,<G,E>,<G,F>，则该数据结构是一种（ ）。A线性结构 B树结构C链表结构 D队列结构10从一个长度为n的顺序表中删除第i个元素(1in)，需向前移动（ ）个元素。An-i Bn-i+1Cn-i-1 Di二填空题（20分）：每空2分，后序序列和中序序列相同的二叉树为 、后序序

4、列和前序序列相同的二叉树为 。2已知某算法的执行时间为n+n2,n代表问题规模，则该算法的时间复杂度是 。3数据结构有线性结构、树结构、 、 等几种逻辑结构。4采用快速排序法进行排序时，如果 时，排序效率会大大降低。5在一个长度为n的顺序表中插入一个元素，最少需要移动 元素，最多需要移动 元素，6如果指针p指向一棵二叉树的一个结点，则判断p没有左孩子的逻辑表达式为 。7栈的原则是 。三简答题（4×5分）1 写出线性表(26,45,12,20,30)采用快速排序算法排序后，第一趟排序过程及结果。（5分）2 线性表采用插入排序算法排序几趟后，有序部分是(16,20,40)，无序部分是(1

5、8,25)，则下一趟的排序需要移动几个元素？写出下一趟结束的结果。（5分）3 给出下图所示的二叉树的中序遍历结果。（5分）AFBCDGE4 试说明单链表采用头结点的优点。（5分）四判断题（5×2分）如果某数据结构的每一个元素最多只有一个直接前驱，则其必为线性表。( )2快速排序算法在最好的情况下时间复杂度是O(n)。( )3进栈、出栈操作的时间复杂度是O(n)。( )4进栈操作时，必须判断栈是否已满。( )5一个单链表不能采用折半查找法进行查找。( ) 五程序填空题（3×5分）1已知QUEUE表示循环队列的数据结构，函数leavequeue是将对头元素的值放入变量e，然后删

6、除对头元素，操作成功返回1，否则返回0。完成以下程序。（4分） typedef struct int data100; int front; int rear; QUEUE;leavequeue (QUEUE *Q, int *e) if( ) return 0;*e = Q->dataQ->front;Q-front = ;return 1;2以下函数ins的功能是在顺序表a中找到第一个值为x的元素，然后在该元素之前插入一个值为y的元素，如果找不到值为x的元素，则新元素成为顺序表的最后一个元素。插入成功返回1，否则返回0。完成以下程序。(8分) typedef srruct in

7、t data100; int len; SQ;int ins(SQ *a, int x, int y) int k,j; if( ) return 0; for(k=0;k<a->len;+k) if(a->elemk = x) break; if(k = a->len) -k;else for (i=a->len-1;i>k;-i) ; =y;a->len ;return 1;3已知一个单链表的表头指针为h，每个结点含元素值data和下一个结点的地址next。链表一共有5个结点，其元素值分别为100,200,300,400,500，经过下列语句后，输

8、出什么结果？。（3分） for (p=h;p->data<300;p=p->next) p->next = p->next->next;printf(“%d”,p->data);六算法设计题（15分）1设计冒泡排序的算法。数据类型定义如下：（8分） #define MAXSIZE 100 typedef int KeyType; typedef struct node KeyType key; infotype otherinfo; ElemType; typedef struct ElemType elemMAXSIZE; int length; S

9、_TBL;2编写算法查找不带头结点的单链表中的第i个结点，如找到返回1，否则返回0。（7分）已知单链表结点数据结构如下：typedef struct node int data; struct node *next; LNode, *LinkList;答案及评分标准：数据结构(C语言)答案及评分标准一选择题（10×2分）：每小题只有一个正确答案，错选或不选均不给分。12345678910CCDDBBACBA二填空题（20分）：每空2分。1没有右子树的二叉树 只有根的二叉树; 2O(n2); 3图结构 集合;4降序排列; 50，n; 6P->lchild=NULL； 7先进后出。

10、三简答题（4×5分）120 12 26 45 30。2需移动两个元素，16 18 20 40。3DBAFGEC4解决单链表的“第一个结点问题”，使头指针变量不为空。四判断题（5×2分）1×；2；3×；4×；5五程序填空题（3×5分）1Q->front = Q->rear;(Q->front+1)%100; 2a->len>=100;a->elemi=a->elemi-1;ak;+;3300六算法设计题（15分）1void bublesort(ElemType *r) int i = 0; int j = 0; ElemType temp; for (i=0; i<n-1;+i) for (j=n-2; j>=I;-j) if (rj+1.key < rj.key) temp = rj+1; rj+1 = rj; rj = temp;