1、第1页 共 5页三 峡 大 学2015年研究生入学考试试题(B卷)科目代码： 938 科目名称： 数据结构 考试时间为3小时，卷面总分为150分答案必须写在答题纸上一、选择题 (每小题 2分，共 40 分)1、线性表采用链式存储时，结点的存储地址（ ）。A. 必须是不连续的 B. 连续与否均可C. 必须是连续的 D. 和头结点的存储地址相连续2、已知指针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
2、. p-next=s; s-next=q3、设有一个顺序栈S, 元素按S1, S2, S3, S4, S5, S6顺序进栈，若6个元素的出栈顺序为S2, S3, S4, S6, S5, S1, 则顺序栈的容量至少应为（ ）。A. 2 B. 3 C. 4 D. 54、设有两个串p和q，求q在p中首次出现的位置的运算称作（ ）。A.连接 B.模式匹配 C.求子串 D.求串长5、设有一个二维数Amn，假设A00存放位置在544，A55存放位置在624，每个元素占一个空间，A22在（ ）位置。A. 592 B. 586 C. 576 D. 6086、设有5个字符出现的频度分别为2,7,5,4，则对应的
3、哈夫曼树的带权路径长度为（ ）。A. 34 B. 33 C. 35 D. 157、 含n个顶点和e条边的无向图的邻接矩阵中非零元素的个数为（ ）。A. e B. 2e C. n2-e D. n2-2e第 2 页8、 长度为500的有序表采用折半查找时，查找成功最大比较次数为（ ）。A. 8 B. 9 C. 10 D. 119、快速排序在下列哪种情况下最易发挥其长处（ ）。A. 被排序的数据中含有多个相同排序码 B. 被排序的数据已基本有序C. 被排序的数据完全无序 D. 被排序的数据中的最大值和最小值相差悬殊10、下列关键字序列中，（ ）是堆。A. 16, 72, 31, 23, 94, 53
4、 B. 94, 23, 31, 72, 16, 53 C. 16, 53, 23, 94，31, 72 D. 16, 23, 53, 31, 94, 7211、 若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1, p2, p3, , pn,若p1=n，则pi为（ ）。A. i B. n = i C. n-i+1 D. 不确定12、一棵具有257个结点的完全二叉树，它的深度为（ ）。A. 7 B. 8 C. 9 D. 1013、在一个图中，所有顶点的度数之和等于图的边数的多少倍（ ）。A. 1/2 B. 1 C. 2 D. 4 14、用邻接表表示图进行广度优先遍历时，通常是采用（ ）这种
5、数据结构 来实现算法的。A. 栈 B. 队列 C. 树 D. 图 15、深度优先遍历类似于二叉树的（ ）。A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历16、有8个结点的无向图最多有（ ）条边。A. 14 B. 28 C. 56 D. 11217、折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中哪些元素比较大小，查找结果是失败。（ ）A. 20，70，30，50 B. 30，88，70，50 C. 20，50 D. 30，88，50第 3 页18、任何一个无向连通图的最小生成树（ ）。A. 只有一棵 B. 一棵或多
6、棵 C. 一定有多棵 D. 可能不存在19、链表适用于哪种查找（ ）。A. 顺序 B. 二分法 C. 顺序，也能二分法 D. 随机20、把一棵树转换为二叉树后，这棵二叉树具有什么样的形态特征（ ）。A. 是唯一的 B. 有多种C. 有多种，但根结点都没有左孩子 D. 有多种，但根结点都没有右孩子二、填空题(每小题 2 分，共 30分)1、对于一个表长为n的顺序表，在表头插入元素的时间复杂度为 ，在表尾插入元素的时间复杂度为 。（要求用大O表示法表示）2、神枪手依次压入10颗子弹进入枪膛，编号分别为1-10，则消灭第4个敌人的子弹编号是 。3、一棵深度为6的满二叉树有 个分支结点和 个叶子结点。
7、4、 是被限定为只能在表的一端进行插入和删除运算的线性表。5、已知某二叉树的中序遍历结果是：DEBAC，后序遍历结果是：EDBCA，则该树的先序遍历序列是 。6、设数组a160, 170的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a32,58的存储地址为 。7、如果一棵完全二叉树具有1000个结点，则此完全二叉树有 个叶子结点，有 个度为2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。8、由3个结点所构成的二叉树有 种形态。9、写出下列程序段的时间复杂度，要求用大O表示法表示。s=0; i=1; for i=0; in; i+) while(i=n)
8、for(j=0; jn; j+) i=i*3; s+=Bij;sum=s;答： 答： 第 4 页三、综合题(共60分)1、试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？(10分)2、说明线性表、栈与队的异同点。（10分）3、根据下图回答问题。（20分）(1) 要完成该AOE网中工程，最短时间是多少？（不考虑单位）（5分）(2) 上图中的关键路径是什么（用顶点序列表示）？将活动a10的时间改成2 可否提前完成？（5分）(3) 若忽略边的权值将上图看成一个AOV网，并约定当存在多个入度为0的结点时先输出编号较小的结点，则请写出拓扑排序结果。 （5分）(4) 若忽略边的方向
9、性将上图看成无向网，各边权值为经济代价，请给出该无向网的一棵最小生成树。（5分）4、已知待排序关键字序列是38，19，50，61，32，23，11，14，15请回答下列排序问题(要求排成升序序列)：（10分）(1) 若采用直接插入排序，第一个位置前移的元素关键字是？(3分)(2) 若采用直接选择排序，第一个位置前移的元素关键字是？(3分) (3) 若采用快速排序，第一个位置前移的元素关键字是？(2分)(4) 若采用堆排序，利用筛选操作建堆过程中最先交换的两个元素关键字是？(2分)5、已知数据序列为： 2，0，3，5，8，7，4，6，2 在一个初始值为空的二叉排序树中依次插入这些结点，请画出该二
10、叉排序树的最终形态。（10分）第 5 页四、阅读程序，回答问题。（每小题 10分，共 20 分）（1） void proc_1(Stack S, int e)Stack T; int d;InitStack(&T);While(!EmptyStack(S) Pop(&S, &d); if (d!=e) Push( &T, d);While(!EmptyStack(T) Pop(&T, &d); Push( &S, d);简述proc_1的功能。（10分）（2） void proc_2(Queue *Q)Stack S; int d;InitStack(&S);While(!EmptyQueue(* Q) DeleteQueue(Q, &d); Push( &S, d);While(!EmptyStack(S) Pop(&S, &d); EnterQueue( Q, d);简述proc_2的功能。（10分）
