杭州电子科技大学数据结构2011--2019年考研专业课真题.docx

《杭州电子科技大学数据结构2011--2019年考研专业课真题.docx》由会员分享，可在线阅读，更多相关《杭州电子科技大学数据结构2011--2019年考研专业课真题.docx（99页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、杭州电子科技大学2019年攻读硕士学位研究生招生考试数据结构试题(试题共五大题，共6页，总分150分)姓名 报考专业 准考证号【所有答案必须写在答题纸上，做在试卷或草稿纸上无效！】一、判断题(本大题共10小题，每小题1分，本大题共10分)1.数据的逻辑结构说明数据元素之间的顺序关系.它依赖于计算机的存储结构.() 2,对任何数据结构链式存储结构一定优于顺序存储结构。()3 .循环队列通常用指针来实现队列的头尾相接.()4 .若栈的入栈序列为1,2,3,4,5,6,则其出栈序列可以是3,2,5,6,14 ()5 .用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关.()6 .取广义表的表尾就

2、是返回广义表中最后一个元素。()7 .稀疏矩阵压缩存储后，必会失去随机存取功能。()8 .关键路径是AOE网中从源点到终点的最长路径。()9,对一棵二叉树进行层次遍历时，应借助于一个栈。()10.在用弗洛伊德算法求解各顶点的最短路径时，每个表示两点间路径的 pathkpj一定是 pathk LJ的子集(k=l,2,3，.n).()二、单项选择题(本大题共15小题，每小题2分，本大题共30分)1 .从逻辑上可以把数据结构分为()大类A.动态结构、静态结构 B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构2 .在一个二维数组A中，假设每个数组元素在长度为3个存储单元，行下标i

3、 为。8,列下标j为。9,从首地址SA开始连续存放。在这种情况下，元素 A85的起始地址为()A. SA+141B.SA+144 C. SA+222 D. SA+2553 .在双向域表指针p的结点前插入一个指针q的结点操作是()A. p-Llink=q;q-Rlink=p;p-Llink-Rlink=q:q-Llink=q;B. p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink;C. q-Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=q;p-Llink=q;D. q-Llink=p-Llink;q-Rlink=

4、q;p-Llink=q;p-Llink=q;4 .在一个长为n的顺序表中删除第i个元素和第i个位置插入一个元素的时间复 杂度为()A.nB. i-1C. n-i D, n-i+15 .对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是 ()A. head=NULL B. headnextNULL C. headnext=head D. head!=NULL6 . 一个栈的输入序列为1,2,3,若输出序列的第一个元素是n,输出第i(l=i nB, n , n-1 C. n*2-l, n2 D. n, n+17 .已知有向图 G=（V, E）,其中 V=V1, V2, V3, V4

5、, V5, V6, V7, V8）.E=, , , , , , , , ,下列哪个序列不是G的拓扑有序序列（）。A. VI, V2, V3, V4, V5, V6, V7, V8B. V3, VI, V2, V4, V5, V6, V7, V8C. V1,V3,V2,V4,V5,V6,V7,V8D. VI, V3.V4, V2,V5,V6,V7, V88 .对线性表进行折半查找，表中元素的存储方式及元素排列要求为（）.A.链接方式存储，元素无序 B.链接方式存储，元素有序C.顺序方式存储，元素无序 D.顺序方式存储，元素有序9 .设哈希表长为15,哈希函数是H（key）=key机3,表中已有数

6、据的关键字为15, 22, 50, 13, 20, 36, 28,现要将关键字为48的结点加到表中，用二次探测再 散列法解决冲突，则放入的位置是（）.A. 8B. 3C. 5D. 910.对序列16, 8, 6, 7, 21, -2, 4进行排序，进行一趟后数据的排列变为4, 8, -2, 7, 21. 6, 16 t则采用的是（）排序.A.选择8.快速C.希尔D.冒泡三、填空题（本大题共15空，每空2分，本大题共30分）1 .元素总数基本稳定的线性表，采用 存储结构，能在很少进行插入和删除操作的情况下，以最快的速度存取表中元素.2 .长度为n的列表，被等分为n/k段，每段长度为k,不同段之间

7、的元素不存在 逆序。对该列表进行插入排序的最坏时间复杂度为.3 .顺序栈用datatl. n存储数据，栈顶指针是top,则值为x的元素入栈的操作 ft.4 .树在计算机内的表示方式有一（1）_，5 . 一棵度为仇的树有n个节点。若每个节点直接用垃个链指向相应的儿子，则 表示这个树所需要的总空间是n*（m+l）（假定每个链以及表示节点的数据域都是 一个单位空间）.当采用儿子/兄弟（First Child/Next Sibling）表示法时，所 需的总空间是6 .设深度为d （只有一个根结点时，d为1）的二叉树只有度为0和2的结点， 则此类二叉树的结点数至少为.7 .如果一个完全二叉树最底下一层为

8、第六层（根为第一层）且该层共有8个叶结 点，那么该完全二叉树共有个结点。8 . G是一个非连通无向图，共有30条边，则该图至少有 个顶点.9 . Dijkstra短路径算法从源点到其余各顶点的短路径的路径长度按 次序依次产生，该算法弧上的权出现 情况时，不能正确产生最短路径.10 .在一个大小为K的空散列表中，按照线性探测冲突解决策略连续插入散列值 相同的N个元素（NK）=问：此时，该散列表的平均成功查找次数是.11 .设用希尔排序对数组归7, 35, -10, 0, 48, 22, 1. 8, 9, 7进行排序，给 出的步长（也称增量序列）依次是4, 2, 1则排序需 趟，写出第一趟结束后，

9、数组中数据的排列次序.四、简答题（本大题共5题，本大题共40分）1 .（本题5分）斐波那契数列Fn定义如下:F0=0, Fl=l, Fn=Fn-l+Fn-2, n=2,3.,如果用大0表示法，试给出递归计算Fn时递归函数的时间复杂度是 多少.2 .（本题8分）假设一棵二叉树的层次次序（按层次递增顺序排列，同一层次自 左向右）为ECRAHXMS,中序序列为ACEHMRSX.请画出该二叉树，并将其转换为 对应的森林.3 .（本题8分）下图是带权的有向图G的邻接表表示法，求： （1）以结点VI出发深度遍历图G所得的结点序列；（2）从结点VI到结点V8的最短路径；4.（本题 10 分）对输入关键字序列

10、 501, 89 , 513 , 60 , 906, 170 , 879 , 245, 653, 460 进行：（1）建立堆排序的初始堆（小顶堆），要求画出主要过程.（2）输出最小值后，如何得到次小值.（并画出相应结果图）5.（本题9分）设一组数据为1,13,27,30,56,70,9, 12,23,现采用的哈希函数 是H（key）=keyM0D13,即关键字对13取模，冲突用链地址法解决，设哈希表 的大小为13（0. 12）,试画出插入上述数据后的哈希表.五、程序题（本大题共3题，本大题共40分）1 .（本题10分）设单链表的表头指针为h,结点结构由data和next两个域构 成，其中dat

11、a域为字符型.写出算法dc（h,n）,判断该链表的前n个字符是否中 心对称.例如xyx,xyyx都是中心对称.2 .（本题15分）在二叉树中查找值为x的结点，试编写算法（用C语言）打印 值为x的结点的所有祖先，假设值为x的结点不多于一个，后试分析该算法的 时间复杂度.3 .（本题15分）设有顺序n个盒子，每个盒子有一个小球，每个小球的颜色是 红，白，蓝之一.要求重新安排这些小球，使得所有红色小球在前，所有白色小球 居中，所有蓝色小球居后，重新安排时对每个小球的颜色只能看一次，并且只允 许交换操作来调整小球的位置.杭州电子科技大学2011年攻读硕士学位研究生入学考试数据结构试题(试题共五大题，5

12、页，150分)姓名 报考专业 准考证号【所有答案必须写在答题纸上，做在试卷或草稿纸上无效！】一、选择题(每小空2分，共28分)1 .在下列数据结构中 具有先进先出特性，具有先进后出特性.a：线性表 b：栈 c：队列 出串2 .如下关于串的陈述中，正确的是 、.a：串是数据元素类型特殊的线性表b：串中的元素是字母c：串中若干个元素构成的子序列称为子串d：空串即为空格串3 .对广义表 A= (a) , (b), (c)执行操作 gettail (gethead(gettaiMA)的结果是：.执行操作 gethead(getlail (gethead(A)的结果是：.a： () b： (5) c：

13、(a) d： (b) e： (c)4 .任何一个连通网的最小生成树.a：只有一棵 b:有一棵或多棵 c:一定有多棵d:可能不存在5 .在有n个结点的二叉树的三叉捱表表示中,空指针数为.a:不确定 b: n c: n+1 d: n+26 .关键路径是指在只有一个源点和一个汇点的有向无环网中源点至汇点 的路径.a:瓠的数目最多 b:弧的数日最少 c:权值之和最大 d:权值之和最小7 .设无向B8G= (丫5)和& (V； E),若G.是G的生成树，则下面不正确的说法是.a: G是G的子图b: G,是G的连通分量c: G是G的无环子图d: G,是G的极小连通子图且V= V8 .下列杳找方法中 适用于

14、查找单链表.a:顺序查找b:折半查找 c:分块查找 d: hash查找9 .卜列排序方法中，是稳定的；具有最好的平均性能；当待排 序序列的关键字次序为倒序时，若需为之进行正序排序，下列方案中以 为佳.a:堆排序 b:快速排序 c:直接插入排序d:简单选择排序1 .数据结构通常有下列4类基本结构：线性结构、树型结构、图型结构、.2 .线性表的 存储结构是以物理位置来表示数据元素之间的逻辑关系的.而线性表的 存储结构是通过指针保持数据元素之间的逻辑关系的.3 . n个顶点的强连通图至少有 条狐，至多有 条孤.4 .若某一二叉树按中序遍历可得到有序序列，则该二叉树是.若某一二叉 树从根结点到其它任一

15、结点的路径上所经过的结点序列按其关键字递增有序， 则该二叉树是.5 .若对完全二叉树中的结点从1开始按层进行编号，设最大编号为n,则编号为i 的结点(lin)的父结点编号为 ;所有编号 的结点为叶子结点.6 .压栈次序为a、b、c.则不可能得到的输出序列是.7 .已知待排序序列为：33,34, 7,28,38,11,65,15,37,20.则：以第一个元素为枢轴的快速排序一趟分划的结果是.堆排序初始建堆(小顶堆)的结果是.希尔排序第一趟(增量为3)的结果是.三、图示结构题(每小题8分，共40分)1 .已知某二叉树的先序遍历次序为：ABCDEFG.中序遍历次序为：BADCFEG .(1) 画出该

16、二叉树形.(2) 给出该二叉树的后序遍历次序.1 3)画出中序线索化后的二叉树形.g2 .已知某无向图如右图所示：(1)画出该图的邻接表存储结构.(2)画出该图的邻接矩阵存储结构.7(3)根据你所绘制的邻接表给出DFSOKD及BFS次序.3 .依序将关键字20、40. 30、80、70、50, 60、10插入到一棵2-3树中(初始状 态为空)，(1)请画出该B-树.(2)再先后删除关键字40、60,画出删除后的B一树.4 .设哈希函数为H(key)=key mod 7,用链地址法处理冲突，若依次在哈希表中插入12 个元素 32、65、83、25、74、21、33、18, 61、27、47、28

17、.(1) 画出它们在表中的分布情形.(2) 计算其平均成功的查找长度.5.假设用于通讯的电文仅由8个字符A、B、C、D、E、F、G、H组成，字符在电文 中出现的频率分别为3、12, 9、23、2、17, 2k 13(I)画出你所建的哈夫曼树，(2)给出每一字符的哈夫曼编码.1. Status Al(SqList L, ElemType cur_e, ElcmType &next_e) (/初始条件：顺序线性表L已存在 int i=l;ElemType *p=L el cm;whiled L. length & *p != cur_e)( if p+: )if(i = L. length) re

18、turn INFEASIBLE;else(next_e = *+p;return OK;2. Status A2(LinkList L, int i, ElemType e) (初始条件：带头结点的单链表L已存在 int j = 0;LinkList p = L, s;while( p & j next; jf)if(!p II j i-1)return ERROR：s = (Li nkLi st)malloc(sizeof(LNode);s-data = e:s-next = p-next;p-next = s; return OK：3. int A3(LinkQueue Q)(/初始条件：

19、链队列Q已存在int i = 0;QueuePtr p：P = Q. front：while(Q. rear != p)i+；p = p-next：return i; 4. void A4(BiTree T,Status(*Visit)(TEleraType) /初始条件：二叉树T已存在if(T)A4(T-lchild, Visit);A4(T-rchi Id, Visit);Visit(T-data);5. int A5(SSTable ST, KeyType key)(初始条件:顺序表ST已存在int i;ST. elem0. key二key;for(i = ST. length; ! E

20、Q (ST. elemi. key, key); -i); return i;)6. int A6(SqList L, int i)I 初始条件:顺序表L已存在int min;int j,k;k = i;min = L. ri. key;for(j = i + l;j = L length： j+)if(L. rj. key next = rear)return ERROR;(1) :rear-next-next=p-next:e=p-data:if (p=rear) ：(3)： return OK;)12 . BiTree SearchBST(BiTree t, KeyType key)(在

21、根指针t所指的一义排序树中递！H地杳找某关键字等于key的数据元素. 若有找成功，则返回该元素结点的指针，否则返回空指针 if (!t)(1)：else if (t-data. key = key)return t;else if (t-data. key key)(2);else ：四、简答题(本大题共6小题,每小题6分，本大题共36分)1 .某二叉树的先序遍历序列为：JCBADEFIGH,中序遍历序列为ABCEDFJGIH.(1)请画出该二叉树：(2)画出其中序线索二叉树.2 .对如心所示的有向图，(1)画出其邻接表；(2)针对的邻接号 写出从顶点1 开始的深度优先和广晟优先遍历序列.3

22、.设数据元素的美键字序列为( 10, 14.7,23,80,65, 54,90, 36,47.23),依次输入这 些元素，创建一棵平衡的一叉排序树(AVL啊)，请逐 画出每插入一个元素后的AVL 树的形态.4 .什么是稳定抻序方法？拈尔排序是不是稳定持序方法？简单选打揖序是不是稔 定格序方法？5 .设哈希表长度是16,哈希函数为H(key)=key mod 13,用线性探测再散列法处 理冲突，依次在哈依次中插入12个元素(47,38,80,45, 14,51.31. 18, 63, 72. 9, 581. (1)画出它们在表中的分布情形.(2)计算等概率时责找成功的平均齐找K度ASL6 .假设

23、用于通讯的电文仅由8个字符组成,字符在电文中出现的妆率及现有的一进 制前缀编码如卜所示：字符ABCDEFGH续率41372422023!5编码11110111010000mu11001101请问这套编码是不是最优的前缀编码？为什么？如果不是，请给出更高效的编码.五、算法设计题(本大题共3小题，每小题10分，本大题共30分) 1.设有一个不带头结点的单链表，表中元素值均不相同.试编写一个算法，删除该 单链表中元素值为x的数据元素.若删除成功,则返问irue.否则返问false.单链表的结点定义为： typedef struct LNode ( ElemType data; struct LNod

24、e next; LNode, LinkList;【以卜两膝均假设一叉树采用二叉链表存储结构，结点定义如卜： typedef struct BiTNode ITElemType data; struct BiTNode *lchiId, *rchiid;I BiTNode. BiTree; 2.设计一算法,计算给定二义树T中度为2的结点个数.3.设指针p (材空)指向一义树中的某个结点.且该结点的左4 f将均1F空，试写 出求p所指结点的中序后继的算法.杭州电子科技大学2013年攻读硕士学位研究生入学考试数据结构试题(试题共六大题，6页，150分)姓名 报考专业准考证号【所有答案必须写在答题纸上，做在试卷或草稿纸上无效！】一、是非题(每小题2分，共10分)1 .对插入、删除操作，电链衣和顺序表的时间乂杂及都“J计为(7