数据结构导论2015年10月真题及答案解析（02142）
-
写出复制一棵二叉树的算法。设原二叉树根结点由指针root指向，复制得到的二叉树根结点由指针newroot指向，函数头为：void CopyTree( BTNode *root, BTNode * newroot )，二叉树的存储结构为：
typedef struct btnode {
DataType data;
struct btnode *lchild, *rchild;
}BTNode, *BTree;
-
已知带头结点的单链表L是按数据域值非递减有序链接的，试写一算法将值为x的结点插入表L中，使得L仍然是有序链接的。
-
采用快速排序方法对关键字序列{265，301，751，129，937，863，742，694，076，438}进行升序排序，写出其每趟排序结束后的关键字序列。
-
要求给出至少2个不同的关键字序列，均能构造出如题32图所示的二叉排序树;对此你会得出什么结论?
题32图
-
设栈S和队列Q的初始状态均为空，7个元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag。现要求：
(1)栈S容量至少是多少?
(2)在(1)的情况下，画出该栈中元素最多时的一个状态示意图。
-
某二叉树结点的中序遍历序列为ABCDEFG、后序遍历序列为BDCAFGE。现要求：
(1)画出该二叉树;
(2)写出该二叉树的先序遍历序列;
(3)该二叉树所对应的森林包括几棵树?
-
假设有一棵完全二叉树按自上而下、从左到右的层序组织包含A、B、C、D、E、F、G这7个结点，分别给出其邻接矩阵和邻接表。
-
影响排序算法时间复杂度的两个因素是关键字的_______次数和记录的移动次数。
-
在直接插入、直接选择和冒泡这三种排序方法中，不稳定的排序方法是_______。
-
在关键字序列{07，12，15，18，27，32，41，92}中用二分法查找和给定值92相等的关键字，在查找过程中依次和给定值92比较的关键字是_______。
-
假设有K个关键字互为同义词，若用线性探测法把这K个关键字用散列函数H将它们存入长度为m的散列表中(K≤m)，则至少共需进行_______次探测。
-
对于有n个顶点的无向图，所有生成树中都有且仅有_______条边。
-
高度(深度)为k的二叉树中结点个数最多是2K-1、最少是_______。
-
设散列表的地址空间为0到12，散列函数为h(k)=k mod 13，用线性探测法解决冲突。现要将关键字序列{10，100，32，45，58，128，3，29，200，400，0}映射到该散列表中，则其中关键字值58的地址为_______。
-
稀疏矩阵可以采用_______方法进行压缩存储。
-
含有11个结点的完全二叉树中度为l的结点的个数最多为_______。
-
数组Q[n]表示一个循环队列，设f的值为队列中第一个元素的位置，r的值为队列中实际队尾的位置加1，并假定队列中最多只有n-1个元素，则计算队列中元素个数的公式是_______.
-
一般说来，在每个逻辑结构上都定义了一组基本运算，通常这些运算包括：建立、_______、读取、插入和删除等。
-
某带有头结点的单链表的头指针为head，则判断该单链表为非空的条件是_______。
-
数据的存储结构又称为物理结构，可分为顺序存储、链式存储、_______以及散列存储等几种方式。
-
在待排记录中其关键字序列基本有序的前提下，时间效率最高的排序方法是( )
- A.直接插入排序
- B.快速排序
- C.选择排序
- D.堆排序
-
假设通信电文使用的字符集为{a，b，e，d，e，f}，各字符在电文中出现的频率分别为{34，5，12，23，8，18}，利用构造Huffman树对每个字符进行编码，则其中编码长度最长的字符是( )
- A.a, b
- B.a，d
- C.b，e
- D.e，f
-
元素的进栈次序为A，B，C，D，E，出栈的第一个元素为E，则第四个出栈的元素为( )
- A.D
- B.C
- C.B
- D.A
-
平均时间复杂度和在最坏情况下的时间复杂度均是O(nlog2n)的排序算法是( )
- A.插入排序
- B.快速排序
- C.选择排序
- D.堆排序
-
在如题10图所示的有向图中，从顶点1出发进行深度优先搜索可得到的结果序列是( )
题10图
- A.1423
- B.1432
- C.1342
- D.1243
-
设森林F中有三棵树，其结点的个数分别为m1、m2、m3，则与F对应的二叉树根结点的右子树上的结点数是( )
- A.m1+m2
- B.m2+m3
- C.m1+m3
- D.m1+m2+m3
-
对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时平均查找长度(ASL)为( )
- A.
- B.
- C.
- D.
- A.
-
若对一棵含有199个结点的完全二叉树按自上而下、从左到右依次对结点编号，根结点的编号为1，则树中最后一个结点(即编号为199)的双亲结点的编号为( )
- A.99
- B.100
- C.101
- D.198
-
二维数组A按行序优先顺序存储，每个数据元素占1个存储单元。若数据元素A[1][1]的存储地址是420，A[3][3]的存储地址是446，则A[5][5]的存储地址是( )
- A.470
- B.471
- C.472
- D.473
-
某双向链表中的结点如题5图所示。删除t所指结点的操作为( )
- A.t->prior->prior=t->next; t->next->prior=t->prior;
- B.t->prior->prior=t->prior; t->next->next=t->next;
- C.t->prior->next=t->prior; t->next->prior=t->next;
- D.t->prior->next=t->next; t->next->prior=t->prior;
-
下列关于栈和队列的叙述中：Ⅰ栈和队列都是线性表;Ⅱ栈和队列都是顺序表;Ⅲ栈和队列都不能为空;Ⅳ栈和队列都能用于递归过程实现;Ⅴ栈的特点是先进后出、队列的特点是先进先出，其中正确的是( )
- A.Ⅰ和V
- B.Ⅰ、Ⅱ、V
- C.Ⅲ和V
- D.Ⅱ、Ⅳ、V
-
在如题3图所示的数组A中链接存储了一个线性表，表头指针为A[0].next，则该线性表中第一个数据元素的值是( )
题3图
- A.60
- B.50
- C.78
- D.40
-
在一个长度为n(n>1)的单链表上，设有头和尾两个指针，下列操作与链表长度有关的是( )
- A.删除单链表中的第一个元素
- B.删除单链表中的最后一个元素
- C.在单链表中第一个元素前插入一个新元素
- D.在单链表中最后一个元素后插入一个新元素
-
“能正确地实现预定的功能，满足具体问题的需要”。这种评价算法好坏的因素称为( )
- A.正确性
- B.易读性
- C.健壮性
- D.时空性
-
有一程序片段：{ i=0; s=0; while(s<=n){ i++; s=s+i; }}，其时间复杂度是( )
- A.O(n)
- B.O(2n)
- C.O(n1/2)
- D.O(1)
