专业课程在职考试大纲

数据结构第一章 绪论 知识点 1 熟悉数据、数据结构、数据对象、数据元素、存储结构和数据类型等名词术语的含 义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系2 分清那些是逻辑结构的性质，那些是存储结构的性质。 复习题 1 什么是数据与数据元素？2 什么是数据结构？什么是数据类型？什么是类型？3 什么是数据的逻辑结构与存储结构？举例说明4 数据结构与软件的关系是什么？5 解决实际问题时，选取或者设计数据结构的原则是什么？-数据：是能输入到计算机中并能被计算机程序处理的符号的总称。 数据元素：是数据的基本单位，它在计算机处理和程序设计中通常作为一个整体进行考 虑和处理 ,一个数据元素可由若干数据项组成。数据对象：是具有相同特征的数据元素的集合，是数据的一个子集。 数据结构：是数据元素的组织形式或数据元素相互之间存在一或多种特定关系的集合。 数据的存储结构：是数据的逻辑结构在计算机内存中的存储方式，又称物理结构。 数据类型：是一组具有相同性质的操作对象以及该组操作对象上的运算方法的集合。 抽象数据类型：是指一个数学模型以及在该模型上定义的一套运算规则的集合。 符合软件应用业务特点的数据结构可以使软件运行效率更高，但软件效率也和编译环 境、操作栈、硬件配置等其他因素有关。通常考虑算法运行所需的存储空间和时间。后 者又涉及四个方面：程序运行时所需输入的数据总量、对源程序编译所需时间、计算机 执行每一条指令所需时间和程序中指令重复执行的次数。6. 下面程序的时间复杂度为 : ( C )For (int i=0; im; i+)For (int j=0; jn; j+) aij=i*j;A O (m2) B O(n2)C O(n*m) D O(n+m)第二章 顺序表 知识点 1 了解顺序表的逻辑结构特性是数据元素之间存在着线性关系，熟练使用顺序存储结构和链式存储结构表示这种关系。2 熟练掌握线性表在顺序存储结构上的基本操作：查找、插入、删除的算法。3 熟练掌握链表中头结点、 头指针、 和首结点的区别以及循环链表、 双链表的的特点。 在线性链表、循环链表、双向链表中实现线性表的基本操作：如建立链表、在链表 中查找某个指定元素并求出该指定元素在链表中出现的次数、在链表中插入元素、 在链表中删除元素、求链表长度的算法；要求能根据实际的应用选择当前的链表结 构，或者生成新的数据结构。掌握数组的两种存储表示方法以及数组在顺序存储结构中地址计算方法。 习题 7. 描述以下概念的区别：头指针、头结点、首元节点。头指针变量和头结点的作用？并比较顺序存储结构和链式存储结构的优缺点。 首元结点：是指链表中的存储线性表中的第一个数据元素 a1 的结点。头指针 ： 是指向链表中的第一个结点(或者为头结点或首元结点)的指针。若链表中 附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指 针为空。头结点： 通常在链表的首元结点之前附设一个结点，称为头结点。 头指针变量和头结点的作用：8. 在顺序表中，插入或移动一个元素，需要平均移动多少个元素？具体移动元素的个数与 什么有关？n/2 、 与元素所在的位置有关。9. 顺序表中逻辑上相邻的元素的物理位置是否紧邻？数组中已知两个元素位置， 如何计算 另一个元素地址？单链表中逻辑上相邻的元素的物理位置是否紧邻？ 在什么情况下， 顺序表比链表好？ .10. 设有一个二维数组 AMN,假设A00存放位置在644(io),A22 在676(io),每个元 素占一个空间 , 则 A33 在 位置 , (10) 表示用十进制数表示11. 二维数组A【1。20 , 1。10】按照行优先顺序存储，每个元素占4个单元，且A【1 ,1】的地址是1000，则A 18,9的存储地址是 (1712 )第三章 栈和队列 知识点 1 掌握栈和队列的结构特点。2 使用顺序结构实现栈的基本操作：栈的定义、栈的压入、栈的弹出、读栈顶元素， 判栈空或满。3 实现队列的基本操作：队列的定义、队列的插入、队列元素的删除、读队列的头结 点、判队列空或满；4 实现循环队列的基本操作：循环队列的定义、队列的插入、队列元素的删除、读队 列的头结点、判队列空或满。5 在相应的实际问题中正确选用它们。如回文的判断。 复习题 12. 写一个算法，借助栈将一个单链表倒置template void LList:reverse() if(head-next = NULL)return;/ First, fix fence by pushing it forward one stepif (fence-next = NULL)fence = head;else fence = fence-next;link* temp = head-next; /first node except header nodewhile (temp != NULL) push( s， temp) ; temp = temp -next;while ( ! EMPTY (S) ) POP (s, temp);fence -next = temp;fence = fence -n ext ；13. 简述栈和队列这两种数据类型的相同点和差异.栈的操作：先进先出；队列先进后出14. 一个栈的入栈序列是 a,b,c,d,e则栈的不可能的输出序列是CA . edcbaB. decba C. dceab D. abcde第四章串 知识点1. 掌握串的顺序存储结构和链式存储结构；2. 在串的顺序存储结构上实现串的各种操作：连接两个串、取子串、删除子串、插入 子串，求子串的位置。3. 在串的链式存储结构上实现串的各种操作：连接两个串、取子串、删除子串、插入 子串。复习题15. 区别空串和空格串。-长度不同，空串长度为0,空格长度为116. 设 s = AMA STUDENT t = GOODVORKER, CONCAT(Substr (s , 6 , 2), t) = ( A GOOD WORKER17. 广义表A (a),则表尾为空表.第五章二叉树和树知识点1. 掌握二叉树的定义、性质和存储结构。2. 熟练掌握二叉树的前序、中序、后序遍历的递归算法和前序、中序的非递归算法，了解栈在遍历过程中的作用和状态。3. 熟练掌握二叉树的层次遍历算法。4. 满树和完全树5. 堆，最大堆和最小堆，建立堆的算法18. 已知一颗度为k的树中有n1个度为1的结点，n2个度为2的结点，。nk个度为k的结点，问该树中有多少个叶子结点？n119. 找出满足在先序遍历和中序遍历中，得到的结点访问序列相同的所有二叉树。20. 找出满足在后序遍历和中序遍历中，得到的结点访问序列相同的所有二叉树。21. 找出满足在先序遍历和后序遍历中，得到的结点访问序列相同的所有二叉树。22. 已知二叉树的前序序列为 ABECDFGHIJ，中序序列为 EBCDAFHIGJ，是否能确定唯一 二叉树？如果可以，请画出这棵二叉树并给出其后序序列-可以。Postorder enumeration: EDCBIHJGFAINORDER: EBDCAFIHGJ23. 假设字符 A,B,C,D,E,F,G,F的使用频度如下表，请构造一棵Huffman树，并写出各字母的Huffman (哈夫曼)编码(不唯一)，计算编码平均长度。A B C D E F G H255363611104-答案不唯一，因为编码不唯一，但平均码长唯一Huffma n codeABCDEFGH1001000000010111011001000124.采用邻接表存储的图的深度优先遍历算法类似于二叉树的(B)A中序遍历B.前序遍历C.后序遍历D. 按层次遍历第六章图知识点1 .掌握图的定义和术语；图的四种表示方法：数组表示法、邻接表。y2 熟练图的两种遍历策略：深度优先和广度优先。“3 .熟练掌握生成最小生成树的方法。.4. 求最短路径长度I -：复习题_ 一25.已知图为无向带权图。(1) 用Dijkstra算法找出从C到所有其他节点的最短路径写出邻接矩阵-(2) 用Kruskal 算法找出最小生成树。画出从A出发的DFS (深度优先搜索)树。第九章查找知识点1 .掌握顺序表和有序表的查找方法如折半查找。2 .熟练掌握哈希表的构造方法以及解决冲突的方法。复习题26请写出在线性表(a,b,c,d,e,f,g)中进行折半查找，查关键字等于e的过程。-A3:d;A4:e27. 使用封闭哈希 closed hashing插入码22, 41,53, 46, 30, 13, 1,67到一个11槽的哈希表中(槽编号0到10)，使用双哈希解决冲突，要使用的哈希函数为 H1和H2定义为H1(k) = 3k mod 11 , H2(k) = 7k mod 10+1.画出所有8个码已被插入后的哈希表，描述如何使用H1和H2进行哈希。-H1(22)=0, H1(41)=2, H1(53)=5, H1(46)=6, no con flict When H1(30)=2, H2(30)=1 so 30 en ters the 3rd slot;H1(13)=6, H2(13)=2 so 13 en ters the 8th slot;H1(1)=3, H2(1)=8 so 1 enters 10 (pass by 0, 8, 5, 2 );H1(67)=3, H2(67)=10 so 67 en ters 1(pass by 2)226741305346131012345678910第十章内部排序知识点熟练掌握各种排序方法。复习题28. 跟踪数组(int a = 72,6,57,88,60,42,83,73,48, 85)使用快速排序算法的状态。第一遍的标尺为60,第二遍是6和73,第三遍为57和88,以此类推。(交换排序中如果标尺被交换, 则交换者被换到最后位置)-i nitial:72 6 57 88 60 42 83 73 48 85pivot 60pass 1:48 6 57 42 60 88 83 73 72 85 pivot 673pass 2:6 42 57 48 60 72 73 85 88 83 pivot 5788pass 3:6 42 48 57 60 72 73 85 83 88 pivot 4285pass 4:6 42 48 57 60 72 73 83 85 88final sorted array: 6 42 48 57 60 72 73 83 85 88补充练习：简答和算法题29. 将两个单链表重新链接成有序单链表。-算法讨论：先判断两个链表中有没有空的，再进行边合并边倒置，也可以先合并再统次倒置。每执行完一步需要判断链表是否有已经到尾的。Void Union(Lin kList a,L in kList b,L in kList c)已知非递减有序链表a,b,归并得到新链表c无重复元素c=(L in kList)malloc(sizeof(LNode);ap=a ?n ext; bp=b? next; cp=c;While (ap |bp) 归并tp=(LinkList)malloc(sizeof(LNode);cp?n ext=tp;cp=tp;if (!ap)cp ?ch =bp?ch;bp=bp ?next;else if (!bp)cp ?ch =ap?ch;ap=ap ?next;else if (ap?ch= bp?ch)cp ?ch= ap?ch;ap= ap?next;bp= bp?next;else if (ap?ch bp?ch)cp ?ch= ap?ch;ap= ap?next;else cp?ch= bp?ch; bp= bp? next;cp?n ext= NULL;30. 设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，如此反复直到所有的人全部出局为止。下面要解决的Josephus问题是：对于任意给定的n, s和m，求出这 n个人的出局序列。请以n = 9, s = 1, m = 5为例，人工模拟Josephus的求解过程以求得问题的解。-出局人的顺序为 5, 1,7, 4, 3, 6, 9, 2, 8。31已知序列 503 ，87，512，61，908，170，897，275，653，462 请给出采用起泡排序法 和快速排序法对该序列作升序排序时的每一趟的结果。-61,503,87,512,170,908,275,897,462,65361, 87, 503, 170, 512, 275,908, 462,897,65361, 87, 170, 503, 275,512, 462,908, 653, 89761, 87, 170, 275,503, 462, 512, 653,908, 89761, 87, 170, 275, 462,503, 512, 653, 897,90832. 用折半查找找出含有关键字值的记录，若找不到，输出比该值小的最大值或比该值大的 最小值所在记录位置。记录用数组存储。/ Return position of greatest element = Kint newbinary(int array, int n, int K) int l = -1;int r = n; / l and r beyond array boundswhile (l+1 != r) / Search value not in array (若返回比 K 大的第一个最小整数所在处？修改 return r ；且 r=n 时返回 ERROR)33. 使用 C+ 抽象类声明一个顺序表，写一个函数交换一个顺序表右方的首两个元素。/ Interchange the order of current and next elementsvoid switch(List L1) Elem temp;if ( ！ L1.remove (temp) coutERROR ；L1.next () ；L1.insert (temp) ；34. 列举你所知的各种排序算法并根据算法复杂度进行分类。相邻元素交换(步长为1)类排序：冒泡排序、插入排序、选择排序，算法复杂度为O(n2)(步长非 1)交换间隔不定或者增量类排序：SHELL 排序、交换排序 O(nlog2n)其他排序：锦标赛、箱柜排序、树图排序等35. 叙述树的索引方法和哈希方法，树可以克服哈希方法的哪些缺点？36. 什么是静态索引结构？什么是动态索引结构？它们各有哪些优缺点？37. 线性表可用顺序表或是链表存储，此两种存储表示各有哪些优缺点？38. 试编写一个算法，在带表头结点的单链表中寻找第 i 个结点。若找到，则函数返回第 i 个结点的地址；若找不到，则函数返回0。template ListNode * List : GetANode ( int i ) 取得单链表中第i个结点地址,i从0开始计数,i 0时返回指针0, i = 0时返回表头结 点地址。if ( i 1 ) return NULL;ListNode * p = first; int k = 0;while ( p != NULL & k GetMax(Array, len-1) ? Arraylen -1 : GetMax(Array, len-1);(2) 求 n 个整数的和。 平方和 ?平方根取整之和？ int Sum(int* Array, int len)if(len = 1)return Arraylen-1;elsereturn Arraylen-1 + Sum(Array, len-1);(3) 求 n 个整数的平均值。 方差？平方之和？40. 已知 Head 为整数型单链表表头，试写一算法，将这个链表变成一个与原来连接方向相 反的单链表。 双链表？循环链表？#include using namespacestd;struct LinkNodeint data; LinkNode* next;/ Head nodeLinkNode head;void CreateLinkList(LinkNode& head, int data) / Create new NodeLinkNode* pNewNode = newLinkNode; pNewNode-data = data;pNewNode-next = NULL;/ link into headpNewNode-next = head.next;head.next = pNewNode;void Print(LinkNode& head)LinkNode* p = head.next;while (NULL != p)cout data next;cout next;n+;while (n)LinkNode* l = head.next;LinkNode* q = NULL; while (l-next != NULL) q = l;l = l-next;if (q & l)/ Remove last one node q-next = NULL;l-next = head.next; head.next = l;n-;int main()head.next = NULL;/ Create Single link listCreateLinkList(head, 20);CreateLinkList(head, 30);CreateLinkList(head, 40);CreateLinkList(head, 50);Print(head);ReverseLinkDirect(head);Print(head); return 0;