华中师范大学《数据结构(华师)》期末考试必备题集

奥鹏期末考核

31501–华中师范大学《数据结构(华师)》奥鹏期末考试题库合集

单选题：
（1）非空循环链表head 的尾结点 p 满足下列( )条件。
A.head->next==p
B.head==p
C.p->next==head
D.p->next==nil
答案问询微信：424329

（2）具有4个顶点的无向完全图有( )边。
A.20
B.12
C.6
D.8
答案问询微信：424329

（3）一个向量的第一个元素的地址是100,每个元素的长度是2 ,则第五个元素的地址是( )。
A.102
B.110
C.108
D.120
答案问询微信：424329

（4）一个栈的输入序列是a,b,c,d,e ,则不可能输出是( )。
A.ecdab
B.cdeba
C.decba
D.abcde
答案问询微信：424329

（5）已知二叉树的前、中根序列分别是abdefcg 和 defbagc,则该二叉树的后根遍历序列是( )。
A.defbgca
B.fedbgca
C.abcdefg
D.gfedcba
答案问询微信：424329

（6）具有6个顶点的无向图至少要有( )条边才能确保是一个连通图。
A.4
B.5
C.6
D.7
答案问询微信：424329

（7）已知一个顺序存储的线性表,设每个结点需占m个存储单元,若第一个结点的地址为da1,则第i个结点的地址为( )
A.da1+(i-1)*m
B.da1+i*m
C.da1-i*m
D.da1+(i+1)*m
答案问询微信：424329

（8）在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是( )
A.访问第i个结点(1<=i<=n)和求第i个结点的直接前趋(2<=i<=n)
B.在第i个结点后插入一个新的结点(1<=i<=n)
C.删除第i个结点(1<=i<=n)
D.将n个结点从小到大排序.
答案问询微信：424329

（9）某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用( )存储方式最节省运算时间。
A.单链表
B.仅有头指针的单循环链表
C.双链表
D.仅有尾指针的单循环链表
答案问询微信：424329

（10）一个递归算法必须包括( )。
A.递归部分
B.终止条件和递归部分
C.迭代部分
D.终止条件和迭代部分
答案问询微信：424329

（11）关二叉树下列说法正确的是( )
A.二叉树的度为2
B.一棵二叉树的度可以小于2
C.二叉树中至少有一个结点的度为2
D.二叉树中任何一个结点的度都为2
答案问询微信：424329

（12）n个结点的完全有向图含有边的数目( )。
A.n*n
B.n* (n + 1)
C.n / 2
D.n*(n – l)
答案问询微信：424329

（13）某堆栈的输入序列为a ,b,c ,d下面的四个序列中,不可能是它的输出序列的是( )。
A.a，c，b，d
B.b，c，d，a
C.c，d，b，a
D.d，c，a，b
答案问询微信：424329

（14）若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法的时间复杂度为( ) (1<=i<=n+1)。
A.O(0)
B.O(1)
C.O(n)
D.O(n2)
答案问询微信：424329

（15）二叉树中第5层上的结点个数最多为( )
A.8
B.15
C.16
D.32
答案问询微信：424329

（16）堆的形状是一棵( )。
A.二叉排序树
B.满二叉树
C.完全二叉树
D.平衡二叉树
答案问询微信：424329

（17）在一棵具有n个结点的二叉树中,所有结点的空子树个数等于( )。
A.n
B.n-1
C.n+1
D.2*n
答案问询微信：424329

（18）有向图的一个顶点的度为该顶点的( )。
A.入度
B.出度
C.入度与出度之和
D.(入度＋出度)/2
答案问询微信：424329

（19）对线性表进行折半查找时,要求线性表必须( )。
A.以顺序方式存储
B.以链接方式存储
C.以顺序方式存储，且元素按关键字有序排序
D.以链接方式存储，且元素按关键字有序排序
答案问询微信：424329

（20）在一个有向图中,所有顶点的度数之和等于所有弧数的( )倍。
A.3
B.2
C.1
D.1/2
答案问询微信：424329

（21）对于顺序存储的有序表(5, 12, 20, 26, 37, 42, 46, 50, 64),为查找元素26,若采用折半查找,需要比较( )次才能查找成功。
A.3
B.4
C.5
D.6
答案问询微信：424329

（22）对于只在表的首、尾进行插入操作的线性表,宜采用的存储结构为( )
A.顺序表
B.用头指针表示的单循环链表
C.用尾指针表示的单循环链表
D.单链表
答案问询微信：424329

（23）100个元素的排序数组分别进行二分查找和顺序查找,在查找失败的情况下,( )的比较次数较多。
A.二分查找
B.顺序查找
C.一样多
D.不一定
答案问询微信：424329

（24）有6个元素6,5,4,3,2,1的顺序进栈,问下列哪一个不是合法的出栈序列( )
A.5,4,3,6,1,2
B.4,5,3,1,2,6
C.3,4,6,5,2,1
D.2,3,4,1,5,6
答案问询微信：424329

（25）在下列排序算法中,时间复杂度为O(nlogn)的是( )
A.冒泡排序
B.简单选择排序
C.直接插入排序
D.堆排序
答案问询微信：424329

（26）在一棵三元树中度为3的结点数为2个,度为2的结点数为1个,度为1的结点数为2个,则度为0的结点数为( )个。
A.4
B.5
C.6
D.7
答案问询微信：424329

（27）在数据结构中,从逻辑上可以把数据结构分为( )。
A.动态结构和静态结构
B.紧凑结构和非紧凑结构
C.线性结构和非线性结构
D.内部结构和外部结构
答案问询微信：424329

（28）如果最常用的操作是取第i个结点及其前驱,则采用( )存储方式最节省时间。
A.单链表
B.双链表
C.单循环链表
D.顺序表
答案问询微信：424329

（29）在长度为n的顺序表的第i个位置上插入一个元素(1≤i≤n+1),元素的移动次数为( )。
A.n–i+1
B.n–i
C.i
D.i–1
答案问询微信：424329

（30）在n个结点的线性表的数组实现中,算法的时间复杂度是O(1)的操作是( )。
A.访问第i(1=i=n)个结点和求第i个结点的直接前驱(1i=n)
B.在第i(1=i=n)个结点后插入一个新结点
C.删除第i(1=i=n)个结点
D.以上都不对
答案问询微信：424329

（31）在单链表指针为p的结点之后插入指针为s的结点,正确的操作是( )。
A.p-next=s;s-next=p-next
B.s-next=p-next ;p-next=s;
C.p-next=s;p-next=s-next
D.p-next=s-next;p-next=s
答案问询微信：424329

（32）若栈采用顺序存储方式存储,现两栈共享空间V[1 m],top[1]、top[2]分别代表第1和第2个栈的栈顶,栈1的底在V[1],栈2的底在V[m],则栈满的条件是( )。
A.|top[2]-top[1]|=0
B.top[1]+1=top[2]
C.top[1]+top[2]=m
D.top[1]=top[2]
答案问询微信：424329

（33）队列的“先进先出”特性是指( )。
A.最早插入队列中的元素总是最后被删除
B.当同时进行插入、删除操作时,总是插入操作优先
C.每当有删除操作时,总是要先做一次插入操作
D.每次从队列中删除的总是最早插入的元素
答案问询微信：424329

（34）在线索化树中,每个结点必须设置一个标志来说明它的左、右链指向的是树结构信息,还是线索化信息,若0标识树结构信息,1标识线索,对应叶结点的左右链域,应标识为( )。
A.00
B.01
C.10
D.11
答案问询微信：424329

（35）在一个无向图中,所有顶点的度数之和等于所有边数的( )倍。
A.1/2
B.1
C.2
D.4
答案问询微信：424329

（36）采用邻接表存储的图的深度优先遍历算法类似于二叉树的( )。
A.先序遍历
B.中序遍历
C.后序遍历
D.按层遍历
答案问询微信：424329

（37）顺序查找法适合于存储结构为( )的线性表。
A.散列存储
B.顺序存储或链式存储
C.压缩存储
D.索引存储
答案问询微信：424329

（38）下面关于B树和B+树的叙述中,不正确的结论是( )。
A.B树和B+树都能有效的支持顺序查找
B.B树和B+树都能有效的支持随机查找
C.B树和B+树都是平衡的多叉树
D.B树和B+树都可用于文件索引结构
答案问询微信：424329

多选题：
（1）对于单链表表示法,以下说法正确的是()
A.指向链表的第一个结点的指针，称为头指针
B.单链表的每一个结点都被一个指针所指
C.任何结点只能通过指向它的指针才能引用
D.尾指针变量具标识单链表的作用，故常用尾指针变量来命名单链表
答案问询微信：424329

（2）对于顺序表的优缺点,以下说法正确的是()
A.无需为表示结点间的逻辑关系而增加额外的存储空间
B.可以方便地随机存取表中的任一结点
C.插入和删除运算较方便
D.由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)
答案问询微信：424329

（3）以下说法错误的是()
A.数据元素是数据的最小单位
B.数据项是数据的基本单位
C.数据结构是带有结构的各数据项的集合
D.数据结构是带有结构的数据元素的集合
答案问询微信：424329

（4）以下说法正确的是()
A.二叉树可以是空集
B.二叉树的任一结点至多有两棵子树
C.二叉树与树具有相同的树形结构
D.二叉树的子树有次序之分
答案问询微信：42432奥鹏期末考核9

（5）以下说法正确的是()
A.对于线性表来说，定位运算在顺序表和单链表上的量级均为O（n）
B.读表元运算在顺序表上只需常数时间O（1）便可实现，因此顺序表是一种随机存取结构
C.在链表上实现读表元运算的平均时间复杂性为O（1）
D.插入、删除操作在链表上的实现可在O（1）时间内完成
答案问询微信：424329

（6）下列说法正确的是()
A.栈是限定在表尾进行插入或删除操作的线性表
B.栈是限定在表头进行插入或删除操作的线性表
C.对列是先进先出的线性表
D.栈是后进先出的线性表
答案问询微信：424329

（7）二叉树的遍历方式有()
A.先序遍历
B.中序遍历
C.后序遍历
D.线索遍历
答案问询微信：424329

（8）下面几个符号串编码集合中,是前缀编码的是()
A.{0,10,110,1111}
B.{11,10,001,101,0001}
C.{00,010,0110,1000}
D.{b,c,aa,ac,aba,abb,abc}
答案问询微信：424329

（9）下面关于哈希(Hash)查找的说法不正确的是()
A.哈希函数构造的越复杂越好，因为这样随机性好，冲突小
B.除留余数法是所有哈希函数中最好的
C.不存在特别好与坏的哈希函数，要视情况而定
D.若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可
答案问询微信：424329

（10）图的存储结构有()
A.邻接矩阵
B.邻接表
C.数组表示法
D.十字链表
答案问询微信：424329

（11）下面关于串的的叙述中,正确的是()
A.串是字符的有限序列
B.空串是由空格构成的串
C.模式匹配是串的一种重要运算
D.串既可以采用顺序存储，也可以采用链式存储
答案问询微信：424329

（12）某堆栈的输入序列为a, b,c,d,下面的四个序列中,可能是它的输出序列的是()
A.a，c，b，d
B.b, c，d，a
C.c, d，b, a
D.d, c，a，b
答案问询微信：424329

（13）数据结构包含四种基本结构,它们是( )
A.集合结构
B.线性结构
C.树形结构
D.图状结构
答案问询微信：424329

（14）在下列情况中,不能为二叉树的是()
A.每个结点至多有两棵子树的树
B.哈夫曼树
C.每个结点至多有两棵子树的有序树
D.每个结点只有一棵右子树
答案问询微信：424329

（15）依据所有数据成员之间的逻辑关系的不同，数据结构分为（ ）
A.非线性结构
B.逻辑结构
C.物理结构
D.线性结构
答案问询微信：424329

判断题：
（1）( )二叉排序树中每个结点的关键字值大于其左非空孩子(若存在的话)的关键字值,且小于其右非空孩子(若存在的话)结点的关键字值。
答案问询微信：424329

（2）( )算法必须具备的5个特征是:有穷性、确定性、可行性、有0或多个输入量,至少有1个输出量。
答案问询微信：424329

（3）哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。
答案问询微信：424329

（4）空栈就是所有元素都为0的栈。
答案问询微信：424329

（5）n*n对称矩阵经过压缩存储后占用的存储单元是原来的1/2。
答案问询微信：424329

（6）对于一个非空二叉树,它的根节点作为第一层,则第i层上最多能有2i-1个结点。
答案问询微信：424329

（7）稀疏矩阵压缩存储后,必会失去随机存取功能。
答案问询微信：424329

（8）广义表中原子个数即为广义表的长度。
答案问询微信：424329

（9）一个循环链表可以由所给定的头指针或者尾指针惟一地确定。
答案问询微信：424329

（10）中序遍历二叉排序树可以得到一个有序的序列。
答案问询微信：424329

（11）对于同一组结点,由于建立二叉排序树时插入结点的先后次序不同,所构成的二叉排序树的形态及深度也不同,所以含有n个结点的二叉排序树不唯一。
答案问询微信：424329

（12）层次遍历初始堆可以得到一个有序的序列。
答案问询微信：424329

（13）快速排序是排序算法中平均性能最好的一种排序。
答案问询微信：424329

（14）深度为6的二叉树最多有64个结点。
答案问询微信：424329

（15）顺序存储方式只能用于存储线性结构。
答案问询微信：424329

（16）队列和栈都是运算受限的线性表。
答案问询微信：424329

（17）散列法存储的基本思想是由关键码的值决定数据的存储地址。
答案问询微信：424329

（18）任何一棵二叉树中至少有一个结点的度为2。
答案问询微信：424329

（19）快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。
答案问询微信：424329

（20）空格也是合法字符,它可以出现在较长的字符串中,也可以单独出现 。
答案问询微信：424329

（21）线性表的逻辑顺序与存储顺序总是一致的。( )
答案问询微信：424329

（22）存储无向图的邻接矩阵是对称的,故只存储邻接矩阵的下(或上)三角部分即可。( )
答案问询微信：424329

（23）若频繁地对线性表进行插入和删除操作,该线性表应该采用顺序结构。( )
答案问询微信：424329

（24）数组的基本操作有存取、修改、检索、排序、插入与删除操作。( )
答案问询微信：424329

（25）在一个循环队列中,队首指针指向队首元素的前一个元素。( )
答案问询微信：424329

（26）图的广度优先搜索算法类似于二叉树的前序遍历。( )
答案问询微信：424329

简答题：
（1）算法的5个重要特征是什么?
答案问询微信：424329

（2）简述二分查找的思想?
答案问询微信：424329

（3）请用递归方法写出归并排序法的主要思想和算法。
答案问询微信：424329