2007年10月高等教育自学考试全国统一命题考试

数据结构     试卷

(课程代码  2331)

本试卷共12页，满分100分；考试时间150分钟。

一、单项选择题(本大题共15小题，每小题2分，共30分)

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1．下面程序段的时间复杂度为

  A．O(1)                             B．O(log n)    

C．O(n)                             D．O(n²)

2．已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在8所指结点之后插入上述链表应执行的语句为    【  】

3．在计算机内实现递归算法时所需的辅助数据结构是    【    】

  A．栈                               B．队列    

C．树                               D．图

4．假设以数组A[m]存放循环A[m]的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置。则队头元素所在的存储位置为    【    】

5．通常将链串的结点大小设置为大于l是为了    【    】

  A．提高串匹配效率                   B．提高存储密度

  C．便于插入操作                     D．便于删除操作

6．带行表的三元组表是稀疏矩阵的一种    【    】

  A．顺序存储结构                     B．链式存储结构

  C．索引存储结构                     D．散列存储结构

7．表头和表尾均为空表的广义表是    【    】

  A．( )                               B．( ( ) )    

C．( ( ( ) ) )                          D．( ( )，( ) )

8．用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为    【    】

  A．n-1                              B．n  

 C．n+l                              D．2n    

9．为便于判别有向图中是否存在回路，可借助于       【    】

   A．广度优先搜索算法                B．最小生成树算法

   C．最短路径算法                    D．拓扑排序算法

10．连通网的最小生成树是其所有生成树中    【    】

   A．顶点集最小的生成树              B．边集最小的生成树

   C．顶点权值之和最小的生成树        D．边的权值之和最小的生成树

11．按排序过程中依据的原则分类，快速排序属于    【    】

   A．插入类的排序方法                B．选择类的排序方法

   C．交换类的排序方法                D．归并类的排序方法

12．下列关键字序列中。构成小根堆的是    【    】

   A．{84，46，62，41，28，58，15，37}

   B．{84，62，58，46，4l，37，28，15}

   C．{15，28，46，37，84，41，58，62}

   D．{15，28，46，37，84，58，62，41}

13．在长度为32的有序表中进行二分查找时，所需进行的关键字比较次数最多为    【  】

A．4                               B．5    

C．6                               D．7    

14．假设在构建散列表时，采用线性探测解决冲突。若连续插入的n个关键字都是同义词，则查找其中最后插入的关键字时，所需进行的比较次数为    【    】

A．n-1                              B．n    

C．n+l                              D．n+2

15．散列文件也称为        【   】

   A．顺序文件                       B．索引文件

   C．直接存取文件                     D．间接存取文件

自考相关信息与资料关注:重庆自考网