2012~2013安徽大学《数据结构》期末试卷.docx

《2012~2013安徽大学《数据结构》期末试卷.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2012~2013安徽大学《数据结构》期末试卷一、单项选择题，在括号内填写所选择的标号（每小题1分，共12分）1.下面程序段的时间复杂度为()。for(inti=0;i

2、向进行插入和删除的操作B.便于双向进行插入和删除的操作C.节省空间D.便于销毁结构释放空间5.设链式栈中结点的结构为（data,link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一个由指针s所指的结点，则应执行()操作。A.top->link=s;B.s->link=top->link;top->link=s;C.s->link=top;top=s;D.s->link=top;top=top->link;6.设有一个递归算法如下intX(intn){if(n<=3)return1;elsereturnX(n-2)+X(n-4)+1;}

3、试问计算X(X(5))时需要调用（）次X函数。A．2B．3C．4D．57.一棵具有35个结点的完全二叉树的高度为()。假定空树的高度为-1。A.5B.6C.7D.88.向具有n个结点的堆中插入一个新元素的时间复杂度为()。A.O(1)B.O(n)C.O(log2n)D.O(nlog2n)9.在一棵AVL树中，每个结点的平衡因子的取值范围是()。A.-1~1B.-2~2C.1~2D.0~110.一个有n个顶点和n条边的无向图一定是()。A．连通的B．不连通的C．无环的D．有环的11.在用Kruskal算法求解带权连通图的最小（代价）生成树时，通常

4、采用一个（）辅助结构，判断一条边的两个端点是否在同一个连通分量上。A.位向量B.堆C.并查集D.生成树顶点集合12.设有一个含有200个元素的表待散列存储，用线性探查法解决冲突，按关键码查询时找到一个元素的平均探查次数不能超过1.5，则散列表的长度应至少为（）。（注：平均探查次数的计算公式为Snl={1+1/(1-α)}/2,其中α为装填因子）A.400B.526C.624D.676二、填空题，在横线处填写合适内容（每小题1分，共12分）1.数据结构的逻辑结构包括线性结构和________结构两大类。2.在程序运行过程中不能扩充的数组是____

5、______分配的数组。这种数组在声明它时必须指定它的大小。3.链表只适用于查找。4.设双向循环链表中每个结点的结构为(data,llink,rlink),则结点*p的前驱结点的地址为__________。5.在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有________个结点。6.一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y)))，结点k的所有祖先的结点数为________个。7.若将一棵树A(B(C,D,E),F(G(H),I))按照左子女-右兄弟表示法转换为二叉树，该二叉树中度为2的结点

6、的个数为________个。8.从一棵二叉搜索树中搜索一个元素时，若给定值大于根结点的值，则需要向________继续搜索。9.设图G=(V,E)，其中则从顶点V0开始对图G的深度优先序列总共有________种。10.第i(i=0,1,...,n-2)趟从参加排序的序列中第i个至第n-1个元素中挑选出一个最小元素，把它交换到第i个位置，此种排序方法叫做_____________排序。11.快速排序在最坏情况下的时间复杂度为____________。12.假定对长度n=100的线性表进行索引顺序搜索，并假定每个子表的长度均为n，则进行索引顺序搜

7、索的平均搜索长度为________。三、判断题，在每小题前面打对号表示正确或打叉号表示错误（每小题1分，共10分）1.算法和程序原则上没有区别，在讨论数据结构时二者是通用的。2.插入与删除操作是数据结构中最基本的两种操作，因此这两种操作在数组中也经常被使用。3.栈和队列都是顺序存取的线性表,但它们对存取位置的限制不同。4.将f=1+1/2+1/3+…+1/n转化为递归函数时，递归部分为f(n)=f(n-1)+1/n，递归结束条件为f(1)=1。5.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和中根遍历，则具有相同的结

8、果。6.进行折半搜索的表必须是顺序存储的有序表。7.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与