数据结构模拟试卷数据结模拟试卷.doc

总分 一 二 三 四 五 六 七 ┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄ 学　院 班　级 学　号 姓　名 ……………○……………密……………○……………封……………○…………线……………………………… 得分 三、应用题（每小题6分，共30分） 1．设一颗二叉树的先序、中序遍历序列分别为：先序遍历序列：ABDFCEGH， 中序遍历序列：BFDAGEHC。1) 写出其后序遍历序列； 2) 并画出它的后序线索二叉树。 2．设一哈希表长为19，采用线性探测法解决冲突，哈希函数H(key)=key%13, （1）画出在空表中依次插入关键字19，01，23，14，55，20，84，27，68,11,10,77后的哈希表。 （2）求在等概率情况下，查找成功的平均查找长度。 得分 一、单选题（每小题2分，共20分） （ A）1．若线性表中最常用的操作是取第i个元素和找第i个元素的前驱元素，采用哪种存储方式最节省时间 A.顺序表 B.单链表 C.双链表 D.单循环链表 （ B ）2．设一个顺序栈S，设将数字1,2,3,4，5，6依次进栈、出栈顺序是2，3，4，6，5，1，则栈的容量至少应该是 A.2 B.3 C.5 D.6 （D ）3．线性表中若采用链表存储结构，要求内存中可用存储单元的地址是 A. 必须是连续的 B.部分必须是连续的 C. 一定不是连续的 D.连续不连续都可以 （ C）4．从广义表LS＝（（a,b,c）,(d,e,f） (tail (LS)) B.tail (head (LS)) C.head (tail(head(tail(LS)))) D. head (tail(tail(head(LS)))) （ A ）5．字符串‘ababaabab’的 得分 四、设计题（本题10分） 设指针la和lb分别指向两个不带头结点的单链表的首节点，设计从表la中删除第i个元素起共len个元素，并将这些元素插入到lb中第j个节点之前。 } 得分 二、填空题（每小题2分，共20分） 在一个带头结点的单循环链表中， p指向尾节点的直接前驱，则指向头结点的指针head可以用p表示为head=（ ）。 设Q[0..N-1]为循环队列，其头尾指针分别为F和R，则队列Q中当前所含元素的个数为（ ）。 有一个10阶对称矩阵采用压缩存储方式（行序为主序）存储其下三角元素，每一个元素占一个存储单元，第一个元素A[1,1]的存储地址为1，A[4,5]的存储地