搜索
考试题型：选择题、填空题、简答题、算法填空、算法设计、附加题第一章绪论1.在数据结构中，数据的基本单位是___答案：CB.数据类型D.数据变量A.数据项C.数据元素2.数据结构中数据元素之间的逻辑关系被称为___B.数据的基本操作D.数据的逻辑结构C.程序的算法A.数据的存储结构3.在定义ADT时，除数据对象和数据关系外，还需说明___A.数据元素D.数据项C.基本操作B.算法4.抽象数据类型的三个组成部分分别是：数据对象，__数据关系_，基本操作。第二章线性数据结构基础1.1.对定义“inta[2]；”的正确描述是（）。A、定义一维数组a，包含a[1]和a[2]两个元素B、定义一维数组a，包含a[0]和a[1]两个元素C、定义一维数组a，包含a[0]、a[1]和a[2]三个元素D、定义一维数组a，包含a(0)、a(1)和a(2)三个元素2.具有后进先出特点的结构是_____。A）栈B）队列C）线性表D）数组3.具有先进先出特点的结构是_____。A）栈B）队列C）线性表D）数组第三章线性结构的顺序存储和实现1.已知栈S=(l,b,c,y)，Pop(S,e)操作之后栈S的结果是____。答案示例：(a,b,c)或()2.已知栈S=(u,b,m,k,v)，Push(S,‘c’)操作之后栈S的结果是____。答案示例：(a,b,c)或()3.用S表示入栈操作，X表示出栈操作，若元素入栈的顺序是(d,l,g,k,a)，为了得到(d,g,l,k,a)出栈序列，用相应的S和X表示的操作串为____。答案示例：SSXXS4.3.1.5、用S表示入栈操作，X表示出栈操作，若元素入栈的顺序是(e,n,d,c,z)，为了得到(d,z,c,n,e)出栈序列，用相应的S和X表示的操作串为____。答案示例：SSXXS5.3.2.1、已知队列Q=(q,v,d,m,e,c)，EnQueue(Q,'y')操作之后队列Q的结果是___。答案形式：（a,b）6.若用一个长度为7的数组来表示循环队列，且当前front和rear的值分别是0和1则该队列的长度是___。7.若用一个长度为6的数组来表示循环队列，且当前front和rear的值分别是1和3当从队列中删除2个元素，再加上4个元素后，rear和front的值分别为___和___。8.以下操作不属于队列的操作是：___B.构造空队列A.队尾添加一个元素C.取队列长度D.删除队列中部的元素9.在队列中，允许进行插入操作的一端称为___A.队首C.栈顶B.队尾D.栈底10.一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是___A.edcbaB.decbaD.abcdeC.dceab11.下述哪一条是顺序存储结构的优点？___B.插入运算方便A.存储密度大C.删除运算方便D.可方便地用于各种逻辑结构的存储表示12.线性表是一种逻辑结构，下面的的叙述中哪一个是错误的？___A.线性表采用顺序存储，必须占用一片连续的存储单元。D.线性表采用链接存储，便于插入和删除操作。B.线性表采用顺序存储，便于进行插入和删除操作。C.线性表采用链接存储，不必占用一片连续的存储单元。13.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。___D.单循环链表B.双链表A.顺序表C.带头结点的双循环链表第四章线性结构的链式存储和实现1.如果用不带头结点的链表表示队列，则在做删除元素操作时，（）___B.仅修改尾指针C.头尾指针都要修改D.仅将被删除元素结点的next域置为nullA.仅修改头指针2.链式实现中队列为空时，front和rear指针是否可以相等：___C.不清楚D.以上都不A.可以相等B.不可以相等3.在链式存储结构中是否存在“空间已满”的情况？__________A.存在C.不一定B.不存在第五章排序基础1.基数排序的时间复杂度是___C.O(nlogn)D.O(d(n+rd))B.O(logn)A.O(n*n)2.对序列74,29,58,63,90,98,41执行升序的简单插入算法，写出排序中各趟的结果是____。3.对序列13,25,96,76,75,47,8执行降序的希尔排序算法，增量序列为（5，3，1），写出排序中各趟的结果是____。4.插入排序算法是（稳定或不稳定）____的排序算法。5.给定关键字序列｛483，35，126，86，678，257，513，750，680，226｝，执行三趟希尔排序，设增量序列为{5,3,1}，请依次写出每一趟的排序结果。第六章哈希表1.设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：addr(15)=4;addr(38)=5;addr(61)=6;addr(84)=7；如用二次探测再散列处理冲突，关键字为49的结点的地址是____。A.8D.9C.5B.32.解决散列法中出现的冲突问题常采用的方法是______B.数字分析法、除余法、线性探测法C.数字分析法、线性探测法、多重散列法D.线性探测法、多重散列法、链地址法A.数字分析法、除余法、平方取中法3.设哈希函数为H(k)=keyMOD7，用线性探测法处理冲突。请画出依次插入元素81，80，6，83，7，13，45后，该哈希表的状态，在各元素下面标出其冲突次数，并求出等概率情况下查找成功的平均查找长度是____。(若平均长度小数超过两位，请保留两位！)4.设哈希函数为H(k)=keyMOD7，用二次探测法处理冲突。请画出依次插入元素1，71，99，20，9，27，75后，该哈希表的状态，在各元素下面标出其冲突次数，并求出等概率情况下查找成功的平均查找长度是____。5.将关键字序列：(19,14,1,29,20,23,57,11,10)，存入用数组A[0..12]实现的哈希表(见下表)，设哈希函数为：H0=keyMOD11，按线性探测再散列法处理冲突：Hi=(H0+di)MOD13。要求：(1)填写关键字序列的存储情况；0123456789101112(2)请写出在哈希表A中查找给定值K=57的过程中，所求得的哈希地址序列。第七章递归1.在有5个互不相同元素的有序表A[1..5]中折半查找值等于A[1]的元素，被比较的元素的下标依次为____。2.在序列2,5,8,11,18,23,31,39,46,55,79,92,99中，用折半查找（二分查找）算法查找是否存在关键字13，写出相应的各趟结果。并写出以C语言描述的完整算法，测试通过3.在对长度为7的有序表进行折半查找，其等概率时查找成功的平均查找长度是____。结果保留三位有效数字4.对序列31,35,19,34,77,30,0执行升序的归并排序，写出三次调用过程Merge的排序结果是____。5.归并排序算法的平均时间复杂度是____，最坏情况时间复杂度是____，辅助存储空间是____。6.对序列46,19,47,12,35,23,7,1,99,62,57,86执行升序的一趟快速排序，设其中第一个元素46为枢轴，写出一趟快速排序结果是____。并写出以C语言描述的完整算法，测试通过7.对序列35,20,88,6,54,60,80执行升序的快速排序，写出三次调用过程Partition的排序结果是____。8.快速排序算法的平均时间复杂度是____，最坏情况时间复杂度是____，辅助存储空间是____。9.某内排序方法的稳定性是指___B.该排序算法允许有相同的关键字记录A.该排序算法不允许有相同的关键字记录C.平均时间为0（nlogn）的排序方法D.执行排序算法之后，相等的关键字的原有位置顺序不变。10.针对下述快速排序算法，请进行代码填空。intPartition(SqList&L,intlow,inthigh){intpivotkey;L.r[0]=L.r[low];pivotkey=L.r[low].key;while(_____(1)________){while(lowhigh&&L.r[high].key=pivotkey)_______(2)______;L.r[low]=L.r[high];while(lowhigh&&L.r[low].key=pivotkey)_______(3)______;L.r[high]=L.r[low];}L.r[low]=L.r[0];returnlow;}voidQSort(RedType&R[],ints,intt){if(st-1){pivotloc=Partition(R,s,t);QSort(R,s,pivotloc-1);______(4)_______;}}voidQuickSort(SqList&L){Qsort(L.r,1,L.length);}第八章二叉树1.按照二叉树的定义，具有3个结点的二叉树有__种？A.3B.6C.4D.52.若二叉树采用二叉链存储结构，要交换其所有分支结点的左、右子树位置，利用______遍历方法最合适。C.后序D.按层次A.先序B.中序3.已知某二叉树的先序遍历序列是cedba，中序遍历序列是debac，它的后序遍历序列是___4.按______，二叉排序树所得到的序列是一个递增有序序列D.任意次序遍历A.中序遍历B.后序遍历C.先序遍历5.试画出与图中所示的树T等价的二叉树。6.平衡二叉树上所有结点的平衡因子可能的取值有：__________。7.在二叉树的第8层上至多有_____个结点。【二叉树的性质】8.深度为4的二叉树至多有_____个结点。9.在一棵二叉树中，度为2的结点有0个，度为1的结点有0个，则度为0的结点数为_____。10.已知某二叉树中叶子数为0，仅有一个孩子的结点数为0，则结点总数为_____。11.深度为5的完全二叉树至少有_____个结点，至多有_____个结点。12.深度9为的满二叉树有_____个结点。13.如果对一棵具有n个结点的完全二叉树按层次从1开始编号，则编号为2的结点双亲结点的编号是_____，如果其有左孩子，则左孩子的编号是_____，如果其有右孩子，则右孩子的编号是_____。14.已知二叉树T如图所示，画出其顺序存储的情况。0号位不用，如何在顺序表中计算某个结点i的左孩子与右孩子的位置号？15.已知二叉树T的先序遍历次序为LSNKJVFE，中序遍历次序为KNJSLFVE，则二叉树的后序遍历为____。16.试画出与图中所示的森林F等价的二叉树。17.试画出与图中所示的二叉树T等价的森林。18.已知二叉树T如图所示，该二叉树的带权路径长度是____。19.已知序列67,65,20,61,10,2,7，该序列____（是或不是）堆，如果是，是（大顶堆或小顶堆）____。20.已知序列8,10,29,63,23,9,31，试将其调整为一个大顶堆的结果是____。写出输出最大数63后，经调整后的大顶堆序列是____。21.已知序列40,51,39,52,10,78,21，试将其调整为一个小顶堆的结果是____。写出输出最小数10后，经调整后的小顶堆序列是____。22.堆排序算法的平均时间复杂度是____，最坏情况时间复杂度是____，辅助存储空间是____。23.画出平衡二叉树失衡的四种类型，并指出相应的调整方法(不需要写算法)第九章树1.已知树T如图所示，试画出其双亲表示法的存储结构。2.已知树T如图所示，试画出其孩子表示法的存储结构。3.一棵m阶（m3）B树，若不为空树，则树中的每个结点至多有____棵子树。A.m-1B.mC.m+1D.以上都不是4.并查集的合并操作所需的时间主要取决于树的____________；有两种方法可优化算法效率，分别是_________和__________；5.在一棵m阶B树中，若某结点的原有关键字个数等于______________，则插入一个新关键字将导致该结点分裂；若某结点及相邻兄弟结点的原有的关键字的个数等于______________，则删除一个关键字而导致结点合并。第