数据结构试卷卷参考答案.doc

《数据结构试卷卷参考答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、福建对外经济贸易职业技术学院课程名称：数据结构适用班级：系别：专业：考试日期：姓名：班级：学号：题型一（20%）二（30%）三（20%）四（30%）总分评卷人得分本题得分小计一、填空题(本大题共20空，每空1分，共20分)1．从数据结构S中的某指定位置上增加一个新结点的运算是加工型运算。2．线性表的元素长度为4，Loc(ai)=2000，则Loc(ai+1)=2004。3．线性表中数据元素的个数n称为线性表的长度。4．以链式存储结构实现的线性表，被称为链表。5．在一个不带表头结点的非空单链表中，若要在指针qtr所指结点的

2、后面插入一个值为x的结点，则需要执行下列操作：ptr=malloc(size);ptr->Data=x;ptr->next=qtr->next;qtr->Next=ptr;6．如果操作顺序是先让字母A、B、C进栈，做两次出栈；再让字母D、E、F进栈，做一次出栈；最后让字母G进栈，做三次出栈。最终这个堆栈从栈顶到栈底的余留元素应该是A。7．字符串是一种特殊的线性表，特殊在于它的数据元素只能是字符，特殊在于串可以作为一个整体参与所需要的处理。8．结点数为7的二叉树的高度最矮是3，最高是7。9．快速排序方法是通过适当的位置交换

3、，把序列中的元素一次性地放到了它的最终位置上。10．将一棵完全二叉树按层次进行编号。那么，对编号为i的结点，如果有左孩子，则左孩子的编号应该是2i；如果有右孩子，则右孩子的编号应该是2i+1。11．树中结点的度，是指结点拥有直接后继的个数。12．所谓结点的深度，即是指该结点位于树的层次数。13．若经过某种排序之后，那些有相同关键字值的记录间的相对位置保持不变，那么称这种排序方法是稳定的。14．在数据结构中，把n（n≥0）棵互不相交的树的集合称为森林。15．在一个具有4个顶点的无向图中，要连通全部顶点，，至少需要3条边。1

4、6．包含无向连通图G的所有n个顶点在内的极小连通子图，是这个图的生成树。17．一个具有n个顶点的完全图的边数是n(n-1)/2。18.对一个基本有序的数据进行排序冒泡排序方法运算次数最少。本题得分小计二、选择题（本大题共15题，每题2分，共30分）1．在常见的数据处理中，(B)是最基本的处理。A．删除B．查找C．读取D．插入2．链式存储结构中，每个数据的存储结点里(D)指向邻接存储结点的指针，用以反映数据间的逻辑关系。A．只能有1个B．只能有2个C．只能有3个D．可以有多个3．在一个单链表中，若现在要删除ptr指针所指结

5、点的直接后继结点，则需要执行的操作是(A)。A．ptr->Next=ptr->Next->Next;B．ptr=ptr->Next;ptr->Next=ptr->Next->Next;C．ptr=ptr->Next->Next;D．ptr->Nextptr;4．在长度为n的顺序表中，往其第i个元素（1≤i≤n）之前插入一个新的元素时，需要往后移动(B)个元素。A．n-iB．n-i+1C．n-i-1D．i5．一个栈的元素进栈序列是a、b、c、d、e，那么下面的(C)不能做为一个出栈序列。A．e、d、c、b、aB．d、e、c

6、、b、aC．d、c、e、a、bD．a、b、c、d、e6．一个循环队列的最大容量为m+1，front为队首指针，rear为队尾指针。那么进队操作时求队位号应该使用公式(D)。A．Cq_front=(Cq_front+1)%mB．Cq_front=(Cq_front+1)%(m+1)C．Cq_rear=(Cq_rear+1)%mD．Cq_rear=(Cq_rear+1)%(m+1)7．在所给的4棵二叉树中，(C)不是完全二叉树。8．设有一棵5个结点的二叉树，其先序遍历序列为：A-B-C-D-E，中序遍历序列为：B-A-D-C

7、-E，那么它的后序遍历序列为(B)。A．A-B-D-E-CB．B-D-E-C-AC．D-E-C-A-BD．A-B-C-D-E9．设森林F中有3棵树，依次有结点n1、n2、n3个。把该森林转换成对应的二叉树后，该二叉树的右子树上的结点个数是(D)。A．n1B．n1+n2C．n3D．n2+n310．一棵有n个结点的树，在把它转换成对应的二叉树之后，该二叉树根结点的左子树上共有(B)个结点。A．n-2B．n-1C．n+1D．n+211．在一个有n个顶点的无向图中，要连通全部顶点，至少需要(C)条边。A．nB．n+1C．n-1D

8、．n/212．对于一个无向完全图来说，它的每个不同顶点对之间，都存在有一条边。因此，有n个顶点的无向完全图包含有(C)条边。A．n(n-1)B．n(n+1)C．n(n-1)/2D．n(n+1)/213．采用顺序查找法查找长度为n的线性表时，其平均查找长度为(C)。A．nB．n/2C．(n+1)/2D．(n-1)/21