数据结构训练题（无答案）

一、单选题（每题1分，共20分）

1.有63个结点的完全二叉树的深度为（）（根的层次为1）。

A.5B.6C.7D.8

2.以数组A|n]存放循环队列中的元素，变量rear和length分别指示队尾元素和队列长度，则

队列中第一个元素的实际位置是（)o

A.(rear-length+1)%nB.(rear-length+m+1)%n

C.(rear-length+m)%nD.(rear-length)%n

3.假设有二维数组设A[0][0]在644处，A⑵⑵在676处。每个元素占一个存储空

间，则A[4][5]的地址（）o

A.708B.707C.710D.7O9

4.在确定选取何种存储结构时，一般不考虑（）o

A.各结点的值如何B.结点个数的多少

c.对数据有.哪些运算D.所用编程语言实现这种结构是否方便

8.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用

（）存储方式最节省运算时间。

A.单链表B.给出表头指针的单循环链表

C.双链表D.带头结点的双循环链表

9.计算机算法必须具备输入、输出和（）等5个特性。

A.可行性、可移植性和可扩充性B.可行性、确定性和芍穷性

C.确定性、有穷性和稳定性D.易读性、稳定性和安全性

II.在一个单链表中，p指向链表中某一结点，若要在p之后插入s所指结点，则执行（）。

A.s->next=p;p->next=s;B.s->next=p->next;p->next=s;

C.s->next=p->next;p=s;D.p->next=s;s->next=p;

12.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（）。

A.O(1)B.O(n)C.O(m)D.O(ni+n)

13.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组R[n]中且有左孩子，则左

孩子是结点（）。

A.R[2i+l]B.R[2i]C.R|i/2]D.R[2i-l]

14.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少

为（）o

A.2hB.2h-1C.2h+1D.h+1

15.在一棵度为3的树中，度为3的结点个数为1,度为2的结点个数为2,则度为0的结点个数为

（）o

A.4B.5C.6D.?

16.数组A[1..10「L60..3]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000

的连续的内存单元中，则元素A[242]的地址为（）

A.1140B.1162C.1270D.1225

18.一个栈的输入序列为12345,则下列序列中不可能是栈的输出序列的是（）

A.23415B.54132

C.23145D.15432

19.若目标串的长度为n,模式串的长度为[n/3],则执行模式匹配算法时，在最坏情况下的时

间复杂度是（）

A.O（n/3）B.O（n）C.O（n2）D.O（n3）

20.由权值分别为11,8,6,4,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）

A.24B.71C.48D.77

二、判断题（每题1分，共10分）

2.二维数组是数组元素为一维数组的线性表，因此它是线性结构。（）

5.栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。（）

6.链表的每个结点都恰好包含一个指针。（）

8.线性表的特点是每个元素都有一个前驱和一个后维。（）

9.哈夫曼树是带权路径最短的树，路径上权值较大的结点离根较近。（）

10.已知二叉数的前序遍历和后序遍历并不能唯一的确定这棵树。（）

三、填空题（每空2分，共20分）

1.在有n个叶子结点的哈夫曼树中，总结点数是一（1）。

2.设W为一个二维数组，行下标从0到8,列下标从2到5,若按行序存储，元素W⑵⑵的地址

与按列序存储时元素（2）的地址相同。

3.在矩阵的快速转置中，辅助向量Cpot”的作用是：（3）o

4.对矩阵采用压缩存储是为了（4）-

5.带头结点的双循环链表L为空表的判断条件是一（5）.

6.在双链表中，在指针P所指结点前面插入一个结点S八时的语句序列是：

SA.next=P；SA.prior=PA.prior：PA.prior=S;⑹：

7.对广义表A=（x,（（a,b）,c,d））的运算head（head（tail（A）））的结果是一（7）。

8.判断线索二叉树中某结点指针P所指结点有左孩子的条件是

四、简答题（每题5分，共30分）

1.画出和下列序列对应的森林F：（5分）

先序序歹lj：ABCDEFGHIJKL

中序序歹|J：CBEFDGAJIKLH

5.假设用于通信的电文仅由8个字母组成，它们出现的频率分别为0.07,0.19,0.02,0.06,

0.32,0.03,0.21,0.10o试为这8个字母设计哈夫曼编码。（5分）

五、算法设计题（共20分）

I.己知线性链表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为

••个新的线性表LC,且LC中的数据元素仍按值非递减有序排列。链表定义如下：

typcdcfstructLnodc{

intdata;

StructLnode*next;

}Lnode,*LinkList;

voidMergeList（LinkList&La.LinkList&Lb,LinkList&Lc）;（6分）

2.若矩阵A。”中的某一元素是第i行中的最小值，同时乂是第j列中的最大值，则称

此元素为该矩阵的一个鞍点。假设以二维数组存放矩阵，试编写一个函数，确定鞍点在数组

中的位置（若鞍点存在时）。（6分）

3.已知二叉树中的结点类型BinTreeNode定义为:

typedefstructBiTNode{

chardata;

structBiTNode*lchild,*rchild;};

根据下面函数声明编写出判断两棵二叉树是否相等的算法，若相等则返回1否则返回0