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