全国2008年10月高等教育自学考试数据结构试题课程代码：02331一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是最符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（ ）A. 栈 B. 队列C. 树 D. 图2.下面程序段的时间复杂度为（ ）for (i=0; i
第一题26、15、19、25
太废脑筋了，懒得想。高手来吧。
CDCADCDC
第六章 树 树是n个结点的有限集合，非空时必须满足：只有一个称为根的结点；其余结点形成m个不相交的子集，并称根的子树。 根是开始结点；结点的子树数称度；度为0的结点称叶子（终端结点）；度不为0的结点称分支结点（非终端结点）；除根外的分支结点称内部结点； 有序树是子树有左，右之分的树；无序树是子树没有左，右之分的树；森林是m个互不相交的树的集合； 树的四种不同表示方法：·树形表示法；·嵌套集合表示法；·凹入表示法·广义表表示法。 二叉树的定义：是n≥0个结点的有限集，它是空集（n=0）或由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。 二叉树不是树的特殊情形，与度数为2的有序树不同。 二叉树的4个重要性质： ·。二叉树上第i层上的结点数目最多为2^（i-1）（i≥1）。； ·深度为k的二叉树至多有（2^k）-1个结点（k≥1）； ·。在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1； ·。具有n个结点的完全二叉树的深度为int（log2n）+1. 满二叉树是一棵深度为k，结点数为（2^k）-1的二叉树；完全二叉树是满二叉树在最下层自右向左去处部分结点； 二叉树的顺序存储结构就是把二叉树的所有结点按照层次顺序存储到连续的存储单元中。（存储前先将其画成完全二叉树） 树的存储结构多用的是链式存储。BinTNode的结构为lchild|data|rchild，把所有BinTNode类型的结点，加上一个指向根结点的BinTree型头指针就构成了二叉树的链式存储结构，称为二叉链表。它就是由根指针root确定的。共有2n个指针域，n+1个空指针。 根据访问结点的次序不同可得三种遍历：先序遍历（前序遍历或先根遍历），中序遍历（或中根遍历）、后序遍历（或后根遍历）。时间复杂度为O（n）。 利用二叉链表中的n+1个空指针域来存放指向某种遍历次序下的前趋结点和后继结点的指针，这些附加的指针就称为“线索”，加上线索的二叉链表就称为线索链表。线索使得查找中序前趋和中序后继变得简单有效，但对于查找指定结点的前序前趋和后序后继并没有什么作用。 树和森林及二叉树的转换是对应的。 转换方法： ·树变二叉树：兄弟相连，保留长子的连线。 ·二叉树变树：结点的右孩子与其双亲连。 ·森林变二叉树：树变二叉树，各个树的根相连。 树的存储结构：·有双亲链表表示法：结点data | parent，对于求指定结点的双亲或祖先十分方便，但不适于求指定结点的孩子及后代。 ·孩子链表表示法：为树中每个结点data | next设置一个孩子链表firstchild，并将data | firstchild存放在一个向量中。 ·双亲孩子链表表示法：将双亲链表和孩子链表结合。 ·孩子兄弟链表表示法：结点结构leftmostchild |data | rightsibing，附加两个分别指向该结点的最左孩子和右邻兄弟的指针域。 树的前序遍历与相对应的二叉树的前序遍历一致；树的后序遍历与相对应的二叉树的中序遍历一致。 树的带权路径长度是树中所有叶结点的带权路径长度之和。树的带权路径长度最小的二叉树就称为二叉树（即哈夫曼树）。 在叶子的权值相同的二叉树中，完全二叉树的路径长度最短。 哈夫曼树有n个叶结点，共有2n-1个结点，没有度为1的结点，这类树又称为严格二叉树。 变长编码技术可以使频度高的字符编码短，而频度低的字符编码长，但是变长编码可能使解码产生二义性。如00、01、0001这三个码无法在解码时确定是哪一个，所以要求在字符编码时任一字符的编码都不是其他字符编码的前缀，这种码称为前缀码（其实是非前缀码）。 哈夫曼树的应用最广泛地是在编码技术上，它能够容易地求出给定字符集及其概率分布的前缀码。哈夫曼编码的构造很容易，只要画好了哈夫曼树，按分支情况在左路径上写代码0，右路径上写代码1，然后从上到下到叶结点的相应路径上的代码的序列就是该结点的前缀码。 第七章 图 图的逻辑结构特征就是其结点（顶点）的前趋和后继的个数都是没有限制的，即任意两个结点之间之间都可能相关。 图GraphG=（V，E），V是顶点的有穷非空集合，E是顶点偶对的有穷集。 有向图Digraph：每条边有方向；无向图Undigraph：每条边没有方向。 有向完全图：具有n*（n-1）条边的有向图；无向完全图：具有n*（n-1）/2条边的无向图； 有根图：有一个顶点有路径到达其它顶点的有向图；简单路径：是经过顶点不同的路径；简单回路是开始和终端重合的简单路径； 网络：是带权的图。 图的存储结构： ·邻接矩阵表示法：用一个n阶方阵来表示图的结构是的，适合稠密图。 ·无向图：邻接矩阵是对称的。 ·有向图：行是出度，列是入度。 建立邻接矩阵算法的时间是O（n+n^2+e），其时间复杂度为O（n^2） ·邻接表表示法：用顶点表和邻接表构成不是的，适合稀疏图。·顶点表结构 vertex | firstedge，指针域存放邻接表头指针。 ·邻接表：用头指针确定。 ·无向图称边表； ·有向图又分出边表和逆邻接表； ·邻接表结点结构为 adjvex | next， 时间复杂度为O（n+e）。，空间复杂度为O（n+e）。。 图的遍历： ·深度优先遍历：借助于邻接矩阵的列。使用栈保存已访问结点。 ·广度优先遍历：借助于邻接矩阵的行。使用队列保存已访问结点。 生成树的定义：若从图的某个顶点出发，可以系统地访问到图中所有顶点，则遍历时经过的边和图的所有顶点所构成的子图称作该图的生成树。 最小生成树：图的生成树不，从不同的顶点出发可得到不同的生成树，把权值最小的生成树称为最小生成树（MST）。 构造最小生成树的算法： ·Prim算法的时间复杂度为O（n^2）与边数无关适于稠密图。 ·Kruskal算法的时间复杂度为O（lge），主要取决于边数，较适合于稀疏图。 最短路径的算法：·Dijkstra算法，时间复杂度为O（n^2）。·类似于prim算法。 拓扑排序：是将有向无环图G中所有顶点排成一个线性序列，若 ∈E（G），则在线性序列u在v之前，这种线性序列称为拓扑序列。 拓扑排序也有两种方法：·无前趋的顶点优先，每次输出一个无前趋的结点并删去此结点及其出边，最后得到的序列即拓扑序列。 ·无后继的结点优先：每次输出一个无后继的结点并删去此结点及其入边，最后得到的序列是逆拓扑序列。 第八章 排序 记录中可用某一项来标识一个记录，则称为关键字项，该数据项的值称为关键字。 排序是使文件中的记录按关键字递增（或递减）次序排列起来。 ·基本操作：比较关键字大小；改变指向记录的指针或移动记录。 ·存储结构：顺序结构、链表结构、索引结构。 经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是稳定的，否则排序算法是不稳定的。 排序过程中不涉及数据的内、外存交换则称之为“内部排序”（内排序），反之，若存在数据的内外存交换，则称之为外排序。 内部排序方法可分五类：插入排序、选择排序、交换排序、归并排序和分配排序。 评价排序算法好坏的标准主要有两条：执行时间和所需的辅助空间，另外算法的复杂程序也是要考虑的一个因素。 插入排序：·直接插入排序： ·逐个向前插入到合适位置。 ·哨兵（监视哨）有两个作用： ·作为临变量存放R[i] ·是在查找循环中用来监视下标变量j是否越界。 ·直接插入排序是就地的稳定排序。时间复杂度为O（n^2），比较次数为（n+2）（n-1）/2；移动次数为（n+4）（n-1）/2； ·希尔排序： ·等间隔的数据比较并按要求顺序排列，最后间隔为1. ·希尔排序是就地的不稳定排序。时间复杂度为O（n^1.25），比较次数为（n^1.25）；移动次数为（1.6n^1.25）； 交换排序：·冒泡排序：·自下向上确定最轻的一个。·自上向下确定最重的一个。·自下向上确定最轻的一个，后自上向下确定最重的一个。 ·冒泡排序是就地的稳定排序。时间复杂度为O（n^2），比较次数为n（n-1）/2；移动次数为3n（n-1）/2； ·快速排序：·以第一个元素为参考基准，设定、动两个指针，发生交换后指针交换位置，直到指针重合。重复直到排序完成。 ·快速排序是非就地的不稳定排序。时间复杂度为O（nlog2n），比较次数为n（n-1）/2； 选择排序：·直接选择排序： ·选择最小的放在比较区前。 ·直接选择排序就地的不稳定排序。时间复杂度为O（n^2）。比较次数为n（n-1）/2； ·堆排序 ·建堆：按层次将数据填入完全二叉树，从int（n/2）处向前逐个调整位置。 ·然后将树根与最后一个叶子交换值并断开与树的连接并重建堆，直到全断开。 ·堆排序是就地不稳定的排序，时间复杂度为O（nlog2n），不适宜于记录数较少的文件。 归并排序： ·先两个一组排序，形成（n+1）/2组，再将两组并一组，直到剩下一组为止。 ·归并排序是非就地稳定排序，时间复杂度是O（nlog2n）， 分配排序：·箱排序： ·按关键字的取值范围确定箱子数，按关键字投入箱子，链接所有非空箱。 ·箱排序的平均时间复杂度是线性的O（n）。 ·基数排序：·从低位到高位依次对关键字进行箱排序。 ·基数排序是非就稳定的排序，时间复杂度是O（d*n+d*rd）。 各种排序方法的比较和选择： ·。待排序的记录数目n；n较大的要用时间复杂度为O（nlog2n）的排序方法； ·记录的大小（规模）；记录大用链表作为存储结构，而快速排序和堆排序在链表上难于实现； ·关键字的结构及其初始状态； ·对稳定性的要求； ·语言工具的条件； ·存储结构； ·时间和辅助空间复杂度。 第九章 查找 查找的同时对表做修改操作（如插入或删除）则相应的表称之为动态查找表，否则称之为静态查找表。 衡量查找算法效率优劣的标准是在查找过程中对关键字需要执行的平均比较次数（即平均查找长度ASL）。 线性表查找的方法： ·顺序查找：逐个查找，ASL=（n+1）/2； ·二分查找：取中点int（n/2）比较，若小就比左区间，大就比右区间。用二叉判定树表示。ASL=（∑（每层结点数*层数））/N. ·分块查找。要求“分块有序”，将表分成若干块内部不一定有序，并抽取各块中的关键字及其位置建立有序索引表。 二叉排序树（BST）定义是：二叉排序树是空树或者满足如下性质的二叉树： ·若它的左子树非空，则左子树上所有结点的值均小于根结点的值； ·若它的右子树非空，则右子树上所有结点的值均大于根结点的值； ·左、右子树本身又是一棵二叉排序树。 二叉排序树的插入、建立、删除的算法平均时间性能是O（nlog2n）。 二叉排序树的删除操作可分三种情况进行处理： ·*P是叶子，则直接删除*P，即将*P的双亲*parent中指向*P的指针域置空即可。 ·*P只有一个孩子*child，此时只需将*child和*p的双亲直接连接就可删去*p. ·*p有两个孩子，则先将*p结点的中序后继结点的数据到*p，删除中序后继结点。 关于B-树（多路平衡查找树）。它适合在磁盘等直接存取设备上组织动态的查找表，是一种外查找算法。建立的方式是从下向上拱起。 散列技术：将结点按其关键字的散列地址存储到散列表的过程称为散列。散列函数的选择有两条标准：简单和均匀。 常见的散列函数构的造方法： ·。平方取中法：hash=int（（x^2）%100） ·。除余法：表长为m，hash=x%m ·。相乘取整法：hash=int（m*（x*A-int（x*A））；A=0.618 ·。随机数法：hash=random（x）。 处理冲突的方法：·开放定址法： ·一般形式为hi=（h（key）+di）%m1≤i≤m-1，开放定址法要求散列表的装填因子α≤1. ·开放定址法类型： ·线性探查法：address=（hash（x）+i）%m； ·二次探查法：address=（hash（x）+i^2）%m； ·双重散列法：address=（hash（x）+i*hash（y））%m； ·拉链法： ·是将所有关键字为同义词的结点链接在同一个单链表中。 ·拉链法的优点： ·拉链法处理冲突简单，且无堆积现象； ·链表上的结点空间是动态申请的适于无法确定表长的情况； ·拉链法中α可以大于1，结点较大时其指针域可忽略，因此节省空间； ·拉链法构造的散列表删除结点易实现。 ·拉链法也有缺点：当结点规模较小时，用拉链法中的指针域也要占用额外空间，还是开放定址法省空间。 第十章 文件 文件是性质相同的记录的集合。记录是文件中存取的基本单位，数据项是文件可使用的最小单位，数据项有时称字段或者属性。 文件·逻辑结构是一种线性结构。 ·操作有：检索和维护。并有实时和批量处理两种处理方式。 文件·存储结构是指文件在外存上的组织方式。 ·基本的组织方式有：顺序组织、索引组织、散列组织和链组织。 ·常用的文件组织方式：顺序文件、索引文件、散列文件和多关键字文件。 评价一个文件组织的效率，是执行文件操作所花费的时间和文件组织所需的存储空间。 检索功能的多寡和速度的快慢，是衡量文件操作质量的重要标志。 顺序文件是指按记录进入文件的先后顺序存放、其逻辑顺序和物理顺序一致的文件。主关键字有序称顺序有序文件，否则称顺序无序文件。 一切存储在顺序存储器（如磁带）上的文件都只能顺序文件，只能按顺序查找法存取。 顺序文件的插入、删除和修改只能通过复制整个文件实现。 索引文件的组织方式：通常是在主文件之外建立一张索引表指明逻辑记录和物理记录之间一一对应的关系，它和主文件一起构成索引文件。 索引非顺序文件中的索引表为稠密索引。索引顺序文件中的索引表为稀疏索引。 若记录很大使得索引表也很大时，可对索引表再建立索引，称为查找表。是一种静态索引。 索引顺序文件常用的有两种： ·ISAM索引顺序存取方法：是专为磁盘存取文件设计的，采用静态索引结构。 ·VSAM虚拟存储存取方法：采用B+树作为动态索引结构，由索引集、顺序集、数据集组成。 散列文件是利用散列存储方式组织的文件，亦称为直接存取文件。 散列文件 ·优点是：文件随机存放，记录不需要排序；插入删除方便；存取速度快；不需要索引区，节省存储空间。 ·缺点是：不能进行顺序存取，只能按关键字随机存取，且询问方式限地简单询问，需要重新组织文件。 多重表文件：对需要查询的次关键字建立相应的索引，对相同次关键字的记录建一个链表并将链表头指针、长度、次关键字作为索引表的索引项。 倒排表：次关键字索引表称倒排表，主文件和倒排表构成倒排文件。
第一题26、15、19、25
不好意思，我不知道
( )逻辑结构相同但存储不同 可以是不同的数据结构 例如 线性表的逻辑结构属于线性结构 采用顺序存储结构为顺序表 而采用链式存储结构称为线性链表
( )栈和队列的逻辑结构相同 其存储表示也可相同(顺序存储和链式存储) 但由于其运算集合不同而成为不同的数据结构
( )数据结构的评价非常复杂 可以考虑两个方面 一是所选数据结构是否准确 完整的刻划了问题的基本特征;二是是否容易实现(如对数据分解是否恰当;逻辑结构的选择是否适合于运算的功能 是否有利于运算的实现;基本运算的选择是否恰当 )
评价好的算法有四个方面 一是算法的正确性;二是算法的易读性;三是算法的健壮性;四是算法的时空效率(运行)
( )见上面题 ( )见上面题 ( )见上面题
( )算法的时间复杂性是算法输入规模的函数 算法的输入规模或问题的规模是作为该算法输入的数据所含数据元素的数目 或与此数目有关的其它参数 有时考虑算法在最坏情况下的时间复杂度或平均时间复杂度
( )算法是对特定问题求解步骤的描述 是指令的有限序列 其中每一条指令表示一个或多个操作 算法具有五个重要特性 有穷性 确定性 可行性 输入和输出
( )频度 在分析算法时间复杂度时 有时需要估算基本操作的原操作 它是执行次数最多的一个操作 该操作重复执行的次数称为频度
集合 线性结构 树形结构 图形或网状结构 逻辑结构 存储结构 操作(运算)
通常考虑算法所需要的存储空间量和算法所需要的时间量 后者又涉及到四方面 程序运行时所需输入的数据总量 对源程序进行编译所需时间 计算机执行每条指令所需时间和程序中指令重复执行的次数
D是数据元素的有限集合 S是D上数据元素之间关系的有限集合
数据结构 这一术语有两种含义 一是作为一门课程的名称;二是作为一个科学的概念 作为科学概念 目前尚无公认定义 一般认为 讨论数据结构要包括三个方面 一是数据的逻辑结构 二是数据的存储结构 三是对数据进行的操作(运算) 而数据类型是值的集合和操作的集合 可以看作是已实现了的数据结构 后者是前者的一种简化情况
见上面题
将学号 姓名 平均成绩看成一个记录(元素 含三个数据项) 将 个这样的记录存于数组中 因一般无增删操作 故宜采用顺序存储
typedef struct
{int num;//学号
char name[ ];//姓名
float score;/平均成绩
}node;
node student[ ];
见上面题 ( )
应从两方面进行讨论 如通讯录较少变动(如城市私人电话号码) 主要用于查询 以顺序存储较方便 既能顺序查找也可随机查找;若通讯录经常有增删操作 用链式存储结构较为合适 将每个人的情况作为一个元素(即一个结点存放一个人) 设姓名作关键字 链表安排成有序表 这样可提高查询速度
线性表中的插入 删除操作 在顺序存储方式下平均移动近一半的元素 时间复杂度为O(n);而在链式存储方式下 插入和删除时间复杂度都是O( )
对算法A 和A 的时间复杂度T 和T 取对数 得nlog 和 logn 显然 算法A 好于A
struct node
{int year month day; };
typedef struct
{int num;//帐号
char name[ ];//姓名
struct node date;//开户年月日
int tag;//储蓄类型 如 零存 一年定期……
float put;//存入累加数;
float interest;//利息
float total;//帐面总数
}count;
( )n ( )n+ ( )n ( )(n+ )(n )/ ( )(n+ )(n )/ ( )n
‘。’;;;;';'v;;b ；‘；。c.';;dpfdpdfpf[]dpp []’；‘；=肋间肌解放方法就解放机经济几哦 经济棵艰苦看法看来棵；可；；可；了；可；看法的；防空洞十分发生；地方；迪斯科法；第十六法；打开法；看法；看法大幅度；浪费扩大；浪费扩大；防空洞；浪费扩大；立刻法；地方克当量反抗；大礼服棵；地方扩大反抗色额；立刻；饿额；而；了； ；老；力量可；考察；立刻；立刻；出来；可是蓝点颏立刻了；人口台；如同可靠； 了；反对乐观法律老古董法；了；历史；六十六赛力散；道路按时；但是；道路按时大力士大力士；六十六但是；类毒素；劳动；似的；赛力散；劳动；了；三联单；劳动手段拉萨；道路撒旦拉萨；大力士的；历史；劳动；类毒素；类毒素；类毒素；劳动；撒赖的；撒赖的；撒赖的；撒赖的；了；了；为了；了；饿勒派我’
把邮箱给我，我给你发过去！！！但是你得先采纳我的！
全国2008年10月高等教育自学考试数据结构试题课程代码：02331一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是最符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（ ）A. 栈 B. 队列C. 树 D. 图2.下面程序段的时间复杂度为（ ）for (i=0; i
数据结构笔试题和答案
数据结构笔试题和答案：
1. 在一个单链表中p所指结点之前插入一个s (值为e)所指结点时，可执行如下操作：
q=head;
while (q->next!=p) q=q->next;
s= new Node; s->data=e;
q->next= ; //填空
s->next= ; //填空
2. 线性表的顺序存储结构是一种 的存储结构，而链式存储结构是一种___的存储结构。
A.随机存取 B.索引存取 C.顺序存取 D.散列存取
3. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址___。
A. 必须是连续的 B. 部分地址必须是连续的
C. 一定是不连续的 D. 连续或不连续都可以
4. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行____。
A. s->next=p->next; p->next=s; B. p->next=s->next; s->next=p;
C. q->next=s; s->next=p; D. p->next=s; s->next=q;
5. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行____。
A. s->next=p; p->next=s; B. s->next=p->next; p->next=s;
C. s->next=p->next; p=s; C. p->next=s; s->next=p;
6. 在一个单链表中，若删除p所指结点的后续结点，则执行____。
A. p->next= p->next->next; B. p= p->next; p->next= p->next->next;
C. p->next= p->next; D. p= p->next->next;
7. 链表不具备的特点是 ____ 。
A 可随机访问任何一个元素 B 插入、删除操作不需要移动元素
C 无需事先估计存储空间大小 D 所需存储空间与线性表长度成正比
8. 以下关于线性表的说法不正确的是 。
A 线性表中的`数据元素可以是数字、字符、记录等不同类型。
B 线性表中包含的数据元素个数不是任意的。
C 线性表中的每个结点都有且只有一个直接前趋和直接后继。
D 存在这样的线性表：表中各结点都没有直接前趋和直接后继。
9. 在一个长度为n的顺序表中删除第i个元素，要移动 个元素。如果要在第i个元素前插入一个元素，要后移( )个元素。 N-I N-I+1
答案
1.q->next=s;
s->next=p;
2.A/C(这题是考察对概念的理解，可参考第7题，“顺序表才能随即存取，而链表不可以”)
3.D
4.C
5.B
6.A
7.A(此题绝对选A，因为链表只能根据他的前一个结点才能找到下一个结点，不具备随即访问元素的功能)
8.C
9.n-i; n-i+1
更多的相关笔试题目推荐：
融捷科java软件工程师技笔试题 运营维护工程师笔试题 中国银行计算机方向笔试题目
CDCADCDC
第一题26、15、19、25
1 、在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用折半查找法查找关键字值20，需做的关键字比较次数为 4 。2、抽象数据类型的三大要素为 数据 、 数据之间结构 和 操作 。3、空格串的长度等于 0 。4 、栈和队列的区别仅在于 插入&&删除 操作定义不相同。5、设一个线性表的长度为50，P是指向线性链表的第10个元素，且P->next->next 指向第 11 元素。6、二叉树的第i层最多有 2^(i-1) 个结点，深度为k的二叉树最多有 2^k-1 个结点。7、利用MST性质来构造最小生成树的两种常用算法为______PRIM___和___KRUSKAL_______。8、常见的四类基本数据结构有：__栈______、____队列_____、____树______、______链表_____。（不确定，数据结构太多，究竟要写那几个？）明天再打 二、判断(对的打∨,错误打×, 10×2 = 20 分)1、 由于链式存储结构不要求逻辑上相邻的元素在物理位置上也相邻，因此，它具有随机存取的优点( y)。2、 赫夫曼树是指带权路径长度WPL最小的二叉树。一般而言，在给定条件下构造出的赫夫曼树不是唯一的 (y )。3、 非空完全二叉树的一个任意结点的右子树深度与其左子树深度的差值或者为0或者为1( y )。4、 先序遍历二叉排序树可得到一个关键字有序的序列( n) 。5、 在n个结点的无向图,若边数大于n-1,则该图必是连通图 ( n )。6、 在n个元素进栈后，它们的出栈顺序和进栈顺序一定正好相反( n )。7、 往顺序表中插人一个元素，平均要移动大约一半的元素(y )。8、 类似于算法的时间复杂度，空间复杂度可以作为算法所需存储空间的量度( y )。9、 赫夫曼树一定是满二叉树( n )。10、 队列的基本特征是先进后出( n )。三、选择题（10×2=20分）1、 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？( B )A. 2 3 4 1 5 6 B. 1 2 4 5 3 6C. 6 4 5 1 2 3 D. 4 5 3 1 2 62、 一棵完全二叉树上有1001个结点，其中叶子结点的个数是BA. 254 B. 500C. 250 D. 以上答案都不对 3、线性链表不具有的特点(A ).A.随机访问 B.不必事先估计所需存储空间大小C.插入与删除时不必移动元素 D.所需空间与线性表长度成正比4、向顺序栈中压入新元素时,应当(B ).(此题需看书上栈定义)A.先移动栈顶指针,再存入元素 B.先存入元素,再移动栈顶指针C.先后次序无关紧要 D.同时进行5、 具有65个结点的完全二叉树的高度为( B). (根的层次号为1)A.8 B.7C.6 D.56、 由权值分别为3，8，10，2，6的叶子结点生成一棵哈夫曼树，则其中非终端结点数为(A )。A. 2 B. 3C. 4 D. 57、 n个顶点的有向完全图中含有向边的数目最多为( D ) A.n-1 B.n C.n(n-1)/2 D.n(n-1) 8、一个对象序列的排序码为{46,79,56,38,40,84},采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为(C ). A.{38,46,79,56,40,84} B.{38,79,56,46,40,84} C.{40,38,46,56,79,84} D.{38,46,56,79,40,84} 9、长度为11的哈希表中已经填有关键字17，60，29的记录，采用二次探测再散列方法解决冲突，则填入关键字38其地址应该为( D)（哈希函数为h(key)=key mod 11） A.4 B.5 C.3 D.610、在一个无向图中,所有顶点的度数之和等于所有边数的(B )倍.A.3 B.2 C.1 D.1/2打完了，为了数据结构考试攒人品~
3.28void InitCiQueue(CiQueue&Q)//初始化循环链表表示的队列Q{Q=(CiLNode*)malloc(sizeof(CiLNode));Q->next=Q;}//InitCiQueuevoidEnCiQueue(CiQueue&Q,int x)//把元素x插入循环列表表示的队列Q,Q指向队尾元素，Q->next指向头结点，Q->next->next指向队尾元素{p=(CiLNode*)malloc(sizeof(CiLNode));p->data=x;p->next=Q->next;//直接把p加在Q的后面Q->next=p;Q=p;//修改尾指针}Status DeCiQueue(CiQueue&Q,int x)//从循环链表表示的队列Q头部删除元素x{if(Q==Q->next)return INFEASIBLE;//队列已空p=Q->next->next;x=p->data;Q->next->next=p->next;free(p);rturn OK;}//DeCiqueue3.31int Palindrome_Test(){InitStack(S);InitQueue(Q);while((c=getchar())!='@'){Push(S,c);EnQueue(Q,c);}while(!StackEmpty(S)){pop(S,a);DeQueue(Q,b);if(a!=b)return ERROR;}return OK;}
1 下列数据结构中，能用二分法进行查找的是__A____。 A、顺序存储的有序线性表 B、线性链表 C、二叉链表 D、有序线性链表 解析：二分法查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列(即从小到大，但允许相邻元素值相等)。 2 在软件设计中，不属于过程设计工具的是__D____。 A、PDL(过程设计语言) B、PAD图 C、N-S图 D、DFD图 解析：软件设计工具包括：程序流程图、N-S、PAD、HIPO，判定表，PDL(伪码)。而DFD(数据流图)属于结构化分析工具。 3 在switch(expression)语句中，expression的数据类型不能是__A____。 A、double B、char C、byte D、short 解析：表达式expression只能返回这个几种类型的值：int、byte、short和char。多分支语句把表达式返回的值依次与每个case子句中的值相比较，如果遇到匹配的值，则执行该case子句后的语句序列。 4 下列叙述中，错误的是__D____。 A、父类不能替代子类 B、子类能够替代父类 C、子类继承父类 D、父类包含子类 5 通过继承实现代码复用： Java中所有的类都是通过直接或间接地继承java.lang.Object类得到的。继承而得到的类称为子类，被继承的类称为父类。子类不能继承父类中访问权限为private的成员变量和方法，子类可以重写父类的方法，及命名与父类同名的成员变量。 子类通过隐藏父类的成员变量和重写父类的方法，把父类的状态和行为改变为自身的状态和行为。注意：子类中重写的方法和父类中被重写的方法要具有相同的名字，相同的参数表和相同的返回类型，只是函数体不同。 由于子类继承了父类所有的属性(私有的除外)，所以子类对象可以作为父类对象使用。程序中凡是使用父类对象的地方，都可以用子类对象来代替。一个对象可以通过引用子类的实例来调用子类的方法。 java运行时系统根据调用该方法的实例，来决定调用哪个方法。对子类的一个实例，如果子类重写了父类的方法，则运行时系统调用子类的方法;如果子类继承了父类的方法(未重写)，则运行时系统调用父类的方法。 6 自定义表格类中的model部分应实现的接口是___A___。 A、AbstractTableModel B、JTable C、TableModel D、TableModelable 7 下列代码中，将引起编译错误的行是__B____。 1)public class Exercise{ 2) public static void main(String args[]){ 3) float f=0.0; 4) f+=1.0; 5) } 6) } A、第2行 B、第3行 C、第4行 D、第6行 解析：float定义变量赋值时，需要在数值后面加f以标识它为浮点型，让系统知道该给它精确到多少位。
一．
1,复杂性 2.线性结构 非线性结构
3．可以按序号随机存取 4.数据元素
5.后进先出 6.n 7.只能在队头进行
9.长度 1 深度 1
10 -+A*BC/DE
11
12 顶点Vp到顶点Vq之间的路径是指定的序列Vp，Vi1，Vi2•••Vim，Vq。
13 n（n-2）/2 14 n—1 15 2n—1
17 一种存储结构
19可以从表中任意结点开始遍历整个链表；只用一个指向尾结点的指针对链表头、尾进行操作，提高了效率。
20栈是仅限制在表的一端进行插入和删除的运算的线性表，是一种操作受限的线性表。
二．
1算法 的时间复杂度和空间复杂度
2.队列
3.
4嵌套集合表示法，广义表表示法，凹入表示法
5. 45 6.S(1) X(1) S(2)S(3)X(3)S(4)X(4)X(2)
7（1） O（nˆ2）
（2） O（nˆ2）
8.
哈夫曼树：
WPL=2*5+4*5+5*4+16*3+8*3+7*3+30=173
9.邻接矩阵：
邻接表：
10.二叉树：
前序：ABCEFD
中序：BEFCDA
后序：FEDCBA
1.X.数据是计算机接收,识别,存储,加工处理的对象的全体.2.√.最后不知道要不要加上一个"运算及实现"3.√4.X.先进后出.5.X6.√7.X.最多有2^h -1个结点8.X9.√10.X二,1.数据结构.2.线性结构和非线性结构.3.顺序表.4.队列.5.2^h -1.6.顺序表.7.排序.8.三.1.A2.A.先进先出.3.没有学.4.C.5.B.一串下去.
全国2008年10月高等教育自学考试数据结构试题课程代码：02331一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是最符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（ ）A. 栈 B. 队列C. 树 D. 图2.下面程序段的时间复杂度为（ ）for (i=0; i