数据结构试题B(08-09-2

1、2008 -2009 学年第 2 学期 数据结构 试题（卷）B课程代码 BB002016 考试方式 闭卷 考试时长 100分钟姓名 学号 教学班号 专业 级 班题 号一二三四五六七八合计满 分10204624100得 分阅卷人得分一、选择题：（10分，每题1分） 1算法的时间复杂度取决于（ ）A问题的规模 B. 待处理数据的初态 C. A和B3已知串S=aaab,其Next数组值为（ ）A0123 B0113 C0111 D01213下面关于线性表的叙述中，错误的是哪一个？（ ）A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储

2、，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。4. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1<=i<=n+1)。A. O(0) B. O(1) C. O(n) D. O(n2) 5. 将一个A1.100，1.100的下三角矩阵，按行优先存入一维数组B15050中，A中元素A66,65（即该元素下标i=66，j=65），在B数组中的位置K为（ ）。A. 2210 B. 2211 C. 2219 6对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）Ahead=NULL Bhead.ne

3、xt=NULL Chead.next=head Dhead!=NULL7一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。A. 不确定 B. n-i+1 C. i D. n-i8一棵具有 n个结点的完全二叉树的树高度（深度）是（ ）Aëlognû +1 Blogn+1 Cëlognû Dlogn-19设无向图的顶点个数为n，则该图最多有（ ）条边。An-1 Bn(n-1)/2 C n(n+1)/2 D0 En210含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（ ） A.3 B

4、.4 得分二、填空题：（20分，每空2分）1. 在线性表的顺序存储中，元素之间的逻辑关系是通过_ 决定的；在线性表的链接存储中，元素之间的逻辑关系是通过_ _决定的。2.三个结点可构成_种不同形态的二叉树。3. 对于栈只能在_(位置)插入和删除元素。4.在数据结构中，数据的逻辑结构分为集合、_、_和图状结构等四类。5对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为2n个，其中_个用于链接孩子结点。6.对二叉排序树进行_遍历，可得到排好序的递增结点序列。7在双向链表结构中，若要求在p 指针所指的结点之前插入指针为s 所指的结点，则需执行下列语句：s->next:

5、=p； s->prior:= _ ；p->prior:=s；_ _:=s；得分三、构造题（46分）1. 给定一组数据8，9， 16，21，5，18，以它构造一棵哈夫曼树，并计算带权路径长度（10分）。2. 对下边的无向加权图，按kruskal算法求其最小生成树，（6分）561v154v2v536v35v第2题图3. 对于下面的有向无环图，写出它的四个不同的拓扑有序序列。（4）712846354. 设有一个关键码的输入序列 5， 33， 18， 7， 46， 73， 3， 22，44，23 ，从空树开始构造二叉排序树，画出每加入一个新结点时二叉树的形态。并计算查找成功时的平均查找长度。(14分)5给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18),写出用下列算法从小到大排序时第一趟结束时的序列（只写出最终的结果）； （1） 希尔排序（第一趟排序的增量为5） （3分）（2） 堆排序（3分）（3） 冒泡排序（3分）（4） 直接插入排序（3分）得分三、算法设计（24分）（一）定义一个单链表类，链表中结点的数据类型为整