《02142数据结构导论201510.docx》由会员分享，可在线阅读，更多相关《02142数据结构导论201510.docx（10页珍藏版）》请在三一办公上搜索。
1、2015年10月高等教育自学考试全国统一命题考试数据结构导论试卷(课程代码02142)本试卷共4页，满分l00分，考试时间l50分钟。考生答题注意事项：1. 本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。2. 第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。3. 第二部分为非选择题。必须注明大、小题号，使用0.5毫米黑色字迹签字笔作答。4. 合理安排答题空间。超出答题区域无效。第一部分选择题一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡” 的相应代码
2、涂黑。未涂、错涂或多涂均无分。1. “能正确地实现预定的功能，满足具体问题的需要”。这种评价算法好坏的因素称为A. 正确性 B.易读性 C.健壮性 D.时空性2. 有一程序片段：i=0； s=0； whi1e(s1)的单链表上，设有头和尾两个指针，下列操作与链表长度有关的 是A. 删除单链表中的第一个元素B. 删除单链表中的最后一个元素C. 在单链表中第一个元素前插入一个新元素D. 在单链表中最后一个元素后插入一个新元素5. 某双向链表中的结点如题5图所示。删除t所指结点的操作为Dpnornext题5图A. t prior prior = t next ； t next prior = t p
3、rior B 一 t 一prior prior 二 t prior ；t 一next - next = - nextC, t - prior next = t prior ； t next - prior 二 t 一 nextD. t prior next = t - next ； t - next prior ：= t 一 prior6. 下列关于栈和队列的叙述中：i栈和队列都是线性表；ii栈和队列都是顺序表；m栈和 队列都不能为空；w栈和队列都能用于递归过程实现；v栈的特点是先进后出、队列的 特点是先进先出，其中正确的是A.I 和 V B.I、II、VC.m和 VD.I、W、V7. 二维数
4、组A按行序优先顺序存储，每个数据元素占1个存储单元。若数据元素A11的存储地址是420, A33的存储地址是446,则A55的存储地址是A. 470B. 471C. 472D. 4738. 若对一棵含有199个结点的完全二叉树按自上而下、从左到右依次对结点编号，根结点 的编号为1,则树中最后一个结点(即编号为199 )的双亲结点的编号为A. 99B. 100C. 101D. 1989. 对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找 成功时平均查找长度(ASL)为BA.理B C d3Ah 15B 15- 15 1510. 在如题10图所示的有向图中，从顶点1出发进
5、行深度优先搜索可得到的结果序列是A. 1423B. 1432C. 1342D. 124311. 设森林F中有三棵树，其结点的个数分别为、m2、m3，则与F对应的二叉树根结点的右子树上的结点数是123A. m +mB. m +mC. m +mD. m +m +m12. 假设通信电文使用的字符集为a，b，e，d，e，f，各字符在电文中出现的频率分别为 34, 5，12, 23, 8，18，利用构造Huffman树对每个字符进行编码，则其中编码长度最长 的字符是A. a. bB. a， dC. b， eD.e，f13. 元素的进栈次序为A,B,c, D, E,出栈的第一个元素为E,则第四个出栈的元素
6、为A.DB. CC. BD. A14. 平均时间复杂度和在最坏情况下的时间复杂度均是0(Nlog2n)的排序算法是A插入排序B.快速排序 2C选择排序D.堆排序15. 在待排记录中其关键字序列基本有序的前提下，时间效率最高的排序方法是A.直接插入排序B.快速排序C.选择排序D.堆排序第二部分非选择题二、填空题(本大题共13小题，每小题2分，共26分)请在答题卡上作答。16. 数据的存储结构又称为物理结构，可分为顺序存储、链式存储、索引存储 以及 散列存储等几种方式。17. 一般说来，在每个逻辑结构上都定义了一组基本运算，通常这些运算包括：建立、查找、读取、插入和删除等。head-next! =
7、NULL 19.18. 某带有头结点的单链表的头指针为head,则判断该单链表为非空的条件是 数组Qn表示一个循环队列，设f的值为队列中第一个元素的位置，r的值为队列中实 际队尾的位置加1,并假定队列中最多只有n1个元素，则计算队列中元素个数的公式是(r-f+n)%n.20. 稀疏矩阵可以采用 三元组表示 方法进行压缩存储。21. 含有11个结点的完全二叉树中度为1的结点的个数最多为1。22. 高度(深度)为k的二叉树中结点个数最多是2k-1、最少是 k。23. 对于有n个顶点的无向图，所有生成树中都有且仅有n-1 条边。24. 设散列表的地址空间为0到12，散列函数为h(k)=k mod 1
8、3，用线性探测法解决冲突。 现要将关键字序列10, 100, 32, 45, 58, 128, 3, 29, 200, 400, 0映射到该散列表 中，则其中关键字值58的地址为 8。25. 假设有K个关键字互为同义词，若用线性探测法把这K个关键字用散列函数H将它们存人长度为m的散列表中(KWm)，则至少共需进行 K(K+1)/2 次探测。26. 在关键字序列07,12,15,18, 27, 32, 41, 92中用二分法查找和给定值92相等的 关键字，在查找过程中依次和给定值92比较的关键字是18,32,41,92。27. 影响排序算法时间复杂度的两个因素是关键字的比较 次数和记录的移动次数
9、。28. 在直接插入、直接选择和冒泡这三种排序方法中，不稳定的排序方法是直接选择。三、应用题(本大题共5小题，每小题6分，共30分)请在答题卡上作答。29. 设栈S和队列Q的初始状态均为空，7个元素abcdefg依次进入栈S。若每个元素出栈 后立即进入队列Q,且7个元素出队的顺序是bdcfeag.现要求：(1)栈s的容量至少是多少？ (2 )在(1)的情况下，画出该栈中元素最多时的一个状态示意图。答(1)栈S的容量至少是3。(2)栈的状态示意图如下(只画出一个即可):21030. 某二叉树结点的中序遍历序列为ABCDEFG、后序遍历序列为BDCAFGE.现要求：(1)画出该二叉树；(2) 写出
10、该二叉树的先序遍历序列；(3) 该二叉树所对应的森林包括几棵树？答(1)所构造出的相应的二叉树为：(2)其先序遍历序列是：EACBDGF (3)所对应的森林中含有2棵树31. 假设有一棵完全二叉树按自上而下、从左到右的层序组织包含A、B、C、D、E、F、G 这7个结点，分别给出其邻接矩阵和邻接表。答：(1鄂接炬霁为:测匿黯酷履乍心i褪 01100001pQ1t0000011f *1? J bi oJJ8H o1ooooofill耕。1 D 0 0。00010000：:G- 001000032. 要求给出至少2个不同的关键字序列，均能构造出如题32图所示的二叉排序树；对此 你会得出什么结论？答：
11、(1) e,f,g,b,a,d,c 或 e,b,d,c,a,f,g 或 e,f,g,b,d,c,a 等等(2) 不同的关键字序列，可能会得到同样的二叉排序树33. 采用快速排序方法对关键字序列265, 301, 751, 129, 937, 863, 742, 694, 076, 438 进行升序排序，写出其每趟排序结束后的关键字序列。答：初始态：265 301 751 129 937 863 742 694 076 438第一趟：076 129 265 751 937 863 742 694 301 438第二趟：076 129 265 438 301 694 742 751 863 937
12、第三趟：076 129 265 301 438 694 742 751 863 937第四趟：076 129 265 301 438 694 742 751 863 937第五趟：076 129 265 301 438 694 742 751 863 937四、算法设计题(本大题共2小题，每小题7分.共14分)请在答题卡上作答.34. 写出复制一棵二叉树的算法。设原二叉树根结点由指针root指向，复制得到的二叉树 根结点由指针 newroot 指向，函数头为：void CopyTree(BTNode*root, BTNode, * newroot), 二叉树的存储结构为：type def st
13、ruct btnode DataType data;struct btnode 孚 lchildr 事 rchild； | BTNode, * BTree.答：void CopyTree(BTNode * root,BTNode * newroot)if ( ! root )newroot = NULL; newrootnewroot -CopyTree (CopyTree (=(BTNode * ) malloc ( sizeof (BTNode);data = root - data;root - Ichild, newroot - Ichild);root - rchild, newro
14、ot - rchild);else35. 已知带头结点的单链表L是按数据域值非递减有序链接的，试写一算法将值为x的结 点插入表匚中，使得L仍然是有序链接的。答：35. int LinklisdnsertCLipklist L,DataType x)LinkList s； nxt；LinkLis 如引K ne 追LinkLisr qL；wbde Up J =NL；LL) & (pdmnext；s = malloct sized (Node)； s data= x；5 ncxt=piq nt：xt Sv5.D10, D15. A1匕穹0，5二、填空题（本大题共13小题,每小SJU分,共踊分）23.
15、 n-125. K(Kl)/227.比较&答 3 iH，查找22. k2d2 1c或1e.一 J0j7色密启帛前2015年10月高等教育自学考试全国统一命踢考试数据结构导论试题答案及评分参考房（课程代码02M2）、单项选择逝（本大题共15学瑜，每浏聘2玲，共3。分）2.CXC4供夕4 C& A】2.C13-C4.D16,索引存概18. head Amxt I =NULL 19. （r+n） % ti20.三元纵表示f 026, IE 点 W，仰 JT J28,直接卷择/三、应用龄不米箱共5小题，每小题6分，共30分）知而S的群般至少型3, H分校的状态示意图如答29囹（只画由个即可）.注 答2
16、9图30. （DM构造出的相应的二又树为:其先序泄历序列zEACHDGF. （2分）怂）所驯应的赢林申含南艺樨捌。涉分）数据结构辱论就提答案及评分参考第1页（共2页）（1部接童阵为*归.3zl-答31图32t Cl)e,fFg,b,aPdtc E,h*d$c,aJ, &或 ej.gb,drG不冏的关键字序列，可能会得到同样的二又排序例.(3分)33. 初始奄：265 301 751 129 937 853 742 694 076 43B第一姻L37G 12&J & 751 537 863 742 694 301 43fi 第二超：。76 139拥5 438 301 6M 742 7&1 863
17、 937 第三痢06 129 265 301 438 694 74幻 751 863 9队： 第阳鼠切6 129 265 301 438 694 742J751 863 937 第翎.76 129 265 301 438 694 742 751 863 937四、算法设计国本大题共2小孰，每小91 7分,共14分34. vciid CopyTrrp(HlLNode *i root, ftTNotfe rewrcmOt if Cl root) new root NULL：妙|欢 data root -dat；it CopyTrQc(roat lchiicF ncwroat_(child); Ix
18、spy Tree( r=- rh il dntrw rocu rchBd) ； 35. tut L-inklisi_lnM!ri.CLi；Tklitl L,DaTaType x)rJULinkList s；LirtkList.p L nexr：LinkL sst q LjwhUf tip! NULL) & (p dnta-nf xt；s= juallot(siaeofCNode)；$ data=x；s -nextp；q ntKis；答31图j日等等（3分）y- yr yr J- Jr XJ- IfcJ4J- 5 /7 A/ 4- 1 1 1 11 2 c c c c c段推给松导沦法题谷案及评分参考第？页（共2页）UJ- J, / %rr.分分分分2 2 1() 分分 fc 11 Jc-(.)
