2017年国家电网数据结构与算法试题(1)

有一组关键字{14,15,30,28,5,10},写出冒泡排序过程的图示。

一棵具有6层的满二叉树中结点数为多少？请写出计算公式。

已知完全二叉树的第8层有4个结点，请计算它的叶子结点数和总结点数。（写出计算过程）。

已知数据序列{10,8,18,15,7,16}，写出采用直接插入算法排序时，每一趟排序的结果。

双向链表有两个指针域，一个指向前趋，另一个指向______。

队列存取数据应遵循的原则是______。

若进栈的次序是A,B,C,D,E,写出两种出栈顺序_______、______。

树和______都属于非线性结构。

顺序表中逻辑上相邻的元素在物理位置上______相邻。

若用冒泡排序对关键字序列（18,16,14,12,10,8）进行从小到大的排序，所需进行的关键字比较总次数是（）。

• A.10
• B.15
• C.21
• D.34

用直接插入排序对下面四个序列进行排序（由小到大），元素比较次数最少的是（ ）。

• A.94,32,40,90,80,46,21,69
• B.32,40,21,46,69,94,90,80
• C.21,32,46,40,80,69,90,94
• D.90,69,80,46,21,32,94,40

一组待排序记录的关键字为（46，79，56，38，40，84），则利用快速排序，以第一个记录为基准元素得到的一次划分结果为（ ）。

• A.(38,40,46,56,79,84)
• B.(40,38,46,79,56,84)
• C.(40,38,46,56,79,84)
• D.(40,38,46,84,56,79)

数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中()的两趟排序后的结果。

• A.选择排序
• B.冒泡排序
• C.插入排序
• D.堆排序

对序列(15，9，7，8，20，-1，4)进行排序，进行一趟排序后，数据的排列变为（4，9，-1，8，20，7，15），则采用的是（）排序。

• A.选择
• B.快速
• C.希尔
• D.冒泡

下列排序方法中，（）是稳定的排序方法。

• A.直接选择排序
• B.二分法插入排序
• C.希尔排序
• D.快速排序

一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为()。

• A.79，46，56，38，40，80
• B.84，79，56，38，40，46
• C.84，79，56，46，40，38
• D.84，56，79，40，46，38

循环队列SQ队满的条件是（）。

• A.SQ->rear==SQ->front
• B.(SQ->rear+1)%MAXLEN==SQ->front
• C.SQ->rear==0
• D.SQ->front==0

已知P为单链表中的非首尾结点，删除P结点的后继结点Q的语句为（）。

• A.P->NEXT=Q->NEXT;FREE(Q);
• B.Q->NEXT=P; FREE(Q);
• C.Q->NEXT=P->NEXT;FREE(Q);
• D.P->NEXT=S;S->NEXT=P;

设front、rear分别为循环双向链表结点的左指针和右指针，则指针P所指的元素是双循环链表L的尾元素的条件是（）。

• A.P==L
• B.P->front==L
• C.P==NULL
• D.P->rear==L

在表长为n的顺序表中进行线性查找，它的平均查找长度为（）。

• A.ASL=n
• B.ASL=(n+1)/2
• C.
• ASL=+1
• D.ASL=log2n

一个线性表第一个元素的存储地址是320，每个元素的长度为3，则第五个元素的地址是(）。

• A.311
• B.328
• C.332
• D.313

下列哪个不是算法的特性（）。

• A.有穷性
• B.可数性
• C.可行性
• D.确定性

数据的基本单位是（）。

• A.数据元素
• B.数据结构
• C.数据项
• D.数据对象

链表适合于（）查找。

• A.顺序
• B.二分
• C.随机
• D.顺序或二分

插入和删除操作只能在一端进行的线性表，称为（）。

• A.队列
• B.线性表
• C.栈
• D.循环队列

队列是仅允许在（）进行插入，而在（）进行删除。()

• A.队尾，队首
• B.队尾，队尾
• C.队首，队尾
• D.队首，队首

在一个长度为n的顺序表中向第i个元素（0< i<=n+1）之前插入一个新元素时，需向后移动（）个元素。

• A.n-i
• B.n-i+1
• C.n-i-1
• D.i

单链表中各结点之间的地址（）

• A.必须连续
• B.部分必须连续
• C.不一定连续
• D.以上均不对

在逻辑上可以把数据结构分成（ ）

• A.线性结构和非线性结构
• B.动态结构和静态结构
• C.紧凑结构和非紧凑结构
• D.内部结构和外部结构