数据结构试卷及答案(共11页).doc

《数据结构试卷及答案(共11页).doc》由会员分享，可在线阅读，更多相关《数据结构试卷及答案(共11页).doc（11页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上-装-订-线-系 专业 年级 班级 学号 顺序号 姓名 -阅-卷-密-封-线- （密封线内不要答题）索 石家庄经济学院/ 学年第 学期课程名称： 数据结构 共 6 页试卷类型： B 考试形式： 闭 卷 一二三四总 分得 分阅卷人一、选择题（每题2分，共20分）1. 算法分析的目的是( )。A. 找出数据结构的合理性B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性2. 在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( )。A. O(1) B. O(n) C. O(n2) D. O(nlog2n)3.

2、一个栈的入栈序列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.

3、 设一棵完全二叉树中有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

4、，85 D. 42，40，60，85，55，80二、填空题（每题1分，共10分）1. 数据的物理结构主要包括 和链式存储结构两种情况。2. 不论是循环队列还是链队列，其入队和出队操作的时间复杂度均为_。3. 设顺序线性表中有10个数据元素，删除第5个位置上的数据元素需要移动表中_个元素。4. 在线性表的单链接存储结构中，每个结点包含有两个域，一个叫 ，另一个叫指针域。5. 设一棵二叉树的前序序列为ABC，则有_种不同的二叉树可以得到这种序列。 6. 在表示n个结点二叉树的二叉链表中，共有 个非空指针域。7. 数据结构的逻辑结构被分为集合结构、线性结构、 和图形结构四种。8. 广义表(a),c,

5、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）画出

6、这棵二叉树；要求写出分析写出过程；（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; jnext&jne

7、xt,j+; (5分) if(!(p-next)|ji-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分) 专心-专注-专业