下载文档原格式
《数据结构导论》考纲、试题、答案一、考试说明本课程为闭卷考试（开卷考试、上交论文、上交作品等考查类课程无考试指导）（根据课程考核实际方式选择），考试时间90分钟，考试题型包括以下题型中的三种（根据每门课程的实际确定题型及分值所占比例）：1、判断题（正确打√，错误打×，每题3分，共15分）2、填空（每空2分，共20分）3、选择题（每题3分，共15分）4、名词解释（每小题4分，共20分）5、简答题（每题6分，共30分）备注：以上题型供参考二、课程知识要点第一章◆数据结构◆实例第二章◆银行排队顺序存储◆学生健康登记表第三章◆栈和队列◆回文◆杨辉三角第四章◆串◆文本加密第五章◆内部排序◆查找◆二叉树第六章◆树◆图◆数组第七章◆文件◆外部排序备注：根据教材实际章节汇总要点，突出需要掌握的重点内容三、重点习题1、判断题◆具有n 个结点的线索二叉树上，含有n+1个线索。
◆三叉链表属于二叉树存储结构。
◆哈夫曼树不存在度为1的结点。
◆栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。
◆栈和队列的存储方式既可是顺序方式，也可是链接方式。
◆二叉树中每个结点的两棵子树是有序的。
2、填空◆数据的逻辑结构指◆一个算法的时间复杂度◆单链表中，增加头结点的目的◆表长为0的线性表◆串的长度◆若两个串的长度相等且对应位置上的字符也相等◆常用的插入排序◆常用的处理冲突的方法◆常用的选择排序方法◆衡量一个算法的优劣主要考虑◆在有n个结点的二叉链表中，空链域的个数◆常用的选择排序方法◆具有10个顶点的无向图，边的总数最多为◆堆排序◆已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有多少个叶子结点◆树有三种常用形式◆深度为5的二叉树至多有多少个结点3、选择题◆串是一种特殊的线性表，其特殊性体现在◆数据的逻辑结构◆算法◆在数据结构中，从逻辑上可以把数据结构分成◆算法分析的目的◆链接存储的存储结构所占存储空间◆链表◆非线性结构是数据元素之间存在一种4、名词解释◆数据◆运算与运算实现的相同点◆串变量◆连通分量◆头指针5、简答题◆数据逻辑结构的特点◆假定一棵二叉树广义表表示为a(b(c,d)),c(((,8))),分别给出先序，中序后序和后序的遍历结果◆假定一组记录的排序码为(46，79，56，38，40，84，50，42)，则利用堆排序方法建立的初始堆为◆从一维数组A[n)中二分查找关键字为K的元素的递归算法，若查找成功则返回对应元素的下标，否则返回一1。
数据结构导论自考题-2(总分100, 做题时间90分钟)一、单项选择题在每小题列出的四个备选项中只有一个是符合题目要求的。
1.与数据元素本身的形式、内容、相对位置、个数无关的是数据的( ) A．存储结构B．存储实现C．逻辑结构D．运算实现SSS_SIMPLE_SINA B C D分值: 2答案:C2.所有的存储结点存放在一个连续的存储空间，该存储方式是( )存储方式。
A．顺序B．链式C．索引D．散列SSS_SIMPLE_SINA B C D分值: 2答案:A[解析] 本题主要考查的知识点是顺序存储方式。
[要点透析] 顺序存储方式是指所有存储结点存放在一个连续的存储区里。
利用结点在存储器中的相对位置来表示数据元素之间的逻辑关系。
3.设线性表有n个元素，以下操作中，( )在顺序表上实现比在链表上实现效率更高。
A．输出第i(1≤i≤n)个元素值B．交换第1个元素与第2个元素的值C．在第i个元素前插入一个元素D．删除第i个元素SSS_SIMPLE_SINA B C D分值: 2答案:A[解析] 本题主要考查的知识点为顺序表和链表。
[要点透析] 由于顺序表具有随机存取特性，所以和链表相比输出第i个元素时效率很高。
本题答案为A。
4.与单链表相比，双链表的优点之一是( )A．插入、删除操作更简单B．可以进行随机访问C．可以省略表头指针或表尾指针D．前后访问相邻结点更灵活SSS_SIMPLE_SINA B C D分值: 2答案:D5.循环队列的队满条件为( )A．(CQ.rear+1)%maxsize==(CQ.front+1)%maxsizeB．(CQ.rear+1)%maxsize==CQ.front+1C．(CQ.rear+1)%maxsize==CQ.frontD．CQ.rear==CQ.frontSSS_SIMPLE_SINA B C D分值: 2答案:C[解析] 本题主要考查的知识点是循环队列的队满条件。
自考专业(计算机信息管理)数据结构导论考试真题及答案
一、选择题（每题2分，共20分） 1. 数据结构是研究（ ） A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的检索技术 答案：C 2. 在数据结构中，通常把满足以下哪一个条件的序列称为线性表（ ）
A. 数据元素之间有多个前驱和多个后继 B. 数据元素之间只有一个前驱和一个后继 C. 数据元素之间只有一个前驱 D. 数据元素之间只有一个后继 答案：B 3. 下列哪种数据结构中，元素之间存在一种一对一的对应关系（ ）
A. 栈 B. 队列 C. 树 D. 图 答案：B 4. 在下列数据结构中，哪个是非线性结构（ ） A. 队列 B. 栈 C. 二叉树 D. 线性表 答案：C 5. 设栈的顺序存储空间为S(1:m)，栈空的条件是（ ）
A. top=m B. top=0 C. top=m+1 D. top=-1 答案：B 6. 下列关于线性表的叙述中，错误的是（ ） A. 线性表是一种线性结构 B. 线性表可以为空表 C. 线性表的元素个数不变 D. 线性表的每个元素都有一个前驱和后继 答案：C 7. 在下列关于队列的叙述中，正确的是（ ） A. 队列是一种先进先出的线性表 B. 队列是一种先进后出的线性表 C. 队列的入口和出口是同一个端点 D. 队列的入口和出口是不同的端点 答案：A 8. 下列关于串的叙述中，正确的是（ ） A. 串是字符的有限序列 B. 串中字符的数目称为串的长度 C. 串中可以包含空格 D. 串的任意一个字符都可以在串中任意位置出现 答案：B 9. 下列关于二叉树的叙述中，正确的是（ ） A. 二叉树是一种特殊的树 B. 二叉树是一种有序树 C. 二叉树中每个节点最多有两个子节点 D. 二叉树中每个节点最多有一个子节点 答案：C 10. 下列关于图的叙述中，正确的是（ ） A. 图是一种线性结构 B. 图是一种非线性结构 C. 图中的顶点之间都有边相连 D. 图中的边都有方向 答案：B 二、填空题（每题2分，共20分） 1. 数据的存储结构包括顺序存储结构和________存储结构。 答案：链式 2. 在链式存储结构中，每个节点包括两部分：数据域和________域。
2012年10月高等教育自学考试全国统一命题考试数据结构导论试题课程代码：02142请考生按规定用笔将所有试题的答案涂、写在答题纸上。
选择题部分注意事项：1. 答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。
2. 每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。
如需改动，用橡皮擦干净后，再选涂其他答案标号。
不能答在试题卷上。
一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的。
错选、多选或未选均无分。
1.下面几种算法时间复杂度阶数中，值最大的是A.O(nlog2n)B.O(n2)C.O(n)D.O(2n)2.即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果，这种算法好坏的评价因素称为A.正确性B.易读性C.健壮性D.时空性3.设顺序表的长度为100，则在第40个元素之后插入一个元素所需移动元素的个数为A.40B.60C.61D.1004.设带头结点的单循环链表的头指针为head，则判断该链表是否为空的条件是A. head->next==headB. head->next==NULLC. head!=NULLD. head==NULL5.在链栈的运算中，不需要．．．判断栈是否为空的是A.出栈B.进栈C.取栈顶元素D.求链栈的元素个数6.一个队列的输入序列是A，B，C，D，则该队列的输出序列是A.A，B，C，DB.B，C，D，AC.D，C，B，AD.C，D，B，A7.以行序为主序的二维数组a［3］［5］中，第一个元素a［0］［0］的存储地址是100，每个元素占2个存储单元，则a［1］［2］的存储地址是A.100B.108C.114D.1168.对任何一棵二叉树T，若叶结点数为5个，则度为2的结点个数为A.4B.5C.6D.无法确定9.m个叶结点的哈夫曼树中，其结点总数为A.mB.2m+1C.2mD.2m-110.二叉树的中序遍历序列中，结点P排在结点Q之前的条件是A.在二叉树中P在Q的左边B.在二叉树中P在Q的右边C.在二叉树中P是Q的祖先D.在二叉树中P是Q的子孙11.有10个顶点的无向完全图的边数是A.11B.45C.55D.9012.在带权有向图中求两个结点之间的最短路径可以采用的算法是A.迪杰斯特拉（Dijkstra）算法B.克鲁斯卡尔（Kruskal）算法C.普里姆（Prim）算法D.深度优先搜索（DFS）算法13.二分查找（Binary Search）算法的时间复杂度是A.O（n2）B.O（nlog2n）C.O（n）D.O（log2n）14.在一棵初始时为空的二叉树中，依次插入键值序列50，72，43，85，75，20，38，45，65，60，构造对应的二叉排序树以后，查找元素60要进行的比较次数是A.2B.3C.4D.515.快速排序属于A.插入排序B.交换排序C.选择排序D.归并排序非选择题部分注意事项：用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。
数据结构导论自考题模拟9(总分100, 做题时间90分钟)一、单项选择题在每小题列出的四个备选项中只有一个是符合题目要求的1.关于算法的描述，不正确的是______SSS_SINGLE_SELA 算法最终必须由计算机程序实现B 所谓最坏时间复杂度是指最坏情况下，估算算法执行时间的一个上界C 健壮的算法不会因非法的输入数据而出现莫名其妙的运行结果D 算法的优劣与算法描述语言无关分值: 2答案:A2.线性表若采用链表存储结构，则要求内存中可用存储单元的地址______SSS_SINGLE_SELA 必须是连续的B 部分地址必须是连续的C 一定是不连续的D 连续不连续都可以分值: 2答案:D[考点] 本题主要考查的知识点是线性表。
由于线性表的顺序存储方式要求占用连续的空间，存储分配只能预先进行，为了克服顺序表的缺点，采用链接方式存储线性表。
3.以下属于逻辑结构的是______SSS_SINGLE_SELA 顺序表B 哈希表C 有序表D 单链表分值: 2答案:C[考点] 本题主要考查的知识点是逻辑结构。
只有有序表属于逻辑结构，其他选项都属于存储结构。
本题答案为C。
4.已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为______SSS_SINGLE_SELA 5B 6C 16D 17分值: 2答案:C5.对特殊矩阵采用压缩存储的目的主要是为了______SSS_SINGLE_SELA 表达变得简单B 对矩阵元素的存取变得简单C 去掉矩阵中多余元素D 减少不必要的存储空间分值: 2答案:D6.将一棵有1000个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的分支结点的编号为______SSS_SINGLE_SELA 48B 49C 50D 51分值: 2答案:C[考点] 本题主要考查的知识点是完全二叉树。
2012年10月高等教育自学考试全国统一命题考试数据结构导论试题课程代码：02142请考生按规定用笔将所有试题的答案涂、写在答题纸上。
选择题部分注意事项：1. 答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。
2. 每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。
如需改动，用橡皮擦干净后，再选涂其他答案标号。
不能答在试题卷上。
一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的。
错选、多选或未选均无分。
1.下面几种算法时间复杂度阶数中，值最大的是A.O(nlog2n)B.O(n2)C.O(n)D.O(2n)2.即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果，这种算法好坏的评价因素称为A.正确性B.易读性C.健壮性D.时空性3.设顺序表的长度为100，则在第40个元素之后插入一个元素所需移动元素的个数为A.40B.60C.61D.1004.设带头结点的单循环链表的头指针为head，则判断该链表是否为空的条件是A. head->next==headB. head->next==NULLC. head!=NULLD. head==NULL5.在链栈的运算中，不需要．．．判断栈是否为空的是A.出栈B.进栈C.取栈顶元素D.求链栈的元素个数6.一个队列的输入序列是A，B，C，D，则该队列的输出序列是A.A，B，C，DB.B，C，D，AC.D，C，B，AD.C，D，B，A7.以行序为主序的二维数组a［3］［5］中，第一个元素a［0］［0］的存储地址是100，每个元素占2个存储单元，则a［1］［2］的存储地址是A.100B.108C.114D.1168.对任何一棵二叉树T，若叶结点数为5个，则度为2的结点个数为A.4B.5C.6D.无法确定9.m个叶结点的哈夫曼树中，其结点总数为A.mB.2m+1C.2mD.2m-110.二叉树的中序遍历序列中，结点P排在结点Q之前的条件是A.在二叉树中P在Q的左边B.在二叉树中P在Q的右边C.在二叉树中P是Q的祖先D.在二叉树中P是Q的子孙11.有10个顶点的无向完全图的边数是A.11B.45C.55D.9012.在带权有向图中求两个结点之间的最短路径可以采用的算法是A.迪杰斯特拉（Dijkstra）算法B.克鲁斯卡尔（Kruskal）算法C.普里姆（Prim）算法D.深度优先搜索（DFS）算法13.二分查找（Binary Search）算法的时间复杂度是A.O（n2）B.O（nlog2n）C.O（n）D.O（log2n）14.在一棵初始时为空的二叉树中，依次插入键值序列50，72，43，85，75，20，38，45，65，60，构造对应的二叉排序树以后，查找元素60要进行的比较次数是A.2B.3C.4D.515.快速排序属于A.插入排序B.交换排序C.选择排序D.归并排序非选择题部分注意事项：用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。
数据结构试题(含答案)数据结构试题(含答案)一、选择题1. 数据结构是计算机科学中的一个重要概念。
下列选项中，不属于数据结构的是：A. 数组B. 栈C. 数据库D. 链表答案：C2. 在数据结构中，栈(Stack)是一种后进先出(LIFO)的数据结构。
下列操作中，不属于栈的是：A. 入栈B. 出栈C. 遍历D. 清空栈答案：C3. 链表(Linked List)是一种常见的数据结构，它由一系列节点组成，每个节点包含两个部分：数据和指向下一个节点的指针。
下列选项中，不属于链表的是：A. 单链表B. 双链表C. 循环链表D. 二叉树答案：D4. 哈希表(Hash Table)是一种根据关键码直接访问存储位置的数据结构。
下列选项中，不属于哈希表的优点是：A. 快速查找B. 插入和删除操作效率高C. 数据无序D. 冲突较少答案：C二、填空题1. 树(Tree)是一种非线性数据结构，它由一组以边连接的节点组成。
树中每个节点最多可以有________个子节点。
答案：无限制/任意个2. 图(Graph)是由节点和连接节点的边组成的数据结构。
图中节点的度是指与该节点相连接的边的________。
答案：数量3. 广度优先搜索(BFS)和深度优先搜索(DFS)是常用的图遍历算法。
在BFS中，使用________结构来保存待访问的节点。
答案：队列4. 在二叉搜索树(Binary Search Tree)中，左子树中的每个节点的值都小于根节点的值，右子树中的每个节点的值都大于根节点的值。
这种特性称为_______________。
答案：二叉搜索树性质三、简答题1. 请简要说明线性数据结构和非线性数据结构的区别。
答案：线性数据结构是指数据元素之间存在一对一的线性关系，例如数组、栈、队列等；而非线性数据结构是指数据元素之间存在一对多或多对多的关系，例如树、图等。
线性数据结构的存储方式是连续的，非线性数据结构的存储方式是离散的。
数据结构试题及答案试题一：线性表题目：以下关于线性表的叙述中，错误的是（）A. 线性表是一种基本的数据结构，它是由n个数据元素组成的有限序列B. 线性表中的数据元素可以是基本数据类型，也可以是复合数据类型C. 线性表中的数据元素是有序的，即元素之间的顺序是固定的D. 线性表的长度可以是零，也可以是任意正整数答案：D解析：线性表的长度可以是零，也可以是任意非负整数。
当线性表的长度为零时，称为空表。
---试题二：栈和队列题目：以下关于栈和队列的叙述中，正确的是（）A. 栈是一种先进先出（FIFO）的数据结构B. 队列是一种先进后出（LIFO）的数据结构C. 栈的插入和删除操作都是在栈顶进行的D. 队列的插入操作在队尾进行，删除操作在队头进行答案：CD解析：栈是一种先进后出（LIFO）的数据结构，而队列是一种先进先出（FIFO）的数据结构。
栈的插入和删除操作都是在栈顶进行的，而队列的插入操作在队尾进行，删除操作在队头进行。
---试题三：链表题目：以下关于链表的叙述中，错误的是（）A. 链表是一种动态的数据结构，其大小可以在运行时改变B. 链表中的元素可以是不连续存储的C. 链表的每个节点至少包含两个部分：一个是存储元素的数据域，另一个是存储下一个节点地址的指针域D. 链表的最后一个节点的指针域通常设置为NULL答案：A解析：链表确实是一种动态的数据结构，其大小可以在运行时改变。
但是，链表的大小并不是可以无限增加的，它受到系统内存大小的限制。
---试题四：树和二叉树题目：以下关于树和二叉树的叙述中，正确的是（）A. 树是一种非线性的层次结构的数据结构B. 二叉树是一种特殊的树，每个节点最多有两个子节点C. 在二叉树中，节点的度是指节点的子节点数D. 二叉树的节点个数n与边数e之间的关系是 n = e + 1答案：ABCD解析：树是一种非线性的层次结构的数据结构，每个节点可以有零个或多个子节点。
二叉树是一种特殊的树，每个节点最多有两个子节点，通常称为左子节点和右子节点。
综合试题一参考答案：一、单项选择题1.B2.B3.B4.D5.D6.D7.B8.C9.D 10.A11.B 12.C 13.A 14.C 15.D二、填空题16．线性结构图状结构 17．O(n2)18．顺序实现链接实现 19．顺序存储结构链式存储结构 20． 2i-1 2k-1 21．-1、O、122．右 23．稀疏图24．nm／2 25．散列文件索引文件26．外排序 27．循环链表28．O(log2n)三、应用题29．解：首先统计每个字符出现的次数，有8个字符一共22次I:5，R:2，H:3，S:5，T:3，O:2，C:1，Y:l然后8个字符对应8个叶子结点，根据出现次数，每次找两个最小的结点合并成一个结点，逐次把森林连成一棵二叉树。
30. 解30 22 25 18 40 12 34 4022 25 18 30 12 34 40 4022 18 25 12 30 34 40 4018 22 12 25 30 34 40 4018 12 22 25 30 34 40 4012 18 22 25 30 34 40 4012 18 22 25 30 34 40 4031．解后根序列46532132．解struct node *lcopy(struct node *P){struct node *head=0，*tail=O；while(p){struct node *t=malloc(sizeof(struct node))；t->data=p->data；t->next=O；if(tail)tail->next=t；tail=t；P=P->next；if(head==O)head=t；}return head；}33．解四、算法设计题34．解因为当front==rear时，不知道是空还是满。
改进设计，可以在结构中添加一个整数变量，用以记录当前队列中元素个数。
typedef struct{DataType data[maxsize]；int front，rear；int count；//记录当前队列中的元素个数}可以从count判断是满还是空，如果满了则不能加入队列元素，如果空了则不能移除队列元素，其他时候和以前的操作一样。
2014年4⽉⾃考数据结构导论试题及答案全国2014年4⽉⾼等教育⾃学考试数据结构导论试题课程代码：02142请考⽣按规定⽤笔将所有试题的答案涂、写在答题纸上。
选择题部分注意事项：1.答题前，考⽣务必将⾃⼰的考试课程名称、姓名、准考证号⽤⿊⾊字迹的签字笔或钢笔填写在答题纸规定的位置上。
2.每⼩题选出答案后，⽤2B铅笔把答题纸上对应题⽬的答案标号涂⿊。
如需改动，⽤橡⽪擦⼲净后，再选涂其他答案标号。
不能答在试题卷上。
⼀、单项选择题(本⼤题共15⼩题，每⼩题2分，共30分)在每⼩题列出的四个备选项中只有⼀个是符合题⽬要求的，请将其选出并将“答题纸”的相应代码涂⿊。
错涂、多涂或未涂均⽆分。
1.下列⼏种算法时间复杂度中，最⼩的是( A )A.O(log2n)B.O(n)C.O(n2)D.O(1)2.数据的存储⽅式中除了顺序存储⽅式和链式存储⽅式之外，还有( D )A.索引存储⽅式和树形存储⽅式B.线性存储⽅式和散列存储⽅式C.线性存储⽅式和索引存储⽅式D.索引存储⽅式和散列存储⽅式3.表长为n的顺序表中做删除运算的平均时间复杂度为( C )A.O(1)B.O(log2n)C.O(n)D.O(n2)4.顺序表中定位算法(查找值为x的结点序号最⼩值)的平均时间复杂度为( C )A.O(1)B.O(log2n)C.O(n)D.O(n2)5.元素的进栈次序为A，B，C，D，E，出栈的第⼀个元素为E，则第四个出栈的元素为( C )A.D6.带头结点的链队列中，队列头和队列尾指针分别为front和rear，则判断队列空的条件为( A )A.front==rearB.front!=NULLC.rear!==NULLD.front==NULL7.深度为5的⼆叉树，结点个数最多为( A )A.31个B.32个C.63个D.64个8.如果结点A有2个兄弟结点，结点B为A的双亲，则B的度为( B )A.1B.3C.4D.59.将题9图所⽰的⼀棵树转换为⼆叉树，结点C是( D )A.A的左孩⼦B.A的右孩⼦C.B的右孩⼦D.E的右孩⼦10.n为图的顶点个数，e为图中弧的数⽬，则图的拓扑排序算法的时间复杂度为( D )A.O(n)B.O(e)C.O(n-e)D.O(n+e)11.⽆向图的邻接矩阵是( D )A.对⾓矩阵B.稀疏矩阵C.上三⾓矩阵D.对称矩阵12.在具有101个元素的顺序表中查找值为x的元素结点时，平均⽐较元素的次数为( A )D.10113.构造散列函数的⽅法很多，常⽤的构造⽅法有( D )A.数字分析法、除留余数法、平⽅取中法B.线性探测法、⼆次探测法、除留余数法C.线性探测法、除留余数法、链地址法D.线性探测法、⼆次探测法、链地址法14.就平均时间性能⽽⾔，快速排序⽅法最佳，其时间复杂度为( B )A.O(n)B.O(nlog2n)C.O(n2)D.O(1og2n)15.下述算法中，不稳定的排序算法是( C )A.直接插⼊排序B.冒泡排序C.堆排序D.归并排序⾮选择题部分注意事项：⽤⿊⾊字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。
2016年10月高等教育自学考试全国统一命题考试数据结构导论试卷(课程代码 02142)本试卷共4页，满分l00分，考试时间l50分钟。
考生答题注意事项：1．本卷所有试题必须在答题卡上作答。
答在试卷上无效，试卷空白处和背面均可作草稿纸。
2．第一部分为选择题。
必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。
3．第二部分为非选择题。
必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。
4．合理安排答题空间。
超出答题区域无效。
第一部分选择题(共30分)一、单项选择题(本大题共10小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡”的相应代码涂黑。
错涂、多涂或未涂均无分。
1．已知问题规模为n，则下列程序片段的时间复杂度是C2．若用计算机来模拟银行客户排队等待办理业务的情形，则所应该采用的数据结构是A．栈 B．队列 C．树 D．图3．若线性表采用链式存储结构，则适用的查找方法为A．随机查找 B．散列查找 C．二分查找 D．顺序查找4．已知指针P和q分别指向某单链表中第一个结点和最后一个结点，假设指针s指向另一个单链表中某个结点，则在S所指结点之后插入上述单链表应执行的语句为A．q→next；s→next；s→next2P； B．s→next=P；q→next=s→next；C．p→next=s→next；s→next=q； D．s→next2q；p→next2s→next；5．栈的运算特点是先进后出，元素a、b、c、d依次入栈，则不能得到的出栈序列是A．abed B．dcba C．cabd D．bcda6．在实现队列的链表结构中，其时间复杂度最优的是A．仅设置头指针的单循环链表 B．仅设置尾指针的单循环链表C．仅设置头指针的双向链表 D．仅设置尾指针的双向链表7．任意一棵二叉树的前序和后序遍历的结果序列中，各叶子结点之间的相对次序关系是A．不一定相同 B. 都相同 C．都不相同 D．互为逆序8．若某棵树的存储结构采用双亲表示法，如题8图所示，则该树的高度是A．2 B．3 C．4 D．59．无向图的邻接矩阵一定是A．对称矩阵 B．对角矩阵 C．稀疏矩阵 D．三角矩阵10．根据连通图的深度优先搜索的基本思想，如题10图所示的连通图的一个深度优先搜索的结果序列是A．123456 B．123465 C. 126345 D．16254311．用顺序查找方法对含有n个数据元素的顺序表按从后向前查找次序进行查找，现假设查找其中每个数据元素的概率不相等，那么A．该顺序表按查找概率由低到高的顺序来存储数据元素，其ASL最小B．该顺序表按查找概率由高到低的顺序来存储数据元素，其ASL最小C．ASL的大小与数据元素在该顺序表中的位置次序无关D．ASL的大小与查找每个数据元素的概率无关12．已知散列表的存储空间为T[0，…，l6]，散列函数为H(k)----k mod l7，用二次探测法解决冲突。
全国2012年1月 数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 1.结点按逻辑关系依次排列形成一条“锁链”的数据结构是( )A.集合 B.线性结构 C.树形结构 D.图状结构 2.下面算法程序段的时间复杂度为( ) for ( int i=0; ifor ( int j=0; ja［i］［j］=i*j; A. O(m2) B. O(n2) C. O(mn) D. O(m+n) 3.线性结构是( )A.具有n（n≥0）个表元素的有穷序列 B.具有n（n≥0）个字符的有穷序列 C.具有n（n≥0）个结点的有穷序列 D.具有n（n≥0）个数据项的有穷序列 4.单链表中删除由某个指针变量指向的结点的直接后继，该算法的时间复杂度是( ) A. O(1) B. O(n) C. O(log2n) D. O(n) 5.关于串的叙述，正确的是( ) A.串是含有一个或多个字符的有穷序列 B.空串是只含有空格字符的串 C.空串是含有零个字符或含有空格字符的串 D.串是含有零个或多个字符的有穷序列 6.栈的输入序列依次为1，2，3，4，则不可能的出栈序列是( )A.1243 B. 1432 C. 2134 D.4312 7.队列是( )A. 先进先出的线性表 B. 先进后出的线性表 C. 后进先出的线性表 D.随意进出的线性表 8.10阶上三角矩阵压缩存储时需存储的元素个数为( ) A.11 B.56 C.100 D.101 9.深度为k（k≥1）的二叉树，结点数最多有( )A.2k 个 B.(2k -1)个 C.2k-1个 D.(2k+1)个 10.具有12个结点的二叉树的二叉链表存储结构中，空链域NULL的个数为( )A. 11 B.13 C. 23 D. 25 11.具有n个顶点的无向图的边数最多为( )A.n+1 B.n(n+1) C.n(n-1)/2 D.2n(n+1)
12.三个顶点v1,v2,v3的图的邻接矩阵为010001010，该图中顶点v3的入度为( )A. 0 B. 1 C. 2 D.
3 13.顺序存储的表格中有60000个元素，已按关键字值升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字值不相同。用顺序查找法查找时，平均比较次数约为( )A.20000 B.30000 C.40000 D.60000 14.外存储器的主要特点是( ) A.容量小和存取速度低 B.容量大和存取速度低 C.容量大和存取速度高 D.容量小和存取速度高 15.在待排数据基本有序的前提下，效率最高的排序算法是()A.直接插入排序 B.直接选择排序C.快速排序D.归并排序 二、填空题(本大题共13小题，每小题2分，共26分) 16.数据的不可分割的最小标识单位是______，它通常不具有完整确定的实际意义，或不被当作一个整体对待。 17.运算分为加工型运算和引用型运算，读取操作是______ 运算。 18.带有头结点的单向循环链表L（L为头指针）中，指针p所指结点为尾结点的条件是 ______。 19.在双链表中，前趋指针和后继指针分别为prior和next。若使指针p往后移动两个结点，则需执行语句 ______。 20.元素s1，s2，s3，s4，s5，s6依次进入顺序栈S，如果6个元素的退栈顺序为s2，s3，s4，s6，s5，s1，则顺序栈的容量至少为 ______。 21. 稀疏矩阵一般采用的压缩存储方法是______ 。 22. 在一棵树中，______ 结点没有双亲。 23.一棵具有n个结点的完全二叉树中，从树根起，自上而下、自左至右给所有结点编号。设根结点编号为1，若编号为i的结点有父结点，那么其父结点的编号为 ______。 24.二叉树的二叉链表存储结构中判断指针p所指结点为叶子结点的条件是______。 25.边稀疏的无向图采用 ______存储较省空间。 26.除第一个顶点和最后一个顶点相同外，其余顶点不重复的回路，称为 ______。 27.二分查找算法的时间复杂度是 ______。 28.要将序列{51，18，23，68，94，70，73}建成堆，则只需把18与 ______相互交换。 三、应用题(本大题共5小题，每小题6分，共30分) 29.将题29图所示的一棵二叉树转换成对应的森林。
题29图 题31图 题32图 30.给定权值｛3，9，13，5，7｝，构造相应的哈夫曼（Huffman）树，并计算其带权路径长度。 31.写出题31图的邻接矩阵和每个顶点的入度与出度。 32. 二叉排序树的各结点的值依次为20~28，请在题32图中标出各结点的值。 33.用冒泡排序法对数据序列（55，38，65，97，76，138，27，49）进行排序，写出排序过程中的各趟结果。 四、算法设计题(本大题共2小题，每小题7分，共14分) 34.设线性表A =（a1， a2， …,am），B=（b1, b2, …,bn），试写一个按下列规则合并A，B为线性表C的算法，使得 C=（a1, b1, …, am ,bm ,bm+1, …,bn） 当m≤n时； 或者 C=（a1, b1, …, an ,bn ,an+1, …,am） 当m>n时。 线性表A，B和C均以带头结点的单链表作为存储结构，且C表利用A表和B表中的结点空间构成。（注意：单链表的长度值m和n均未显式存储。） 35. 二叉树的二叉链表类型定义如下： typedef struct btnode { datatype data; struct btnode *lchild,*rchild; } bitreptr; 写出后根遍历根指针为t的二叉树的递归算法( void postorder (bitreptr *t) )。 全国2011年10月 数据结构导论试题 课程代码:02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 1.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，元素退栈后即进入队列Q，若6个元素的出队序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少为( )A.2 B.3 C.4 D.6 2.设计一个判别表达式中左右括号是否配对出现的算法，采用的最佳数据结构为( ) A.线性表的顺序存储结构 B.队列 C.线性表的链式存储结构 D.栈 3.下列程序段的时间复杂度为( ) i=0；s=0； while（sA.O（n） B.O(log2n) C.O(n) D.O(n2) 4.设A是n×n的对称矩阵，将A的对角线及对角线上方的元素Aij(1≤i,j≤n,i≤j)以列优先顺序存放在一维数组元素B［1］至B［n(n+1)/2］中，则元素Aij(i≤j)在B中的位置为( ) A.i(i-l)/2+j B.j(j-l)/2+i C.j(j-l)/2+i-1 D.i(i-l)/2+j-1 5.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是( ) A.G中有弧 B.G中有一条从Vi到Vj的路径 C.G中没有弧 D.G中有一条从Vj到Vi
的路径
6.下列序列中，由第一趟快速排序可得到的序列（排序的关键字类型是字符串）是( ) A.［da，ax，eb，de，bb］ff［ha，gc］ B.［cd，eb，ax，da］ff［ha，gc，bb］ C.［gc，ax，eb，cd，bb］ff［da，ha］ D.［ax，bb，cd，da］ff［eb，gc，ha］ 7.不稳定的排序方法是( )A.直接插入排序 B.冒泡排序 C.堆排序 D.二路归并排序 8.设散列表表长m=14，散列函数为h（k）=k%11，表中已有4个记录，如果用二次探测法处理冲突，关键字为49的记录的存储位置是( ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 15 38 61 84 A.3 B.5 C.8 D.9 9.若元素1，2，3依次进栈，则退栈不可能出现的次序是( ) A.3，2，1 B.2，1，3 C.3，1，2 D.1，3，2 10.直接插入排序的时间复杂度是( )A.O（n2） B.O（nlog2n） C.O（n） D.O（log2n） 11.稀疏矩阵是指( ) A.元素少的矩阵 B.有少量零元素的矩阵 C.有少量非零元素的矩阵 D.行数、列数很少的矩阵 12.深度为k（k≥1）的二叉树，结点数最多有( )A.2k B.2k-1 C.2k-1 D.2k-1-1 13.由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为( )A.23 B.37 C.44 D.46 14.有n个顶点的有向完全图的弧数为( )A.n2 B.2n C.n（n-1） D.2n（n+1） 15.图的深度优先搜索类似于二叉树的( )A.先根遍历 B.中根遍历 C.后根遍历 D.层次遍历 二、填空题(本大题共13小题，每小题2分，共26分) 16.下列程序段的时间复杂度为_________。 for(i=1;i<=n;i++) for(j=1;j<=n;j++) x++; 17.数据结构中结点按逻辑关系依次排列形成一条“锁链”的结构是_________。 18.在表长为n的顺序表上做删除运算，平均要移动的结点个数为_________。 19.在带有头结点的单循环链表head中，指针p所指结点为尾结点的条件是_________。 20.队列又称为_________的线性表。 21.顺序栈被定义为结构类型，含有两个域：data和top，则对栈*sq进行初始化的操作是_________。 22.对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n2=_________。 23.一棵具有n个结点的二叉树，采用二叉链表存储，则二叉链表中指向孩子结点的指针有_________个。 24.若连通图G的顶点个数为n，则图G的生成树的边数为_________。 25.一个具有n个顶点的无向图的边数最多为_________。 26.中根遍历二叉排序树所得到的结点访问序列是键值的_________序列。 27.冒泡排序的平均时间复杂度为_________。 28.将序列{60，20，23，68，94，70，73}建成堆，则只需把20与_________互相交换。 三、应用题(本大题共5小题，每小题6分，共30分) 29.如题29图所示，在栈的输入端元素的输入顺序为A，B，C，D，进栈过程中可以退栈，写出在栈的输出端以A开头和以B开头的所有输出序列。
题29图 题30图 题31图 题32图 30.一棵二叉树如题30图所示，写出该二叉树的先根遍历序列、中根遍历序列和后根遍历序列。 31.将题31图所示的一棵二叉树转换成森林。 32.对于有向无环图： （1）叙述求拓扑排序算法的基本步骤； （2）对于题32图，写出它的4个不同的拓扑排序序列。 33.判别以下序列是否为堆。如果不是，则把它调整为堆。 （1）（100，86，48，73，35，39，42，57，66，21）；（2）（12，70，33，65，24，56，48，92，86，33）。 四、算法设计题(本大题共2小题，每小题7分，共14分) 34.n个结点的完全二叉树按结点编号将值顺序存放在一维数组元素A［1］至A［n］中，试编写算法实现将顺序存储结构转换为二叉链表存储结构，其中根结点由tree指向。 35.试写出冒泡排序算法。
