资源描述：
《数据结构(c语言)模拟试卷(2)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、洛雅德科技学院200~200学年第学期期末试题——数据结构(C语言)题号一二三四五六总分分数本课程为闭卷考试，试卷共六道大题，试卷满分100分，考试时间120分钟。一．选择题（10×2分）：共10小题，请将答案填入题中的括号中，每小题只有一个正确答案，错选或不选均不给分。1．如果树的结点有4个兄弟，而且B为A的双亲，则B的度为（）Ａ．3Ｂ．4C．5D．12．设有一个栈，元素的进栈次序为A,B,C,D,E，则下列（）是不可能的出栈序列。A．A,B,C,D,EB．B,C,D,E,AC．E,A,B,C,DD．E,D,C,B,A3．在所有排序方法中，关键字的比较次
2、数与记录的初始排列无关的是（）。A．快速排序B．冒泡排序C．直接插入排序D．简单选择排序4．设一棵二叉树共有20个度为2的结点，则叶子结点共有（）个。A．40B．19C．20D．215．在具有N个单元的顺序存储循环队列中，假定front和rear分别为对头指针和对尾指针，则判断对满的条件为（）。A．front==rearB．(rear+1)%MAXSIZE==frontC．front-rear==1D．rear%MAXSIZE==front6．设有1000个元素，用二分法查找时，最小比较次数为（）Ａ．0Ｂ．1C．10D．5007．一个元素进入队列的时间复杂
3、度是（）。A．O(1)B．O(n)C．O(n2)D．O(log2n)8．一棵完全二叉树中根结点的编号为1，而且23号结点有左孩子但没有右孩子，则完全二叉树共有（）个结点。A．24B．45C．46D．479．如某数据结构的数据元素的集合为S={A,B,C,D,E,F,G}，数据元素间的关系为R={,,,,,}，则该数据结构是一种（）。A．线性结构B．树结构C．链表结构D．队列结构610．从一个长度为n的顺序表中删除第i个元素(1≤i≤n)，需向前移动（）个元素。A．n-iB．n-i+1C．n-i-1
4、D．i二．填空题（20分）：每空2分，１．后序序列和中序序列相同的二叉树为、后序序列和前序序列相同的二叉树为。2．已知某算法的执行时间为n+n2,n代表问题规模，则该算法的时间复杂度是。3．数据结构有线性结构、树结构、、等几种逻辑结构。4．采用快速排序法进行排序时，如果时，排序效率会大大降低。5．在一个长度为n的顺序表中插入一个元素，最少需要移动元素，最多需要移动元素，6．如果指针p指向一棵二叉树的一个结点，则判断p没有左孩子的逻辑表达式为。7．栈的原则是。三．简答题（4×5分）1．写出线性表(26,45,12,20,30)采用快速排序算法排序后，第一趟排
5、序过程及结果。（5分）2．线性表采用插入排序算法排序几趟后，有序部分是(16,20,40)，无序部分是(18,25)，则下一趟的排序需要移动几个元素？写出下一趟结束的结果。（5分）3．给出下图所示的二叉树的中序遍历结果。（5分）AFBCDGE4．试说明单链表采用头结点的优点。（5分）四．判断题（5×2分）１．如果某数据结构的每一个元素最多只有一个直接前驱，则其必为线性表。()2．快速排序算法在最好的情况下时间复杂度是O(n)。()3．进栈、出栈操作的时间复杂度是O(n)。()4．进栈操作时，必须判断栈是否已满。()65．一个单链表不能采用折半查找法进行查找
6、。()五．程序填空题（3×5分）1．已知QUEUE表示循环队列的数据结构，函数leavequeue是将对头元素的值放入变量e，然后删除对头元素，操作成功返回1，否则返回0。完成以下程序。（4分）typedefstruct{intdata[100];intfront;intrear;}QUEUE;leavequeue(QUEUE*Q,int*e){if(){return0;}*e=Q->data[Q->front];Q-front=;return1;}2．以下函数ins的功能是在顺序表a中找到第一个值为x的元素，然后在该元素之前插入一个值为y的元素，如果找不
7、到值为x的元素，则新元素成为顺序表的最后一个元素。插入成功返回1，否则返回0。完成以下程序。(8分)typedefsrruct{intdata[100];intlen;}SQ;intins(SQ*a,intx,inty){intk,j;if()return0;for(k=0;klen;++k){if(a->elem[k]==x){break;}}if(k==a->len){--k;}else{for(i=a->len-1;i>k;--i){;}6}=y;a->len;return1;}3．已知一个单链表的表头指针为h，每个结点含元素值data和下一
8、个结点的地址next。链表一共有5个结点，其元素值分别为100,2
