数据结构习题_部分答案_全真模拟.doc

云南财经大学信息学院数据结构模拟试题题库数据结构课程建设小组模拟试题部分一、单项选择题1. 若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用_（3）_存储方式最节省运算时间。（1）单链表 （2）双链表(3) 容量足够大的顺序表 （4）带头结点的双循环链表2. 若某线性表中最常用的操作是取第I 个元素的前驱元素，则采用_（3）_存储方式最节省运算时间。（1）单链表 （2）双链表(3)顺序表 （4）带头结点的双循环链表3. 将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（_A_）。 A98 B.99 C.50 D.484. 一个具有n个顶点的无向完全图的边数为（B）。An(n+1)/2 Bn(n-1)/2 C n(n-1) Dn(n+1)5. 折半查找要求查找表中各元素的关键字值必须是_A_排列。 A.递增或递减 B.递增 C.递减 D.无序6. 栈操作的原则是 B 。A. 先进先出 B.后进先出 C.只能进行插入 D. 只能进行删除7. 设一个栈的输入序列为A，B，C，D，则借助一个栈所得的输出序列不可能是_（4）_。（1）A，B，C，D （2）D，C，B，A （3）A，C，D，B （4）D，A，B，C8. 将下三角矩阵A1.10，1.10的所有非0 元素以行序为主序存放在首地址为2000的存储区中，每个元素占有4个单元，则元素A9，5的首地址为（D）A2340 B2336 C2164 D21609. 串是_（4）_。（1） 不少于一个字母的序列 （2）任意个字母的序列（3） 不少于一个字符的序列 （4）有限个字符的序列10. 链表不具有的特点是_（1）_.（1）可随机访问任一元素 （2）插入删除不需要移动元素（3）不必事先估计存储空间 （4）所需空间与线性表长度成正比11. 在有n个结点的哈夫曼树中，其结点总数为_（4）_。（1） （1） 不确定 （2）2n （3）2n+1 （4）2n-112. 任何一个无向连通图的最小生成树_（2）_。（1） 只有一棵 （2）有一棵或多棵 （3）一定有多棵 （4）可能不存在13. 将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为_（1）_。（1）98 （2）99 （3）50 （4）4814. 将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的右孩子编号为_2_。（1）98 （2）99 （3）50 （4）4815. 将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的双亲编号为_2_。（1）23 （2）24 （3）25 （4）无法确定16. 设计一个判别表达式中左右括号是否配对出现的算法，采用（B）数据结构最佳。A线性表的顺序存储结构 B栈 C队列 D线性表的链式存储结构17. 下列序列中，_（1）_是执行第一趟快速排序后得到的序列（排序的关键字类型是字符串）。（1）da,ax,eb,de,bbffha,gc (2)cd,eb,ax,daffha,gc,bb(3)gc,ax,eb,cd,bbffda,ha (4)ax,bb,cd,daffeb,gc,ha18. 用n个键值构造一棵二叉排序树，最低高度为_（4）_。（1）n/2 (2)n1/2 (3)NLOG2N (4)LOG2N+119. 折半查找要求查找表中各元素的关键字值必须是_1_排列。（1） 递增或递减 （2）递增 （3）递减 （4）无序20. 对于关键字值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从关键字值为_（3）_的结点开始。（1）100 （2）12 （3）60 （4）1521. 快速排序的记录移动次数（C）比较次数，其总执行时间为0（NLOG2N）A大于 B大于等于 C小于等于 D小于22. 3个结点可构成（D）个不同形态的二叉树。A2 B3 C4 D523. 对有n个记录的有序表采用二分查找，其平均查找长度的量级为（A）AO（LOG2N） BO（NLOG2N） CO（N） DO（N2）24. 对有n个记录的表按记录键值有序的顺序建立二叉排序树，在这种情况下，其平均查找长度的量级为（C）AO（LOG2N） BO（NLOG2N） CO（N） DO（N2）25. 设矩阵A1.8,1.8是一对称矩阵，若每个矩阵元素占3个单元，将其上三角部分按行序为主序存放在数组B中，B的首址为1000，则矩阵元素A6，7的地址为（B）A1031 B1093 C1096 D1032 26. 链表适用于顺序查找，但在链表中进行（D）操作的效率比在顺序存储结构中进行同样操作的效率高。A顺序查找 B二分法查找 C快速查找 D插入27. 散列法中的冲突指的是（C）。A两个元素具有相同的序号 B两个元素的键值不同，而其它属性相同 C不同键值的元素对应于相同的存储地址 D数据元素过多28. 如果以链表作为栈的存储结构，则退栈操作时（C）A必须判断栈是否满 B对栈不作任何判断 C必须判断栈是否空 D判断栈元素的类型 29. 设数组A0.M作为循环队列SQ的存储空间，front 为队头指针，rear为对尾指针，则执行出队操作的语句为（D）Afront=front+1 Bfront=(front+1)%m Crear=rear+1 Drear=(rear+1)%m30. 深度为6的二叉树至多有（D）个结点A64 B32 C31 D6331. 设高度为k的二叉树上只有度为0和2的结点，则此类二叉树中所含的结点数至少为（C）AK+1 B2K C2K-1 D2K+132. 堆的存储表示（A）A顺序存储 B.静态链接存储 C.动态链接存储 D.不一定 33. 若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用( A )遍历方法最合适。A前序 B中序 C后序 D按层次34. 利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，查找元素35要进行( A )元素间的比较。A4次 B5次 C. 7次 D10次35. 下面给出的四种排序法中( D )排序法是不稳定性排序法。 A插入 B冒泡 C二路归并 D堆积36. 下面 B 方法可以判断出一个有向图中是否有环（回路）？ A.深度优先遍历 B.拓朴排序 C.求最短路径 D.求关键路径37. .若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( D ) A.顺序存储结构 B.链式存储结构 C.索引存储结构 D.散列存储结构 38. 在长度为n的顺序表的第i(1in+1)个位置上插入一个元素，元素的移动次数为( A ) A.n-i+1 B.n-i C.i D.i-1 39. .对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( C ) A.顺序表 B.用头指针表示的单循环链表 C.用尾指针表示的单循环链表 D.单链表 40. .为查找某一特定单词在文本中出现的位置，可应用的串运算是( D ) A.插入 B.删除 C.串联接 D.子串定位 41. 已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=SCIENCESTUDY，则调用函数Scopy(P,Sub(S,1,7)后得到( A ) A.P=SCIENCE B.P=STUDY C.S=SCIENCE D.S=STUDY 42. 三维数组A456按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A345的存储地址为(B ) A.356 B.358 C.360 D.362 43. 如右图所示广义表是一种( C ) A.线性表 B.纯表 C.结点共享表 D.递归表 44. 下列陈述中正确的是( D ) A.二叉树是度为2的有序树 B.二叉树中结点只有一个孩子时无左右之分 C.二叉树中必有度为2的结点 D.二叉树中最多只有两棵子树，并且有左右之分 45. n个顶点的有向完全图中含有向边的数目最多为( D ) A.n-1 B.n C.n(n-1)/2 D.n(n-1) 46. 已知一个有向图如右所示，则从顶点a出发进行深度优先偏历，不可能得到的DFS序列为( A ) A.a d b e f c B.a d c e f b C.a d c b f e D.a d e f bc47. .在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是( C ) A.快速排序 B.堆排序 C.归并排序 D.基数排序 48. 不可能生成右图所示二叉排序树的关键字序列是( A ) A.4 5 3 1 2 B.4 2 5 3 1 C.4 5 2 1 3 D.4 2 3 1 5 49. ALV树是一种平衡的二叉排序树，树中任一结点的( B ) A.左、右子树的高度均相同 B.左、右子树高度差的绝对值不超过1 C.左子树的高度均大于右子树的高度 D.左子树的高度均小于右子树的高度 50. 在VSAM文件的控制区间中，记录的存储方式为( ) A.无序顺序 B.有序顺序 C.无序链接 D.有序链接二、判断题(判断下列各题是否正确，若正确在括号内打“”，错误的打； 1如果两个串含有相同的字符，则这两个串相等。（N） 2数组可以看成线性结构的一种推广，因此可以对它进行插入、删除等运算。( N)， 3在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块元素个数有关。（Y）4在顺序表中取出第i个元素所花费的时间与i成正比。（N） 5在栈满情况下不能作进栈运算，否则产生“上溢”。（Y） 6二路归并排序的核心操作是将两个有序序列归并为一个有序序列，(Y) 7对任意一个图，从它的某个顶点出发，进行一次深度优先或广度优先搜索，即可访问图的每个顶点。（N）8二叉排序树或是一棵空二叉树，或是具有下列性质的二叉树；若它的左子树非空，则根结点的值大于其左孩子的值；若它的右子树非空，则根结点的值小于其右孩子的值。（N）9在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的(N)。10一个有向图的邻接表和逆邻接表中表结点的个数一定相等（Y）（101，88，46，70，34，39，45，58，66，10）是堆（Y）； 将一棵树转换成二叉树后，根结点没有左子树（N）； 用二叉树的前序遍历和中序遍历可以导出树的后序遍历（Y）； 即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同(N)； 哈夫曼树是带权路径长度最短的二叉树，路径上权值较大的结点离很较近（Y）。11、表示一个有1000个顶点、1000条边的有向图的邻接矩阵有1000000个矩阵元素，是否稀疏矩阵 是 12.（ N）串长度是指串中不同字符的个数。13.（ N）数组可以看成是线性结构的一种推广，因此可以对它进行插入、删除等运算。14.（ Y）在顺序表中取出第i个元素所花费的时间与i成正比。15. ( Y)在栈满的情况下不能作进栈的运算，否则产生“上溢”。16.（ Y二路归并排序的核心操作是将两个有序序列归并为一个有序序列。17.（ N ）对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。18.（ Y）一个有向图的邻接表和逆邻接表中的结点个数一定相等。19（ Y）在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表的个数有关，而且与每一块中的元素个数有关。12（ N）叉排序树或者是一棵空树，或者 是具有下列性质的二叉树：若它的左子树非空，则根结点的值大于其左孩子的值；若它的右子树非空，则根结点的值小于其右孩子的值。21（ N）执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。三、填空题1. 在带有头结点的单链表L中，第一个元素结点的指针是_L-next_。2. 在双循环链表中，在指针p所指结点前插入指针s所指的结点，需执行下列语句：s-next=p; s-prior=p-prior; p-prior=s; _s-prior-next_=s;3. 设s1.maxsize为一个顺序存储的栈，变量top指示栈顶位置，栈为空的条件是_top=0_，栈为满的条件是_top=maxsize_。4. 具有100个结点的完全二叉树的深度为_7_。5. 有向图G用邻接矩阵A1.n,1.n存储，其第i行的所有元素之和等于顶点i的_出度_。6r指向单链表的最后一个结点，要在最后一个结点之后插入e所指的结点，需执行的三条语句是r-next=s; r=s；rnext=NULL。 7在单链表中，指针p所指结点为最后一个结点的条件是p-next=null8设一个链栈的栈顶指针是ls，栈中结点格式为info;link;栈空的条件是 ls=null。如果栈不为空，则退栈操作为p=ls； ls=ls-link；free(p)。9已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有12个叶子结点。10图有三种常用的存储结构，即孩子链表法，孩子兄弟链表法和 双亲表示法。11n个顶点的连通图的生成树有n-1条边。12一个有向图G中若有弧、和，则在图G的拓扑序列中，顶点vi,vj vk的相对位置为i,j,k13设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序 方法对其进行排序(按递增顺序)：冒泡最省时间，快速最费时间。14。下面是将键值为x的结点插入到二叉排序树中的算法，请在划线处填上适当的内容。 typedef struct pnode int key； struct node *left，*right；void searchinsert(int x;pnode t)/*t为二叉排序树根结点的指针*/if (t=null) p=malloc(size);p-key=x;p-left=null;p-right=null;t=p; else if (xkey) searchinsert(x,t-left) else searchinsert(x,t-right)15线性表的循环链表的主要优点是从表中任一结点出发都能访问到所有的结点。而使用双向链表，可根据需要在前后两个方向上方便地进行查找。16在带有头结点的单链表L中，则需执行下列三条语句：u=L-next ；Lnext=u-next；free(u);17有一个长度为20的有序表采用二分查找方法进行查找，共有4 个元素的查找长度为3。 18采用冒泡排序对有n个记录的表A按键值递增排序；若L的初始状态是按键值递增，则排序过程中记录的比较次数为n-1。若A初始状态为递减排列，则记录的交换次数为n(n-1)/219.在无头结点的双链表中，指针p所指结点是第一结点的条件是p-prior=null.20G为无向图，如果从q的某个顶点出发，进行一次广度优先搜索，即可访问图的每个顶点，则该图一定是连通图。21如果一个有向图中没有环，则该图的全部结点可以排成一个拓扑序列。22深度为8(根的层次号为1)的满二叉树有8 个叶子结点。23将一棵有100个结点的完全二叉树按层编号，则编号为49的结，其双亲PARENT(X) 的编号为 24 。24设有一个链队，结点结构为data;next；front为队头指针，rear为队尾指针，当执行入队操作时需执行下列语句：malloc(p);p-data=x;p-next=null;rear-next=p;rear=p;25.在散列法中，元素个数 越多，发生冲突的可能性越大。26在带有头结点的单链表L中，第一个元素结点的指针是 L-next。27在顺序文件中，存取第i个记录，必须先存取 第I-1号元素。28设s1.maxsize为一个顺序存储的栈，变量top指示栈顶位置，栈为空的条件是 top=0，栈为满的条件是 top=maxsize29具有64个结点的完全二叉树的深度为 7 30有向图G用邻接矩阵A1.N,1.N存储，其第I列的所有元素之和等于顶点I的入度。 31在双循环链表中，若要在指针P所指结点前插人指针S所指的结点，则需执行下列语句 s-next=p;s-prior=p-prior;p-prior=s;s-prior-next=p;32对于下图所示二叉树；按前序遍历所得到的结点序列A，B，D，E，H，C，F33分别采用堆排序、快速排序、冒泡排序和归并排序算法对初始状态为递增序列的表按递增顺序排序，最省时间的是冒泡排序 ，最费时间的是快速算法34. 对于下面的二叉树，按中序遍历所得到的结点序列为_。35. 对下图所示的网，执行prim算法可得到最小生成树，试在下表的空白处填上适当的内容，以说明该算法的执行过程。 1 5 5 4 23214顶点134UV（U，V）代价（2，1）（2，3）4（2，4）221，3，4（U，V）代价（2，3）42，41，3（U，V）代价（3，1）12，4，31（U，V）代价2，4，3，136、设广义表L(（），（）) 则head(L)是 () ；tail(L)是 ()；L的长度是 2 ；深度是 2 37、在n个记录的有序顺序表中进行折半查找，最大的比较次数是logn 。在如图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两个语句实现该操作，它们依次是_S-NEXT-NEXT=P-NEXT_和_P-NEXT=S_。 38串S=I am a worker的长度是_14_。假设一个10阶的下三角矩阵A按列优顺序压缩存储在一维数组C中，则C数组的大小应为_55_。 39在n个结点的线索二叉链表中，有_n+1_个线索指针。40对关键字序列(52，80，63，44，48，91)进行一趟快速排序之后得到的结果为_48,44,52,63,80,91_。二、 应用题1 已知二叉树的后跟序列和中根序列如下，构造出该二叉树。后根序列：ABCDEFG中根序列：ACBGEDF2 有一组关键码序列8，9，5，3，7，2，1，分别采用冒泡排序、快速排序、直接选择排序、直接插入排序、二路归并排序方法由小到大进行排序，在下面的选项中请选择各种排序第一趟排序的结果。冒泡排序：E快速排序：A直接选择排序：B直接插入排序：C二路归并：FA1，2，5，3，7，8，9B1，9，5，3，7，2，8C9，8，5，3，7，2，1D9，5，3，7，2，1，8E8，5，3，7，2，1，9F8，9，3，5，2，7，13 设图G=（V，E），V=1，2，3，4，5，6，E=，请写出图G中顶点的所有拓扑序列。4 设图G=（V，E），V=1，2，3，4，5，6，E=，请画出其邻接表，并说明每个顶点的入度和出度。5 对如下所示的二叉树，画出其顺序存储结构。6 已知图G的邻接表如图所示，画出图G的所有连通分量。现有5个结点（A，B，C，D，E），它们的权值分别为5，10，12，15，30，在下面的选项中选择一个编号，说明这5个结点的哈夫曼编码。（2）（1） A：1，B：001，C：010，D：011，E：000（2） A：000，B：001，C：010，D：011，E：1（3） A：001，B：011，C：010，D：000，E：1（4） A：000，B：1，C：010，D：011，E： 0017 已知一表为23，45，24，6，57，45，35，按表中顺序依次插入初始为空的二叉排序树，要求画出建立的二叉排序树。设有序序列30,18,3,61,14,49，请按该序列构成一棵二叉排序树，并求其查找成功时的平均查找长度。 答：二叉排序树: (3分)平均查找长度= (1+22+32+4) * 1/6 =2.5 (2分)8 对如下所示的交通网，顶点表示城市，边表示连接城市间的公路，边上的权表示修路的代价。怎样选择能够沟通每个城市且总造价最省的n-1条公路，画出所有可能的方案。9 设有n个元素的有序表为A，K为一个给定的值，填空完成二分查找算法：binsrch(a,n,k)int a,k; int low,hig,mid; low=0; hig=n; while(low=hig) mid=(low+hig)/2;if(kn=G1-n; G2-e=G1-e; for(i=0;in;i+) G2-adjlisti.vertex=G1-vexsi; G2-adjlisti.firstedge= (1) ; for (i=0;in;i+) for (j=0;jn;j+) if(G1-edgesijweight= (2) ; p-adjvex=j; p-next=G2-adjlisti.firstedge; (3) ; (1) NULL(2) G1-edgesij(3) G2-adjlisti.firstedge=p11.阅读下列算法，并回答下列问题： (1)该算法采用何种策略进行排序? 插入排序(2)算法中Rn+1的作用是什么? 监视哨Typedef struct KeyType key; infoType otherinfo; nodeType; typedef nodeType SqListMAXLEN; void sort(SqList R,int n) /n小于MAXLEN-1 int k;i; for(k=n-1;k=1;k-) if(Rk.keyRk+1.key) Rn+1=Rk; for(i=k+1;Ri.key=hr)h=h1+1; 2分else h=hr+1四、算法填空和分析1、ListInsert_L(LinkList L, int pos, ElemType e) /在带头结点的单链表L中第pos个数据元素之前插入数据元素eStatus ListInsert_L(LinkList L, int pos, ElemType e) p = L; j = 0;while (p & j next; +j; / 寻找第pos-1个结点if (!p | j pos-1) return ERROR; / pos小于1或者大于表长s = (LinkList) malloc ( sizeof (LNode); / 生成新结点s-data = e; s-next = p-next; / 插入L中p-next = s;return OK;2、void Merge (Elem SR, Elem TR, int i, int m, int n) / 将有序的SRi.m和SRm+1.n归并为有序的TRi.nfor (j=m+1, k=i; i=m & j=n; +k) / 将SR中记录由小到大地并入TRif (SRi.key=SRj.key) TRk = SRi+;else TRk = SRj+;if (i=m) TRk.n = SRi.m;/ 将剩余的SRi.m复制到TRif (j=n) TRk.n = SRj.n;/ 将剩余的SRj.n复制到TR / Merge3、int Partition (Elem R, int low, int high) / 交换记录子序列Rlow.high中的记录，使枢轴记录到位，并返回/其所在位置，此时，在它之前（后）的记录均不大（小）于它R0 = Rlow;/ 用子表的第一个记录作枢轴记录pivotkey = Rlow.key; / 枢轴记录关键字while (lowhigh) / 从表的两端交替地向中间扫描while(low=pivotkey)-high;Rlow = Rhigh;/ 将比枢轴记录小的记录移到低端while (lowhigh & Rlow.key=pivotkey) +low;Rhigh = Rlow;/ 将比枢轴记录大的记录移到高端Rlow = R0; / 枢轴记录到位return low; / 返回枢轴位置 / Partition4、折半查找算法：int binsrch(JD r,int n,int k) int low,high,mid,found; low=1; high=n; found=0; while(lowrmid.key) low=mid+1; else if(k=rmid.key) found=1; else high=mid-1; if(found=1) return(mid); else return(0);5、设有一个表头为head的单链表。通过遍历一趟链表，将链表中所有结点按逆序链接。Typedef struct nodeint data; struct node *next;pointer;Void invert(pointer head)p=NULL;while (head!=NULL)u=head; head=head-next;u-next= p ;p=u;had=p;五、编写算法：1、设某单链表L的结点结构如下，单链表L用于存放某人的电话薄，现在由于电话号码从7位升为8位（加60000000），请用C语言编写算法，实现电话薄中所有电话号码从7位升为8位。Typedef struct nodechar name9;/姓名long data;/电话号码 struct node *next;pointer;int length(pointer L) p=L; while(p!=NULL) p-data= p-data+60000000;p=p-next;2、设二叉树采用二叉链表表示，编写算法，将二叉树中所有结点的左右子树相互交换。void Bitree_Revolute(Bitree T)/交换所有结点的左右子树T-lchildT-rchild; /交换左右子树if(T-lchild) Bitree_Revolute(T-lchild);if(T-rchild) Bitree_Revolute(T-rchild); /左右子树再分别交换各自的左右子树 设计题：1 设某单链表L的结点结构为data,next,试画出该链表的结构图，并用类C语言编写算法，判断该链表的元素是否是递增的。2 设某单链表L的结点结构为data,next,试画出该链表的结构图，并用类C语言编写算法，统计该链表的长度。3 设一棵二叉树以二叉链表作为存储结构，结点结构为lch,data,rch，其中data域中存放一个字符，设计一个算法按前根遍历顺序打印出data域为数字的字符。4 设BT为二叉排序树，t指向根结点，每个结点的结构为lch,key,rch，试用类C语言写出算法，用来输出二叉排序树中最小的键值。5 设一棵二叉树以二叉链表为存储结构，结点结构为lch,data,rch，设计一个算法求此二叉树上度为2的结点数。6 设一个环上有若干个整数，若采用单循环链表L存储该环，L的存储结构为：data,next，试画出链表L的结构图，并编写算法判断环上任意两个相邻的键值之差的绝对值是否不超过2。7.假设二叉树T采用如下定义的存储结构： typedef struct node DataType data; struct node *lchild,*rchild; PBinTree; 其中，结点的lchild域和rchild域已分别填有指向其左、右孩子结点的指针。请编写一个递归算法，将该存储结构中各结点的lchild和rchild域的值进行交换。 2001年10月数据结构试题及答案一、 单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。1算法指的是（ ） A计算机程序 B解决问题的计算方法 C排序算法 D解决问题的有限运算序列2线性表采用链式存储时，结点的存储地址（ ） A必须是不连续的 B连续与否均可 C必须是连续的 D和头结点的存储地址相连续3将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（ ） AO（1） BO（n） CO（m） DO（m+n）4由两个栈共享一个向量空间的好处是：（ ） A减少存取时间，降低下溢发生的机率 B节省存储空间，降低上溢发生的机率 C减少存取时间，降低上溢发生的机率 D节省存储空间，降低下溢发生的机率5设数组datam作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ ） Afront=front+1 Bfront=(front+1)%(m-1) Cfront=(front-1)%m Dfront=(front+1)%m6如下陈述中正确的是（ ） A串是一种特殊的线性表 B串的长度必须大于零 C串中元素只能是字母 D空串就是空白串7若目标串的长度为n，模式串的长度为n/3，则执行模式匹配算法时，在最坏情况下的时间复杂度是（ ） AO（ ） BO（n） CO（n2） DO（n3）8一个非空广义表的表头（ ） A不可能是子表 B只能是子表 C只能是原子 D可以是子表或原子9假设以带行表的三元组表表示稀疏矩阵，则和下列行表0 2 3 3 5 对应的稀疏矩阵是（ ） 10在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( ) A4 B5 C6 D711在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( ) Ae B2e Cn2e Dn22e12假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是( ) AO(n) BO(e) CO(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希尔排