武汉纺织大学数学与计算机学院数据结构历年考研真题汇编

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（八）？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)。计算结点(04±1)入 度的时间复杂度是().(A).ai)(B). CKn(C). 0(e)(D). O("e)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 'Top;(l)成员函数Push(const int &key)：若申请不到存储空间，返回false,否则，把参数key压 进堆极，并返回true.bool Stack:Push(const int &key)(Node *Pt = new Node();if(Qj) return false;Pt->key = key;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 'Head JPtl, Pt2;Head = NULL;while (Pl != NULL) Ptl = (PNode *) calloc。，sizcof(PNode);Ptl-> Coef = P1 ->Coef;Ptl-> Expn = Pl->Expn;if( )Head = Ptl;else Pt2->next = Ptl; ;Pl -Pl->next;)0):(2)函数Tim«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 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