南京邮电大学2005年数据结构考研试卷
南 京 邮 电 学 院
2005年攻读硕士学位研究生入学考试
数 据 结 构 试 题
一、单选题（每题3分，共30分）
1. 设使用某算法对n 个元素进行处理，所需的时间是
T(n) = 100n log 2n + 200n + 2000 则该算法的渐进时间复杂度为 。
A. O(1)
B. O(n)
C. O(200n)
D. O(nlog 2n)
2. 设顺序表的长度为n ，并设从表中删除元素的概率相等。则在平均情况下，从表中删除一个元素需要移动的元素个数是 。
A. (n －1)/2
B. n/2
C. n(n －1)/2
D. n(n ＋1)/2
3. 如果只保存一个n 阶对称矩阵a 的下三角元素（含对角线元素），并采用行主序存储在一维数组b 中，a[i][j]（或a[i, j]）存于b[k]，则对i A. (1)2 i i j ++ B. (1)2j j i ++ C. (1)2i i j ?+ D. (1)2 j j i ?+ 4. 一棵三叉树中，已知度为3的结点个数等于度为2的节点数，且树中结点的数目为13，则度为2的结点数目为 。 A. 4 B. 2 C. 3 D. 5 5. 在基于关键字比较的排序算法中， 算法在最坏情况下的时间复杂度不高于O （nlog 2n ） 。 A. 冒泡排序 B. 合并排序 C. 希尔排序 D. 快速排序 6. 已知一棵由关键字集合{18，43，27，77，44，36，39}所构造的二叉搜索树（也称为二叉排序树），对该树进行中序遍历得到的节点序列为 。 A. 树形未定 B. 18，43，27，77，44，36，99 C. 18，27，36，39，43，44，77 D. 77，44，43，39，36，27，18 7. 一个索引文件，如果经常需要插入和删除元素，宜采用 做索引。 A. 二叉排序树 B. 二叉平衡树 C. B-树 D. B+树 8. 均匀的散列函数应当使关键字集合中的元素，经过散列函数映射到散列表中任何位置的概率 。 A. 相等 B. 最小 C. 最大 D. 一定 9. 关键路径是指AOE（Activity On Edge）网中。 A. 二叉排序树 B. 二叉平衡树 C. B-树 D. B+树 10. 堆可以是最大堆，也可以是最小堆。下列序列中，既不是最大堆，也不是最小堆。 A. （90，85，78，67，56，42，35，24，18） B. （18，35，56，24，42，78，67，85，90） C. （90，78，85，56，67，35，42，18，24） D. （18，35，24，56，42，78，67，85，90） 二、填空题（每题6分，共42分） 1. 设有n个顶点的有向图采用邻接矩阵表示，并保存在二维数组a中，则求第i个顶点的入度和出度的计算公式分别是⑴ 和⑵ 。 2.设有20个元素构造二叉平衡树，其最大和最小高度分别是 ⑶ 和 ⑷ 。 3. 某二叉树结点的中序序列为A，B，C，D，E，F，G，后序序列为B，D，C，A，F，G，E，则该二叉树的先序序列为⑸ ，该二叉树对应的森林中包括⑹ 棵树。 4. 对一个有向图进行拓扑排序，输出的拓扑序列不能包括图中全部顶点，表明此图⑺。如果此图代表一个工程之间的领先关系，当算法执行出现上述情况时，应当检查⑻ 。 5. 设对主串“bcdb cdca bcdb cdba c”和模式串“bcdb cbd”进行KMP模式匹配。第1趟匹配失败后，若使用非改进的Next函数，则下一趟将由主串的第⑼ 字符与模式串的第⑽ 字符开始比较。若采用改进的Next函数，则下一趟匹配将由主串的第⑾ 字符与模式串的第⑿ 字符开始比较。字符串中字符从1开始编号。 6. 假定散列表使用除留余数法散列函数H，key为关键字，模为M，则该散列函数的形式为⒀ 。若采用移位折叠法散列函数，散列地址取3位，设key=43256789654，则所得的散列函数值为 ⒁ 。 7. 在将中缀表达式转换为后缀表达式和计算后缀表达式的算法中，都需要使用堆栈。对于前者，进入堆栈的元素为表达式中的⒂ ，而对于后者，进入堆栈的元素为 ⒃ 。中缀表达式(a+b)/c-(f-d/e)所对应的后缀表达式是 ⒄ 。 三、解答题（每题8分，共48分） 1. 已知有向图如图1所示，并已建成该图的邻接表。使用该邻接表对此图进行深度优先遍历时，结点被访问的次序是：1，3，2，5，6，4；对其进行广度优先遍历时，结点被访问的次序是：1，3，2，4，6，5。 ⑴ 画出产生上述遍历结果的邻接表； ⑵ 分别画出产生上述遍历结果的深度优先生成树和广度优先生成树。 图1 2. 设无向图如图2所示，现采用克鲁斯卡尔算法求最小代价生成树。再加入一条新边时，为了判定是否会因此形成回路，可以使用并查集（该数据结构也用于求等价关系问题）。 ⑴ 画出所生成的最小代价生成树； ⑵ 给出在算法执行中，当生成树上有5条边时的并查集的状态。 图2 3. 设有数据元素的有序序列（22，32，35，44，48，51，57，60）， ⑴ 现采用对半查找方法查找60，请按比较的次序，列出与60做比较的表中元素； ⑵ 对半查找方法要求元素序列采用何种存储表示方法。 4. 关于图3所示的4阶B-树，回答下列问题： ⑴ 依次插入关键字70和85，画出插入后的B 树。 ⑵ 依次删除关键字14和16，画出删除后的B 树（仍从原图３中删除）。 ⑶ 你认为用于存储B-树中每个结点的存储块的大小是否应相同，为什么？ 40 14 49 58 5 1 6 42 53 60 63 72 图3 5. 使用快速排序算法对元素序列（23，43，36，30，20，54，76，28）进行排序。 ⑴ 写出对上述序列进行第一趟排序后的结果； ⑵ 待排序的元素序列处于什么状态时快速排序所需时间最长？ ⑶ 采用什么措施可改善快速排序的最坏情况时间性能？ 6. 设二叉搜索树如图4所示， ⑴ 在该树上插入元素35，画出插入后的二叉搜索树； 12 5 43 76 43 7527 4838 ⑵ 从⑴所生成的树上删除25，画出删除后的二叉搜索树。 图4 四、算法设计题（共30分） 1. (12分) 设计一个算法，按元素值的“非增”次序，打印一棵二叉搜索树（也称二叉排序树）的元素。设二叉搜索树采用二叉链表存储，每个结点有三个域：lchild, rchild, data。算法中，除二叉链表中原有的结点空间外，只允许使用若干指针变量，不允许使用额外的元素空间。 2. （18分） 已知无向图采用邻接矩阵表示，但该邻接矩阵不使用二维数组存储，而今使用一维数组g保存邻接矩阵的下三角部分元素（不含对角线元素）。请设计一个或多个函数（或过程），求无向图的各连通分量的顶点集。 2015年南京邮电大学数据结构考研初试题目 判断题（共15题*2分） 1.消除递归不一定需要使用栈，此说法() 2.稀疏矩阵压缩存储后，必会失去随机存取功能() 3.完全二叉树中，若一个结点没有左孩子，则它必是叶结点() 4.连通分量是无向图的极大强连通子图() 5.在9阶B-树中，除叶子以外的任意结点的分支数介于5和9之间() 6.在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转() 7.10个叶子结点的哈弗曼树，其高度最小为58.队列和栈不可以使用散列存储() 选择题（共15题*2分） 1.以下属于逻辑结构的是（）。 A．顺序表B.哈希表 C.有序表 D.单链表 2.下列数据中，（）是非线性数据结构。 A．栈B.队列C.完全二叉树D.堆 3.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）储方式最节省运算时间。 A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表 4.循环队列存储在数组A[0..m]中，则入队时的操作为（）。 A.rear=rear+1 B.rear=(rear+1)mod(m-1) C.rear=(rear+1)mod m D.rear=(rear+1)mod(m+1) 5.二叉树在线索后，仍不能有效求解的问题是（）。 A.先序线索二叉树中求先序后继B．中序线索二叉树中求中序后继C．中序线索二叉树中求中序前驱D．后序线索二叉树中求后序后继6.下面几个符号串编码集合中，不是前缀编码的是（）。 A．{0,10,110,1111}B．{11,10,001,101,0001} C．{00,010,0110,1000} D．{b,c,aa,ac,aba,abb,abc} 7.用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为()。 A．5B．6C．8D．9 8.下列关于AOE网的叙述中，不正确的是（）。 A．关键活动不按期完成就会影响整个工程的完成时间 B．任何一个关键活动提前完成，那么整个工程将会提前完成 C．所有的关键活动提前完成，那么整个工程将会提前完成 D．某些关键活动提前完成，那么整个工程将会提前完成 9.m阶B-树是一棵() A.m叉排序树 B.m叉平衡排序树 C.m-1叉平衡排序树 D.m+1叉平衡排序树 10.关于杂凑查找说法不正确的有几个()【南京理工大学2000一、16（1.5分）】 A.采用链地址法解决冲突时，查找一个元素的时间是相同的 实验报告 （2015 / 2016学年第二学期） 课程名称数据结构A 实验名称二叉树的基本操作及哈夫曼编码译码系统的实现 实验时间2016 年 4 月14 日 指导单位计算机科学与技术系 指导教师骆健 学生姓名班级学号 学院(系) 管理学院专业信息管理与信息系统 实习题名:二叉树的基本操作 班级姓名学号日期2016.04.14 一、问题描述 设计递归算法，实现下列二叉树运算：删除一棵二叉树、求一棵二叉树的高度、求一棵二叉树中叶子结点数、复制一棵二叉树、交换一棵二叉树的左右子树。设计算法，按自上到下，从左到右的顺序，按层次遍历一棵二叉树。设计main函数，测试上述每个运算。 二、概要设计 文件tree.cpp中在该文件中定义二叉树的链式存储结构，用队列实现二叉树的层次遍历，并且编写实现二叉树的各种基本操作函数。其中包括结点类BTNode，循环队列类SeqQueue，二叉树类BinaryTree。主函数main的代码如图所示。 三、详细设计 1.类和类的层次设计 程序定义了循环队列SeqQueue类和二叉树BinaryTree类。SeqQueue类主要是用队列实现，层次遍历。运用后序遍历思想，把树分解为左右子树和跟结点再进行左右交换并计算树的高度，最后删除二叉树。 （a ）循环队列类 （b ）二叉树类 2. 核心算法 程序利用循环队列SeqQueue 类通过不断出队并输出节点的值，将左右孩子入队直到队列为空实现二叉树的层次遍历。并运用后序遍历思想，将二叉树树分解为左右子树和根结点，利用(p -> lChild)和(p -> rChild)计算结点数目，并通过交换结点的左右子树实现左右交换，计算树的高度，最后删除二叉树。核心算法主要是二叉树BinaryTree 类中的High ，Node_num ，Exchange ，Level_traversal 四个函数，其设计流程图如下： SeqQueue -int front, rear; -int maxSize; -BTNode 数据结构B期末试卷 班级学号姓名得分 一、解答题：（共82分） 1、下列程序段或函数的时间复杂度。（10%） （1）for (int k=0;k 4、根据下图所示的树回答问题：（共13%） （1）画出该树等效的二叉树。（3%） 等效的二叉树 （2）、写出对该树进行先序、后序遍历的结点序列。（4%） （3）用带右链的先序表示法来存储此树，填写下表。（6%） 下标0 1 2 3 4 5 6 7 8 9 10 11 sibling element ltag 5、假设用于通讯的电文仅由{ABCDEFGH} 8个字母组成，字母在电文中出现的频率分别为0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10。请画出哈夫曼树并在树中标明编码情况，给出这8个字母的哈夫曼编码，最后求出WPL。（9%） 数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 6.0上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。 （3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>//头文件 #include nodetype *create()//建立单链表，由用户输入各结点data域之值，//以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"< 南 京 邮 电 学 院 2005年攻读硕士学位研究生入学考试 数 据 结 构 试 题 一、单选题（每题3分，共30分） 1. 设使用某算法对n 个元素进行处理，所需的时间是 T(n) = 100n log 2n + 200n + 2000 则该算法的渐进时间复杂度为 。 A. O(1) B. O(n) C. O(200n) D. O(nlog 2n) 2. 设顺序表的长度为n ，并设从表中删除元素的概率相等。则在平均情况下，从表中删除一个元素需要移动的元素个数是 。 A. (n －1)/2 B. n/2 C. n(n －1)/2 D. n(n ＋1)/2 3. 如果只保存一个n 阶对称矩阵a 的下三角元素（含对角线元素），并采用行主序存储在一维数组b 中，a[i][j]（或a[i, j]）存于b[k]，则对i 数据结构(C语言版) 实验报告 专业班级学号姓名 实验1 实验题目：单链表的插入和删除 实验目的： 了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。 实验要求： 建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。 实验主要步骤： 1、分析、理解给出的示例程序。 2、调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测 试程序的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。 3、修改程序： （1）增加插入结点的功能。 （2）将建立链表的方法改为头插入法。 程序代码: #include"" #include"" #include"" #include"" typedef struct node . . 示意图： head head head 心得体会： 本次实验使我们对链表的实质了解更加明确了，对链表的一些基本操作也更加熟练了。另外实验指导书上给出的代码是有一些问题的，这使我们认识到实验过程中不能想当然的直接编译执行，应当在阅读并完全理解代码的基础上再执行，这才是实验的意义所在。 实验2 实验题目：二叉树操作设计和实现 实验目的： 掌握二叉树的定义、性质及存储方式，各种遍历算法。 实验要求： 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历 的操作，求所有叶子及结点总数的操作。 实验主要步骤： 1、分析、理解程序。 2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针）， 如ABD###CE##F##，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求 所有叶子及结点总数。 实验代码 #include"" #include"" #include"" #define Max 20 ertex=a; irstedge=NULL; irstedge; G->adjlist[i].firstedge=s; irstedge; R[i] 留在原位 数据结构Ａ复习要点 第1章基础知识 算法与数据结构（数据结构概念、逻辑结构、数据存储结构示等） 数据抽象和抽象数据类型（数据结构规范、实现） 算法分析的基本方法（时间复杂性、空间复杂性） 第2章线性表 线性表的顺序和链接表示 理解在顺序表、单链表上实现线性表运算，能设计相应算法程序 顺序和链接表示的优缺点比较 第3章堆栈和队列 了解栈和队列的概念、特点 理解顺序栈和循环队列运算的实现 中缀表达式与后缀表达式的转换 后缀表达式计算 第4章数组和字符串 一般数组存储方法 三元组存储稀疏矩阵的方法 三元组表示的快速矩阵转置方法 字符串的概念、KMP算法及其改进 第5章树 二叉树的定义、性质及二叉链表 理解二叉树的遍历算法（遍历结果、算法设计），能设计相应算法程序 堆、堆的建立和调整 森林与二叉树的相互转换 哈夫曼树构造、哈夫曼编码、WPL计算 第6章集合与搜索 理解有序表的顺序搜索算法 理解对半搜索算法 平均搜索长度的计算 第7章搜索树 理解二叉搜索树的定义、性质和插入、删除算法 二叉平衡树的定义及插入算法 B-树的定义和插入、删除方法 第8章散列表 掌握散列函数的相关概念 散列函数 解决冲突的开地址法（线性探查法，二次探查法、双散列法） 第9章图 图的基本概念和存储结构 理解图的算法（结果）：遍历、拓扑排序、最小代价生成树、关键路径、最短路径第10章内排序 三种简单排序算法、快速排序和两路合并排序算法、过程、结果 排序算法的时间复杂度（最好、最差，平均）、稳定性 第11章文件 文件的基本概念 初始游程的生成及竞赛树 考试样题 填空题 写出表达式a*b+c/d的后缀形式________。 已知一无向图G=(V,E)，其中V={a,b,c,d,e}，E={(a,b), (a,d), (a,c) (d,c), (b,e)}，现用某一种遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是__________遍历方法。 在顺序表长度为n中，平均在表中插入一个元素需要移动元素的个数可用计算公式为________。 一个表长为n的线性表，其排序时间最快为。 选择题 具有n 个顶点的有向完全图中，边的总数为（）条。 A）n（n+1） B）n（n-1） C）n（n-1）/2 D）n（n+1）/2 设一个栈输入序列是1、2、3、4、5，则下列序列中不可能是栈的输出序列是（）。 A）32541 B）15432 C）14523 D）23145 二叉树的前序遍历为EFHIGJK，中序遍历序列为HFIEJKG。该二叉树根结点的右子树的根是（） A) E B) F C) G D) H 对有14个元素的有序表A[1]-A[14]作对半查找，查找元素A[4]时的被比较元素依次为（） A. A[1],A[2],A[3],A[4] B.A[7],A[3],A[5],A[4] C. A[1],A[2],A[7],A[4] D.A[7],[A5],A[3],A[4] 设有一个长度为100且已排好序的表，用对半搜索进行查找，若搜索不成功，则至少要比较______次。 （） A．9 B．8 C．7 D．6 简答题 用一维数组存放的一棵完全二叉树如图所示： 图 写出前序、中序、后序遍历该二叉树时访问结点的顺序。 图的邻接表表示一个给定的无向图。 （1）给出从顶点v1开始，用深度优先搜索法进行遍历时的顶点序列； （2）给出从顶点v1开始，用广度优先搜索法进行遍历时的顶点序列。 1.1实验步骤 随着计算机性能的提高，它所面临的软件开发的复杂度也日趋增加，因此软件开发需要系统的方法。一种常用的软件开发方法，是将软件开发过程分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实习题的复杂度远不如实际中真正的软件系统，但为了培养一个软件工作者所应具备的科学工作的方法和作风，我们制订了如下所述完成实验的5个步骤： 1、问题分析和任务定义 通常，实验题目的陈述比较简洁，或者说有模棱两可的含义。因此，在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么，限制条件是什么，解决问题的关键是什么。注意：本步骤强调的是做什么，而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的形式；输出数据的类型、值的范围及输出的形式；若是会话式的输入，则结束标志是什么，是否接受非法的输入，对非法输入的回答方式是什么等等。这一步还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式输入的数据。 2．数据类型和算法设计 在设计这一步骤中需分概要设计和详细设计两步实现。概要设计指的是，对问题分析中提出的解决问题的关键点进行进一步阐述，提出问题的解决方案（算法思想）；详细设计中首先对概要设计中涉及的操作对象定义相应的数据类型，并在具体的存储结构下描述关键问题解决过程；同时要综合考虑程序功能，按照以数据结构为中心的原则划分模块，说明各模块的功能，画出模块之间的调用关系图，模块的划分和调用应使得程序结构清晰、合理、简单和易于调试。详细设汁的结果是对数据结构和基本操作的规格说明作出进一步的求精，定义相应的存储结构并写出各过程和函数的伪码算法。在求精的过程中，应尽量避免陷入语言细节，不必过早表述辅助数据结构和局部变量。 3．编码实现和静态检查 编码是把详细设计的结果进一步求精为程序设计语言程序。如何编写程序才能较快地完成调试是特别要注意的问题。程序的每行不要超过60个字符。每个过程（函数）体一般不要超过40行，最长不得超过60行，否则应该分割成较小的过程（函数）。要控制if语句连续嵌套的深度，分支过多时应考虑使用switch语句。对函数功能和重要变量进行注释。一定要按格式书写程序，分清每条语句的层次，对齐括号，这样便于发现语法错误。 在上机之前，应该用笔在纸上写出详细的程序编码，并做认真地静态检查。多数初学者在编好程序后处于以下两种状态之一：一种是对自己的“精心作品”的正确性确信不疑；另一种是认为上机前的任务已经完成，纠查错误是上机的工作。这两种态度是极为有害的。对一般的程序设计者而言，当编写的程序长度超过50行时，通常会含有语法错误或逻辑错误。上机动态调试决不能代替静态检查，否则调试效率将是极低的。静态检查主要有两种方法，一是用一组测试数据手工执行程序（通常应先检查单个模块）；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注解。 4．上机准备和上机调试 上机准备包括以下几个方面： （1）熟悉C语言用户手册或程序设计指导书。 （2）注意Turbo C、VC与标准C语言之间的细微差别。 （3）熟悉机器的操作系统和语言集成环境的用户手册，尤其是最常用的命令操作，以便顺利进行上机的基本活动。 （4）掌握调试工具，考虑调试方案，设计测试数据并手工得出正确结果。“磨刀不误砍柴工”。学生应该熟练运用高级语言的单步调试和程序调试器DEBUG调试程序。 实验1: 顺序表的操作实验 一、实验名称和性质 二、实验目的 1．掌握线性表的顺序存储结构的表示和实现方法。 2．掌握顺序表基本操作的算法实现。 3．了解顺序表的应用。 三、实验内容 1．建立顺序表。 2．在顺序表上实现插入、删除和查找操作（验证性内容）。 3．删除有序顺序表中的重复元素（设计性内容）。 4．完成一个简单学生成绩管理系统的设计（应用性设计内容）。 四、实验的软硬件环境要求 硬件环境要求： PC机（单机） 使用的软件名称、版本号以及模块： Windows环境下的VC++6.0 五、知识准备 前期要求熟练掌握了C语言的编程规则、方法和顺序表的基本操作算法。 六、验证性实验 1．实验要求 编程实现如下功能： （1）根据输入顺序表的长度n和各个数据元素值建立一个顺序表，并输出顺序表中各元素值，观察输入的内容与输出的内容是否一致。 （2）在顺序表的第i个元素之前插入一个值为x的元素，并输出插入后的顺序表中各元素值。 （3）删除顺序表中第i个元素，并输出删除后的顺序表中各元素值。 （4）在顺序表中查找值为e的数据元素，如果查找成功，则显示“查找成功”和该元素在顺序表中的位置，否则显示“查找失败”。 2. 实验相关原理： 线性表的顺序存储结构称为顺序表，顺序表的存储结构描述为： #define MAXLEN 30 /*线性表的最大长度*/ typedefstruct { Elemtypeelem[MAXLEN]; /*顺序表中存放元素的数组，其中elemtype为抽象数据类型，在程序 具体实现时可以用任意类型代替*/ int length; /*顺序表的长度，即元素个数*/ }Sqlist; /*顺序表的类型*/ 【核心算法提示】 1．顺序表插入操作的基本步骤：要在顺序表中的第i个数据元素之前插入一个数据元素x,首先要判断插入位置i是否合法，假设线性表的表长为n，则i的合法值范围：1≤i≤n+1，若是合法位置，就再判断顺序表是否满，如果满，则增加空间或结束操作，如果不满，则将第i个数据元素及其之后的所有数据元素都后移一个位置，此时第i个位置已经腾空，再将待插入的数据元素x插入到该位置上，最后将线性表的表长增加1。 2．顺序表删除操作的基本步骤：要删除顺序表中的第i个数据元素，首先仍然要判断i 的合法性，i 的合法范围是1≤i≤n，若是合法位置，则将第i个数据元素之后的所有数据元素都前移一个位置，最后将线性表的表长减1。 3．顺序表查找操作的基本步骤：要在顺序表中查找一个给定值为e的数据元素，则可以采用顺序查找的方法，从顺序表中第1个数据元素开始依次将数据元素值与给定值e进行比较，若相等则查找成功，函数返回该数据元素在顺序表中的位置，若顺序表中所有元素都与给定值e不相片，则查找失败，函数返回0值。 【核心算法描述】 status Sqlist_insert(Sqlist&L,inti,Elemtypex) /*在顺序表L中第i个元素前插入新元素x*/ {if (i<1||i>L.length+1) return ERROR; /*插入位置不正确则出错*/ if (L.length>=MAXLEN) return OVERFLOW; /*顺序表L中已放满元素，再做插入操作则溢出*/ for(j=L.length-1;j>=i-1;j--) L.elem[j+1]=L.elem[j];/*将第i个元素及后续元素位置向后移一位*/ L.elem[i-1]=x; /*在第i个元素位置处插入新元素x*/ L.length++; /*顺序表L的长度加1*/ return OK; } status Sqlist_delete(Sqlist&L,inti,Elemtype&e) /*在顺序表L中删除第i个元素*/ {if (i<1||i>L.length)return ERROR; /*删除位置不正确则出错*/ for(j=i;j<=L.length-1;j++) L.elem[j-1]=L.elem[j]; /*将第i+1个元素及后继元素位置向前移一位*/ L.length--; /*顺序表L的长度减1*/ return OK； } int Sqlist_search(SqlistL,Elemtype x) /* 在顺序表中查找值为x的元素，如果找到，则函数返回该元素在顺序表中的位置，否则返回0*/ 南 京 邮 电 学 院 2001年攻读硕士学位研究生入学考试 数 据 结 构 试 题 一、完成下列各题（每小题6分，共18分）： 1、已知字符串p = ‘abbabbac ’，计算next(7)和nextval(7)的值。 2、给出下列排序算法最坏的情况时间复杂性，并指出其中那些算法是稳定的？ ⑴快速排序 ⑵简单选择排序 ⑶堆排序 3、设度为m 的树采用多重链表存储，每个结点有m+1个域，其中有一个数据域，m 个指向孩子的指针域。则空指针的数目是多少？说明这种存储方式的利弊。 二、完成下列各题：（每小题8分，共40分） 1、设二叉树以带右链的先序次序存储，其存储结构如下： 6 3 5 0 0 0 9 0 0 0 E H F I G A B D C J 1 2 3 4 5 6 7 8 9 10 则画出该二叉树。 2 、对于下列AOE 网络，求出各活动可能的最早开始时间和允许的最晚完成时间，并问整个工程的最短完成时间是多少？ 3、设有13个初始游程，其长度分别为28，16，33，19，5，7，18，20，12，31，38，22，10。试画出4路合并最佳合并树，并计算它的加权路径长度。 4、设散列表ht 的长度为11，散列函数h 1(key) = key mod 11,h 2(key)=key mod 9+1。采用双重探查法解决冲突，请从空表开始，依次插入下列关键字值序列：70，25，80，35，60，45，50，55，建立散列表。 5、设有初始关键字值序列为：71，74，2，72，54，93，52，28，现采用堆排序方法进行排序，请给出手工执行堆排序的过程。 三、设E是一棵扩充二叉树的外路径长度，I是内路径长度，n是内结点个数。试写出三者的关系式，并使用数学归纳法证明之。（10分） 四、有序表以顺序方式存储，其存储结构说明如下： Type list=array[1..n] of integer 实现下列对半查找的函数过程： Function bisearch(r:list;low,high,tkey:integer):integer; 其中，tkey为待查关键字值。若tkey在表r中，则返回该关键字值在表中的位置，否则返回0。并画出n=10的对半查找判定树。（16分） 五、已知有n个结点的树以双亲表示法存储在一堆数组中。请设计一个的算法求树中每个结点的层次和树的高度，将求得的每个结点的层次保存在一维数组c中，并分析你所设计的算法的时间复杂性。（16分） 一、实验目的 1、学习线性表的顺序表示和实现，会进行顺序表的插入、删除、合并 2、学习线性表的链式表示和实现，会进行链表的插入、删除、合并 二、实验内容 1、编程实现：（1）在顺序表ajcniydu的第三个位置插入p。（2）删除顺序表ajcniydu第三个位置的元素。 2、编程实现将顺序表acdijtuy和cfklns合并。 3、编程实现：（1）在链表asdfghjkl的第四个位置插入z。（2）删除顺序表asdfghjkl第四个位置元素。 4、编程实现两个有序链表adfi和cefi的合并。 三、实验步骤 1.+ 2.代码： #include { printf("输入字符串："); int i=0; for(i;i 数据结构实验报告全集 数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 6.0上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。（3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>//头文件 #include { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"< 实验报告 （2015 / 2016 学年第一学期） 课程名称数据结构 实验名称图的基本运算及飞机换乘次数最少问题 实验时间2015 年12 月 4 日 指导单位计算机科学与技术系 指导教师黄海平 学生姓名陈明阳班级学号Q14010119 学院(系) 贝尔英才专业信息科技强化班 实验报告 实验名称图的基本运算及飞机换乘次数最少问题指导教师黄海平 实验类型验证实验学时 4 实验时间12.4 一、实验目的和要求 飞机最少换乘次数问题。 （1）设有n个城市，编号为0~n-1，m条航线的起点和终点由用户输入提供。寻找一条换乘次数最少的线路方案。 （2）参考：可以使用有向图表示城市间的航线；只要两城市间有航班，则图中这两点间存在一条权值为1的边；可以使用Dijkstra算法实现。 二、实验环境(实验设备) VSUAL STUDIO2015 三、实验原理及内容 对象视图： 源代码： Graph.h #include 《 数据结构B 》期末试卷（A ） 本试卷共 4 页； 考试时间 110 分钟； 专业 班级 学号 姓名 一、填空题（20分，共10题） 1. 数据结构主要研究数据的______结构，数据的存储结构以及在数据上执行的运算。 2. 设顺序表长度为100，若下标从0开始计，则删除元素a 10需要移动______个元素。 3. 一棵二叉树中，若叶结点的个数为2011，则度为2的结点个数为______。 4. 有向图进行拓扑排序时，没有输出图中所有顶点，说明图中存在______。 5. 线性表采用二分搜索必须满足两个条件：线性表关键字必须是______；存储结构 必须采用顺序存储结构。 6. 二叉搜索树的______序遍历序列是一个按关键字递增排列的有序序列。 7. 设有一组记录的关键字为{19, 14, 1, 69, 20, 27, 55, 79}，散列函数为h(key) = key%11，散列函数值为3的有______个。 8. 快速排序算法平均情况下的渐近时间复杂度为O(______)。 9. 采用二次探查法解决冲突可能产生_______聚集。 10. 图常见的两种存储结构有邻接矩阵和_______。 二、选择题（20分，共10题） 1. 一个算法必须在执行有穷步之后结束。这是算法的_______。 A. 有穷性 B. 正确性 C. 确定性 D. 可行性 2. 在指针p 所指示的结点之后插入新结点s 的操作是_______。 A. s->link=p;p->link=s; B. s->link=p->link;p->link=s; C. s->link=p->link;p=s; D. p->link=s;s->link=p; 3. 栈和队列的共同点是_______。 A. 都是先进后出 B. 都是先进先出 C. 只允许在端点处插入和删除元素 D. 没有共同点 4. 后缀表达式：5 3 2 * 3 + 3 / +的值为_______。 A. 18 B. 7 C. 9 D. 8 装 订 线 内 不 要 答 题 自 觉 遵 守 考 试 规 则，诚 信 考 试，绝 不 作 弊 关于南邮的公费以及自费的问题,请直接到这里来看! 1、由于广大考友对南邮的公费以及自费的问题问得比较多，我在这里统一回答一下: 1)南邮的公费比例是比较高的,至少前几年是这样的,平均下来在85%左右，由于现在国家说要慢慢地取消公费，所以以后就不知道了。 2)公费生只要交三年的住宿费2000元，并且每个月有200元补助。 3)自费生除了交2000元住宿费外，还要每年交4000元学费，并且没有补助。 4)南邮的研究生自己买电脑的时候，只要有发票，都可以报销1000元。 注意:以上所说的情况，都是前几年的情况。 2、问题:公费的分数最低是多少啊？ 答:没什么最低分，2006年信息与通信工程没招够，307照样公费，只要是第一志愿报通信过了国家线的，够了复试线全是公费，部分调剂生也是公费。 另外:保送生全是公费。 关于报考及课程的相关问题: 1、问题:请问，南邮是报专业还是报导师？06年的通信与信息系统的复试413微机原理及应用或414数据结构与05年的不同，明年还会变么？ 南邮的信号与信息处理是不是比通信与信息系统要好些？请赐教 答:南邮是在报名的时候报专业，在复试快结束的时候报导师。 明年还会不会变我也不知道。 个人认为这两个专业差不多，通信与信息系统稍好一点点，个人意见，仅供参考！ 2、问题:管理科学与工程初试④414数据结构或418企业管理和复试复试科目:418企业管理或424系统分析与设计中的"或"是什么意思,是自己选择还是学校选择,具体解释一下好吗?谢谢 选择不同科目不是会由于题目不同而造成分数不同吗?老师会不会倾向与某个科目呢,比如这两个选哪个好呢? 答:自己选,二选一.但是初试和复试不能先同一科目. 数据结构实验代码南邮实验课实验十各种算法性能比较#include while(i>0) { last=0; for(j=0;j 重庆文理学院软件工程学院实验报告册 专业：_____软件工程__ _ 班级：_____软件工程2班__ _ 学号：_____2 ___ 姓名：_____周贵宇___________ 课程名称：___ 数据结构 _ 指导教师：_____胡章平__________ 2013年 06 月 25 日 { ElemType elem[MAXSIZE]; /*线性表占用的数组空间*/ int last; /*记录线性表中最后一个元素在数组elem[ ]中的位置（下标值），空表置为-1*/ }SeqList; #include "common.h" #include "seqlist.h" void px(SeqList *A,int j); void main() { SeqList *l; int p,q,r; int i; l=(SeqList*)malloc(sizeof(SeqList)); printf("请输入线性表的长度:"); scanf("%d",&r); l->last = r-1; printf("请输入线性表的各元素值:\n"); for(i=0; i<=l->last; i++) { scanf("%d",&l->elem[i]); } px(l,i); printf("请输入要插入的值:\n"); scanf("%d",&l->elem[i]); i++； px(l,i); l->last++; for(i=0; i<=l->last; i++) { printf("%d ",l->elem[i]); } printf("\n"); } void px(SeqList *A,int j) { int i,temp,k; for(i=0;i2015年南京邮电大学数据结构初试真题
南邮数据结构上机实验二二叉树的基本操作及哈夫曼编码译码系统的实现
南邮数据结构B期末试卷.doc
数据结构实验报告全集
南京邮电大学2005年数据结构考研试卷
数据结构实验报告-答案
数据结构A复习要点及样题(南邮)
数据结构实验1
《数据结构》实验1
2001年南邮考研数据结构考研试卷
数据结构实验1
数据结构实验报告全集
南邮数据结构实验三
(完整word版)南邮通达数据结构B期末试卷及答案,推荐文档
南邮考研有关问答
南邮数据结构实验算法分析
数据结构实验答案
- 2014年考研南京邮电大学数据结构真题(回忆版)
- 南邮数据结构课后习题课
- 南邮陈慧南版数据结构课后习题答案
- 南京邮电大学数据结构A第3章
- 南邮_数据结构作业解答讲解
- 南京邮电大学数据结构A第7章
- 南京邮电大学数据结构A第6章
- 2015年南京邮电大学数据结构
- 2014南邮考研数据结构真题
- 南邮_数据结构作业答案讲解
- 南京邮电大学考研数据结构真题
- 南邮数据结构实验一
- 南京邮电大学数据结构A第5章
- 最新南京邮电大学数据结构811真题
- 2006年南邮考研数据结构考研试卷
- 南邮_数据结构作业答案讲解
- 南邮_数据结构作业答案讲解教学教材
- 南邮_数据结构课后习题答案讲解
- 南京邮电大学2006年数据结构考研试卷
- 2016南京邮电大学数据结构811真题