【考研计算机专业课】武汉大学期末试题 数据结构2011

《数据结构》期末考试试题及答案一、单项选择题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个结点的线索二叉树上含有的线索个数为。

数据结构部分（共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 。

武汉大学计算机学院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。

武汉大学数据结构考试题(附答案)编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（武汉大学数据结构考试题(附答案)）的内容能够给您的工作和学习带来便利。

同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。

本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快业绩进步，以下为武汉大学数据结构考试题(附答案)的全部内容。

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。

1、倘若在对串的插入、删除运算中，期望运算速度最快，则应采用（ C ）。

A）顺序表示法 B）单字符为结点的单链表表示法C）等量分块表示法 D）不等量分块表示法2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a??11为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（ B ）。

A）13 B）33 C）18 D）403、如果结点A有3个兄弟，而且B为A的双亲，则B的度为（ B ）。

A）3 B）4 C）5 D）14、已知广义表L=((x,y,z),a,(u,t,w))，从L 表中取出原子项t 的操作是（ D ）。

A) Head(Head(Tail(Tail(L))))B) Tail(Head(Head(Tail(L))))C) Head(Tail(Head(Tail(L))))D)Head(Tail(Head(Tail(Tail(L)))))5、以下属于顺序存储结构优点的是（ A ）。

A) 存储密度大B) 插入运算方便C）删除运算方便D）可方便地用于各种逻辑结构的存储表示6、下面关于线性表的叙述中，错误的是哪一个？（ D ）A）线性表采用顺序存储，必须占用一片连续的存储单元。

B）线性表采用链接存储，便于插入和删除操作。

C）线性表采用链接存储，不必占用一片连续的存储单元。

D）线性表采用顺序存储，便于进行插入和删除操作。

7、对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。

这样的排序方法是（ A ）。

A）直接选择排序 B）直接插入排序C）快速排序 D）起泡排序8、下面关于线性表的叙述中，错误的是哪一个？（ D ）A）线性表采用顺序存储，必须占用一片连续的存储单元。

B）线性表采用链接存储，便于插入和删除操作。

C）线性表采用链接存储，不必占用一片连续的存储单元。

D）线性表采用顺序存储，便于进行插入和删除操作。

一、单项选择题1. 某计算机字长32位，存储容量是8MB，若按字编址，它的寻址范围是：A. 0~256K－1B. 0~512K－1C. 0~1M－1D. 0~2M－12. 浮点数加减运算过程一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤。

设浮点数的阶码和尾数均采用补码表示，且位数分别为4位和8位(均含1位符号位)。

若有两个数X=21×29/32，Y=25×5/16，则浮点加法计算X+Y的最终结果是：A．0101 11010110 B．0101 01101011C．0100 01101011 D. 发生溢出3. 十进制数5.5的单精度浮点数IEEE 754代码为:A. 01000001010110000000000000000000B. 01000000101000000000000000000000C. 01000000101011000000000000000000D. 01000000101100000000000000000000 4．某计算机的Cache共有16块，采用2路组相联映射方式，每个主存块大小为32字节，按字节编址。

主存500号单元所在主存块应装入到Cache的组号是：A．0 B．1 C．7 D．155．某计算机主存容量为64KB．其中ROM区为4KB．其余为RAM区，按字节编址；现要用2K×4位的ROM芯片和4K×8位的RAM芯片来设计该存储器，则需要上述规格的ROM 芯片数和RAM芯片数分别是：A．4、15 B．2、15 C．4、30 D. 2、306．有一个16K×l的DRAM芯片，芯片内是128×128结构，采用分散刷新方式，如果刷新间隔不超过2ms，刷新信号的周期是:A．62.5us B．15.625us C．31.25us D．2ms7．某机器字长16位，主存按字节编址，转移指令采用相对寻址，由两个字节组成，第一字节为操作码字段，第二字节为补码表示的相对位移量字段。

数据结构期末考试试题及答案一、选择题1. 以下哪种数据结构是线性存储结构？A. 树B. 图C. 链表D. 哈希表答案：C2. 在二叉搜索树中，若删除一个节点，则需要进行以下哪些操作？A. 仅删除操作B. 删除操作和调整树结构操作C. 插入操作D. 忽略操作答案：B3. 快速排序算法的时间复杂度在最坏情况下是：A. O(log n)B. O(n)C. O(n log n)D. O(n^2)答案：D4. 下面哪个排序算法适用于大数据量的排序？A. 冒泡排序B. 快速排序C. 插入排序D. 归并排序答案：D5. 哈夫曼树是一种特殊的：A. 二叉树B. 多叉树C. 哈希表D. 图答案：A二、填空题1. 链表的基本操作包括__________、__________、__________和__________。

答案：创建、插入、删除、查找2. 栈是一种后进先出（LIFO）的数据结构，其添加元素的操作称为__________，移除元素的操作称为__________。

答案：push、pop3. 在图的遍历算法中，按照遍历方向的不同，可以分为__________和__________。

答案：深度优先遍历、广度优先遍历4. 红黑树是一种自平衡的__________。

答案：二叉搜索树4. 散列表（哈希表）的主要优点是__________。

答案：查找速度快三、简答题1. 请简述数组和链表的区别及各自的优缺点。

答案：数组是一种顺序存储结构，通过索引直接访问元素，访问速度快，但是插入和删除操作需要移动大量元素，效率较低。

链表是一种非顺序存储结构，通过指针连接元素，插入和删除操作只需要改变指针，效率较高，但是访问元素需要从头开始遍历，速度较慢。

2. 请解释二分查找法的工作原理及其适用条件。

答案：二分查找法是一种在有序数组中查找特定元素的算法。

工作原理是将数组分为两部分，判断目标值与中间元素的大小关系，然后在相应的一半中继续查找，重复此过程，直到找到目标值或范围缩小到无法再分。

数据结构2011年秋季期末复习提纲期末考试形式：闭卷试卷总评成绩：试卷70%+平时30%试卷题型：1.选择题（20分），2.应用题（30分）3.程序填空题（30分）4.算法设计题（20分）每章复习要点：第1章：概念理解：数据结构，时间复杂度程序段：i=1;while(i<=n)i=i*2;第2章：表的顺序存储结构，链式存储结构（单链表、循环链表、双向链表），表的基本操作与应用，本章所占分值在15分左右，会考表的算法。

(1)顺序存储结构1、下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

2、对于顺序表的优缺点，以下说法错误的是：（）A、无需为表示节点间的逻辑关系而增加额外的存储空间；B、可以方便地随机存取表中的任一节点；C、插入和删除运算较方便；D、由于顺序表要求占用连续的空间，存储分配智能预先进行。

(2) 链式存储结构1、链表不具备的特点是？（）A．可随机访问任一节点。

B．插入删除不需要移动元素。

C．不必事先估计存储空间。

D．所需空间与其长度成正比。

2、（1) 静态链表既有顺序存储的优点，又有动态链表的优点。

所以，它存取表中第i个元素的时间与i无关。

(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。

(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。

以上错误的是（）。

A．（1）（2）B．（1）C．（1）（2）(3) D．（2）3、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是A、head==NULLB、head→next==NULLC、head→next==headD、head!=NULL4、如果对线性表的运算只有两种，即删除第一个元素，在最后一个元素后面插入新元素，最好使用（）A、只有表头指针而没有表尾指针的循环单链表B、只有表尾指针而没有表头指针的循环单链表C、非循环双链表D、循环双链表5、线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）A．O（i）B．O（1）C．O（n）D．O（i-1）第3章：栈的实现，栈的应用（数制转换，括号匹配），Hanoi塔不考，队列的实现（其中循环队列重点）。

数据结构复习题一、单项选择题1.不带头结点的单链表head为空的判断条件是( )。

A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL2.链表不具有的特点是( )。

A.可随机访问任一元素B.插入删除不需要移动元素C.不必事先估计存储空间D.所需空间与线性表长度成正比3. 设输入序列为A,B,C,D,借助一个栈不可以得到的输出序列是( )。

A. A,B,C,DB. A,C,D,BC. D,C,B,AD. D,A,B,C4.栈和队列都是（）。

A.顺序存储的线性表B.链式存储的线性表C.限制存取点的线性结构D.限制存取点的非线性结构5. 串的长度是（）。

A.串中不同字符的个数B. 串中不同字母的个数C.串中所含字符的个数且字符个数大于0D.串中所含字符的个数6. 栈和队列的主要区别在于（）。

A.它们的逻辑结构不一样B.它们的存储结构不一样C.所包含的运算个数不一样D.插入删除运算的限定不一样7.从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较（）个结点。

A.nB.n/2C.(n-1)/2D.(n+1)/28.线性表是具有n个（）的有限序列。

A. 表元素B. 字符C. 数据元素D. 信息项9.某二叉树的前序和后序序列正好相同，则该二叉树一定是（）的二叉树。

A. 空或只有一个结点B. 高度等于其结点数C. 任一结点无左孩子D. 任一结点无右孩子10.下列排序算法中,第一趟排序完毕后,其最大或最小元素一定在其最终位置上的算法是（）。

A. 归并排序B. 直接插入排序C. 快速排序D. 冒泡排序11.深度为n的二叉树中所含叶子结点的个数最多为（）个。

A.2nB.nC.2n-1D.2n-112.某数组第一个元素的存储地址为100，每个元素的长度为2，则第五个元素的地址是（）。

A.110B.108C.100D.12013.串是（）。