四川师范大学2007－2008学年度第二学期数据结构期末考试试
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
B1四川师范大学计算机科学学院电子商务、教育技术学专业2007－2008学年度第二学期期末考试数据结构试卷B卷答卷说明：1.本试卷共9页，五个大题，满分100分，120分钟完卷。2.本试卷为闭卷考试，请将所有题目直接做在试卷上。3.本试卷适用于2006级4、5班。得分评卷人一、单项选择题(每题2分，共20分，请将答案填在答题卡中)答题卡题号12345答案题号678910答案题号一二三四五总分总分人分数www.zhinanche.com1．单循环链表的尾结点的指针域的值为()。A)NULLB)0C)首结点地址D)尾结点地址2．设有一个足够大的栈，入栈元素的顺序为wxyz,，则栈的可能输出序列是（）。A）zwyxB）ywxzC）wxyzD）zxyw3．设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是：Ａ)BCDEFＢ)BCDEFGＣ)BCPQRSTＤ)BCDEFEF4．若广义表A=（(a,b,c),(d,e,f)）,则式子GetHead(GetTail(GetHead(GetTail(A))))的值为（）。A）（a,b,c）B）(d,e)C）eD）fwww.zhinanche.com5．下列程序段的时间复杂度是（）。i=1;while(i<=n)i*=2;A）O(1)B）O(㏒2n)C）O(n)D）O(n2)6．已知一算术表达式的中缀形式为A＋B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为（）。A）–A+B*C/DEB）–A+B*CD/EC）–+*ABC/DED）–+A*BC/DE7．假设有60行70列的二维数组a[1…60,1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为（）。（无第0行第0列元素）Ａ）16902Ｂ）16904Ｃ）14454Ｄ）答案A,B,C均不对8．设满二叉树的深度为m，现采用顺序表示法存储该满二叉树，每个结点占L个存储单元，则共需要()个存储单元。A)mB)2m*LC)(2m-1)*LD)(2m+1)*L9．在一个图中，所有顶点的度数之和等于图的边数的（）倍。A）1/2B）1C）2D）410．若在线性表中采用折半查找法查找元素，该线性表应该（）。A）元素按值有序B）元素按值有序，且采用链式存储结构C）元素按值有序，且采用顺序存储结构D）采用顺序存储结构得分评卷人www.zhinanche.com二、填空题(每题2分，共20分，请将答案填在答题卡中。)答题卡题号12345答案①①①②②②题号678910答案①①②②1．在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行的语句为①、②。2．一个算法的效率可分为①效率和②效率。3．在顺序表中访问任意一结点的时间复杂度均为①，因此，顺序表也称为②的数据结构。4．设一棵完全二叉树有700个结点，则共有个叶子结点。5．具有n个顶点的有向简单图最多有条边。6．若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为。7．三元组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的①、②和元素值。8．在一棵平衡二叉排序树中，每个结点的左子树高度与右子树高度之差的绝对值不超过________。9．在冒泡、希尔、快速和堆排序算法中，在待排序数据已有序时，花费时间反而最多的是排序。10、大多数排序算法都有两个基本的操作①和②。得分评卷www.zhinanche.com人三、简答题(共5道小题，其中1-4题每题5分，第5题10分，共30分)1.已知n阶下三角矩阵A(即当1≤i＜j≤n时，有aij＝0;当1≤j≤i≤n时，aij≠0)，按照压缩存储的思想，可以将其主对角线以下所有元素(包括主对角线)从第一列开始采用列序为主序依次存放于一维数组B[1..]中。请写出下三角任意元素aij(j≤i)在B中的下标k的值的计算公式。（5分）www.zhinanche.com2.假设字符a、b、c、d、e、f的使用次数分别是5,8,11,23,25,28，画出Huffman树，并根据这棵树写出a、b、c、d、e、f的Huffman（哈夫曼）编码。（5分）3．用序列（46，88，45，39，70，58，101，10，66，34）建立一个二叉排序树，画出该树，并求在等概率情况下查找成功的平均查找长度。（5分）www.zhinanche.com4．已知一个无向图的邻接表如下图所示，要求：(5分)（1）画出该无向图；（2）根据邻接表，分别写出用DFS(深度优先搜索)和BFS（广度优先搜索）算法从顶点V0开始遍历该图后所得到的遍历序列。5．若关键字序列为（47，7，29，11，16，92，22，8，3，50，37，89，94，21），取哈希函数为：Hash(key)=keymod11，给出用链地址法解决冲突所构造的哈希表，然后求出在等概率的情况下，这种方法在查找成功时的平均查找长度。(10分)www.zhinanche.com得分评卷人四、阅读算法并填空（10分）如下是一个折半查找算法，请在画线处填上适当内容，将算法补充完整。//查找表存储结构表示typedefstruct{ElemType*elem;//数据元素存储空间基址intlength;//表长度}Table;intSearch(TableST,KeyTypekey){//设有序表ST中元素按关键字降序排列，要求在其中查找其关键字等于key的数据元//素，找到则返回该元素在表中的位置，否则返回0。low=1;①while②{mid=(low+high)/2;ifEQ(key,ST.elem[mid].key)returnmid;elseifLT(key,ST.elem[mid].key)③;www.zhinanche.comelse④;}⑤;}//Searchwww.zhinanche.com得分评卷人五、用类C语言描述下列算法，并给出必要说明。（每题10分，共20分）1、已知带表头结点的单链表L，在该单链表中第i个结点处插入新元素X。已知线性表的单链表存储结构如下：typedefstructLnode{elemtypedata;Lnode*next;}Lnode,*LinkList;www.zhinanche.com2、设二叉树采用二叉链表存储结构，试设计一个算法计算一棵给定二叉树的所有叶子结点的数目。//二叉树的存储表示typedefstructBiTNode{ElemTypedata;StuctBiTNode*lchild,*rchild;//左右指针标志}BiTNode,*BiTreewww.zhinanche.com
浙公网安备 33021202002483