数据结构试卷及答案(共11页).doc
精选优质文档-倾情为你奉上-装-订-线-系 专业 年级 班级 学号 顺序号 姓名 -阅-卷-密-封-线- （密封线内不要答题）索 石家庄经济学院/ 学年第 学期课程名称： 数据结构 共 6 页试卷类型： B 考试形式： 闭 卷 一二三四总 分得 分阅卷人一、选择题（每题2分，共20分）1. 算法分析的目的是( )。A. 找出数据结构的合理性B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性2. 在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( )。A. O(1) B. O(n) C. O(n2) D. O(nlog2n)3. 一个栈的入栈序列a，b，c，d，则栈的不可能的输出序列是_。 A. dcba B. adcb C. dcab D. abcd 4. 字符串的长度是指（ ）。 A. 串中所含字符的个数B. 串中不同字母的个数 C. 串中不同字符的个数D. 串中不同数字的个数5. 数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A85的起始地址为( )。A. SA+141 B. SA+144 C. SA+222 D. SA+2256. 任意3个结点可组成不同形态的二叉树共有（ ）A. 30种 B. 3种 C. 4种D. 5种7. 设一棵完全二叉树中有14个结点，则该完全二叉树的深度为（ ）。A. 4 B.2 C. 3 D. 58. 在一个图中，所有顶点的度数之和等于所有边数的（ ）倍。A. 1/2 B. 1 C. 2 D. 4 9. 有一个顺序表为1，3，19，12，32，41，45，当顺序查找值3为的结点时，（ ）次比较后查找成功。A. 1 B. 2 C. 4 D. 810. 设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字60为基准而得到的一趟快速排序结果是（ ）。A. 40，42，60，55，80，85 B. 42，45，55，60，85，80C. 42，40，55，60，80，85 D. 42，40，60，85，55，80二、填空题（每题1分，共10分）1. 数据的物理结构主要包括 和链式存储结构两种情况。2. 不论是循环队列还是链队列，其入队和出队操作的时间复杂度均为_。3. 设顺序线性表中有10个数据元素，删除第5个位置上的数据元素需要移动表中_个元素。4. 在线性表的单链接存储结构中，每个结点包含有两个域，一个叫 ，另一个叫指针域。5. 设一棵二叉树的前序序列为ABC，则有_种不同的二叉树可以得到这种序列。 6. 在表示n个结点二叉树的二叉链表中，共有 个非空指针域。7. 数据结构的逻辑结构被分为集合结构、线性结构、 和图形结构四种。8. 广义表(a),c,d)的表尾是 。9. 在一个大顶堆中，堆顶元素的值是所有结点中的_。10. n个顶点的连通无向图至少有 条边。-阅-卷-密-封-线- （密封线内不要答题）索 三、综合题（共50分）1. 对于给定的5个实数W=9，5，13，3，6，试构造Huffman树；并求出该树的最小带权路径长度和各结点的Huffman编码。要求写出Huffman树的构造过程。(10分)2. 对给定的一组关键字：65，97，76，13，27，49，55，4写出希尔排序（增量为5，3，1）前2趟排序结果。（6分） 3. 已知一棵二叉树的前序遍历序列和中序遍历序列分别为 ABEFIJDGH和 EBIFJAGDH。要求：（1）画出这棵二叉树；要求写出分析写出过程；（2）写出这棵二叉树的后序遍历序列。（8分）4. 已知一组关键字(19,14,23,1,68,20,84)，哈希函数为：H(key)=key MOD 13, 哈希表长为m=16，设每个记录的查找概率相等，用线性探测再散列处理冲突，计算每个关键字的哈希地址，构造出哈希表，并计算平均查找长度。（10分）-阅-卷-密-封-线- （密封线内不要答题）索 5. 使用普里姆算法构造下图的最小生成树。要求写出过程。（10分）6. 分析下面程序段的时间复杂度，（要求给出分析计算过程）（6分） m=0; for (i=1;i<=n; i+) for (j=1; j<=n; j+) m+;四、算法设计题（每题10分，共20分）1. 用类C语言编写在带头结点的单链表L中删除第i个元素。 2. 二叉树采用二叉链表存储结构，用类C语言编写统计一棵二叉树t中元素值等于e的结点个数的算法。石家庄经济学院/2 学年第 学期数据结构卷 参考答案及评分标准 一、选择题（每题2分，共20分）15: C B C A C 610: D A C B C评分标准：每题选对2分，错选，漏选均不得分。二、填空题（每题1分，共10分）1. 顺序存储结构2. O（1）3. 54. 值域5. 56. n-17. 树形结构8. (c,d)9. 最大值10. n-1评分标准：每题填对1分，错填，漏填均不得分。三、综合题（共50分）1. Huffman树如下图：3614386522913 (4分)WPL=(3+5)*3+(6+9+13)*2=80 （2分）按左0右1，进行编码。结点6的编码 00结点3的编码 010结点5的编码 011结点9的编码 10结点13的编码 11 （4分）2. 希尔排序（增量为5，3，1）的前2趟排序结果：第1趟结果：49 55 4 13 27 65 97 76 （3分）第2趟结果：13 27 4 49 55 65 97 76 （3分）JIHGFEDBAA3. （1）二叉树为： （6分）（2）该二叉树后序序列： EIJFBGHDA （2分）4. （7分）哈希表如下：（1分）ASL=(5*1+2+3)/7=1.43 (2分)5. 评分标准： （b）到（d），每步2分。6. 首先分析出程序段的基本操作是m+ ，然后计算出基本操作的重复执行次数为：n+n+n+n= n2. (4分 )所以，时间复杂度为：O(n2) （2分）四、算法设计题（每题10分，共20分）1. 用类C语言编写在带头结点的单链表L中删除第i个元素。 Status ListDelete_L(LinkList &L,int i,ElemType e) /在带头结点的单链表L中删除第i个元素,并由e返回其值 p=L;j=0;/初始化,p指向第一个结点,j为计数器 while(p->next&&j<i-1)/寻找第i个结点，使p指向它的前趋 p=p->next,j+; (5分) if(!(p->next)|j>i-1)return ERROR;/删除位置不合理 q=p->next; p->next=q->next; e=q->data; free(q) /删除并释放结点 return OK; (5分)/ ListDelete_L 2. 二叉树采用二叉链表存储结构，用类C语言编写统计一棵二叉树t中元素值等于e的结点个数的算法。typedef struct btnode * bitreptr;struct btnode datatype data;bitreptr lchild, rchild; void countleaf(bitreptr t, int &count) if(t!=null) if(t data= =e) count+; /count的初值设为0 (4分) countleaf(tlchild, count); (3分) countleaf(trchild, count); (3分) 专心-专注-专业
