数据结构复习题29页.doc

数据结构复习题 简答题 抽象数据类型是如何定义的，写出一个ADT的描述 数据的存储结构可用哪四种基本的存储方法得到 简述单链表的概念 画出在单链表上插入和删除结点的示意图 试比较顺序表和链表的优缺点 二叉树是如何定义的，有何性质 什么是遍历 无向图与有向图的度是如何定义的 简述选择排序的基本思想 二分查找的基本思想是什么 一、单项选择题 1.计算机算法指的是( )。 A.计算方法 B.排序方法 C.解决某一问题的有限运算序列 D.调度方法 2.在一个单链表中，若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; D. p↑.next:=s;s↑.next=p; 3.某个向量第一元素的存储地址为100，每个元素的长度为2，则第五个元素的地址是( )。 A.110 B.108 C.100 D.120 4.循环队列用数组A［0..m-1］存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是( )。 A.(rear-front+m) MOD m B.rear-front+1 C.rear-front-1 D.rear-front 5.栈和队列的共同特点是( )。 A.都是先进后出 B.都是先进先出 C.只允许在端点处插入和删除元素 D.没有共同点 6.深度为n的二叉树中所含叶子结点的个数最多为( )个。 A.2n B.n C.2n-1 D.2n-1 7.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 8.下面的二叉树中，( )不是完全二叉树。 9.下列说法错误的是( )。 A.一个图的邻接矩阵表示是唯一的 B.一个图的邻接表表示是不唯一的 C.一个图的生成树必为该图的极小连通子图 D.一个无环有向图的拓扑排序序列必唯一 10.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 11.对线性表进行二分查找时，要求线性表必须( )。 A.以顺序方式存储 B.以链接方式存储 C.以顺序方式存储，且结点按关键字有序排序 D.以链接方式存储，且结点按关键字有序排序 12.直接存取文件的特点是( )。 A.记录按关键字排序 B.记录可以进行顺序存取 C.存取速度快，但占用较多的存储空间 D.记录不需要排序，存取效率高 13.文件存储的基本单位是( )。 A.记录 B.数据项 C.属性 D.关键字 14.一组记录的排序码为(47、78、61、33、39、80)，则利用堆排序的方法建立的初始堆为( )。 A.78、47、61、33、39、80 B.80、78、61、33、39、47 C.80、78、61、47、39、33 D.80、61、78、39、47、33 二、判断题 1.算法和程序没有区别，所以在数据结构中二者是通用的。( ) 2.在顺序表中无需为表示结点间的逻辑关系而增加存储空间。( ) 3.单链表中的头结点就是单链表的第一个结点。( ) 4.队列和栈都是运算受限的线性表。( ) 5.任何一棵二叉树中至少有一个结点的度为2。( ) 6.散列技术可用于表示并实现动态查找表。( ) 7.对于同一组结点，由于建立二叉排序树时插入结点的先后次序不同，所构成的二叉 排序树的形态及深度也不同，所以含有n个结点的二叉排序树不唯一。( ) 8.在磁带上的顺序文件中插入新的记录时，必须复制整个文件。( ) 9.插入排序是稳定的，而直接选择排序是不稳定的。( ) 10.对于n个记录的集合进行冒泡排序，所需要的平均时间是0(n)。( ) 三、填空题 1.通常从四个方面评价算法的质量：_________、_________、_________和____