2024年高等教育工学类自考-02331数据结构历年考试高频考点试题附带答案

2024年高等教育工学类自考-02331数据结构历年考试高频考点试题附带答案（图片大小可自由调整）第1卷一.参考题库(共25题)1.对于一棵具有n个结点的二叉树，若一个结点的编号为i（1≤i≤n），则它的左孩子结点的编号为（），右孩子结点的编号为（），双亲结点的编号为（）2.如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。3.以孩子兄弟表示法做存储结构，求树中结点x的第i个孩子。4.在高级语言中，不可以定义结构体类型的指针变量。5.算法分析的两个主要方面是（）。A、空间复杂度和时间复杂度B、正确性和简单性C、可读性和文档性D、数据复杂性和程序复杂性6.队列操作的原则是（）。A、先进先出B、后进先出C、只能进行插入D、只能进行删除7.对顺序表的优缺点，以下说法错误的是（）A、无需为表示结点间的逻辑关系而增加额外的存储空间B、可以方便地随机存取表中的任一结点C、插入和删除运算较为方便D、由于要求占用连续空间，所以存储分配只能预先进行（静态分配）8.栈是一种特殊的线性表，允许插入和删除运算的一端称为（）。不允许插入和删除运算的一端称为（）。9.程序越短，程序运行的时间就越少。10.假设R是集合M上的一个关系，R的定义是什么？对实际问题而言，其含义是什么？11.在树的概念中，下列选项中关于树的兄弟描述正确的是（）A、双亲是同一个结点B、双亲是不同的结点C、在树中不同的层D、都不对12.广义表（f ，h ，（a ，b，d，c），d ，e ，（（i ，j），k ））的长度是（）。13.如下图所示，若从顶点a出发，按图的深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。 A、abecdfB、acfebdC、aebcfdD、aedfcb14.结点的层次15.设散列表表长m=14，散列函数H（k）=kmod11。表中已有15、38、61、84四个元素，如果用线性探侧法处理冲突，则元素49的存储地址是（）。A、8B、3C、5D、916.数据结构里，以下字符串处理函数中，返回值不是char的是（）。A、strcatB、strcmpC、strcpyD、strlen17.序列3，1，7，18，6，9，13，12经一趟归并排序的结果为（）。18.将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（）。A、98B、99C、50D、4819.已知一个无向图的邻接表如图所示，要求：画出该无向图20.已知哈希表地址空间为A[0..8]，哈希函数为H（k）=k mod 7，采用线性探测再散列处理冲突。若依次将数据序列：76，45，88，21，94，77，17存入该散列表中则元素17存储的下标为（）。A、0B、1C、2D、3E、4F、5G、6H、721.以下程序是前序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。 22.设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（） A、AB、BC、CD、D23.树的后跟遍历24.对一组记录（5，8，9，2，12，7，56，44，39）进行直接插入排序（由小到大排序），当把第6个记录7插入有序表，为寻找插入位置需比较（）次。25.从有序表(14，20，33，45，54，72，87，96)中，分别用二分查找法查找45和54元素时，其查找长度分别为（）和（）第2卷一.参考题库(共25题)1.假定对长度n=50的有序表进行二分查找，则对应的判定树高度为（），判定树中前5层的结点数为（），最后一层的结点数为（）。2.对于一个栈，给出输入项A，B，C。如果输入项顺序为A，B，C所组成，则全部可能的输出项有（）种，不可能的输出项为（）。3.数据结构里，线性结构有：顺序表、链表、栈、队列。4.在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为（）。A、 nB、 2nC、 eD、 2e5.已知数据序列为（12，5，9，20，6，31，24），对该数据序列进行排序，写出插入排序、起泡排序、快速排序、简单选择排序、堆排序以及二路归并排序每趟的结果。6.表达式a*（b+c）-d的后缀表达式是（）。A、abcd+-B、abc+*d-C、abc*+d-D、-+*abcd7.在线性表的下列存储结构中，读取元素花费的时间最少的是（）。A、单链表B、双链表C、循环链表D、顺序表8.顺序表插入、删除分别需要移动（）个元素。A、n-iB、n-i+1C、n-1D、n-29.下面程序段中带下划线的语句的执行次数的数量级是（） 10.假定一个顺序表的长度为40，并假定查找每个元素的概率都相同，则在查找成功情况下的平均查找长度（），在查找不成功情况下的平均查找长度（）。11.下列关于算法的时间复杂度陈述正确的是（）A、算法的时间复杂度是指执行算法程序所需要的时间B、算法的时间复杂度是指算法程序的长度C、算法的时间复杂度是指算法执行过程中所需要的基本运算次数D、算法的时间复杂度是指算法程序中的指令条数12.对于右图所示的树： 写出按层遍历得到的结点序列。13.在无向图G的邻接矩阵A中，若A[i，j]等于1，则A[j，i]等于（）A、i+jB、i-jC、1D、014.给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。15.单链表的主要优点是（）A、便于随机查询B、存储密度高C、逻辑上相邻的元素在物理上也是相邻的D、插入和删除比较方便16.在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系都相同。17.假设用于通信的电文由字符集{a，b，c，d，e，f，g，h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10}，试为这8个字母进行哈夫曼编码。请回答：求出此哈夫曼树的带权路径长度WPL。18.带头结点的单链表head为空的判定条件是（）。A、head==NULLB、head->next==NULLC、head->next!=NULLD、head!=NULL19.已知一棵度为m的树中有：n1个度为1的结点，n2个度为2的结点，……，nm个度为m的结点，问该树中共有多少个叶子结点？20.哈夫曼树是指（）的二叉树。21.在表结构中最常用的是线性表，栈和队列不太常用。22.树状结构中数据元素的位置之间存在（）的关系。A、每一个元素都有一个直接前驱和一个直接后继B、一对一C、多对多D、一对多23.设二叉排序树中有n个结点，则在二叉排序树的平均查找长度为（） A、AB、BC、CD、D24.已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC（A[0][0]），则A[i][j]的地址是（）。25.从存储结构上可以把数据结构分为（）两大类。A、动态结构、静态结构B、顺序结构、链式结构C、线性结构、非线性结构D、初等结构、构造型结构第3卷一.参考题库(共25题)1.数据结构里，空格串与空串是一样的概念。2.下面哪一方法可以判断出一个有向图是否有环（回路）（）。A、求节点的度B、拓扑排序C、求最短路径D、求关键路径3.数据结构里，结构体数组，即定义数组的每个元素都是一个结构体类型的。4.在双向链表中，每个结点含有两个指针域，一个指向（）结点，另一个指向（）结点。5.数组A[1‥40，1‥30]采用三元组表示，设数组元素与下标均为整型，则在非零元素个数小于（）时，才能节省存储空间。A、1200B、401C、399D、4006.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度（）。A、O（log2n）B、O（1）C、O（n）D、O（n2）7.已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为da1，则第I个结点的地址为（）。A、da1+（I-1）*mB、da1+I*mC、da1-I*mD、da1+（I+1）*m8.（1） 设计二次多项式ax2+bx+c的一种抽象数据类型，其数据部分为多项式的三个系数项a、b、c；操作部分包括：初始化数据成员a、b、c，实现两个多项式相加，给定x求多项式的值，求方程ax2 +bx+c=0的两个实根，按照ax**2+bx+c的格式输出二次多项式。    （2） 假定数据成员a、b、c定义如下：        请写出上述各操作的具体实现。9.有一个100×90的稀疏矩阵，非0元素有10，设每个整型数占2个字节，则用三元组表示该矩阵时，所需的字节数是（）。A、20B、66C、18000D、3310.画出下图所示有向图的所有强连通分量。 11.函数重载要求（）、（）或（）有所不同。12.设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为（）在链式存储结构上实现顺序查找的平均时间复杂度为（）13.证明任何一棵满二叉树T中的分支数B满足B=2(N0-1)（其中N0为叶子结点数）。14.对于线性表（18，25，63，50，42，32，90）进行散列存储时，若选用H（K）=K%9作为散列函数，则散列地址为0的元素有（）个，散列地址为5的元素有（）个。15.数据结构里，二叉树中的结点都是度为2的结点。16.下列关于图遍历的说法不正确的是（）。A、连通图的深度优先搜索是一个递归过程B、图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C、非连通图不能用深度优先搜索法D、图的遍历要求每一顶点仅被访问一次17.在一个单链表中，若删除p所指向结点的后续结点，则执行（）。A、p->next=p->next->next；B、p=p->next；p->next=p->next->next；C、p=p->next；D、p=p->next->next；18.假定一个待散列存储的线性表为（32，75，29，63，48，94，25，46，18，70），散列地址空间为HT[11]，若采用除留余数法构造散列函数和链接法处理冲突，试求出每一元素的散列地址，画出最后得到的散列表，求出平均查找长度。19.在一个无向图中，若两顶点之间的路径长度为k，则该路径上的顶点数为（）。A、 kB、 k+1C、 k+2D、 2k20.已知一个无向图的邻接表如图所示，要求：根据邻接表，分别写出用DFS（深度优先搜索）和BFS（广度优先搜索）算法从顶点V0开始遍历该图后所得到的遍历序列。21.有向树22.假设有60行70列的二维数组a[1…60，1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32，58]的存储地址为。（无第0行第0列元素）（）A、16902B、16904C、14454D、答案A，B，C均不对23.顺序栈存储空间的实现使用（）。A、链表B、数组C、循环链表D、变量24.下述（）是顺序存储结构的优点？A、存储密度大B、插入运算方便C、删除运算方便D、可方便地用于各种逻辑结构的存储表示25.两个非递增有序的顺序表可以（）成一个非递增有序的顺序表。A、合并B、插入C、删除D、修改第1卷参考答案一.参考题库1.参考答案:2i；2i+1；i/2（或i/2）2.参考答案:错误3.参考答案:先在链表中进行遍历，在遍历过程中查找值等于x的结点，然后由此结点的最左孩子域firstchild找到值为x结点的第一个孩子，再沿右兄弟域rightsib找到值为x结点的第i个孩子并返回指向这个孩子的指针。 树的孩子兄弟表示法中的结点结构定义如下： 具体算法如下： 4.参考答案:错误5.参考答案:A6.参考答案:A7.参考答案:C8.参考答案:栈顶栈底9.参考答案:错误10.参考答案:如果R是对集合M自身的笛卡尔积所取的一个子集，那么我们就说“R是集合M上的一个关系”。对实际问题而言，它表示的是集合M中元素的某种相关性。例如，对于参加一个羽毛球比赛的运动员集合，可以用一个二元关系表示出各场比赛的胜负关系。对于一组课程的集合，可以用一个二元关系表示出各门课程之间的先修和后续关系等等。11.参考答案:A12.参考答案:613.参考答案:D14.参考答案:从树根开始定义，根结点为第1层，它的子结点为第2层，以此类推。15.参考答案:A16.参考答案:B,D17.参考答案:1，3，7，18，6，9，12，1318.参考答案:A19.参考答案:20.参考答案:F21.参考答案:22.参考答案:C23.参考答案:若树非空，则按从左到右的顺序遍历根结点的每一棵子树，之后再访问根结点。其访问顺序与其对应的二叉树的中序遍历相同。24.参考答案:425.参考答案:1；3第2卷参考答案一.参考题库1.参考答案:6；31；192.参考答案:5；CAB3.参考答案:正确4.参考答案:A5.参考答案:用上述排序方法的每趟结果如下： 6.参考答案:B7.参考答案:D8.参考答案:A,B9.参考答案:log2n10.参考答案:20.5；4111.参考答案:C12.参考答案:abcdefghijklm13.参考答案:C14.参考答案:正确15.参考答案:D16.参考答案:正确17.参考答案:18.参考答案:B19.参考答案:设该树的总结点数为n， 则n=n0+n1+n2+……+nm 又：n=分枝数+1=0×n0+1×n1+2×n2+……+m×nm+1由上述两式可得： N.0=n2+2n3+……+（m-1）nm+120.参考答案:带权路径长度最小21.参考答案:错误22.参考答案:D23.参考答案:B24.参考答案:Loc(A[0][0])+(i*N+j)*k25.参考答案:C第3卷参考答案一.参考题库1.参考答案:错误2.参考答案:B3.参考答案:正确4.参考答案:前驱；后继5.参考答案:D6.参考答案:C