河北东方学院2021 -2022 学年第一学期期末《数据结构》补考试卷

河北东方学院2021—2022学年第一学期期末《数据结构》补考试卷一、选择题（共15小题，每小题2分，共30分）O(n^2)，表明该算法的（）[单选题]*n^2n^2n^2成正比(正确答案)n^2成正比p结点（非尾结点）之后的一个结点的操作是（）[选题]*A.p->next=pA.p->next=pB.p->next->next=p->nextC.p->next->next=pD.p->next=p->next->next(正确答案)计的（）[]*A.A.正确性B.可读性C.可使用性D.健壮性(正确答案)在下列排序方法中，关键字比较的次数与记录的初始排列次序无关的是（）。[单选题]*A.A.希尔排序B.冒泡排序C.直接插入排序D.简单选择排序(正确答案)33210的结点数为（）[]*A.4A.4B.5C.6(正确答案D.7A．6B.15C.16(正确答案D.21G(V,E)17G的边数最少是（A．6B.15C.16(正确答案D.21在以下排序方法中，（）[单选题]*简单选择排序简单选择排序折半插入排序(正确答案C.希尔排序快速排序1001个结点，其叶子结点的个数是（）[]*A.250A.250B.501(正确答案C.254D.505StackEmpty(s)的值为（）。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);Pop(s,y)[单选题]*A.aA.aB.bC.1(正确答案D.03B-2047个关键字，则树的最大高度是（）[单选题]*A.11A.11B.12(正确答案C.13D.1411R[1…13]={1,3,9,12,32,41,45,62,75,77,82,510折半查找法查找值为82的结点时，经过（）次比较后查找成功。[单选题]*A.1A.1B.2C.4(正确答案D.813个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有（）[选题]*A.13B.12C.26A.13B.12C.26D.25(正确答案)操作正确的是（）[单选题]*

储，初始栈顶指针top为n，则以下元素x进栈的A.top++;data[top]=x;B.data[top]=x;top++;C.top--;data[top]=x;A.top++;data[top]=x;B.data[top]=x;top++;C.top--;data[top]=x;D.data[top]=x;top--;(正确答案)L中，至少有一个结点的条件是（）[单选题]*A.L->next!=NULLA.L->next!=NULLB.L->next!=L(正确答案)C.p==NULLD.p->next==L算法的空间复杂度是指（）[单选题]*A.A.算法中输入数据所占用的存储空间的大小B.算法本身所占用的存储空间的大小C.算法中所占用的所有存储空间的大小D.算法中需要的辅助变量所占用存储空间的大小(正确答案)二、填空题（共10小题，每小题1分，共10分）数据的基本单位 ，最小单位 。[填空题]*空1答案：数据元素空2答案：数据项逻辑结构的类型有集合、 、树形结构、 。[填空题]*对二叉排序树进行 遍历，可以得到关键字从小到大排列的结点序列。[填空题]* (答案：中序)4.对一组数据（4,48,96,23,12,60,45,73）采用直接插入排序算法进行递增排序，当把60插入到有序表中时，为寻找插入位置需比较 次。[填空题]* (答案：2)用一个大小为8的数组来实现环形队列，队头指针front指向队头元素的前一位置，队尾指针rear指向队尾元素位置。当前front和rear的值分别是0和5，在进队3个元素，又出队3个元素，front和rear的值分别是 、 [填空题*空1答案：3空2答案：0对于n个顶点的连通图来说，它的生成树一定有 条边。[填空]* (答案：n-1)对矩阵的压缩存储是为了 。[填空题]* (答案：节省存储空间)用邻接矩阵法存储图，占用的存储空间数只与图中 有关，而与边数关。[填空题]* (答案：结点个数)通过对堆栈S操作：Push(S,1),Push(S,2),Pop(S),Push(S,3),Pop(S),Pop(S)输出的序列为： 。[填空题]* (答案：231)10.广义表（（(a,b,(）,c）,d),e,((f),g))的长度是 ，深度是4。[填空题]* (答案：3)三、简答题（共6小题，每小题5分，共30分）voidfun(intn){inti,x=0;for(i=1;i<n;i++){for(j=i+1,j<=n;j++)x++;}}[填空题]*对于如图所示的二叉树转换成树。[填空题]*已知先序序列为ABCEGDFH，中序序列为CBGEAFHD。构造 对应的二树。[填空题]*G，试回答以下问题。给 从顶点V0 发的一个深度优先遍历序列和一个广度优先遍历序列。G的一个拓扑序列。[填空题]*G0始，画出其构成过程。[填空题]*6.已知数据元素序列（35，66，2，15，6，81，6*，9）进行调整为大根堆。[填空题]*四、编程题（共2小题，每小题15分，共30分）nLO(n)O(1)x[填空题]*答案解析：1．voiddelnode1(SqList*&L，ElemTypex){intk=0，i;（1分）for(i=0;i<L->length;i++)（4分）if(L->data[i]!=x){L->data[k]=L->data[i];k++;（13分）}L->length=k;（15分）}[填空题]*答案解析：2．voidconversion(intn,intd){SqStackS;（1