2012-2019年三峡大学836数据结构真题合辑

第2第2页三峡大学2012年研究生入学考试试题（A卷）科目代码：型匕科目名称：数据结构（考生必须将答案写在答题纸上，总分150分，考试时间180分钟）一、选择题（每小题2分，共40分）1、线性表采用链式存储时，结点的存储地址（）。必须是不连续的B.连续与否均可C.必须是连续的D.和头结点的存储地址相连续2、已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行（）操作。A.s—>next二p—>next;p—>next二sB.q—>next二s;s—>next二pC.p—>next二s->next;s—>next二pD.p—>next二s;s—>next二q3、设有一个顺序栈S,元素按S1,S2,S3,S4,S5,S6顺序进栈，若6个元素的出栈顺序为S2,S3,S4,S6,S5,S1,则顺序栈的容量至少应为（）。A.2B.3C.4D.54、如下陈述中正确的是（）。A.串是一种特殊的线性表B.串的长度必须大于零C.串中兀素只能是字母D.空串就是空白串5、设有一个二维数A[m][n]，假设A[0][0]存放位置在544,A[5][5]存放位置在624，每个元素占一个空间，A[2][2]在（）位置。A.592B.586C.576D.6086、设有5个字符出现的频度分别为1,2,3,5,4,则对应的哈夫曼树的带权路径TOC\o"1-5"\h\z长度为（）。A.34B.33C.35D.157、含n个顶点和e条边的无向图的邻接矩阵中非零元素的个数为（）。A.eB.2eC.n2—eD.n2—2e第页三峡大学2017年硕士研究生入学考试试题（A卷）科目代码：936科目名称：数据结构考试时间为3小时，卷面总分为150分答案必须写在答题纸上一单选题（每小题5分，共60分）1数据在计算机存储器内表示时，物理地址与逻辑地址没有关联的，为—。A.存储结构B.逻辑结构C.链式存储结构D.顺序存储结构在一个长度为n的顺序表中删除第i个元素（1<=i<=n）时，需向前移动个A.n-iB.n-i+lC.n-i-1D.i在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行—s—>next二p—>next;p—>next二sq—>next二s;s—>next二pp—>next二s->next;s—>next二pp—>next二s;s—>next二q线性表的顺序存储结构是一种的存储结构。A.随机存取B.顺序存取C.索引存取D.散列存取在等概率情况下，顺序表的插入操作要移动结点。A.全部B.—半C.三分之一D.四分之一TOC\o"1-5"\h\z向一个栈顶指针为hs的链栈中插入一个s结点时，应执行。hs->next二s;s->next二hs;hs=s;s->next二hs->next;hs->next二s;s->next二hs;hs=hs->next;在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为。A.front二front->nextB.rear二rear—>nextC.rear二front->nextD.front二rear—>next若m行n列二维数组A,其元素记为A[i][j],i=0,l,-・m-l,j=0,l,-・n-l,按列优先顺序存储，则A[i][j]地址为。A.LOC(A[O][O])+[j*m+i]B.LOC(A[O][O])+[j*n+i]C.LOC(A[O][O])+[(j-1)*n+i-1]D.LOC(A[O][O])+[(j-l)*m+i-l]对于长度为9的顺序存储的有序表，若采用折半查找，在等概率情况下的平均查找长度为—的9分之一。TOC\o"1-5"\h\zA.20B.18C.25D.22对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元素26的比较次数为_。A.2B.3C.4D.5在索引查找中，若用于保存数据元素的主表的长度为144,它被均分为12子表，每个子表的长度均为12,则索引查找的平均查找长度为。A.13B.24C.144D.79若一个元素序列基本有序，则选用_方法较快。A.直接插入排序B.简单选择排序C.堆排序D.快速排序二填空题（每小题5分，共30分）从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较个元素结点。在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是。若对n阶对称矩阵A,其元素计为A[i][j],i,j=0,2,・・・n-l,以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组B中，B的元素为B[i],i=O,l,…，n（n+l）/2-l,则下三角中的A[i][j]）元素对应B中位置元素。在一个具有n个顶点的有向完全图中，所含的边数为。从具有n个结点的二叉排序树中查找一个元素时，在最坏情况下的时间复杂度为。在对n个元素进行冒泡排序的过程中，至少需要趟完成。三应用题（每题10分，共60分）1•计算下面程序段的时间复杂度：i=1;while（i<=n）i=i*3;对于线性表的两种存储结构（顺序表和链表），若线性表的总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，应选用何种存储结构？试说明理由。什么是队列的上溢现象？一般有几种解决方法，试简述之。4分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。5在一棵度为M树