2015年三峡大学838数据结构考研真题硕士研究生入学考试试题

第1页共 3 页 三 峡 大 学 2015年研究生入学考试试题(B卷) 科目代码： 838 科目名称： 数据结构 考试时间为3小时，卷面总分为150分 答案必须写在答题纸上 （本套试题出现的代码采用C语言规定） 一、 单选题 （每题2分，共30分） 1. 某线性表中最常用的操作是存取第i个元素及其前驱的值，采用（ ）存储方式最省时间。 A. 顺序表 B. 带头结点的单向链表 C. 带头结点的双向循环链表 D. 带尾指针的单向循环链表 2. 下列选项中，（ ）是链表不具有的特点。 A. 插入和删除运算不需要移动元素 B.所需存储空间与线性表的长度成正比 C. 不必事先估计存储空间大小 D.可以随机访问表中任意元素 3. 设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S,如果每个元素出栈后立即进入队列Q,且7个元素出队的顺序为b,d,c,f,e,a,g,则栈S的容量至少是（ ） A. 2 B. 3 C. 5 D.7 4. 设队列中有A,B,C,D,E这5个元素，其中队首元素为A.如果对这个队列重复执行下列操作：1）输出队首元素；2）把队首元素插入到队尾；3）删除队首元素；4）再次删除队首元素。前述操作直到队空为止，则可能得到输出序列（ ） A. ACECC B. ACE C. ACECCC D. ACEC 5. 下列排序算法中，（ ）算法可能会出现下面的情况，即当初始数据有序时，花费时间反而最多。 A. 堆排序 B. 冒泡排序 C.快速排序 D.希尔排序 6. 在关键字随机分布的前提下，用平衡的二叉排序树进行查找，其平均查找长度同（ ）数量级相当。 A. 顺序查找 B. 二分查找 C. 快速查找 D. 都不正确 7. 对于一个有向图，若一个顶点的度为k1, 出度为k2, 则对应的邻接表中，该结点单链表的边结点数目为（ ） A. k1 B. k2 C. k1-k2 D.k1+k2 第 2 页 8. 已知一个有向图G具有n个顶点和e条弧，用邻接表来存储表示需要（ ）个弧结点。 A. n B. n2 C. e D. 2e 9. 已知哈希表的长度m=10, 哈希函数H(key)=key%7,关键字为k的记录在定址时产生了冲突，若采用开放地址法（也称再散列法）解决冲突，则新地址的计算公式为（ ） A.(H(k)+di)/10 B.(H(k)+di)/7 C. (H(k)+di) D. (H(k)+di)%7 10. 已知一个带头结点的非空循环单链表，其尾指针是R,则其首元素结点的地址为（ ） A. R->next B. *(R->next->next) C. &(R->next->next) D. R->next->next 11. 下列关键字序列，不可能构成某二叉排序树的查找路径的序列是（ ） A. 95,22,91,24,94,71 B.92,20,91,34,88,35 C. 21,89,77,29,36,38 D. 12,25,71,68,33,34 12. 若7个顶点的无向图是连通的，则其边数至少是（ ） A.6 B.7 C. 8 D.14 13. 已知一个完全二叉树的第6层（树根为第1层）有8个叶子结点，则该树的结点个数最多为（ ） A.39 B.52 C.111 D.119 14． 快速排序在下列( )情况下最容易发挥其长处。 A. 被排序的数据中含有多个排序码 B. 被排序数据已基本有序 C. 被排序数据完全无序 D. 被排序数据的最大值和最小值相差悬殊 15. 对n个不同的元素进行冒泡排序，在下列（ ）情况下换位次数最多。 A. 元素从小到大排列好 B. 元素从大到小排列好 C. 元素无序 D. 元素基本有序 二、填空题 （每空2分，共30分） 1.在n个元素的顺序表中删除一个元素，需要平均移动（ ）次。 2.循环单链表以list为头指针，结点的指针域next,指针p所指结点为表尾结点的条件是（ ）。 3．一个长度为N的数组空间存放循环队列，头尾指示器分别为front和rear,则该队列元素个数为（ ）。 4．广义表（（a,b），（a,(b)））的深度是（ ）。 5. 如果结点A有3个兄弟，B是A的双亲，则B的度是（ ）。 6. 有一个图的邻接矩阵按行依次是[[0,1,1,1], [1,0,1,0], [1,1,0,1], [1,0,1,0]]，图中有（ ）条边，度最大的的顶点的度是（ ）。 7. 在一组记录（54,38,96,23,15,72,60,45,83）进行插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较（ ）次 第3 页 8. 对于n个记录的集合进行冒泡排序，在最坏情况下所需时间是（ ），若对其进行快速排序，在最坏情况下所需时间是( ) 9. 假设用循环单链表实现队列，结点指针域为next, 若队列非空，且尾指针为R,则将新结点S加入队列时，需执行三条语句（ ）；（ ）；R=S;. 10. n个顶点的连通无向图至少有（ ）条边，最多有（ ）条边 11. 在程序段： for(i=1;i<=n;i++) for (j=i+1;j<=n;j++)x++; 中，x++执行了（ ）次。 三、 计算题（每题10分，共50分） 1. 假设有6行8列的二维数组A(下标从0开始),每个元素占6个字节，存储器按字节编址。已知A的首地址为1000,计算：1)数组A共占用多少字节。（2分）2）数组A的最后一个元素地址（3分）3）按行存储时A[3][6]的地址（2分）按列存储时A[3][6]的地址(3分)。 2. 已知一棵度为k的树中n1个度为1的结点，n2个度为2的结点，…，nk个度为k的结点，则该树中有多少个叶子结点(5分)并证明之（5分）。 3.二叉树的先根次序访问序列为GFKDAIEBCHJ，中根次序访问序列为DIAEKFCJHBG，画出这个树（10分）。 4. 对图一，从顶点0开始访问，给出深度优先和广度优先搜索结果（各5分）。 012435图 1 6785. 给定关键字序列（8,3,25,19,12,30,47,34），按次序插入建立一个二叉排序树，画出这个树（10分）。 四、 程序题（每题20分，共40分） 1已知一个带有表头结点的单链表，结点结构为{data, link}。假设链表中只给出了头指针list.在不改变链表的前提下，设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法获得该结点的data的值，并返回1；否则返回回0.采用C语言实现函数int search(RecordType *list, int k，DataType *d)。（不得使用额外大内存） 2 已知二叉树的数据为正整数，按顺序方式存储与数组A中，对比完全二叉树缺失结点的地方存0.编写C语言函数int Count（int A[]）计算二叉树中非叶子结点的数目。