2024年大学试题(计算机科学)-数据结构笔试考试历年高频考点试题摘选含答案

2024年大学试题(计算机科学)-数据结构笔试考试历年高频考点试题摘选含答案第1卷一.参考题库(共75题)1.编写算法求给定结点在二叉排序树中所在的层数。2.顺序表的定义如下： 其中ElemType的含义是：通用数据类型；size的含义是：（）。3.在索引查找中，假定查找表（即主表）的长度为96，被等分为8个子表，则进行索引查找的平均查找长度为（）。4.图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。5.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K%9作为散列函数，则散列地址为1的元素有（）个。A、1B、2C、3D、46.在顺序队列中，什么叫真溢出？什么叫假溢出？为什么顺序队列常都采用循环队列结构？7.图所示是一个无向带权图，请分别按Prim算法和Kruskal算法求最小生成树。 8.数据的存储结构被分为（）、（）、（）和（）四种。9.一个连通图的（）是一个极小连通子图。10.对于右图所示的树： 写出先根遍历得到的结点序列。11.顺序表的特点是（）。A、表中元素的个数为表长B、按顺序方式存储数据元素C、逻辑结构中相邻的结点在存储结构中仍相邻D、按表中元素的次序存储12.以下与数据的存储结构无关的术语是（）。A、循环队列B、链表C、哈希表D、栈13.实现递归调用属于（）的应用。A、栈B、数组C、队列D、二叉树14.在单链表中，要取得某个元素，只要知道该元素所在结点的地址即可，因此单链表是随机存取结构。15.有向图中的结点前驱后继关系的特征是（）。16.某循环队列的容量MAXSIZE=6，队头指针front=3，队尾指针rear=0，则该队列有（）个元素。17.在散列技术中，处理冲突的两种主要方法是（）和（）。18.序列3，1，7，18，6，9，13，12经一趟归并排序的结果为（）。19.字符串的长度是指（）A、串中不同字符的个数B、串中不同字母的个数C、串中所含字符的个数D、串中不同数字的个数20.假定一棵二叉树的结点数为19，则它的最小深度为（），最大深度为（）21.假设有一个带表头结点的链表，表头指针为head，每个结点含三个域：data，next和prior。其中data为整型数域，next和prior均为指针域。现在所有结点已经由next域连接起来，试编一个算法，利用prior域（此域初值为NULL）把所有结点按照其值从小到大的顺序链接起来。22.在初始化一个稀疏矩阵的函数定义中，矩阵形参应说明为（）参数。23.给定排序码的序列{39、33、13、15、58、41、27、46、23}。请回答：采用快速排序的方法进行排序，写出各趟排序结果。24.某二叉树的前序遍历序列是ABCDEFG，中序遍历序列是CBDAFGE，则其后序遍历序列是（）。25.折半搜索只适用与有序表，包括有序的顺序表和有序的链表。26.哈夫曼树是其树的带权路径长度（）的二叉树。27.将二叉排序树T按前序遍历序列依次插入初始为空的二叉排序树T’中，则T与T’是相同的，这种说法是否正确？28.假设一个栈的输入序列为A，B，C，D，E，则下列序列中不可能是栈的输出序列的是（）A、B、C、D、A、EB、E、D、A、C、BC、B、C、A、D、ED、A、E、D、C、B29.用链接方式存储的队列，在进行插入运算时（）A、仅修改头指针B、头、尾指针都要修改C、仅修改尾指针D、头、尾指针可能都要修改30.对于n个记录的集合进行归并排序，所需的附加空间消耗是（）31.设有一个长度为35的顺序表，要在第5个元素之前插入1个元素（也就是插入元素作为新表的第5个元素），则移动元素个数为（）A、30B、31C、5D、632.对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。33.采用折半查找方法进行查找，数据文件应为（），且限于（）。A、有序表；顺序存储结构B、有序表；链式存储结构C、随机表；顺序存储结构D、随机表；链式存储结构34.下列关于图遍历的说法不正确的是（）。A、连通图的深度优先搜索是一个递归过程B、图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C、非连通图不能用深度优先搜索法D、图的遍历要求每一顶点仅被访问一次35.给定一棵用链表表示的二叉树，其根结点为root，试写出求二叉树各结点的层数的算法。36.对包含n个元素的哈希表进行查找，平均查找长度为（）A、O（log2n）B、O（n）C、O（nlog2n）D、不直接依赖于n37.简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。38.试编写算法，计算的i!*2i值并存入数组a[0..arrsize-1]的第i-1个分量中（i=1，2，…，n）。假设计算机中允许的整数最大值为maxint，则当n>arrsize或对某个k（1≤k≤n），使k!·2k＞maxint时，应按出错处理。注意选择你认为较好的出错处理方法。39.如果将线性数据结构关系描述为1：1，那么树型和图型数据结构应分别为（）和（）。40.数据元素之间（）的整体称为逻辑结构。41.根据图的存储结构进行某种次序的遍历，得到的顶点序列是（）（唯一/不唯一）的。42.已知某二叉树的后序遍历为dabcc，中序遍历为debac，则它的前序遍历为（）。43.已知二叉排序树的左右子树均不为空，则（）上所有结点的值均小于它的根结点值，（）上所有结点的值均大于它的根结点的值。44.下面算法的时间复杂度为（） A、O（1）B、O（n）C、O（n2）D、O（n!）45.子串“acd”在主串“abdcacdefac”中的位置是（）A、3B、5C、7D、146.已知一维数组A采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144，则第一个元素的地址是（）。A、108B、180C、176D、11247.在线性表的顺序存储中，元素之间的逻辑关系是通过（）决定的，在线性表的链接存储中，元素之间的逻辑关系是通过（）决定的。48.设有两个串p和q，求q在p中首次出现的位置的运算称作（）A、连接B、模式匹配C、求子串D、求串长49.数据元素之间的逻辑关系，也称（）。50.已知一个带头结点单链表L，在表头元素前插入新结点*s的语句为：（）A、 L=s；s-＞next=L；B、 s-＞next=L->next；L-＞next=s；C、 s=L；s-＞next=L；D、 s-＞next=L； s=L；51.在散列存储中，装填因子a的值越大，则（）；a的值越小，则（）52.已知单链表上一结点的指针为p，则删除该结点后继的正确操作语句是：（）A、 s= p-＞next； p=p-＞next；  free（s）；B、 p=p-＞next；  free（p）；C、 s= p-＞next； p-＞next=s-＞next；  free（s）；D、 p=p-＞next；  free（p-＞next）；53.要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需（）一个位置，移动过程是从（）向（）依次移动每一个元素。54.设一组初始记录关键字序列（5，2，6，3，8），以第一个记录关键字5为基准进行一趟快速排序的结果为（）。A、2，3，5，8，6B、3，2，5，8，6C、3，2，5，6，8D、2，3，6，5，855.shop是一个结构体普通变量，它有一个成员变量叫price，则下列选项中关于使用price变量格式不正确的是（）。A、shop->priceB、shop.priceC、Cshop（price）D、shop&price56.已知指针p指向单链表中某个结点，则语句p->next=p->next->next的作用（）。57.（）可以看做是从具体问题抽象出来的数学模型。58.strlen计算字符串长度时候不计算’/0’在内。59.画出对下面的5阶B树插入关键字37后的结果。60.设待排序文件各个记录的排序码序列为：19、23、2、67、39、91、43、25，进行堆排序，请回答：画出初始建成的大根堆对应的完全二叉树。61.（）在链表中进行操作比在顺序表中进行操作效率高。A、顺序查找B、折半查找C、分块查找D、插入62.简述索引文件的检索过程。63.广度优先周游一棵二叉树所得到的结点序列，叫作这棵二叉树的层次序列。64.一个队列的入队序列是1，2，3，4，则队列的出队序列是（）。A、1，2，3，4B、4，3，2，1C、1，4，3，2D、3，4，1，265.栈的应用比较广泛，入栈和出栈都在栈的一端，这端称为（）。A、栈顶B、栈底C、栈中D、都不对66.在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行（）操作。A、s->next=p->next；p->next=s；B、q->next=s；s->next=p；C、p->next=s->next；s->next=p；D、p->next=s；s->next=q；67.数组通常只有两种运算：（）和（），这决定了数组通常采用（）结构来实现存储。68.在数据的树型结构中，数据元素之间为（）的关系。A、0︰0B、1︰1C、1︰nD、m︰n69.试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。 70.递归的算法简单、易懂、容易编写，而且执行效率也高。71.堆排序所需的时间与待排序的记录个数无关。72.判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以用（）。A、求关键路径的方法B、求最短路径的方法C、广度优先遍历算法D、深度优先遍历算法73.有向图G可拓扑排序的判别条件是（）。74.线性表（a1，a2，…，an）以链接方式存储时，访问第i位置元素的时间复杂性为（）。A、O（i）B、O（1）C、O（n）D、O（i-1）75.假设循环队列中只设rear和quelen来分别指示队尾元素的位置和队中元素的个数，试给出判别此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。第2卷一.参考题库(共75题)1.当待排序序列基本有序或个数较小的情况下，最佳的内部排序方法是（），就平均时间而言，（）最佳。2.给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。3.实现任意二叉树的后序遍历的非递归算法而不适用栈结构，最佳的二叉树方法是采用（）。4.在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（）。A、s-＞next=p+1； p-＞next=s；B、（*p）.next=s； （*s）.next=（*p）.next；C、s->next=p-＞next； p-＞next=s-＞next；D、s->next=p-＞next； p-＞next=s；5.链表不具有的特点是（）。A、可随机访问任一元素B、插入删除不需要移动元素C、不必事先估计存储空间D、所需空间与线性表长度成正比6.栈和队列是两种特殊的线性表，栈的操作特性是（），队列的操作特性是（），栈和队列的主要区别在于（）。7.设有向无环图G中的有向边集合E={，，，}，则下列属于该有向图G的一种拓扑排序序列的是（）A、1，2，3，4B、2，3，4，1C、1，4，2，3D、1，2，4，38.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（）A、acbedB、decabC、deabcD、cedba9.在完全二叉树中，若某结点元左孩子，则它必是叶结点。10.采用简单选择排序，比较次数与移动次数分别为（）。A、O（n），O（logn）B、O（logn），0（n*n）C、0（n*n），0（n）D、0（nlogn），0（n）11.设有程序段 i=1； while(iA、O(n)B、O(logn)C、O(nlogn)D、O(n2)12.在下列存储形式中，（）不是树的存储形式。A、双亲表示法B、顺序存储表示C、孩子兄弟表示法D、孩子链表表示法13.顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作的时间代价基本上都是等效的。则插入一个元素大约要移动表中的（）个元素。14.对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（n）。15.对二叉排序树进行（）遍历，可以得到该二叉树所有结点构成的从小到大排序序列。A、前序B、中序C、后序D、按层次16.设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树的结点个数为n，森林F中第一棵树的结点的个数是（）。A、m－nB、m－n－1C、n＋1D、不能确定17.已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，…，nk个度为k的结点，问该树中有多少个叶子结点？18.对于n个记录的集合进行快速排序，所需要的平均时间是O（nlog2n）。19.数据结构里，邻接表是图的一种存储结构，是一维数组和链表的结合。20.下列四个序列中，（）不是快速排序第一趟的可能结果。A、[68，11，69，23，18，70，73]93B、11[68，69，23，18，70，73，93]C、[68，11，69，23，18]70[93，73]D、[18，11，23]93[68，70，69，73]21.一个序列中有10000个元素，若只想得到其中前10个最小元素，则最好采用（）方法。A、快速排序B、堆排序C、插入排序D、归并排序22.顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？23.证明：对任一满二叉树，其分枝数B＝2（n0-1）。（其中，n0为终端结点数）24.已知如图所示的一个网，按照Prim方法，从顶点1 出发，求该网的最小生成树的产生过程。 25.chars[]="where"；则s数组的的长度是（）。A、4B、5C、6D、726.设图的邻接矩阵为，则该图为（）。 A、有向图B、无向图C、强连通图D、完全图27.truct的作用是（）。A、定义整型变量B、定义结构体类型C、定义浮点型变量D、定义字符型变量28.在一个单向链表中p所指结点之后插入一个s所指的结点时，可执行（）。A、p->next=s；s->next=p->nextB、p->next=s->next；C、p=s->nextD、s->next=p->next； p->next=s；29.KMP模式匹配算法是由（）同时发现的，因此而得名。A、莫里斯B、克努特C、普拉特D、克鲁伊特30.在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点查找任何一个元素。31.在任意一棵非空二叉排序树，删除某结点后又将其插入，则所得二叉排序树与删除前原二叉排序树相同。32.设长度为n的链队列用单循环链表表示，若只设头指针，则入队和出队操作的时间复杂度分别为（）和（）；若只设尾指针，则入队和出对操作的时间复杂度分别为（）和（）。33.当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快速度存取线性表中的元素时，应采用（）存储结构。34.假定一个循环顺序队列的队首和队尾指针分别为f和r，则判断队空的条件是（）A、f+1==rB、r+1==fC、f==0D、f==r35.算法分析的目的是找出数据结构的合理性。36.设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p->llink和p->rlink表示，则下列等式中（）成立。A、p=p->llinkB、p=p->rlinkC、p=p->llink->llinkD、p=p->llink->rlink37.数据结构的四种基本类型中，（）的元素是一对多关系。38.数据结构里，数组作为参数的时候，其传递方式是（）。A、地址传递B、值传递C、形参传递D、实参传递39.一组记录排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（）A、79，46，56，38，40，80B、84，79，56，38，40，46C、84，79，56，46，40，38D、84，56，79，40，46，3840.已知哈希表地址空间为A[0..8]，哈希函数为H（k）=k mod 7，采用线性探测再散列处理冲突。若依次将数据序列：76，45，88，21，94，77，17存入该散列表中在等概率情况下查找成功的平均查找长度为（）。A、0B、1C、2D、3E、4F、5G、6H、741.线性表就是顺序存储的表42.利用简单选择排序对n个记录进行排序，最坏情况下，记录交换的次数为（）。43.编写一个算法，利用栈的基本运算返回指定栈中的栈底元素。44.在具有头结点的单链表中，头指针指向链表的第一个数据结点。45.当α的值较小时，散列存储通常比其他存储方式具有（）的查找速度。A、较慢B、较快C、相同D、不确定46.试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作为存储结构，且树中结点的关键字均不同。47.设一组初始记录关键字序列为（60，80，55，40，42，85），则以第一个关键字45为基准而得到的一趟快速排序结果是（）A、40，42，60，55，80，85B、42，45，55，60，85，80C、42，40，55，60，80，85D、42，40，60，85，55，8048.设有数据结构（D，R），其中D={1，2，3，4，5，6}，R={（1，2），（2，3），（2，4），（3，4），（3，5），（3，6），（4，5），（4，6）}。试画出其逻辑结构图并指出属于何种结构。49.一个数组a所占有的存储空间的大小即数组长度为（），下标为i的元素a[i]的存储地址为（），或者为（）。50.一个具有n个顶点的有向图最多有（）条边。A、n×（n-1）/2B、n×（n-1）C、n×（n+1）/2D、n251.链式栈与顺序栈相比，一个明显的优点是通常不会出现栈满的情况。52.散列技术中的冲突指的是（）。A、两个元素具有相同的序号B、两个元素的键值不同，而其他属性相同C、数据元素过多D、不同键值的元素对应于相同的存储地址53.数据结构里，以下字符串处理函数中，返回值不是char的是（）。A、strcatB、strcmpC、strcpyD、strlen54.在单链表中，除了首元结点外，任一结点的存储位置由（）指示。55.哈夫曼树是带权路径长度（）的二叉树。56.数据结构里，算法的设计要求中健壮性是指（）。A、算法可以忽略特殊情况B、算法应该能对输入数据不合法的情况做合适的处理C、算法可以不关注不合法的数据D、以上都不对57.有一关键字序列（265，301，751，129，937，863，742，694，076，438），写出希尔排序的每趟排序结果。（取增量为5，3，1）58.设计一个判别表达式中左右括号是否配对的算法，采用（）数据结构最佳A、顺序表B、栈C、队列D、链表59.设一个有向图为G=（V，E），其中V={v1，v2，v3，v4}，E={，，，，}，请回答下列各问：（2）画出该图的邻接矩阵存储结构图示。60.如果将所有中国人按照生日来排序，则使用（）算法最快。A、归并排序B、希尔排序C、快速排序D、基数排序61.下面是利用队列对二叉树进行从上往下，从左往右的层次遍历算法。 62.结点最少的树为（），结点最少的二叉树为（）63.n个顶点e条边的图，若采用邻接表存储，则空间复杂度为（）。64.每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做（）排序。A、插入B、堆C、快速D、归并65.线性有序表（a1，a2，a3，…，a256）是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索（）次。设有100个结点，用二分法查找时，最大比较次数是（）。66.栈是特殊的线性表，其特殊性在于（）67.表长为n的顺序存储的线性表，当在任意位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（），删除一个元素需要移动元素的平均个数为（）A、（n-1）/2B、nC、（n+1）/2D、n/268.简述各种查找算法的适用范围。69.将下面图5-16所示的树转换为二叉树，图5-17所示的二叉树转换为树或森林。 70.索引顺序文件是一种特殊的顺序文件，因此通常存放在磁带上。71.编写一个算法，求出邻接表表示的有向图中序号为numb的顶点的度数。72.设哈希（散列）表表长为15（哈希地址为0~14），哈希函数为H（key）=key%11，冲突处理采用线性探测Hi=（H（key）+1）%11，则将一列数15，20，26，30，35，40存储该哈希表，元素40的哈希地址为（）73.推到和估算算法的时间复杂度属于（）。A、事前分析估算的方法B、事后统计方法C、运行后计算时间D、都不对74.向一个循环队列中插入元素时，需要首先移动（），然后再向所指位置（）新插入的元素。75.对于给定结点的关键字集合K={5，7，3，1，9，6，4，8，2，10}， （1）试构造一棵二叉排序树； （2）求等概率情况下的平均查找长度ASL。第1卷参考答案一.参考题库1.参考答案：根据题目要求采用递归方法，从根结点开始查找结点p，若待查结点是根结点，则深度为1，否则到左子树（或右子树）上去找，查找深度加1。 具体算法如下： 2.参考答案：顺序表中元素的个数3.参考答案：114.参考答案：前序；栈；层序；队列5.参考答案：D6.参考答案：当front0，rear=M时，再有元素入队发生溢出，称之为“假溢出”，存储空间还有剩余。为了改进这种状况，可以将顺序队列想象为一个首尾相接的环状空间，称之为循环队列。7.参考答案：按Prim算法求最小生成树的过程如下： 按Kruskal算法求最小生成树的过程如下： 8.参考答案：顺序；链接；索引；散列9.参考答案：生成树10.参考答案： abecfgkdhilmj11.参考答案：B12.参考答案：D13.参考答案：A14.参考答案：错误15.参考答案：一个结点可能有若干个前驱，也可能有若干个后继16.参考答案：317.参考答案：开放定址法；拉链法18.参考答案：1，3，7，18，6，9，12，1319.参考答案：C20.参考答案：5；1921.参考答案：22.参考答案：引用（或指针）23.参考答案： 24.参考答案：CDBGFEA25.参考答案：错误26.参考答案：最小27.参考答案：正确28.参考答案：B29.参考答案：D30.参考答案：O（n）31.参考答案：B32.参考答案：33.参考答案：A34.参考答案：C35.参考答案：36.参考答案：D37.参考答案：38.参考答案： 39.参考答案：1：N；M：N40.参考答案：逻辑关系41.参考答案：唯一42.参考答案：cedba43.参考答案：左子树；右子树44.参考答案：B45.参考答案：B46.参考答案：D47.参考答案：物理存储位置；链域的指针48.参考答案：B49.参考答案：数据的逻辑结构50.参考答案：B51.参考答案：产生冲突的可能性就越大；产生冲突的可能性就越小52.参考答案：C53.参考答案：前移；前；后54.参考答案：C55.参考答案：A,C,D56.参考答案：删除p的后继结点57.参考答案：数据的逻辑结构58.参考答案：正确59.参考答案： 60.参考答案： 61.参考答案：D62.参考答案： 索引文件的检索过程为： A.将索引表读入内存中，并根据检索条件在索引表中进行查找（由于索引项按关键字有序排列，因此在索引表上可以采用折半查找算法）。 B.若索引表中存在匹配项，则根据匹配索引项中存储的物理地址直接读取外存上的相应记录；若索引表中不存在该记录，则说明外存上也不存在该记录、不需做外存访问操作。63.参考答案：正确64.参考答案：A65.参考答案：A66.参考答案：B67.参考答案：存取；修改；顺序存储68.参考答案：C69.参考答案：DLR：A B D F J G K C E H I L M   LDR：B F J D G K A C H E L I M   LRD://J F K G D B H L M I E C A70.参考答案：错误71.参考答案：错误72.参考答案：D73.参考答案：没有回路74.参考答案：C75.参考答案：根据题意，可定义该循环队列的存储结构： 第2卷参考答案一.参考题库1.参考答案：直接插入排序；快速排序2.参考答案：正确3.参考答案：三叉列表的存储结构4.参考答案：D5.参考答案：A6.参考答案：后进先出；先进先出；对插入和删除操作限定的位置不同7.参考答案：A8.参考答案：D9.参考答案：正确10.参考答案：C11.参考答案：B12.参考答案：D13.参考答案：n/214.参考答案：正确15.参考答案：B16.参考答案：A17.参考答案： 18.参考答案：正确19.参考答案：正确20.参考答案：D21.参考答案：B22.参考答案： 一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。 采用循环队列是解决假溢出的途径。 另外，解决队满队空的办法有三： ①设置一个布尔变量以