数据结构考试样题(天津科技大学)

数据结构考试样题一、填空题（每小题2分，共２０分）1.数据的逻辑结构包括集合结构、线性结构、。2.对算法从时间和空间两方面进行度量，分别称为分析。3.不带有头结点的单链表head为空的条件是。4.对于栈只能在插入和删除元素。5.深度为k的二叉树最多有个结点。6.空格串是。7.Hash技术关键是两个方面。8.快速排序的平均时间复杂度为。9.HEAD(TAIL(((a,(b,c))))=。10.已知一个图的邻接矩阵表示，计算第i个结点的入度的方法是。二、单项选择题（每小题2分，共２０分）１．以下哪一个不是队列的基本运算（）？（A）从队尾插入一个新元素（B）从队列中删除第i个元素（C）判断一个队列是否为空（D）读取队头元素的值2．若进栈序列为１,２,３,４,假定进栈和出栈可以穿插进行，则可能的出栈序列是（）。（A）２，４，１，３（B）３，１，４，２（C）３，４，１，２（D）１，２，３，４3．有64个结点的完全二叉树的深度为（）（根的层次为1）。（A）8（B）7（C）6（D）54．串是一种特殊的线性表，其特殊性体现在（）。（A）可以顺序存储（B）数据元素是一个字符（C）可以链接存储（D）数据元素可以是多个字符5．链表不具有的优点是（）。（A）可随机访问任一元素（B）插入删除不需要移动元素（C）不必事先估计存储空间（D）所需空间与线性表长度成正比6．对有18个元素的有序表作二分查找，则查找A[3]的比较序列的下标依次为()。(A)1，2，3(B)9，5，2，3(C)9，5，3(D)9，4，2，37．对矩阵压缩存储是为了()。(A)方便运算(B)节省存储空间(C)方便存储(D)提高运算速度8．快速排序属于（）。(A)插入排序(B)交换排序(C)归并排序(D)选择排序9．设矩阵A{1..n,1..n]是一个对称矩阵，为了节省存储，只将其下三角部分按行序存放在一维数组B[1..n(n-1)/2]中，对下三角部分中任一元素aij(i=j),在一维数组B的下标位置k的值()。(A)i(i-1)/2+j-1(B)i(i-1)/2+j(C)i(i+1)/2+j-1(D)i(i+1)/2+j10．某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）二叉树。(A)空或只有一个结点(B)高度等于其结点数(C)任一结点无左孩子(D)任一结点无右孩子三、简答题（共40分）1.对下列数据表，写出采用二路归并算法排序的每一趟的结果。（7分）(50,12,20,31,44,66,61,80,30,75)2.已知某二叉树按后序遍历序列为CEDBHJIGFA，按中序遍历序列为CBEDAHGIJF,试画出该二叉树形状（要求写出中间过程），并写出它的先序遍历序列。（9分）3．已知一组元素为(37,70,29,46,25,78,62,12)，画出按元素排列输入生成的一棵二叉排序树，并求其在等概率情况下查找成功的平均查找长度（要求写出每插入一个元素时二叉排序树形状）。（8分）4.设a,b,c,d,e,f六个字母出现的次数分别为7,19,2,6,32,3,试为这六个字母设计huffman编码并画出对应huffman树。（8分）5．画出下列无向图的邻接表存储结构，并由邻接表写出由E出发的广度优先搜索序列和深度优先搜索序列。（8分）A|B---C---DE四、设计或分析题(共20分)１．设单链表具有头结点，且表中元素各不相同，试给出在单链表中删除值为x的结点的算法。（10分）2．设一棵二叉树以二叉链表存储，试设计算法求此二叉树的深度。（10分）StatusDelete_Between(Linklist&L,elemtypex)//删除元素{p=L;while(p-next&&p-next-data!=x)p=p-next;if(p-next)/{q=p-next;p-.next=q-next;}}//Delete_BetweenintGet_Depth(BitreeT)//求子树深度的递归算法{if(!T)return0;else{m=Get_Depth(T-lchild);n=Get_Depth(T-rchild);return(mn?m:n)+1;}}//Get_Depth