数据结构导论2014年10月真题及答案解析（02142）

假设线性表中结点是按键值递增的顺序排列，试编写一个顺序查找算法，将岗哨设在高下标端。并说明等概率情况下查找成功和不成功时的平均查找长度。

单链表的结构定义如下：

typedef struct node

{ int data;

   struct node *next;

}Node, *LinkList;

试编写算法int CountLinklist(LinkList head,int x)实现在带头结点的单链表head中计算值为x的结点数。

判断序列(28，75，33，68，25，56，47，99，86，36)是否为堆?如果不是，则把它调整为堆(最小堆)。

将题32图所示的一棵树转换为二叉树。

分别写出题30图所示二叉树的先序遍历、中序遍历和后序遍历的结点序列。

写出题31图所示有向图顶点的所有拓扑排序序列。

最好情况下，冒泡排序算法的时间复杂度为_______，它是一种稳定的排序方法。

如题29图所示，在栈的输入端元素的输入顺序为A，5，8，试写出在栈的输出端可以得到的以数字开头的所有输出序列，并写出进栈、出栈的操作过程(用push(X)表示X进栈，pop(x)表示x出栈)。

二叉排序树上的平均查找长度介于________和O(n)之间。

二分查找算法的时间复杂度是________。

索引顺序表由两部分组成：一个是顺序表，另一个是_______。

一个树的最少结点个数为_______。

已知完全二叉树的第5层有5个结点，则整个完全二叉树有________个叶结点。

为了节省存储空间，将矩阵中多个值相同的元素只分配一个存储空间，零元素不存储，这种存储方式通常称为矩阵的________。

100个结点的二叉树采用二叉链表存储时，空指针域NULL有______个。

链栈LS中，Ls->next指向栈顶结点，则新结点 * P入栈的操作为：P->next=LS->next;和_______;。

在带有头结点的循环链表中，头指针为head，判断P所指结点为尾结点的条件是_________

线性表中所含结点的个数称为_______。

在数据库中，_____又称为字段或域。

双向循环链表中，在P所指结点的后面插入一个新结点 * t，需要修改四个指针，分别为：t->prior=P; t->next=P->next; p->next—>prior=t; _______;。

下述四种排序算法中，所需辅助存储量最多的是(　　)

• A.堆排序
• B.快速排序
• C.归并排序
• D.直接选择排序

直接选择排序算法的时间复杂度为(　　)

• A.O(1)
• B.O(log²n)
• C.O(n)
• D.O(n²)

已知一个有序表为(15，19，30，33，49，50，65，88，93，126，164)，当二分查找值为126的元素时，检索成功需进行的比较次数为(　　)

• A.1次
• B.2次
• C.3次
• D.4次

设图的顶点数为n，则采用邻接矩阵作为存储结构的图的深度优先搜索算法的时间复杂度为(　　)

• A.O(1)
• B.O(n)
• C.O(n²)
• D.O(log₂n)

n个顶点的无向图若采用邻接矩阵存储，则该矩阵的大小是(　　)

• A.n×(n-1)
• B.(n-1)×(n-1)
• C.(n+1)×(n+1)
• D.n×n

具有10个叶结点的哈夫曼树中度为1的结点数为(　　)

• A.0个
• B.10个
• C.19个
• D.20个

深度为k的二叉树，结点个数最多为(　　)

• A.2^k
• B.2^k-1
• C.2^k-1
• D.2k-1

已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，nk个度为k的结点，则该树中的叶结点个数为(　　)

• A.
• B.
• C.
• D.

循环队列存储在数组A[m]中，则入队列操作中队列尾指针rear的变化为(　　)

• A.rear=rear+1
• B.rear=(rear+1)%(m-1)
• C.rear=(rear+1)%m
• D.rear=(rear+1)%(m+1)

单链表与顺序表相比，其特点是(　　)

• A.运算算法实现简单
• B.便于随机存取数据
• C.不需要预先分配存储空间
• D.结点个数受到限制

关于链栈的说法，正确的是(　　)

• A.链栈不用预先考虑容量的大小
• B.链栈出栈时不需要判断栈空
• C.链栈进栈时需要判断栈满
• D.链栈出栈时需要判断栈满

在表长为n的顺序表中做插入运算的时间复杂度为(　　)

• A.O(n)
• B.O(log₂n)
• C.O(1)
• D.O(n²)

在表长为101的顺序表中做删除运算，平均移动元素的次数为(　　)

• A.25
• B.50
• C.51
• D.100

下列算法的时间复杂度为(　　)

for( i=1; i<=n; i++)

{ m++;

  for(j=1; i<=n; j++)

       k*=m;

}

• A.O(n)
• B.O(n²)
• C.O(n³)
• D.O(log₂n)

根据数据元素之间关系的不同特性，通常将数据结构分为四类基本结构，即(　　)

• A.集合、顺序结构、树形结构、图结构
• B.集合、线性结构、链式结构、图结构
• C.集合、线性结构、树形结构、图结构
• D.线性结构、顺序结构、链式结构、图结构