1、第一有些历年考研真题汇编2014年武汉纺织大学数学与核算机学院848数据规划考研真题武汉纺织大学2014年接收硕士学位研讨生试卷类别代码 h4s类别称号 数据规划考试时刻 20m年1月5日下午报考专业k试题内容不得跨越画线规模,试题有必要打印，图表清楚，标示精确。2、试题之间不必空格.3、答案请写在答题纸匕在此试卷上答题无效,题号-四五六七ak十卜一得分得分本试畲总分150分,考试时刻3小时。一、填空题(每空3分，共30分)1、以下程序段中语句“k+j的频度是ok = 0;for (i = 1: i <= n: i+)for (j = i: j <= rt; j+)k+;2、是数据的

2、根柢电位,在核算机程序中一般作为个全体进行思考和处置m3、在长度为n的次序表中，删去第i个元素时，需将 个元素顺次向前移动一个方位.4、入栈操作p”h(&s, q的操作成果是刺进元素p为新的 元素.5、结点a有9个兄弟，结点b是结点a的双亲，结点b的度是 o6、在富含1000个结点的二叉链表中有 个空链域。7、深度为10的满二叉树有 个结点.8,在有100个极点的行向图中，弧的数口最少是0,最多是.9,在以下有序表中，选用“减半查找，找到20需比照 次. 8, 11, 15, 20, 32, 41, 57)共6页:第i页10、已知循环行列q的声明如下，则循环行列q的长度是 。defin

3、e max 1000 最大行列长度 struct （char *base;int font; /头指针，若行列不空，指向行列头元素int rear; /尾指针，若行列不空，指向行列尾元素的卜.一个方位 q;二、答复题（每题10分，共80分）1、已知二义树的中序遍历序列为bdceafihjg.后序遍历序列为decbijhgfa,需求: 画出该二叉树（8分）给出该二叉树的光序遍历序列（2分）2、已知 8 个权值为30, 70, 15, 10, 20, 35, 50, 60）,需求；根据8个权值规划并画出赫夫里（huffman）树（8分）求该赫夫曼（huffman）树的带权途径长度（2分）4、设待查

4、找的要害词序列为50, 100, 60, 50, 30, 20, 25, 30, 90,需求:规划并画出二叉排序树（8分）假定每个记载的自找概率相等，求查找成功时的均匀查找长度（2分）5、已知一组要害词为19, 14, 23, 1, 68, 20, 84, 27, 55, h, 10, 79）,哈希函数为h（kcy）=kcy y0d 11,哈希表长为11,选用链地址法处置冲突，需求:规划并画出哈希表（8分）假定每个记载的查找概率相等，求查找成功时的均匀查找长度（2分）baecd100134a3a43a2a2a6、已知无向图的邻接表如下:从极点c ，根据邻接表，给出深度优先查找序列（5分）从顶

5、点c ，根据邻接表，给出广度优先查找序列（5分）7、已知连通网如卜，从极点f初步，选用普里姆（prim）算法，给出规划最小生 成树的进程（10分）8、己知待排序的要害词序列为50, 30, 25, 100, 90, 80, 70,选用“快速排序”办法，给出按从小到大的次序排序的进程（10分）三、算法填空题（每空5分，共20分）1、己知单链表的存储规划如下:typedef struct lnodo elemtype data;struct lnode *next;)lnode, *linklist;试结束在带头结点的单链表l中第i个方位之前刺进元素e的算法。status li st inser

6、t_l(li nklist &l, int i, elemtype e) p = l;j = o；while(p && j < i – 1) p = p->next;+j;if(!p i j > i – 1)return error;s = (linklist)malloc(sizeof(lnode);s->data = e: p->next = s;return ok:)2、已知线性表的动态分配次序存储规划如卜.:4define list_init_size 100define listincrement 10typedef struct

7、 (elemtype *elcm;int length;int listsize; sqlist;试结束规划一个空的线性表l的算法。status initlist_sq(sqlist &l)共6页:第5页l elem = (elemtype )malloc(list_init_size * sizeof(elemtype); if (!l. olcm)exit(overflow):l listsizc = list init_size: return ok;)3、已知静态查找表的次序存储规划如下: typedef struct elemtype *eiem;int length; ss

8、table;试结束在次序表st中次序杳找要害词等于key的数据元素的尊法。 int search_seq(sstable st, int key) int i; 一 一 -9for(1 = st. length; st. elemi. key != key; -i)* return i:)4、已知静态查找我的次序存储规划如下: typedef struct elemtype *e1em:int length: sstablc;试结束在有序表st中次序查找要害词等j- key的数据元索的算法。共6页:第6页int search bin(sstable st, int key) int low,

9、mid, high;low = 1:high = st.length;while(low <= high) if (key = st. elemmid. key)return mid;elseif (key < st.elemtmid. key)high = mid – 1;elselow = mid + 1;)return 0;)四、算法方案题(共20分)已知二叉树的二叉能表存储规划如下:typedef struct bitnode telemtype data;struct bitnode *lchiid, *rchild;)bitnode, *bitree;试方案求二叉树叶子

10、结点个数的算法。函数头如下:int countofleaves(bitree t)其间，t是指向二叉树根结点的指针，函数的回来值是二叉树叶子结点的个数。共6页；第6页2013年武汉纺织大学数学与核算机学院848数据规划考研真题武汉纺织大学2013年接收硕士学位研讨生试卷类别代码 h4s类别称号 数据规划考试时刻 2013年1月6日下午报考专业fa试题内容不得跨越冏绕的阖，试题有必要打印.图表清楚，标示精确.2、试题之间不留空格.九答案谙写在答题纸匕在此试卷上答腿无效.题号-"j_afl四k六七九十h一得分得分本试卷总分i知分,5试时刻3小时.一、填空题(每空3分，共30分1、数据规划的

11、方法界说d;na_slruclw(d中，d是的 有限集2>以下程序段的时刻更杂度为 afor (i = 2; i <= n; +i)for (j = 2; j <- i – i; +j)+x;3、对个初始为空的栈3实施操作pu$hg,5)、pushes, 2) push(s,4)、pop区x)和ge(top(st 乂)后，k 的值为 a4, 一棵有n个结点的树中，一切结点的度数之和为5、假定在线性及的任何方位上刺进兀索地等概率的，则表长为n的限序存储规划的 畿性衣中.刺进一个元素时所需移动元素的均匀次数为6、在含tttisal)个结点的各棵树中，深度最小的树含tt 个分支结点

12、.7、深度为9的满二丈树有 个叶子结点,8、选用直接刺进措序对300个记载揖序.所需进行要害词间比照的次数最少是次。土具有20个极点的连通图至少闻仃 条边.共4蛇第1页共4页:第2页3、对如卜.无向图，试从极点a给出选用普里姆（prim）算法规划最小生成树的进程（10 分）4、对如卜带权有向图，选用迪杰斯特拉（dijkslra卜算法求极点a到其他各极点的最短5、已知一个长度为8的线性表,其要害词序列为50,70,80,75,10,20,30,25,按各 元素的次序规划棵二叉排序树，着各元素的查找概率相等，求该二叉排序树的均匀 查找长度。 （15分）6、已知一组要害词为9, 14, 33, 5,

13、 68, 20,84, 27, 55, ii）,哈希表长为12,按哈希函数:h（kcy） = kcy mod 11和翻开定址法处置冲突，增量序列选用线性勘探再散列，试构 造哈希表，并求查找要害词11需顺次与哪些要害词比照。 （10分）7、若待排序的要害词序列为25, 73, 12, 80, 116, 15（,按增量值3, 2, 1给出希尔排序 的从小到大排序进程。（10分）8、若待排序的要害词序列为65, 76, 18,36,95,30,给出快速排序的从小到大排序 进程. （10分）三、算法方案题（每题15分，共30分）1、函数sum的功用是求形参位数字之和，例如，假定形参n等卜1357,则函

14、数sum的回来值为16(16= 1+3 + 5 + 7),编写函数sum,函数首部如下:int sum(int n)2、已知二又树选用二叉链表存储，二又链表界说如下typcdcf stnict bitnode (teicmtypc data;struct bitnode *lchild9 *rchild; bitnode, *bitree;函数depth的功用是求二叉树的深度，形参root是指向二叉树根结点的指针，回来值 是二义树的深度，编写函数depth,函数苜部如卜.:int depth(bitree root)共4页:第4页第二有些兄弟院校真题汇编2015年中山大学918专业基础(数据结

15、构)考研真题中山大学二o一五年攻读硕士学位研讨生入学考试试题考生须知悉数答案一概写在答题纸匕答在试题纸上的不计分!答题要写清题号，不必抄题.类别代码:918类别称号:专业基础(数据规划)考试时刻工12月28日下午 一，单项选择题1每小题3分.共45分)l stl中的优先行列是选用啥数据规划来完成的？a.堆区行列c.栈d.图丸数据规划中，与所运用的核算机无关的是数据的()规划.人存储及物理c.逻辑d,物理和存储3.核算机算法指的是(a.核算办法b.排序办法 c.调度办法 d.处置疑问的有里指令序列4,给定一个有n个元素的数组5为偶数).假定要找出数组中的最大元素和最小元素，最少要进 行c )次

16、比照？a.2n bcn72-2 c. 2n-2 口 4 加35 .给定一个包括250个整数的数组，读数蛆中的整数已按从小到大的次序排好序假定用二分查 我从该数纲中寻找某个给定的整数打最多只需要徽()次比照.a-8 b. 9 c106 76 .t(n)标明某个算法的时刻夏杂度.假定(n) = 2了(n+o(n),则丁为()a. cxiogn) ft. 0< n)c, ofnlogjn) d* o(n:)工假定整数n>0,下面的程序的时刻凌乱度是().x-2;while (x<n/3)-z*k;a. o(og3n) b. o(n) c. o(nlog2n) d.o(r?)s,下列

17、排序算法中，哪个是平稳的排序算法？a.选择排序b.快速排序c,归并措序d.希尔排序9 .假定小明用某一揖序算法对整畋序苑但2,45"5/5, xi)进行排序.0以下为排序进程中序列状况的 改变进程:ifta: 82 45 25 15 21第一步:45 82 251s 21第二步:25 45 股 15 21第三步:1s25 4s 82 2 l考试完串.试捱随答脍ift一同交回.第】页共4页请问小明用的是啥排序算法？a.选择排序b,归并排序 c,快速排序d.刺进排序10 .以下的排序算法中，哪个算法在最坏情况下的时刻凌乱度是0（8）？a.堆排序b.快速排序c.归并排序d.基数排序11

18、.给定一个算术表达式x。x的骤瞰平法是a*b+c*d-e,且x的前缀方法是+*ab>cde。那么，x 的后缀方法是啥？a. acd*e-b*+ b.ab*cd*+e- c. cd*e-ab*+d.ab*cd*e-+12 .给定一棵空的avl树，顺次把13, 24, 37, 90, 53逐个刺进该树，在此进程中要坚持该树为avl 树（假定左子树的元素要小于右子树）,则究竟得到的avl树的高度是（）,树根是（）.a.3, 37 b. 3,24 c. 4, 37 d. 3, 5313 .下面哪个函数跟着n增大而增加得最快？（）.a. 100n2log2h b. n（log2nyc. n1-1

19、 d. tv + 1000nlo&n14、一个有n个极点的无向图最多有（）条无向边（假定该图无自环）.a. n b. n（n-l） cn（n-1） d. 2n15、一棵高度为k的二叉树最多有（）个节点a. 1 b. 2-1 c. 2k1 d. 2k+l二、简答题（共55分）1 .（11分）给定一个整数数组4,632,157）.假定用选择排序算法对数组中的整数进行从小到大排 序.请写出每次迭代后数组中的状况（即每次迭代后，数组中的7个整数是如何排序的）2 .（11分）从空的二叉树初步，根据字典顿？，严肃依照二叉排

序树（或称二叉查找树）的刺进算 法，顺次刺进e, b, d, f, a, g

20、, c请画出规划二叉排序树的每一进程.3 . （10分）假定一个堆为（56,38,42,3025,403520），则顺次从中删去两个元素后得到的堆是啥？ 需求商出进程.4 .给定一个空的哈希表，顺次把键12, 34, 55, 54, 13,21, 19, 70刺进到哈希表中。假定选用的哈希函 数是h（k）=k mod 11,选用线性探查（linear probing）来处置冲突（1）当上述键值悉数刺进后，请画出哈希表的状况.（6分）（2）假定每个键值被查找的概率对等，请核算出均匀有找长度（average search length） （6分）下标012345689101键15.给定图g如下第

21、3页共4页（1）请找出并画出图g的一棵最小价值生成树.（5分）（2）请画出图g对应的邻接矩阵. （6分）三、编程题(共50分)1.(10分)以下是一个(不无缺的)直接刺进排序算法的代码，请根据注释的提示把短少的代 码弥补无缺.void insertion_sort(int entryf int count)( 一int first_unsorted;/ position of first unsorted entryint position;/ searches sorted part of listint current;/ holds the entry temporarily remov

22、ed from listfor(first_unsorted = 1; firstlynsorted < count; first_unsorted+) – -if(entryfirst_unsorted < entryfirst_unsorted – 1) -/please complete the code here2. (15分)逆奘铢表:写一算法逆置带头结点的单链表l,需求逆置后的单链表使用i中的原结点, 不可以以从头请求结点空间.链表结点的声明如下，templote <class entry>struct nodeentry data;node<entry

23、> . next;k请完成下面的函数:void reverse (nodc<entry>* l)3. (25分)写一个算法，逐层遍历一棵二叉树(从上到下，从左到右).以下是二叉树及二叉树 中的节点的声明:template <class entry>class binary_tree public:binary_tree();void loyer_order(void(visit)( binary_node<entry> &);protected:binary_node<entry> root;k -template <dass

24、 entry>struct binary_nodeentry data;binary_node<en try> . left;binary_node<entry> * right;binary_node();binary node(const entry &x););请完成下面的函数:void layer_order(void(*vi$it)( entry &).第4页共4页2014年中山大学912专业基础(数据规划)考研真题中山大学二o一四年攻读硕士学位研讨生入学考试试题类别代码:912类别称号:专业基础(数据规划)考试时刻:i月5日下午考生须知

25、悉数答案一概写在答题纸上， 答在试题纸上的不计分！答阚要写 清题号，不必抄题.一、单项选择题(每题2分，共40分)u算法凌乱度一般是表达算法在最坏情况卜所需要的日箕餐。一般不必来表达算法凌乱度的表 达式为(卜(a).贝苏)(b),0(100)(c), oinlcgn)(d),0(1.52 .数据规划有四类根柢结的，不是其四类规划之一的是().(a).集结(b).线性规划(c).存储规划(d),槽形规划3 .在存储信息进程中.经过对美健字的核算来礴定其存储方位的数据规划是(a). haah 表(c),卷式规划(d).二叉查找树)，次序规划4 .有关单向链表的正确描绘是( 羽(a)在0(1)时刻内

26、找到指定的要害词(b),在刺进和删去操作时无需移动链表结点(c).在。(i)时闾内眈除指定的美他字(d).单向链表的存储功率高于数组的存辅功率5 .假定h。劭是不带头结点的双向循环鞋的头结点指针.判别链表为空的条件是(),(a) . head = null(b) . head->next = head(c), head .next = null(d). heajd->next = null6 .鄙人列关于*字符串”的陈述中，正确的描绘是( 卜(a),字符串必定有一个结束符j空串呜“空白串唬同一个意义7,关于行列的不正确描绘是)(a). fifo(c),可造访行列中任何元

27、素(b).字符串只能用接连存储空间来存储(0).字符串是一种特别的线性表(b).可用集表完成动态行列(d). h用动态接连存储空间完成动态行列(b). rc旷(rcari- 1) % qsize(d). front = (front +【)% qsi了_e8.假定循环行列的长度为qsig 其头、足下标分期:为from和re* 熟行列不满的情况卜，"入 队”后相应下标改变的语句为(),(a), rear- rear+ l(cx front = fiont + 1考试结束，试题随答题纸一同交回.第1页共7页9,用健表来完成仓库，next是域表结点中的指针字段，top为栈顶指针.在断定仓库

28、非空的情况 下，出栈的语句是()，其间:一切变量都合法界说了，free(point)是开释指针point所指 向的存储空间.(a). top = top->next;(b). free(top); top = top->next;(c). top = top->next; free(top); (d). pt=top; top = top->next; free(pt);10 .设a1010为一个对称矩阵，数组下标从初步.为了节约存储，将其下三角有些按行 存放在一维数组b0.54。b40所对应的数组元素()(a). a381(b).a28(c). a(3r(d). a2

29、7111 .若一棵二叉树的后序和中序序列别离是班6m和期於，则其先序序列是().(a), abdfec(b). abdefc(c). acbdtf(d). acbefd12 .用一维数组来存储满二叉树，若数组下标从0初步，则元素下标为削q0)的左子结点下标是 (x不思考数组下标越界疑问)(a).见 1(b). 2k(c). 2k+l(d). 2h213 .假定71和勿是二叉查找树7的支配子树，h(7)标明树t的高度。若树丁是4%树，则 ()(a), nm – hu6 = o(b). 7/(71)-g) =1(c). hm – h(tr) w 1(d).附-hg)" 114 .用邻接矩

30、阵存储有个极点(0,1,41)和e条边的无向医(0攵(止1)/2)。在图中没有无向边 ayxogj"")的情况下，添加此边后，批改邻接矩阵的时刻凌乱度是().(a). 0(1)(b).(c). o(e)(d). o(n+e)15 .用邻接矩阵存储有个极点(0,1,外1)和e条边的有向图(0女。(1)。核算结点(04e)16 .下列排序算法中，时刻凌乱度最差的是().(a).选择排序(b).归并排序(c).快速排序(d),堆排序17 .对，个数进行排序时，对根据

31、比照的排序算法，其时刻复朵度下界为()。(a).。(炉)(b). 0(1。耿)(c). %1。即)(d). %)18 .用基数(桶)排序算法对仅由字母和数字构成字符串进行排序(不区别字母巨细写)时，需要桶的 个数是().(a). 10(b). 26(c). 36(d). 6219 .假定有个无序要害词，有关其查找算法的不正确描绘是().(a).要害词可存储在数组中(c).要害词可存储在单向链表中(c).最坏查找功率为0(%)(d).均匀查找功率为0(1。改)20 .鄙人列算法中，求连通图的最小生成树算法是().(a). dfs 算法 (b). kmp 算法(c). dijkstra 算法 (d

32、). kruskal 算法二、答复题(每题10分，共50分)1 .已知一个无向图的极点集为 l2,3,4,5,6,7,其邻接矩阵如下所示(0.无边小有边).123 45 671010 11 00-2101 11 103010 11 104111 00 005111 00 106011 01 017-000 00 10.(1) .画出该图的图形:(2) .根据邻接矩阵从极点4 进行宽度优先遍历(同一个结点的邻接结点按结点编号的巨细 为序)，值出相应的宽度优先遍历树。2 .筒单描绘求图最小生成树的prim算法(普里姆算法)的根柢思维，并按算法进程从结点d开 始，列出图2的最小生成树的求解进程.3

33、 .简略叙说兼并排序算法(merge sort)的根柢思维.按递加次序对下面所给数值进行排序，并按 进程列出每步排序后的数位序列,假定在排序进程需要区别时，用函数14,来处置.待排序的数值序列:87 56 10 23 44 83 724 .己知有下列13个元素的散列表:012345678910n12205043 6957 j 6263其散列函数为人(wo = (3key + 5) % m(m=13),处置冲突的办法为线性勘探再散列法，探查序 列为:九= s(zey) + 4)%m, 4= i, 2,3,，加问:在表中对要害词50和56进行查找时，所需进行的比照次数为多少？顺次写出每次核算 公式

34、和值。5.假定 在通讯中，字符gb,g&e,工g呈现的频率如下:a: 10% b: 12%c:7% 4 21% e: 9% f28% g: 13%(1)根据huffman算法(赫夫曼算法)画出其赫夫曼树；(2)给出每个字母所对应的舜夫曼携码，规则:结点左分支边上标0,右分支边上标1；(3)核算其加权途径的长度wpl.三、阅览了解题，按空白编号填写相应的c/c+言语语句，以完成函数功用。(每空2 分，每题10分，共30分)1.假定界说了下面的链式仓库类，试编写有关成员函数。struct node int key;nodepublic:node() next = null;class st

35、ack public:siacko top = null; ;stacko；bool push(const int &key);bool empty() return (top=null); ; private:node return t

36、rue;)(2)析构函数stack。:开释仓库所用的一切存储空间.stackstack。(node *pt;while (4) pt = top;. ;delete pt, ) )2 .假定用不带头结点的单向链表存储一元多项式，并按指数有序存储(从大到小).其链表结点的 规划界说如下:typedef struct _pnode int coef;系数int expn;/指数(规则:指数加)struct pnode *next; pnode;(1)函数pnode *copy(pnode *p】):把pl指向的多项式仿制一份，并回来新多项式的首地址 (不思考请求结点内存失利的情况).pnode c

37、opycpnode *p1)(pnode pnode，p1, pnode p2):核算多项式pl pl xp2,其间；p2是一个多项式结 点。运算进程中，不

38、思考数值的溢出疑问。void time(pnode *p1, pnode p2)(pnode *pt;for (pt = pl; pt != null; pt = pt->next) 假定:pl是多项式+的首地址，p2 = (-4,2),即:p2为实施time(pl,p2)后,pl指向的多项式为:-? + 8-40?o"null“null 且"null 其他3 .假定二叉树txt/。“ tg中叶子数的界说如下:-0leaves(t)= < ileaves(7/j + leave"")已知二叉树的结点界说如下:typedef struct bi

39、nnode int key;struct -binnode *lchild, *rchi】d; binnode;(1)函数leaves(root)是求以结点root为根的二叉树中的叶子数.int leaves(binnode troot)if( root = null ) return 0;if( )return 1;return (); 函数postorder(rooi)是后序遇历以结点root为根的二叉树。 void postorder(binnode troox)print及“key: %dnn, rool->key); )第7页共7页四、算法方案题(每题15分，共30分)用c/c

40、+言语完成下面函数的功用.1 .假定用链表存储集结，空链标明空集.存储集结的链表结点界说如下: lypedef struct _element int element;集结元素struct element *next; element;/集结的结点界说例如:*=11,22, 8=9这些集结的存储链表如下匿所示。2211null(1) element *union(element *af element *b),其功用是生成集结力和打的并集链表,回来并 集链表的头指针(不思考请求结点失利的情况).(10分)(2) void display(char name, element *a),其功用是显

41、示集结力中的元素列衰，其间:name 是集结a的符号名或任何字符串.(5分)例如有下列语句:element a,.b, *c;c = unionfa. b); c是集结/和8并集的首地址，集结4和8已按需求存储好display(ua=a);输出成果:a=11,22)display,set b:”, b);输出成果:setb:2 .已知二叉查找树(binary search tree)或二叉排序树(binary serling tree)的结点界说如下:typedef struct _bsnode int key;struct bsnode lchild, *rchild; /左子树的关钝字b根

42、的小，右子树的要害词匕棍的大 bsnode;编写函数int lnsert(bsnode root, int key),其功用是在以结点*root为根的二叉查找树中刺进 关犍字key。若刺进成功，则返叵0.若要害词已存在，则回来1.若请求结点失利，则回来2.2013年中山大学867专业基础(数据规划)考研真题中山大学考生须知悉数答案一概写在答题纸匕 答在试题纸上的不计分！请用蓝、 黑色摄水笔或圆珠笔作答.答腴要 写清题号，不必抄题，二。一三年攻读硕士学位研讨生入学考试试题类别代码:867类别称号:专业基础(数据规划)考试时刻:1月6日下午 一、单项选择题(诲题2分，共40分)l算法凌乱度一般是表

43、达算法在最坏情况下所需要的核算量,假定算法出在处置n个数据的时 间爱杂度为。(1),算法也在处置n个数据时除10次接连调用算法从外，其它有些的时刻复 杂度共为0(1).那么，算法色的时刻凌乱度为()(a). on(b). 0(1。)(c),仪0/1)(d). 0(1)2 .按存储空间的可变特性，可把数据规划的存储方法分为()(a).静态存储和动态存储(b),线性存储和非线性存储(c).次序存储和链式存储(d).内存存储和外存存储构3 .在存储信息进程中，用要害词巨细来断定存储方位的数据规划是()(a). hash震(8),二叉查找树(c),链式规划(d).次序规划4 .有关双向链表的正确描绘是

44、()(a).在时刻内找到指定的要害词位).可从缱表中的任意结点找到头结点(c).在。(】)时问内删去指定的要害词(d).结点接连存储，在。时刻内断定前后结点5 .鄙人列关于“字符串”的陈述中，不正确的描绘是()(a).字符串是 种特别的线性表(c).字符串的长度有必要大于零6.关于雄栈的不正瑜描绘是()(a).堆找可用数组来完成 f1lo(b).字符串可以接连存铭，也可以链式存储(d). “空串”与“空白串”不是同一个意义(b)可造访枝顶和柱底元素(d), l1fo，假定循环行列的长度为qsizu，其头、尾下标别离为front和ruaj.在还可“入队”的情况下,核算行列中已有的元素个

45、数为()(a), front – rear + 1(c). (front rear+qsizc+1) % qsizc(b). rear – front + 1). (rear front-i-qsizc+1) % qsize考试结束，试期和草稿维随答题纸一同交回.8 .用链表来完成仓库，next是链表结点中的指针字段,top为栈顶指针。pt为其时待压栈的结点 指针(非空)，有关压栈信息已存储好.压栈的语句是()(a). top = pt;(b). pt->next = top;(c). pt->next = top = pt;(d). pt->next = top, tap

46、= pt;9 .假定head是不带头结点的单向循环链的头结点指针.判别链表为空的条件是()(a) . headnext = null(c). head = null(b) . head->next = head(d). head->next = null10 .设a1010为一个对称矩阵，数组下标从00初步.为了节约存储，将其下三角有些按行 存放在一维数组b0.54 b30所对应的数组元素().(a). a72(b). a73(c).a82(d). a8311 .若一棵二叉树的先序和中序序列别离是abfbdc和bfhdcc,则这今后序序列是()(a), bfdeac(b). fbed

47、ca(c). fbdeca(d). dbefca12 .用一维数组来存储满二叉树，若数组下标从0初步，则元素下标为如t>0)的父结点下标是 () (a). lv2j(b). l(m)/2j(c).r(ar-iy21(d),旧2113 .对任意一颗二叉树t,故7)标明树7的高度.若树7富含个结点，那么，()(a).财=佻0(b). h(t) < 8吵)(c). h(t) = 0(1。改)(d). h(t) 2 ocogw)14 .用邻接矩阵存储有个极点(0,1,1)和e条边的有向廛(0g(比1).在邻接矩阵中删去结 点的时刻凌乱度是()(a).o(l)(b). o(h)(c). 0(

48、e)(d).o(/e)15 .用邻接矩阵存储有个极点(0,卢-1)和e条边的有向图(0幺9(止1)。判别结点i到结点 大0玄js1-1)有边的时刻凌乱度是() (a).o(0(b). o(n)(c). 0(e)(d). o(w+e)16 .下列排序算法中，均匀时刻凌乱度为如2)的是()(a).刺进排序(b).归并排序(c).快速排序(d).堆排序17 .对，个数进行排序时，根据比照的排序算法至少褥要比照的次数为()(a), a】。耿)(b). o(n)(c). 0(闭则(d).5方)18 .用基数(桶)排序算法对32位无符号数按字书进行排序时，即:先用最一个字节(最低字节)进 行排序，再顺次用

49、第二、第三和第四个字节进行排序。得要桶的个数是() (a).8(b). 16. (c). 128(d). 25619 .假定有个待查找要害词，有关减半查找算法的不正确描绘是().(a).最坏攫索功率为(b).均匀查找功率为5lo即)(c).查找功率为0(1。明)(d).数据有序且次序存储20.鄙人列算法中，求图中两点之间最短途径的算法是()(a). dfs 算法 (b). prim 算法(c). dijkstra 算法 (d). kmp 算法二、答复题（每题10分，共50分）1 .已知一个无向图的极点集为,4c,4e/g，其邻接矩阵如口所示（0-无边,1 有边）,6 10 111 1 00 0

50、 00 0 00 0 10 0 11 1 0图2 （第2题用图）（1） .画出该图的图形；（2） .根据邻接矩阵从极点4 进行深度优先遍历（同一个结点的邻接结点按结点的字母序为 序），画出相应的深度优先遍历树。2 .简略描绘求图最小生成树的kruskal算法（克鲁斯卡尔算法）的根柢思维，并按进程列出图2的 最小生成树的求解进程.3 .简略叙说堆排序算法（heapsort）的根柢思维.按“由小到大依序所给的数值，并按排序进程列 出每次已堆化好的特排数值序列。可不列出“已排好”的数值和难化进程中的堆形状或数值序 歹ik假定给额定信息，将判别这些信息的正确性.初始己堆化好的待排数值序列:93 67

51、 78 15 34 40 334 .已知有下列13个元素的散列表:0123456789 10 11 1263 | 20 50 i 43 | 44 | 49 才其散列的数为人（太"）=（3幻+ 7） %加（加=13）,处置冲突的办法为线性勘探再散列法，探查序列为:ai=（a（t即） + 4）%m, 4= 1,2,3,三-1问，在表中对关健字50和36进后查找时，所 进行的比照次数为多少？顺次写出每次核算 公式和值.5 .假定在通讯中，字符。，“。，&4工8呈现的菠率如下:a: 27% b: 20%c:16% d: 19% e: 9% f: 2% g: 7%（1）根据huffin

52、an算法（荔夫曼算法）画出其赫夫曼树；（2）给出每个字母所对应的赫夫曼编码，规则:结点左分支边上标】，右分支边上标0:（3）核算其加权途径的长度wpl三、阅览了解题，按空白编号填写相应的c/ch言语语句，以完成函数功用。(每空2 分，每题10分，共30分)1.假定界说了下面的链式行列类，试编写有关成员函数.struct node int key;node *next;public:node。 next = null;node(int key, node *next=null) key = key; next 口 next;);class queue public:queue() front =

53、 rear = null; ;yueueo;bool append(const intbool empty。 return (frontnull); ; private:node front, *rear;)；(1)成员函数appcnd(const int若请求不到存储空间，回来false,否则，把参数item附加到行列尾部，并回来true。bool queue: :append(const int &item)(node *pt = new node(item);if (pt = null) return false;if ()front = pt;else ;(3)；return

54、true;)(2)析构函数依eueo:开释行列所占用的一切存储空间。queue: :-queue()node *pt;while ()pt = front;(5 ；delete pt;)2.假定用不带头结点的单向链表存储一元多项式，并按指数有序存储(从大到小或从小到大).其 链表结点的规划界说如下:typedcf struct _pnode int coef;/ 系数int expn;/指数(规则:指数x)struct _pnode 拿next; pnode;(1)函数reverse(pnode *p1):按多项式指数巨细回转多项式，指针*pl指向多项式的首结 点.回转后，指针*p

55、1仍指向该多项式的首结点.void reverse(pno<ie *p1)(pnodc *exp, *ptl, *pt2;exp = *pl;if (exp = null) return;ptl i

56、nt i;value = 0;fbr(pt = pl;pt != null; pt = pt->next) ;for (i = 0; i < pt->expn; i+)(53 ;value- item;)return value;)3.假定二叉树六v, %”踪中结点数的界说如下:rot是空树(= l rnodescto+nodesctr)其他已知二叉树的结卬>(1)函数nodes(root

57、)是求以结点root为根的二叉树中的结点数。int nodes(binnode *root)(if (1) return 0;return (2);)(2)函数lnorder(root)是中序遍历以结点root为根的二叉树 void inorder(binnode *root)(if (3) (；prmtf(ukcy: %dnn, root->kcy);:)（接下页）第6页共7页四、算法方案题(每题15分，共30分) 用c/c+言语完成下面函数的功用。1 .假定有集结和8,其笛卡尔积c为4×8,且ich/1冈身.假定用硅表存储集结，空链标明交集，存佬根柢集结和笛卡尔根的性表结点界说如f:

58、 typedef struct _element int element;/根柢集结中的元素struct _elcment *ncxt; element;/根柢集结的结点界说typedef struct -elements int elementl,elcincnt2; / 笛卡尔积中的元素,dementi ea, elcment2gj5struct .elements *next; elements;笛r尔枳的结点界说例如:42,3, oaxb. />)这些集结的存储链表如下图所示.(1) elements descartesfelement element b),其功用是生成存储笛卡

59、尔积的链表， 并回来该疑表的头指针(不思考请求内存空间失利的情况)(9分)(2) int number(elements *c),其功用是获取笛卡尔积c中的元素个数(6分)例如有下列语句:element *a, *b;elements *c = descartes(a, b);集结力和3己按需求存储好int nc = number(c);/nc 的值为 42 .已知二叉查找树(binary search tree，二叉排序树(binary sorting tree)的结点界说如下:typedef struct bsnode int key;struct -bsnode lchild, *rchild; /左子树的要害词比根的小，右子树的要害词比根的大 bsnode;编写函数find(bsnodc *root, int key),其功用是在以结点root为根的二叉查找树中找“比参数 key大的最小值，若找不到，则回来null,否则，回来该结点地址.第7页共7页2012年中山大学909专业基础(数据规划)考研真题中山大学考生须知悉数答案一概写在答题纸匕 答在试题纸上的不计分！请用蓝， 黑色墨水笔或圆珠笺作答.答题要 写清题号，不必抄题。二。