【考研计算机专业课】武汉大学期末试题 数据结构2011
- 格式：pdf
- 大小：316.88 KB
- 文档页数：9
文档推荐
-
武汉大学DSP试卷及答案页数:12
-
武大GIS历年考研真题98-12年页数:16
-
武汉大学数据结构考试题(附答案)页数:11
-
武汉大学计算机学院级系统结构试卷页数:3
-
武汉大学2013级本科软件工程试卷页数:4
下载文档原格式
合集下载
《数据结构》期末考试试题及答案
《数据结构》期末考试试题及答案一、单项选择题1. 数据结构是计算机科学的基础学科之一。
下列哪个选项正确描述了数据结构的定义？A. 数据结构是一种计算机程序B. 数据结构是一种存储和组织数据的方法C. 数据结构是一种人工智能技术D. 数据结构是一种操作系统答案：B2. 链表和数组是常见的数据结构，它们之间的主要区别是：A. 数组可以存储不同类型的数据，而链表只能存储相同类型的数据B. 数组的元素在内存中是连续存储的，而链表的元素在内存中是分散存储的C. 链表可以随机访问元素，而数组只能顺序访问元素D. 链表的插入和删除操作更高效，而数组的访问操作更高效答案：B3. 在二叉树中，每个节点最多可以有多少个子节点？A. 1B. 2C. 3D. 无限多个答案：B二、填空题1. 假设有一组数据 [5, 8, 3, 2, 9]，按照从小到大的顺序进行冒泡排序的过程中，经过三次交换后的结果是__2__，__3__，__5__，__8__，__9__。
2. 请完成以下代码，实现栈的入栈和出栈操作：```pythonclass Stack:def __init__(self):self.stack = []def push(self, item):self.stack.append(item)def pop(self):if not self.is_empty():return self.stack.pop()def is_empty(self):# 示例代码s = Stack()s.push(1)s.push(2)s.push(3)print(s.pop()) # 输出 3print(s.pop()) # 输出 2print(s.is_empty()) # 输出 False ```答案：```pythonclass Stack:def __init__(self):self.stack = []def push(self, item):self.stack.append(item)def pop(self):if not self.is_empty():def is_empty(self):return len(self.stack) == 0# 示例代码s = Stack()s.push(1)s.push(2)s.push(3)print(s.pop()) # 输出 3print(s.pop()) # 输出 2print(s.is_empty()) # 输出 False```三、简答题1. 请简要介绍树的基本概念及常见的树结构。
数据结构期末考试试题及答案
数据结构期末考试试题及答案一、选择题（每题2分，共20分）1. 在数据结构中，算法的时间复杂度是指（）。
A. 编写代码的时间B. 代码的长度C. 执行代码所需的时间D. 执行代码所需的指令条数2. 下列关于队列的描述，错误的是（）。
A. 队列是先进先出（FIFO）的线性表B. 队列允许在一端进行插入操作C. 队列的插入操作称为入队D. 队列的删除操作称为出栈3. 对于长度为n的有序数组，使用二分查找法查找一个元素的平均时间复杂度是（）。
A. O(n)B. O(n^2)C. O(log n)D. O(1)4. 在图的遍历中，深度优先搜索（DFS）使用的数据结构是（）。
A. 栈B. 队列C. 链表D. 数组5. 哈希表的冲突可以通过多种方式解决，以下哪种不是解决冲突的方法？（）A. 开放寻址法B. 链地址法C. 线性探测法D. 排序法6. 一个完全二叉树共有700个节点，它的最大节点数是（）。
A. 700B. 701C. 1400D. 14017. 快速排序算法的最坏情况发生在（）。
A. 每次选择的基准都是最大值B. 数据已经有序C. 数据已经完全逆序D. 所有数据元素相等8. 在一个具有n个节点的二叉搜索树中，最坏情况下查找一个元素的时间复杂度是（）。
A. O(n)B. O(log n)C. O(n^2)D. O(1)9. 堆排序算法中，将一个堆调整为最大堆或最小堆的过程称为（）。
A. 堆调整B. 堆构建C. 堆分解D. 堆维护10. 以下哪个不是B树的特性？（）A. 所有键值都存储在内部节点和叶子节点中B. 所有叶子节点都在同一层上C. 每个内部节点至多有m个子节点D. 每个内部节点的非叶子子节点都至少有m/2个子节点二、简答题（每题5分，共30分）1. 什么是递归？请举例说明递归算法的应用场景。
2. 请简述图的邻接矩阵和邻接表两种存储方式的优缺点。
3. 解释什么是平衡二叉树，并说明它为什么在实际应用中很重要。
数据结构期末考试试题
武汉大学计算机学院2010年－2011学年第一学期“数据结构”考试试题（A）一、单项选择题（每小题2分，共计40分）1. 下列各项中属于逻辑结构的是。
A. 哈希表B. 有序表C. 单链表D. 顺序表2. 以下算法的时间复杂度为。
void fun(int n){ int i=1; while (i<=n) i=i*2; }A. O(n)B. O(n2)C. O(nlog2n)D. O(log2n)3. 在一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动个元素。
A. nB. i-1C. n-iD. n-i+14. 判断带头结点的循环单链表L中只有一个结点的条件是。
A. L==NULLB. L->next==LC. L->next->next==LD. L->next==NULL5. 中缀表达式a*(b+c)-d的后缀表达式是。
A. abcd*+-B. abc+*d-C. abc*+d-D. -+*abcd6. 设环形队列中数组的下标是0～N-1，其头尾指针分别为f和r（f指向队列中队头元素的前一个位置，r指向队尾元素的位置），则其元素个数为。
A. r-fB. r-f-1C. (r-f)％N+1D. (r-f+N)％N7. 若用一个大小为6的数组来实现环形队列，队头指针front指向队列中队头元素的前一个位置，队尾指针rear指向队尾元素的位置。
若当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为。
A. 1和5B. 2和4C. 4和2D. 5和18. 稀疏矩阵采用压缩存储后，通常必会失去功能。
A. 顺序存储B. 随机存取C. 输入输出D. 以上都不对9. 一棵有124个叶子结点的完全二叉树，最多有个结点。
A. 247B. 248C. 249D. 25010. n个结点的线索二叉树上含有的线索个数为。
武大计算机类真题数据结构(2007-A
数据结构部分（共75分）一. 单项选择题（2×10分，共20分）1. 某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，故采用 d 存储方式最节省运算时间。
A. 单链表B.循环单链表C. 双链表D.仅有尾结点指针的循环单链表2. 栈和队列的共同点是c 。
A. 都是先进后出B. 都是先进先出C. 只允许在端点处插入和删除元素D. 没有共同点3．对于含有n个互不相同字符的串，则真子串（不包括串自身）的个数是c 。
A. nB.n2C.n(n+1)/2D.n(n-1)/24. 在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为 cA. 4B. 5C. 6D. 75. 某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是d 。
A. 空或只有一个结点B. 完全二叉树C. 二叉排序树D. 高度等于其结点数6. 对图1所示的无向图，从顶点1开始进行深度优先遍历；可能得到顶点访问序列是a 。
A.1 2 4 3 5 7 6B.1 2 4 3 5 6 7C.1 2 4 5 6 3 7D.1 2 3 4 5 7 6图1 一个无向图7. 对于含有n个顶点的带权无向连通图，它的最小生成树是指该图中任意一个d。
A.由n-1条权值最小的边构成的子图B.由n-l条权值之和最小的边构成的子图C.由n条权值之和最小的边构成的连通子图D.由n个顶点构成的边的权值之和最小的连通子图8. 有一组数据{15,9,7,8,20,1,7,4}，用堆排序的筛选方法建立的初始小根堆为c 。
A.{1,4,8,9,20,7,15,7}B.{1,7,15,7,4,8,20,9}C.{1,4,7,8,20,15,7,9}D.以上都不对9. 在含有27个结点的二叉排序树上，查找关键字为35的结点，则依次比较的关键字有可能是 d 。
A.28,36,18,46,35B.18,36,28,46,35C.46,28,18,36,35D.46,36,18,28,3510. 采用败者树进行k路平衡归并的外排序算法，其总的归并效率与k b 。
【考研计算机专业课】武汉大学期末试题 数据结构2007
四、算法设计题（共 30 分）
1. 解：用 p 从头至尾扫描单链表，pre 指向*p 结点的前驱，用 minp 保存值最小的结点 指针，minpre 指向*minp 结点的前驱。一面扫描，一面比较，将最小值的结点放到*minp 中。算法如下：
void delminnode(LinkList *&L) {
三、问答题（共 40 分）
1. 答： 二叉树中度为 1 的结点个数只能是 1 或 0。 设 n1=1， n=n0+n1+n2=n0+n2+1=1001， 由性质 1 可知 n0=n2+1，由两式可求 n0=500.5，不成立；设 n1=0，n=n0+n1+n2=n0+n2=1001， 由性质 1 可知 n0=n2+1，由两式可求 n0=501。本题答案为：501。 评分标准：只给出结果给 3 分，推导过程占 5 分。 2. 答：对于邻接矩阵表示的无向图，顶点 i 的度等于第 i 行中元素等于 1 的个；对于 邻接矩阵表示的有向图，顶点 i 的出度等于第 i 行中元素等于 1 的个数；入度等于第 i 列中 元素等于 1 的个数；度数等于它们之和。 对于邻接矩阵表示的无向图，顶点 i 的出度等于 g->adjlist[i]为头结点的单链表中结点 的个数；入度需要遍历各顶点的边表，若 g->adjlist[k]为头结点的单链表中存在顶点编号为 i 的结点，则顶点 i 的入度增 1；度数等于它们之和。 评分标准：有向图、无向图两种存储方式各占 4 分。 3. 建立平衡二叉树过程如图 2 所示(图中加阴影的结点表示要调整的结点)。
评分标准：根据算法的正确性评分，不考虑算法的时间复杂度。 2．解：递归算法如下：
武汉大学《数据结构》2020-2021学年第一学期期末试卷
武汉大学计算机学院2020－2021学年第一学期“数据结构”考试试题（A）姓名学号(序号)_学校要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。
每张答题纸都要写上姓名和序号。
一、单项选择题（每小题2分，共计20分）1.下列说法中，不正确的是。
A.数据元素是数据的基本单位B.数据项是数据中不可分割的最小可标识单位C.数据可由若干个数据元素构成D.数据项可由若干个数据元素构成2.对于一个线性表，既要求能够较快地进行节点插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应采用存储结构。
A.顺序B.链式C.散列D.索引3.如果以链表作为栈的存储结构，则退链栈操作时。
A.必须判断链栈是否满B.判断链栈元素的类型C.必须判断链栈是否空D.对链栈不作任何判断4.设循环队列中数组的下标是0～N-1，其头尾指针分别为f和r，则其元素个数为。
A.r-fB.r-f-1C.(r-f)％N+1D.(r-f+N)％N5.设二维数组A[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素，a[0][0]的存储地址为860，则a[3][5]的存储地址是。
A.1000B.860C.1140D.12006..一个无向图中有16条边，度为4的顶点有3个，度为3的顶点有4个，其余顶点的度均小于3，则该图至少有个顶点。
A.10B.11C.12D.137.采用邻接表存储的图的广度优先遍历算法类似于二叉树的算法。
A.先序遍历B.中序遍历C.后序遍历D.层次遍历8.一个有向图G的邻接表存储如图1所示，现按深度优先搜索遍历，从顶点0出发，所得到的顶点序列是。
图1有向图G 的邻接表A.0,1,2,3,4B.0,1,2,4,3C.0,1,3,4,2D.0,1,4,2,39.在含有27个节点的二叉排序树上，查找关键字为35的节点，则依次比较的关键字有可能是。
A.28,36,18,46,35B.18,36,28,46,35C.46,28,18,36,35D.46,36,18,28,3510.对关键字序列{15,9,7,8,20,-1,4}进行排序，进行一趟排序后数据序列变为{9,15,7,8,20,-1,4}，则采用的是算法。
《数据结构》期末考试试卷（含答案）
《数据结构》期末考试试卷（含答案）《数据结构》期末考试试卷（ A ）一、选择题（每小题2分，共24分）1．计算机识别、存储和加工处理的对象被统称为( A )A.数据B.数据元素C.数据结构D.数据类型2．栈和队列都是（A）A．限制存取位置的线性结构B．顺序存储的线性结构C．链式存储的线性结构D．限制存取位置的非线性结构3．链栈与顺序栈相比，比较明显的优点是( D )A.插入操作更加方便B.删除操作更加方便C.不会出现下溢的情况D.不会出现上溢的情况4．采用两类不同存储结构的字符串可分别简称为( B )A.主串和子串B.顺序串和链串C.目标串和模式串D.变量串和常量串5．一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是：BA. 110 B .108C. 100D. 1206．串是一种特殊的线性表，其特殊性体现在：BA.可以顺序存储 B .数据元素是一个字符C. 可以链接存储D. 数据元素可以是多个字符7．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为：CA. 2h B .2h-1C. 2h+1D. h+1软件开发网/doc/d818218954.html,8．树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。
这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。
下列结论哪个正确？AA. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同B .树的后根遍历序列与其对应的二叉树的后序遍历序列相同C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同D. 以上都不对9．一个有n个顶点的无向图最多有多少边？CA. n B .n(n-1)C. n(n-1)/2D. 2n10．在一个图中，所有顶点的度数之和等于所有边数的多少倍?CA. 1/2 B .1C. 2D. 411．当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为（A）A．左子树的叶子结点B．左子树的分支结点C．右子树的叶子结点D．右子树的分支结点软件开发网/doc/d818218954.html,12．对于哈希函数H(key)=key%13,被称为同义词的关键字是( D )A.35和41B.23和39C.15和44D.25和51二、已知某棵二叉树的前序遍历结果为A,B,D,E,G,C,F,H,I,J，其中中序遍历的结果为D,B,G,E,A,H,F,I,J,C。
2011年数据结构期末试题(附完整答案)
15．串是一种特殊的线性表，其特殊性体现在（ ） A.可以顺序存储 B.数据元素是一个字符 C.可以链接存储 D.数据元素可以是多个字符 16．树的基本遍历策略分为先根遍历和后根遍历；二叉树的基本遍历策 略可分为先序遍历、中序遍历和后序遍历。结论( )是正确的。 A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B.树的后根遍历序列与其对应的二叉树的先序遍历序列相同 C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D.以上都不对 17．由五个分别带权值为9，2，3，5，14的叶子结点构成的一棵哈夫曼 树，该树的带权路径长度为( )。 A. 60 B. 66 C. 67 D. 50 18．一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二 叉树中度为2的结点有( )个 A. 33 B. 34 C. 32 D. 30 19．有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找 值82为的结点时，（ ）次比较后查找成功。 A. 1 B. 2 C. 4 D. 8 20．若有文件的关键字序列为：[265] [301] [751] [129] [937] [863] [742] [694] [076] [438]，以下为二路归并排序过程。第二趟为: A.[265 301] [129 751] [863 937] [694 742] [076 438] B.[076 129 265 301 438 694 742 751 863 937] C.[129 265 301 694 742 751 863 937] [076 438] D.[129 265 301 751] [694 742 863 937] [076 438]
⑴ ⑷
⑵ ⑸
⑶
3.请在标号处填写合适的语句。完成下列程序。(每空1分，共5分) int Binary_Search(S_TBL tbl，KEY kx) { /* 在表tbl中查找关键码为kx的数据元素，若找到返回该元素在表中的位 置，否则，返回0 */ int mid，flag=0； low=1；high=length； while( ⑴ &!flag ) { /* 非空，进行比较测试 */ mid= ⑵ ； if(kx<tbl.elem[mid].key) ⑶ ； else if(kx>tbl.elem[mid].key) ⑷ ； else { flag= ⑸ ；break；} } return flag; } ⑴ ⑵ ⑶ ⑷ ⑸
武汉大学数据结构考试题(附答案)
武汉大学数据结构考试题(附答案)编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（武汉大学数据结构考试题(附答案)）的内容能够给您的工作和学习带来便利。
同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。
本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快业绩进步，以下为武汉大学数据结构考试题(附答案)的全部内容。
1. 下面程序段的执行次数为（ A ）for(i=0；i＜n-1；i++)for(j=n；j＞i;j--)state；A. n(n+2）2 B 。
（n-1)(n+2）2 C。
n(n+1)2 D. （n-1)(n+2)2。
一个向量第一个元素的存储地址是100,每个元素的长度为2，则第5个元素的地址是（ B ）A. 110 B 。
108 C. 100 D. 1203. 一个栈的入栈序列是a,b,c，d，e，则栈的不可能的输出序列是（ C ）A。
edcbaB 。
decba C. dceab D. abcde4。
循环队列用数组A[0，m－1]存放其元素值，已知其头尾指针分别是front和rear,则当前队列中的元素个数是（ D ）A. (rear-front+m）％m B .read—front+1C. read-front—1 D. read—front5．不带头结点的单链表head为空的判定条件是（ A ）A. head=NULL B .head—next=NULLC. head-next=head D。
head！=NULL6．在一个单链表中，若p所指的结点不是最后结点,在p之后插入s所指结点，则执行（B)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;7. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较多少个结点（ D ）A. n B .n2 C。
【考研计算机专业课】武汉大学期末试题 数据结构2012
数据结构试题
5
{0} {01} {0 1 {0 1 {0 1 {0 1
2} 2 3} 2 3 4} 2 3 4 5}
0 0 0 0 0 0
7 7 7 7 7 7
11 11 11 11 11 11
∞ 16 16 16 16 16
∞ ∞ 18 18 18 18
∞ ∞ 19 19 19 19
0 0 0 0 0 0
二、问答题（共 3 小题，共 30 分）
1.答（1）先序遍历得到的序列为：(50,38,30,45,40,48,70,60,75,80)，中序序列是一个有 序序列，所以为：(30,38,40,45,48,50,60,70,75,80)，由先序序列和中序序列可以构造出对应 的二叉树，如下图所示。
97 38 30 40 45 48 60 70 75 80
A B
C.ACDBE
E
D.ABDEC
C
D
图 1 一个无向图
15. 设有 100 个元素的有序顺序表，用折半查找时，成功时最大的比较次数是
。
A.25 B.50 C.10 D.7 16. 已知一个长度为 16 的顺序表，其元素按关键字有序排序，若采用折半查找法查找 一个不存在的元素，则平均关键字比较的次数是 。 A.70/17 B.70/16 C.60/17 D.60/16 17. 以下关于 m 阶 B-树的叙述中正确的是 。 A.每个节点至少有两棵非空子树 B.树中每个节点至多有 m/2-1 个关键字 C.所有叶子节点均在同一层上 D.当插入一个关键字引起 B-树节点分裂时，树增高一层 18. 为提高散列（哈希）表的查找效率，可以采取的正确措施是 。 Ⅰ.增大装填（载）因子 Ⅱ.设计冲突（碰撞）少的散列函数 Ⅲ.处理冲突（碰撞）时避免产生聚集（堆积）现象 A.仅Ⅰ B.仅Ⅱ C.仅Ⅰ、Ⅱ D.仅Ⅱ、Ⅲ 19. 数据序列{8,9,10,4,5,6,20,1,2}只能是 的两趟排序后的结果。 A.简单选择排序 B.冒泡排序 C.直接插入排序 D.堆排序 20. 用某种排序方法对顺序表{24,88,21,48,15,27,69,35,20}进行排序，各趟元素序列的 变化情况如下： （1）{24,88,21,48,15,27,69,35,20} （2）{20,15,21,24,48,27,69,35,88} （3）{15,20,21,24,35,27,48,69,88} （4）{15,20,21,24,27,35,48,69,88}
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
A. 1 和 5 B. 2 和 4 C. 4 和 2 D. 5 和 1 9. 一棵深度为 h（h≥1）的完全二叉树至少有 A 个结点。 h-1 h A. 2 B. 2 h C. 2 +1 D. 2h-1+1 10. 一棵含有 n 个结点的线索二叉树中，其线索个数为 C 。 A. 2n B. n-1 C. n+1 D. n 11. 设一棵哈夫曼树中有 1999 个结点，该哈夫曼树用于对 C 码。
（1）{24,88,21,48,15,27,69,35,20} （2）{20,15,21,24,48,27,69,35,88} （3）{15,20,21,24,35,27,48,69,88} （4）{15,20,21,24,27,35,48,69,88} 则所采用的排序方法是 A 。 A. 快速排序 C. 直接插入排序 20. 以下序列是堆的是 C 。 A. {75,65,30,15,25,45,20,10} C. {75,45,65,30,15,25,20,10}
字。 A. 1 B. m/2 C. m/2-1 D. m/2+1 17. 哈希查找方法一般适用于 D 情况下的查找。 A. 查找表为链表 B. 查找表为有序表 C. 关键字集合比地址集合大得多 D. 关键字集合与地址集合之间存在着某种对应关系。 18. 对含有 n 个元素的顺序表采用直接插入排序方法进行排序， 在最好情况下算法 的时间复杂度为 A 。 A. O(n) B. O(nlog2n) 2 C. O(n ) D. O( n ) 19. 用某种排序方法对数据序列{24,88,21,48,15,27,69,35,20}进行递增排序， 元素序 列的变化情况如下：
个字符进行编
D
A. 999 B. 998 C. 1000 D. 1001 12. 一个含有 n 个顶点的无向连通图采用邻接矩阵存储， 则该矩阵一定是 A 。 A. 对称矩阵 B. 非对称矩阵 C. 稀疏矩阵 D. 稠密矩阵 13. 设无向连通图有 n 个顶点 e 条边，若满足 A ，则图中一定有回路。 A. e≥n B. e<n C. e=n-1 D. 2e≥n 14. 对于 AOE 网的关键路径，以下叙述 D 是正确的。 A. 任何一个关键活动提前完成，则整个工程一定会提前完成 B. 完成整个工程的最短时间是从源点到汇点的最短路径长度 C. 一个 AOE 网的关键路径一定是唯一的 D. 任何一个活动持续时间的改变可能会影响关键路径的改变 15. 设有 100 个元素的有序表，用折半查找时，不成功时最大的比较次数是 。 A. 25 B. 50 C. 10 D. 7 16. 在一棵 m 阶 B-树中删除一个关键字会引起合序 B. {75,65,45,10,30,25,20,15} D. {75,45,65,10,25,30,20,15}
二、问答题（共 4 小题，每小题 10 分，共计 40 分） 1. 如果对含有 n（n>1）个元素的线性表的运算只有 4 种：删除第一个元素；删除 最后一个元素；在第一个元素前面插入新元素；在最后一个元素的后面插入新元素， 则最好使用以下哪种存储结构，并简要说明理由。 （1）只有尾结点指针没有头结点指针的循环单链表 （2）只有尾结点指针没有头结点指针的非循环双链表 （3）只有头结点指针没有尾结点指针的循环双链表 （4）既有头结点指针也有尾结点指针的循环单链表 2. 已知一棵度为 4 的树中，其度为 0、1、2、3 的结点数分别为 14、4、3、2，求 该树的结点总数 n 和度为 4 的结点个数，并给出推导过程。 3. 有人提出这样的一种从图 G 中顶点 u 开始构造最小生成树的方法： 假设 G=(V，E)是一个具有 n 个顶点的带权连通无向图，T=(U，TE)是 G 的最小生 成树，其中 U 是 T 的顶点集，TE 是 T 的边集，则由 G 构造从起始顶点 u 出发的最小 生成树 T 的步骤如下： （1）初始化 U={u}。以 u 到其他顶点的所有边为候选边。 （2）重复以下步骤 n-1 次，使得其他 n-1 个顶点被加入到 U 中。 从候选边中挑选权值最小的边加入到 TE， 设该边在 V-U 中的顶点是 v，将 v 加入 U 中。 考查顶点 v，将 v 与 V-U 顶点集中的所有边作为新的候选边。 若此方法求得的 T 是最小生成树，请予以证明。若不能求得最小边，请举出反例。 4. 有一棵二叉排序树按先序遍历得到的序列为： (12,5,2,8,6,10,16,15,18,20)。回答 以下问题： （1）画出该二叉排序树。 （2）给出该二叉排序树的中序遍历序列。 （3）求在等概率下的查找成功和不成功情况下的平均查找长度。 三、算法设计题（每小题 10 分，共计 30 分） 1. 设 A 和 B 是两个结点个数分别为 m 和 n 的单链表（带头结点） ，其中元素递增 有序。设计一个尽可能高效的算法求 A 和 B 的交集，要求不破坏 A、B 的结点，将交 集存放在单链表 C 中。给出你所设计的算法的时间复杂度和空间复杂度。 2. 假设二叉树 b 采用二叉链存储结构，设计一个算法 void findparent(BTNode *b,ElemType x,BTNode *&p)求指定值为 x 的结点的双亲结点 p， 提示， 根结点的双亲为 NULL，若在 b 中未找到值为 x 的结点，p 亦为 NULL。
武汉大学计算机学院 2010 年－2011 学年第二学期“数据结构”考试试题（A） 要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要 写上姓名和学号。 一、单项选择题（每小题 1.5 分，共计 30 分） 1. 数据结构是指 D 。 A. 一种数据类型 B. 数据的存储结构 C. 一组性质相同的数据元素的集合 D. 相互之间存在一种或多种特定关系的数据元素的集合 2. 以下算法的时间复杂度为 A 。 void fun(int n) { int i=1; while (i<=n) i++; } A. O(n) B. O( n ) C. O(nlog2n) D. O(log2n) 3. 在一个长度为 n 的有序顺序表中删除元素值为 x 的元素时，在查找元素 x 时采 用二分查找，此时的时间复杂度为 B 。 A. O(n) B. O(nlog2n) 2 C. O(n ) D. O( n ) 4. 在一个带头结点的循环单链表 L 中，删除元素值为 x 的结点，算法的时间复杂 度为 A 。 A. O(n) B. O( n ) C. O(nlog2n) D. O(n2) 5. 若一个栈采用数组 s[0..n-1]存放其元素，初始时栈顶指针为 n，则以下元素 x 进 栈的正确操作是 C 。 A.top++;s[top]=x; B.s[top]=x;top++; C.top--;s[top]=x; B.s[top]=x;top--; 6. 中缀表达式 “2*(3+4)-1” 的后缀表达式是 B ， 其中#表示一个数值的结束。 A. 2#3#4#1#*+B. 2#3#4#+*1#C. 2#3#4#*+1#D. -+*2#3#4#1# 7. 设环形队列中数组的下标为 0～N-1， 其队头、 队尾指针分别为 front 和 rear （front 指向队列中队头元素的前一个位置， rear 指向队尾元素的位置） ，则其元素个数为 D 。 A. rear-front B. rear-front-1 C. (rear-front)％N+1 D. (rear-front+N)％N 8. 若用一个大小为 6 的数组来实现环形队列， 队头指针 front 指向队列中队头元素 的前一个位置，队尾指针 rear 指向队尾元素的位置。若当前 rear 和 front 的值分别为 0 和 3， 当从队列中删除一个元素， 再加入两个元素后， rear 和 front 的值分别为 B 。