2024年高等教育工学类自考-02331数据结构考试近5年真题集锦（频考类试题）带答案

（图片大小可自由调整）2024年高等教育工学类自考-02331数据结构考试近5年真题集锦（频考类试题）带答案第I卷一.参考题库(共100题)1.若L是splist类型的顺序表，则表中的第i个数据元素是（）。2.对于结点类型为LNode的单链表，编写出下列算法： 统计出单链表中结点的值等于给定值x的结点数。3.快速排序方法在（）情况下最不利于发挥其长处。A、要排序的数据量太大B、要排序的数据中有多个相同值C、要排序的数据已基本有序D、要排序的数据个数为奇数4.树的定义具有递归性。5.数据结构里，关于传递描述正确的是（）。A、值传递传递的是变量的值B、地址传递传递的是一个地址C、值传递时，实参不会随着形参的变化而变化D、地址传递时，实参会随着形参的变化而变化6.一个图的广度优先搜索树是惟一的7.具有n个顶点的有向无环图最多有多少条边？8.栈和队列的共同点是（）。A、都是树形结构B、都是限制存取点的线性结构C、都是线性结构D、都不对9.序列12，10，13，11，16，14，采用冒泡排序算法，经一趟冒泡后，序列的结果是（）10.n个结点无向完全图的的边数为（），n个结点的生成树的边数为（）。11.假定一组记录为(46,79,56,64,38,40,84,43)，在冒泡排序的过程中进行第一趟排序时，元素79将最终下沉到其后第（）个元素的位置。12.序列14，12，15，13，18，16，采用冒泡排序算法，经一趟冒泡后，序列的结果是（）13.二叉树中每个结点的两棵子树是有序的。14.所谓静态链表就是一直不发生变化的链表。15.下列选项中是C语言中的计算字符串长度的是（）。A、strcpyB、strcatC、strcmpD、strlen16.具有3个结点的二叉树的有（）种不同形态。A、6B、5C、3D、417.根据数据结构的类型的定义分析算法： if语句中的条件应为什么？18.栈与队列都是操作受限的线性表。19.设n，m为一棵二叉树上的两个结点，在中序遍历序列中n在m前的条件是（）。A、 n在m右方B、 n在m左方C、 n是m的祖先D、 n是m的子孙20.假定一棵二叉树的结点数为18个，则它的最小高度（）A、4B、5C、6D、1821.简述ISAM文件的组织方法。22.数组a经初始化char a[]=“English”；a[7]中存放的是（）。23.设一个带头结点的单向链表的头指针为head，设计算法，将链表的记录，按照data域的值递增排序。24.四种排序（）的空间复杂度最大。A、快速排序B、冒泡排序C、希尔排序D、堆25.对于长度为20的顺序表，若采用二分查找法，则查找第八个元素的查找长度（）A、2B、3C、4D、526.给定排序码的序列{39、33、13、15、58、41、27、46、23}。请回答：采用希尔（Shell）排序（步长分别为5，3，1），写出各趟排序结果。27.下列选项中是用来定义结构体的关键字是（）。A、structB、functionC、staticD、stack28.在m阶B-树中每个结点上至少有个关键字，最多有m个关键字。29.索引顺序文件既能进行（）存取，又能进行（）存取，因而是最常用的文件组织方法之一，通常用（）结构来组织索引。30.图G的生成树是该图的一个极小连通子图31.对一个有向图进行拓扑排序，一定可以将图的所有顶点按其关键码大小排列到一个拓扑有序的序列中。32.非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（）。33.设一棵二叉树结点的先序遍历序历为：ABDECFGH，中序遍历序历为：DEBAFCHG，则二叉树中叶结点是（）。34.具有10个叶子结点的二叉树中有（）个度为2的结点。A、8B、9C、10D、1135.栈的操作，入栈又叫压栈，一般用（）代替。A、pushB、popC、outD、in36.对稀疏矩阵进行压缩存储，可采用三元组表，一个6行7列的稀疏矩阵A共有38个零元素，其相应的三元组表共有（）个元素。37.数据结构里，下面关于串的的叙述中，哪一个是不正确的？（）A、串是字符的有限序列B、空串是由空格构成的串C、模式匹配是串的一种重要运算D、串既可以采用顺序存储，也可以采用链式存储38.有穷性是算法的特性。39.散列表的查找效率取决于散列表造表时选取的散列函数和处理冲突的方法。40.简述常用的四种哈希函数及其计算规则。41.已知一组记录为（46，74，53，14，26，38，86，65，27，34），给出采用堆排序法进行排序时每一趟的排序结果。42.算法的效率用时间复杂度来衡量。43.以单链表为存储结构，写一个直接选择排序算法。44.在一个单向链表中，在p所指结点之后插入一个s所指的结点时，可执行s->next=p->next；和（）A、p=sB、p->next=s->nextC、p=s->nextD、p->next=s45.试编写算法实现链表的就地逆置（不增加存储空间），即把链表A中的数据元素（a1，a2，…，an）逆置为（an，an-1，…，a1）。46.二叉排序树删除一个结点后，仍是二叉排序树。47.二叉树必须有左子树和右子树，不能只有右子树。48.已知指针p指向单链表中某个结点，则语句p->next=p->next->next的作用（）。49.下面（）可以判断出一个有向图中是否有环（回路）。A、广度优先遍历B、拓扑排序C、求最短路径D、求关键路径50.简述顺序表和链表存储方式的特点。51.虽然关键字序列的顺序不一样，但依次生成的二叉排序树是一样的。52.对于长度为18的顺序存储的有序表，若采用折半查找，则查找第15个元素的比较次数为（）。A、 3B、 4C、 5D、 653.具有n个结点的完全二叉树若按层次从上到下，从左到右对其编号（根结点为1），则编号最大的分支结点序号是（），编号最小的分支结点序号是（），编号最大的叶子结点序号是（），编号最小的叶子结点序号是（）54.在一个堆的顺序存储中，若一个元素的下标为i，则它的左孩子元素的下标为（），右孩子元素的下标为（）。55.若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。A、快速排序B、堆排序C、归并排序D、直接插入排序56.在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的（）、（）和（）三项。57.若二叉排序树中关键码互不相同，则其中最小元素和最大元素一定是叶子结点。58.下列排序算法中，（）不能保证每趟排序至少能将一个元素放到其最终的位置上。A、希尔排序B、快速排序C、冒泡排序D、堆排序59.假定一个待哈希存储的线性表为（32，75，29，63，48，94，25，36，18，70，49，80），哈希地址空间为HT[12]，若采用除留余数法构造哈希函数和拉链法处理冲突，试画出最后得到的哈希表，并求出平均查找长度。60.数据结构里，函数调用是，形参传给实参，是单向传递的。61.下列选项中是结构体普通变量或指针变量引用其成员时使用时的符号的是（）。A、->符号B、.符号C、->>符号D、#符号62.数据结构里，二叉树不可以是空二叉树。63.数据结构涉及哪几个方面？64.设查找表为（7，15，21，22，40，58，68，80，88，89，120），元素的下标依次为1，2，3，……，11。 （1）画出对上述查找表进行折半查找所对应的判定树（树中结点用下标表示） （2）说明成功查找到元素40需要经过多少次比较？ （3）求在等概率条件下，成功查找的平均比较次数？65.拓扑排序是指结点的值是有序排序的。66.若一组记录的排序码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。A、38，40，46，56，79，84B、40，38，46，79，56，84C、40，38，46，56，79，84D、40，38，46，84，56，7967.在对n个元素进行冒泡排序的过程中，至少需要（）趟完成。A、1B、nC、n-1D、n/268.设在链式存储的线性表中，设结点结构为datalink，欲在p结点后插入一个结点q的关键步骤为（）。A、q->link=p->link；p->link=q；B、p->link=q->link；p->link=q；C、q->link=p->link；q->link=p；D、p->link=q->link；q->link=p；69.设有一顺序栈，元素1，2，3，4，5依次进栈，如果出栈顺序是2，4，3，5，1则栈的容量至少是：（）A、1B、2C、3D、470.在单链表中，要访问某个结点，只要知道该结点的地址即可；因此，单链表是一种随机存取结构。71.拉链法（链地址法）72.当采用分快查找时，数据的组织方式为（）。A、数据分成若干块，每块内数据有序B、数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C、数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D、数据分成若干块，每块（除最后一块外）中数据个数需相同73.设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a85的地址为（）74.数据结构里，函数参数为哪项时，参数传递属于地址传递。（）A、数组B、float型C、char型D、int型75.设有一个已按各元素值排好序的线性表，长度为125，用折半查找与给定值相等的元素，若查找成功，则至少需要比较（）次，至多需比较（）次。76.权值为{1，2，6，8}的四个结点构成的哈夫曼树的带权路径长度是（）。A、18B、28C、19D、2977.抽象数据类型与计算机内部表示和实现无关78.已知如下所示长度为12的表：（Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec）若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。79.假定一个顺序循环队列存储于数组a[n]中，其队首和队尾指针分别用front和rear表示，则判断队满的条件为（）A、（rear - 1）％ n == frontB、（rear + 1）％ n == frontC、（front - 1）％ n == rearD、（front + 1）％ n == rear80.对于一个图G，若边集合E（G）为无向边的集合，则称该图为（）。81.数据结构里，二叉树中的结点都是度为2的结点。82.简述堆的定义和堆的构建过程。83.若一棵满二叉树含有121个结点，则该树的深度为（）。84.在完全二叉树中，若一个结点是叶结点，则它没有（）。A、左孩子结点B、右孩子结点C、左孩子和右孩子结点D、左孩子结点，右孩子结点和兄弟结点85.如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）。A、完全图B、连通图C、有回路D、一棵树86.图的广度优先搜索类似于树的（）次序遍历。A、先根B、中根C、后根D、层次87.对于双目操作符，其重载函数带有（）个参数，其中至少有一个为（）的类型。88.设G1=（V1，E1）和G2=（V2，E2）为两个图，如果V1V2，E1E2则称（）。A、G1是G2的子图B、G2是G1的子图C、G1是G2的连通分量D、G2是G1的连通分量89.在下面冒泡排序算法中填入适当内容，以使该算法在发现有序时能及时停止。 bubble（R） RectypeR[n]； {inti，j，exchang； Rectypetemp； i=1； do {exchang=False； for（j=n；j>=¬¬i+1；j--） if（R[j]<r[j-1]{temp=R[j-1]； R[j-1]=R[j]； R[j]=temp； exchang=True； } （）； }while（exchang=False）； }</r[j-1]90.假设表达式有单字母变量和双目四则运算符构成。试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰表达式。91.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（） A、AB、BC、CD、D92.散列表中解决冲突的两种方法是（）和（）93.对给定的序号j（1＜j＜n），要求在无序记录A[1]~A[n]中找到按关键码从小到大排在第j位上的记录，试利用快速排序的划分思想设计算法实现上述查找。94.在一非空二叉树的中，根结点的右边只有（）上的所有结点。95.设散列表的地址范围是[0..9]，散列函数为并采用链表处理冲突，请画出元素7、4、5、3、6、2、8、9依次插入散列表的存储结构。96.在线性表的单链表存储中，若一个元素所在结点地址为p，则其后继结点的地址为（）97.下列四个序列中，（）是堆。A、75，65，30，15，25，45，20，10B、75，65，45，10，30，25，20，15C、75，45，65，30，15，25，20，10D、75，45，65，10，25，30，20，1598.编写循环队列入队和出队的算法。99.在一个具有n个顶点的无向图中，要连通所有顶点则至少需要（）条边。100.简述森林转换为二叉树的具体步骤。第I卷参考答案一.参考题库1.参考答案：Lelem[i-1]2.参考答案：3.参考答案：C4.参考答案：正确5.参考答案：A,B,C,D6.参考答案：错误7.参考答案：具有n个顶点的有向无环图最多有n×（n—1）/2条边。 这是一个拓扑排序相关的问题。—个有向无环图至少可以排出一个拓扑序列，不妨设这n个顶点排成的拓扑序列为v1，v2，v3，„，vn，那么在这个序列中，每个顶点vi只可能与排在它后面的顶点之间存在着以vi为弧尾的弧，最多有n-i条，因此在整个图中最多有（n-1）+（n-2）+„+2+1=n×（n-1）/2条边。8.参考答案：B,C9.参考答案：10，12，11，13，14，1610.参考答案：n(n-1)/2；n-111.参考答案：412.参考答案：12，14，13，15，16，1813.参考答案：正确14.参考答案：错误15.参考答案：D16.参考答案：B17.参考答案：S.top= =S.MaxSize-1118.参考答案：正确19.参考答案：B20.参考答案：B21.参考答案：在ISAM文件中，每个柱面的磁道被分为3个部分： A.一部分磁道作为记录存储的基本的区，其中每一磁道将记录按主关键字大小进行有序顺序存储。 B.一部分磁道作为记录存储的溢出区，在一个已满磁道中插入新记录时，就会产生溢出的记录（即该磁道容纳不下的记录），这些溢出记录以链表形式存储在溢出区中。 C.一部分磁道作为索引区，用于存储磁道索引表。与基本的区和溢出区相对应，表中的每一索引项又由基本索引项和溢出索引项组成。基本索引项用来存放基本的区一个磁道中记录的最大关键字值和第一个记录的位置；溢出索引项用来存放从该磁道溢出记录的最大关键字值和该磁道在溢出区中的第一个溢出记录的位置。22.参考答案：字符串的结束符23.参考答案：voidassending（Lnode*heaD. {Lnode*p，*q，*r，*s； p=head->next；q=p->next；p->next=NULL； while（q） {r=q；q=q->next； if（r->datadatA. {r->next=p；head->next=r；p=r；} else {while（!p&&r->data>p->datA. {s=p；p=p->next；} r->next=p；s->next=r；} p=head->next；} }24.参考答案：A25.参考答案：C26.参考答案：27.参考答案：A28.参考答案：错误29.参考答案：顺序；二分；树30.参考答案：错误31.参考答案：错误32.参考答案：p->next=head33.参考答案：E、F、H34.参考答案：B35.参考答案：A36.参考答案：437.参考答案：B38.参考答案：错误39.参考答案：正确40.参考答案：除余法：选取一个适当的正整数p（通常p为不大于哈希表存储空间尺寸的最大素数），以元素的关键字值k除以p，得到的余数作为元素的存储地址，即h（k）=k%p。 数字分析法：若元素的关键字由多位组成，且关键字的位数比存储空间地址码位数多、每一位的取值范围及关键字的取值分布情况预先知道，则可以对元素关键字的各位进行分析，去掉分布较集中的位、保留分布较均匀的位。 折叠法：若元素的关键字由多位组成，且关键字的位数比存储空间地址码位数多，但关键字的取值分布情况未知，则可以用折叠法将关键字分为几段（除了最后一段位数可以少一些，其他各段的位数均等于存储空间地址码位数），并将所有段的值做叠加求和运算，将叠加和的最高位进位舍去后取剩余部分作为元素的存储地址。 平方取中法：对元素的关键字值求平方，并取中间几位作为元素的存储地址。41.参考答案：42.参考答案