全国2010年1月自考数据结构试题及答案.doc

更多优质自考资料尽在百度贴吧自考乐园俱乐部（全国2010年1月自考数据结构试题及答案课程代码：02331一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1若一个算法的时间复杂度用T(n)表示，其中n的含义是（ A ）A问题规模 B语句条数C循环层数 D函数数量2具有线性结构的数据结构是（ C ）A树 B图C栈和队列 D广义表线性结构有：顺序表、栈和队列、串3将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为（ C ）AO(1) BO(m)CO(n)DO(m+n)4在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是（ D ）A2个 B3个 C4个D6个5假设以数组A60存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为（ D ）A3 B37C50 D976若栈采用链式存储结构，则下列说法中正确的是（ B ） A需要判断栈满且需要判断栈空 B不需要判断栈满但需要判断栈空 C需要判断栈满但不需要判断栈空D不需要判断栈满也不需要判断栈空7若串str=”Software”，其子串的数目是（ D ）A8 B9C36 D378设有一个10阶的下三角矩阵A，采用行优先压缩存储方式，all为第一个元素，其存储地址为1000，每个元素占一个地址单元，则a85的地址为 （ C ）A1012 B1017C1032 D1039P61中在n阶方阵A这个下三角矩阵中，第i（i从0开始）行（0in）有i+1个元素，元素总数为：n(n+1)/2，并将元素放在一个向量sa0. n(n+1)/2-1中。若ij，则aij在左下三角矩阵中，sak与aij的对应关系是k=i(i+1)/2+j。若idataS-top； 19在串匹配中，一般将主串称为目标串，将子串称为_模式串_。P5520已知广义表C=(a(b，c)，d)，则：tail(head(tail(C)= _( )_。P66中若广义表LS非空（n1）（通常用圆括号将广义表括起来，用逗号分割其中的元素。用大写字母表示广义表，用小写字母表示原子。），则a1是LS的表头，其余元素组成的表称为LS的表尾。长度：元素的个数深度：表展开后所含括号的层数（从最里面往最外面数）21用6个权值分别为6、13、18、30、7和16的结点构造一棵哈夫曼(Huffman)树，该树的带权路径长度为_231_。 22已知有向图如下所示，其中顶点A到顶点C的最短路径长度是_35_。23对序列55，46，13，05，94，17，42进行基数排序，第一趟排序后的结果是42,13,94,55,05,46,17。24高度为3的3阶B-树最少的关键字总数是_7_。一颗高度为h的k阶B-树中最多可容纳多少个关键字？解 要使高为h的k阶B-树容纳最多的关键字，则每个结点中的关键自数据就必须达到最大值k-1.因此这时的25VSAM通常作为大型索引顺序文件的标准组织，其动态索引结构采用的是_B+树_。P214三、解答题(本大题共4小题，每小题5分，共20分)26假设二叉树的RNL遍历算法定义如下： 若二叉树非空，则依次执行如下操作： (1)遍历右子树； (2)访问根节点； (3)遍历左子树。已知一棵二叉树如图所示，请给出其RNL遍历的结果序列。GCFABDP77页图6.11中的中序序列LNR、前序序列NLR、后序序列LRN27已知一个无向图G=(V，E)，其中V=A，B，C，D，E，F，邻接矩阵表示如下所示。请回答下列问题：(1)请画出对应的图G。P103中的图7.70 1 2 3 4 5A B C D E F 0 A 0 1 0 1 0 01 B 1 0 1 1 1 02 C 0 1 0 0 0 1 3 D 1 1 0 0 1 04 E 0 1 0 1 0 15 F 0 0 1 0 1 0 (2)画出图G的邻接表存储结构。P105中图7.828已知一组待排记录的关键字序列为(16，12，18，60，15，36，14，18，25，85)，用堆排序方法建小根堆，请给出初始建堆后的序列。P154中，注：n=10，从第n/2（1i ）个结点起进行调整。若i=5，则与i=10或i=11进行互换；即i与2i或2i+1中的关键字进行互换。29已知一棵二叉排序树如图所示。 请回答下列问题：(1)画出插入元素23后的树结构；(2)请画出在原图中删除元素57后的树结构。四、算法阅读题(本大题共4小题，每小题5分，共20分)30已知下列程序，Ls指向带头结点的单链表。 Typedef struct node DataType data; struct node * next; * LinkList; void f30( LinkList Ls ) LinkList p, q; q = Ls-next; if ( q & q-next ) Ls-next = q-next; p=q while ( p-next ) p = p-next; p-next = q; q-next = NULL;请回答下列问题：(1)当Ls指向的链表如下图所示，请画出执行本函数之后的链表的结果。(2)请简述算法的功能。删除单链表的中间结点和尾结点。31已知字符串处理函数f31程序如下。 int f31(char*strl，char*str2) while(*strl=*str2&(*strl!=0) strl+； str2+； return(*strl-*str2 ? l0)； 请回答下列问题：(1) 若调用语句是f31(”abcde”，”abcdf”)，则函数的返回值是什么?答：A的ASCII 065A的ASCII 097若调用语句是 f31(”abcde”，”abcde”)，则函数的返回值是什么?答：由于字符串结束标识0对应的ASCII码是0，则*strl-*str2=0再按照条件表达式的形式为逻辑表达式？表达式1：表达式2若逻辑表达式的值为非零，则条件表达式的值等于表达式1的值；若逻辑表达式的值为零，则条件表达式的值等于表达式2的值。则函数的返回值是0。 (2)简述该函数的功能。答：如果两个字符串结点*strl和*strl中的字符相等，且字符串结点*strl中的字符不等于字符串结束标识0，则两个字符串结点*strl和*strl中的字符指针自加运算。如果条件不满足，则字符串结点*strl和*strl中的字符相减。若逻辑表达式的值为非零，则条件表达式的值等于1；若逻辑表达式的值为零，则条件表达式的值等于0。32数组A中存储有n个整数，请阅读下列程序。 void f32(intA，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 while return； 请回答下列问题：(1)当A=10，8，2，4，6，7时，执行f32(A，6)后，数组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 struct KeyType key； InfoType otherinfo； SeqListN+1； int BinSearch(SeqList R, int n，KeyType K) int low=1，high=n； while( (1)lowK) high=mid-1； else (3)low=mid+1 ； return O； BinSearch 请在空白处填写适当内容，使该程序功能完整。 (1) lowlchild)+ SumNodes(T-rchild)+1;自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园.俱乐部id：5346389（请牢记它哦在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部