《2022年月数据结构试题及答案 .pdf》由会员分享，可在线阅读，更多相关《2022年月数据结构试题及答案 .pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 / 6 2001 年 10 月数据结构试卷及答案第一部分选择题(30 分 一、单项选择题本大题共15 小题，每小题2 分，共30 分）在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。1算法指的是 ） A计算机程序 B 解决问题的计算方法 C排序算法 D 解决问题的有限运算序列2线性表采用链式存储时，结点的存储地址） A必须是不连续的 B连续与否均可 C必须是连续的 D和头结点的存储地址相连续3将长度为n 的单链表链接在长度为m 的单链表之后的算法的时间复杂度为） AO1） B On） COm） DOm+n）4由两个栈共享一个向量空间的好处是：）
2、A减少存取时间，降低下溢发生的机率 B节省存储空间，降低上溢发生的机率 C减少存取时间，降低上溢发生的机率 D节省存储空间，降低下溢发生的机率5设数组datam 作为循环队列SQ 的存储空间，front 为队头指针，rear 为队尾指针，则执行出队操作后其头指针front 值为 %(m-1 Cfront=(front-1%m D front=(front+1%m 6如下陈述中正确的是） A串是一种特殊的线性表 B 串的长度必须大于零 C串中元素只能是字母 D 空串就是空白串7若目标串的长度为n，模式串的长度为n/3 ，则执行模式匹配算法时，在最坏情况下的时间复杂度是 ） AO） BOn） C
3、On2） D On3）8一个非空广义表的表头） A不可能是子表 B 只能是子表 C只能是原子 D 可以是子表或原子9假设以带行表的三元组表表示稀疏矩阵，则和下列行表0 2 3 3 5 对应的稀疏矩阵是 A4 B 5 C 6 D 7 11在含 n 个顶点和e 条边的无向图的邻接矩阵中,零元素的个数为( Ae B 2e C n2e Dn22e 12假设一个有n 个顶点和 e 条弧的有向图用邻接表表示,则删除与某个顶点vi 相关的所有弧的时间复杂度是( 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 6 页2 / 6 AO(n B O(e C
4、 O(n+e DO(n*e 13用某种排序方法对关键字序列25，84，21， 47，15，27，68，35，20）进行排序时，序列的变化情况如下： 20，15，21，25， 47，27，68， 35，84 15，20，21，25， 35，27，47， 68，84 15，20，21，25， 27，35，47， 68，84 则所采用的排序方法是） A选择排序 B希尔排序 C 归并排序 D快速排序14适于对动态查找表进行高效率查找的组织结构是）A有序表 B 分块有序表 C 三叉排序树 D线性链表15不定长文件是指）A文件的长度不固定 B 记录的长度不固定C字段的长度不固定 D 关键字项的长度不固定第
5、二部分非选择题共 70 分）二、填空题 本大题共10 小题，每小题2 分，若有两个空格，每个空格1 分，共20 分）不写解答过程，将正确的答案写在每小题的空格内。错填或不填均无分。16数据的逻辑结构是从逻辑关系上描述数据，它与数据的无关，是独立于计算机的。17在一个带头结点的单循环链表中，p 指向尾结点的直接前驱，则指向头结点的指针head 可用 p 表示为 head= 。18栈顶的位置是随着操作而变化的。19在串 S=“structure ”中，以t 为首字符的子串有个。20假设一个9 阶的上三角矩阵A 按列优先顺序压缩存储在一维数组B 中，其中B�。存储矩阵中第1 个元素 a1,1,则
6、 B中存放的元素是。21已知一棵完全二叉树中共有768 结点，则该树中共有个叶子结点。22已知一个图的广度优先生成树如右图所示，则与此相应的广度优先遍历序列为。23在单链表上难以实现的排序方法有和。24在有序表 12，24，36，48，60，72，84）中二分查找关键字72 时所需进行的关键字比较次数为。25多重表文件和倒排文件都归属于文件。三、解答题 本大题共 4 小题，每小题5 分，共 20 分）26画出下列广义表的共享结构图形表示 P=）,(x,y,x,(z）27请画出与下列二叉树对应的森林。28已知一个无向图的顶点集为a, b, c, d, e ,其邻接矩阵如下所示a b c d e
7、(1画出该图的图形；=key%13, 处理冲突的方法为双重散列法，探查序列为： hi=(h(key+ *h1(key%m =0,1,， m1 其中h1(key=key%11+1 回答下列问题：1）对表中关键字35，20，33 和 48 进行查找时，所需进行的比较次数各为多少？2）该散列表在等概率查找时查找成功的平均查找长度为多少？四、算法阅读题= 请在空白处填入适当的内容。intcomstr(LinkString s1,LinkString s2 /s1 和 s2 为两个链串的头指针while(s1&s2 if(s1datedatereturn 1； if(s1dates2datereturn
8、1 ； if( return1； if( return1 ； 31阅读下面的算法LinkListmynote(LinkList L /L 是不带头结点的单链表的头指针if(L&L-next q=L ；L=L next；p=L； S1 ： while(pnext p=pnext； S2 ： pnext=q；qnext=NULL； return L； 请回答下列问题：1）说明语句S1的功能；2）说明语句组S2的功能；精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 6 页4 / 6 3）设链表表示的线性表为a1,a2, ,an）,写出算法执行
9、后的返回值所表示的线性表。32假设两个队列共享一个循环向量空间 /若第 i 个队列不满，则元素x 入队列，并返回1；否则返回0 if(i1return 0 ； if(Q reari=Q front return0 ； Q data =x； Q reari= 。 return1； 33已知二叉树的存储结构为二叉链表，阅读下面算法。typedefstruct node DateType data；Struct node * next ； ListNode；typedefListNode * LinkList ；LinkListLeafhead=NULL； Void Inorder (BinTree
10、 T LinkList s；If(T Inorder(T lchild； If (!T lchild&(!T rchild s=(ListNode*malloc(sizeof(ListNode； s data=Tdata； s next=Leafhead；Leafhead=s； Inorder(T rchild； 对于如下所示的二叉树精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 6 页5 / 6 1）画出执行上述算法后所建立的结构；2）说明该算法的功能。五、算法设计题 int arrange(int a&# 。,int 1,int h
11、,int x /1 和 h 分别为数据区的下界和上界inti,j,t ；i=1；j=h；while(i while(i=xj- ； while(i=xi+ ；if(i t=aj；aj=ai ；ai=t ； if(ai return i ； else return i 1； 1）写出该函数的功能；2）写一个调用上述函数实现下列功能的算法：对一整型数组bn 中的元素进行重新排列，将所有负数均调整到数组的低下标端，将所有正数均调整到数组的高下标端，若有零值，则置于两者之间，并返回数组中零元素的个数。全国 2001 年 10 月高等教育自学考试数据结构试卷参考答案课程代码： 02331 一、单项选择题
12、本大题共15 小题，每小题2 分，共 30 分） 1D ，10111213 14 15二、填空题 本大题共 10 小题，每小题2 分，共 20 分）16存储 nextnext 18进栈和退栈1912 20a4,8 21384 22abefcdg 23快速排序、堆排序、希尔排序24 25.多关键字三、解答题 本大题共 4 小题，每小题5 分，共 20 分）26图 1 图 2 2728该图的图形为：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 6 页6 / 6 深度优先遍历序列为：abdce 广度优先遍历序列为：abedc 29）对关键字
13、35、20、33 和 48 进行查找的比较次数为、；）平均查找长度四、算法阅读题next s2=s2next s2(或 s2!=NULL或 s2&!s1 s1(或 s1!=NULL或 s1&!s2 return 0 31.1）查询链表的尾结点2）将第一个结点链接到链表的尾部，作为新的尾结点3）返回的线性表为%2(或 1i Qreari (Qreari%Maxsize 33.(1Leafhead F H G D 2）中序遍历二叉树，按遍历序列中叶子结点数据域的值构建一个以Leafhead 为头指针的逆序单链表 或按二叉树中叶子结点数据自右至左链接成一个链表）。五、算法设计题本题共 10 分） 341）该函数的功能是：调整整数数组a&#。中的元素并返回分界值i，使所有 x 的元素均落在a1.i上，使所有x 的元素均落在ai1.h上。 或 int f(int b&# 。,int n intp,q ；intp,q ； p=arrange(b,0,n1,0； p=arrange(b,0,n1,1； q= arrange(b,p+1,n1,1； q= arrange(b,0,p,0 ； return q p； return pq； 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 6 页