首页
微信群
QQ群

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

如果您发现本试卷没有包含本套题的全部小题，请尝试在页面顶部本站内搜索框搜索相关题目，一般都能找到。

1: 写出复制一棵二叉树的算法。设原二叉树根结点由指针root指向，复制得到的二叉树根结点由指针newroot指向，函数头为：void CopyTree( BTNode *root, BTNode * newroot )，二叉树的存储结构为：
typedef struct btnode {
DataType data;
struct btnode *lchild, *rchild;
}BTNode, *BTree;

2: 已知带头结点的单链表L是按数据域值非递减有序链接的，试写一算法将值为x的结点插入表L中，使得L仍然是有序链接的。

3: 采用快速排序方法对关键字序列{265，301，751，129，937，863，742，694，076，438}进行升序排序，写出其每趟排序结束后的关键字序列。

4: 要求给出至少2个不同的关键字序列，均能构造出如题32图所示的二叉排序树;对此你会得出什么结论?
题32图

5: 设栈S和队列Q的初始状态均为空，7个元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag。现要求：
(1)栈S容量至少是多少?
(2)在(1)的情况下，画出该栈中元素最多时的一个状态示意图。

6: 某二叉树结点的中序遍历序列为ABCDEFG、后序遍历序列为BDCAFGE。现要求：
(1)画出该二叉树;
(2)写出该二叉树的先序遍历序列;
(3)该二叉树所对应的森林包括几棵树?

7: 假设有一棵完全二叉树按自上而下、从左到右的层序组织包含A、B、C、D、E、F、G这7个结点，分别给出其邻接矩阵和邻接表。

8: 影响排序算法时间复杂度的两个因素是关键字的_______次数和记录的移动次数。

9: 在直接插入、直接选择和冒泡这三种排序方法中，不稳定的排序方法是_______。

10: 在关键字序列{07，12，15，18，27，32，41，92}中用二分法查找和给定值92相等的关键字，在查找过程中依次和给定值92比较的关键字是_______。

11: 假设有K个关键字互为同义词，若用线性探测法把这K个关键字用散列函数H将它们存入长度为m的散列表中(K≤m)，则至少共需进行_______次探测。

12: 对于有n个顶点的无向图，所有生成树中都有且仅有_______条边。

13: 高度(深度)为k的二叉树中结点个数最多是2K-1、最少是_______。

14: 设散列表的地址空间为0到12，散列函数为h(k)=k mod 13，用线性探测法解决冲突。现要将关键字序列{10，100，32，45，58，128，3，29，200，400，0}映射到该散列表中，则其中关键字值58的地址为_______。

15: 稀疏矩阵可以采用_______方法进行压缩存储。

16: 含有11个结点的完全二叉树中度为l的结点的个数最多为_______。

17: 数组Q[n]表示一个循环队列，设f的值为队列中第一个元素的位置，r的值为队列中实际队尾的位置加1，并假定队列中最多只有n-1个元素，则计算队列中元素个数的公式是_______.

18: 一般说来，在每个逻辑结构上都定义了一组基本运算，通常这些运算包括：建立、_______、读取、插入和删除等。

19: 某带有头结点的单链表的头指针为head，则判断该单链表为非空的条件是_______。

20: 数据的存储结构又称为物理结构，可分为顺序存储、链式存储、_______以及散列存储等几种方式。

21: 在待排记录中其关键字序列基本有序的前提下，时间效率最高的排序方法是(　　)

A.直接插入排序
B.快速排序
C.选择排序
D.堆排序

22: 假设通信电文使用的字符集为{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

23: 元素的进栈次序为A，B，C，D，E，出栈的第一个元素为E，则第四个出栈的元素为(　　)

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

24: 平均时间复杂度和在最坏情况下的时间复杂度均是O(nlog2n)的排序算法是(　　)

A.插入排序
B.快速排序
C.选择排序
D.堆排序

25: 在如题10图所示的有向图中，从顶点1出发进行深度优先搜索可得到的结果序列是(　　)
题10图

A.1423
B.1432
C.1342
D.1243

26: 设森林F中有三棵树，其结点的个数分别为m1、m2、m3，则与F对应的二叉树根结点的右子树上的结点数是(　　)

A.m1+m2
B.m2+m3
C.m1+m3
D.m1+m2+m3

27: 对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时平均查找长度(ASL)为(　　)

A.<img src="//img1.yqda.net/question-name/5f/caad74f6fa7d66912675acf6c553bf.png" width="23" height="42"/>
B.<img src="//img1.yqda.net/question-name/f8/f29811b7f1da591f7903d545daca25.png" width="24" height="42"/>
C.<img src="//img1.yqda.net/question-name/ef/d4b47e5842eedf2d6411aad950f0a7.png" width="22" height="42"/>
D.<img src="//img1.yqda.net/question-name/60/36c4a0252624e261f2991274176f23.png" width="23" height="42"/>

28: 若对一棵含有199个结点的完全二叉树按自上而下、从左到右依次对结点编号，根结点的编号为1，则树中最后一个结点(即编号为199)的双亲结点的编号为(　　)

A.99
B.100
C.101
D.198

29: 二维数组A按行序优先顺序存储，每个数据元素占1个存储单元。若数据元素A[1][1]的存储地址是420，A[3][3]的存储地址是446，则A[5][5]的存储地址是(　　)

A.470
B.471
C.472
D.473

30: 某双向链表中的结点如题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;

31: 下列关于栈和队列的叙述中：Ⅰ栈和队列都是线性表;Ⅱ栈和队列都是顺序表;Ⅲ栈和队列都不能为空;Ⅳ栈和队列都能用于递归过程实现;Ⅴ栈的特点是先进后出、队列的特点是先进先出，其中正确的是(　　)

A.Ⅰ和V
B.Ⅰ、Ⅱ、V
C.Ⅲ和V
D.Ⅱ、Ⅳ、V

32: 在如题3图所示的数组A中链接存储了一个线性表，表头指针为A[0].next，则该线性表中第一个数据元素的值是(　　)
题3图

A.60
B.50
C.78
D.40

33: 在一个长度为n(n>1)的单链表上，设有头和尾两个指针，下列操作与链表长度有关的是(　　)

A.删除单链表中的第一个元素
B.删除单链表中的最后一个元素
C.在单链表中第一个元素前插入一个新元素
D.在单链表中最后一个元素后插入一个新元素

34: “能正确地实现预定的功能，满足具体问题的需要”。这种评价算法好坏的因素称为(　　)

A.正确性
B.易读性
C.健壮性
D.时空性

35: 有一程序片段：{ i=0; s=0; while(s<=n){ i++; s=s+i; }}，其时间复杂度是(　　)

A.O(n)
B.O(2n)
C.O(n<sup>1</sup><sup>/2</sup>)
D.O(1)

相关试卷

管理信息系统2009年1月真题及答案

所属类型：真题考试2021-03-24

管理信息系统2009年10月真题及答

所属类型：真题考试2021-03-24

管理信息系统2010年1月真题及答案

所属类型：真题考试2021-03-24

管理信息系统2010年10月真题及答

所属类型：真题考试2021-03-24

管理信息系统2011年1月真题及答案

所属类型：真题考试2021-03-24

管理信息系统2011年10月真题及答

所属类型：真题考试2021-03-24

管理信息系统2012年4月真题及答案

所属类型：真题考试2021-03-24

管理信息系统2012年10月真题及答

所属类型：真题考试2021-03-24

管理信息系统2013年4月真题及答案

所属类型：真题考试2021-03-24

管理信息系统2013年10月真题及答

所属类型：真题考试2021-03-24