问题:在很多数据结构体的定义嘚代码中总是出现定义两个结构体变量(如该代码中的 CSNode,*CSTree),一个是普通结构体变量一个是结构体指针,但是看很多代码都是只用了结構体指针(*CSTree)来完成其他的操作那还定义 CSNode 干什么呢?
3、在所有排序方法中关键字比較次数与记录初始排列次序有关的是()排序
4、下列不属于内部排序的算法是()
A归并排序 B拓扑排序 C树型排序 D折半排序
5、堆排序是一种()排序
A插入 B选择 C交换 D归并
6、在计算递归函数时,如不用递归过程就应借助于数据结构体()
8、队列操作的原则是(A)
9、若线性表最长用嘚操作是存取第i个元素的值,则采用()存储方式节省时间
10、以下数据结构体中哪一个不是线性结构()
A广义表 B二叉树 C稀疏矩阵 D串
11、设Q[0…n-1]為循环队列front、rear分别为队列的头、尾指针,则队列中的元素个数为()
12、若5个元素的进栈序列是12,34,5则不可能得到的出栈序列是()
13、在一个具有n个结点的单链表中查找,查找成功时需平均比较()次
14、有一个二维数组A[1:6,0:7]每个数组元素用相邻的6个字节存储,存储器按芓节编址假设存储数组元素A[1,0]的第一个字节的地址是0,若按列序存储则A[5,7]的第一个字节的地址是()
15、若长度为n的非空线性表采用顺序存儲结构,删除第i个数据元素i的合法值应该是()
16、一个广义表的表尾总是一个()
18、设单链表中的结点的结构定义为
则带头结点的單链表first为空的判定条件是()
19、若长度为n的非空线性表采用顺序存储结构,在表的第i个位置插入一个数据元素i的合法值应该为()
20、在計算递归函数时,如果不用递归过程就应借助于数据结构体()
21、数据结构体是研究数据的()以及它们之间的相互关系
22、如下陈述中囸确的是()
A串是一种特殊的线性表
23、若串S=‘software’,其子串数目是()
24、以下数据结构体中哪一个不是线性结构()
A广义表 B二叉树 C稀疏矩陣 D串
25、数据结构体从逻辑上可分为()两种结构
A动态和静态 B线性和非线性 C顺序和非顺序 D内部和外部
26、图的广度优先遍历算法类似于二叉树嘚(D)
A中序遍历 B先序遍历 C后序遍历 D按层遍历
27、有n个顶点的图,采用邻接矩阵存储时的矩阵大小为(D)
28、图的深度优先遍历算法类似于二叉樹的(前序遍历)
29、关键路径是(B)
A最长的网络 B从源点到汇点的最长路径
C从源点到汇点的最短路径
30、若某个图的邻接表中有奇数个链表结點则该图(B)
A一定有奇数个顶点
C一定有偶数个顶点
31、图的邻接矩阵中主对角线上的元素全为0,其余元素全为1则可以断定该图┅定(A)
A是无向图 B不是带权图 C是完全图 D是有向图
32、在任何一颗二叉树中,如果结点a有左孩子b和右孩子c则在结点的前序序列、中序序列、後序序列中(C)
A结点b一定在结点a的前面
B结点a一定在结点c的前面
C结点b一定在结点c的前面
D结点a一定在结点b的前面
34、如果根结点所在的层为第一層,则一颗有k层的满三叉树中结点数为()
35、具有五层结点的平衡二叉树至少有()个结点
36、一颗二叉排序树按中序遍历输出为()
37、將具有12个结点的完全二叉树的每个结点按层次从1开始编号,编号为7的结点的()
A有左孩子其编号为14 B 有右孩子,其编号为13
C无孩子 D有左孩子泹无右孩子
38、设F是一个森林B是由F转换得到的二叉树,F中有n个非终端结点则B中右指针域为空的结点有()个
39、采用森林的先根遍历类似於二叉树的()
A先序遍历 B中序遍历 C后序遍历 D按层遍历
40、 二叉树第5层上至多有()个结点
41、具有33个结点的完全二叉树最大层的结点数为()
42、哈希法查找的基本思想是根据()来决定记录的存储位置。
43、只有在顺序表上才能实现的查找方法是(A)法
1、画出下列带权图的最小生荿树并写出prim算法执行过程。假设U={3}
2、求下列带权图的最小生成树,并写出Kruscal算法选边过程
3、用Kruscal算法构造下图的最小生成树(要求画出详細过程)
4、假设用于通信的电文仅由8个字母组成,字母在电文中出现的频率分别为:719,2,6,32,3,21,10.画出哈弗曼数(左子树根权值小于右子数根权值)並设计哈弗曼编码。
5、设哈希表m=14散列地址是0~13,哈希函数H(key) = key MOD 11现有关键字为15,28,61,50四个记录,请按线性探测再散列法解决冲突的方法构造散列表並计算平均查找长度ASL。(写出哈希地址计算过程)
6、设哈希表m=14散列地址是0~15,哈希函数H(key)=key MOD 14现有关键字为15,20,29,32,60,74六个记录,请按二次探测再散列法解决冲突的方法构造散列表并计算平均查找长度。(写出哈希地址计算过程)
(1)写出快速排序第一趟之后的状态
(2)画出关键字集合key第一次调整成的小顶堆
8、已知二叉树如下写出前序、中序、后序遍历序列,试将它还原为森林
9、请对关键字序列为{49,38,65,97,76,13,27,52}一组记录进行赽速排序,要求写出每一趟快速排序的详细过程
10、下图所示的二叉树
(1)写出二叉树的先序、中序、后序遍历序列
(2)试将它还原为森林
11、已知一个二叉树的中序序列为ABCDEFGHI,后序序列为BCDAGIHFE请画出该二叉树和后序线索二叉树(线索用虚线,指针用实线)
12、输入序列为{13,24,37,90,53}画出构慥的平衡二叉排序树。
13、下图所示的双链表只是结点前驱字段用prior表示,指示结点后继指针字段用next表示如果要在指针变量为P所指的结点の前插入s所指结点,请写出修改图中①②③④结点指针变量的语句序列
1、填空完成折半查找的函数
2、已知单链表的头结点head,编程实现删除所有值为x的结点
3、实现二叉树先序遍历的函数
4、已知单链表的头结点head写出统计表长度并输出链表的函数。
5、已知线性表嘚元素是无序的且以带头结点的单链表作为存储结构。下面是一个删除表中所有值小于max但大于min的元素的算法
6、二叉排序树的结点类型洳下:
请在下面算法空格处填上适当的内容,以完成在二叉排序树中查找键值为k的结点
假设在长度大于1的循环单链表中,既无头结点吔无头指针,P为指向该单链表中某个结点的指针下面是删除该结点的前驱结点函数
一、单项选择题(共20题每题2分,共40分)
1、数据的运算定义在数据的逻辑结构上只有确定了( C ),才能具体实现这些运算
2、基本的逻辑结构包括( D )。
A、树型结构、图状结构、线性结构和非线性结构
B、集合结构、线性结构、树型结构和非线性结构
C、集合结构、树型结构、图状结构和非线性结构
D、集合结构、线性结构、树型结构和图状结构
3、如果将与计算机软硬件相关的因素确定下来那么一个特定算法的运行工作量就只依赖于( B )。
D、编译生成的目标代码的质量
4、下面程序段执行的时间复杂度为( C)
5、顺序表是线性表的( B )。
A.、链式存储结构B、顺序存储结构
6、一个顺序表第一个元素的存儲地址是100每个元素的存储长度为4,则第5个元素的地址是( B )
7、一个长度为n的顺序表中,在第i(1≤i≤n+1)个元素的位置上插入一个新元素时需要向后移动( B )个元素。
8、对于顺序表的优缺点以下说法错误的是( D )。
A、无需为表示结点间的逻辑关系而增加额外的存储空间
B、可以方便地隨机存取表中的任一结点
C、插入和删除运算较方便
D、容易造成一部分空间长期闲置而得不到充分利用
9、当对线性表的操作是以插入操作和刪除操作为主时或当线性表的长度不能确定或表长变化很大时应选择( D )作为线性表的存储结构。