资源描述：
《数据结构期末考试试题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、2005年－2006学年第二学期“数据结构”考试试题（A）姓名 学号(序号)_答案隐藏 班号 要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清楚姓名、班号和学号），需写清楚题目的序号。每张答题纸都要写上姓名和序号。一、单项选择题（每小题2分，共20分）1．数据的运算a 。A.效率与采用何种存储结构有关 B.是根据存储结构来定义的C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述答：A。2.链表不具备的特点是 a 。A.
2、可随机访问任一结点 B.插入删除不需要移动元素C.不必事先估计存储空间 D.所需空间与其长度成正比答：参见本节要点3。本题答案为：A。3.在顺序表中删除一个元素的时间复杂度为 c 。A.O(1) B.O(log2n)C.O(n) D.O(n2)答：C。4．以下线性表的存储结构中具有随机存取功能的是 d 。A.不带头结点
3、的单链表 B.带头结点的单链表C.循环双链表 D.顺序表解 D。5.一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 c 。A.edcba B.decba C.dceab D.abcde答：C。6.循环队列qu的队空条件是 d 。A.(qu.rear+1)%MaxSize==(qu.fr
4、ont+1)%MaxSizeB.(qu.rear+1)%MaxSize==qu.front+1C.(qu.rear+1)%MaxSize==qu.frontD.qu.rear==qu.front答：D。7.两个串相等必有串长度相等且 b 。A.串的各位置字符任意 B.串中各位置字符均对应相等C.两个串含有相同的字符 D.两个所含字符任意答：B。8.用直接插入排序对下面四个序列进行递增排序，元素比较次数最少的是c 。A.94,32,40,90,
5、80,46,21,69 B.32,40,21,46,69,94,90,80C.21,32,46,40,80,69,90,94 D.90,69,80,46,21,32,94,40答：C。9.以下序列不是堆（大根或小根）的是 d 。A.{100,85,98,77,80,60,82,40,20,10,66} B.{100,98,85,82,80,77,66,60,40,20,10}C.{10,20,40,60,66,
6、77,80,82,85,98,100} D.{100,85,40,77,80,60,66,98,82,10,20}答：D。10.以下排序方法中，b，在初始序列已基本有序的情况下，排序效率最高。A.直接选择排序 B.昌泡排序C.快速排序 D.堆排序答：B。二、填空题（每题2分，共10分）1.将f=1+++…(n>3)转化成递归函数，其递归出口是 ① ，递归体是 ②
7、答：①f(1)=1 ②f(n)=f(n-1)+评分标准：每空1分2．广义表((),a,(a),((a)))的长度是4① ，深度是3 ② 。答：4 3评分标准：每空1分3.具有n个结点的二叉树采用二叉链存储结构，共有n+1 个空指针域。答：n+1。4.在有n个顶点的有向图中，每个顶点的度最大可达2(n-1) n-1 。答：2(n-1)。5.外排序的基本方法是归并法。它一般要经历文件预处理①和多路归并②两个阶段。答：产生初始归并段（或顺串） 多路归并评分标准：每空1分三、问答题（共30分）1．设n是偶数，试计
8、算运行下列程序段后m的值并给出该程序段的时间复杂度（需写出过程）。（6分）intm=0,i,j;for(i=1;i<=n;i++) for(j=2*i;j<=n;j++) m++;∑i=1```i=n/2 (n-2i+1)(n+1)n/2-2*(1+2+…n/2)=(n+1)n/2-2*(
