数据结构(c语言)试卷（1）

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

1、成都东软信息技术学院200~200学年第学期期末试题——数据结构(C语言)题号一二三四五六总分分数本课程为闭卷考试，试卷共六道大题，试卷满分100分，考试时间120分钟。一．选择题（10×2分）：共10小题，请将答案填入题中的括号中，每小题只有一个正确答案，错选或不选均不给分。1．组成数据的基本单位是（）Ａ．数据项Ｂ．数据类型C．数据元素D．数据变量2．线性表的链式存储实现有利于（）运算。A．插入B．读表元C．查找D．定位3．二叉树第i(i≥1)层最多有（）个结点。A．2iB．2iC．2i-1D．2i-14．设单链表中指针p指向结点

2、A，若删除A后的结点存在，则需要修改指针的操作为（）。A．p->next=p->next->nextB．p=p->nextC．p=p->next->nextD．p->next=p5．设一数列的输入顺序为1,2,3,4,5,6，通过栈操作不可能排成的输出序列为（）。A．3,2,5,6,4,1B．1,5,4,6,2,3C．2,4,3,5,1,6D．4,5,3,6,2,16．如果结点A有3个兄弟，而且B为A的双亲，则B是度为（）Ａ．3Ｂ．4C．5D．17．设循环队列Q[0..N-1]的头尾指针为F.R，当插入元素时尾指针R加1，头指针F总

3、是指向队列中第一个元素的前一个位置，则队列中元素计数为（）。A．R-FB．N-(R-F)C．(R-F+N)%ND．(F-R+N)%N8．若给定的关键字集合为{20,15,14,18,21,36,40,10}，一趟快速排序结束后，键值的排序为（）。A．10,15,14,18,20,36,40,21B．10,15,14,18,20,40,36,21C．10,15,14,20,18,40,36,21D．15,10,14,18,20,36,40,219．设有100个元素，用二分法查找时，最大比较次数是（），最小比较次数是（）。A．25B．7

4、C．10D．110．具有2000个结点的二叉树，其高度至少为（）。6A．9B．10C．11D．12二．填空题（20分）：每空2分，１．前序序列和中序序列相同的二叉树为。2．具有64个结点的完全二叉树的深度为。3．数据结构讲述的三大关系是、、。4．已知二叉树中的叶子树为50，仅有一个孩子的结点数为30，则总结点数为。5．简单选择排序在最好情况下所做的交换元素次数为。6．队列的原则是。7．快速排序算法在最差的情况下其时间复杂度是。8．顺序存储的队列如果不采用循环方式，则会出现问题。三．简答题（4×5分）1．试比较顺序存储和链式存储的优缺

5、点。（5分）2．简述栈和队列这两种数据结构的相同点和不同点。（5分）3．已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA，试画出这棵二叉树。（5分）4．采用简单选择排序对线性表（26,15,12,16,5,30）进行排序，进行交换的第一对元素是哪两个元素？在什么情况下，第一趟不需要进行元素的交换？（5分）四．判断题（5×2分）１．如果某数据结构的每一个元素都最多只有一个直接前驱和一个直接后继，则该数据结构必为线性表。()2．6若有一个叶子结点是某子树的中序遍历的最后一个结点，则它必是该子树的先序遍历的最后一

6、个结点。()3．进栈操作时，必须判断栈是否已满。()4．如果某排序算法是稳定的，那么该方法一定具有实际应用价值。()5．折半查找法的前提之一是线性表有序。()五．程序填空题（3×5分）1．以下是采用冒泡排序法对数组a进行排序，完成程序。（4分）bsort(inta[],intn){intn,inti,intj,inttemp;for(i=;j=i;--j){if(){temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}}}2．在单链表（表头指针为head）的元素中找出最

7、后一个值为e的元素，返回其指针；如果找不到，返回NULL。完成以下程序。(6分)typedefsrructLinkNode{intdata;structLinkNode*next;}Node;Node*search_link(Node*head,inte){Node*p,*q;q=;for(p=head;;p=p->next){if(p->data==e){;}}returnq;}3．下列算法是输出一棵二叉树的第i层的所有结点的值。假定根结点是第1层，完成以下程序。（5分）typedefsrructLinkNode{intdata;

8、structLinkNode*lchild,*rchild;}Node;voidouti(Node*tree,inti){if(tree==NULL)return;6if(i==1){printf(“%d”,tree->data)