数据结构课程复习题

选择题

数据结构被形式地定义为<D,R>,其中D是( )的有限集。
- A 算法 B 数据元素 C 数据操作 D 逻辑结构
数据结构被形式地定义为<D,R>,其中R是( )的有限集.
- A 操作 B 映像 C 存储 D 关系
以下不是顺序表的优点的是（　　）
- A、便于随机存取 B、花费的存储空间比链表少 C、便于插入与删除 D、数据元素的物理顺序与逻辑顺序相同
在数据结构的讨论中把数据结构从逻辑上分为（）。
- A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构
用单链表表示的链式队列的队头在链表的（）位置。
- A.链头　　　 B.链尾　　　 C.链中
线性表是具有n个（）的有限序列（n≠0)
- A.表元素 B.字符 C.数据元素　　　　　　　 D.数据项
采用线性链表表示一个向量时，要求占用的存储空间地址（）。
- A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 可连续可不连续
向一个有127个元素的有序的顺序表中插入一个新元素并保持原来顺序不变，平均要移动( )个元素。
- A.8 B.63.5 C.63 D.7
若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用( )存储方式最节省运算时间。
- A 单链表 B双链表 C 单循环链表 D带头结点的双循环链表
链表不具有的特点是( ).
- A 可随机访问任一元素 B插入删除不需要移动元素 C 不必事先估计存储空间 D所需空间与线性表长度成正比
在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。
1. O(n) B. O(n/2) C. O(1) D. O(n²)
带头结点的单链表first为空的判定条件是( )：
1. first == NULL; B. first->link == NULL; C. first->link == first; D. first != NULL;
线性表的顺序存储结构是一种( ) 的存储结构.
- A 随机存取 B 顺序存取 C 索引存取 D 散列存取
线性表的链式存储结构是一种 ( )的存储结构.
- A 随机存取 B 顺序存取 C 索引存取 D 散列存取
给定有n个元素的无序顺序表,建立一个有序单链表的时间复杂度为( ) .
- A O(1) B O(n) C O(n²) D O(nlog₂n)
在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度为( ) .
- A O(1) B O(n) C O(n²) D O(nlog₂n)
链表表示线性表的优点是（　　）
- A、便于随机存取 B、花费的存储空间比顺序表少 C、便于插入与删除 D、数据元素的物理顺序与逻辑顺序相同
一个栈的入栈序列是 a,b,c,d,e,则栈的不可能的输出序列是( )。
- A edcba B decba C dceab D abcde
当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。
1. n-2 B. n-1 C. n D. n+1
将一个递归算法改为对应的非递归算法时，通常需要使用（）。
- A: 栈 B: 队列 C: 循环队列 D: 优先队列
一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（）。
- A: 4, 3, 2, 1 B: 2, 4, 3, 1 C: 1, 2, 3, 4 D: 3, 2, 1, 4
在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（）。
- A: ( front - rear + 1) % m B: ( rear - front + 1) % m C: ( front - rear + m) % m D: ( rear - front + m) % m
从一个顺序队列删除元素时，首先要（　　　）。
1. 前移一位队首指针 B. 后移一位队首指针 C. 取出队首指针所指位置上的元素 D. 取出队尾指针所指位置上的元素
在系统实现递归调用时需利用递归工作记录保存实际参数的值。在传值参数情形，需为对应形式参数分配空间，以存放实际参数的副本；在引用参数情形，需保存实际参数的（），在被调用程序中可直接操纵实际参数。
1. 空间 B. 副本 C. 返回地址 D. 地址
判定一个循环队列Q（最多有MAXQSIZE个元素）为空的条件为( ) 。
- A Q.front==Q.rear B Q.front!=Q.rear C Q.front==(Q.rear+1)%MAXQSIZE D Q.front!=(Q.rear+1)%MAXQSIZE
判定一个循环队列Q（最多有MAXQSIZE个元素）为满的条件为( ) 。
- A Q->front==Q->rear B Q->front!=Q->rear C Q->front==(Q->rear+1)%MAXQSIZE D Q->front!=(Q->rear+1)%MAXQSIZE
若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,pn,若p1=n,则pi为( ) .
- A i B n-i C n-i+1 D 不确定
一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列？（）
1. 1，3，2，4 B. 2，3，4，1 C. 4，3，1，2 D. 3，4，2，1
串是( )。
- A 不少于一个字母的序列 B任意个字母的序列 C 不少于一个字符的序列 D有限个字符的序列
设有两个串p和q，求q在p中首次出现的位置的运算称为( )。
- A 连接 B 模式匹配 C 求子串 D 求串长
串是一种特殊的线性表，其特殊性体现在( ) 。
- A 可以顺序存储 B 数据元素是一个字符 C 可以链式存储 B 数据元素是多个字符
设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按行序放在一维数组B[1，n(n+1)/2]中,对下三角部分中任一元素aij(i>=j),在一维数组B中的下标位置是( )。
- A i(i-1)/2+j-1 B i(i-1)/2+j C i(i+1)/2+j-1 D i(i+1)/2+j
三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A[３][4][5]的存储地址为( )。
- A 356 B 358 C 360 D 362
广义表(a,b,c,d)的表尾是( ).
- A d B (d) C b,c,d D (b,c,d)
广义表(a,b,c,d)的表头是( ).
- A a B (a) C a,b,c D (a,b,c)
设一个广义表中结点的个数为n,则广义表深度算法的时间复杂度为( )。
- A.O(1) B.O(n) C. O(n²) D. O(log₂N)
下列广义表中，深度为2的有（　　　）。
- A.(a，b)　　　　　　　　　 B.((c，(a，b))，d) C. (c，(a，b))　　　　　　D. ((a，b)，(c，(a，b)))
高度为h的满二叉树（仅含根结点的二叉树高度为零）的结点最少是多少（）
- A、h＋1 B、2^h＋1 C2^h+1-1 D、2^h
一棵具有５层满二叉树中节点总数为（　　）。
- A、３１　 B、３２　 C、３３　 D、１６
对某二叉树进行前序遍右的结果为ABDEFC，中序遍历的结果为DBFEAC,则后序周游的结果为（）
- A.DBFEAC　　　　　　　 B.DFEBCA C.BDFECA 　　　　　　　D.BDEFAC
在有n个叶子结点的哈夫曼树中，其结点总数为( )。
- A 不确定 B 2n C 2n+1 D 2n-1
任何一个无向连通图的最小生成树( )。
- A 只有一棵 B 有一棵或多棵 C 一定有多棵 D 可能不存在
将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为( )。
- A 98 B 99 C 50 D 48
若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是（）
1. 9 B. 11 C. 12 D. 不确定
在一棵树中，（）没有前驱结点。
1. 分支结点 B. 叶结点 C. 树根结点 D. 空结点
在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。
1. 2 B. 1 C. 0 D. –1
下列说法中错误的是（　　）
- A.n个结点的树的各结点度数之和为n-1 B. n个结点的无向图最多有n*(n-1)条边 C. 用相邻矩阵存储图时所需存储空间大小与图的结点数有关，而与边数无关 D. 散列表中碰撞的可能性大小与负载因子有关
一个二叉树的前序遍历序列为ABCDEFG，它的后序遍历序列可能是( ).
1. CABDEFG B. ABCDEFG C. DACEFBG D.CDBFGEA
已知二叉树的后序遍历序列为41253,中序遍历序列为45213,则它的前序遍历序列为( ).
- A 13254 B 45312 C 45123 D 35421
在线索化二叉树中,t所指的结点没有左子树的充要条件是( ) .
- A t->left=NULL B t->ltag=1 C t->left=NULL 且 t->ltag=1 D 以上都不对
在线索化二叉树中,t所指的结点没有右子树的充要条件是( ).
- A t->right=NULL B t->rtag=1 C t->right=NULL 且 t->rtag=1 D 以上都不对
n个顶点的连通图至少有( )条边。
- A.n-1　　　　B.n C.n+1　　　　D.0
设无向图的顶点个数为n，则该图最多有（）条边。
- A.n-1 　　　　　　　　　B.n(n-1)/2 C.n(n+1)/2　　　　　　 D.0
采用邻接表存储的图的宽度优先遍历算法类似于二叉树的( ) 。
- A 先序遍历 B 中序遍历 C 后序遍历 D 按层遍历
可以判断一个有向图中含有环（回路）的方法为( )。
- A 广度优先遍历 B 拓扑排序 C 求最短路径 D 求关键路径
采用邻接表存储的图的深度优先遍历算法类似于二叉树的( ) 。
- A 先序遍历 B 中序遍历 C 后序遍历 D 按层遍历
一个具有8个顶点的有向图中，所有顶点的入度之和与所有顶点的出度之和的差为( )。
- A 16 B 8 C 0 D 2
在有向图中每个顶点的度等于该顶点的（）。
1. 入度 B. 出度 C. 入度与出度之和 D. 入度与出度之差
折半查找要求查找表中各元素的关键字值必须是( )排列。
- A 递增或递减 B递增 C递减 D 无序
采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（）。
- A: n B: n/2 C: (n-1)/2 D: (n+1)/2
下述排序算法中，稳定的是（　　　）。
- A、直接选择排序　B、表插入排序　　C、快速排序 D、堆排序
对线性表进行折半查找时，必须要求线性表( ) 。
- A 以顺序方式存储 B 以链接方式存储 C 以顺序方式存储，且结点按关键字有序排列 D 以链接方式存储，且结点按关键字有序排列
顺序查找法适合于存储结构为 ( )的线性表。
- A 散列存储 B 顺序存储或链接存储 C 压缩存储 D 索引存储
采用折半查找方法查找长度为n的线性表时，每个元素的平均查找长度为( ) .
- A O(n²) B O(nlog₂n) C O(n) D O(log₂n)
对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（）的值除以9。
1. 20 B. 18 C. 25 D. 22
当α的值较小时，散列存储通常比其他存储方式具有（）的查找速度。
1. 较慢 B. 较快 C. 相同
如果只想得到1024个元素序列中第5个最小元素之前的部分排序的序列，用（）方法最快。
- A.起泡排序　　　　　　　 B.快速排序 C.简单选择排序　　　　　D.堆排序
如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（）就是不稳定的排序方法。
- A.起泡排序　　　　　　　B.归并排序 C.直接插入排序　　　　　 D.简单选择排序
５个不同的数据元素进行直接插入排序，最多需要进行（　　）次比较。
- A、８　　B、１０　 C、１５　　D、２５
下列序列中，( )是执行第一趟快速排序后得到的序列（排序的关键字类型是字符串）。
- A [da,ax,eb,de,bb]ff[ha,gc] B [cd,eb,ax,da]ff[ha,gc,bb] C [gc,ax,eb,cd,bb]ff[da,ha] D [ax,bb,cd,da]ff[eb,gc,ha]
对于关键字值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从关键字值为( )的结点开始。
- A 100 B 12 C 60 D 15
排序方法中，从未排序序列中筛选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为( )。
- A 希尔排序 B 起泡排序 C 插入排序 D 选择排序
排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放在已排序序列的正确位置上的方法，称为( )。
- A 希尔排序 B 起泡排序 C 插入排序 D 选择排序
下列排序方法中，哪一种方法的比较次数与纪录的初始排列状态无关？（）
1. 直接插入排序 B. 起泡排序 C. 快速排序 D. 直接选择排序
对n个记录的文件进行二路归并排序，总的时间代价为（　　）
５个不同的数据元素进行直接插入排序，最多需要进行（　　）次比较。
在基于排序码比较的排序算法中，（）算法的最坏情况下的时间复杂度不高于O(nlog2n)。
1. 起泡排序 B. 希尔排序 C. 归并排序 D. 快速排序

判断题

只允许最下面的二层结点的度数小于2的二叉树是完全二叉树。（　　　）
n个结点的有向图，若它有n(n－1)条边，则它一定是强连通的。（　　　）
多维数组元素之间的关系是线性的。（　　　）
相邻矩阵表示图所用的存储空间大小与图的边数成正比。（）
霍夫曼树一定是满二叉树。（）
栈是一种线性结构。（　　）
顺序表中所有结点的类型必须相同。（　　　）
链接表中所有灵活利用存储空间，所以链表都是紧凑结构。（　　　）
数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。（　　　）
链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。（　　　）
在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。（　）
通常递归的算法简单、易懂、容易编写，而且执行的效率也高。（　　　）
一个广义表的表尾总是一个广义表。（　　　）
当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。（　　　）
对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(h)。（　　　）
存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。（　　　）

简答题

算法的时间复杂度和空间复杂度的度量方法。
稀疏的一元多项式的线性表表示。
已知栈的入栈序列，求栈可能的出栈序列。（队列）
在使用栈求表达式的值的算法中，描述栈OPND和OPTR的变化情况。
画出循环队列的入队和出队过程示意图。
如果已知多维数组的首地址和数据元素的类型，求任一元素的地址。反之亦然。
画出给定的稀疏矩阵的三元组（带行逻辑联结信息）表示法和十字链表表示法。
画出广义表的头尾链表存储表示示意图。
二叉树的五个重要性质。
写出二叉树的先序、中序和后序遍历序列。已知先序、中序求后序。
树、森林与二叉树的相互转换。
构造Hufman树，求Huffman编码。
画出给定图的邻接表表示示意图。
求图的深度和广度优先遍历序列。
求有向图的拓扑序列。
如何求顺序查找法和二分查找法的平均查找长度。
画出二叉排序树的建立过程。
画出AVL树的建立过程，主要画出它的平衡调整过程。
指出几种构造哈希函数的常用方法和解决冲突的方法。
已知一组关键字，按指定的哈希函数和指定的处理方法构造哈希表．
按照给定的排序方法,写出排序的每一趟过程.
指出各种排序过程的时间复杂度和空间复杂度.

要求必须掌握的算法

顺序表的插入元素和删除元素算法
单链表的插入和删除结点算法
双向循环链表的插入和删除结点算法
顺序栈的基本操作
链式队列的基本操作
循环队列的基本操作
栈的应用:表达式求解
串的模式匹配算法
稀疏矩阵的转置算法
二叉树的三种遍历算法(递归的)
二叉树的创建算法
图的DFS和BFS遍历算法
图的创建算法
Prim算法
Dijkstra算法
求有向图的拓扑序列
顺序查找算法
二分查找算法
二叉排序树的查找算法
直接插入排序算法
冒泡排序算法
快速排序算法
简单选择排序算法
堆排序算法
归并排序算法