模拟试卷二
一、单选题（每题 2 分，共20分）
1.在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结
点，则执行(B )。
A. HL=p; p->next=HL;
B. p->next=HL->next; HL->next=p;
C. p->next=HL; p=HL;
D. p->next=HL; HL=p;
2.若顺序存储的循环队列的QueueMaxSize=n,则该队列最多可存储（A B ）个元素.
A. n
B.n-1
C. n+1
D.不确定
3.下述哪一条是顺序存储方式的优点？（C A ）
A．存储密度大 B.插入和删除运算方便
C. 获取符合某种条件的元素方便
D.查找运算速度快
4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在600(10)，A[3][3]存放位置在
678(10)，每个元素占一个空间，问A[2][3](10)存放在什么位置？(脚注(10)表示用10进制表示,m>3) BD
A．658 B．648 C．633 D．653 3m+3=78 m=25
5.下列关于二叉树遍历的叙述中，正确的是( DA ) 。
A. 若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点
B．若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点
C．若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点
D．若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点
6.k层二叉树的结点总数最多为( A ).
A．2k-1 B.2K+1 C.2K-1 D. 2k-1
7.对线性表进行二分法查找，其前提条件是( ).
A.线性表以链接方式存储，并且按关键码值排好序
B.线性表以顺序方式存储，并且按关键码值的检索频率排好序
C.线性表以顺序方式存储，并且按关键码值排好序
D.线性表以链接方式存储，并且按关键码值的检索频率排好序
8.对n个记录进行堆排序，所需要的辅助存储空间为
A. O（1og2n）
B. O（n）
C. O（1）
D. O（n2）
9.对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）
=K %7作为散列函数，则散列地址为0的元素有（）个，
A．1 B．2 C．3 D．4
10.下列关于数据结构的叙述中，正确的是( D ).
A.数组是不同类型值的集合
B.递归算法的程序结构比迭代算法的程序结构更为精炼
C.树是一种线性结构
D.用一维数组存储一棵完全二叉树是有效的存储方法
二、填空题（每空1分，共26分）
1.数据的逻辑结构被分为_________、________、__________和___________四种。
2.一个算法的时间复杂度为(3n3+2000n log2n+90)/n2，其数量级表示为________。
3.对于一个长度为n的单链存储的队列，在表头插入元素的时间复杂度为_________，在
表尾插入元素的时间复杂度为____________。
4.假定一棵树的广义表表示为A（D（E，G），H（I，J）），则树中所含的结点数为__________
个，树的深度为___________，树的度为_________。
5.后缀算式79 2 30 + - 4 2 / *的值为__________。中缀算式（3+X*Y）-2Y/3对
应的后缀算式为_______________________________。
6.在一棵高度为5的理想平衡树中，最少含有_______个结点，最多含有_______个结点。
7.在树中，一个结点的直接后继结点称为该结点的________。一个结点的直接前趋结点称
为该结点的________。
8.在一个具有10个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的
有向完全图中，包含有________条边。
9.假定一个线性表为(12,17,74,5,63,49,82,36)，若按Key % 4条件进行划分，使得同一余数
的元素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。
10.对一棵B_树进行删除元素的过程中，若最终引起树根结点的合并时，会使新树的高度
比原树的高度___________。
11.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序
过程的时间复杂度为________。
12.在线性表的散列存储中，装填因子α又称为装填系数，若用m表示散列表的长度，n
表示待散列存储的元素的个数，则α等于________。
三、运算题（每题 6 分，共24分）
1．在如下数组A中链接存储了一个线性表，表头指针存放在A [ 0].next，试写出该线性表。
data
next
2．KBCDAFHIGJ, 试画出这棵二叉树。
3．已知一个图的顶点集V为：V={1,2,3,4,5,6,7};
起点
终点
权
4．画出向小根堆中加入数据4, 2, 5, 8, 3, 6, 10, 1时，每加入一个数据后堆的变化。
四、阅读算法（每题7分，共14分）
1.在下面的每个程序段中，假定线性表La的类型为List，元素类型ElemType为int，
并假定每个程序段是连续执行的。试写出每个程序段执行后所得到的线性表La。
（1）InitList(La);
Int a[]={100,26,57,34,79};
For (i=0;i<5;i++)
Insert(La,a[i]);
TraverseList(La);
（2）DeleteFront(La);
InsertRear(La, DeleteFront(La));
TraverseList(La);
（3）ClearList(La);
For (i=0;i<5;i++)
InsertFront(La,a[i]);
TraverseList(La);
2.现面算法的功能是什么？
void ABC(BTNode * BT)
{
if BT {
cout<
ABC(BT->left);
ABC(BT->right);
}
}
五、算法填空（共8分）
二分查找的递归算法。
Int Binsch(ElemType A[],int low,int high,KeyType K)
{
if ___________________{
int mid=(low+high)/2;
if (_____________________) return mid; //查找成功，返回元素的下标 else if (K return Binsch(A,low,mid-1,K); //在左子表上继续查找 else return_____________________________； //在右子表上继续查找 } else ________________； //查找失败，返回-1 } 六、编写算法（共8分） HL为单链表的表头指针，试写出在该单链表中查找具有给定的元素item的算法。 bool Find(LNode* HL, ElemType &item) 模拟试卷二参考答案 一、单选题（每题2分，共20分） 1.B 2.B 3.A 4.D 5.A 6.A 7.C 8.C 9.D 10.D 二、填空题（每空1分，共26分） 1.集合结构线性结构树结构图结构 2.O(n) 3.O(1) O(1) 4.7 3 2 5.94 3 X Y * + 2 Y * 3 / - 6.16 31 7.孩子（或子）结点双亲（或父）结点 8.45 n(n-1) 9.（12，36）（17,5,49）（74，82）（63） 10.减少1（或减少） 11.O(log2n) O(nlog2n) 12.n/m 三、运算题（每题6分，共24分） 1.线性表为：（90，40，78，50，34，60） 2.当前序序列为ABKCDFGHIJ，中序序列为KBCDAFHIGJ时，逐步形成二叉树的过程 如下图4所示： 3. (1,6)1, (2,4)1, (2,5)2, (5,7)2, (2,6)3, (3,5)7 4.见图5。 图5 四、阅读算法（每题7分，共14分） 1.(1) La=(26,34,57,79,100) (2)La=(57,79,100,34) (3)La=(79,34,57,26,100) 2.前序遍历链式存储的二叉树。 五、算法填空（每空2分，共8 分） (low<=high) K==A[mid].key Binsch(A,mid+1,hight,K) return -1 六、编写算法（8分） bool Find(LNode* HL, ElemType &item) { LNode* p=HL; while p if (p->data==item){ return true; } else p=p->next; return false; } 模拟试卷二 七、单选题（每题 2 分，共20分） 11.在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结 点，则执行( )。 A. HL=p; p->next=HL; B. p->next=HL->next; HL->next=p; C. p->next=HL; p=HL; D. p->next=HL; HL=p; 12.若顺序存储的循环队列的QueueMaxSize=n,则该队列最多可存储（）个元素. A. n B.n-1 C. n+1 D.不确定 13.下述哪一条是顺序存储方式的优点？（） A．存储密度大 B.插入和删除运算方便 C. 获取符合某种条件的元素方便 D.查找运算速度快 14.设有一个二维数组A[m][n]，假设A[0][0]存放位置在600(10)，A[3][3]存放位置在 678(10)，每个元素占一个空间，问A[2][3](10)存放在什么位置？(脚注(10)表示用10进制表示,m>3) A．658 B．648 C．633 D．653 15.下列关于二叉树遍历的叙述中，正确的是( ) 。 A. 若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点 B．若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点 C．若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点 D．若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点 16.k层二叉树的结点总数最多为( ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 17.对线性表进行二分法查找，其前提条件是( ). E.线性表以链接方式存储，并且按关键码值排好序 F.线性表以顺序方式存储，并且按关键码值的检索频率排好序 G.线性表以顺序方式存储，并且按关键码值排好序 H.线性表以链接方式存储，并且按关键码值的检索频率排好序 18.对n个记录进行堆排序，所需要的辅助存储空间为 A. O（1og2n） B. O（n） C. O（1） D. O（n2） 19.对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K） =K %7作为散列函数，则散列地址为0的元素有（）个， A．1 B．2 C．3 D．4 20.下列关于数据结构的叙述中，正确的是( ). E.数组是不同类型值的集合 F.递归算法的程序结构比迭代算法的程序结构更为精炼 G.树是一种线性结构 H.用一维数组存储一棵完全二叉树是有效的存储方法 八、填空题（每空1分，共26分） 13.数据的逻辑结构被分为_________、________、__________和___________四种。 14.一个算法的时间复杂度为(3n3+2000n log2n+90)/n2，其数量级表示为________。 15.对于一个长度为n的单链存储的队列，在表头插入元素的时间复杂度为_________，在 表尾插入元素的时间复杂度为____________。 16.假定一棵树的广义表表示为A（D（E，G），H（I，J）），则树中所含的结点数为__________ 个，树的深度为___________，树的度为_________。 17.后缀算式79 2 30 + - 4 2 / *的值为__________。中缀算式（3+X*Y）-2Y/3对 应的后缀算式为_______________________________。 18.在一棵高度为5的理想平衡树中，最少含有_______个结点，最多含有_______个结点。 19.在树中，一个结点的直接后继结点称为该结点的________。一个结点的直接前趋结点称 为该结点的________。 20.在一个具有10个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的 有向完全图中，包含有________条边。 21.假定一个线性表为(12,17,74,5,63,49,82,36)，若按Key % 4条件进行划分，使得同一余数 的元素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。 22.对一棵B_树进行删除元素的过程中，若最终引起树根结点的合并时，会使新树的高度 比原树的高度___________。 23.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序 过程的时间复杂度为________。 24.在线性表的散列存储中，装填因子α又称为装填系数，若用m表示散列表的长度，n 表示待散列存储的元素的个数，则α等于________。 九、运算题（每题 6 分，共24分） 5．在如下数组A中链接存储了一个线性表，表头指针存放在A [ 0].next，试写出该线性表。 data next 6．KBCDAFHIGJ, 试画出这棵二叉树。 7．已知一个图的顶点集V为：V={1,2,3,4,5,6,7}; 起点 终点 权 8．画出向小根堆中加入数据4, 2, 5, 8, 3, 6, 10, 1时，每加入一个数据后堆的变化。 十、阅读算法（每题7分，共14分） 3.在下面的每个程序段中，假定线性表La的类型为List，元素类型ElemType为int， 并假定每个程序段是连续执行的。试写出每个程序段执行后所得到的线性表La。 （4）InitList(La); Int a[]={100,26,57,34,79}; For (i=0;i<5;i++) Insert(La,a[i]); TraverseList(La); （5）DeleteFront(La); InsertRear(La, DeleteFront(La)); TraverseList(La); （6）ClearList(La); For (i=0;i<5;i++) InsertFront(La,a[i]); TraverseList(La); 4.现面算法的功能是什么？ void ABC(BTNode * BT) { if BT { cout< ABC(BT->left); ABC(BT->right); } } 十一、算法填空（共8分） 二分查找的递归算法。 Int Binsch(ElemType A[],int low,int high,KeyType K) { if ___________________{ int mid=(low+high)/2; if (_____________________) return mid; //查找成功，返回元素的下标 else if (K return Binsch(A,low,mid-1,K); //在左子表上继续查找 else return_____________________________； //在右子表上继续查找 } else ________________； //查找失败，返回-1 } 十二、编写算法（共8分） HL为单链表的表头指针，试写出在该单链表中查找具有给定的元素item的算法。 bool Find(LNode* HL, ElemType &item) 模拟试卷二参考答案 七、单选题（每题2分，共20分） 1.B 2.B 3.A 4.D 5.A 6.A 7.C 8.C 9.D 10.D 八、填空题（每空1分，共26分） 13.集合结构线性结构树结构图结构 14.O(n) 15.O(1) O(1) 16.7 3 2 17.94 3 X Y * + 2 Y * 3 / - 18.16 31 19.孩子（或子）结点双亲（或父）结点 20.45 n(n-1) 21.（12，36）（17,5,49）（74，82）（63） 22.减少1（或减少） 23.O(log2n) O(nlog2n) 24.n/m 九、运算题（每题6分，共24分） 5.线性表为：（90，40，78，50，34，60） 6.当前序序列为ABKCDFGHIJ，中序序列为KBCDAFHIGJ时，逐步形成二叉树的过程 如下图4所示： 7. (1,6)1, (2,4)1, (2,5)2, (5,7)2, (2,6)3, (3,5)7 8.见图5。 十、阅读算法（每题7分，共14分） 3.(1) La=(26,34,57,79,100) (2)La=(57,79,100,34) (3)La=(79,34,57,26,100) 4.前序遍历链式存储的二叉树。 十一、算法填空（每空2分，共8 分） (low<=high) K==A[mid].key Binsch(A,mid+1,hight,K) return -1 十二、编写算法（8分） bool Find(LNode* HL, ElemType &item) { LNode* p=HL; while p if (p->data==item){ return true; } else p=p->next; return false; } 计算机专业基础综合数据结构（排序）模拟试卷2(题后含答案及解 析) 题型有：1. 单项选择题 2. 综合应用题 单项选择题1-40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。 1．采用简单选择排序，比较次数与移动次数分别为( )。 A．O(n)，O(log2n) B．O(log2n)，O(n2) C．O(n2)，O(n) D．O(nlog2n)，O(n) 正确答案：C 解析：简单选择排序的关键字比较次数KCN与对象的初始排列无关。第i 趟选择具有最小关键字对象所需的比较次数总是n—i—1次(此处假定整个待排序对象序列有n个对象)。因此，总的关键字比较次数为：最坏情况是每一趟都要进行交换，总的对象移动次数为RMN=3(n一1)。知识模块：数据结构 2．就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是( )。 A．堆排序＜快速排序＜归并排序 B．堆排序＜归并排序＜快速排序 C．堆排序＞归并排序＞快速排序 D．堆排序＞快速排序＞归并排序 正确答案：A 解析：此题考查的知识点为排序的空间复杂性。堆排序辅助空间为O(1)，快速排序为O(log2n)，归并排序为O(n)。应选A。知识模块：数据结构 3．一组记录的关键码为(25，48，16，35，79，82，23，40，36，72)，其中，含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为( )。 A．16，25，35，48，23，40，79，82，36，72 B．16，25，35，48，79，82，23，36，40，72 C．16，25，48，35，79，82，23，36，40，72 D．16，25，35，48，79，23，36，40，72，82 正确答案：A 解析：对于(25，48，16，35，79，82，23，40，36，72)，(25，48)和(16，35)归并的结果为(16，25，35，48)。(79，82)和(23，40)归并后的结果为(23，40， 长沙理工大学数据结构模拟试卷2 一、填空题（每空1分，共10分） 1．顺序存储结构中数据元素之间的逻辑关系是由存储位置表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 2．非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（）。 3．n个顶点的连通图用邻接矩阵表示时，该矩阵至少有（）个非零元素。 4．（）可作为实现递归函数调用的一种数据结构。 5．由权值为{3, 8, 6, 2, 5}的叶子结点生成一棵哈夫曼树，其带权路径长度为（）。 6．设S="I_ am_ a_ teacther"，其长度为（）。 7．稀疏矩阵一般压缩存储方法有两种，分别是（）和（）。 8．分块有序是指将文件划分为若干块，（）无序，（）有序。 二、判断题（你认为正确的请打对，错误的打错。每题2分，共10分） 1．线性表的顺序存储结构优于链接存储结构。 2．B—树是一种动态索引结构，它既适用于随机查找，也适用于顺序查找。 3．在线索二叉树中，任一结点均有指向其前趋和后继的线索。 4．用一维数组存储二叉树时，总是以前序遍历存储结点。 5．在索引顺序表上采用分块查找，在等概率情况下，其平均查找长度不仅与子表个数有关，而且与每一个子表中的对象个数有关。 三、单选题（请把你认为正确的答案填入括号内，每小题1分，共10分） 1．假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（）。 A 树 B 图 C 线性表 D 集合 2．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（）结构。 A 栈B队列 C 数组D线性表 3．若某线性表经常的操作是取第i 个元素和找第i个元素的前趋，则采用（）存储方法最节省时间。 A 顺序表 B 单链表 C 双链表 D 单循环链表 4．广义表(a, b, (c, (d)))的表尾是（）。 A (d) B (c,(d)) C b D (b,(c,(d))) 5．堆的形状是一棵（）。 A二叉排序树B满二叉树C完全二叉树 D 判定树 6．设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（）。 A 6 B 4 C 3 D 2 7．G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。 A 6 B 7 C 8 D 9 8．设有5000个元素，希望用最快的速度挑选出前10个最大的，采用（）方法最好。 A快速排序B堆排序C希尔排序 D 归并排序 9．设有10000个记录，通过分块划分为若干子表并建立索引，那么为了提高查找效率，每一个子表的大小应设计为( )。 A 100 B 200 C10 D 5 10．设有两个串p和q，求q在p中首次出现的位置的运算称作（）。 A 连接 B 模式匹配 C 求子串 D 求串长 期末样卷参考答案 一．是非题（每题2分共20分） 1. 线性表的链式存储结构优于顺序存储结构。F 2. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。F 3．字符串是数据对象特定的线性表。T 4．在单链表P指针所指结点之后插入S结点的操作是：P->next= S ; S-> next = P->next; F 5．一个无向图的连通分量是其极大的连通子图。T 6．邻接表可以表示有向图，也可以表示无向图。T 7．假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的中序遍历。 T 8．通常，二叉树的第i层上有2i-1个结点。F 9．对于一棵m阶的B-树,树中每个结点至多有m 个关键字。除根之外的所有非终端 结点至少有┌m/2┐个关键字。F 10．对于任何待排序序列来说，快速排序均快于起泡排序。F 二．选择题（每题2分共28分） 1．在下列排序方法中，（c）方法平均时间复杂度为0(nlogn)，最坏情况下时间复杂度为0(n2)；（d）方法所有情况下时间复杂度均为0(nlogn)。 a. 插入排序 b. 希尔排序 c. 快速排序 d. 堆排序 2. 在有n个结点的二叉树的二叉链表表示中，空指针数为（b）。 a.不定 b.n+1 c.n d.n-1 3. 下列二叉树中，（a）可用于实现符号不等长高效编码。 a.最优二叉树 b.次优查找树 c.二叉平衡树 ?? d.二叉排序树 4. 下列查找方法中，（a）适用于查找有序单链表。 a.顺序查找 b.二分查找 c.分块查找 d.哈希查找 5. 在顺序表查找中，为避免查找过程中每一步都检测整个表是否查找完毕，可采用 （a）方法。 a.设置监视哨 b.链表存贮 c.二分查找 d.快速查找 6. 在下列数据结构中，（c）具有先进先出特性，（b）具有先进后出特性。 a．线性表 b．栈 c．队列 d．广义表 7．具有m个结点的二叉排序树，其最大深度为（f），最小深度为（b）。 a. log 2 m b. └ log2 m ┘ +1 c. m/2 d .┌ m/2 ┐ -1 e. ┌ m/2 ┐ f. m 8．已知一组待排序的记录关键字初始排列如下：56,34,58,26,79,52,64,37,28,84,57。 下列选择中（c）是快速排序一趟排序的结果。 （b）是希尔排序（初始步长为4）一趟排序的结果。 （d）是基数排序一趟排序的结果。 （a）是初始堆（大堆顶）。 a)84，79，64，37，57，52，58，26，28，34，56。 b)28，34，57，26，56，52，58，37，79，84，64。 c)28，34，37，26，52，56，64，79，58，84，57。 d)52，34，64，84，56，26，37，57，58，28，79。 数据结构模拟试题二 一．判断题（每小题1 分，共15分） 1.构成数据的最小单位是数据项。 2.空线性表的一个特性是线性表中各结点尚未赋值。 3.非循环单向链表一定要有表头指针。 4.顺序栈的栈顶指针是一个指针类型的变量。 5.在表示树的双亲数组中，找结点的双亲要比找结点的孩子容易。 6.哈夫曼树中不存在度为1的结点。 7.在图中，与V i相邻的顶点其序号一定是i+1或i-1。 8.如果是不连通的无向图，则在相应的邻接表中一定有空链表。 9.矩阵的行数和列数可以不相等。 10.广义表的深度与广义表中含有多少个子表元素有关。 11.折半查找可以在有序的双向链表上进行。 12.散列查找过程中，关键字的比较次数和散列表中关键字的个数直接相关。 13.对n个元素执行简单选择排序，排序码的比较次数总是n(n-1)/2次。 14.物理记录的大小与逻辑记录的大小成正比。 15.对索引文件，索引表是建立在内存的，数据区是建立在外存的。 二．填空题（每空1分，共15分） 1.在程序中，描述顺序表的存储空间一般用________变量。 2.若用Q[0]~Q[100]作为循环顺序队列的存储空间，用“队首指针f的值等于队尾指针r 的值”作为队空的标志，则创建一个空队列所要执行的操作是___________。 3.栈和顺序栈的区别仅在于________。 4.n个结点的二叉树最大高度是___，最小高度是___。 5.树的存储方法主要有_____、_____和_____三种。 6.n个顶点的强连通图中至少有___条边。 7.10行20列矩阵若用列优先顺序表来表示，则矩阵中第7行第6列元素是顺序表中第___ 个元素。 8.在各元素查找概率相等的情况下，在含有14个元素的平衡二叉排序树上查找其中一个 元素，元素间的平均比较次数至少是_____次，至多是______次。 9.对n个元素执行快速排序，在进行第一次分组时，元素的移动次数至多是____次，至少 是___次。 10.在B-树中，若某结点有i个孩子，则该结点中一定有___个关键字。 三．选择题（每题2分，共30分） 1.数据结构的研究内容不涉及________。 A．算法用什么语言来描述B．数据如何存储 C．数据的运算如何实现D．数据如何组织 2. 若H1是动态单向链表的表头指针，H2是动态双向链表的表头指针，则________。A．H1和H2占用同样多的内存空间B．H1和H2是同类型的变量 C．H2要比H1占用更多的内存空间 D．双向链表要比单向链表占用更多的内存空间 3. 对于K个带头结点的静态单向链表来说，若各结点类型相同，则K个链表一般可共用_________。 A．同一个数组B．某些数组元素C．同一个表头结点D同一个表头指针 4.最不适合用作链接栈的链表是_____________。 A．只有表头指针没有表尾指针的循环双向链表 B．只有表尾指针没有表头指针的循环双向链表 C．只有表尾指针没有表头指针的循环单向链表 D．只有表头指针没有表尾指针的循环单向链表 5.栈和队列的共同点在于_____________。 A．都对存储方法作了限制B．都是只能进行插入、删除运算C．都对插入、删除的位 模拟试卷二 一、选择题（每小题2分，共10分） 1．若线性表最常用的操作是存取第i个元素及其前趋的值，则采用存储方式节省时间。 a．单链表 b. 双链表 c．单循环链表 d．顺序表 2．对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其有孩子的编号，则可采用次序的遍历实现编号。 a．无序 b．中序 c．后序 d．从根开始的层次遍历 3．某二叉树的先序序列和后序序列正好相反，则该二叉树一定是的二又树。 a．空或只有一个结点 b. 高度等于其结点数 C．任一结点无左孩子 d．任一结点无右孩子4．下列排序算法中，时间复杂度不受数据初始状态影响，恒为 O（nlog2n）的是 。 a．堆排序 b. 冒泡排序 c．直接选择排序 d. 快速排序 5. 下列排序算法中，算法可能会出现下面情况：初始数据有序时，花费 的时间反而最多。 a．堆排序 b．冒泡排序 c．快速排序 d. SHELL排序 二、判断题（每小题1分，共10分） 1．（）在循环队列中，若尾指针Rear大于头指针Front，则其元素个数为 Rear - Front。 2．（）串是n个字母的有限序列（n >= 0）。 3. ( ）若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树。 4．（）二叉树只能采用二又链表来存储。 5.（）有向图用邻接矩阵表示后，顶点i的出度等于第i行中非0且非加 的元素个数。 6．（）图G的某一最小生成树的代价一定小于其他生成树的代价。 7.（）给定结点数的平衡二叉树的高度是唯一的。 8.（）9阶B树中，除报以外的任一结点中的关键字个数不少于4。 9．（）只有在初始数据表为倒序时，冒泡排序所执行的比较次数最多。 10.（）堆排序中，在输出一个根之后的调整操作中，“临时根”结点的值将 被调到“叶子结点”上。 三、项空（每小题2分，共20分） 计算机专业基础综合（数据结构）模拟试卷2 (总分：70.00，做题时间：90分钟) 一、单项选择题(总题数：21，分数：42.00) 1.单项选择题1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数： 2.00）__________________________________________________________________________________________ 解析： 2.栈和队列的主要区别在于( )。 （分数：2.00） A.它们的逻辑结构不一样 B.它们的存储结构不一样 C.所包含的运算不一样 D.插入和删除运算的限定不一样√ 解析：解析：栈和队列的逻辑结构都是线性的，都有顺序存储和链式存储，有可能包含的运算不一样，但不是其主要区别。任何数据结构在针对具体问题时所包含的运算都可能不同。所以正确答案是D。 3.若循环队列以数组Q[0．．m-1]作为其存储结构，变量rear。表示循环队列中的队尾元素的实际位置，其移动按rear=(rear+1)MOD m进行，变量length表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是( )。 （分数：2.00） A.rear-length B.(rear—length+m)MOD m C.(rear—length+1+m)MOD m √ D.m-length 解析：解析：按照循环队列的定义，因为元素移动按照rect=(rear+1)MOD m进行，则当数组Q[m—1]存放了元素之后，下一个入队的元素将存放到Q[0]中，因此队列的首元素的实际位置是(rear—length+1+m)MOD m。 4.一个以向量V[n]存储的栈，其初始栈顶指针top为n+1，则对于x，其正确的进栈操作是( )。 （分数：2.00） A.top=top+1；V[top]=x B.V[top]=x；top=top+1 C.top=top-1；V[top]=x √ D.V[top]=x；top=top-1 解析：解析：此题考查的知识点是入栈的具体操作。操作时要看栈顶的地址，先取得空间，再入栈。本题栈顶为n+1，应该用减法，所以选C。D是先存入，破坏原有数据，所以错。 5.为了增加内存空间的利用率和减少溢出的可能性，两个栈可以共享一片连续的内存空间，此时应将两栈的栈底分别设在( )。 （分数：2.00） A.内存空间的首地址 B.内存空间的尾地址 C.内存空间的两端√ D.内存空间的中间 解析：解析：两个栈共享一个内存空间时，需要把两个栈的栈底设在内存空间的两端。 6.已知输入序列为abcd，经过输出受限的双端队列后，能得到的输出序列是( )。 （分数：2.00） A.dacb B.cadb √ C.dbca D.以上答案都不对 数据结构模拟题2 一、判断题。判断下列各题是否正确，若正确，在答题卡中涂“A”，否则涂“B”。1．线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。Χ 2．线性表的链式存储结构优于顺序存储结构。Χ 3．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。Χ 4．顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。Χ 5．链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。Χ 6．两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。√ 7．在循环队列中，元素的个数为rear-front。Χ 8．完全二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。√ 9．邻接表存储结构只用于有向图的存储，邻接矩阵对有向图和无向图的存储都适用。Χ 10．连通分量是无向图中的极小连通子图。Χ 11．没有回路的图能进行拓扑排序。√ 12．生成树指的是图的极大连通子图。Χ 13．采用折半查找法对有序表进行查找总比采用顺序查找法对其进行查找要快。Χ 14．采用线性探测法处理冲突时，当从哈希表中删除一个记录时，不应将这个记录的所在位置的数据置空，因为这样会影响以后的查找。√ 15．对于给定的关键字集合，以不同的次序插入到初始为空的二叉排序树中，得到的二叉排序树是相同的。Χ 二、单选题。 1．数据结构可以分为三大类，它们是【】、树和图。A A、线性表 B、栈和队列 C、链表 D、顺序表 2．下列程序段的时间复杂度为【】。A for(i=0；i 模拟试卷二 一、单选题（每题2 分，共20分） 1.在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行(B )。 A. HL=p; p->next=HL; B. p->next=HL->next; HL->next=p; C. p->next=HL; p=HL; D. p->next=HL; HL=p; 2.若顺序存储的循环队列的QueueMaxSize=n,则该队列最多可存储（A B ）个元素. A. n B.n-1 C. n+1 D.不确定 3.下述哪一条是顺序存储方式的优点？（C A ） A．存储密度大 B.插入和删除运算方便 C. 获取符合某种条件的元素方便 D.查找运算速度快 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在600(10)，A[3][3]存放位置在678(10)，每个元素占一个 空间，问A[2][3](10)存放在什么位置？(脚注(10)表示用10进制表示,m>3) BD A．658 B．648 C．633 D．653 3m+3=78 m=25 5.下列关于二叉树遍历的叙述中，正确的是( DA ) 。 A. 若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点 B．若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点 C．若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点 D．若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点 6.k层二叉树的结点总数最多为( A ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.对线性表进行二分法查找，其前提条件是( ). A.线性表以链接方式存储，并且按关键码值排好序 B.线性表以顺序方式存储，并且按关键码值的检索频率排好序 C.线性表以顺序方式存储，并且按关键码值排好序 D.线性表以链接方式存储，并且按关键码值的检索频率排好序 8.对n个记录进行堆排序，所需要的辅助存储空间为 A. O（1og2n） B. O（n） C. O（1） D. O（n2） 9.对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K %7作为散列函数， 则散列地址为0的元素有（）个， A．1 B．2 C．3 D．4 10.下列关于数据结构的叙述中，正确的是( D ). A.数组是不同类型值的集合 B.递归算法的程序结构比迭代算法的程序结构更为精炼 C.树是一种线性结构 D.用一维数组存储一棵完全二叉树是有效的存储方法 二、填空题（每空1分，共26分） 1.数据的逻辑结构被分为_________、________、__________和___________四种。 2.一个算法的时间复杂度为(3n3+2000n log2n+90)/n2，其数量级表示为________。 3.对于一个长度为n的单链存储的队列，在表头插入元素的时间复杂度为_________，在表尾插入元素的时间 复杂度为____________。 4.假定一棵树的广义表表示为A（D（E，G），H（I，J）），则树中所含的结点数为__________个，树的深度为 ___________，树的度为_________。 5.后缀算式79 2 30 + - 4 2 / *的值为__________。中缀算式（3+X*Y）-2Y/3对应的后缀算式为 _______________________________。 6.在一棵高度为5的理想平衡树中，最少含有_______个结点，最多含有_______个结点。 7.在树中，一个结点的直接后继结点称为该结点的________。一个结点的直接前趋结点称为该结点的________。 8.在一个具有10个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含 有________条边。 9.假定一个线性表为(12,17,74,5,63,49,82,36)，若按Key % 4条件进行划分，使得同一余数的元素成为一个子表， 则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。 10.对一棵B_树进行删除元素的过程中，若最终引起树根结点的合并时，会使新树的高度比原树的高度 ___________。 11.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序过程的时间复杂度为 数据结构模拟试卷(二)参考答案 一、单项选择题（每小题2分，共30分） 1~5 ACABB 6~10 ABABA 11~15 BADCB 二、填空题(每空2分，共20分) 16．数据结构一般包括三个方面内容：数据的逻辑结构，数据的存储结构及数据的运算。17．在包含n个结点的顺序表上做等概率插入运算，平均要移动__ n/2_ ___个结点。18．队列的特性是___ _ 先进先出__。19．已知二叉树中叶子数为30，仅有一个孩子的结点数为20，则总结点数为__79 __。 20．______中序_遍历二叉排序树中的结点可以得到一个递增的关键字序列（选填“先序”、“中序”或“后序”）。 21．n个节点的连通图至少有_____ n-1 ____条边。 22．在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑，应最好选择快速排序排序。 23．带有一个头结点的单链表head为空的条件是（假设指针域的名称为next） __ head->next==NULL ___。 24．设一组初始关键字序列为(38，65，97，76，13，27，10)，则第3趟简单选择排序后的结果为_______10,13,27,76,65,97,38 ____________。 25．在拓扑排序中，拓扑序列的第一个顶点必定是入度为零的顶点。 三、简答题（每题6分，共36分） 26．已知一棵树边的集合为｛ 模拟试题二 模拟试题二 一、选择题（28分） 1.设一数列的顺序为l，2，3,4，5,通过栈结构不可能排成的顺序数列为( )。 A)3,2，5，4，l B)1，5,4，2，3 C）2，4，3,5,l D）4，5，3，2,l 2。二叉树的第3层最少有（)个结点。 A)0 B）1 C)2 D）3 3。—个n个顶点的连通无向图，其边的个数至少为( )。 A) n-l B)n C）n+l D）nlogn 4。下列排序方法中，( ）的比较次数与记录的初始排列状态无关。 A）直接插入排序 B）起泡排序 C）快速排序 D）直接选择排序 5.-棵哈夫曼树总共有II个结点，则叶子结点有( ）个。 A）5 B）6 C）7 D)9 6.已知某算法的执行时间为（n+n2)+log2(n+2)，n为问题规模,则该算法的时间复杂度是( ）。 A)O（n）B）O（n2) C）O（log2n）D）O(nlog2n) 7。如果一棵树有10个叶子结点，则该树总共至少有( )个结点。 A）lO B）11 C）19 D) 21 8。—个100×100的三角矩阵a采用行优先压缩存储后，如果首元素a[0]［0]是第一个元素，那么a[4] [2］是第( )个元素。 A）13 B) 401 C) 402 D）403 9.有一棵二叉树如题图1,该树是（）。 A）二叉平衡树B)二叉排序树 C)堆的形状D)以上都不是 10。对于含有n个顶点e条边的无向连通图，利用Prim算法生成最小代价生成树，其时间复杂度为（)，利用Kruska算法的时间复杂度为（). A）O（log2n) B）0(n2) C)O（ne) D）O（elog2ne) 11.具有n个顶点的完全有向图的边数为( ）. A）n（n—l)/2 B）n（n-l） C) n2 D）n2—1 12。设有100个元素，用折半查找时,最大比较次数为（)，最小比较次数为（）。 A）25 B)7 C) 10 D)l 试卷三 一、单项选择题(在下列每小题四个备选答案中选出一个正确答案，并将其字母标号填入题干的括号内。每小题2分，共30分) 1．数据结构可以形式化地定义为（S，△），其中S指某种逻辑结构，△是指（）A.S上的算法 B.S的存储结构 C.在S上的一个基本运算集 D.在S上的所有数据元素 2．下列说法正确的是（） A.线性表的逻辑顺序与存储顺序总是一致的 B.线性表的链式存储结构中，要求内存中可用的存储单元可以是连续的，也可以不连续 C.线性表的线性存储结构优于链式存储结构 D.每种数据结构都具有插入、删除和查找三种基本运算 3．稀疏矩阵一般采用（）方法压缩存储。 A.三维数组 B.单链表 C.三元组表 D.散列表 4.在一个单链表中，若p↑结点不是最后结点，在p↑之后插入s↑结点，则实行( )。 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; 5.某个向量第一元素的存储地址为100，每个元素的长度为2，则第五个元素的地址是 ( )。 A.110 B.108 C.100 D.120 6.下面的二叉树中，( )不是完全二叉树。 7.一组记录的排序码为(47、78、61、33、39、80)，则利用堆排序的方法建立的初始堆为 ( )。 A.78、47、61、33、39、80 B.80、78、61、33、39、47 C.80、78、61、47、39、33 D.80、61、78、39、47、33 8.假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针域，现要把一个指针s所指的新结点作为非空双链表中q所指地点(中间结点)的直接后继结点插入到该双向链表中，则下列算法段能正确完成上述要求的是( ) A.q->right=s; s->left=q; q->right->left=s; s->right=q->right; B.s->left=q; q->right=s; q->right->left=s; s->right=q->right; C.s->left=q; s->right=q->right; q->right->left=s; q->right=s; D.以上都不对 9.由下列三棵树组成转的森林换成一棵二叉树为( ) 计算机专业基础综合数据结构（树与二叉树）模拟试卷2(题后含答 案及解析) 题型有：1. 单项选择题 2. 综合应用题 单项选择题1-40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。 1．设树T的度为4，其中度为1、2、3和4的结点个数分别为4、1、1、1，则T中的叶子数为( )。 A．10 B．11 C．9 D．7 正确答案：D 解析：根据题中条件可知，1×4+2×1+3+4+1=4+1+1+1+n0，由此可以得出：n0=1×4+2×1+3+4+1一(4+1+1+1)=14—7=7. 知识模块：数据结构 2．用下列元素序列(22，8，62，35，48)构造平衡二叉树，当插入( )时，会出现不平衡的现象。 A．22 B．35 C．48 D．62 正确答案：C 解析：由题中所给的结点序列构造二叉排序树的过程如下图：当插入48后，首次出现不平衡子树，虚线框内即为最小不平衡子树。知识模块：数据结构 3．下面的算法实现了将二叉树中每一个结点的左右子树互换。addQ(Q，bt)为进队的函数，delQ(Q)为出队的函数，empty(Q)为判别队列是否为空的函数，空白处应填的内容是( )。typedef struct node{ int data；struct node*lchild，*rchild；}btnode；void exchange(btnode*bt){ btnode*p，*q；if(bt){ addQ(Q，bt)；while(!EMPTY(Q)){ p=delQ(Q)；q=p-＞rchild；p一＞rchild=p一＞lchild；( (1) )=q；if(p->lchild) ( (2) )；if(p-＞rchild)addQ(Q，p-＞rchild)；} }} A．p-＞lchild，delQ(Q，p一＞lchild) B．p-＞rchild，delQ(Q，p-＞lchild) C．p-＞lchild，addQ(Q，p-＞lchild) D．p-＞rchild，addQ(Q，p-＞lchild) 吉林大学智慧树知到“计算机科学与技术”《数据结构》 网课测试题答案 （图片大小可自由调整） 第1卷 一.综合考核(共15题) 1.非空的循环单链表head的尾结点(由指针p所指)满足()。 A.p->next=NULL B.p=NULL C.p->next=head D.p=head 2.当文件局部有序或文件长度较小的情况下，最佳的排序方法是()。 A.直接插入排序 B.直接选择排序 C.冒泡排序 D.归并排序 3.具有n(n0)个顶点的无向图最多含有n(n-1)/2条边。() A.正确 B.错误 4.对于前序遍历和中序遍历结果相同的二叉树为所有结点只有右孩子的二叉树。() A.正确 B.错误 5.一个好的算法应具备以下性质：() A.正确性 B.可读性 C.稳健性 D.有穷性 6.类string中包含的串运算有()。 A.Find() B.Substr() C.Insert() D.Length() 7.单链表中的头结点就是单链表的第一个结点。() A.正确 B.错误 8.设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数最少()个。 A.k+1 B.2k C.2k-1 D.2k+1 9.从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较()个结点。 A.n B.n/2 C.(n-1)/2 D.(n+1)/2 10.在第一趟排序之后，一定能把数据表中最大或最小元素放在其最终的排序算法是冒泡排序。() A.正确 B.错误 11.判断一个表达式中左右括号是否匹配，采用栈实现较为方便。() A.正确 B.错误 12.带头结点的单链表head为空的判断条件是()。 A.head=NULL B.head->next=NULL C.head->next=head D.head!=NULL 13.Huffman树、平衡二叉树都是数据的逻辑结构。() A.正确 B.错误 14.任何一棵二叉树中至少有一个结点的度为2。() A.正确 B.错误 15.在无向图中，所有顶点的度数之和是所有边数的()倍。 A.0.5 B.1 C.2 D.4 数据结构试卷及答案 一、选择题（共30题，每题2分，共60分） 1. 数据结构是解决什么问题的基础？ A. 数据的存储和组织问题 B. 数据的计算和分析问题 C. 数据的传输和交换问题 D. 数据的加密和解密问题 2. 下列哪种数据结构可以实现后进先出（LIFO）的特性？ A. 栈 B. 队列 C. 链表 D. 树 3. 哪种数据结构可以快速地查找和插入元素？ A. 数组 B. 链表 C. 栈 D. 队列 4. 在二叉树中，每个节点最多有几个子节点？ A. 0 B. 1 C. 2 D. 3 5. 下列哪种排序算法的时间复杂度是O(nlogn)？ A. 冒泡排序 B. 插入排序 C. 快速排序 D. 选择排序 ... 二、填空题（共10题，每题4分，共40分） 1. 数据结构中，关系密切的元素组成的集合称为________。 2. 对一个链表进行插入或删除操作，时间复杂度是________。 3. 在树结构中，没有子节点的节点称为________。 4. 广度优先搜索（BFS）使用的数据结构是________。 5. 在堆排序中，堆的建立时间复杂度是________。 ... 三、简答题（共5题，每题10分，共50分） 1. 请简要解释什么是数组，并说明其在数据结构中的优势和限制。 2. 请解释栈和队列这两种数据结构的特点和应用场景，并给出一个实际的例子。 3. 请解释什么是二叉树，给出一个二叉树的例子，并说明其遍历的方法。 4. 请简要解释图的概念，并说明图的遍历方法。 5. 请解释并比较快速排序和归并排序两种常用的排序算法，包括它们的时间复杂度和空间复杂度。 ... 答案解析： 一、选择题答案： 1. A 2. A 3. B 4. C 5. C 二、填空题答案： 1. 集合 数据结构样卷 一．判断题（15分） 1．（0 ）线性表的各种基本操作在顺序存储结构上的实现均比在链式存储结构上的实现效率要低。 2．（0 ）一个有向图的邻接表和逆邻接表中表结点的个数一定相等。3．（1 ）先序遍历森林和先序遍历与该森林相对应的二叉树，其结果不同。4．（1 ）不使用递归，也可实现二叉树的先序、中序和后序遍历。 5．（1 ）散列法存储的基本思想是由关键字的值决定数据的存储地址。6．（1 ）采用折半查找法对有序表进行查找总是比采用顺序查找法对其进行查找要快。 7．（0 ）在任何情况下，快速排序方法的时间性能总是最优的。 8. （ 0 ）二维数组是其数据元素为线性表的线性表。 9.（0 ）拓扑排序是一种内部排序方法。 10．（0 ）数据的物理结构是指数据在计算机内实际的存储形式。 二．单选题（每个选择项2分，共20分） 1. 单循环链表的主要优点是( D )。 A.不再需要头指针 B.已知某个结点的位置后，能够容易找到它的直接前趋 C.在进行插入，删除运算时，能更好地保证链表不断开 D.从表中任一结点出发都能扫描到整个链表 2. 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用( D )存储方式最节省时间。 A．顺序表B．单链表C．双链表D．单循环链表3. 在Hash函数H (k) = k MOD m 中，一般来讲，m应取( C )。 A．奇数B．偶数C．素数D．充分大的数4. 图的深度优先遍历算法类似于二叉树的( A )，广度优先遍历算法类似于二叉树的( D )。 A．先序遍历B．中序遍历C．后序遍历D．层次遍历 5. 对树而言，不合适的遍历方法是( D )。 A．先序遍历B．中序遍历C．后序遍历D．层次遍历 6. 若广义表A满足Head(A)==Tail(A)，则A为( B )。 A. ( ) B. (( )) C. (( ),( )) D. (( ),( ),( )) 7. 下列二叉树中，( A )可用于实现符号的不等长高效编码。 1 全真模拟试题 、单项选择题(在每个小题的 4个备选答案中，选出正确的答案，并将其号码填在题后 的括号内。每小题 2分，共24分) 1•一个具有n 个顶点的无向完全图的边数为( ) ① n(n+1)/2 ② n(n-1)/2 ③ n( n-1) ④ n(n +1) 2•在索引顺序表中查找一个元素，可用的且最快的方法是( ) ① 用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找 ② 用顺序查找法确定元素所在块，再用二分查找法在相应块中查找 ③ 用二分查找法确定元素所在块，再用顺序查找法在相应块中查找 ④ 用二分查找法确定元素所在块，再用二分查找法在相应块中查找 3 .若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个 元素，则采用( )存储方式最节省运算时间。 ①单链表 ③带头结点的双循环链表 4•串是( ) 5•堆排序在最坏情况下，其时间复杂性为( ) ① 0(nlog 2n) ② 0(n 2) ③ O(log 2n 2) ④ O(log 2n) 6•快速排序的记录移动次数( )比较次数，其总执行时间为 0(nlog2n)。 ①大于 ②大于等于 ③小于等于 ④小于 7. —棵二叉树有n 个结点，要按某顺序对该二叉树中的结点编号， (号码为1-n ),编 号须具有如下性质：二叉树中任一结点 V ,其编号等于其左子树中结点的最大编号加 1。 而其右子树中结点的最小编号等于 V 的编号加1。试冋应按()遍历顺序编号。 9•对有n 个记录的有序表采用二分查找，其平均查找长度的量级为( ) ① O(log 2n) ② O(nlog 2n) ③O(n) ④ O(n 2) 10 •对有n 个记录的表按记录键值有序的顺序建立二叉树，在这种情况下，其平均查 找长度的量 级为( ) ① O(n) ② O(nlog 2n) ③ O(1) ④(log 2n) 11 .栈操作的原则是( ) ①先进先出②后进先出 ③栈顶插入④栈顶删除 12 .设矩阵A 是一对称矩阵(a ij =a ji ,1<=i,j<=8)，若每个矩阵元素占 3个单元，将其上 三角部分(包括对角线)按行序为主序存放在数组 B 中，B 的首地址为1000,则矩阵元素 a 67的地址为() ① 1031 ② 1093 ③ 1096 ④ 1032 二、判断题(判断下列各题是否正确，正确在括号内打“V” ，错的打“x”。每小题1 分, 共10分) ②双链表 ④容量足够大的顺序表 ①一些符号构成的序列 ③一个以上的字符构成的序列 ②有限个字母构成的序列 ④有限个字符构成的序列 ①前根 ②中根 8.3个结点可构成( ①2 ②3 ③4 ③后根 ④层次 )个不同形态的二叉树。 ④5 全真模拟试题（二） 一、单项选择题（在每个小题的 4个备选答案中，选出正确的答案，并将其号码填在题后 的括号内。每小题 2分，共24分） 1•一个具有n 个顶点的无向完全图的边数为（ ） ① n （n+1）/2 ② n （n-1）/2 ③ n （ n-1） ④ n （n +1） 2•在索引顺序表中查找一个元素，可用的且最快的方法是（ ） ① 用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找 ② 用顺序查找法确定元素所在块，再用二分查找法在相应块中查找 ③ 用二分查找法确定元素所在块，再用顺序查找法在相应块中查找 ④ 用二分查找法确定元素所在块，再用二分查找法在相应块中查找 3 .若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个 元素，则采用（ ）存储方式最节省运算时间。 ①单链表 ③带头结点的双循环链表 4•串是（ ） 5•堆排序在最坏情况下，其时间复杂性为（ ） ① 0（nlog 2n ） ② 0（n 2） ③ O （log 2n 2） ④ O （log 2n ） 6•快速排序的记录移动次数（ ）比较次数，其总执行时间为 0（nlog2n ）。 ①大于 ②大于等于 ③小于等于 ④小于 7. —棵二叉树有n 个结点，要按某顺序对该二叉树中的结点编号， （号码为1-n ）,编 号须具有如下性质：二叉树中任一结点 V ,其编号等于其左子树中结点的最大编号加 1。 而其右子树 中结点的最小编号等于 V 的编号加1。试冋应按（）遍历顺序编号。 9•对有n 个记录的有序表采用二分查找，其平均查找长度的量级为（ ） ① O （log 2n ） ② O （nlog 2n ） ③O （n ）④ O （n 2） 10 •对有n 个记录的表按记录键值有序的顺序建立二叉树，在这种情况下，其平均查 找长度的量级为（ ） ① O （n ） ② O （nlog 2n ） ③ O （1） ④（log 2n ） 11 .栈操作的原则是（ ） ①先进先出②后进先出 ③栈顶插入④栈顶删除 12 .设矩阵A 是一对称矩阵（a ij =a ji ,1<=i,j<=8），若每个矩阵元素占 3个单元，将其上 三角部分（包括对角线）按行序为主序存放在数组 B 中，B 的首地址为1000,则矩阵元素 a 67的地址为（） ① 1031 ② 1093 ③ 1096 ④ 1032 二、判断题（判断下列各题是否正确，正确在括号内打“V” ，错的打“x”。每小题1 分, 共10分） 1 •如果两个串含有相同的字符，则这两个串相等。 （） 2. 数组可以看成线性结构的一种推广， 因此可 ②双链表 ④容量足够大的顺序表 ①一些符号构成的序列 ③一个以上的字符构成的序列 ②有限个字母构成的序列 ④有限个字符构成的序列 ①前根 ②中根 ③后根 ④层次 8.3个结点可构成（ ①2 ②3 ③4 个不同形态的二叉树。 ④5 《数据结构》模拟试题A 一、单项选择题（每题 3 分，共24分） 1．下面关于线性表的叙述错误的是（）。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现 2．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。 (A)2m-1 (B)2m (C) 2m+1 (D) 4m 3．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（）。 (A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M 4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。 (A) BADC (B) BCDA (C) CDAB (D) CBDA 5．设某完全无向图中有n个顶点，则该完全无向图中有（）条边。 (A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1 6．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。 (A) 9(B) 10(C) 11(D) 12 7．设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。 (A) n-1 (B) n (C) n+1 (D) 2n-1 8．设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（）。 (A) 2，3，5，8，6 (B) 3，2，5，8，6 (C) 3，2，5，6，8 (D) 2，3，6，5，8计算机专业基础综合数据结构(排序)模拟试卷2(题后含答案及解析)
长沙理工大学数据结构模拟试卷2及答案
数据结构试题2(含答案)
数据结构模拟试题二及答案
《数据结构》模拟试卷二
计算机专业基础综合(数据结构)模拟试卷2
数据结构模拟2--带答案
《数据结构》模拟试卷二及答案
utf8''数据结构模拟试卷(二)参考答案
(完整word版)数据结构试题试卷二含答案
数据结构(第二版)-模拟试题自测卷AB卷带答案2
计算机专业基础综合数据结构(树与二叉树)模拟试卷2(题后含答案及解析)
吉林大学智慧树知到“计算机科学与技术”《数据结构》网课测试题答案2
数据结构试卷及答案
数据结构试卷2(含答案)
《数据结构》全真模拟试题与解答
《数据结构》全真模拟试题二与解答02
《数据结构》模拟试题与参考答案2(四套题)
相关主题
文本预览