1、第1页共 4 页三 峡 大 学2017年硕士研究生入学考试试题(A卷)科目代码： 936 科目名称： 数据结构 考试时间为3小时，卷面总分为 150 分答案必须写在答题纸上一 单选题（每小题5分，共60分）1数据在计算机存储器内表示时，物理地址与逻辑地址没有关联的，为 。A.存储结构B.逻辑结构 C.链式存储结构D.顺序存储结构2. 在一个长度为n的顺序表中删除第i个元素(1=inext=p-next; p-next=sBq-next=s; s-next=pCp-next=s-next; s-next=pDp-next=s; s-next=q4. 线性表的顺序存储结构是一种_的存储结构。 A随
2、机存取B顺序存取C索引存取D散列存取5. 在等概率情况下，顺序表的插入操作要移动_结点。 A全部 B一半 C三分之一 D四分之一第 2 页6. 向一个栈顶指针为hs的链栈中插入一个s结点时，应执行_。 Ahs-next=s; Bs-next=hs; hs=s;Cs-next=hs-next;hs-next=s; Ds-next=hs; hs=hs-next;7. 在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为_。Afront=front-next Brear=rear-nextCrear=front-next Dfront=rear-next8. 若m行n
3、列二维数组A， 其元素记为Aij, i=0,1,m-1,j=0,1,n-1, 按列优先顺序存储，则Aij地址为 。A.LOC(A00)+j*m+i B. LOC(A00)+j*n+iC.LOC(A00)+(j-1)*n+i-1 D. LOC(A00)+(j-1)*m+i-19. 对于长度为9的顺序存储的有序表，若采用折半查找，在等概率情况下的平均查找长度为 的9分之一。A. 20 B. 18 C. 25 D. 2210. 对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元素26的比较次数为 。A. 2 B. 3 C. 4 D. 511. 在索引
4、查找中，若用于保存数据元素的主表的长度为144，它被均分为12子表，每个子表的长度均为12，则索引查找的平均查找长度为 。A. 13 B. 24 C. 144 D. 7912. 若一个元素序列基本有序，则选用 方法较快。A. 直接插入排序 B. 简单选择排序C. 堆排序 D. 快速排序第 3 页二 填空题 （每小题5分，共30分）1. 从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较_个元素结点。 2. 在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是_。 3. 若对n阶对称矩阵A, 其元素计为Aij, i,j=0,2,n-1, 以行
5、序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组B中，B的元素为Bi, i=0,1, n(n+1)/2-1, 则下三角中的A ij )元素对应B中_位置元素。4. 在一个具有n个顶点的有向完全图中，所含的边数为_。5. 从具有n个结点的二叉排序树中查找一个元素时，在最坏情况下的时间复杂度为_。6. 在对n个元素进行冒泡排序的过程中，至少需要_趟完成。三 应用题 (每题10分，共60分)1. 计算下面程序段的时间复杂度：i=1;while(i=n)i=i*3;2. 对于线性表的两种存储结构（顺序表和链表），若线性表的总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，应选用何种存储结构？试说明理由。3. 什么是队列的上溢现象？一般有几种解决方法，试简述之。第 4 页4分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。5在一棵度为M树中，度为1的结点数为N1，度为2的结点数为N2，度为M的结点数为NM，则该数中含有多少个叶子结点？给出计算过程。6. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用冒泡排序法进行排序时每一趟的排序结果。
