资源描述：
《专升本数据结构试题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、专升木《数据结构》试卷一、填空题：（每小题2分，共10分）1.设有数据结构（D,R）,其中D是数据元素的有限集，R是一的有限集。2.深度为k的二叉树其结点数至多有一个。3.栈是一种特殊的线性表，它允许在表的一端进行—操作。4.通常象交通、道路问题的数学模型是一种称为的数据结构。5.哈希表是一种查找表，nJ以根据哈希函数直接获得二、单项选择题：（每小题2分，共10分）对于下列各题，在备选答案中选出一个正确的，并将具编号填在“”位置上。1•若线性表最常用的操作是存取第i个元素及其前驱元素的值，则采用—存储方式最节省运算时间。A.单链表B.双链表C.单循环链表D.顺序表
2、2.下列排序算法中，_算法在进行一趟相应的排序处理结束后不一定能选出一个元素放到其最终位置上。。A.直选择排序B.冒泡排序C.归并排序D.堆排序3.队列的操作原则是A.先进后出B.先进先出C.只能进行插入D.只能进行删除4.在具有n个结点的二义链表中，非空的链域个数为A.n~lB.nC.n+lD.不确定5.对具有n个元素的有序查找表采用折半杳找算法杳找一个键值，其最坏比较次数的数量级为A.0（log2n）B.0（n）C.O（nlog2n）D.O（n2）三、判断题：（每小题2分，共10分）判断下列各题是否正确，若正确，在题后的括号内填“T”,否则填“F”o1.在栈为
3、空的情况下不能作出栈处理，否则，将产生下溢出。（）2.如果有向图G=（V,E）的拓扑序列唯一，则图屮必定仅有一个顶点的入度为0、一•个顶点的出度为0。（）3.在大根堆中，必定满足每个结点的键值大于其左右了树中所有结点的键值。（）4.在采用线性探测法处理冲突的散列表屮所有同义词在表屮相邻。（）5.在索引顺序表屮，对索引表既可采用顺序查找，也可采用二分杳找。（）四、解答下列各题：（每题10分，共40分）1.已知线性表L采用帯头结点的的单向循环链表表示,试给出它的存储结构类型描述及相应的示意图。。2.已知-•棵二义树的先序、屮序和后序序列如下所示，请填写各序列屮空格处的
4、结点，并画出该二义树的二义链表存储结构示意图。先序序列是：_B_F_ICEH_G；中序序列是：D_KF【A_EJC_；后序序列是：_k_fbhj_g_a3.已知数据表为（48,70,33,65,24,56,12,92,86,22）,a）写出采用快速排序算法进行排序时第一趟快速划分的详细过程及结果；b）写出按基数排序思想对最低位进行一次分配和收集的结果。4.对图1所示的带权无向图，写出它的邻接矩阵和深度优先捜索序列，并按克鲁斯卡算法求其最小生成树（写出求解的详细过程示意图）。五、算法设计题：（前两题必做，每题15分，共30分；第三题为附加题，选做，10分）1.已知队
5、列Q以循环队列存储。写出Q的存储结构类型描述，并试编写算法实现将元索x插入队列Q的入队操作EnQueue(Q,x)和从队列Q中获取队首元素的函数GetTop(Q)。2.假设线性表L二@1,边,……,an)用带头结点的单链表存储表示,试编写算法对其实现就地逆置，即利用原链表中每一个结点存储空间，使得元素的逻辑次序改变为(an,……，a2,al)o3.设非空二叉树T采用中序线索二叉链表表示，写出T的存储结构类型描述。试编写算法InOrderTraverse(T)实现对二叉树T的中序遍历。山东：07年专升本考试数据结构模拟试题2一、单项选择题：(每小题2分，共10分)对
6、于下列各题，在备选答案中选出一个正确的，并将其编号填在“”位置上。1.折半查找法耍求查找表中各元素的键值必须是一A.递增或递减B.递增C.递减0.无序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用
7、邻接表存储，则求每个顶点入度的算法时间复杂度为A.0(n)B.0(n+e)C.0(n*n)D・0(n*e)二、判断题：(每小题2分，共10分)判断下列各题是否正确，若正确，在题后的括号内填“T”，否则填“F”o1.在队满情况下不能作入队处理，否则，将产生“上溢”。()2.基于插入思想的排序算法都是稳定的。()3.一个有向图的邻接表和逆邻接表屮的结点个数不一定相等。()4.若一棵二叉树的任一非叶了结点度为2,则该二叉树为满二叉树。()5.广义表是线性表的推广，因此也可以采用顺序方式进行存储。()三、填空题：(每小题2分，共10分)1.在单链表中，删除指针P所指结点的
8、后继结点的
