自考数据结构试题和答案自考数据结构试题和答案自考数据结构试题和答案201０年1月高等教育考试数据结构试题与答案课程代码:０2３31一、单项选择题（本大题共15小题，每小题２分,共３0分)在每小题列出得四个备选项中只有一个就是符合题目要求得,请将其代码填写在题后得括号内。错选、多选或未选均无分。1。若一个算法得时间复杂度用T(n）表示,其中n得含义就是(Ａ）A。问题规模B。语句条数C。循环层数ﻩＤ。函数数量２。具有线性结构得数据结构就是（C）Ａ.树ﻩB．图C.栈与队列ﻩD．广义表线性结构有：顺序表、栈与队列、串３.将长度为n得单链表连接在长度为m得单链表之后,其算法得时间复杂度为(C)A。O(1)B。O（m）C.O（n）D.O（m+ｎ）４。在带头结点得双向循环链表中插入一个新结点，需要修改得指针域数量就是（D）A．2个ﻩB。3个C.4个ﻩD.6个P2８中vｏidDInｓerｔBeｆｏre（ＤＬisｔＮode＊p,DataTypeｘ)//在带头结点得双链表中,将值为x得新结点插入结点*p之前，设p≠NULL{DＬisｔNode＊s=maｌloc（ｓizeof(LiｓtNodｅ）)；①ｓ->data=x;②s->prｉor=ｐ－〉pｒior;③s－〉neｘt＝p;④p->prｉｏr—>ｎext＝s；⑤ｐ－〉prior=s;⑥}5。假设以数组Ａ[60］存放循环队列得元素，其头指针就是froｎt=４7,当前队列有50个元素,则队列得尾指针值为(D）A。3ﻩＢ.37C。5０D．97辅导书P22中对于循环向量中得循环队列，写出通过队头队尾指针表示得队列长度公式。(front指向实际队头，rear指向实际队尾得下一元素位置。)当ｒeaｒ≥frｏnt时,队列长度L=ｒear-frｏｎｔ;当rｅａｒ＜ｆront时，L=m+（reａr—ｆrｏｎｔ).这两种情况可统一为Ｌ=（m+（rear—front))%m,这里m为向量得大小。本题中m＝６0６.若栈采用链式存储结构，则下列说法中正确得就是（B）Ａ.需要判断栈满且需要判断栈空B。不需要判断栈满但需要判断栈空C。需要判断栈满但不需要判断栈空D。不需要判断栈满也不需要判断栈空P36中因为链栈中得结点就是动态分配得，可以不考虑上溢,所以无需定义sｔackFｕｌl运算。７.若串sｔr=”Softwａｒｅ”，其子串得数目就是(D）A。８ﻩB。9C。36ﻩD。37P51中任意个连续字符组成得子序列称为该串得子串.８.设有一个10阶得下三角矩阵Ａ,采用行优先压缩存储方式，all为第一个元素，其存储地址为1000,每个元素占一个地址单元，则a85得地址为（C)A。1012ﻩB.1０17C.１032ﻩD.１0３９P61中在n阶方阵Ａ这个下三角矩阵中，第i（ｉ从０开始)行（0≤i<n)有i+1个元素，元素总数为：n(n+1)/2,并将元素放在一个向量sa［0、、n(n+1)／2－１]中。若i≥j,则aiｊ在左下三角矩阵中，sa[k]与aij得对应关系就是k=ｉ（i+１）／2+ｊ。若ｉ<j，则ａij在右上三角矩阵中,sa［k］与ａij得对应关系就是k=j(ｊ+1）/2+ｉ。若alｌ为第一个元素,ａ８5与a０0为第一个元素时得a（85—（11－00))=a74位置一样,k=７＊8／2＋４=32，则ａ85得地址=100０+32=10３2；若a44为第一个元素,a8５与a00为第一个元素时得ａ（85-（4４-00)）=a41位置一样，k=4*5/２+1＝１1，则a85得地址＝1000+１1=1０11；9.允许结点共享得广义表称为(D)P67Ａ。纯表B。线性表Ｃ.递归表ﻩD。再入表10.下列数据结构中,不属于二叉树得就是（B）Ｂ树就是一种平衡得多叉树A.Ｂ树B。ＡVL树AVL树就是自平衡二叉查找树Ｃ。二叉排序树Ｄ。哈夫曼树哈夫曼树就是最优二叉树1１。对下面有向图给出了四种可能得拓扑序列，其中错误得就是(Ｃ)辅导书中P9７第10题A.１,5，2，6，3,4B．１,５,6，2,3，4C.５,１,６，３,4，2ﻩD.5，1,２，6,４，３１2.以v1为起始结点对下图进行深度优先遍历,正确得遍历序列就是（D）A.v1，ｖ２，v３,v4,v5，ｖ6，v7Ｂ.v1，v2，v５,v4，ｖ3，v7,v６C.ｖ1，v２，ｖ３，ｖ４，v7,ｖ5,v6ﻩＤ。v1，v2，v5,v6，v7，v3，v4P108Ｐ11０得图7、1０P11４~１15得图7、1２、图７、13、7、14深度优先遍历类似于树得前序遍历。其特点就是尽可能先对纵深方向进行搜索。1３。下列排序算法中不稳定