​数据结构自考2011年10月真题

数据结构自考2011年10月真题及答案解析

本试卷为单选题型，填空题，算法阅读，算法设计等题型。

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

1.在数据的逻辑结构中，树结构和图结构都是(　　)

A.非线性结构
B.线性结构
C.动态结构
D.静态结构

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

A.O(1)
B.O( )
C.O(n)

D.

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 6typedef 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.已知10x12的二维数组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.

D.

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分) 请在每小题的空格中填上正确答案。错填、不填均无分。

11.若一个算法中的语句频度之和为 ，则该算法的渐近时间复杂度为 。

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

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

14.字符串中任意个连续的字符组成的予序列称为该串的 。

15.假设一个10阶的上三角矩阵A按z…--…-顺I序压缩存储在一维数组B中，若矩阵中的第一个元素a1，1在B中的存储位置k=O，则元素a5，5在B中的存储位置k=

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

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

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

19.设有一组记录的关键字为{19，14，23，1，68，12，10，78，25}，用链地址法构造散列表，散列函数为h(key)=key%11，散列地址为1的链中有 个记录。

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

三、解答题(本大题共4小题，每小题5分，共20分)

21.对于下列稀疏矩阵(注：矩阵元素的行列下标均从1开始)(1)画出三元组表;(2)画出三元组表的行表。

22.已知一个森林的前序遍历序列为CBADHEGF，后序遍历序列为ABCDEFGH。(1)画出该森林;(2)画出该森林所对应的二叉树。

23.对关键字序列(429，653，275，897，170，908，473，256，726)进行基数排序，写出每一趟的排序结果。

24.对下列关键字序列 (87，25，310，08，27，132，68，96，187，133，70，63，47，135)构造散列表，假设散列函数为h(key)=key%13，用拉链法解决冲突。(1)画出该散列表;(2)求等概率情况下查找成功的平均查找长度ASL;(3)写出删除值为70的关键字时所需进行的关键字比较次数。

四、算法阅读题(本大题共4小题，每小题5分，共20分)

31.阅读下列算法，并回答问题：(1)假设p(3，7，7，11，20，20，20，51，51)，写出执行函数=f30(&L)后的L.(2)简述f30的功能。

32.阅读下列算法，并回答问题：(1)假设栈S=(3，8，6，2，5)，其中5为栈顶元素，写出执行函数f3l(&S)后的S;(2)简述函数f31的功能。void f31(Stack*S){ Queue Q;InitQueue(&Q);while(!StackEmpty(S))EnQueue(&Q，Pop(&S));while(!QueueEmpty(Q))Push(&S，DeQueue(&Q));}

33.假设具有n个结点的完全二叉树顺序存储在向量BT[ 1..n]中，阅读下列算法，并回答问题：(1)若向量BT为：      1 2 3 4 5 6 7画出执行函数f32(BT，7，1)的返回结果;(2)简述函数f32的功能。BinTree f32(DataType BT[]，intn，inti){BinTree p;if(i>n)return NULL;p=(BinTNode*)malloc(sizeof(BinTNode));p->data=BT[i];p->lchild=f32(BT,n，i*2);p->rchild=f32(BT，n，i*2+1);return p;}

34.已知有向图的邻接表和邻接矩阵定义如下：#define MaxNum 50 图的最大顶点数typedef struct node{int adjvex; ∥邻接点域struct node半next; ∥链指针域}EdgeNode; ∥边表结点结构typedef struct{char vertex; ∥顶点域EdgeNode *frrstedge; ∥边表头指针}VertexNode; ∥顶点表结点结构typedef struct{VertexNode adjlist[MaxNum]; ∥邻接表int n，e; ∥图中当前顶点数和边数}ALGraph; ∥邻接表描述的图typedef struct{char vertex[MaxNum]; ∥顶点表int adjmatrix[MaxNum][MaxNum]; ∥邻接矩阵int n，e; ∥图中当前顶点数和边数}AMGraph; ∥邻接矩阵描述的图下列算法是将邻接表描述的图Gl改为邻接矩阵描述的图G2趁，在空白处填上适当内 容使算法完整： 

五、算法设计题(本大题共1小题，共10分)

41.设顺序表L是一个递增有序表。编写算法，要求利用二分查找法确定插入位置，将元素x插入到L中，使L保持有序。