数据结构习题课.doc

《数据结构习题课.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、复习重点1.数据结构的概念，逻辑结构、物理结构的概念及各自包含的内容2.算法的特性、设计要求，如何度量算法的时间效率。3.线性表的顺序/链式存储结构的特点，插入、删除算法。4.栈和队列的逻辑特性，顺序栈的入栈/出栈、循环队列的入队/出队算法。5.以三元组顺序表存放的稀疏矩阵的转置算法。6.二叉树的性质及其四种遍历算法。7.森林与二叉树的相互转换。8.WPL、前缀编码的概念，哈夫曼树的构造算法。9.图的相关概念，邻接矩阵及邻接表的存储结构。10.图的深度优先/广度优先遍历算法。11.最小生成树的两种算法。12.拓扑排序的意义

2、和算法。13.最短路径算法。14.顺序表、有序表的查找算法。15.二叉排序树的性质、插入/删除算法、平衡二叉树的性质、插入算法。16.哈希表的相关概念，常用的冲突处理方法。17.直接插入排序、希尔排序、快速排序、堆排序、归并排序的算法。注意：1.上述每个知识点可能会以任何题型出现，复习的时候别把它们当做“简答题”来复习。2.红色（下划线）标识的知识点或算法，只要求对给出的初始数据，能画出结果则可。其他的算法则可能会出现在“算法题”中。自测题第1章绪论一、判断1.顺序存储方式只能用于存储线性结构。（错）2.顺序查找法适用于存

3、储结构为顺序或链式存储的线性表。（对）二、选择1.计算机算法必须具备输入、输出、（B）等5个特性。A.可行性、可移植性和可扩展性B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、安全性和稳定性1.算法在发生非法操作时可以作出处理的特性称为（C）。A.正确性B.易读性C.健壮性D.可靠性2.数据结构是一门研究非数值计算的程序设计问题中计算机的（A）以及它们之间的（B）和运算的学科。A.操作对象B.计算方法C.逻辑存储D.数据映像A.结构B.关系C.运算D.算法3.在数据结构中，逻辑上数据结构可分为：（B）A.动

4、态结构和静态结构B.线性结构和非线性结构C.紧凑结构和非紧凑结构D.内部结构和外部结构4.数据结构主要研究数据的（D）A.逻辑结构B.存储结构C.逻辑结构和存储结构D.逻辑结构和存储结构及其运算的实现5.为了描述n个人之间的同学关系，可用（C）结构表示A.线性表B.树C.图D.队列6.下面的程序段违反了算法的（A）原则voidsam(){intn=2;while(!odd(n))n+=2;printf(n);}A.有穷性B.确定性C.可行性D.健壮性三、问答1.什么是逻辑结构和物理结构？各自包含哪几种？2.线性结构和树型结

5、构的特点分别是什么？3.简述顺序存储结构与链式存储结构在表示数据元素之间关系上的只要区别。4.简述算法的5个特性。第2章线性表一、选择1.线性表是具有n个（C）的有限序列A.表元素B.字符C.数据元素D.数据项E.信息项2.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（A）A.nB.2n-1C.2nD.n-13.下述哪一条是顺序存储结构的优点？（A）A．物理上相邻的元素在逻辑上也相邻B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示1.下面关于线性表的叙述中，错误的是哪一个？（B）A．

6、线性表采用顺序存储，必须占用一段连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链式存储，不必占用一片连续的存储单元。D．线性表采用链式存储，便于进行插入和删除操作。2.指针P所指的元素是双向循环链表L的尾元素的条件是（D）A.P=LB.P=NULLC.P->Link=LD.P->Rlink=L3.在一个单链表中删除P结点的后继结点的语句是（　A）A.p->next=p->next->nextB.p=p->next；p->next=p->next->next;C.p->next=p->next

7、;D.p=p->next->next;4.循环链表的主要优点是（D）A.不再需要头指针了B.已知某个结点的位置后，能很容易找到它的直接前驱结点C.在进行删除操作后，能保证链表不断开D.从表中任一结点出发都能遍历整个链表二、问答1.在非空双向循环表中q所指的结点后面插入p所指的结点的语句是？2.循环队列为满和空时的条件。3.若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？为什么？4.设单链表中结点的数据域为data，指针域为next，指针p为表中某一结点的地址，请写出在p结点之前插入一个s结点的C语言描

8、述语句。第3章栈和队列一、选择1.PUSH和POP命令常用于（C）操作A.队列B.数组C.栈D.记录2.判断一个表达式中左右括号是否匹配，采用（D）实现较为方便A.线性表的顺序存储B.队列C.线性表的链式存储D.栈3.用单链表表示的链式队列的对头在链表的（A）位置A.链头B.链尾C.链中4.设栈的输入序