山东：11年专升本考试数据结构模拟试题2一、单项选择题：（每小题2分，共10分）对于下列各题，在备选答案中选出一个正确的，并将其编号填在“”位置上。1.折半查找法要求查找表中各元素的键值必须是。A.递增或递减B.递增C.递减D.无序2.若对某线性表最常进行的操作是在最后一个元素之后插入和删除第一个元素，则采用存储方式最节省运算时间。A.单链表B.双链表C.仅有头指针的单循环链表D.仅有尾指针的单循环链表3.有64个结点的完全二叉树的深度为（假设根结点的层次为1）。A.8B.7C.6D.54.对于键值序列（2，33，21，18，65，38，7，49，24，86），用筛选法建堆，必须从键值为的结点开始。A.86B.2C.65D.385.设图G用邻接表存储，则求每个顶点入度的算法时间复杂度为。A.O(n)B.O(n+e)C.O(n*n)D.O(n*e)二、判断题：（每小题2分，共10分）判断下列各题是否正确，若正确，在题后的括号内填“T”，否则填“F”。1.在队满情况下不能作入队处理，否则，将产生“上溢”。（）2.基于插入思想的排序算法都是稳定的。（）3.一个有向图的邻接表和逆邻接表中的结点个数不一定相等。（）4.若一棵二叉树的任一非叶子结点度为2，则该二叉树为满二叉树。（）5.广义表是线性表的推广，因此也可以采用顺序方式进行存储。（）三、填空题：（每小题2分，共10分）1.在单链表中，删除指针P所指结点的后继结点的语句是：。2.有向图G用邻接矩阵A[1..n，1..n]存储表示，其第i行的所有元素之和等于顶点i的。3.基数排序算法的时间复杂度为。4.平衡二叉树中每个结点的平衡因子定义为。5.利用直接插入排序算法对有n个元素的数据表进行排序，在最坏情况下，元素的移动次为。四、解答下列各题：（每小题10分，共40分）1.写出采用顺序方式存储的栈的类型描述及相应的入栈、出栈操作的示意图。2.已知数据表为（60，20，31，5，44，55，61，30，80，150，4，29），写出采用希尔排序算法进行排序的详细过程和结果（假设增量序列dlta[]={6,3,1}）。3.已知图G的邻接表存储结构示意图如下所示，画出它的逻辑关系示意图，以及按深度优先搜索和广度优先搜索进行遍历所得到的顶点序列。4.设散列函数为H(K)=Kmod5，散列表的地址空间为0..6，初始时散列表为空，用线性探测法解决冲突，请写出依次插入23，14，9，6，30，12，18时散列地址的计算过程及结果，以及最后得到的散列表。五、算法设计题：（前两题必做，每题15分，共30分；第三题为附加题，选做，10分）1.设计算法将一个带头结点的单循环链表A分解为两个具有相同结构的链表B、C，其中：B表中的结点为A表中元素的顺序号为奇数的结点，而C表中的结点为A表中元素的顺序号为偶数的结点。（要求利用原表结点。）2.已知S为顺序栈。写出S的存储结构类型描述。试编写算法实现将元素x插入栈S的入栈操作Push(S,x)和删除栈顶元素的出栈操作Pop(S)。3.已知一棵完全二叉树存于顺序表sa中，sa.elem[1..sa.last]包含各结点值。试编写算法根据此顺序存储结构建立该二叉树的二叉链表T。