2008-09(2)数据结构期末试卷(c)

《2008-09(2)数据结构期末试卷(c)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、汕头职业技术学院2008-2009学年第二学期期末试卷（C）课程名称数据结构学分_____拟题人何汉阳审题人___________系(校区)计算机系班级_______________学号_____姓名__________题号一二三四五六七八总分评卷人得分一、填空（每空1分，共20分）1.数据结构是研究数据的__________和________以及他们之间的相互关系，并对这种结构定义相应的__________。2.在线性表的顺序存储中，元素之间的逻辑关系是通过_________决定的；在线性表的链接存储中，元素之间的逻

2、辑关系是通过_____________决定的。3.对于一个具有N个结点的单链表，在已知的结点*P后插入一个新结点的时间复杂度为_________,在给定值为X的结点后插入一个新结点的时间复杂度为_____________。4.一个字符串相等的充要条件是__________________和______________________。5.对于一棵具有n个结点的二叉树，对应二叉链表中指针总数为________个，其中_______个用于指向子女结点，__________个指针空闲着。6.在一棵三叉树中，度为3的结点数有2

3、个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有__________个。7.在霍夫曼编码中，若编码长度只允许小于等于4，则除了已对两个字符编码为0和10外，还可以最多对__________个字符编码。8.在一个无向图中，所有顶点的度数之和等于所有边数的______倍。在一个具有n个顶点的无向图中，要连通所有顶点则至少需要________条边。9.以折半搜索方法从长度为12的有序表中搜索一个元素时，平均搜索长度为___________。10.在直接选择排序中，记录比较次数的时间复杂度为________

4、,记录移动次数的时间复杂度为______。11.假定一组记录的排序码为（46，79，56，38，40，80），对其进行快速排序的一次划分的结果为_____________________。二、选择题（在正确答案上打“√”，共20分，每小题2分）1.根据具有n个元素的一个线性表,建立一个有序单链表的时间复杂性为:(A).O(1)(B).O(n)(C).O(n2)(D).O(logN)2.采用链接方式存储线性表的优点是_________。(A).便于随机存取(B).花费的存储空间较顺序存储少(C).便于插入和删除操作(D)

5、.数据元素的物理顺序和逻辑顺序相同3．队列操作的原则是_________。(A).先进先出(B).后进先出(C).只能进行插入(D).只能进行删除4．在有n个结点的二叉链表中，值为非空的链域的个数为______。(A).n-1(B).n+l(C).2n-1(D).2n+l5.在一个链队列中,假定front和rear分别为队首指针和队尾指针,则进行插入s结点的操作时应执行________。(A).front->next=s;front=s;(B).rear->next=s;rear=s;(C).s->next=rear;

6、rear=s;(D).s->next=front;front=s;6.在一个长度为n的顺序表中，删除值为x的元素需要比较和移动元素的平均次数为_______。(A).n/2(B).(n+1)/2(C).n(D).n+17．下面关于图的存储的叙述中，哪一个是正确的。（）(A)．用相邻矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关(B)．用相邻矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关(C)．用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关(D)．用邻接表法存储图

7、，占用的存储空间数只与图中边数有关，而与结点个数无关8．非空的循环单链表head的尾结点(有指针p所指)满足______。(A).p->next=NULL(B).p->next=head(C).p=NULL(D).p=head9.下列陈述中正确的是()(A).二叉树是度为2的有序树(B).二叉树中结点只有一个孩子时无左右之分(C).二叉树中必有度为2的结点(D).二叉树中最多只有两棵子树，并且有左右之分10.在最好和最坏情况下的时间复杂度均为O(nlog2n)且稳定的排序方法是()(A).快速排序(B).堆排序(C).

8、归并排序(D).基数排序三、判断题（每小题2分，共20分）1、逻辑结构不相同的数据，要采用不同的存储方法来存储。（）2、在有n个元素的顺序表中，删除任意一个元素所需移动结点的平均次数为n-1。（）3、线性表的链式存储方式优于顺序存储方式。（）4、对顺序栈进行进栈、出栈操作，不涉及元素的前、后移动问题。（）5、已知二叉树的先序和后序