2015暨南大学考研数据结构真题

需要暨南大学考研数据结构历年真题+参考答案+复习资料，请加QQ: 15级师兄2015年全国硕士研究生统一入学考试自命题试题（B卷）k! k! k! k! k! k! k! k! k! k! k! k! k! k! k! k! k1k1k1k1k1z #T#T#T#TTT7 T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T TW #T #T #T 学科、专业名称：计算机科学与技术、软件工程 研究方向：计算机系统结构，计算机软件与理论，计算机应用技术，软件工程，计算机技术 （专业学位） ，软件工程（专业学位）考试科目名称及代码：数据结构830考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。一单项选择题每题2分，共30分）1线性表采用链式存储时，其地址（）。A.必须是连续的B.部分地址必须是连续的C.定是不连续的D.连续与否均可以2若有一个栈的输入序列是1, 2, 3,，n,输出序列的第一个元素是n,则第i个输出元素 是（）。A. n-i B. n-i-1 C. n-i+1 D.不确定3. 已知单链表上一结点的指针为P,则删除该结点后继的正确操作语句是（）。A. s= p-next; p=p-nextfree（s）;B. p=p-next; free（p）;C. s= p-next; p-next=s-nexfree（s）;D. p=p-next; free（p-next）;4. 若使用邻接矩阵表示某有向图，则矩阵中非零元素的个数等于（）。A.图中顶点的数目B.图中边的数目C.图中边的数目的两倍D.无法确定5. 下列哪种排序需要的附加存储开销最大（）。A.快速排序 B.堆排序C归并排序D.插入排序6. 下面哪一方法可以判断出一个有向图是否有环（即回路）（）。A.拓扑排序 B.求最短路径C.求最小生成树D.广度优先遍历7. 具有n个顶点的无向图至少应有（）条边才能确保是一个连通图.A. n-1B. nC. n+1D. 2n&对线性表进行折半查找时，要求线性表必须（）。A.以顺序方式存储B.以顺序方式存储，且结点按关键字有序排序C.以链接方式存储D.以链接方式存储，且结点按关键字有序排序9. 若使用二叉链表作为树的存储结构，在有n个结点的二叉链表中非空的链域的个数为（）。A. n-1B. 2nTC. n+1D. 2n+110. 在内部排序中，排序时不稳定的有（）。A.插入排序 B.冒泡排序 C快速排序D归并排序11. 个具有500个结点的完全二叉树具有一个孩子的结点个数最多为（）。A. 1B. 250C. 0D. 24912. 从未排序序列中取出一个元素，并将其依次插入已排序序列的方法，称为（）。D.选择排序）遍历方法。D.层次D.只能进行删除e为图的边数目，建立图的算A.希尔排序B归并排序C.插入排序13. 如果希望对二叉排序树遍历的结果是升序的，应采用（A.先序B.中序C.后序14队列操作的原则是（）A.先进先出B.后进先出C.只能进行插入 15.在用邻接表表示有向图的情况下，假设n为图的顶点数目,法的时间复杂度为()。A. O(n+e)B. 0(e)C. O(nxe)D. 0(n3)二填空题每空2分，共20分）1 .循环链表的主要优点是。2. 根据数据元素之间关系的不同特性，基本逻辑结构分为线性结构、树形结构和四种。3对一棵完全二叉树中按照从上到下、从左到右的顺序从1开始顺序编号，则编号为11双 亲结点的编号为，编号为10的结点的左孩子结点（若存在）的编号为。4下面程序段的时间复杂度是。S=0;for（ i=0;iN; i+）for（j=0; j2N+1; j+）S+;5 深度为h的满二叉树共有个结点。6-棵m阶非空B-树，每个结点最多有棵子树，除根之外的所有非终端结点至少有棵子树。7在单链表中，若要在指针p所指结点后插入指针s所指结点，则需要执行下列两条语 句：。三.判断题（每题I分，共10分，正确的选t错误的选f）1数据元素是数据的基本单位。（）2线性表中的每一个元素都有一个前驱和后继元素。（）3当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（）4.带权无向图的最小生成树是唯一的。（）5设有序的关键字序列是（2, 5, 8, 9，12，14，16，18, 20, 22, 25），当用折半查找方 法查找关键字22时，需经3次比较运算。（）6-棵m阶B+树中每个结点最多有m个关键码，最少有2个关键码。（）7根据拓扑排序结果可以判断一个有向图中是否存在环路。（）8图的深度优先搜索中可以采用栈来暂存刚访问过的顶点。（）9已知一颗树的先序序列和后序序列，一定能构造出该树。（）10存储图的邻接表中，邻接表的大小不但与图的顶点个数有关，而且与图的边数也有关。 )四.简答题(45分)1. 简述下列算法的功能。(6分)typedef struct BiTNode TElemTypedata;struct BiTNode *lchild, *rchild; BiTNode, *BiTree;void Process(BiTree T)IniS tack(S);P=T;while (P|!StackEmpty(S)if (P) push(&S, P); P=P-lchild;else pop(&S, P); prin tf(P-da ta);P=P-rchild;2. 假设表中关键字序列为(7,6,9,10,14,8),将关键字依次插入一棵初始为空的二叉排 序树。画出二叉排序树的生成过程。(10分)3. 关键字序列T=(63, 55, 48, 37, 20, 90, 84, 32),对其从小到大排序，以第一个关 键字为枢轴(支点)，写出快速排序具体实现过程(10分)。4. 个有六个顶点v1,v2,v3,v4,v5,的网的邻接矩阵如图1所示，解答下列问题：(1) 画出该网(2分)(2) 能否写出一种拓扑排序序列，若可以，写出一种拓扑排序序列(2分)(3) 求出从顶点V到其他各顶点之间的最短路径，并写出计算过程。(8)82015888888810308488810G.arcs :二 88888888815888X884108图1.5. 设用于通信的电文由字符集a, b,c,d,e,f,g中的字母构成，它们在电文中出现的频度 分别为0.34,0.12,0.10,0.08, 0.13,0.20,0.03,如何为这7个字母设计二进制前缀编码 使得电文总长最短，写出编码过程。(7分)五算法填空，(每空2分，共20分)1. 以下算法功能是:插入元素e到队列Q中，完成算法的空格部分。typedef struct Qnode QElemType data;struct Qnode *next;Qnode, *QueuePtr;typedef struct QueuePtr front队头QueueP tr rear;/队尾 LinkQueue;status EnQueue(LinkQueue &Q, QElemType e) P= (QueuePtr)malloc(sizeof(Qnode);辻 L)exit(OVERFLOW);P-data二 P-next=P;Q.rear二 ;Return OK;2. 以下程序为图的深度优先遍历算法，完成算法的空格部分。Boolean visi tedMax;/ 访问标志数组Status (*Visi tFunc)(in t/访问函数变量void DFStraverse( Graph G , Status(*visit)(int v) vistFunc二visit;for (v=0;vG.vexnum;+v)visitedv二False;for (v二 ;+v)if ( ) DFS(G, v); void DFS(Graph G, int v) visited ; VisitFunc(V);for (w=FirstAdjvex(G, ; w= NextAdjVex(G,v,w)if (!visited ;六编写算法（25分）1已知线性表中的元素按值递增有序排列，并以带头结点的单链表作存储结构。试编写算 法，删除表中所有值大于X且小于y的元素（若表中存在这样的元素），同时释放被删除 结点空间。（10分）2设计一个算法，求不带权无向连通图G中距离顶点v的最远顶点。（15分）共 5 页，第 5 页考试科目： 数据结构