自考数据结构试题和答案

1、错选、多选或未n的含义是(A )B .语句条数D .函数数量B .图D .广义表m的单链表之后，其算法的时间复杂度为(B. 0(m)D.0(m+n)2010年1月高等教育考试数据结构试题和答案课程代码：02331一、单项选择题 (本大题共15小题，每小题 2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内 选均无分。1 .若一个算法的时间复杂度用T(n)表示，其中A .问题规模C.循环层数2 .具有线性结构的数据结构是(C )A .树C .栈和队列线性结构有：顺序表、栈和队列、串3 .将长度为n的单链表连接在长度为A. 0(1)C.0( n)4 .

2、在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是(x的新结点插入结点*p 之前，当前队列有50个元素，则队列的尾指针值为A. 2个C. 4个P28中void Din sertBefore(DListNode *p,DataType x)设 pz NULLDListNode *s=malloc(sizeof(ListNode);s-data=x;s-prior=p-prior;s-n ext=p;p-prior- n ext=s;p-prior=s;5 .假设以数组 A60存放循环队列的元素，B. 3个D. 6个在带头结点的双链表中，将值为其头指针是fron t=47D. 97C

3、. 50辅导书 P22中（front 指向实际队头， rear指向实际队对于循环向量中的循环队列，写出通过队头队尾指针表示的队列长度公式。尾的下一元素位置。）当rear front时，队列长度L=rear-fr ont ；当rearvfr ont时，L=m+(rear-fr ont)。这两种情况可统一为，这里m为向量的大小。本题 中6 .若栈采用链式存储结构，则下列说法中正确的是（L=(m+(rear-fr on t)%mm=60A.需要判断栈满且需要判断栈空B.不需要判断栈满但需要判断栈空C .需要判断栈满但不需要判断栈空D.不需要判断栈满也不需要判断栈空P36中因为链栈中的结点是动态分配的

4、，可以不考虑上溢，所以无需定义stackFull 运算。7 .若串str= ” Software ”，其子串的数目是（C. 3637P51中任意个连续字符组成的子序列称为该串的子串。设有一个10阶的下三角矩阵 A ,米用行优先压缩存储方式，an为第一个元素，其存储地址为1000,每个元素占10121032在n阶方阵A这个下三角矩阵中，第i j，则aj在左下三角矩阵中，sak与aj的对应关系是k=i(i+1)/2+ja若i1）（通常用圆括号将广义表括起来，用逗号分割其中的元素。用大写字母表示广义表，用小17 .长度为n的线性表采用单链表结构存储时，在等概率情况下查找第i个元素的时间复杂度是O(n

5、)P171中二分查找(Binary Search )又称折半查找，它是一种效率较高的查找方法。但是，二分查找要求线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。一般设有序表是递增有序的。二分查找的基本思想是：设Rlowhigh 是当前的查找区间，首先确定该区间的中点位置mid= L(low+high)/2 ，然后将待查的K值与Rmid.key比较，若相等，则查找成功并返回此位置，否则须确定新的查找区间；若Rmid.keyK ，则由表的有序性可知Rmidn.keys均大于 K,因此若表中存在关键字等于K的结点，则该结点必定是在位置mid左边的子表 R1mid-1中，故新的查

6、找区间是左子表R1mid-1 ;类似地，若 Rmid.keydataS-top；19 .在串匹配中，一般将主串称为目标串，将子串称为_模式串_。P5520 .已知广义表C=(a(b , c) , d),贝卩：tail(head(tail(C)= ()P66中写字母表示原子。），贝U ai是LS的表头，其余元素组成的表称为LS的表尾。长度：元素的个数深度：表展开后所含括号的层数（从最里面往最外面数）21 .用6个权值分别为6、13、18、30、7和16的结点构造一棵哈夫曼 （Huffman）树，该树 的带权路径长度为231P90中结点的带权路径长度，是该结点到树根之间的路径长度与结点上权的乘积。

7、WPL=30 X1+18 X2+16 X3+13 X4+6 X5+7 X5=30+36+48+52+30+35=23122 .已知有向图如下所示，其中顶点A到顶点C的最短路径长度是_35_。P90中树的路径长度是从树根到树中每一结点的路径长度之和。显然，在结点数目相同的二叉树中，完全二叉树的路径长度最短。P122 中源点s到终点v的最短路径长度简称为最短距离。P73中完全二叉树（Complete Bi nary Tree ，见图6.7的b）若一颗二叉树至多只有最下面的两层上结点的度数（P70中,一个结点拥有的子树数称为该结点的度Degree。一颗树的度是指该树中的结点的最大度数。度为零的结点称

8、为叶子Leaf或终端结点。）可以小于2，而且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。23 .对序列55 , 46 , 13 , 05 , 94 , 17 , 42进行基数排序，第一趟排序后的结果是42,13,94,55,05,46,17 P162 中基数排序的基本思想是：从低位到高位依次对Kj （j二d-1,d-2,d-3? ,0 ）进行箱排序。在d趟箱排序中，所需的箱子数就是基数 rd。K如被排序的记录关键字i取值范围是0-99间整数的例子，就是一个基数radix为10 , d为2的基数排序。899424 .高度为3的3阶B-树最少的关键字总数是_7。辅导书P

9、147中（最多关键字总数的解答）一颗高度为 h的k阶B-树中最多可容纳多少个关键字？解 要使高为h的k阶B-树容纳最多的关键字，则每个结点中的关键自数据就必须达到最大值k-1.因此这时的B-树实际上可看成是满k叉树。不妨设根的层数为1，则第1层只有1个根结点，第2层上共有k个结点，第2h-l上共有k个结点，？，第 h层上共有k个结点，树中结点总数为：由每个结点可容纳k-1关键字可知，树中可容纳的关键字总数为：hn=（k-1） Xm=（k-1） x=k -13以h=3 , k=101为例，相应的 B-树最多可容纳101 -1=100+10100+1020100=1030300个关键字，树中结点总

10、数为3（101 -1）/100=1+101+10201=10303。示意图如下：第1层：1个结点100个关键字第2层：101个结点101 X100=10100 个关键字2第3层：101 =10201个结点10201x 100=1020100 个关键字j满足：厂m/2 n -1 wj Em-1。即每个非根结点至hn -1 ,最少可容纳的结点总数为P182中（最少关键字总数的解答）一颗m （ m為）阶的B-树，每个非根结点中所包含的关键字个数少应有厂m/2n-1个关键字，至多有 m-1个关键字。（注：厂m/2n是指不小于（即大于等于）m/2的最小整数。）一颗高度为h的m阶B-树中最少可容纳的关键字

11、总数为：厂m/2h厂 m/2 n -1h3厂m/2 q -1= 2 -1=7个。示意图如下:B+树。P214厂 m/2 n -i以h=3 , m=3为例，相应的B-树最少可容纳的关键字总数为第1层：1个结点厂m/2 n -1=1个关键字第2层：2个结点2 个关键字2第3层：2 =4个结点4个关键字25 . VSAM通常作为大型索引顺序文件的标准组织，其动态索引结构采用的是三、解答题(本大题共 4小题，每小题 5分，共20分)26 .假设二叉树的RNL遍历算法定义如下：若二叉树非空，则依次执行如下操作：(1) 遍历右子树；(2) 访问根节点；(3) 遍历左子树。已知一棵二叉树如图所示，请给出其R

12、NL遍历的结果序列GCFABD27 .已知一个无向图P77页图6.11中的中序序列 LNR、前序序列 NLR、后序序列 LRND,E,F邻接矩阵表示如下所示。P10100】101110010001G=(V , E)，其中 V=A , B, C,110 0 100 1 0 I 0 10 0 10 10请回答下列问题：(1) 请画出对应的图 G。P103中的图7.7012345ABCDEF0 A0101001 B1011102 C0100013D 110010（2）画出图G的邻接表存储结构。 P105中图7.828 .已知一18 ,0mLd123435vertexfirstedge顶点表adjve

13、xnext2-4边表组待排记录的关键字序列为（16 , 12,60, 15, 36 , 14 , 18, 25 , 85），用堆排序方法建小根堆，请给出初始建堆后的序列。P154 中，注：n=10，从第匚 n/2（1 i n ext;if ( q & q- next ) Ls-n ext = q-n ext; p=qwhile ( p-next )p = p-n ext;p-n ext = q;q-next = NULL;请回答下列问题:(1)当Ls指向的链表如下图所示，请画出执行本函数之后的链表的结果。LsM(2)请简述算法的功能。删除单链表的中间结点和尾结点31 .已知字符串处理函数f31

14、程序如下in t f31(char*strl,char*st while(*strl=*str2&(*strl!= 0 )strl+；str2+ ；return(*strl-*str2 ? l0)请回答下列问题:(1)若调用语句是 f31( ” abcde ”abcdf ”)，贝V函数的返回值是什么答:A 的 ASCII 065A 的 ASCII 097由于e 对应的ASCII码是101，f对应的 ASCII码是102，则e f=101 102=-1再按照条件表达式的形式为 逻辑表达式？表达式 1 :表达式2若逻辑表达式的值为非零，则条件表达式的值等于表达式1的值；若逻辑表达式的值为零，则条件

15、表达式的值等于表达式2的值。则函数的返回值是1。若调用语句是f31( ” abcde ”，” abcde ”)，贝V函数的返回值是什么？答：由于字符串结束标识0对应的 ASCII码是0，贝U *strl-*str2=0再按照条件表达式的形式为逻辑表达式？表达式 1 :表达式2若逻辑表达式的值为非零，则条件表达式的值等于表达式1的值；若逻辑表达式的值为零，则条件表达式的值等于表达式2的值。则函数的返回值是0。(2)简述该函数的功能。答：如果两个字符串结点*strl 和*strl中的字符相等，且字符串结点*strl中的字符不等于字符串结束标识0，则两个字符串结点*strl 和*strl中的字符指针

16、自加运算。如果条件不满足，贝V字符串结点*strl1 ;若逻辑表达式的值为零，则和*strl中的字符相减。若逻辑表达式的值为非零，则条件表达式的值等于 条件表达式的值等于0。32 .数组A中存储有n个整数，请阅读下列程序。void f32(i ntA,int n) int i , j , k, x;k=n-l ；while(k0)i=k ；k=0 ；for(j=O ; jAj+1)x=Aj ；Aj=Aj+l；Aj+1=x;k=j ； / end of if / end of whilereturn ；请回答下列问题：(1) 当A=10 , 8, 2, 4, 6, 7时，执行f32(A , 6)

17、后，数组 A中存储的结果是什么？答：数组 A中存储的结果是10。(2) 说明该算法的功能。答：数组 A中存储有 n个整数，当k=n-1时，则第k个向量是最后一个整数。;同时比较第当k0时，即数组A非空时，设i=k， k=0，如果j=0，且ji (即j小于k)时，j自加(即数组下标自加) j个整数和第j+1个整数。如果第j个整数大于第j+1个整数，则通过语句x=Aj；Aj=Aj+l；Aj+1=x；进行交换，同时令 k=j。如果j大于等于i (即j大于等于k)时，则结束执行 if语句和 while语句，并返回。33 .下面程序实现二分查找算法。Typedef structKeyType key ；

18、In foType otheri nfo；SeqListN+1；int Bin Search(SeqList R, i nt n, KeyType K)int low=1, high=n ；while( (1)lowK)high=mid-1 ；else(3) low=mid+1return O;/ Bin Search请在空白处填写适当内容，使该程序功能完整。(1) lowlchild)+ SumNodes (T-rchild)+1;辅导书P66 P76第四题的第2小题中问：写一递归算法求二叉树中度为2的结点总数答：二叉树中度 2度结点数的递归定义如下： 当T为空或T是叶子时，以T为根的二叉树

19、的2度结点数为0 ; 当T是2度结点时，以T为根的二叉树的2度结点数为T的左右子树中2度结点数之和再加上T结点本身; 当T是1度结点时，以T为根的二叉树中2度结点数为T的左右子树中2度结点数之和。算法如下：int D2Nodes(Bi nTree T)if(! T II ! T-lchild & ! T-rchild)/逻辑运算符的执行优先次序是：！非-&与- I或，即T为空或T是叶子return 0;if(T-lchild & T-rchild)/T是 2 度结点return 1+D2Nodes (T-lchild)+D2Nodes(T-rchild);else /T 是1度结点return

20、 D2Nodes(T-lchild)+D2Nodes (T-rchild);二、在任何事情上都不要觉得自己受了多大的委屈，哭哭啼啼和别别扭扭改变不了糟糕的现状。心子开一点，认真地该干啥干啥，反倒走得顺畅许多。扛得住多少东西，最后就会得到多少东西，大致就是这么个理儿吧。三、生命本没有意义，你要能给他什么意义，他就有什么意义。与其终日冥想人生有何意义，不如试用此生做点有意义的事。四、爱怕沉默。太多的人，以为爱到深处是无言。其实，爱是很难描述的一种情感，需要详尽的表达和传递。五、有些路，只能一个人走。六、有一种落差是，你配不上自己的野心，也辜负了所受的苦难。七、有些决定，只需要一分钟，可是，却会用一

21、辈子，去后悔那一分钟。八、“忽然想通了 ”，这五个字说来简单，要做到可真不容易。我佛如来在菩堤树下得道，就因为他“忽然想通了 ”达.摩祖师面壁十八年，才总算“忽然想通了 ”无.论什么事，你只要能 “忽然想通了 ”，你就不会有烦恼，但达到这地步之前，你一定已不知道有过多少烦恼。九、如果他总为别人撑伞，你何苦非为他等在雨中十、我对前任的感觉很简单，哪怕他的女朋友来我面前秀恩爱，我也不会觉得烦。就像在看别人吃一碗很香的卤肉饭，吧唧嘴巴弄得很大声，但我自己心里是明白的：我吃过那种饭，其实没那么好吃。十一、为什么我们总是不懂得珍惜眼前人？在未可预知的重逢里，我们以为总会重逢，总会有缘再会，总以为有机会说

22、一声对不起，却从没想过每一次挥手道别，都可能是诀别，每一声叹息，都可能是人间最后的一声叹息。十二、我在最好的时候碰到你，是我的运气。可惜我没时间了。想想，说人生无悔，都是赌气的话。人生若无悔，那该多无趣啊。我心里有过你。可我也只能到喜欢为止了十三、我说不出来为什么爱你，但我知道，你就是我不爱别人的理由十四、当你在转圈的时候，这个世界很大，当你勇往直前，这个世界就很小十五、现在男女之间的恋爱，总是答应太快，结果分手也快。人性的规律是容易得到的就容易放弃。凡是通过努力得到的，不管是感情还是物品，都会使人顿生珍惜之感。所以在感情上，当有人追求时，内心的一份矜持是必要的，即使心里很爱，也需要给追求者时间和难度，这样两人走到一起才会珍惜感情、地久天长。二十八、失望，有时候也是一种幸福。因为有所期待，所以才会失望。因为有爱，才会有期待。所以纵使失望也是一种幸福，虽然这种幸福有点痛。