北京理工大学计算机学院889数据结构[专业硕士]历年考研真题汇编

《北京理工大学计算机学院889数据结构[专业硕士]历年考研真题汇编》由会员分享，可在线阅读，更多相关《北京理工大学计算机学院889数据结构[专业硕士]历年考研真题汇编（47页珍藏版）》请在装配图网上搜索。

1、目录第一部分历年考研真题汇编2004年北京理工大学计算机学院467 数据结构专业硕士考研真题2003年北京理工大学计算机学院数 据结构专业硕士考研真题第二部分兄弟院校真题汇编2015年中山大学918专业基础（数据 结构）考研真题2014年中山大学912专业基础（数据 结构）考研真题2013年中山大学867专业基础（数据 结构）考研真题2012年中山大学909专业基础（数据 结构）考研真题第一部分历年考研真题汇编2004年北京理工大学计算机学院467数据结构专业硕士考研真题机密启用前试题答案必顼书 写在答题纸上.在试题和草格纸 上答题无效，北京理工大学2004年攻读硕士学位研究生入学考试试題科目

2、代码;科目名称:467科目分号:0116數据结构 特别提醒：请将答案标明题号写在答题纸上，答案写在 试题和草稿纸上无效。一、 单项选择题（共40分）1、在数据结构中，数据的基本単位是 A）数据项 B）数据类型 C）数据元素D）数据变虽2、在数妪结构中，与所使用计算机无关的是数据的 0A）存储结构 B）逻辑和物理结构 C）逻辑结构D）物理结构3、在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是 C） n插入操作算法 B）需要判断是否表空D）需要判断是否袤空和表满D) log nA） n B） n log n4、在线性表的链式存储结构下，A）需要判断是否表满C）不需要判断是否表满5、若线

3、:生表最常用的操作是存取第i个元素及其前趋和后继元素的 值，为了节省时间应采用的存储方式是 .A）年谜表 B）双向链表 C）单循环链表D）顺序表6、在p行指向的结点后插入由q指向的新结点的语句序列是 “A） p-next-q;q-next=p-next; B） q=p-next:p-next=q:C） q-next=p-ncxt;p-next=q; D） p-p-next： q-rsext=p：7、用単涟表表示的链式栈的栈顶一般设在链表的 A）铤头 B）链尾 C）應头或链尾均可D）可以任意位置 第页共9页机密启用前北京理工大学2004年攻读硕士学位研究生试题答案必矩B 写在答题纸一二， 在试题

4、和草祠纭 上答题无效。入学考试试题科目代码： 467科目分号： 0116科目名称：数据结构 8、在表达式求值的算符优先算法中，从找顶到栈底运算符栈中的运算 符优先级是 A) 从高到低B)从低到高 C)无序 D)无序、有序均可以9、若用 个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear 和from的值分别为 - A) 1 和 5 B) 2 和 4 C) 4 和 2D) 5 制 i10、具有300个节点的二叉树，其髙度至少应为 A) 6B) 7C) 8D) 911、设叭n为一棵二叉树上的两个结点，在中序遍历时，口在m前

5、的条件是 。A) n VE m左方 B) n是m祖先 C) n在m右方 D) n是m子孙12、判断一个有向图是否有环(回路)的方法是 A)求结点的度B)拓扑排序C)求关键路径0求最短路径13、在有向图的邻接表存储结构中，顶点v在链表中出现的次数是 A)顶点的v的度B)顶点v的出度0顶点V的入度D)依附于顶点V的边数1L用邻嗟表表示图时，顶点个数为n,边的条数为e,在邻接表上执 行有关图的遍勇操作时，时间代价是 A) 0(n) B) 0(n+e) C) 0(n*e) D) 0(max(n, e) 机密启用前北京理工大学2004年攻读硕士学位研究生入学考试试题467科目分号： 0116数据结构试题

6、答案必须拈写在答题纸上，在试题和草摘纸科目代码;上答题无效， 科目名称: 15、对下图所示的有向图.A） VO VI V2 V4 V6 V3C）V5 V3从顶点vO出发的深度优先序列是 V5 B） VO VI16、对于一棵二叉排序树，为了得到所有节点的有序序列.应该对排 序树进行 eA）前序遍历B）中序遍历 C）后序遍历 0）层次遍历17、排序算法的稳定性是指 ,A）B）C）D）排序之后，能使值相同的数据保持原顺序中的相对位置不变 排序之后，能使值相同的数据保持原顺序中的绝对位置不变 算法的排序性能与被排序元素的数量关系不大 算法的排序性能与被排序元素的数量关系密切18、若要求：从任一结点出发

7、到根的路径上所经过的结点序列按其关 健字有序-满足这样性质的二叉树是 。A）堆B）哈夫曼（Huffman）树C）完全二叉树D）二叉捶序树19、既希望较快地査找又便于线性表动态变化的査找方法是 0A）顺序者找 B）折半查找 C ）索引顺序査找 D）哈希査找 机密启用前北京理工大学2004年攻读硕士学位研究生试题答案必须书 写在答題卽:上.在试題和基稿纸 上答諷无氣入学考试试题科目代码：467科目分号： 0116科目名称：概据结构 20、二寸斉找又称折半査找） 。A）适用于链式存储结构B）固用于顺序存储结构C）既适用于链式存储结构又适用于顺序存信姑构D）既不适用于链式存储结构又不适用于顺序存储结构

8、特别提酬：请将答案标明题号写在答题纸上，答案写在 试题和草稿纸上无效。二、填空题（共26分）I、设冇一个空栈，现输入序列为1,2,3,45。经过push, push, pop, push, pop. push, pop， push 后，输出序列为 *队先线索二叉树中的任意结点X,若K有左子树.则X的后继为X的 链所指的结点，否则为X的 键或 线索所指的结点3、对任何一棵二叉树，若它有nO个叶子结点、能个度为2的结点, 则有：n0= .4、深度为6的平衡二叉树最少应该 结点。5、对于-边稀疏图要求最小生成树应该选用 算法。 机密启用前北京理工大学2004年攻读硕士学位研究生试题答案必須再 写在答

9、题纸一， 在试题和草物纸 上答题无效。入学考试试题科目代码： 467科目分号： 0116科目名称：数据结构 6、有”个顶点的无向连通图至少有 条边。有“个顶点的有向强 连通图至少有 条边说明。7、用邻接矩阵表示无向图时，若图中有100个顶点，100条边，则形 成的矩阵有 元素，有 非零元素。8、设有100个元素，用二分法査找时，最大比较次数是 .9、给岀美键字，哈希表通过 确定记录的存储位置。三、简答题（共48分）1、用一个一维数组S构成两个共享的栈，S的大小为MAX,则如何共 享？栈满和栈空的条件是什么？2、若将-个双端队列顺序表示在一维数组冗浦中，两个端点设为 endl和end?,并组织成

10、一个循环队列.试写出双端队列所用指针endl和 end2的初始仏条件及队空与队满条件。3、试分剂找出满足以下条件的所有二叉树:（I） 叉树的前序序列与中序序列相同:（2）二又树的中序序列与后序序列相同;一叉树的前序序列与后序序列相同， 第6页共9页科目代码： 467科目分号： 0116科目名称：数据结构 机密启用前北京理工大学2004年攻读硕士学位研究生 入学考试试题试题答案必须15写在答题纸上1在试題和草稿豕科目代码； 467科目分号：0116上答题无效。|科目名称:数据结构4、对于如下图所示的图(1) 画出该图的邻接表。(2) 给出此图的一个拓扑序列,第10页共9页5,请画出在下列二叉排序

11、树中依次删除节点50和60之后的二叉排序 机机密启用前北京理工大学2004年攻读硕士学位研究生试题答案更须细 写在答题纸上， 在试题和草稿纸 上答题无殺.入学考试试题6、请首先按照下列顺序建立平衡二叉树：50, 23, 60. 15, 25, 65.10和20.画出建立的平衡二叉树，然后在你建立的平衡二叉树中依次插入:5, 80, 19疝訪，请依次画出插入毎个节点之后平衡二叉树的变化.7、请在下面m=3的B树中依次插入90和30.请画出B树的变化过程.8、对以下序列(7, 3, i, 10, 2, 4, 5, 8, 9, 6, 11)按照升序进 行排序，遣写出一趟快速排序的过程及結果。四、算法

12、设计(共36分)I、假设L是一个带头结点的単链表(链表元素的取值范围为I到 MAXSIZE之间的整数).试给出下面函数A的功能及参数S的含义。void A ( LinkList L, int S , int MAXSIZE ) for ( i=l; inext;while ( p != NULL )(Sp-data+;p = p_next;/ whileI/ifI/A试聘答案必须8 写在答题纸上.在试題和草程至 上答题无效.机密启用前 北京理工大学2004年攻读硕士学位研究生 入学考试试题2、设有一个线性表(e, ei,，e0.2, en.i)存放在一维数组 AarraySizel中的前n个数

13、组元素位置。请编写一个函数将这个线性表原地 逆置,即将数组的前n个原址内容置换为(en.u en.2, elf e0)o函数的結 构如下：void inverse ( Type A , int n ) A是需要反序的数组，n为数组中包含的元素的数量清在inverse函技中項写适当的i吾句完成规定的功能。请写明算法的基本思 路，并在算法的主要步骤上如注释。3、设用二叉链表存贮二叉树，结点的结构如下：lypedef struct BiTNode ElemType data：struct BiTNode * Ichild, * rchild; BiTNode, * BiTree;试编写判断两楞二又树

14、是否相導的算法。函数结构如下：Status equai ( BiTree T1，- BiTree T2 )本算法判断两棵二叉树是否相等，/若相等瓯回1,否则返回化清equal函在中设计适当的算法,填写适当的语句完成规定的功能。请 写明算法的基本思路，并在算法的主要步骤上加注释，机密启用前北京理工大学2004年攻读硕士学位研究生试题答案必须书 写在答题纸上， 在试題和草稿抵 上答题无效.入学考试试题4、对表达式可以采用前缀表示法，例如表达式：8+3*(2-7)1/2,采 用前缀表示法可以表示为：- + 8*3-27/4 2。假设表达式中包含的运算符号只有+、-减)、*和厶表达式中包含的 操作数均

15、是单个的数字形式(0-9).假设系统已经提供了两个现成的函数：two_result和is_operatorn)3.如图阴侦的又树的中序序列是0.0( tf)4. ( H理数类Rfliianal中，实现实數转换为有理数的函数是A. Itilicnuil(ib/ubk x)IS, tjfxralor dhjAc( viu!) ejiMC. K;itional( long mini, long dcnom) D. operator doublet National r) itunst5. 在安全数組类中.币栽的下标运算符“I ”返回的是a. m 元素值r.数组元素引用C.数摑元素指针D.数组元素下标

16、6, 在整型集合类Scl中.数据成员setrange志示的是A.我合中元素的个数H.位数组的字节数匚生合中元素个教的最大伯D.位数组字賢数的批大值7, 包再77个结点的二叉树的最小深度是A. 3B. 4C. 58. 在后在表达式求偵洲:法中，要用个梅A. 0B. C. 2D. 39, 洒要从1000个数中选出炳小的I。个虬律法並合适：L基数排序电归并排序242C.堆排序D.快速排序10.若有向图中任意两个結点之间有一条有向路径.则称该有向囲是 。 A.连通分量B.强连通分量C.弱连通图D,強连通图二填空题L我们把每种数据结构均视为抽象类型，它不但定义了数据的 方式，还给 出了处理数据的 O2.

17、 数据结构的面向对象方法提供了对代码的 ，即可将过去开发和测试过的 代码“植入”新的应用中。3. C+ +主要通过 和 来支持多态性。 4. 数组的特点是可以 访问数据元素。 5. 在事件驱动银行模拟实例中，主要包括两种事件: _和 。6. 在函数 Push(const Data Type& item)中.const 的作用是o 1. 在顺序表类Seqli&t中，Find和Delete函数要求DaiaType上定义了 运算符。三、回答下列问題1. 用基数排序对下列序列排序：317.286.726,35427,819.381,列出第二遍结束后表 中内容。2. 请最多用两句话描述复制构造函数在处理

18、带动态数据类中的作用。3. 在迭代算子类Iterator中，Rtsct和Next两个方法的作用是什么？4. 与竞赛排序相比,堆排序的主要优点是什么？四、算法題l.InsctSort(Nle *& head)是一个利用插入排序算法对链表内容进行排序的函 数。清在空缺处填入正确的内容template clas& T Avoid InsertSort ( Node * & head)INode * nwhead , * olclhead;Node * currPtr * prevPtr. * tempPtr, * newTiode;T ilem; while (ddbcad ! = NULL)Ipr

19、evftr = NULL;currRr = ncwhead;item = oldhead - data;tempPlr = oldliod;okfhead = oldhcad - NextNode();delete ten叩Ptnwhile (currPtr ! = NULL)Iif (item data) break: prcvPlr = cunrPtr;currPtr = currPtr - NcxtNode();Iif ( prcvPlr = NULL) ekeInewnode = new Node (item);head = nehcad;12,清编写一递归函数void Reverse

20、Cint a int s, int O其功能是将數组a.中从下 标s开始到e结束的整数顏倒顺序.如：执行前：h =10,1,2, 3.4,56| s= Ie = 4执行后曲=10, 4. 3f 2V 1, 5 6要求在该函数中不使用新的数组，没有循环。（注:本題可以使用C+ +或C语言编写）244第二部分兄弟院校真题汇编2015年中山大学918专业基础（数据结构）考研真题中山大学考生领知全部答案一檢写在答題纸上，答在成题纸上的不汁分1答.題要写清题号，不必抄题*二。一五年攻读硕士学位研究生入学考试试题 科目代码918科目名称：专业基础(数据结构)考试时间:12月28日下午请问小明用的是什么排序

21、算法？A.选择推序B.归井排序 C快速排序D.插入择序10. 以下的排序塊注中，哪个穽法在下环情况下的时间复衆度最。s勺？A,堆排序8.快速排序C. EJ并排序D一基数排序11. 给定一个算术表达式心X的中绿形武是A*& (6 分)F标012| 345678910i5.给定囲G如下第3页共4页iff找出并画出图3的一棵最小代价生成树.。分） 清西出圈G对应的鄭接地陣.（6分）三縮程應(共50分)1.(1。分)以下是一个(不完整的)直接插入排序算法的代码，清根据注释的提示把铢少的代 码补充完整。void insertion_sort(int entry。，int count)irrt first

22、_unsorted;/ position of first unsorteci entryint position：H searches sorted part of listInt current;/ holds the entry temporarily removed from listfor(first_unsorted = 1; firstunsort&d count; first unsorted+*)if(entryfifst_un$Qrted entryfirst unsorted -1)(/please complete the code here)2.(15分)逆转链表：写

23、_算法逆置帯头结点的隼链表L.要求逆置后的単旌規利用I中的原结点， 不可以重新申谙皓点空间.链去结点的声明如下；template struct Node(Entry data;Node * next;F请实现下面的函敌：void reverse (Node* L)3- (25分写一个算法，逐届遍历一根二又树(从上到下，从左到右.以下是二又馆及二又树 中的节点的声明：tempfote Sass Entrychss &fnQry_tree public:Binory_tree(;void Lyer_order(vaid(*visit( Binarynode &);protected：Binary_

24、node * root;template struct BSnafy_nQdeEntry data;Binary_nde * 也ft; Binary_ne * right; 听。叫_nxtfe化请实现下面的函数：void Layerorder(void(*visit Entry &).第4页共4页2014年中山大学912专业基础（数据结构）考研真题中山大学二。一四年攻读硕士学位研究生入学考试试题料目代码:912专业基础(数据结构)考试时间;I月5日下午考生预知全部答案一律号在答題纸上， 答在试题维七的不计分！答题要写 淸题号，不必慮楚.一単项选择题每題2分，共40分)1，算法氈条度通常是衣达算

25、法在最坏情现下所琵要的计算笙* 般不用来在达算法复杂度的表 达式为(、(A). tXn1)(B). 0(100).釈曲跡)(00(1.5A數据能构有四类基本维构，不是其四类结构之一的是().(A).巢合(B).线性结构(C).存瑞第构(D),樹形培物3. 在存儲信息过程中，逋过对美谴字的计算来确定其存務位置的数据始构是().(AJ. Hash表甲)二叉搜索树C),縫式结构(D).嗣序靖构4. 有美単向縫湛的正确描述是().(A).在(XD时间内找到指定的美链字(B).在插入和舸除操作时无需球动链表结点(C).在顷1)时间内删除指定的关键字(D).单向鏡眾的存儲效率髙矛数蛆的存储效第(B). H

26、ead-next 二 Head(D). Head-jiext = NULL 正确的描述是()(B)-字筍率只能用连接存储空冋來存備(D) 一字符事是一神特殊的线性表丸個设Head是不带头结点的双向循环槌的头结点指针.判断倍喪为空的条件是().(A) Head NULL(C). Hee.dmxt = NULL6- 在下列关于“字符戦的除述中，(A).字符串一定有一个结束符(C)，“空本”与空白串”是同一个含义(B)可用锥戒实现动态队列CD).可用动态洼续存儲空闻实训动态队列M头、里下标分别为Front fD Rear,在队列不満的情况下，“入 ).(B). Rear- (Rcar+ 1) % Q

27、size(D). From - (From + 1)% QSi?g7- 美F队列的不正驹描述是(A). HFO(C).可访问队列中任何元素8,假设循孙队列的表度为QSiiSr跃”后相应下标变化的语句为(A). Rjear= Rea叶 1(C). Front = Front + i若试能毕，试题她答题纸一起交四9一用槌表来实现堆找，睥組是能表條直中的指针字段，Top为械项指针.在他定理找非察節情况 下，出栈的语句是()，其中：所有变量滞舂法定义了* frtc(Point)J放指针Point所指 向的存備空向.(A). Tbp = Top-next;(BJ. free(Tflp); Top = T

28、op-nfixt;(C). Tap = Top-next; free(Top);(D), Pt=Top; Top = TopEext; free(Pt);10-设Al剛1可为个対称矩阵，数组下标从剧向幵始.为了节省存储，再其下三角部分按行 存放在维數缱理丄54IJ知所対应的数组元素t ).(A).A31(8(B)ARIR)(C).A3(7(D).A2f7II.若一揉二叉树的后序知中序序列分荆是婀同和逸冲 則其先序序列是().(A), abdjec(B). abdefi:(C). acbd&f(D). acbefUIA用一维数组来存储满二又树，若数组下标从0开始，則元素下标为帕整0)的左子结点下

29、标是 (X不考虑数组下标越界阿題、(A). 2k-(By 2(C). 2jH-1(D). 2H213假设戏和办是二叉搜索欄的左右子树，M发示树的高度“若树丁是,g 树.则15.16.17,18.()*(A)川_风勇=(B).戸-阳)=I(C).H(w- 玳瑜si(D).W 1用邹接籟阵存储有m个项点(0.1,.-1)和#条边的无向臥gJGG-IH环在图中没有无向边 WE的情况下，增加此谊后，修改部接矩阵的时间宴衆度是()，(A),(XI)伽0#)(C). 0(e)(D?. FS 算法 (B). KMP 算法仁),Dijkstra 算法 (D). Kruskal 法二、解答战(每题10分.共50

30、分)巳紂一个无向圈的顼点集为 1,2,33, 5,6,7 ,其邻接矩阵如下所示0-无边,1-有选).10 10 110 0210 1111030 10 111041 1 1 0 0 0 051110 0 1060 110 10 170 0 0 0 0 1 0第2題用图第3页共7页(】).画出该图的图形;(2).根据邻接短阵从顶点4出发进行寛度扰先遇历(同一个結点的邻接结点按结点转号的大小 为序)，画出梢应的宽度优先遍历树-2. 简单挂述求图最小生成埔的Prim算法(普里媛算法)的基本思想，并按算法步骤从结点ZJ开 始，列出图2的最小生成树的求解过程*3. 简单綴述合并排序算法(Mcr&e So

31、rt)的基本思想，按递増斯序对下面所给数值进行排序，并接 步器列出每歩拌序后的数領序列.假设在排序过程需要划分时，用函数lx”来处理， 掩排序的数值序死：87 56 10 23 44 83 724. 已知有下列13个元素的散列表：。12345678910 II 12205043695762: 63其散列函敏为其钮)=(3地+5)% m(m=13),处理冲突的方法为线性探测苒散列洛 探査序 列为：岛=(h(key) + d) % m, d, 1,2,3,问：在表中对关摟字50和56进行登找时，所需迸行的比教次数为多少？成次写出萼次计算 公式和童5. 假设 在通指中，字符出现的頻率如下：a: 10

32、% t: 12% c：l% d:2% e: 9% /:28% g: 13%(1) 根据Huffman算法(症夫建算法)画出其赫夫曼树；(2) 给出毎个字母所对应的赫夫熒墙玛.规定，結点左分支边上标0,右分支边上标1：(3) 计算其加权路径的长度WPL.三，阅读理解题，按空白编号壊写相应的C/C-+语言语句，以实现函数功能(每空a 分，每顕1。分.共30分)】傲设定义了下面的链式堆栈类试绸写相关成员函数，struct Node (iru key;Node *next;pubHciNodc() ( next = NULL; J;；class Stack (public:Stack() Top NU

33、LL, ;-SlackO；baal Pushfconst ini &key);baal Em ply 0 return (TopNULL);privatesNode *Tbp;I；(1) 成员函数Puh(const mt &key)：若申请不到存備空间-返回falss.否则耙參数key ffi 进避找，幷返3 true.bool Stack:Push(con$t int &key)(Node *Pt - new NodeQ；if ( =H ) return false;Pt-key - key;(2 ;_；return true;(2) 析构函敝宾配虹)：择敏堆桟所巨的所冇存储空间.Stack

34、:Stacfc()(Ncde 叩I；while (Pt =Tup;:desete Pt;笛4英共7页2-假设用不帯头结点的单向链表存储一元多項式，并按指数者序存储(从大到小)*其桂衰结点的 结构定义如下；typedef struct _PNade (int Co&f;系数tot Expn-/指数(规定：指数王0)struct _PNode *next;)PNode; 函数PNode*Copy(PNade “Pl)；把Pl指向的多项式复制一粉并返回新多项式的首地址 印考感申清结点内存失畋的情况).PNode *Copy(PNode *PI)PNodc *Headr *Ptl, *Pt2;Head

35、 a NULL;while (Pl I-NULL) (Ptl = (PNode *) caloc(l1 sizeof(PNode);Ptl - Coef = Pl-Coef;Pit - Expn = Pl-Expn：f( Qj Head = Pll;else Pt2-Agxt = Ptl; ；Pl = Pl-next;(2)函JfcTime(PNode *P1S PNode P2)；计算多项式Pl - P1XP2.其中P2是一个多项式结 点.运算过程中，不考虑数值的溢出间題*void Tim(PNode *PI, PNode P2)PNode *Pt;for (Pt = Pl; Pt != N

36、ULL; Pt = Pt-f ext) 假没：円是多硬式+的首地址，P2HY2),即：P2为占执行 Time(Pl,P2)B, Pl 指向的多项式为a -12T4x* + 40x2.第5页共7页丄 假设二又树T滯中叶子数的定义如下:TNULLT广NULL 且 TNULL 其他roLe8VCS(T)- t 0printRckey)； 第&页共7页四、算法设计题(每韧1S分，共30分)用口CX语言实觊下面函数的功h也1. 假设用笛表存储集合,空縫表示空集.存瓏集合的遂表结点定义如下: typedef struct .Element int elementU集合元素struct .Element *

37、next; Element;H集舍的结点定义例如：X=(11,22f 卜这些集合的存儲链表如下图所示。22NULLbL第7页共7页(1) Element Pn就(Element *A, Element *B),其功能是生成集合和8的并集縫表，返回并 集链表的头指针(不考虐申请结点、失败的情况).(10分)void Dispy(char *Name( Element *Ab其功能是显示集会/中的元素列表.其中：Name 是集合A的符号名或任何字符串.(5分)例如有下列语句：0C是集合滝翱&并堡的首地让，眼舍X和H己按要柔存儒好 /输出结果：A=( 11,22)缩出结果，Set BiElement

38、 *A,寧& *C;C Union(A, B);Display A);Di项就Set 0? B);2.己知二叉覆索樹Binary Search Tree)戒二又排序树(Binary Sorting Tree)的结点定义如下： typedef struct BSNode int key;struct_BSNode *LChild峨Child; /左子树的关健字比根的小，右子构的关谜比樨的大 BSNode;编写函数int lnsert(BSNode *root int key).其功能是在以结点*攻为根的二叉捜:索:树中将人 美St key.若插入成功，貝I返回伉若关键字己存在，则返回若申请结点失

39、败刑返回2,2013年中山大学867专业基础（数据结构）考研真题中山大学考生须知全部答案一律写在答曲纸上. 答在试願鮭上的不计分I请用置 黑色墨水笔或圆珠笔作答。答題蜃 写淸題号，不必抄璃.二。一三年攻读硕士学位研究生入学考试试题科目代码；867科目名称：专业基础(数据结构)考试时间：1月6日下午一、单项选择観(每题2分，共40分)1. 算法复杂度通常是表达算法在最坏情揽下所需要的计算SL暇设算法4在处建&个数据的时 间厘杂度为0(1)，算法治在处理“个数据时除10次连续调用算法禹外，其它部分的时间夏 杂度共为。那么，算法小的时间复杂度为()(A). O(n)(B). 0). LIFO假设循环

40、队列的长度为QSizd其头、尾下标分别为Fmnt和Rear.在还诃“入队”的情况下, 计算队列中己TF的元素个数为()(A). Front - Rear + 1(B). Rear 一 Front + 1(C). (Front- Rear+QSize+1) % QSizc(D), (Rear Front HQSize+t) % QSize考试完毕，试題和草稿纸随答题纸一起交回。第2页共7页8. 用養表来实现谁战.wxt是链表结点中的指针字段，Top为栈顶指针甲Pt为当前待压栈的色点指针(非空 有关压栈信息已存储好。压栈的语句是()(A). Top k Pt;(B). Pt-nexl = Top;

41、(C). Ft-next = Top - Pt;(D). Pt-next = Top* Top = Pt：9. 假设Head是不帯头舖点的隼向循环链的头结点指针。判断链表为空的条件是()(A), Head.next = NULL(B). H&ad-next = Head(C). Head = NULL(D). Headnexl = NULL10. 设 虹mgo为一个对拶,律,数组下标从叫开始。为了节省存備，将其下三鸞部分按行 存放在-堡狡坦BO.54b 030所対应的数組元素().(A).A72(B)AP1 (C).A82(D).A8J3Ik若一棵二冥材釣先序和中序序到分别是ftblcdebf

42、edet.剧其后序序列是()(A), bfdeac(B), fb&dca(C). fljdeci(D), dbefea12.用一雄数组来存航满二又树，若揪组下程从0开始，则元素下标为 碓0的父结点下标是13.15.16,17,3)丄枕(B). LtJt-iyz(c).f(Jt-iy2l (d tol对住憲一瑚二瓦树n示柵r的高度”若樹丁會有#个结点，那么、 )(A).附-响(B).明兰以1創(C).可乃=OGofifl)(D). 7/(7) 3 0(1 迎町用邻接拒阵存備有吊个顶点也和e条边的有向圏沒成中1).在邻接矩阵中玲除结 点祯式出-I)的时间藐杂度是()(A).(7(n(B). O(n

43、)(GW#)(D). Otrt+e)用部接矩阵存儘有K个项点(0丄I)和。条边的有向图判断结点；到結点 人0關/S1)有边的时膂瓠朶度是()(A). 0(1)戸)珈)(C).O(e)下列排陪算法中，平均时间复杂度为3普)的是()(A).插入排序C0).归井排序(C),快速排序对的个数进行推序时，基于比较的搏序算法至少需哽比较的次数为( (A). O(lDgn)p),风卧,砌咿)OA WE)(D).堆排序(D)削)n.20.用基数(橘)排序京法对32位无符号散按字节进行拌序时，即：先用最-个字节尊低字节)进 育排序.再依欢用第二、第三和第四个字节迸行排序。需要捅的个教是()(A). 8(B).

44、16(C). 12S假设有M个特査拽关縫字，有关折芈査挂算法的不正确描述窪( (A),散坏搜索效率为8)一平均搜索效率为如働) (C).捜索效率为0(如事)(D)-数据有序且顺序存储在下列第法中，求图中两点之间最短建役的算法是()(A). DFS 蘇法 (R). Prim 算法(C). Dijkstra 算法(D). 256)*(D). KMP 算法二、解答题(毎應10分，共50分)1.已知一个无向图的頂点c,dte,f,gt其邻接矩阵如下所示(0无边,1-有边*a b c d e f gaoiioiofb10 11110c110 10 0 0d0 I 1 0 0 0 0e1 1 0 0 0

45、0 1f0 1 0 0 0 0 1gLl 0 0 0 1 1 0.第5页共7页图2第2题用图，画M该图的图形；(2)-根据邻接矩阵从顶点a出发进行深度优先遍历(同一个结点的邻接结点按结点的字母序为 序).画出相应的深旅优先遍历树.2. 简单描述求图最小生成树的Krmka】算法(克魯斯长尔算法)的基本思想，并按步霜列出图2的 最小生成树的求解过程.3. 简単叙述堆排序算法(HeapSE)的基本思想.按,由小到大”排序所给的数也并按择序步骤列 出毎次己堆化好的待择数值序列.可不列出“己排好”的数值和堆化过程中的堆形状或数值序 列，如果给额外信息，将判断这些信息的正确性。初始已堆化好的待排数值序列：

46、93 67 78 15 34 40 334. 已知有下列13个元素的愀列表:0 , 1 , 2 , 3 , 45 , 6 , 7 . 8 , 9 . 10 , 1】.12.| 63 | 20 | 50 | 43 |44 | 49 58其散列函数为M加y)=。御+ 7)%处理冲突的方法为雄性探演再散列法，蟻査序列为：hi - (h(key) +(!) % m, 4= 1,2,3,s-1*问：在表中对关键字50和36进行査找时.所需通行的比较次数为多少？依次写出毎次计算 公式和值，5.假设在通信中，字符a,b,c,d,ejg出现的领率如下：a: 27% A: 20% c:16% d: 19% e：

47、 9% f. 2% g: 7%(1)服据Huffin血算法(恭夫曼算法)画出其赫夫曼树；给山毎个字母所对应的赫夫曼装码.规定：结点左分支边上标1,右分支边上拣皿(3)计算其加权路径的长度WPL.三、阅读理解题，按空白编号填启相应的CJC卄语言语句,以实现函数功能.(每空2 分，毎题1。分，共30分)L暇设定义了下面的链式职列类，试编写相关成员函散。struct Node (int key；Node *iwxt;public;Node() next = NULL; ;Nodc(ini Key, Node *Nex.t=NULL) ( key = Key; next 後 Nex.1;；如s Que

48、ue public:Queue() ( Front = Rear = NULL;-Queue()：bool AppenI(const intbool Empty0 ( retuni (FrontNULL); ;private:Node Frpjitl *Rear;E;成员函Appcnd(const ini &Ttein)：若申请不到存储空间，返回false.否购.把参数Item 附加到队列尾部并返回饷珏bool Queue: :Appcnd(ccnst int Altem)(Mode *Pt = new Node(rtetn);if (Pt = NUIJJ remm faiw;iff 卩_) Front = Ft;else 2 ; tn；renim true;f2)析枸函jftQueuet)：釋放队列所占用的所有存储空同“Qm$u)e：:-JustieONode *Pt;while 耸 _ J Pl - Fronts ；delete Pi;2,假设用不带头结点的単向链表存梏一元多项式.并按指数有序存储(从大到小或从小到大).其 链表结点的结构定义如下：tjpedef struct _PNonext; ；while (Ptl != NULL) (Pl2 = Ptl;