四川师范大学-第二学期数据结构期末试题B1.doc

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。 四川师范大学 第二学期数据结构期末考试试题 B1四川师范大学计算机科学学院电子商务、 教育技术学专业 第二学期期末考试数据结构试卷B卷答卷说明: 1.本试卷共9页, 五个大题, 满分100分, 120分钟完卷。2.本试卷为闭卷考试, 请将所有题目直接做在试卷上。3.本试卷适用于 级4、 5班。总分题号一二三四五总分人分数得分评卷人一、 单项选择题(每题2分, 共20分, 请将答案填在答题卡中)答题卡题162738495号答案题号答案10 1单循环链表的尾结点的指针域的值为()。A)NULL地址B)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) f 5下列程序段的时间复杂度是( i=1;) 。while(i=n)i*=2;A) O(1)B) O(2n)C) O(n)D) O(n)26已知一算术表示式的中缀形式为AB*C-D/E, 后缀形式为ABC*+DE/-, 其前缀形式为( ) 。A) A+B*C/DEC) +*ABC/DEB) A+B*CD/ED) +A*BC/DE7假设有60行70列的二维数组a160,170以列序为主序顺序存储, 其基地址为10000, 每个元素占2个存储单元, 那么第32行第58列的元素a32,58的存储地址为( ) 。( 无第0行第0列元素) ) 16902C均不对) 16904) 14454) 答案A,B,8设满二叉树的深度为m, 现采用顺序表示法存储该满二叉树, 每个结点占L个存储单元, 则共需要()个存储单元。A)mB)2m*LC)(2m-1)*LD)(2m+1)*L9在一个图中, 所有顶点的度数之和等于图的边数的( ) 倍。D) 4A) 1/2B) 1C) 210若在线性表中采用折半查找法查找元素, 该线性表应该( ) 。A) 元素按值有序B) 元素按值有序, 且采用链式D) 采用顺序存储结构存储结构C) 元素按值有序, 且采用顺序存储结构得分评卷人 二、 填空题(每题2分, 共20分, 请将答案填在答题卡中。)答题卡题号答案162738495题号答案101在一个单链表中, 若 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、 大多数排序算法都有两个基本的操作和。得分评卷 人三、 简答题(共5道小题, 其中1-4题每题5分, 第5题10分, 共30分)1.已知n阶下三角矩阵A(即当1ijn时, 有aij0;当1jin时, aij0), 按照压缩存储的思想, 能够将其主对角线以下所有元素(包括主对角线)从第一列开始采用列序为主序依次存放于一维数组B1.中。请写出下三角任意元素aij(ji)在B中的下标k的值的计算公式。( 5分) 2.假设字符 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分) 4已知一个无向图的邻接表如下图所示, 要求: (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分) 得分评卷人四、 阅读算法并填空( 10分) 如下是一个折半查找算法, 请在画线处填上适当内容, 将算法补充完整。/查找表存储结构表示typedefstructElemType*elem;intlength;Table;/数据元素存储空间基址/表长度intSearch(TableST,KeyTypekey)/设有序表ST中元素按关键字降序排列, 要求在其中查找其关键字等于key的数据元/素, 找到则返回该元素在表中的位置, 否则返回0。low=1;whilemid=(low+high)/2;ifEQ(key,ST.elemmid.key) returnmid;elseifLT(key,ST.elemmid.key); else;/Search 得分评卷人五、 用类C语言描述下列算法, 并给出必要说明。( 每题10分, 共20分) 1、 已知带表头结点的单链表L, 在该单链表中第i个结点处插入新元素X。已知线性表的单链表存储结构如下: typedef struct Lnode elemtype data;Lnode * next;Lnode,*LinkList; 2、 设二叉树采用二叉链表存储结构, 试设计一个算法计算一棵给定二叉树的所有叶子结点的数目。/二叉树的存储表示typedef struct BiTNodeElemType data;Stuct BiTNode * lchild,*rchild;/左右指针标志BiTNode,*BiTree