数据结构试卷及答案(1)

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.一个栈的入栈序列a，b，c，d，则栈的不可能的输出序列是____。A.dcbaB.adcbC.dcabD.abcd4.字符串的长度是指（）。A.串中所含字符的个数B.串中不同字母的个数C.串中不同字符的个数D.串中不同数字的个数5.数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为()。A.SA+141B.SA+144C.SA+222D.SA+225-----------------------------------------------装-------------------------------------------订----------------------------------线------------------------------------系专业年级班级学号顺序号姓名-----------------------阅-------------------------卷---------------------------密----------------------------封---------------------------线-----------------------（密封线内不要答题）索26.任意3个结点可组成不同形态的二叉树共有（）A.30种B.3种C.4种D.5种7.设一棵完全二叉树中有14个结点，则该完全二叉树的深度为（）。A.4B.2C.3D.58.在一个图中，所有顶点的度数之和等于所有边数的（）倍。A.1/2B.1C.2D.49.有一个顺序表为{1，3，19，12，32，41，45}，当顺序查找值3为的结点时，（）次比较后查找成功。A.1B.2C.4D.810.设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字60为基准而得到的一趟快速排序结果是（）。A.40，42，60，55，80，85B.42，45，55，60，85，80C.42，40，55，60，80，85D.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个顶点的连通无向图至少有条边。3三、综合题（共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分）-----------------------阅-------------------------卷---------------------------密----------------------------封---------------------------线--------------------------（密封线内不要答题）索43.已知一棵二叉树的前序遍历序列和中序遍历序列分别为ABEFIJDGH和EBIFJAGDH。要求：（1）画出这棵二叉树；要求写出分析写出过程；（2）写出这棵二叉树的后序遍历序列。（8分）4.已知一组关键字(19,14,23,1,68,20,84)，哈希函数为：H(key)=keyMOD13,哈希表长为m=16，设每个记录的查找概率相等，用线性探测再散列处理冲突，计算每个关键字的哈希地址，构造出哈希表，并计算平均查找长度。（10分）55.使用普里姆算法构造下图的最小生成树。要求写出过程。（10分）6.分析下面程序段的时间复杂度，（要求给出分析计算过程）（6分）m=0;for(i=1;i=n;i++)for(j=1;j=n;j++)m++;-----------------------阅-------------------------卷---------------------------密----------------------------封---------------------------线--------------------------（密封线内不要答题）索6四、算法设计题（每题10分，共20分）1.用类C语言编写在带头结点的单链表L中删除第i个元素。2.二叉树采用二叉链表存储结构，用类C语言编写统计一棵二叉树t中元素值等于e的结点个数的算法。7石家庄经济学院/2学年第学期数据结构卷参考答案及评分标准一、选择题（每题2分，共20分）1~5:CBCAC6~10:DACBC评分标准：每题选对2分，错选，漏选均不得分。二、填空题（每题1分，共10分）1.顺序存储结构2.O（1）3.54.值域5.56.n-17.树形结构8.(c,d)9.最大值10.n-1评分标准：每题填对1分，错填，漏填均不得分。三、综合题（共50分）1.Huffman树如下图：(4分)36143865229138WPL=(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趟结果：495541327659776（3分）第2趟结果：132744955659776（3分）3.（1）二叉树为：（6分）（2）该二叉树后序序列：EIJFBGHDA（2分）4.（7分）JIHGFEDBAA9哈希表如下：（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四、算法设计题（每题10分，共20分）1.用类C语言编写在带头结点的单链表L中删除第i个元素。StatusListDelete_L(LinkList&L,inti,ElemTypee){//在带头结点的单链表L中删除第i个元素,并由e返回其值p=L;j=0;//初始化,p指向第一个结点,j为计数器while(p-next&&ji-1){//寻找第i个结点，使p指向它的前趋p=p-next,j++;}(5分)if(!(p-next)||ji-1)returnERROR;//删除位置不合理q=p-next;p-next=q-next;e=q-data;free(q)//删除并释放结点returnOK;(5分)}//ListDelete_L2.二叉树采用二叉链表存储结构，用类C语言编写统计一棵二叉树t中元素值等于e的结点个数的算法。typedefstructbtnode*bitreptr;structbtnode{datatypedata;bitreptrlchild,rchild;}voidcountleaf(bitreptrt,int&count){if(t!=null){if(t→data==e)count++;//count的初值设为0(4分)countleaf(t→lchild,count);(3分)countleaf(t→rchild,count);(3分)}}