本人是今年考上广州大学计算机专业的，说真的，专插本这条路并不好走，很辛苦!但是当你知道自己考上了，那感觉是相当激动的！！ 2011年高考成绩揭晓，我就过了3A二分而已，那时候心情很沉重，只有3条路可以选择，第一是复读第二就是读3A尾的学校第三就是去打工，最后的抉择是报了中山火炬技术学院（全省专科不知道是倒数第二还是倒数第三的学校） 2011年九月带着沉重的心情来到了中山火炬技术学院，这学校名气小的可怜，问了N多人都没人知道这学校，学校也小的可怕，十几分钟就可以走完，当时感觉自己很悲剧，上了这样的学校很没面子，因此痛下决心来不管怎么样要往上爬，从一个师兄那里听说可以插本，考到的话第一学历是本科，但是听说插本很难，比高考，考研究生还要难上百倍，便没怎么想插本了，还是专心学好大专的专业吧 一转眼，2年过去了，到了大三，很多同学都去实习了，我又一次走到人生十字路口上，是去工作还是去插本，经过几天考虑还是决定插本了，因为第一我觉的要进好的企业需要本科第二我不想那么快工作，那时候作出插本决定已经是9月底了，中山火炬技术学校插本的人很少，所以只好通过加插本QQ群来了解插本信息 因为本人不想给家庭负担所以没有参加任何培训班，刚开始复习全靠自己摸索着的，很痛苦，哪里是重点哪里不是重点都不知道，幸亏在进群之后知道考纲这回事，慢慢的走上了复习的正规道路，每天8点就起来看书，除开吃饭上厕所什么的离开一下教室其他都是在教室看书，一直看到晚上10点钟，回到宿舍继续看书，因为宿舍没人，所以看到2点左右才睡觉，每个星期抽出半天去放松，这样才能保证效率，那时候备考时候真是很无聊很痛苦，知道不少人都已经放弃了，但是还是坚持到最后，3月去广州考试，看见考广大计算机人400多人，心里有点怕怕的，但是马上调整好心态，心里说怕什么，大不了考不上去工作呢，在考试那2天就浏览一下书本和总结的考点，考完也不去想考试结果，因为没有什么意义了，四月八出成绩了，当时心里发毛了，因为说不担心那是假的，我是先要我舍友帮我查的，她说过了，我还是担心，最后自己鼓起勇气查的，当我点一下鼠标的那一刻眼睛是闭着的，闭了好久才敢看成绩。当时自己惊叫了起来：过了过了，战争终于结束了。自己也没想到会考的这么好，它见证了我几个月的付出是值得的好了，啰嗦了那么多，不知道说了这么多大家看了是什么心情，写的乱七八糟的，不过都是个人真实感受，现在就分享一下我各科复习经验吧 政治 这个是最恶心的科目，我用最多时间来备考这科，因为高中读的是理科，对它不感冒，但是考了67分，虽然不是很高分，但是我已经很满足了，现在谈谈这科复习方法，我10月开始看政治书的，一天一章的看，看到11月，看了大概四次书本，你会问为什么要看书，很简单，因为政治选择题很坑爹，不少题目是书本的，但是考纲没有的，12月开始之后，我就根据录音去划书，整理笔记，然后开始背，每个白天抽3小时背政治，然后晚上回宿舍打开电脑用 1小时选择题，培养做题感觉，到一月中，开始做历年真题，并把考过的大题给划掉，重点背那些没出的，没背熟的反复的背和默写，要是你学我这样做，我想政治可以个满意的分数。 英语
数据结构 一、单选题 1. 计算机算法指的是（b ）。 A．程序B．问题求解步骤的描述C．调度方法D．排序方法 2. 以下数据结构中，（a ）个是非线性数据结构。 A．树B．字符串C．队D．栈 3. 对于顺序存储的线性表，访问元素和插入元素的时间复杂度分别为：（c ）。 A．O(n) O(n) B．O(n) O(1) C．O(1) O(n) D．O(1) O(1) 4. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（b ）。 A.p->next=s;s->next=p->next B.s->next=p->next; p->next=s C.p->next=s;p->next=s->next D.p->next=s->next; p->next=s 5. n个顶点的有向图中,含有向边的数目最多为( d ) A．n-1 B．n C．n(n-1)/2 D．n(n-1) 6. 循环队列存储在数组A[0..m]中，则入队时的操作为（ d ） A．rear=rear+1 B．rear=(rear+1)mod(m-1) C．rear=(rear+1)mod m D．rear=(rear+1)mod(m+1) 7. 字符串?ababaabab?的next函数为（d ） A.011232232 B.012341234 C.011122334 D. 011234234 8. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为（ b ）A．9 B．11 C．15 D．不确定 9. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当以列为主序存放时，元素A[5,8]的首地址为（ b ）。A．BA+141 B．BA+180 C．BA+222 D．BA+225 10. n个顶点的带权无向连通图的最小生成树包含(b )个顶点 A．n-1 B．n C．n/2 D．n+1 11．有关二叉树的下列说法正确的是（ b ） A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 12．关键路径是AOE网中（ a ）。 A．从源点到汇点的最长路径B．从源点到汇点的最短路径 C．最长回路 D．最短路径（从源点到汇点的所有路径中，经过弧的数目最多的路径） 13．若查找每个记录的概率相等，则在具有n个记录的连续文件中采用顺序查找查找一个记录，其平均查找长度ASL为（c）。 A．(n-1)/2 B．n/2 C．(n+1)/2 D．n 14．就平均性能而言，目前最好的内部排序方法是（d ） A．冒泡排序B．希尔排序C．堆排序D．快速排序 15．已知广义表LS=((a,b,c),(d,e,f))，运用head和tail函数取出LS中原子e的运算是（d ）A．head(tail(LS)) B．tail (head (LS) C．head(tail(head(tail(LS)))) D．head(tail(tail (head (LS)))) 17．在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：( a ) A. 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B. 在第i个结点后插入一个新结点（1≤i≤n）
沈阳工业大学 机械工程学院 机械设计2007——2009 工业设计概论2007——2008 材料科学与工程学院 材料科学基础2007——2009 普通物理2007——2009 电气工程学院 电工基础2007——2009（2009年有两种） 电子技术2007——2009 信息科学与工程学院 电子技术2007——2009 半导体物理2007——2009 信号与系统、通信原理2007——2009 电工基础2007——2009（2009年有两种） 线性代数与常微分方程2007——2009 数据结构2007——2009 建筑工程学院 材料力学2007——2009 结构力学2007——2008 石油化工学院 化工原理（石油化工学院化学工艺专业）2009 化工原理（2）（石油化工学院化学工艺专业）2007——2008 物理化学（石油化工学院化学工艺专业）2009 物理化学（2）（石油化工学院化学工艺专业）2007——2008 理学院 化工原理（理学院应用化学专业）2009 化工原理（1）（理学院应用化学专业）2007——2008 物理化学（理学院应用化学专业）2009 物理化学（1）（理学院应用化学专业）2007——2008 数学分析2007——2009 高等代数2007——2009 量子力学2007——2009 普通物理2007——2009 管理学院
管理学2007——2009 基础工业工程2007——2009 会计学2007——2009 企业管理学2007——2009 经济学院 现代经济学2007——2009 文法学院 马克思主义哲学2007——2009 科学技术哲学2007——2009 法理学、民事诉讼法学2007——2009 民法学、商法学2007，2009 民商法学2008 马克思主义基本原理2007——2009 中国化的马克思主义概论2007——2009 单考试卷 数学（单考）2007，2009 英语（单考）2007，2009 政治理论（单考）2007，2009
中国农业科学院 2017年硕士研究生招生考试自命题科目考试大纲 科目代码：808 考试科目：数据结构 一、考查目标 要求考生比较系统地理解数据结构的基本概念和基本理论，掌握数据结构的基本方法，具备一定的运算能力、逻辑思维能力、编程能力和综合运用所学知识分析问题和解决实际问题的能力。 二、考试形式和试卷结构 1.试卷满分及考试时间 本试卷满分为150分，考试时间为180分钟。 2.答题方式 闭卷、笔试。 3.试卷内容结构 考试内容包括数据的方法、存储数据结构的方法以及在各种结构上执行操作的算法。题型包括单项选择、填空、简答和写算法题等。 三、考试大纲 1、数据结构概论 1)数据、数据元素、抽象数据类型、数据结构、数据的逻辑结构与存储结构等概念； 2)算法的定义、特性、算法的时间复杂度、算法的空间复杂度、递归算法等概念。 2、线性表 1）掌握线性表的基本概念及其存储结构； 2）掌握顺序表的各种操作（插入、删除等）实现及算法复杂度； 3)掌握单链表的各种操作（插入、删除等）实现及算法复杂度； 4)了解顺序表和链表的特点，对比他们的优缺点。 3、桟和队列 1)了解栈、队列的基本概念； 2)掌握栈的入桟、出栈操作，并能利用栈解决实际问题；
3)掌握队列的入队、出队操作，并能利用队列解决实际问题。 4、数组和广义表 1)理解多维数组的行主序、列主序存储； 2)了解特殊矩阵（对称矩阵、三角矩阵、稀疏矩阵）的压缩存储； 3)了解广义表的定义、表示和存储方法。 5、树和二叉树 1)了解树和二叉树的基本概念、术语和性质； 2)掌握二叉树的两种存储结构（顺序存储、二叉链表存储）； 3)掌握二叉树的先根、中根、后根遍历算法； 4)掌握常见的构造二叉树的方法； 5)掌握二叉树的层次遍历算法，能够用顺序循环队列演示遍历过程； 6)掌握建立哈夫曼树和哈夫曼编码的方法及带权外路径长度（WPL）的计算； 7)了解树和二叉树的相互转换，了解树的存储、遍历。 6、图 1)了解图的基本概念； 2)掌握图的存储结构（邻接矩阵表示法、邻接表表示法）； 3)掌握图的两种遍历算法（深度优先搜索遍历、广度优先搜索遍历）； 4)掌握图的最小生成树算法思想（Prim、Kruskal）； 5)掌握图的最短路径算法思想（Dijkstra）。 7、查找 1)了解查找的基本概念（查找表、查找、平均查找长度ASL）； 2)掌握线性表的查找算法（顺序查找、折半查找、分块查找）。会计算查找过程中的比较次数，会分析它们的算法时间复杂度，了解它们的优点和缺点，能够根据实际情况选择适当的查找算法； 3)掌握二叉排序树的定义以及查找、插入等操作。了解平衡二叉树； 4)掌握散列技术：会利用除余法构造散列函数，掌握处理冲突的两种方法（开放定址法、链地址法），会计算平均查找长度。 8、排序 1)掌握排序的基本概念（排序算法的稳定性、排序算法性能评价）；
数据结构,专科 一、简答题（ 1、假设一个有向图的顶点集合V={c1,c2,c3,c4,c5},弧集 S={
h f c / / \ d k g 后序是hdfbkgcea 3、已知关键字序列{70，83，100，65，10，9，7，32}，现对其 从小到大排序，写出快速排序每一趟结束时的关键字状态。 答#include
譬如第一次结果就是70，83，100，65，10，32，7，9 70比83小，所以位置没变。。 4、设s="I AM A WORKER"，t=" GOOD"，q=" WORKER"。求： StrLength(s)，StrLength(t) ，SubString(s,8,6) ， Index(s,q,1) 。 答：strlength(s)=14；strlength(t)=4；substr(s,8,6)=worker；substr(s,q,1)=o; 5、在单链表中设置头结点有什么作用？ 答：头结点就是在单链表的开始结点之前附加的一个结点，设置头结点的优点有两个：（1）由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其他位置上一样，无须进行其他特殊处理；（2）无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就一样了。 6、设哈希函数H(key)=key MOD 13,用线性探测再散列法解决 冲突。对关键字序列{ 55，19，01，68，23，27，20，84 } 在地址空间为0-10的散列区中建哈希表，画出此表，并求等 概率情况下查找成功时的平均查找长度。
数据结构》期末考试试题及答案 ( 2003-2004 学年第 2 学期 ) 单项选择题 1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 7．图的 Depth-First Search （DFS ） 遍历思想实际上是二叉树（ 法的推广。 （A ）、先序 （ B ）、中序 （C ）、后序 （D ）、层序 8．在下列链队列 Q 中，元素 a 出队的操作序列为（ p=Q.front->next; p->next= Q.front->next; p=Q.front->next; Q.front->next=p->next; p=Q.rear->next; p->next= Q.rear->next; p=Q->next; Q->next=p->next; 9． Huffman 树的带权路径长度 WPL 等于（ c （ A ）、除根结点之外的所有结点权值之和1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为 （ c ）。 （A ） 、正确性 （B ）. 可行性 （C ）. 健壮性 2．设 S 为 C 语言的语句 ,计算机执行下面算法时， for （i=n-1 ； i>=0 ； i--） for （j=0 ；j数据结构与算法分析 C++版答案
Data Structures and Algorithm 习题答案 Preface ii 1 Data Structures and Algorithms 1 2 Mathematical Preliminaries 5 3 Algorithm Analysis 17 4 Lists, Stacks, and Queues 23 5 Binary Trees 32 6 General Trees 40 7 Internal Sorting 46 8 File Processing and External Sorting 54 9Searching 58 10 Indexing 64 11 Graphs 69 12 Lists and Arrays Revisited 76 13 Advanced Tree Structures 82 i
ii Contents 14 Analysis Techniques 88 15 Limits to Computation 94
Preface Contained herein are the solutions to all exercises from the textbook A Practical Introduction to Data Structures and Algorithm Analysis, 2nd edition. For most of the problems requiring an algorithm I have given actual code. In a few cases I have presented pseudocode. Please be aware that the code presented in this manual has not actually been compiled and tested. While I believe the algorithms to be essentially correct, there may be errors in syntax as well as semantics. Most importantly, these solutions provide a guide to the instructor as to the intended answer, rather than usable programs.
专升本《数据结构》 一、（共75题,共150分） 1. 数据的基本单位是（）。（2分） A.数据元素 B.记录 C.数据对象 D.数据项 .标准答案：A 2. （）是数据的不可分割的最小单位。（2分） A.数据对象 B.数据元素 C.数据类型 D.数据项 .标准答案：D 3. 算法的空间复杂度是对算法（）的度量。（2分） A.时间效率 B.空间效率 C.可读性 D.健壮性 .标准答案：B 4. （）是限制了数据元素的内部结构仅为一个字符的线性表。（2分） A.栈 B.队列 C.串 D.数组 .标准答案：B 5. 串的长度是指串中所含（）的个数。（2分） A.不同字符 B.不同字母 C.相同字符 D.所有字符 .标准答案：D 6. 采用带头结点双向链表存储的线性表，在删除一个元素时，需要修改指针（）次。（2分） A.1 B.2 C.3 D.4 .标准答案：B 7. 线性表的顺序存储结构是一种（）的存储结构。（2分） A.顺序存取 B.随机存取 C.索引存取 D.Hash存取 .标准答案：B 8. 数组a[1..m]采用顺序存储，a[1]和a[m]地址分别为1024和1150，每个元素占2字节，则m是（）。（2分） A.64 B.32 C.16 D.8 .标准答案：A 9. 深度为h的二叉树，第h层最多有（）个结点。（2分） A.h B.2h-1 C.2h-1 D.2h .标准答案：C 10. m个结点的二叉树，其对应的二叉链表共有（）个非空链域。（2分） A.m B.m+1 C.2m D.m-1 .标准答案：B 11. 下面叙述错误的是（）。（2分） A.顺序表是借助物理单元相邻表示数据元素之间的逻辑关系 B.对于空队列进行出队操作过程中发生下溢现象 C.有向图的邻接矩阵一定是对称的 D.具有相同的叶子个数和具有相同的叶子权值的赫夫曼树不是唯一的 .标准答案：C 12. 以下与数据的存储结构无关的术语是（）。（2分） A.循环队列 B.双向链表 C.哈希表 D.数组 .标准答案：D 13. 在一个长度为n的链式栈中出栈实现算法的时间复杂度为（）。（2分） A.O(1) B.O(log n) C.O(n) D.O(n2) .标准答案：A 14. 在具有k个度数为2的二叉树中，必有（）个叶子结点。（2分） A.k B.k-1 C.2k D.k+1 .标准答案：D 15. 在关键字序列（10,20,30,40,50）中，采用折半法查找20，关键字之间比较需要（）次。（2分） A.1 B.2 C.3 D.4 .标准答案：C 16. 16某二叉树的后序遍历序列和和中序遍历序列均为abcd，该二叉树的前序遍历序列是（）。（2分） A.abcd B.dcba C.acbd D.dbca .标准答案：B 17. n个顶点的无向连通图的生成树，至少有（）个边。（2分） A.n(n-1) B.n(n-1)/2 C.2n D.n-1 .标准答案：D 18. 可以采用（）这种数据结构，实现二叉树的层次遍历运算。（2分） A.队列 B.树 C.栈 D.集合 .标准答案：A
“数据结构”期末考试试题 一、单选题(每小题2分，共12分) 1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。 A． HL＝ps p一>next＝HL B． p一>next＝HL；HL＝p3 C． p一>next＝Hl；p＝HL； D． p一>next＝HL一>next;HL一>next＝p； 2．n个顶点的强连通图中至少含有( )。 A.n—l条有向边 B.n条有向边 C.n(n—1)／2条有向边 D.n(n一1)条有向边 3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A.O(1) B.O(n) C.O(1Ogzn) D.O(n2) 4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 A．24 B．48 C． 72 D． 53 5．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。 A.整形 B.引用型 C.指针型 D.常值引用型· 6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。 A．O(n) B．O(1) C．O(n2) D．O(10g2n) 二、填空题(每空1分，共28分) 1．数据的存储结构被分为——、——、——和——四种。 2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。 3．——中缀表达式 3十x*(2.4／5—6)所对应的后缀表达式为————。 4．在一棵高度为h的3叉树中，最多含有——结点。 5．假定一棵二叉树的结点数为18，则它的最小深度为——，最大深度为——· 6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定——该结点的值。 7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。 8．表示图的三种存储结构为——、——和———。 9．对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为——，对用邻接表表示的图进行任一种遍历时，其时间复杂度为——。 10．从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为——和——· 11．假定对长度n＝144的线性表进行索引顺序查找，并假定每个子表的长度均
2019年内蒙古工业大学考研专业课初试大纲 数据结构自命题考试大纲 科目名称数据结构科目代码808 一、考试范围及要点 1．数据结构的基本概念 数据、数据元素与数据项的概念及其相互间关系，清楚数据的逻辑结构、存储结构的联系与区别，理解抽象数据类型的概念，掌握算法的时间性能分析和空间性能分析方法。要点是分析算法的时间和空间性能。 2．线性表 线性表的基本概念、线性表的顺序实现、线性表的链式实现、线性表顺序实现与链式实现的异同。要点是线性表的顺序结构与线性表的链式结构的插入、删除和按关键字查找的算法实现。 3．栈与队列 栈与队列的概念与基本操作，栈的应用，链队列与循环队列的组织方法。要点是栈的基本操作、链队列与循环队列的组织方法与基本操作的实现。 4．串 串的概念与串的表示和实现。要点是以堆形式实现的串的组织方法与基本操作的实现、模式匹配算法。 5．数组与广义表 多维数组的结构特点及其存储地址计算方法，矩阵的压缩存储思想，广义表及其存储结构。 要点是数组的存储地址计算、矩阵压缩存储地址映射关系及广义表的逻辑结构与存储结构。 6．树与二叉树 树的基本概念，二叉树的定义与性质，二叉树的存储结构，二叉树的遍历算法，树和森林的基本概念与哈夫曼树等。要点是二叉树的顺序存储结构与链式存储结构，二叉树的遍历算法与哈夫曼编码。 7．图 图的基本概念，图的两种存储结构(邻接矩阵和邻接表)的表示方法，图的遍历算法，图的最小生成树的概念及相关算法，拓扑排序与关健路径。要点是图的存储结构与图的遍历算法，最小生成树的概念及相关算法，图的拓扑排序算法。 8．查找 查找的基本概念，静态查找表的实现，二叉排序树的概念及查找，哈希表的思想及相关算法。要点是折半查找、二叉排序树与哈希表。 9．排序 排序的基本概念，插入排序，交换排序，选择排序，归并排序与基数排序。要点是快速排序、堆排序与归并排序算法实现与性能分析。 二、考试形式及试卷结构 考试形式： 闭卷笔试 试卷结构： 1．单项选择题； 2．简答与计算题 参考书目： 数据结构(C语言版)，严蔚敏吴伟民编著，清华大学出版社，2012 数据结构习题与解析，李春葆编著，清华大学出版社，2013 精都考研网（专业课精编资料、一对一辅导、视频网课）https://www.doczj.com/doc/dc13098437.html,
本科插班生考试大纲《数据结构与算法》 《数据结构与算法》专业课程考试大纲 考试科目名称：数据结构与算法 一、考试性质 普通高等学校本科插班生招生考试是由专科毕业生参加的选拔性考试。高等学校根据考生的成绩，按已确定的招生计划，德、智、体全面衡量，择优录取。该考生所包含的内容将大致稳定，试题形式多种，具有对学生把握本课程程度的较强识别、区分能力。 二.考试内容及要求 一、考试基本要求 通过数据结构与算法理论的学习，使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步了解对算法的时间分析和空间分析技术；配合算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力，对理论和实践的操作使学生得到全面的领会和深刻的认识。 二、考核知识点及考核要求 本大纲的考核中，按照“识记”、“领会”、“简单应用”和“综合应用”等四个层次规定应达到的能力层次要求。各能力层次为递进等级关系，后者必须建立在前者的基础上，其含义是： 识记：要求考生知道有关的名词、概念、原理、知识的含义，并能正确认识或识别。 领会：要求在识记的基础上，能把握相关的基本概念、基本原理和基本方法，掌握有关概念、原理、方法的区别与联系。 简单应用：要求在领会的基础上，运用所掌握的基本概念、基本原理和基本方法中的少量知识点，分析和解决一般的理论问题或实际问题。 综合应用：要求在简单应用的基础上，运用学过的多个知识点，综合分析和解决比较复杂的实际问题。
第1章绪论 一、考核知识点 1、数据结构的基本概念 2、抽象数据类型的表示和实现 3、算法的概念和特性 4、算法时间复杂度和空间复杂度分析 二、考核要求 1、识记 （1）数据结构的研究内容 2、领会 （1）抽象数据类型的表示和实现 （2）算法的定义和特性 （3）评价算法优劣的基本标准 3、简单应用 （1）简单数据结构的程序设计 （2）简单数据结构程序的时间复杂度和空间复杂度分析 4、综合应用 （1）数据结构的一些基本概念 （2）算法的时间复杂度分析 第2章线性表 一、考核知识点 1、线性表的类型定义 2、线性表的顺序表示和实现 3、线性表的链式表示和实现 4、线性表的应用
《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 、 1. 对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为 (c )。 (A)、正确性但).可行性(C).健壮性 2 ?设S为C语言的语句,计算机执行下面算法时， for(i=n-1 ; i>=0; i--) for(j=0 ; jvi; j++) (A)、n2(B). O(nlgn) 3?折半查找法适用于( a (D). 输入性 算法的时间复杂度为(d S； (C). O(n) (D). )。 O(n2) (A)、有序顺序表(B)、有序单链表 (C)、有序顺序表和有序单链表都可以 4 .顺序存储结构的优势是( d )。 (A)、利于插入操作(B)、利于删除操作 (C)、利于顺序访问(D)、利于随机访问 5. 深度为k的完全二叉树，其叶子结点必在第 (A)、k-1 ( B)、k (C)、k-1 和 6. 具有60个结点的二叉树，其叶子结点有 (A)、11 ( B)、13 ( C)、48 (D)、无限制 c )层上。 (D)、1 至 k 12个，则度过1 (D)、37 k 的结点数为( 7 .图的Depth-First Search(DFS) 遍历思想实际上是二叉树( 法的推广。 (A)、先序(B)、中序(C)、后序(D)、层序 8.在下列链队列Q中，元素a出队的操作序列为( a )遍历方 front (A )、 (B )、 (C)、 (D )、p=Q.front->next; p->next= Q.front->next; p=Q.front->next; Q.front->next=p->next; p=Q.rear->next; p->next= Q.rear->next; p=Q->next; Q->next=p->next; 9. Huffman树的带权路径长度WPL等于( (A)、除根结点之外的所有结点权值之和(C)、各叶子结点的带权路径长度之和(B) 、 ) 所有结点权值之和 根结点的值 b ■
广东技术师范学院 《计算机科学技术导论》（本科插班生入学考试）考试大纲 （计算机科学学院制定） 一、考试性质与试题命题的原则 《计算机科学技术导论》是广东技术师范学院为计算机科学与技术等专业的本科 插班生入学考试所设置的一个专业课考试科目。它的评价标准是高等学校计算机类专 业高职高专毕业生或相近专业毕业生能达到的及格或及格以上水平，以保证录取的本 科插班生具有一定的计算机科学基础理论及必要的专业技能能力，以利于择优选拔。 考试对象为参加教育部面向全面招生的本科插班生入学考试的高职高专毕业生以及 具有同等学历的报考人员。 《计算机科学技术导论》课程考试的目的和要求是：准确、简明地考核考生对计算机科学体系框架、计算机科学基本知识以及现代计算机发展方向、主要理论和科学方法的掌握和理解水平，衡量他们在理解、掌握和运用这些基本专业理论和知识的基础上，观察、分析和解决技术问题的能力。 二、考试形式及试卷结构 1.考试形式为闭卷、笔试；考试时间为120分钟，试卷满分为100分。 2、试题命制的原则：作为一项选拔性考试，《计算机科学技术导论》考试试题在设计上应具有较高的信度和效度、必要的区分度和合理的难度。命题根据本大纲规定的考试目标和考核内容，考试命题应具有一定的覆盖面且重点突出，侧重考核考生对本学科的基本理论、基本知识和基本技能的掌握程度，以及运用所学的知识解决实际问题的能力。 3.试题对不同能力层次要求的分数比例：识记25%、理解55%，综合应用15%，其他5%。 4.合理安排试题的难度结构。试题难易度分为易、较易、较难、难四个等级。试卷中难易度试题的分布比例，易约占25%，较易约占35%，较难约占20%，难约占10%。 5.试卷的题型有：单项选择题、多项选择题、简答题、改错题、计算题、填空题、综合题等。可根据考核要求，适当安排各种题型数量的比例，达到考核对知识点的识记、理解以及运用水平和能力。
一、选择题（共15题，每题2分，共计30分） 1、单链表的一个存储结点包含（ C ） A.指针域和链域 B.指针域或链域 C.数据域或指针域 D.数据域和链域 2、采用线性链表表示一个向量时，要求占用的存储空间地址（ D ）。 A、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、可连续可不连续 3、当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（ B ）。 A. n-2 B. n-1 C. n D. n+1 4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。 A、s→next = p→next; p→next = s; B、p→next = s; s→next k = q; C、p→next = s→next; s→next = p; D、q→next = s; s→next = p; 5、在数组A中，每一个数组元素A[i, j] 占用3个存储字，行下标i从1到8，列下标j 从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（ C ）。 A、 80 B、 100 C、 240 D、 270 6、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。 A、栈 B、队列 C、循环队列 D、优先队列 7、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。 A、4, 3, 2, 1 B、2, 4, 3, 1 C、1, 2, 3, 4 D、3, 2, 1, 4 8.下述各类表中可以随机访问的是（D ）。 A. 单向链表 B. 双向链表 C.单向循环链表 D.顺序表 9.在一个长度为n的顺序表中为了删除第5个元素，从前到后依次移动了15个元素。则原顺序表的长度为（ B ）。 A. 21 B. 20 C. 19 D. 25 10.元素1，3，5按顺序依次进栈，则该栈的不可能的输出序列是（ B ）。 A. 5 3 1 B. 5 1 3 C. 3 1 5 D. 1 5 3 11.一个队列的入队序列是5，6，7，8，则队列的输出序列是（ A ）。 A. 5 6 7 8 B. 8 7 6 5 C. 7 8 6 5 D.可能有多种情况 12．在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（C ）。 A．p=q->next B．p->next=q C．p->next=q->next D．q->next=NULL 13.设一棵哈夫曼树共有n个非叶结点，则该树一共有（ B ）个结点。 A. 2*n-1 B. 2*n +1 C. 2*n D. 2*(n-1) 14.对如图1所示二叉树进行中序遍历，结果是（ A ）。 A. dfebagc B. defbagc C. defbacg D.dbaefcg
韩山师范学院2019年本科插班生招生考试 计算机科学与技术 专业 数据结构 试卷（A 卷） 一、单项选择题（每题2分，共30分） 1. 由3个结点可以构造出多少种不同的二叉树？（ ） A ．2 B ．3 C ．4 D ．5 2. 一个栈的输入序列为A B C ，则下列序列中不可能是栈的输出序列的是( )。 A. B C A B.C B A C. C A B D. A B C 3. 算法的时间复杂度取决于（ ） 。 A ．问题的规模 B ．待处理数据的初态 C ．计算机的配置 D ．A 和B 4. 数组的逻辑结构不同于下列（ ）的逻辑结构。 A. 树 B. 栈 C. 队列 D. 线性表 5. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（ ）。 A ．8 B ．63.5 C ．63 D ．7 6. 用邻接表表示图进行深度优先遍历时，通常借助（ ）来实现算法。 A ．队列 B. 栈 C. 树 D ．图 7. 数据的最小单位是（ ）。 A.数据元素 B.数据项 C.数据类型 D. 数据变量
8. 设无向图G中有n个顶点，则该无向图的最小生成树上有（） 条边。 A. 2n B. 2n-1 C. n-1 D. n 9. 为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）。 A.栈 B.队列 C.线性表 D.有序表 10. 程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂 度为（）。 n) C.O(n2) D.O(n3/2) A. O(n) B. O(nlog 2 11.设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）。 A. q=p->next；p->next=q->next；free(q)； B. q=p->next；p->data=q->data；free(q)； C. q=p->next；p->data=q->data；p->next=q->next；free(q)； D. q=p->next；q->data=p->data；p->next=q->next；free(q)； 12. 顺序表中第一个元素的存储地址是100，每个元素的长度为2，则 第15个元素的地址是（）。 A.110 B.108 C.100 D.128 13. 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）。 A．所有的结点均无左孩子 B．所有的结点均无右孩子 C．只有一个叶子结点 D．是任意一棵二叉树 14. 具有n个顶点的有向图最多有（）条边。 A．n B．n2 C．n(n+1) D．n(n-1) 15. 设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i 的入度为（）。 A.第i行非0元素的个数之和 B. 第i列非0元素的个数之和 C.第i行0元素的个数之和 D. 第i列0元素的个数之和
2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序
《数据结构》考试大纲 I 考试的性质与目的 本科插班生考试是由专科毕业生参加的选拔性考试。《数据结构》是计算机科学与技术专业（本科）的一门专业基础课程，考试主要检查考生对常用基本数据结构（顺序表、链表、栈、队列、树、二叉树、图等）的逻辑结构、存储结构和相应算法的掌握程度，以保证后续课程的学习。 II 考试的内容 一、考试基本要求 1、基本理论知识 （l）、数据结构的基本概念和基本术语，算法的描述方法和算法分析的基本概念。 （2）、线性表的基本概念、线性表的基本操作以及这些操作分别在顺序存储和链式存储结构下的实现及复杂度分析。 （3）、栈和队列的定义、存储结构、实现和典型应用。 （4）、串的定义及其基本操作。 （5）、数组的定义、运算和顺序存储。 （6）、树的定义、基本术语和存储结构，二叉树的定义和性质、二叉树的存储结构及其各种操作，哈夫曼树的概念和应用。 （7）、图的定义和术语、图的存储结构及其各种操作。 （8）、各种查找方法的算法、适用范围及时间复杂度的分析。 （9）、多种内排算法的基本思想和算法的时间复杂度分析，不同排序方法的比较。 2、基本技能 （1）、能阅读用类C语言编写的算法。 （2）、能分析算法所完成的功能、运行结果和时间复杂度。 （3）、能根据要求用类C语言编写算法。 二、考核知识点及考核要求 第一章绪论 一、考核知识点 1.数据、数据元素、数据项、数据对象、数据结构、逻辑结构、物理结构、元素、结点等基本概念。抽象数据类型的定义、表示和实现方法。 2.算法、算法的特性、如何用类C语言来描述算法。 3.算法设计的基本要求以及计算语句频度和估算算法时间复杂度的方法。 二、考核要求 1.识记：有关数据结构的基本概念，四种基本数据结构的特点。 2.理解：四种基本数据结构的基本运算，算法复杂度度量的基本概念。 3.应用：用类C语言描述算法