数据结构小课堂（6.7讲师版）

? 考试形式：

? 选择：小知识点

? 填空：小的知识点以及相关重点算法的代码填空 ? 简答（40分）：不用编程（画出构造一个堆的流程、构造一棵哈夫曼编码树。。。） ? 编程（30分）：需要编程实现（逆序一个链表）

? 现学的数据结构：

? 顺序表 ? 栈 ? 队列

? 二叉树（二叉搜索树） ? 堆 ? 要求掌握：

? 定义

? 编程实现（数组，链表） ? 应用

一、 单选：

1.以下数据结构中哪一个是非线性结构？( D )

A、队列 B、栈 C、线性表 D、二叉树

2. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)。每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。（ C）

A、688 B、678 C、692 D、696

3.二叉树的第K层的结点数最多为( D ).

kKK-1k-1

A、2-1 B、2+1 C、2 +1 D、 2

4. 设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（A）。

A、 BADC B、BCDA C、 CDAB D、CBDA

5.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ B ）个空指针域。 A、 2m-1 B、 2m C、 2m+1 D、 4m 6. 设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ C ）。 A、 R-F B、 F-R C、(R-F+M)％M D、(F-R+M)％M 7.下面程序的时间复杂为（B）

for（i=1，s=0；i<=n；i++） {t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；}

234

A、 O(n) B、 O(n) C、 O(n) D、 O(n)

8.设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（B ）。

2

A、 O(1) B、 O(log2n) C、O(n) D、 O(n)

9.设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（ C ）。

2

A、 O(n) B、 O(nlog2n) C、 O(1) D、 O(n)

10.设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长

度之和为（ D ）。

A、20 B、 30 C、40 D、 45

二、填空：

1. 后缀算式9 2 3 +- 10 2 / -的值为（-1）。中缀算式（3+4X）-2Y/3对应的后缀算式为

（3 4 X * + 2 Y * 3 / -）。

2. 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指

针。在这种存储结构中，n个结点的二叉树共有（2n）个指针域，其中有（n-1）个指针域是存放了地址，有（ n+1）个指针是空指针。

3. 在堆排序的过程中，对任一分支结点进行筛选运算的时间复杂度为（ O(log2n)），整个

堆排序过程的时间复杂度为（ O(nlog2n)）。

4. 数据的物理结构主要包括（顺序存储结构）和（链式存储结构）两种情况。

5. 设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为

（ p>llink->rlink=p->rlink; p->rlink->llink=p->rlink）（设结点中的两个指针域分别为llink和rlink）。

6. 深度为k的完全二叉树中最少有（2k-1）个结点。

7. 设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线

上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有(i(i+1)/2+j-1)个数据元素。 8. 补充二分查找代码：

templateintorderedList:: BinarySearch( const Type &x ) const { //折半搜索的迭代算法

inthigh = , low = 0, mid; while ( ) {

mid = ( low + high ) / 2; if ( Element[mid].getKey ( )

else if ( Element[mid].getKey ( ) > x ) ;

else return mid; } return -1; }

9. 下面程序段的功能实现数据x进栈，要求在括号处填上正确的语句。

typedefstruct {int s[100]; int top;} sqstack; void push(sqstack&stack,int x) {

if (stack.top==m-1) printf(“overflow”);

else {（stack.s[stack.top]=x）;（stack.top++） ;}

}

10.template void BinaryTree:: PreOrder( BinTreeNode *current ) { if ( current != NULL ) { cout<

PreOrder( current→leftChild ); PreOrder( current→rightChild ); } }

三、简答题

1.已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。

参考答案：

AEFNULLDHFKJGBC 2.下图所示的森林：

(1)求树（a）的先根序列和后根序列； (2) 求森林先序序列和中序序列； （3）将此森林转换为相应的二叉树；

ABD(a)参考答案：

GCEFIHJ(b)K

(1) ABCDEF; BDEFCA；(2) ABCDEFGHIJK; BDEFCAIJKHG（3）转换为相应的二叉树

ABCDEFIJKHG

3.设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给 出构造过程。 参考答案：

45 45 45 45 45

80 80 40 80 40 80

48 48 48