全国2011年10月高等教育自学考试

数据结构试题

课程代码：02331

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

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

1、在数据的逻辑结构中，树结构和图结构都是（   ）

A.非线性结构                                            B.线性结构

C.动态结构                                                D.静态结构

2.在一个长度为n的顺序表中插入一个元素的算法的时间复杂度为（   ）

A.O（1）                                                  B.Ｏ（log n）      

C.O（n）                                                  D.O（n²）

3.指针p1和p2分别指向两个无头结点的非空单循环链表中的尾结点，要将两个链表链接成一个新的单循环链表，应执行的操作为（   ）

A.p1－＞next=p2－＞next;p2－＞next=p1－＞next;

B. p2－＞next=p1－＞next;p1－＞next=p2－＞next;

C. p=p2－＞next; p1－＞next=p;p2－＞next=p1－＞next;

D. p=p1－＞next; p1－＞next= p2－＞next；p2－＞next=p;

4.设栈的初始状态为空，入栈序列为1，2，3，4，5，6，若出栈序列为2，4，3，6，5，1，则操作过程中栈中元素个数最多时为（   ）

A.2个                                                         B.3个

C.4个                                                         D.6个

5.队列的特点是（   ）

A.允许在表的任何位置进行插入和删除

B.只允许在表的一端进行插入和删除

C.允许在表的两端进行插入和删除

D.只允许在表的一端进行插入，在另一端进行删除

6.一个链串的结点类型定义为

﹟define NodeSize  6

typedef struct node{

      char data[NodeSize];

      struct node*next;

}LinkStrNode;

如果每个字符占1个字节，指针占2个字节，该链串的存储密度为（   ）

A.1/3                                                            B.1/2

C.2/3                                                             D.3/4

7.广义表A=（a,B,(a,B,(a,B,……）））的长度为（   ）

A.1                                                               B.2 

C.3                                                               D.无限值

8.已知10×12的二维数组A，按“行优先顺序”存储，每个元素占1个存储单元，已知A[1][1]的存储地址为420，则A[5][5]的存储地址为（   ）

A.470                                                            B.471                   

C.472                                                            D.473

9.在一棵二叉树中，度为2的结点数为15，度为1的结点数为3，则叶子结点数为（   ）

A.12                                                             B.16                           

C.18                                                              D.20

10.在带权图的最短路径问题中，路径长度是指（   ）

A.路径上的顶点数                                        B.路径上的边数

C.路径上的顶点数与边数之和                       D.路径上各边的权值之和

11.具有n个顶点、e条边的无向图的邻接矩阵中，零元素的个数为（   ）

A.e                                                              B.2e

C.n²-2e                                                       D.n²-1

12.要以O（n log n）时间复杂度进行稳定的排序，可用的排序方法是（   ）

A.归并排序                                                 B.快速排序

C.堆排序                                                     D.冒泡排序

13.若希望在1000个无序元素中尽快求得前10个最大元素，应借用（   ）

A.堆排序                                                     B.快速排序                 

C.冒泡排序                                                 D.归并排序

14.对有序表进行二分查找成功时，元素比较的次数（   ）

A.仅与表中元素的值有关                            B.仅与表的长度和被查元素的位置有关

C.仅与被查元素的值有关                            D.仅与表中元素按升序或降序排列有关

15.散列文件是一种（   ）

A.顺序存取的文件                                       B.随机存取的文件

C.索引存取的文件                                       D.索引顺序存取的文件

二、填空题（本大题共10小题，每小题2分，共20分）

请在每小题的空格中填上正确答案。错填、不填均无分。

16.若一个算法中的语句频度之和为T（n）=3n³-200nlog₂n+50n，则该算法的渐近时间复杂度为__________.

17.在单链表中，除了第1个元素结点外，任一结点的存储位置均由_____________指示。

18.栈的修改是按__________的原则进行。

19.字符串中任意个连续的字符组成的子序列称为该串的__________。

20.假设一个10阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，若矩阵中的第一个元素a₁₁在B中的存储位置k=0，则元素a₅₅在B中的存储位置k=__________。

21.在一棵具有n个结点的严格二叉树中，度为1的结点个数为__________。

22.对于稀疏图，采用__________表示法较为节省存储空间。

23.在排序过程中，如果_____________，则称其为外部排序。

24.设有一组记录的关键字为｛19，14，23，1，68，12，10，78，25｝，用链地址法构造散列表，散列函数为h（key）=key％11,散列地址为1的链中有__________个记录。

25.多关键字文件的特点是除主文件和主索引外，还建有__________。

三、解答题（本大题共4小题，每小题5分，共20分）

26.对于下列稀疏矩阵（注：矩阵元素的行列下标均从1开始）