1、更多优质自考资料尽在百度贴吧自考乐园俱乐部（http:/ ）欢迎加入.欢迎 交流.止不住的惊喜等着你.自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园.俱乐部 id：5346389（请牢记它哦在百度贴吧的搜索框中输入俱乐部 id,可以直接进入俱乐部全国 2010 年 1 月自考数据结构试题及答案课程代码：02331一、单项选择题(本大题共 15 小题，每小题 2 分，共 30 分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1若一个算法的时间复杂度用 T(n)表示，其中 n 的含义是（ A ）A问题规模 B语句条
2、数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需要判断栈满且需要判
3、断栈空B不需要判断栈满但需要判断栈空C需要判断栈满但不需要判断栈空D不需要判断栈满也不需要判断栈空7若串 str=”Software”，其子串的数目是（ D ）A8 B9C36 D378设有一个 10 阶的下三角矩阵 A，采用行优先压缩存储方式，a ll为第一个元素，其存储地址为1000，每个元素占一个地址单元，则 a85的地址为 （ C ）A1012 B1017C1032 D1039P61 中在 n 阶方阵 A 这个下三角矩阵中，第 i（i 从 0 开始）行（0idataS-top；19在串匹配中，一般将主串称为目标串，将子串称为_模式串_。P5520已知广义表 C=(a(b，c)，d)，则
4、：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进行基数排序
5、，第一趟排序后的结果是42,13,94,55,05,46,17。箱 号 0 1 2 3 4 5 6 7 8 9内 容 42 13 94 55,05 46 17箱 号 0 1 2 3 4 5 6 7 8 9内 容 5 13,17 42,46 55 94第 一 次 装 箱 (a)第 二 次 装 箱 (b)24高度为 3 的 3 阶 B-树最少的关键字总数是_7_。一颗高度为 h 的 k 阶 B-树中最多可容纳多少个关键字？解 要使高为 h 的 k 阶 B-树容纳最多的关键字，则每个结点中的关键自数据就必须达到最大值 k-1.因此这时的25VSAM 通常作为大型索引顺序文件的标准组织，其动态索引结构
6、采用的是_B +树_。P214更多优质自考资料尽在百度贴吧自考乐园俱乐部（http:/ ）欢迎加入.欢迎 交流.止不住的惊喜等着你.自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园.俱乐部 id：5346389（请牢记它哦在百度贴吧的搜索框中输入俱乐部 id,可以直接进入俱乐部三、解答题(本大题共 4 小题，每小题 5 分，共 20 分)26假设二叉树的 RNL 遍历算法定义如下：若二叉树非空，则依次执行如下操作：(1)遍历右子树；(2)访问根节点；(3)遍历左子树。已知一棵二叉树如图所示，请给出其 RNL 遍历的结果序列。GCFABDP77 页图 6.11 中的中序序列
7、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已知 一组待排记录的关键字序 列为FEDCBA012345vertxfirstedgadjvexnxt130
8、 32 4150 411 5324顶 点 表 边 表更多优质自考资料尽在百度贴吧自考乐园俱乐部（http:/ ）欢迎加入.欢迎 交流.止不住的惊喜等着你.自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园.俱乐部 id：5346389（请牢记它哦在百度贴吧的搜索框中输入俱乐部 id,可以直接进入俱乐部(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 中的关键字进行互换。2
9、9已知一棵二叉排序树如图所示。请回答下列问题：(1)画出插入元素 23 后的树结构；(2)请画出在原图中删除元素 57 后的树结构。85218436156018216 10974316121860536418258i=， 不 调 整 8526014361581216 10987431612188536460258i=4， 调 整85260183615814216 1097312141815361860258i=， 调 整 8526018361814512 109753215148636860258i=2， 不 调 整i1， 调 整小 根 堆 初 始 建 堆 后 的 序 列23更多优质自考资料尽
10、在百度贴吧自考乐园俱乐部（http:/ ）欢迎加入.欢迎 交流.止不住的惊喜等着你.自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园.俱乐部 id：5346389（请牢记它哦在百度贴吧的搜索框中输入俱乐部 id,可以直接进入俱乐部四、算法阅读题(本大题共 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 p=qwhile ( 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
