浙江省2002年1月高等教育自学考试数据结构导论试题
课程代码：02142
一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。每小题1分，共14分)
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.以顺序方式存储
 &nb来源:91exam .orgsp; 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

二、判断题(判断下列各小题，正确的在题后括号内打“√”，错的打“╳”。每小题2分，共20分)
1.算法和程序没有区别，所以在数据结构中二者是通用的。(      )

2.在顺序表中无需为表示结点间的逻辑关系而增加存储空间。(      )

3.单链表中的头结点就是单链表的第一个结点。(      )

4.队列和栈都是运算受限的线性表。(      )

5.任何一棵二叉树中至少有一个结点的度为2。(      )

6.散列技术可用于表示并实现动态查找表。(      )

7.对于同一组结点，由于建立二叉排序树时插入结点的先后次序不同，所构成的二叉排序树的形态及深度也不同，所以含有n个结点的二叉排序树不唯一。(      )

8.在磁带上的顺序文件中插入新的记录时，必须复制整个文件。(      )

9.插入排序是稳定的，而直接选择排序是不稳定的。(      )

10.对于n个记录的集合进行冒泡排序，所需要的平均时间是0(n)。(      )

三、填空题(每小题2分，共30分)
1.通常从四个方面评价算法的质量：_________、_________、_________和_________。

2.字符串的逻辑结构为：_________。

3.设head为单链表的头结点，则判断单链表为空的条件是：_________。

4.在具有n个单元的循环队列中，队满时共有_________个元素。

5.矩阵压缩存储的基本思想是：_________的多个元素只分配一个存储空间，_________不分配空间。

6.树的三种常用存储结构是：孩子链表表示法、_________和_________。

7.深度为K的完全二叉树至少有_________个结点，至多有_________个结点。

8.图的主要存储结构有两种，分别为：_________和_________。

9.二叉排序树上，结点的平衡因子定义为该结点_________子树的高度减去该结点_________子树的高度。

10.散列技术既是一种_________方式，又是一种_________方法。

11.在索引非顺序文件中，记录不按关键字顺序排列，因此对每个记录要建立一个索引项，这样的索引表称为_________索引。

12.文件的修改包括：_________、_________和更新记录三种操作。

13.与磁带存储器相比，磁盘存储器的优点是存取速度快，既适应于_________存取，又适应于_________存取。

14.直接插入排序需要_________个记录的辅助空间。

15.在插入和选择排序中，若初始数据基本正序，则选用_________；若初始数据基本反序，则选用_________。