自考02331数据结构（12-19）真题试卷

课程代码：02331一、单项选择题（本大题共15小题，每小题2份，共30分）1．从逻辑上可以把数据结构分为两大类。（B）A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构2．下面关于线性表的叙述中，错误的是（B）A．线性表采用顺序存储，必须占用一片连续的存储单元B．线性表采用顺序存储，便于进行插入和删除操作C.线性表采用链接存储，不必占用一片连续的存储单元D．线性表采用链接存储，便于插入和删除操作3．一个栈的输入序列为1，2，3…，n，若输出序列的第一个元素是n，输出第i(1≤i≤n)个元素是（B）A．不确定B．n-i+lC．ID．n-i4．串的长度是指（B）A．串中所含不同字母的个数B．串中所含字符的个数C.串中所含不同字符的个数D．串中所含非空格字符的个数5．假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=。（B）A．808B．818C．1010D．10206．有n个叶子的哈夫曼树的结点总数为（D）A．不确定B．2nC．2n+lD．2n-17．要连通具有n个顶点的有向图，至少需要条边。（B）A．n-1B．nC．n+lD．2n8．具有12个关键字的有序表，折半查找的平均查找长度是（A）A．3．1B．4C．2．5D．59．下列排序算法中，其中是稳定的。（B）A．堆排序，冒泡排序B．快速排序，堆排序C．直接选择排序，归并排序D．归并排序，冒泡排序10．栈的插入和删除操作在进行。（A）A．栈顶B．栈底C．任意位置D．指定位置11．图中有关路径的定义是（A）A．由顶点和相邻顶点序偶构成的边所形成的序列．B．由不同顶点所形成的序列C．由不同边所形成的序列D．上述定义都不是12．若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（C）A．(n-1)／2B．n／2C．(n+1)／2D．n13．已知一算术表达式的中缀形式为A+B*C-D／E，后缀形式为ABC*+DE／-，其前缀形式为（D）A．-A+B*C／DEB．-A+B*CD／EC．-+*ABC／DED．-+A*BC／DE14．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B）A．9B．11C．15D．不确定15．ISAM文件和VASM文件属于（B）A.索引非顺序文件B．索引顺序文件C顺序文件D．散列文件二、填空题(本大题共10tj、题，每小题2分，共20分)16．设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC,则其前序遍历序列为CADB。17．数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度。18．链接存储的特点是利用指针来表示数据元素之间的逻辑关系。19．设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为O（m+n）。20．所谓稀疏矩阵指的是非零元很少（t<<m*n）。21．在完全二叉树中，编号为i和j的两个结点处于同一层的条件是[log2i]=[log2i]。22．在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要N条弧。23．平衡二叉树的定义是二叉树中任意结点左子树高度与右子树高度差的绝对值小于等于1。24．堆排序的算法时间复杂度为O（nog2n）。25．高度为8的完全二叉树至少有64个叶子结点。三、解答题(本大题共4小题，每小题5分，共20分)26．一个线性表为B：(12，23，45，57，20，03，78，31，15，36)，设散列表为HT[0..12]，散列函数为H(key)=key％13并用线性探查法解决冲突。请画出散列表，并计算等概率情况下查找成功的平均查找长度。27．设给定一个权值集合耻气3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL。WPL=7828．已知一个无向图如下图所示，要求用Kruskal算法生成最小树(假设以①为起点，要求画出构造过程)。29．设待排序的记录共7个，排序码分别为8，3，2，5，9，1，6。用直接插入排序。试以排序码序列的变化描述形式说明排序全过程(动态过程)，要求按递减的顺序排序。第一趟（3）[8,3]，2，5，9，1，6第二趟（2）[8，3，2]，5，9，1，6第三趟（5）[8，5，3，2]，9，1，6第四趟（9）[9，8，5，3，2]，1，6第五趟（1）[9，8，5，3，2，1]，6第六趟（6）[9，8，6，5，3，2，1]四、算法阅读题(本大题共2小题，每小题10分，共20分)30．对单链表中元素按插入方渊晾的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处，完成其功能。Typedefstructnode{Intdata;structnode*next;}linknode,*link;VoidInsertsort(linkL){Linkp,q,r,u;P=L->next;(1)While((2)){r=L;q=L->next;while((3)&&q->data<=p->data){r=q;q=q->next;}u=p->next;(4);(5);p=u;}}（1）l-.next=null(2)p!=null(3)q!=null(4)p->next=r->next(5)r->next=p31．下列算法实现求采用顺序结构存储的串s和串t的一个最长公共子串，请补充完整。Voidmaxcomstr(orderstring*s,*t;intindes,length){IntI,j,k,length1,con;Index=0;length=0;i=1;While(i<=s.len){J=1;While(j<=t.len){K=1;Length1=1:Con=1;While(con)If(1){length1=length1+1;k=k+1;}else(2);if(length1>length){index=I;lenth=length1;}(3);}else(4);}(5);}}(1)i+k<=s.len&&j+k<=t.len&&s[i+k]==t[j+k](2)con=0(3)j+=k(4)j++(5)i++五、算法设计题（本大题10分）32.设二维数组a[1..m，1..n]含有m*n个整数。（1）写出算法（pascal过程会c函数）：判断a中算有元素是否互不相同？输出相关信息：如果全不相同输出yes，否则输出no。（2）试分析算法的时间复杂度。二维数组中的每一个元素同其它元素都比较一次，数组中共m*n个元素，第1个元素同其它m,n-1个元素比较，第2个元素同其它m,n-2个元素比较，……，第m*n-1个元素同最后一个元素(m*n)比较一次，所以在元素互不相等时总的比较次数为(m*n-1)+(m*n-2)+....+2+1=(m*n)(m*n-1)／2。在有相同元素时，可能第一次比较就相同，也可能最后一次比较时相同，设在(m*n-1)个位置上均可能相同，这时的平均比较次数约为(m*n)(m*n—1)／4，总的时间复杂度是0(n4)。

课程代码：02331一、单项选择题（本大题共15小题，每小题2份，共30分）1．下列数据中，属于非线性数据结构的是（C）A．栈B．队列C．完全二叉树D．堆2．下面关于算法说法正确的是（D）A．算法最终必须由计算机程序实现B．为解决某问题的算法同为该问题编写的程序含义是相同的C．算法的可行性是指指令不能有二义性D．以上几个都是错误的3．下述哪一条是顺序存储结构的优点（A）A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示4．设A是n~n的对称矩阵，将A的对角线及对角线下方的元素按行序存放在一维数组Brn(n+1)／2]中，对上述任一元素aijti习)，在一维数组B中的位置为（B）A．i(i-1)／2+jB．i(i十1)／2+jC．j(j-1)／2+i-1D．j(j+1)／2+i-15．下述编码中不是前缀码的是(B)A．(00，01，10，11)B．(0，l，00，11)C．(0，10，110，111)D．(1，01，000，001)6．树的后序遍历序列等同于该树对应的二叉树的(B)A．先序序列B．中序序列C.后序序列D．以上均不是7．在有向图G的拓扑序列中，若顶点Ⅵ在顶点Ⅵ之前，则下列情形不可能出现的是(D)A．G中有弧<Vi，vi>B．G中有一条从Ⅵ到Ⅵ的路径C．G中没有弧<Vi，Ⅵ>D．G中有一条从邯到Ⅵ的路径8．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是(C)A．快速排序B．堆排序C．归并排序D．直接插入排序9．下面关于线性表的叙述中，错误的是(B)A．线性表采用J顿序存储，必须占用一片连续的存储单元B．线性表采用顺序存储，便于进行插入和删除操作C．线性表采用链式存储，刁；必占用一片连续的存储单元D．线性表采用链式存储，便于插入和删除操作10．n个结点的完全有向图含有边的数目为(D)A．n×nB．n×(n+1)C．n／2D．n×(n-1)11．若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度(ASL)为(C)A．(n-1)／2B．n/2C．(n+1)／2D．n12．已知有向图如下所示，其中顶点A到顶点C的最短路径长度是(D)A.43B.40C.45D.3313．下面说法不正确的是(A)A．广义表的表头总是一个广义表B．广义表的表尾总是一个广义表C．广义表难以用顺序存储结构D．广义表可以是一个多层次的结构14．在含有n个关键字的小根堆(堆顶元素最小)中，关键字最大的记录有可能存储在以下哪个位置上(D)A，『n/2』B．『n/2』-1C．1D．『n/2』+215．下面关于B和B+树的叙述中，不正确的是(C)A．B树和B+树都是平衡的多叉树B。B树和B+树都可用于文件的索引结构C．B树和B+树都能有效地支持顺序检索D．B树和B+树都能有效地支持随机检索二、填空题(本大题共10小题，每小题2分，共20分)16．数据结构一般包括逻辑结构、存储结构和数据验算三个方面的内容。17．线性表L=(a1，a2，…,an)用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是（n-1）/2。18．带头结点的双循环链表L为空表的条件是L->next==L&&L->prior==L。19.栈是限定仅在表尾进行插入或删除操作的线性表。20．设某广义表H=(A，（a，b，c))，运用head函数和tail函数求出广义表H中某元素b的运算式为head（tail（head（tail（H））））。21.深度为k的完全二叉树至少有2k-1个结点。22．求图的最小生成树有两种算法，克努斯卡尔（Kruskal）算法算法适合于求稀疏图的最小生成树。23．在各种查找方法中，平均查找长度与结点个数n无关的查找方法是散列查找。24．利用树的孩子兄弟表示法存储，可以将一棵树转换为二叉树。25．下面程序段的时间复杂度是O（1）。三、解答题（本大题共3小题，每小题5分，共15分）26.对于后序线索二叉树，怎样查找任意结点的直接后继？对于中序线索二叉树，怎样查找任意结点的直接前驱？后序线索树中结点的后继(根结点无后继)，要么是其右线索(当结点的rtag=l时)(1′)，要么是其双亲结点右子树中最左下的叶子结点(门。对中序线索二叉树某结点，若其左标记等于1，则左子女为线索，指向直接前驱C仇否则，其前驱是其左子树上按中序遍历的最后一个结点(1′)。27.已知A为稀疏矩阵，试从空间角度，比较采用两种不同的存储结构（二维数组和三元组表）完成求运算的优缺点。稀疏矩阵A采用二维数组存储时，需要n*n个存储单元，(门完成求∑aii(1<=i<=n)时，由于a[i][i]随机存取，速度快(1′)但采用三元组表时，若非零元素个数为t，需3(t+1)”个存储单元(第一个分量中存稀疏矩阵A的行数，列数和非零元素个数，以后t个分量存各非零元素的行值、列值、元素值)，比二维数组节省存储单元(1′);但在求∑aii(1<=i<=n)时，要扫描整个三元组表，以便找到行列值相等的非零元素求和，其时间性能比采用二维数组时差(2′)。28．下面的邻接表表示一个给定的无向图G(1)给出从顶点v1开始，对图G用深度优先搜索法进行遍历时的顶点序列；V1V2V3V4V5V6(2)给出从顶点vl开始，对图G用广度优先搜索法进行遍历时的顶点序列。V1V2V3V4V5V6四、算法阅读题(本大题共3小题，每小题5分，共15分)29．试将下列递归过程改写为非递归过程。参考算法：30．下面是用c语言编写的对不带头结点的单链表进行就地逆置的算法，该算法用L返回逆置后的链表的头指针。试在空缺处填入适当的语句。31．已知N元整型数组a存放N个学生的成绩，已按由大到小排序，以下算法是用二分查找方法统计成绩大于或等于X分的学生人数，请填空使之完善。#defineN/*学生人数*／五、算法设计题(本大题共2小题，每小题10分，共20分)32．已知顺序表R和增量序列d10-L1]，编写算法实现希尔排序，并用希尔排序对数组{503，087，512，061，908，170，897，275，653，426}进行排序，给出的步长(也称增量序列)依次是5，3，1，写出排序的过程。33．请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下：PUSH(ST，X)：元素x入ST栈；POP(ST，X)：ST栈顶元素出栈，赋给变量x；Sempty(ST)：判ST栈是否为空。那么如何利用栈的运算来实现该队列的三个运算：①enqueue：插入一个元素入队列；②dequeue：删除一个元素出队列；⑧queueempty：判队列为空。

2015年4月高等教育自学考试《数据结构》试题课程代码：02331一、单项选择题1．以下各阶时间复杂度中，性能最优的是（A）A．B．C．D．2．头指针head指向带头结点的单循环链表。链表为空时下列选项为真的是（D）A．head!=NullB.head==NullC．head->next=NullD．head->next=head3．设栈的进栈序列为a,b,c,d,e，经过合理的出入栈操作后，不能得到的出栈序列是（A）A．d,c,e,a,bB．d,e,c,b,aC．a,b,c,d,eD．e,d,c,b,a4．使用大小为6的数组实现循环队列，若当前rear=0，front=3。当从队列中出队一个元素，再入队两个元素后，rear和front的值分别是（C）A．1和5B．4和2C．2和4D．5和15．二维数组a[10][20]按行优先顺序存放在连续的存储空间中，元素a[0][0]的存储地址为200，若每个元素占1个存储空间，则元素a[6][2]的存储地址是（B）A．226B．322C．341D．3426．广义表A=(a,(b,c,(e,f,g,h)))的深度是（B）A．2B．3C．4D．77．以二叉链表作为二叉树的存储结构，在有n(n>0)个结点的二叉链表中，空指针域的个数是（B）A．n-1B．n+1C．2n-1D．2n+18．构造一棵含n个叶结点的哈夫曼树，树中结点总数是（C）A．n-1B．n+1C．2n-1D．2n+19．若图G的邻接表中有奇数个表结点，下列选项中，正确的是（D）A．G中必有奇数个顶点B．G中必有偶数个顶点C．G为无向图D．G为有向图10．下列关于有向无环图G的拓扑排序序列的叙述中，正确的是（C）A．存在且唯一B．存在且不唯一C．存在但可能不唯一D．无法确定是否存在11．对下图进行广度优先搜索遍历，不能得到的遍历序列是（B）A．v1v2v4v5v3B．v1v2v5v3v4C．v2v5v1v3v4D．v2v1v5v4v312.下列排序方法中，效率较高且使用辅助空间最少的方法是（C）A．冒泡排序B．快速排序C．堆排序D．归并排序13．下列排序方法中，平均比较次数最少的方法是（B）A．插入排序B．快速排序C．简单选择排序D．归并排序14．对含有16个元素的有序表进行二分查找，关键字比较次数最多是（C）A．3B．4C．5D．615．下列叙述中，不符合m阶B树定义的是（D）A．根结点可以只有一个关键字B．所有叶结点都必须在同一层上C．每个结点内最多有m棵子树D．每个结点内最多有m个关键字二、填空题16．算法必须满足可行性等五个准则，其中确定性的含义是：算法中每条指令的含义都必须明确，无二义性。17．采用大表示法时，常数阶算法的时间复杂度记为。18．一个线性表如果需要频繁地增删元素，则存储结构应该选择链式存储结构。19．队列Q中已有元素1，3，5，数据序列2，4，6，8，10依次入队，再连续执行6次出队操作，得到的出队序列是1，3，5，2，4，6。20.广义表A=(a(b,c,(e,f,g,h)))，head(tail(A))=（b,c,(e,f,g,h)）。21.一棵右子树为空的二叉树在后序线索化后，其空指针域的个数为2。22.用矩阵作为图的存储结构，该矩阵称为图的邻接矩阵。23.普里姆（Prim）算法得到的是带权连通图的最小生成树。24.希尔排序方法使用的增量序列中，最后一个增量必须是1。25.若待排序序列的关键字基本有序，采用快速排序或直接插入排序时，效率较高的是直接插入排序。三、解答题26．顺序栈的类型定义如下：typedefstruct{DataTypedata[MaxSize];inttop;}SeqStack;SeqStackS;规定栈底位置在MaxSize-1，请回答下列问题。(1)若要求栈空时条件为真，则判断栈空的条件表达式是什么?(2)若要求栈满时条件为真，则判断栈满的条件表达式是什么?(3)用语句表示将x入栈的操作。答：27.已知广义表及结点类型结构如下：ypedefenum{ATOM,LIST}NodeTag;//ATOM=O,表示原子;LIST=1,表示子表//ATOM=O,表示原子;LIST=1,表示子表typeclefstructGLNode{NodeTagtag;//区分原子结点和表结点union{DataTypedata;//存放原子结点的值OLNode*slink;//指向子表的指针};GLNode*next;//指向下一个表结点}*Glist;//广义表类型请回答下列问题。(1)若广义表A为空表，应如何表示?(2)若广义表A二(a,(b,c))，画出A的存储结构。答：28．己知散列函数为H(key)=key％11，现将关键字序列{23,27,34,56,58,10,18,120}散列到散列表HT[0…10]中，利用线性探查法解决冲突。回答下列问题。(1)画出最后的散列表；(2)求在等概率情况下查找成功时的平均查找长度。答：29．给定带权图G如题29图所示，使用迪杰斯特拉(Dijkstra)算法，求顶点v1到其他各项点的最短路径，列出每条路径上的各顶点及路径长度。答：四、算法阅读题30．设下列程序段中的数据皆为int型，请指出该程序段的功能是什么。voidf30(CirQueue*Q){intx;SeqStackS;InitStack(&S);//初始化栈Swhile(!QueueEmpty(Q)){x=DeQueue(Q);Push(&S,x);}while(!StackEmpty(&S)){x=Pop(&S);EnQueue(Q,x);｝｝答：程序段的功能是：将队列Q中的所有元素的排列次序反转。31．下列函数的功能是在带头结点的单链表head中删除所有数据域值为xr的结点，请在空白处填上适当的语句，使其完成指定功能。voidf31(LinkListhead,intx){LinkNode*p,*q,*s;p-head;q=p->next;while(q!=NULL)if(q->data==x){s=q;q=q->next;free(s);p->next=q;}else{p=q;q=q->next（或q=p->next）,｝｝32．下列函数的功能是：在带头结点的单链表上进行选择排序。请在空白处填上适当内容将函数补充完整，并说明该算法是否是稳定的。typedefstructnode{KeyTypekey;stmctnode*next;}RecType,*LinkList;voidf32(LinkListH){LinkListp,q,r=H;while(r->next!=NULL){p=r;q=p->next;'while(q->next)//查找最小值结点{if(p->next->key>q->next->key)p=q;q=q->next;｝q=p->next;//将最小值结点取下p->next=q->next;q->next=r->next;//将最小值结点插入r->next=q;r=q;}｝该算法是稳定的排序方法。33.阅读程序，并回答下列问题。typedefintKeyType;typedefstmct{KeyTypekey;InfoTypeotherinfo;}RecType;typedefRecTypeSeqList[MAXSIZE+1];intf33(SeqListR,KeyTypeK,intIow,inthigh){intmid;while(low<high){mid=(low+high)/2;if(R[mid].key>=K)returnf33(R,K,low,mid);elsereturnf33(R,K,mid+l,high);｝if(R[low].key==K)returnlow;elsereturn0;｝假设顺序表R的元素存入在下标为1~8的数组元素中，K=7，low=1，high=8。(1)R的关键字依次为{1,2,3,4,5,6,7,8}，函数f33的返回值是多少?答：函数的返回值为7(2)R的关键字依次为{7,7,7,7,7,7,7,7}，函数f33的返回值是多少?答：函数的返回值为1(3)简述函数的功能。答：函数实现二分查找，返回值为查找目标在表中第一次出现的下标位置。五、算法设计题34.存储二叉树的二叉链表定义如下：typedefstructnode{chardata;structnode*lchild,*rchild;}BinTNode;typedefBinTNode*BinTree;请编写一个后序遍历二叉树的递归程序voidPostOrder(BinTreeroot)，并输出遍历序列。其中root指向二叉树根结点。答：

2015年10月高等教育自学考试《数据结构》试题课程代码：02331一、单项选择题1．下列选项中，不属于线性结构的是A．网B．栈C.队列D．线性表2.长度为n的顺序表，删除位置i上的元素(0≤i≤n-1)，需要移动的元素个数为A.n-iB．n-i-1C．iD．i+l3．栈采用不同的存储方式时，下列关于出栈过程的叙述中，正确的是A．顺序栈需要判定栈空，链栈也需要判定B．顺序栈需要判定栈空，而链栈不需要判定C．顺序栈不需要判定栈空，而链栈需要判定D．顺序栈不需要判定栈空，链栈也不需要判定4.若一个栈以数组V[0..n-1]存储，初始栈顶指针top为n，则x入栈的正确操作是A．top=top+1；V[top]=xB．V(top)=x；top=top+1C.top=top-1；V[top]=xD．V(top)=x；top=top-15.在二维数组a[9][10]中，每个数组元素占用3个存储空间，从首地址SA开始按行优先连续存放，则元素a[8][5]的起始地址是A．SA+141B.SA+144C.SA+222D．SA+2556.广义表A=(x,((y),((a)),A))的深度是A．2B．3C．4D．7．一棵左子树为空的二叉树在前序线索化后，其空指针域个数为A.0B．1C．2D.不确定8．下列关于哈夫曼树的叙述中，错误的是A．用n个结点构造的哈夫曼树是唯一的B．哈夫曼树中只有度为0或度为2的结点C．树中两个权值最小的结点可能是兄弟结点D．同一结点集构造的二叉树中，哈夫曼树的WPL最小9．6个顶点的强连通图中，含有的边数至少是A．4B．5C．6D．710．对题10图进行深度优先搜索遍历，下列选项中，正确的遍历序列是A．v3v4v5v1v2B．v3v5v2v1v4C．v4v5v2v3v1D．v5v1v2v4v311．下列选项中，能构成题10图中一条路径的是A．v1v2v4v5v3B．v1v2v5v3v4C．v2v5v1v3v4D．v2v1v5v4v312．有向图采用邻接矩阵存储，某一行中非零元素的个数等于A．对应顶点v的度B．对应顶点v的出度C．对应顶点v的入度D．依附于对应顶点v的边数13．以下选项中，符合堆定义的是A．{102,24,55,60,89,93}B．{24,89,55,60,93,102}C．{102,93,55,60,89,24}D.{102,60,89,93,55,24}14．己知关键字序列为{66,82,25,51,98,108}，利用快速排序方法，以第一个元素为基准得到的一趟排序结果为A．{25,51,66,82,98,108}B．{25,51,66,98,82,108}C．{51,25,66,108,98,82}D．{51,25,66,82,98,108}15．下列选项中，其平均查找性能与基于二叉排序树的查找相当的是A．二分查找B．顺序查找C．分块查找D．索引顺序查找二、填空题16．线性表(a1,a2,…,an)中，除外，每个元素都有唯一的直接前趋。17．指针p指向单链表中某个结点，在p所指结点后插入指针s所指的结点，正确的操作序列是18．设Push、Pop分别表示入栈和出栈操作，x=10，y=20，z=30。依次进行下列操作：Push(y)、Push(z)、Push(z)、x=Pop()、y=Pop()，x、y的值分别是。19．广义表L=(a,(b,c,(e,f,g,h))),head(L)=。20．设树T的度为3，其中度为1、2和3的结点个数分别为3、2和1，则T中叶子结点的个数为。21．由一棵二叉树的后序遍历序列和遍历序列可以唯一确定该二叉树。22．在有n个顶点的无向图中，任一顶点的度不大于。23．借助于一个栈来实现的图的遍历算法是、。24．若有向图中存在拓扑排序序列，则该图一定不存在。25．已知关键字序列为{66,82,25,51,98,108)，一趟二路归并排序的结果为。三、解答题26．已知n阶对称矩阵A的元素为aij(0≤i，j≤n-1)，采用“按行优先”．将下三角部分的元素(含主对角线)保存在一维数组sa中，且约定元素a0,0保存在sa[0]中，元素aij(0≤i，j≤n-1)保存在sa(k)中，请给出由下标i,j计算下标k的计算公式。27．己知二叉树T如题27图所示。请问答下列问题：(1)画出该二叉树对应的森林。(2)写出对森林进行前序遍历的遍历序列。28．题28图所示为一棵含2个关键字的3阶B树T。现将关键字序列{40,60,70,20,10}依次插入到T中，画出每插入一个关键字后得到的树型。29．给定无向带权连通图G如题29图所示，从顶点v0开始，使用普里姆(Prim)算法，求G的最小生成树T。请回答下列问题。(1)画出最小生成树T。(2)计算T中各边权值之和。四、算法阅读题30．请写出下列程序段的输出结果。#defineListSize100typedefstmct{intdata[ListSize];intlength;}SeqList;voidf30(SeqList.*list){inti,j,k;for(i=0;i<=list->length-2;i++){j=i+l;while(j<=list->length-1){if(list->data[i]==-list->data[j]){for(k=j;k<list->length-1;k++list->length--;}elsej++;}}}voidmain()SeqListlist={{0,3,7,3,3,3,4,O,3,7),10};inti;t30(&list);printf(',!en=%d\n",list.length);for(i=O;i<list.length;i++)prinff("%d,",list.data[i]);prinff("\n");31．已知存储稀疏矩阵三元组表的类型定义如下：#defineMAX100typedefstmct{inti,j;//非零元素的行号、列号(下标)ihtv;}TriTupleNode;typedefstruct{TriTupleNodedata[MAX];//存储三元组的数组intm,n,t;//矩阵的行数、列数和非零元素个数}TSMatrix;//稀疏矩阵类型函数f31的功能是将a所表示的矩阵转置后保存在*b中。请在空白处填写适当内容，intf31(TSMatdxa,TSMatrix*b)//返回值:1表示出错，0表示正确{//a和*b分别是矩阵M、T的三元组表，T为稀疏矩阵M的转置.intp,q,col;b->m=a.n;b->n=a.m;b->t=a.t;if(b->t<0)return1;else{q=0;for(col=0;col<a.n;++col)for(p=0;p<(1);++p)if((2)==col){b->data[q].i=(3);b->data[q].j=(4);b->data[q].v=a.data[p].v;++q;)}return0;}(1)(2)(3)(4)32．已知二叉树的二叉链表类型定义如下：typedefstructnode{chardata;structnode*lchild,*rchild;}BinTNode;typedefBinTNode*BinTree;函数CopyBin的功能是完成二叉树Bt的复制,程序如下:BinTreeCopyBin(BinTreeBt)//函数返回值为指向复制后的二叉树根的指针{BinTreep;if(Bt==NULL)(1);else{p=(BinTNode*)malloc(sizeof(BinTNode));p->data=Bt->data;p->lchild=(2);p->rchild=(3);}}returnp;为完成指定功能，请在空白处填写适当内容，使其功能完整。33．函数f33的参数t指向题33图所示的二叉排序树的根，阅读程序，回答下列问题。typedefihtKeyType;typedefstructnode{KeyTypekey;node*lchild,*rchild;}BSTNode,*BSTree;BSTreeF33(BSTreet,KeyTypeK){BSTreep;while(t!=NULL){if(t->key==K){prinff("查找成功\n");returnt;}p=t;if(t->key>K)t=t->lchild;elset=t->rchild;}printf("查找不成功\n");t=(BSTree)malloc(sizeof(BSTNode));t->key=K;t->lchild=NULL;t->rchild=NULL;if(p->key>K)p->lchild=t;elsep->rchild=t;returnNULL;(1)若连续3次调用函数03，参数K的值依次取10、25、10，写出每次调用后函数的输出结果；(2)说明函数f33的功能。五、算法设计题34．已知顺序表SeqList定义如下：typedefstreet{KeyTypekey;InfoTypeotherinfo;}ReeType;typedefRecTypeSeqList[MAXSIZE+1];编写函数，用冒泡排序法将n个元素的待排序列R按关键字降序排序。函数原型为：iht134(SeqListR,intn).

2016年4月高等教育自学考试《数据结构》试题课程代码：02331一、单项选择题1．下列选项中，属于非线性数据结构的是A．队列B．栈C．二叉排序树D．线性表2．瑞士计算机科学家沃思教授曾指出：算法+数据结构=程序。这里的数据结构指的是A．数据的逻辑结构和存储结构B．数据的线性结构和非线性结构C．数据的紧凑结构和非紧凑结构D．数据的J顷序结构和链式结构3．线性表顺序存储时，逻辑上相邻的两个数据元素，其存储地址A．一定相邻B．一定不相邻C．不一定相邻D．可能不相邻4．数据元素1,2,3,4,5依次入栈，则不可能得到的出栈序列是A．4,5,3,2,1B．1,2,3,4,5C．4,3,5,1,2D．5,4,3,2,15．设顺序表首元素A[0]的存储地址是4000，每个数据元素占5个存储单元，则元素A[20]的起始存储地址是A．4005B．4020C．4100D．41056.广义表A=(a,(b,c,(e,f))),函数head(head(tail(A)))的运算结果是A.aB.bC.cD.e7．设高度为h的二叉树中，只有度为0和2的结点，则此类二叉树包含的结点数至少是A．2hB．2h-1C．2h+1D．h+18．一棵非空二叉树了的前序遍历和后序遍历序列正好相反，则了一定满足A．所有结点均无左孩子B．所有结点均无右孩子C．只有一个叶子结点D．是一棵满二叉树9．设图的邻接矩阵A如下所示。各顶点的度依次是A．1,2,1,2B．2,2,1,1C．3,4,2,3D．4,4,2,210．无向图G如题10图所示，从顶点a开始进行深度优先遍历，下列遍历序列中，正确的是A．a,b,e,c,d,fB．a,c,f,e,d,bC．a,c,b,e,f,dD．a,e,d,f,c,b11．设带权连通图G中含有n(n>1)个顶点，下列关于G的最小生成树T的叙述中，正确的是A．T中可能含有回路B．T中含有图G的所有边C．T是唯一的，且含有n-1条边D．T可能不唯一，但权一定相等12．若要求对序列进行稳定的排序，则在下列选项中应选择A．希尔排序B．快速排序C．直接插入排序D．直接选择排序13．下列排序算法中，空间复杂度最差的是A．归并排序B．希尔排序C．冒泡排序D．堆排序14．下列排序算法中，初始数据有序时，花费的时间反而更多的算法是A．插入排序B．冒泡排序C．快速排序D．希尔排序15．对线性表上进行二分查找时，要求上必须满足A．以顺序方式存储B．以顺序方式存储，且数据元素有序C．以链接方式存储D．以链接方式存储，且数据元素有序二、填空题16．下面程序段的时间复杂度是。i=1；while(i<n)i=i*2；17．在单链表的p结点之后插入s结点的操作是。18．只能在线性表的两端进行插入或删除操作的两种逻辑结构分别是。19．广义表A=(x,(y,z,(u,v,w)))的长度是。20．一棵树的后序遍历序列与其对应的二叉树的序遍历序列相同。21．在有向图、无向图中，其邻接矩阵一定对称的是。22．要计算图中从某一顶点出发到其余各项点的最短路径，可选用算法。23．设关键字序列为28,72,97,63,4,53,84，使用希尔排序法将其排成升序序列，若第一趟采用的间隔是3，则该趟排序的结果是。24．对具有15个关键字的关键字序列进行顺序查找时，查找成功的平均查找长度为。25．在二叉排序树的查找过程中，若当前结点的关键字值大于待查找关键字，则应在该结点的子树上继续查找。三、解答题26．设Q是有N个存储空间的循环队列，初始状态front=rear=0，约定指针rear指向的单元始终为空。定义如下：#defineN100typedefstruct{chardata[N];intfront,rear;}CQ;GQ*Q;(1)写出清空队列的语句序列；(2)写出判断队列为满的表达式；(3)给出计算队列长度L的表达式。27．已知4×5稀疏矩阵M按行优先顺序存储的三元组表如下：(1)写出矩阵M(2)给出矩阵M的转置矩阵T按行优先顺序存储的三元组表。28．给定一组权值数据{3,8,9,11,4}，回答下列问题。(1)画出基于所给数据的一棵哈夫曼树；(2)计算所得哈夫曼树的带权路径长度WPL。29.已知有向图G=(V,E),其中V={v1,v2,v3,v4,v5,v6,v7},E={<v1,v2>,<v1,v3>,<v1,v4>,<v2,v5>,<v3,v5>,<v3,v6>,<v4,v6>,<v5,v7>,<v6,v7>}。(1)画出有向图G；(2)判断图G是否存在拓扑排序序列，若不存在请说明理由：若存在请给出一个拓扑排序序列。四、算法阅读题30．阅读程序f30(intA[],intn){intm;if(n<=0)return-1;if(n==l)return0;m=f30(A,n-1);if(A[m]>A[n-1])returnm;elsereturnn-1;}已知线性表A={25,34,256,9,38,47,128,256,64}。（1）若主函数调用语句为f30（A,5），f30的返回值是多少？（2）若主函数调用语句为f30（A,9），f30的返回值是多少？（3）给出算法f30的功能。31．已知栈的基本操作定义如下，请在空白处填写适当内容，完成相应的功能。typedefstruct{//栈定义chardata[StackSize];inttop;}SeqStack;SeqStacks;voidInitStack(SeqStack*s)//栈初始化{s->top=-1;}intStackEmpty(SeqStack*s)//判栈是否为{return(1);}intStackFull(SeqStack*s)//判栈是否为满{returns->top--StackSize-1;}charpush(SeqStack*s,charc)//入栈操作{if(StackFull(s))remm'\0';//操作失败else(2)=c;returnc;//操作成功}charpop(SeqStack*s)//出栈操作{if(StackEmpty(s))return'\0';//操作失败elsereturn(3)//操作成功}32．设带头结点的单链表初始为空。将从键盘读入的每个字符作为一个结点加入该链表表尾，当读入回车符时结束并返回链表表头指针。请在空白处填写适当内容，完成其功能。typedefstructnode{chardata;structnode*next;}ListNode;typedefListNode*LinkList;LinkListf32(){LinkListhead=NULL;ListNode*p,*rear;charch;head=(ListNode*)malloc(sizeof(ListNode));rear=head;while((ch=getchar())!='\n'){(1),p->data=ch;(2);rear=p;}rear->next=NULL;return(3);33．给出二叉链表定义如下。程序f33生成原二叉树的镜像树，即将二叉树中所有结点的左、右子树互换。请在空白处填写适当内容，完成其功能。typedefcharDataType;typedefstructnode{DataTypedata;//data是数据域structnode*lchild,*rchild;//分别指向左右孩子}BinTNode;typedefBinTNode*BinTree;BinTreef33(BinTreeT){BinTreeNewT;if((1))returnNULL;(2)=(BinTree)malloc(sizeof(BinTNode));NewT->data=T->data;NewT->lchild=(3);NewT->rchild=(4);return(5);}五、算法设计题34.实现f34，对含有n个整数的数组A进行选择排序。函数原型如下。voidf34(intA[],intn)；／／对含有n个整数的数组A进行选择排序

2016年10月高等教育自学考试《数据结构》试题课程代码：02331一、单项选择题1．下列选项中，不属于线性结构特征的是A．数据元素之间存在线性关系B．结构中只有一个开始结点C．结构中只有一个终端结点D．每个结点都仅有一个直接前趋2．设n个元素的顺序表中，若将第i(1≤i<n)个元素e移动到第j(1<j≤n，i<j)个位置，不改变除e外其他元素之间的相对次序，则需移动的表中元素个数是A．j-i-1B．j-iC．j-i+1D．i-j3．若用一个大小为7的数组作为循环队列的存储结构，且当前rear和front的值分别为2和4，在此之前的操作是从队列中删除了一个元素及加入两个元素，请问这3个操作之前real'和front的值分别是A．0和1B．0和3C．3和6D．4和54．已知广义表LS=(((a))，((b,(c))，(d,(e,f)))，())，LS的长度是A．2B．3C．4D．55．一棵完全二叉树了的全部k个叶结点都在同一层中且每个分支结点都有两个孩子结点。了中包含的结点数是-A．kB．2k-1C．k2D．2k-16．如果某二叉树的前序遍历序列为abced，中序遍历序列为cebda，则该二叉树的后序遍历序列是A．cedbaB．decbaC．ecdbaD．ecbad7．一个森林有阴棵树，顶点总数为，2，则森林中含有的总边数是A．mB．n-1C．n-mD．n+m8．设图的邻接矩阵A如下所示。各顶点的度依次是A．1,2,1,2B．2,2,1,1C．3,4,2,3D．4,4,2,29．若对下面无向图进行深度优先遍历，得到的正确遍历序列是A.h,c,a,b,d,e,g,fB.e,a,f,g,b,h,c,dC.d,b,c,a,h,e,f,gD.a,b,c,d,h,e,f,g10．已知有向图G如下所示，G的拓扑序列是A.a,b,e,c,d,f,gB.a,c,b,f,d,e,gC.a,c,d,e,b,f,gD.a,c,d,f,b,e,g11．下列排序算法中，在每一趟都能选出一个元素放到其最终位置上的是A．插入排序B．希尔排序C．归并排序D．直接选择排序12．对一组数据(2,12,16,88,5,10)进行排序，若前3趟排序结果如下：第一趟：2,12,16,5,10,88第二趟：2,12,5,10,16,88第三趟：2,5,10,12,16,88则采用的排序方法是A．冒泡排序B．希尔排序C．归并排序D．基数排序13．设有序表为{9,12,21,32,41,45,52}，当二分查找值为52的结点时，元素之间的比较次数是A．1B．2C．3D．414．下列选项中，既能在顺序存储结构也能在链式存储结构上进行查找的方法是A．散列查找B．顺序查找C．二分查找D．以上选项均不能15．在一棵5阶B树中，每个非根结点中所含关键字的个数最少是A．1B．2C．3D．4二、填空题16．两个栈S1和S2共用含100个元素的数组S[0..99]，为充分利用存储空间，若S2的栈底元素保存在S[99]中，则S1的栈底元素保存在中。17．在一个单链表中，已知指针变量q所指结点不是表尾结点，若在q所指结点之后插入指针变量s所指结点，则正确的执行语句是。18．设顺序表第1个元素的存储地址是1000，每个数据元素占6个地址单元，则第11个元素的存储地址是。19．二叉树采用顺序存储方式保存，结点X保存在数组A[7]中，若X有右孩子结点Y，则Y保存在中。20．一棵二叉树中，度数为1的结点个数为n1，度数为2的结点个数为n2，则叶结点的个数为。21．已知广义表LS=((a,b)，c,d)，head(LS)是。22．在无向图G的邻接矩阵A中，若A[i,j]=1，则A[j,i]=。23．已知大根堆中的所有关键字均不相同，最大元素在堆顶，第2大元素可能存在的位置有2个，第3大元素可能存在的位置有个。24．在有n个元素组成的顺序表上进行顺序查找。若查找每个元素的概率相等，则查找成功时平均查找长度是。25．线性探查法和拉链法解决的是散列存储中的问题。三、解答题26．对题26图中所给的二叉排序树T，回答下列问题。(1)给出能生成了的2种关键字插入序列；(2)给出了的前序遍历序列。27．对题27图所示的无向带权图G，回答下列问题。(1)给出图G的邻接矩阵；(2)给出图G的一棵最小生成树。28．现有5个权值分别是20、31、16、7和15的叶结点，用它们构造一棵哈夫曼树，画出该树。29．对于给定的一组关键字序列{26,18,60,65,45,13,32}，写出使用直接选择排序方法将其排成升序序列的过程。四、算法阅读题30．设非空双向循环链表L的头指针为head，表结点类型为DLNode，定义如下。typedefhatDataType;typedefstmctdlnode{DataTypedata;//data是数据域stmctdlnode*prior,*next;//prior指向前趋结点，next指向后继结点}DLNode;typedefDLNode*DLinkList;初始时，L中所有结点的prior域均为空(NULL)，next域和data域中已经正确赋值。如题30图a所示。函数f30完成的功能是：将L中各结点的prior域正确赋值，使L成为双向循环链表。如题30图b所示。请在空白处填上适当内容将算法补充完整。voidf30(DLinkListhead){DLNode*p;p=head;while(p->next!=(1)){(2)=p;p=p->next;}(3)=p;}31．已知二叉树的二叉链表类型定义如下，阅读程序，并回答问题。typedefcharDataType;typedefstmctnode{DataTypedata;//data是数据域stmctnode*lchild,*rchild;//分别指向左、右孩子结点}BinTNode;typedefBinTNode*BinTree;voidf31(BinTreebt){if(bt!=NULL){printf("%c",bt->data);f31(bt->lchild);printf("%c",bt->data);}}若二叉树了如下所示，写出调用f31(T)的输出结果。32．阅读下列程序，写出f32的输出结果。voidf32(){SeqStack*S;charx,y;InitStack(S);x='h';y='t';Push(S,x);Push(S,'c');x=Pop(S);Push(S,x);Push(S,y);Push(S,'a');Push(S,x);while(!StackEmpty(S)){y=Pop(S);pfintf("%c",y);}pfintf("%c\n",'!');}33．阅读程序，回答下列问题。intf33(NodeTypeR[],KeyTypek,intn){inti=n-1,count=1;R[0].key=k;while(R[i].key!=k){i--;count++;}if(i==0)return-1;elsereturncount;}(1)变量count的含义是什么?(2)f33的功能是什么?五、算法计算题34．已知单链表类型定义如下：typedefstructnode{intdata;streetnode*next;}ListNode;typedefListNode*List_ptr;单链表L中结点数不少于2。设计算法判断L中存储的全部n个数据是否是斐波那契序列的前n项。如果是，则函数返回1，否则返回0。函数原型如下：intIsF(List_ptrhead)；//判定是否是斐波那契序列注：斐波那契序列的定义为：f0=0，f1=1，fn=fn-1+fn-2(n≥2)

2017年4月高等教育自学考试《数据结构》试题课程代码：02331一、单项选择题(本大题共]5d、题，每小题2分，共30分)1．下列叙述中，不正确的是A．算法解决的只能是数值计算问题B．同一问题可以有多种不同算法C．算法的每一步操作都必须明确无歧义D．算法必须在执行有限步后结束2．下列关于栈中逻辑上相邻的两个数据元素的叙述中，正确的是A．顺序存储时不一定相邻，链式存储时一定相邻B．顺序存储时不一定相邻，链式存储时也不一定相邻C．顺序存储时一定相邻，链式存储时也一定相邻D．顺序存储时一定相邻，链式存储时不一定相邻3．对带头结点的单循环链表从头结点开始遍历(head为头指针，p=head->next)。若指针p指向当前被遍历结点，则判定遍历过程结束的条件是A．p==NULLB．head==NULLC．p==headD．head!=p4．设栈的入栈序列为1,2,3,4,5，经过入、出栈操作后，，可能得到的出栈序列是A．2,3,5,1,4B．4,2,1,3,5C．3,4,1,2,5D．3,4,2,1,55．数组A[2][3]按行优先顺序存放，A的首地址为10。若A中每个元素占用一个存储单元，则元素A[1][2]的存储地址是A．10B．12C．14D．156．广义表((a，b)，(c，d))的表尾是A．bB．dC．(c，d)D．(