《数据结构-C语言版》 第一章绪论 单项选择题 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．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是____ __。 A. n2 B. nlogn C. n D. logn 7．设使用某算法对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为____ ___。 A. O(1) B. O(n) C. O(200n) D. O(nlog2n)
CDCBBDD 第二章线性表 单项选择题 1．链表不具有的特点是____ ____。 A. 可随机访问任一元素 B. 插入和删除时不需要移动元素 C. 不必事先估计存储空间 D. 所需空间与线性表的长度正比 2．设顺序表的每个元素占8个存储单元。第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为。 A. 139 B. 140 C. 147 D. 148 3．在线性链表存储结构下，插入操作算法。 A. 需要判断是否表满 B. 需要判断是否表空 C. 不需要判断表满 D. 需要判断是否表空和表满 4．在一个单链表中，若删除p所指结点的后继结点，则执行。 A. p->next = p->next->next; B. p->next = p->next; C. p = p->next->next; D. p = p->next; p->next = p->next->next; 5．将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为。A. O(n) B. O(1) C. O(m) D. O(m+n) 6．需要预分较大空间，插入和删除不需要移动元素的线性表，其存储结构是。 A. 单链表 B. 静态链表 C. 线性链表 D. 顺序存储方式ACCABB 填空题 1．在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的_____结点。2．在单链表中，指针p所指结点为最后一个结点的条件是。 3．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。4．在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动元素的个数是。 5．在长度为n的顺序表中插入一个元素的时间复杂度为。 1前驱 2 p->next==NULL
知识点： 01．绪论 02．顺序表 03．链表 04．栈 05．链队列 06．循环队列 07．串 08．数组的顺序表示 09．稀疏矩阵 10．广义表 11．二叉树的基本概念 12．二叉树遍历、二叉树性质 13．树、树与二叉树的转换 14．赫夫曼树 15．图的定义、图的存储 16．图的遍历 17．图的生成树 18．静态查找（顺序表的查找、有序表的查找） 19．动态查找（二叉排序树、平衡树、B树） 20．哈希查找 21．插入排序（直接插入、折半插入、2路插入、希尔排序）22．选择排序（简单选择、树形选择、堆排序） 23．快速排序、归并排序
101A1（1）．数据的逻辑结构是（A）。 A．数据的组织形式B．数据的存储形式C．数据的表示形式D．数据的实现形式 101A1（2）．组成数据的基本单位是（C）。 A．数据项B．数据类型C．数据元素D．数据变量 101B1（3）．与顺序存储结构相比，链式存储结构的存储密度（B）。 A．大B．小C．相同D．以上都不对 101B2（4）．对于存储同样一组数据元素而言，（D）。 A．顺序存储结构比链接结构多占空间B．在顺序结构中查找元素的速度比在链接结构中查找要快C．与链接结构相比，顺序结构便于安排数据元素D．顺序结构占用整块空间而链接结构不要求整块空间101B2（5）．下面程序的时间复杂度为（B）。 x=0； for（i=1；i 第三章习题 1. 按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答： ⑴如进站的车厢序列为123，则可能得到的出站车厢序列是什么？ ⑵如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。（即 写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。 2. 设队列中有A、B、C、D、E这5个元素，其中队首元素为A。如果对这个 队列重复执行下列4步操作： （1）输出队首元素； （2）把队首元素值插入到队尾； （3）删除队首元素； （4）再次删除队首元素。 直到队列成为空队列为止，得到输出序列： （1） A、C、E、C、C （2） A、C、E （3） A、C、E、C、C、C （4） A、C、E、C 3. 给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈 空与栈满？ 4. 按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，画出对 下列算术表达式求值时操作数栈和运算符栈的变化过程： A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ 5. 试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形 如‘序列1& 序列2’模式的字符序列。其中序列1和序列2中都不含字符’&’，且序列2是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。 6. 假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将 一个通常书写形式且书写正确的表达式转换为逆波兰式。 7. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素 结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。 8. 要求循环队列不损失一个空间全部都能得到利用, 设置一个标志域tag , 以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。 9. 简述以下算法的功能（其中栈和队列的元素类型均为int）： （1）void proc_1(Stack S) { int i, n, A[255]; n=0; while(!EmptyStack(S)) 1、计算机构成原理（冯·诺依曼结构）：1945年，冯·诺依曼首先提出了“存储程序”的概念和二进制原理，后来，人们把利用这种概念和原理设计的电子计算机系统统称为“冯.诺曼型结构”计算机。冯.诺曼结构的处理器使用同一个存储器，经由同一个总线传输。 2、三总线：地址总线AB（用来传递存储单元或输入\输出接口的地址信息，信息传送是单向的），数据总线DB（用于CPU与内存、CPU与输入\输出接口之间传输数据），控制总线CB（用来传递各种控制和应答信号） 3、字长的参数意义：CPU内部各寄存器之间一次能够传递的数据位，即在单位时间能够一次处理的二进制位数。该指标反映CPU内部预算处理的速度和效率。 4、主频的参数意义：CPU的时钟频率，也是CPU的工作频率，用来表示CPU的运算速度。主频越高，CPU的速度也就越快。CPU的主频＝外频×倍频系数。 5、计算机的基本工作原理：计算机的基本工作原理是存储程序和程序控制原理，又称冯诺依曼原理。简要概括为三点：①计算机应包括运算器、存储器、控制器、输入设备、输出设备五大基本部件。②计算机应采用二进制来表示指令和数据。③指令和数据都放在存储器中，然后启动计算机工作，计算机无需操作人员干预，能够自动高速地从存储器中逐条取出指令和执行命令。 6、计算机的系统组成（硬件系统和软件系统）：见P12图1.3。 ①计算机硬件系统由运算器（完成算术运算和逻辑运算）、控制器（协调指挥计算机各部件工作）、存储器（存储程序和数据，实现记忆功能）、输入设备（输入信息并转化为机内信息存储）、输出设备（将机内信息转化为便于识别、处理和使用的字符、图形输出显示）。 ②计算机的软件系统由系统软件（用于控制、管理和维护计算机）和应用软件（为解决某一专门问题而开发的软件程序）组成。 7、计算机的层次结构：P13图1.4。 8、计算机的硬件组成：P12图1.3。主要包括主板、CPU、存储器、总线、I/0接口、I/0设备等。 9、ROM与RAM的区别：ROM为只读存储器，CPU对它只取不存。ROM中的信息一般由制造商写入并做固化处理，即使断电ROM中的信息也不会丢失。RAM为随机存储器，是一种读写存储器，随时可写入或读取信息 10、计算机指令：指示计算机执行某种操作的命令，能够被计算机识别并执行的二进制代码。由操作码（指明指令要进行什么操作）和地址码（指出参与操作的数据在存储器中的位置）组成【【。 11、计算机指令系统：计算机所有指令的集合。指令系统描述了CPU的基本功能，一台计算机的指令越多、越丰富，则该计算机的功能就越强。不同的计算机的指令系统拥有的指令种类和数目是不同的。 12、计算机逻辑运算：以二进制数为基础。基本的逻辑运算有“与（AND）”、“或（OR）”、“非（NOT）”运算三种，其他的逻辑运算都可由这三种推出。 排序算法（19） 1.以单链表为存储结构，写一个直接选择排序算法。 2.设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关 键字之前。请分析算法的时间复杂度。 3.写一个双向冒泡排序的算法，即在排序过程中交替改变扫描方向。 4. 4.下面是一个自上往下扫描的冒泡排序的伪代码算法，它采用lastExchange 来记录每趟扫描中进 行交换的最后一个元素的位置，并以它作为下一趟排序循环终止的控制值。请仿照它写一个自下往上扫描的冒泡排序算法。 void BubbleSort(int A[],int n) //不妨设A[0..n-1]是整型向量 int lastExchange,j,i=n-1; while (i>0) lastExchange=0; for(j=0;j if([j+1] 交换A[j]和A[j+1]; lastExchange=j; } i=lastExchange;//将i置为最后交换的位置 }//endwhile }//BubbleSort 5.改写快速排序算法，要求采用三者取中的方式选择划分的基准记录；若当前被排序的区间长度小于等于3时，无须划分而是直接采用直接插入方式对其排序。 6.对给定的j(1 ≤ j ≤ n ),要求在无序的记录区R[1..n]中找到按关键字自小到大排在第j个位置上的记录(即在无序集合中找到第j个最小元)，试利用快速排序的划分思想编写算法实现上述的查找操作。 7.以单链表为存储结构，写一个直接选择排序算法。 8.写一个heapInsert(R,key)算法，将关键字插入到堆R中去，并保证插入R后仍是堆。提示：应为堆R增加一个长度属性描述(即改写本章定义的SeqList类型描述，使其含有长度域)；将key先插入R 中已有元素的尾部(即原堆的长度加1的位置，插入后堆的长度加1)，然后从下往上调整，使插入的关键字满足性质。请分析算法的时间。 9.写一个建堆算法：从空堆开始，依次读入元素调用上题中堆其中。 10.写一个堆删除算法：HeapDelete(R,i),将R[i]从堆中删去，并分析算法时间，提示：先将R[i]和堆中最后一个元素交换，并将堆长度减1，然后从位置i开始向下调整，使其满足堆性质。 第一章绪论 一、选择题 1.D 2.C 3.C 4.B 5.D 6.C 7.D 8.C 9.A 10.D 11.D 12.B 二、填空题 1. 逻辑结构存储结构运算 2. 集合结构线性结构树形结构图状结构 3. 有穷性. 确定性. 可行性. 输入. 输出 4. 顺序存储. 链式存储 5. 数据元素 6. 线性结构非线性结构 三、简答题 1. 尽管算法的含义与程序非常相似，但两者还是有区别的。首先，一个程序不一定满 有穷性，因为它不是一个算法。其次，程序中的指令必须是计算机可以执行的，而 算法中的指令却无此限制。如果一个算法采用机器可执行的语言来书写，那么它就 是一个程序。 2. 数据结构是指数据对象以及该数据对象集合中的数据元素之间的相互关系（数据元 素的组织形式）。例如：队列的逻辑结构是线性表（先进后出）；队列在计算机中 既可以采用顺序存储也可以采用链式存储；队列可进行删除数据元素. 插入数据元 素. 判断是否为空队列，以及队列置空等操作。 3. 数据元素之间的逻辑关系，也称为数据的逻辑结构。数据元素以及它们之间的相互 关系在计算机存储器内的表示（又称映像）称为数据的存储结构，也称数据的物理 结构。 4. 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表 示一个或者多个操作。此外，一个算法还具有下列5个特性： （1）有穷性：一个算法必须在执行有穷步之后结束，即算法必须在有限时间内完 成。 （2）确定性：算法中每一步必须有明确的含义，不会产生二义性。并且，在任何 条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。 （3）可行性：一个算法是能执行的，即算法中的每一步都可以通过已经实现的基 本运算执行有限次得以实现。 （4）输入：一个算法有零个或者多个输入，它们是算法开始时对算法给出的初始 量。 （5）输出：一个算法有一个或者多个输出，它们是与输入有特定关系的量 5. 举例说明四种基本结构的区别: 集合: 数据元素之间无任何关系,如集合A={x,5,t,&}; 线性结构: 数据元素之间存在一个对一个的关系,如线性表L=（2,3，4,5,7,10）； 树形结构: 数据元素之间存在一个对多个的关系,如文件系统目录管理； 图状结构: 数据元素之间存在多个对多个的关系,如教学计划课程安排顺序图。 四. 算法设计题 1.数据的四种存储结构是( ) A.顺序存储结构、链接存储结构、索引存储结构和散列存储结构 B.线性存储结构、非线性存储结构、树型存储结构和图型存储结构 C.集合存储结构、一对一存储结构、一对多存储结构和多对多存储结构 D.顺序存储结构、树型存储结构、图型存储结构和散列存储结构 2.若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点，要使操作时间最少， 下列选项中，应选择的存储结构是( ) A.无头结点的单向链表 B.带头结点的单向链表 C.带头结点的双循环链表 D.带头结点的单循环链表 3.若带头结点的单链表的头指针为head，则判断链表是否为空的条件是( ) A.head=NULL B.head->next=NULL C.head!=NULL D.head->next!=head 7.若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是( ) A.树中没有度为2的结点 B.树中只有一个根结点 C.树中非叶结点均只有左子树 D.树中非叶结点均只有右子树 8.若根结点的层数为1，则具有n个结点的二叉树的最大高度是( ) A.n B. C. +1 D.n/2 9.在图G中求最小生成树可以采用的算法是( ) A.迪杰斯特拉（Dijkstra）算法 B.克鲁斯卡尔（Kruskal）算法 C.深度优先遍历(DFS)算法 D.广度优先遍历(BFS)算法 10.下图G=(V,E)是一个带权连通图，G的最小生成树的权为( ) A.15 B.16 C.17 D.18 11.在下图中，从顶点1出发进行深度优先遍历可得到的序列是( ) A.1 2 3 4 5 6 7 B.1 4 2 6 3 7 5 C.1 4 2 5 3 6 7 D.1 2 4 6 5 3 7 12.如果在排序过程中不改变关键字相同元素的相对位置，则认为该排序方法是( ) A.不稳定的 B.稳定的 C.基于交换的 D.基于选择的 13.设有一组关键字(19, 14, 23, 1，6，20, 4，27, 5，11, 10, 9)，用散列函数H(key)=key%13构造散列表，用拉链法解 决冲突，散列地址为1的链中记录个数为( ) A.1 B.2 C.3 D.4 14.已知二叉树结点关键字类型为字符，下列二叉树中符合二叉排序树性质的是( ) 1.多媒体和对媒体技术的定义、分类 答：多媒体是融合两种或者两种以上媒体的人——机互动的信息交流和传播媒体；多媒体的主要特点是多样性，集成性，交互性，实时性。 2.标准通用标记语言（SGML）可以用来定义文档结构和文档内容的标签。 超文本标记语言（HTML）是面向显示的标记语言。 虚拟现实造型语言（VRML）是创建含有三维交互对象的Web网页程序设计语言。 3.超文本:是包含指向其它文档或者文档元素的指针的电子文档。 超文本系统：是一种提供了复杂格式超文本的解释的软件系统，包括文本格式，图像，超级链接——一种文字间的跳转以提供某一个主题（关键词）的相关内容。 超媒体：超文本＋多媒体。 4.多媒体系统可分为四个层次：基础、系统、服务和使用。 5.多媒体技术是利用计算机对文本、图形、图像、声音、动画、视频等多种信息综 合处理、建立逻辑关系和人机交互作用的技术。 6.声音信号数字化的定义和步骤，在数字话过程中对声音质量的影响。 答:定义——将具有一定幅度和频率的连续变化的模拟声音信号，通过A/D转换器以一定的频率对模拟信号街区一个振幅值，并用指定字长的二进制未来表示，从而将连续的模拟音频信号转变成能被计算机处理的离散的数字音频信号。 步骤：采样（采样频率不应该低于声音信号最高频率的两倍，这样就能做到无损数字化）（采样精度：a.量化位数，b.信噪比） 量化（把采样得到的声音信号幅度转换成数字值） 对声音质量有关的重要因素是：采样频率量化位数声道数 对声音质量的度量有两种基本的方法;一种是客观质量度量，另一种是主观质量度量。 7.人的听力范围：20——20k HZ 话音信号：300——3k HZ 8.声音文件的数据量：（采样频率×量化精度×声道数×时间）/ 8（采样频率– Hz ，时间–秒，数据 量–字节） 9.MIDI音频和波形音频的区别。 MIDI是指电子乐器数字接口 MIDI 传输的不是声音信号, 而是音符、控制参数等指令, 它指示MIDI 设备要做什么,怎么做, 如演奏哪个音符、多大音量等。它们被统一表示成MIDI 消息，波形音频传输的是模拟信号,也就是电信号 10.产生MIDI乐音的主要的两种方法。 一种是频率调制合成法，另一种是乐音样本合成法也称为波形表合成法。 11.声音音频编码的类别及其优缺点。 波形编译码器：话音质量高，但是数据率也高； 音源编译码器：数据率低，但是合成话音的质音有待提高； 混合编译码器：数据率和音质介于以上二者之间。 12.脉冲编码调制技术（区分均匀量化，非均匀 如果采样相等的量化间隔对采样得到的信号做量化，那么这种量化称为均匀量化。 对输入信号进行量化时，大的输入信号采用大的量化间隔，小的输入信号采用小的量化间隔，这就是非均匀量化。 13.增量调制是一种预测编码技术，是PCM编码的一种变形（他是对实际的采样信号与预测的采 样信号之差的极性进行编码） 当输入信号的变化速度超过反馈回路输出信号的最大变化速度时，就会出现斜率过载。 当输入信号与预测信号的差值接近零的区域，增量调制的输出出现随机交变的0和1，这种现 重庆大学 （重庆大学的在不断更新，目前更新这些2010原版试卷，代理价格5元一份，还价勿扰） 经济学原理（含政治经济学和西方经济学）2010 微观经济学（含宏观经济学）2010 行政管理学2010 综合考试（1）（含管理学原理、政治学原理、社会学）2010 微观经济学（含宏观经济学）2010 工程项目管理2010 建筑技术经济学2010 二外法语2010 < 二外日语2010 基础英语2010 英语翻译与写作2010 高等代数2010 数学分析2010 机械原理2010 系统工程导论（含运筹学及系统工程导论）2010 金属学及热处理（含金属材料）2010 电子技术（1）（含模拟电子技术和数字电子技术）2010 微机原理及应用2010 … 自动控制原理2010 电路原理（上册）2010 材料力学2010 结构力学2010 岩土力学2010 流体力学2010 水分析化学2010 物理化学（含物理化学实验）2010 化学综合2010 化工原理（含化工原理实验）2010 ] 药学专业基础综合（含药物化学、药物分析）2010 安全系统工程2010 新闻传播理论2010 新闻传播学2010 贸易及行政学院 马克思主义哲学原理2008——2009 科学技术哲学概论2002——2007 科学技术史2002，2004——2009 辩证唯物主义与历史唯物主义2000 : 经济学原理（含政治经济学和西方经济学）2003——2009（2003有答案）微观经济学（含宏观经济学）1998——2003，2005——2009 西方经济学（微观经济学、宏观经济学）1999——2002 政治经济学1999——2002 教育心理学2002 教育心理学（含教育学）2003 教育学基础（含教育心理学）2004 行政管理学2002——2006 行政管理学专业综合考试2002 综合考试（1）（含管理学原理、政治学原理、社会学）2004——2006 ! 经济与工商管理学院 微观经济学（含宏观经济学）1998——2003，2005——2009 西方经济学（微观经济学、宏观经济学）1999——2002 政治经济学1999——2002 会计学原理（含财务管理）1999——2000 运筹学1998，2000 管理学（含会计学原理）1999——2000 技术经济学（含会计学原理）1998——2000（注：1998年有两种） 信息管理与信息技术2006 @ 信息管理2007——2009 情报检索与情报研究2006——2009 教育心理学2002 教育心理学（含教育学）2003 教育学基础（含教育心理学）2004 建设管理与房地产学院 工程项目管理2001——2002，2006——2009 经济与管理基础知识2001——2002 区域经济学2004——2005 < 区域经济学（1）2002 区域经济学专业综合考试（1）2003 建筑施工2001——2002，2004——2009 建筑技术经济学2006——2009 专业综合考试（3）[含工程项目管理、经济与管理基础知识] 2003 土地管理学2004，2006——2009（2005的不清晰） 1、在数据结构中，数据的逻辑结构可以分成 A．内部结构和外部结构 B．线性结构和非线性结构 C．紧凑结构和非紧揍结构 D．动态结构和静态结构 2、带头结点的链表L为空的条件。 A.L->next=NULL B.L=NULL C.L->data=NULL D.L->next->data=NULL 3、在下面的程序段中，对x的赋值语句的频度为 x=1; while （x<=n） x=x+2 n) A．O(2n) B．O(n) C．O(n2) D．O(log 2 4、一个顺序表第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 A、110 B、108 C、100 D、120 5、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=3，则pi为 A．i B．n-i C．n-i+1 D．不确定 6、有8个结点的无向连通图最少有条边。 A．5 B. 6 C. 7 D. 8 7、在一个单链表L中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行。 A.q->next=p;p->next=q; B.p->next=q->next;q=p; C.q->next=p->next;p->next=q; D.p->next=q->next;q->next=p; 8、设输入队列序列是1，2，3，4,则是其出队列序列。 A. 1，2，3，4， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， 9、若数据元素之间存在多对多的关系，则该结构称结构 A.集合 B.线性 C.树形 D.图形 10、数组A[1..4，1...5]中含有元素的个数 A. 55 B. 45 C. 20 D. 16 11、以下特征中，不是算法的特性 A.有穷性 B.确定性 C.有0个或多个输出 D.可行性 12、折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中比较大小，查找结果是失败。 A．20，70，30，50 B．30，88，70，50 C．20，50 D．30，88，50 13、采用穷举法进行串的模式匹配，主串长度为n，子串长度为m;若匹配成功时，最多比较元素个数 A.n B.m C.(n-m+1)*m D.n-m+1 14、下面关于串的定义正确的是 A．有零个或多个字符组成的有限序列 Examination Paper on Data Structure Ⅰ Fill Vacant Position () 1.In a ________ data structure, all insertions and deletions of entries are made at one end. It is particularly useful in application involving________. 2.In processing a sequential list with n entries: insert and remove require time approximately to ________. 3.One of method of searching is ________ that requires ordered list. 4.The time complexity of the quicksort is ________. 5.Only ________ ________ graph has topological order. 6.According the definition of Binary Tree, there will be ________ different Binary Trees with 5 nodes. ⅡSingle choice () 1.The Linked List is designed for conveniently ________data item. a. getting b. inserting c. finding d. locating 2.Assume a sequence list as 1,2,3,4,5,6 passes a stack, an impossible output sequence list Is ________ . a. 2,4,3,5,1,6 b.3,2,5,6,4,1 c.1,5,4,6,2,3 d.4,5,3,6,2,1 3. A queue is a structure not implementing ________. a. first-in/first-out b. first-in/last-out c. last-in/last-out d. first-come/first-serve 4.Removing the data item at index i from a sequential list with n items, ________ items need to be shifted left one position. a. n-i b. n-i+1 c. i d. n-i-1 5.The addresses which store Linked List ________ . a. must be sequential b. must be partly sequential c. must be no sequential d. can be sequential or discontiguous 6.The time requirement of retrieving a given target in hash table with n entries is _______ a. O(n) b. O(log2n) c. O(1) d. O(nlog2n) 7.If the Binary Tree T2 is transformed from the Tree T1, then the postorder of T1 is the ________ of T2. a. preorder b. inorder c. postorder d. level order 8.In the following sorting algorithm, ________ is an unstable algorithm. a. the insertion sort b. the bubble sort c. quicksort d. mergesort 9.Assume there is a ordered list consisting of 100 data items, using binary search to find a special item, the maximum comparisons is ________ . a. 25 b.1 c. 10 d.7 10.The result from scanning a Binary Search Tree in inorder traversal is in ________ order. a. descending or ascending b. descending c. ascending d. out of order 11.The ________ case is worst for quicksort. a. the data which will be sorted is too larger. 一、绪论 1.基本概念 数据元素（基本单位）、数据项（最小单位）、数据结构（逻辑结构、存储结构、操作或运算）、逻辑结构（集合、线性、树、图或网）、存储结构（顺序存储、链式存储、索引、散列）、数据类型、抽象数据类型、算法的5个重要特性、算法设计的4个要求 2.时间复杂度 例6 i=0;k=0; do 【k=k+10;i++;i++;】 while(i 例14 fact(int n) 【if(n<=1) return 1; else return (n*fact(n-1)); 】 二、线性表 1.等概率下顺序表插入与删除的平均移动次数 2.单链表、双向链表的插入与删除 3.静态链表 4.单链表、循环链表遍历一次的循环条件。 三、栈 1.基本概念 2.假定有三个元素A，B，C依次进栈，试写出所有可能的出栈序列 3.给入栈顺序，不可能的出栈顺序 4.顺序栈空、滿的条件、入栈、出栈操作 5.应用、中缀转后缀 6.循环队列空、滿的条件、入队列、出队列操作、队列元素个数的 求法 7.链队列的入、出 五、数组 一维二维地址 1.设有一个二维数组A[M][N]，采用以行序为主序的存储方式，假设A[0][0]存放位置在5000，A[2][4]存放位置在5160，每个元素占2个单元，问数组A的每行占多少单元？A[4][5]存放在什么位置？ 2.设二维数组A[7][7]，按行优先顺序存储，每个元素占1个字节，设A[0][0]的存储地址为3020，则A[1][3]的存储地址为多少？如果该二维数组为对称矩阵， Final Examination Paper on Data Structures(A) I、Fill Vacant Position (1′×10=10′) 1、____________is the name for the case when a function invokes itself or invokes a sequence of other functions,one of which eventually invokes the __________again. 2、In a __________ data structure, all insertions and deletions of entries are made at one end. It is particularly useful in applications involving __________. 3、In c++ , we use ____________operator to implement the circular queues. 4、In processing a contiguous list with n entries: insert and remove require time approximately to _________. And clear, empty, full, size operate in ________ time. 5、One of method of searching is ____________________that requires ordered list. 6、The time complexity of the quicksort is______________. 7、Only __________ ____________graph has topological order. II、Multiple choice (2′×10=20′) 1、In a tree, ______are vertices with the same parent. ( ) A. children B. sibling C. adjacent D. leaf 2、A queue is a version of ( ) A. linked list B. LIFO list C. sequential list D. FIFO list 3、How many shapes of binary trees with four nodes are there ( ) A. 12 B.15 C. 14 D. 13 4、Among sorting algorithms, which kind of algorithm is divide-and-conquer sorting ( ) A. shell sort B. heap sort C. merge sort D. inserting sort 5、For the following graph, one of results of depth_first traversal is ( ) A. abcdefghi B. abcdeighf C. acbdieghf D.abdeighfc 6、In a binary tree, if the result of traversing under preorder is the same as that under inorder, then ( ) A. It is only a binary tree with one node B. It is either empty, or the left subtree of any node of the tree is empty C. It is only an empty binary tree D. It is either empty, or the right subtree of an node of the tree is empty 7、There are _______solutions to the problem of placing four queens on a 4×4 board. ( ) A. 2 B. 3 C. 6 D. 4 8、Which function is smallest order of magnitude? ( ) A. 2 n B. n + lgn C.n 0.1 D.10000 黄老师： 题型结构如下： 单项选择题，15小题，30分； 填空题，5小题，10分； 综合应用题，50分（树、图、查找） 算法设计与分析，2选1,10分（线性结构） 试卷中一些算法只给英文名称； 考查范围(黑体字为建议的重点考查内容；红字为备注；蓝字为拟纳入的考研大纲内容) 一、绪论 （一）算法、数据结构基本概念 （二）算法分析中O（f（n））符号的含义 （三）时间复杂度简单分析表示 二、线性表 （一）线性表的定义和基本操作 （二）线性表的实现 1.顺序存储 2.链式存储 3.线性表的应用 三、栈、队列 （一）栈和队列的基本概念 （二）栈和队列的顺序存储结构 （三）栈和队列的链式存储结构 （四）栈和队列的应用 四、树与二叉树 （一）树的概念 （二）二叉树 1.二叉树的定义及其主要特征 2.二叉树的顺序存储结构和链式存储结构 3.二叉树的遍历及应用 （三）树、森林 1. 森林与二叉树的转换 2. 树的存储结构； 3.树和森林的遍历 4.线索二叉树的基本概念和构造 （四）二叉树的应用 1.哈夫曼（Huffman）树和哈夫曼编码 2.二叉排序树 五、图 （一）图的基本概念 （二）图的存储及基本操作 1.邻接矩阵法 2.邻接表法 （三）图的遍历 1.深度优先搜索 2.广度优先搜索 （四）图的基本应用 1.最小（代价）生成树 2.最短路径 3.拓扑排序 4.关键路径 六、查找 （一）查找的基本概念 （二）顺序查找法 （三）折半查找法 （四）二叉查找树及其基本操作（只考察基本概念）（五）平衡二叉树（只考察基本概念） （六）散列（Hash）表 （七）查找算法的分析及应用 七、排序 （一）排序的基本概念 （二）直接插入排序 （三）气泡排序（bubble sort） （四）简单选择排序 （五）希尔排序（shell sort） （六）快速排序 （七）堆排序 （八）二路归并排序（merge sort） （九）各种排序算法的比较 （十）排序算法的应用 计算机网络课程设计 小组成员： 课程设计指导教师评定成绩表（学生姓名: 学号: ） 项目分 值 优秀 (100>x≥90) 良好 (90>x≥80) 中等 (80>x70) 及格 (70>x≥60) 不及格 (x<60) 评 分参考标准参考标准参考标准参考标准参考标准 学习态度15 学习态度认 真，科学作风 严谨，严格保 证设计时间并 按任务书中规 定的进度开展 各项工作 学习态度比较 认真，科学作 风良好，能按 期圆满完成任 务书规定的任 务 学习态度 尚好，遵守 组织纪律， 基本保证 设计时间， 按期完成 各项工作 学习态度尚 可，能遵守组 织纪律，能按 期完成任务 学习马虎， 纪律涣散， 工作作风 不严谨,不 能保证设 计时间和 进度 技术水平 与实际能力25 设计合理、理 论分析与计算 正确，实验数 据准确，有很 强的实际动手 能力、经济分 析能力和计算 机应用能力， 文献查阅能力 强、引用合理、 调查调研非常 合理、可信 设计合理、理 论分析与计算 正确，实验数 据比较准确， 有较强的实际 动手能力、经 济分析能力和 计算机应用能 力，文献引用、 调查调研比较 合理、可信 设计合理， 理论分析 与计算基 本正确，实 验数据比 较准确，有 一定的实 际动手能 力，主要文 献引用、调 查调研比 较可信 设计基本合 理，理论分析 与计算无大 错，实验数据 无大错 设计不合 理，理论分 析与计算 有原则错 误，实验数 据不可靠， 实际动手 能力差，文 献引用、调 查调研有 较大的问 题 创新10 有重大改进或 独特解，有一 定实用值 有较大改进或 新颖解，实用 性尚可 有一定改 进或新的 见解 有一定见解观念陈旧 论文(计算 书、图纸)撰写质量50 结构严谨，逻 辑性强，层次 清晰，语言准 确，文字流畅， 完全符合规范 化求，书写工 整或用计算机 打印成文；图 纸非常工整、 清晰 结构合理，符 合逻辑，文章 层次分明，语 言准确，文字 流畅，符合规 范化要求书写 工整或用计算 机打印成文； 图纸工整、清 晰 结构合理， 层次较为 分明，文理 通顺，基本 达到规范 化求，书写 比较工整； 图纸比较 工整、清晰 结构基本合 理，逻辑基本 清楚，文字尚 通顺，勉强达 到规范化要 求；图纸比较 工整 内容空泛， 结构混乱， 文字表达 不清，错别 字较多，达 不到规范 化要求；图 纸不工整 或不清晰 指导教师评定成绩： 指导教师签名：年月日数据结构第三章习题18页word
重庆大学【大学计算机基础(基础班)】考试要点
数据结构习题
数据结构1-4章习题答案
数据结构习题2011级
重庆大学多媒体复习资料
重庆大学(已有10试题)
数据结构练习题
数据结构英文试题
数据结构复习题
数据结构试题(英文版)C
数据结构复习题汇总
重庆大学计算机网络
相关主题
文本预览