数据结构（c语言）试卷（4）

《数据结构（c语言）试卷（4）》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、成都东软信息技术学院200~200学年第学期期末试题——数据结构(C语言)题号一二三四五六总分分数本课程为闭卷考试，试卷共六道大题，试卷满分100分，考试时间120分钟。一．选择题（10×2分）：共10小题，请将答案填入题中的括号中，每小题只有一个正确答案，错选或不选均不给分。1．组成数据的基本单位是（）Ａ．数据项Ｂ．数据类型C．数据元素D．数据变量2．下面程序段的时间复杂度为（）。for(i=0;i

2、C．O(m+n)D．O(m*n)3．在一个长度为n的顺序存储线性表中，删除第i个元素(1≤i≤n+1)时，需向前移动（）个元素。A．n-iB．n-i+1C．n-i-1D．i4．在一个单链表中，已知*q结点是*p结点的前趋结点，若在*q和*p之间插入*s结点，则需执行（）。A．s->next=p->next;p->next=s;B．q->next=s;s->next=p;C．p->next=s->next;s->next=p;D．p->next=s;s->next=q;5．若让元素a，b，c依次进栈

3、，则出栈次序不可能出现（）种情况。A．cbaB．bacC．cabD．acb6．在一个链队列中，假定front和rear分别为队头和队尾指针，则插入*s结点的操作应执行（）。Ａ．front->next=s;front=s;Ｂ．s->next=rear;rear=s;C．rear->next=s;rear=s;D．s->next=front;front=s;7．当采用顺序存储方式存储队列时，可能出现存储空间剩余，而不允许继续入队的情况，称为（）。A．溢出B．队列不能用顺序存储方式C．数组存储空间过小D

4、．假溢出8．一棵深度为k的满二叉树有（）个结点。A．2k-1B．2k-17C．2kD．2k9．一棵完全二叉树的结点按层次遍历从1开始编号，如果编号为m的结点有双亲，则双亲的编号为（）。A．2×mB．m/2C．m＋1D．m-110．快速排序在（）情况下最不利于发挥其长处。A．被排序的数据量很大B．被排序的数据完全无序C．被排序的数据已基本有序D．被排序的数据中最大的值与最小值相差不大二．填空题（30分）：每空2分，1.数据的逻辑结构被分为、、和四种。2．在一个长度为n的顺序表中删除一个元素，最少需移

5、动个元素，最多需移动________个元素。3．对于一个顺序栈作进栈运算时，应先判断栈是否为，判断的条件是，作出栈运算时，应先判断栈是否为，判断的条件是。4．栈的原则是。5．在一棵二叉树上第5层的结点数最多为。6．设一颗完全二叉树共有50个叶子结点，则它共有________个度为2的结点。7．在一个具有n个顶点的无向完全图中，包含有条边，在一个具有n个顶点的有向完全图中，包含有条边。三．判断题（5×2分）1．完全二叉树未必是满二叉树。()2．线性表中的每个元素都有一个前驱元素和后继元素。()3．二

6、叉排序树采用先序遍历可以得到结点的有序序列。()4．采用顺序结构存储线性表时，其地址可以是不连续的。()5．一个有序的单链表不能采用折半查找法进行查找。()四．应用题（20分）1.画出带头结点的单链表、单循环链表和双向循环链表的示意图，并归纳三者的不同之处。（9分）2.对于给定的一组关键码：83，40，63，13，84，35，画出用简单选择排序对上述序列进行操作的各趟结果。（5分）71.给出下图所示的二叉树的先序、中序、后序的遍历结果。（6分）AFBCDGE五．算法设计题（20分）1．有顺序表A和

7、B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也是从小到大升序排列。要求写出完整代码。（12分）2．写出折半查找的算法，并回答其使用的局限性。（8分）7答案及评分标准：数据结构(C语言)答案及评分标准一．选择题（10×2分）：每小题只有一个正确答案，错选或不选均不给分。12345678910CDABCCDABC二．填空题（30分）：每空2分。1．集合线性结构树型结构图型结构2．0n－13．满top==MAXSIZE-1空top==-1。4．后进先出5．166．

8、497．n三．判断题（5×2分）1．√；2．×；3．×；4．×；5．√四．应用题（4×5分）1.a1an……HHLAB单链表：只有从头结点出发，才能访问到所有结点。单循环链表：从任意一结点出发，均可访问到其他结点。双向循环链表：既可以方便的找到前趋结点，又可方便的找到后继结点。2．83，40，63，13，84，3513，40，63，83，84，3513，35，63，83，84，4013，35，40，83，84，6313，35，40，63，84，83713，35，40，63，83，8