苏州大学数据结构课程试卷2卷（共 5页）
考试形式：闭卷年月院系 ______________ 年级 ______________ 专业 ______________
学号 ______________ 姓名 ______________ 成绩 ______________
一、填空（2分×16）
1、下面程序段的时间复杂度为____mn_______。
f or (i=0; i for (j=0; j A[i][j]=i*j; 2、设一个数列为1，2，3，4，5，6，通过栈结构可以排成的顺序数列为 ______________________________（写2个），不可以排成的顺序数列为 _______________________（写2个）。 3、算术表达式A/(B*(E+F))-T**K的逆波兰表示式为____ABEF+*/TK**- ______________________。 4、将10阶下三角矩阵A[1..10][1..10]压缩到一维数组SA[0..54]中，并采用行序为主序，则元素A[5][4]在数组SA中的下标为__________________。 5、设字符串s1='abcde',s2='opqr', 则Concat(s1,s2)=______________, Index(s2,'p')=_______。 6、已知一棵二叉树的中序遍历结果为DBHEAFICG，后序遍历结果为DHEBIFGCA，则先序遍历结果为_________________________。 7、设有序表有100个元素，在折半查找时，最大比较次数是_________，最小比较次数是_____________。 8、设哈希函数H(k)=k mod 11，哈希表的地址空间为0～11，假定哈希表中已填有关键字分别为17，60，29的记录。若采用二次探测再散列，则关键字为39的第四个记录应填入位置______________。若不采用二次探测再散列，而是采用线性探测再散列，则则关键字为39的第四个记录应填入位置______________。 9、设有关键字输入序列：（45，25，80，60，18，30，12，40，70），生成一棵二叉查找树，在等查找概率情况下查找成功时的平均查找长度为______________。 10、以下为链式Stack的拷贝构造函数，请在其中的下划线处填上适当的内容。 Stack :: Stack(const Stack &original) // copy constructor /* Post: The Stack is initialized as a copy of Stack original. */ { Node *new_copy, *original_node = __ _______; if (original_node == NULL) top_node = NULL; else { // Duplicate the linked nodes. top_node = new_copy = ______________________; while (original_node->next != NULL) { original_node = original_node->next; new_copy->next = new Node(original_node->entry); ________________________; } } } 二、应用题 1、对于如图所示的树，试回答：(1)树的度是多少？树的深度是多少？(2)哪些为非终端结点？(3)画出其孩子兄弟链表。（4）将该树转换为二叉树。(10分) A B C D F E G J H I K A 2、以递归树形式画出汉诺塔递归函数move(3,1,2,3)的执行过程。（8分） 3、已知如图所示带权有向图G ，（1）给出邻接矩阵和邻接表；（2）从结点V1出发分别对G 进行深度优先搜索和广度优先搜索，给出结点序列；（3）给出G 的一个拓扑序列。（10分） 23 18 7 56A 4 4、（1）设一组记录的关键字序列为（25，50，15，35，80，85，20，40，36，70），对其进行2-路归并排序，写出排序过程。 （2）在堆排序、快速排序和归并排序三种排序方法中，若从节省存储空间考虑，则应首选哪种方法？若只从算法稳定性考虑，则应选取哪种方法？若只从最坏情况下排序最快并且要节省内存考虑，应选取哪种方法？（10分） 三、算法设计题 1、写出循环队列的类定义，并编写代码，实现循环队列的入队和出队方法。（10分） class Queue（总10分） {public: (4分) Queue(); bool empty(); bool full(); Error_code Append(Qentry &item); Error_code serve(); Error_code retrieve(Qentry &item); Private: int rear; int length; Qentry entry[Maxq]; } Error_code append(Qentry &item) { if (length= =maxq) return OVERFLOW; rear=(rear+1) % maxq; entry[rear]=e; length++; return OK; } （3分） Error_code serve(Qentry &item) { if (length= =0) return ERROR; head=((rear+ maxq)-length+1) % maxq; item=entry[head]; length--; return OK; } （3分） 2、编写算法，在兄弟孩子链表表示的树中求叶子结点数。（10分） 树的孩子兄弟链表定义：typedef struct CSNode{ ElemType data; Struct CSNode *firstchild, *nextsibling; } CSNode, *CSTree; int tree_leafcount (CSTree T ); 3、n个顶点的有向图的邻接表定义如下： typedef struct ArcNode { int adjvex ; struct ArcNode *nextarc ; } ArcNode ; typedef struct VNode { vertextype data ; Arcnode *firstarc ; } VNode ;AdjList[MAX_VERTEX_NUM] ; typedef struct{ AdjList vertices; int vexnum,arcnum; }ALGraph; 请写出计算图中出度为2的顶点个数的算法。 (10分) int graph_count(ALGraph G); 一、填空题 1、 在任何需要数据反转的问题里，首先应考虑用 栈 来保存数据。 2、在顺序线性表下，根据位置来进行元素的插入和删除，主要的时间花费在 移动后续元素位置 ；在单链表下进行元素的插入和删除，主要时间花费在 找到目标元素位置 。 3、 具有n 个顶点的无向图，至少要有 n-1 条边，才能保证该图是连通图。 4、 用二分查找方法进行查找，要求数据文件应为有序序列，且限于顺序存储结构。 5、在哈希查找中，评判一个哈希函数优劣的两个主要指标是： 散列分布均匀性和冲突解决方法。 6、由三个结点构成的二叉树，共有 5 种不同的形状。 7、高度为h (h ≥ 1)的完全二叉树的结点数在2n-1和 2n -1之间。 (设只有1个根结点的二叉树高度为1) 8、对于有n (n ≥ 1)个顶点的连通图，其生成树有 n-1 条无向边。n(n ≥ 1)个顶点的有向完全图有 n(n-1) 条有向边。 9、图的深度优先搜索遍历类似于树的 先序 遍历。图的广度优先搜索遍历需要用到的辅助数据结构是 队列 。 10、以关键字比较为基础的排序方法所能达到的最好时间复杂度为 n 。排序过程中总的关键字比较次数与记录的初始排列顺序无关的排序方法有 选择排序 。稳定的算法有 冒泡排序、插入排序 。 二、应用题 1、简述拓扑排序的实际意义，并写出下图的1个深度优先拓扑序列和1个广度优先拓扑序列。 拓扑排序的实际意义:如果按照拓扑排序的顶点次序，在开始每一项活动时，能够保证它的所有前驱活动都已经完成，从而使整个工程顺序进行，不会出现冲突情况。 DFS:acfhdgbe BFS:acdfhbeg 2、已知一个无向连通图如图所示： 1 34a b d e c f 2 22g h 21211 1) 请用Prim 算法构造该无向图的最小生成树，给出详细求解过程。 2) 分别用邻接矩阵和邻接表这两种存储结构表示该无向图。 3) 请写出一个合理的从顶点a 出发得到的DFS 序列(假设邻接表中边表按照递增序)。 4) 请写出一个合理的从顶点a 出发得到的BFS 序列(假设邻接表中边表按照递增序)。 3、简述插入排序的基本思想，并对以下关键字集合，{72，73，71，23，94，16，05，68}进行插入排序，计算总的比较次数。 1:72 73 71 23 94 16 05 68 东北大学继续教育学院 数据结构II 试卷（作业考核线上） B 卷 （共8 页） 一、单选题（每小题2分，共10小题，20分） [A ] 1．抽象数据类型的三个组成部分分别为 A．数据对象、数据关系和基本操作 B．数据元素、逻辑结构和存储结构 C．数据项、数据元素和数据类型 D．数据元素、数据结构和数据类型 [D ] 2．下列各式中，按增长率由小至大的顺序正确排列的是 A．n，n！，2n ，n3/2 B．n3/2，2n，n logn，2100 C．2n，log n，n logn，n3/2 D．2100，logn, 2n, n n [A ] 3. 已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向 另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为 A. q->next=s->next；s->next=p； B. s->next=p；q->next=s->next； C. p->next=s->next；s->next=q； D. s->next=q；p->next=s->next； [C ] 4．二维数组A[20][10]采用行优先的存储方法，若每个元素占2个存储单元，且第1 个元素的首地址为200，则元素A[8][9]的存储地址为 A．374 B．576 C．378 D．580 [B ] 5．设有一个顺序栈的入栈序列是a、b、c，则3个元素都出栈的可能不同排列个数为 A．4 B．5 C. 6 D. 7 [D ] 6. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的 叶子数为 A．5 B．6 C．7 D．8 [C ] 7．以下说法不正确的是 A．无向图中的极大连通子图称为连通分量 B．连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D．有向图的遍历不可采用广度优先搜索 [B ] 8. 假设在构建散列表时，采用线性探测解决冲突。若连续插入的n个关键字都是同义 词，则查找其中最后插入的关键字时，所需进行的比较次数为 A. n-1 B. n C. n+l D. n+2 [B ] 9．设置溢出区的文件是 A．索引非顺序文件B．ISAM文件 C．VSAM文件D．顺序文件 [A ] 10. 已知一组关键字为{25,48,36,72,79,82,23,40,16,35}，其中每相邻两个为有序子 序列。对这些子序列进行一趟两两归并的结果是 A.{25,36,48,72,23,40,79,82,16,35} B.{25,36,48,72,16,23,40,79,82,35} C.{25,36,48,72,16,23,35,40,79,82} D.{16,23,25,35,36,40,48,72,79,82} 二、填空题（每小题1分，共10小题，10分） 11.下面程序段中带下划线的语句的执行次数的数量级是( log n )。 2 i=1； WHILE(i 2017年数据结构期末考试题及答案 一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出 8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点 数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域 为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是 _____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。A．P所指结点指针字段的值为空B．P的值与H的值相等 C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等 4. 栈的定义不涉及数据的__________。 A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构 5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。 A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5 6. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。 A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在 7.对于一棵具有n个结点，度为3的树来说，____________。 A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓ D．至少在某一层上正好有3个结点 8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。 A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点 D．是一个有根有向图 9. 特殊矩阵用行优先顺序表表示，_____________ A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素 武汉大学计算机学院 2011年－2012学年第二学期“数据结构”考试试题（A） 要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。 一、单项选择题（共20小题，每小题2分，共40分） 1. 下列各选项中属于逻辑结构的是。 A. 哈希表 B.有序表 C. 线索二叉树 D. 单链表 2. 从逻辑上可以把数据结构分为两大类。 A. 动态结构、静态结构 B. 顺序结构、链式结构 C. 线性结构、非线性结构 D. 初等结构、构造型结构 3. 算法的时间复杂度取决于。 A. 问题的规模 B. 待处理数据的初始状态 C. A和B D. A和B都不对 4. 建一个有n个元素的有序单链表，其算法的时间复杂度为。 A. O(1) B. O(n) C. O(nlogn) D. O(n2) 5. 若某线性表中最常用的操作是读取第i个元素和找到第i个元素的直接前驱，则应 采用存储方式最节省运算时间。 A. 单链表 B. 顺序表 C. 双向链表 D. 单循环链表 6. 执行操作时，需要使用队列作为辅助存储空间。 A. 查找哈希表 B. 广度优先搜索 C. 用Dijkstra算法求最短路径 D. 深度优先搜索网 7. 用链式方式存储的队列，在进行删除运算时。 A. 仅修改头指针 B. 仅修改尾指针 C. 队首、队尾指针都要修改 D. 队首、队尾指针可能都要修改 8. 递归过程或函数调用时，处理参数及返回地址，要用一种称为的数据结构。 A. 队列 B. 多维数组 C. 栈 D. 线性表 9. 线索二叉树是一种结构。 A. 逻辑 B. 逻辑和存储 C. 物理 D. 线性 10. 已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，那么其前缀形 式应为。 A. –A+B*C/DE B. –A+B*CD/E C. -+*ABC/DE D. -+A*BC/DE 少年易学老难成，一寸光阴不可轻- 百度文库 《数据结构》 一、单项选择题（本大题共10小题，每小题3分，共30分） 1、若进栈的序列为1，2，3，4，则不可能得到的出栈序列是（）。 A. 3,2,1,4 B. 3,2,4,1 C. 4,2,3,1 D. 2,3,4,1 2、深度为k的完全二叉树所含叶结点的个数最多为（），设根结点在第1层上。 A. 2k B. 2k-1 C. k D. 2k-1 3、衡量查找算法效率的主要标准是（）。 A. 元素个数 B. 所需的存储量 C. 平均查找长度 D. 算法难易程度 4、与线性表的顺序存储不相符的特性是（）。 A. 插入和删除操作灵活 B. 需要连续的存储空间 C. 便于随机访问 D. 存储密度大 5、若进队序列为1，2，3，则出队序列是（）。 A. 3,2,1 B. 1,2,3 C. 1,3,2 D. 3,1,2 6、不带头结点的单链表L为空的判定条件是（）。 A. L==NULL B. L->next==NULL C. L->next==L D. L!=NULL 7、union(A,B,C)表示求集合A和B的并集C。若A={a,b,c},B={c,d},则union(A,B,C)运算后C=（）。 A．{a,b,c,d} B．{a,b,c} C．{a,b} D．{c,d} 8、数组A中，每个元素的长度为3个存储单元，行下标i从1到5，列下标j从1到6，从首地址SA开始连续存放在存储器内，存放该数组至少需要的存储单元数是（）。 A. 90 B. 70 C. 50 D. 30 9、遍历一棵具有n个结点的二叉树，在先序序列、中序序列和后序序列中所有叶子结点的相对次序（）。 A. 都不相同 B. 完全相同 C. 先序和中序相同 D. 中序和后序相同 10、用给定的哈夫曼编码来压缩数据文件，其压缩效率主要取决于（）。 A. 文件长度 B. 平均码长 C. 被压缩文件的特征 D. 以上都不是 1、设有如下遗产继承规则：丈夫和妻子可以互相继承遗产，子女可以继承父亲或母亲的遗产，子女间不能相互继承，则表示该遗产继承关系的最合适的数据结构应该是（）。 A. 树 B. 图 C. 数组 D. 二叉树 2、下列排序中，占用辅助空间最多的是（）。 A. 堆排序 B. 冒泡排序 C. 直接选择排序 D. 二路归并 3、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）。 A. 选择排序 B. 冒泡排序 C. 希尔排序 D. 插入排序 4、在待排序序列局部有序的情况下，最好的内部排序应该是（）。 A. 直接选择排序 B. 堆排序 C. 直接插入排序 D. 快速排序 5、下列排序算法中不稳定的是（）。 A. 直接选择排序 B. 直接插入排序 C. 起泡排序 D. 归并排序 6、当利用大小为N的数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。 A. top++ B. top-- C. top=0 D. top=N-1 7、在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。 A. 2 B. 3 C. 4 D. 5 8、利用3,6,8,12,5,7这六个值作为叶子结点的权，生成一棵哈夫曼树，该树的深度为（）。 A. 3 B. 4 数据结构考试题库 绪论 一、填空题 1.数据的逻辑结构被分为集合、(线性结构)、(树形结构)和(图状结构)四种。 2.物理结构是数据结构在计算机中的表示，又称为(存储结构)。 3.数据元素的逻辑结构包括( 线性)、(树)和图状结构3种类型，树形结构和图状结构合称为(非线性结构)。 4.(数据元素)是数据的基本单位，(数据项)是数据不可分割的最小单位。 5.线性结构中元素之间存在(一个对一个)关系，树形结构中元素之间存在(一个对多个)关系，图状结构中元素之间存在(多个对多个)关系。 ？6.数据结构是一门研究非数值计算的程序设计问题中：计算机的(数据元素)以及它们之间的(关系)和(运筹)等的学科。 7.算法的五个重要特性为有穷性、确定性、(输入)、(输出)和(可行性)。 二、选择题 1.数据的不可分割的基本单位是(D)。 A.元素 B.结点 C.数据类型 D.数据项 *2.线性表的逻辑顺序与存储顺序总是一致的，这种说法(B)。 A.正确 B.不正确 C.不确定 D.无法选择 3.线性结构是指数据元素之间存在一种(D)。 精心整理，用心做精品2 A.一对多关系 B.多对多关系 C.多对一关系 D.一对一关系 4.在数据结构中，从逻辑上可以把数据结构分成(A)。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 5.线性表若采用链式存储结构时，要求内存中可用存储单元的 地址( D)。 A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续不连续都可以 三、简答题 1.算法的特性是什么。 答：有穷性确定性可行性有0或多个输入有1或多个输出线性结构 一、填空题 1.在一个长度为n的线性表中删除第i个元素（1≤i≤n）时，需向前移动(n-i)个元素。 2.从循环队列中删除一个元素时，其操作是(先移动队首指针，后取出元素)。 3.在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为(p->next)。 4.在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把(p->next)的值赋给q->next，然后(q->date)的值赋给p->next。 5.从一个栈删除元素时，首先取出(栈顶元素)，然后再使(栈顶指针)减1。 6.子串的定位操作通常称做串的(模式匹配)。 精心整理，用心做精品3 苏州大学计算机学院数据结构与操作系统考研复试指南本文包含：具有苏大特色的《数据结构与操作系统》（872）备考指南、苏大特色的复试，分量绝对足。 本文不包含：不包含政治英语数学等内容。 一、简单介绍 本人2013届考研，我是到大三下了才开始有考研的想法的，被两个关系很好的老师给“忽悠”的。本科是一所内地普通的二本院校，一般来讲考苏大的本科背景都差不多。我本科阶段的成绩并不好，挂科也有，60徘徊的科目也不少。英语六级过了但是考了三次，软考过了软设也考了三次，然后就没有了，说这些主要是为了让学弟学妹们有所比较，说实在的讲到底考研最重要的还是坚持，很多的同学就是不能坚持，甚至考到最后了弃考的。 二、《数据结构与操作系统》（872）备考指南 （一）时间安排 我当时是最后两个月了才开始看的，并且只在下午看。我的基础很一般，专业课的复习既要重视因为分数多好拿分，复试的同学除了跨专业的几乎没有低于120的，我考了136，所以说要重视。同时又要轻视因为实在是很简单的，比起408难度降低了很多。要记得东西稍微有点多，所以可以靠后点开始复习。 （二）全部书籍资料准备 0．请忽略苏大所谓的参考教程，特别是那本板砖操作系统，如果是对付考研绝对没必要看。 1．我没有买任何专业课方面的书只在学校图书馆借了两本书《计算机专业考研辅导丛书：数据结构联考辅导教程(2010版)》、《计算机专业考研辅导丛书:计算机操作系统联考辅导教程(2011版)》，这两本书用来对付苏大的872非常好，并不要求最新的，要知道苏 大的考纲都很多年没改了，试卷结构题型也比较稳定。相信你们学校图书馆也肯定有借。 2．打印一份苏大872考纲，只要打印《数据结构与操作系统》的就可以了。 3．打印苏大99-2010年的872真题（某些年份可能缺失），论坛就有得下。 （三）复习过程 1．首先要看一遍苏大的考纲和真题，了解苏大考什么、怎么考。考纲更重要的作用是看不考什么，例如树的遍历，大纲上是没有层次遍历的，这个一直也没考过。看真题的时候我把考点列成了一张表，这个也是为了能让自己在复习的时候有的放矢，分清重点。 2．接下来就是复习那两本书。操作系统：书并不算厚，从头到尾的看，做些笔记，做练习题的时候完全可以跳过选择题。可以将真题的名词解释收集到一起，看书的时候就摘抄下来，方便以后背诵。苏大的操作系统靠的再难也就只有进程同步了，知道经典了同步问题其实就差不多了，无非就是场景换换，没记错的话13年是没有考同步的。数据结构：名词解释部分方法同操作系统，特别重要的就是动手写，要准备很厚一叠白纸，那些基本的操作和算法一定要懂，我想这对很多同学来讲都是难点，但是不要畏难。这本书的亮点就在它的那些算法部分的练习题，基本上苏大考过的会考的都可以找到一模一样或者类似的，并且他分了难度星级，很多五星级的是可以跳过的，那么难是不会考的。一定要动手写，实在搞不懂背也要背下来。除了名词解释，只要看算法题就可以了，其他题目完全可以忽略。 3．第2步的过程会比较久，但是务必坚持，有些经典算法要经常练习。注意控制好节奏，操作系统可以快点复习，主要记的多，可以集中背诵。数据结构务必多写（再怎么强调也不为过），开始会有些不习惯，慢慢的你会喜欢的。 4．复习完那两本书之后就可以看真题了，不可否认无论是什么正规考试，历年真题都绝对是最好的复习资料。苏大试题是会有原题的，也就是考过的很可能一点不变的再考，名词解释最明显，所以真题一定要好好把握。 北京师范大学2011～2012学年第 1 学期期末考试试卷（A 卷） 课程名称： 数据结构 任课教师姓名： 刘玉铭 卷面总分： 100 分 考试时长： 100 分钟 考试类别：闭卷 院（系）： 数学科学学院 专 业： 年级： 2010 姓 名： 学 号： 阅卷教师（签字）： 一、 单项选择题（每题2分，共10题20分） 1．以下那一个术语与数据的存储结构无关？ 。 A ．栈 B ．哈希表 C ．线索树 D ．双向链表 2．链表不具有的特点是 。 A ．插入、删除不需要移动元素 B ．可随机访问任一元素 C ．不必事先估计存储空间 D ．所需空间与线性表长度成正比 3．算术表达式a+b*（c+d/e ）转为后缀表达式后为 。 A ．ab+cde/* B ．abcde/+*+ C ．abcde/*++ D ．abcde*/++ 4．二维数组A[10][20]采用列优先的存储方法,若每个元素占2个存储单元，设A[0][0]的地址为100，则元素A[7][6]的存储地址为 。 A ．232 B ．234 C ．390 D ．392 装 订 线 5．若一棵二叉树具有10 个度为2 的结点，5 个度为1 的结点，则度为0 的结点个数是。 A．9 B．11 C．15 D．不确定 6．一棵二叉树中序序列为FEABDC，后序序列为FBADCE，则层序序列为。 A. ABCDEF B. EFCDBA C. FECDAB D. EFCDAB 7．在有向图G 的拓扑序列中，若顶点Vi 在顶点Vj 之前，则下列情形不可能出现的是。 A．G 中有弧 数据结构期末考试试题及答案 、选择题 评价一个算法时间性能的主要标准是()。1. A、算法易于调试 B、算法易于理解 C、算法的稳定性和正确性 D、算法的时间复杂度 )等五个特性。计算机算法具备有输入、输出、 2. A、可行性、可移植性和可扩充性 B、可行性、确定性和有穷性 C、确定性、有穷性和稳定性 D、XX、稳定性和XX 。带头结点的单链表head为空的判定条件是()3. A、h ead==NULL B、h ead->next==NULL C、head->next==head D、head！=NULL 以下关于线性表的说法不正确的是()。4. A、线性表中的数据元素可以是数字、字符、记录等不同类型。 B、线性表中包含的数据元素个数不是任意的。 C、线性表中的每个结点都有且只有一个直接前趋和直接后继。 D、存在这 样的线性表：表中各结点都没有直接前趋和直接后继。 在顺序表中，只要知道()，就可在相同时间内求出任一结点的存储地址。 5.A、基地址 B、结点大小 C、向量大小 D、基地址和结点大小 ()运算中，使用顺序表比链表好。6. A、插入 B、删除 C、根据序号查找 D、根据元素值查找一个长度为n的顺序表中，向第i个元素之前插入一个新元素时，需要向后移动()个元素7.A、n-i B、n-i+1 C、n-i-1 D、i ()适合作为经常在首尾两端操作线性表的存储结构。8. A、顺序表 B、单链表 C、循环链表 D、双向链表 栈和队列的共同点是() 9. A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点 一个队列的入列序列是1234，则队列的输出序列是()。10. A 、4321 B 、12 3 4 C 、1432 D 、 3241队列与一般的线性表的区别在于()。11. A、数据元素的类型不同 B、运算是否受限制 C、数据元素的个数不同 D、逻辑结构不同 假上溢”现象会出现在()中。12. A、循环队列 B、队列 C、链队列 、顺序队列D.二、填空 一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分） 1、串的长度是（）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数，且大于0 D、串中所含字符的个数 2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2 3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5 5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。 A、n-1 B、2n-1 C、n+1 D、2n+1 6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2) 8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆 最新苏州大学考研笔记汇总 ——苏大本科笔记与考研真题哪里下载？ 纵观整个考研过程，考研笔记的重要程度不言而喻，从考研初期的知识理解到中期的要点记忆，再到后期的提纲要领，可以说，考研笔记在整个备考过程中起到中流砥柱的重要作用。若是在备考期间，能拥有一份往届苏州大学考研高分学长学姐的笔记也是极好的！他们的笔记往往内容详细、条理清晰，是对考点的把握和理解的体现。不过由于笔记数量过于稀缺，有需求的考生又很多，总有许多考生抱怨根本买不到。针对考研笔记的稀缺性，东吴苏大考研网官方教学研发团队联合苏州大学各专业排名前三的学长学姐们针对苏州大学各专业考点，共同编写了一系列《考研复习全析》，自发售以来好评率超过98%！欲知更多苏州大学考研详情，请点击进入【苏大考研真题答案】，也可报名（苏大考研辅导班），考研成功，快人一步！ [东吴苏大考研网] 2019苏州大学871传热学考研复习全析 [东吴苏大考研网] 2019苏州大学考研889英语教学论复习全析（含真题，共三册）[东吴苏大考研网] 2019苏大665中外音乐史考研复习全析（含历年真题） [东吴苏大考研网] 2019苏州大学666生物化学（农）考研复习全析（含历年真题，共两册） [东吴苏大考研网] 2019苏大842自动控制原理考研复习全析（含历年真题） [东吴苏大考研网] 2019苏大841电子技术基础（机电）考研复习全析（含历年真题）【共两册】 [东吴苏大考研网] 2019苏大839管理信息系统与数据结构考研复习全析（含历年真题，共两册） [东吴苏大考研网] 2019苏大850高等数学基础考研复习全析（含历年真题，共两册）[东吴苏大考研网] 2019苏大627生物化学考研复习全析（含历年真题，共两册）[东吴苏大考研网] 2019苏大862材料科学基础考研复习全析（含历年真题） [东吴苏大考研网] 2019苏大858材料学（F）考研复习全析（共两册，含历年真题） 读书破万卷下笔如有神 《数据结构》试卷（A卷） 一、选择题 1. 数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 D.顺序存储结构 C. 链式存储结构 3. 树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 D. 一对多关系 C.多对一关系 4. 设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; 23nn) D.O(C.O(n) B.O( ) A.O(1) 5. 算法分析的目的是（1），算法分析的两个主要方面是（2）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6. 计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7. 数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。 不好说D. 相同C. 高B. 低A. 读书破万卷下笔如有神 8. 数据结构作为一门独立的课程出现是在（）年。 A.1946 B.1953 C.1964 D.1968 9. 数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对 10. 计算机内部数据处理的基本单位是（）。 A.数据 B.数据元素 C.数据项 D.数据库 11.若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为( )。 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.以顺序方式存储，且数据元素有序 数据结构模拟卷(含答案)经典习题 练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位10. 下列图示的顺序存储结构表示的二叉树是( ) 苏州大学数据结构课程试卷2卷（共 5页） 考试形式：闭卷年月院系 ______________ 年级 ______________ 专业 ______________ 学号 ______________ 姓名 ______________ 成绩 ______________ 一、填空（2分×16） 1、下面程序段的时间复杂度为____mn_______。 f or (i=0; i 韩山师范学院2013年专升本插班生考试试卷 计算机科学与技术 专业 数据结构 试卷 （A 卷） 一、 单项选择题（每题2分，共40分） 1、从逻辑上可以把数据结构分为（ A ）两大类。 A ．动态结构、静态结构 B ．顺序结构、链式结构 C ．线性结构、非线性结构 D ．初等结构、构造型结构 2、下面关于算法说法错误的是（ D ） A ．算法最终必须由计算机程序实现 B ．为解决某问题的算法同为该问题编写的程序含义是相同的 C ． 算法的可行性是指指令不能有二义性 D ．以上几个都是错误的 3、栈和队列的共同特点是( A )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 4、以下数据结构中，哪一个是线性结构（ D ）？ A ．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 5、下面关于线性表的叙述中，错误的是哪一个？（B） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 6、静态链表中指针表示的是（B）。 A．内存地址B．数组下标 C．表头地址 D．下一元素地址//所谓静态链表就是没有指针的，用下标模仿这个指针的功能的 7、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。 A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 8、下列各种排序算法中平均时间复杂度为O(n2)是（D）。 A．快速排序 B. 堆排序 C. 归并排序 D. 冒泡排序 9、设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择 （B）。 A. 小于等于m的最大奇数 B. 小于等于m的最大素数 C. 小于等于m的最大偶数 D. 小于等于m的最大合数 10、字符串的长度是指（C）。 A. 串中不同字符的个数 B. 串中不同字母的个数 C. 串中所含字符的个数 D. 串中不同数字的个数 11、设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为 （ D ）。 A. top=top+1; B. top=top-1; C. top->next=top; D. top=top->next; 12、二叉排序树可以得到一个从小到大的有序序列。( B ) A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历苏州大学数据库期末练习(附答案)
数据结构II试卷B及答案(孟凡荣)
2017年数据结构期末考试题及答案A
数据结构模拟试题及答案
苏州大学研究生试卷2012年数据结构本科A
大工数据结构课程考试模拟试卷a
数据结构考试题库
苏州大学计算机学院数据结构及操作系统考研复试真题答案指南
数据结构试卷-A+答案
数据结构期末考试试题及答案
数据结构模拟试题1
最新苏州大学考研初试复试笔记汇总大全
数据结构试卷A卷
《数据结构》期末考试题及答案
数据结构模拟卷(含答案)经典习题培训讲学
数据结构课程试卷2卷 苏州大学
【良心出品】2013韩山师范学院专升本插班生考试《数据结构》课程试卷
相关主题
文本预览