全国2009年1月自考数据结构导论考试试题,答案,笔记

《全国2009年1月自考数据结构导论考试试题,答案,笔记》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、全国2009年1月高等教育自学考试数据结构导论试题课程代码：02142一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.数据的不可分割的最小标识单位是（A）A.数据项B.数据记录C.数据元素(数据和运算基本单位)D.数据变量2.for（i=0；i

2、0；knext=p—>next—>next（下一个，下一个原则）B.p=p—>nextC

3、.p=p—>next—>nextD.p—>next=pHsSHs5.向一个栈顶指针为hs的链栈中插入一个*s结点时，应执行的操作为（B）A.hs—>next=s；B.s—>next=hs；hs=s；（下一个，赋值原则）C.s—>next=hs—>next；hs—>next=s；D.s—>next=hs；hs=hs—>next；6.设循环队列的元素存放在一维数组Q［0‥30］中，队列非空时，front指示队头元素的前一个位置，rear指示队尾元素。如果队列中元素的个数为11，front的值为25，则r

4、ear应指向的元素是（A）A.Q［4］B.Q［5］C.Q［14］D.Q［15］30-25-1=47.定义二维数组A［1‥8，0‥10］，起始地址为LOC，每个元素占2L个存储单元，在以行序为主序的存储方式下，某数据元素的地址为LOC+50L，则在以列序为主序的存储方式下，该元素的存储地址为（D）具有n个结点的二叉树1.有n-1个孩子2.有n+1空指域NULL3.有2n个指针域A.LOC+28LB.LOC+36LC.LOC+50LD.LOC+52L 8.具有n个结点的二叉树，拥有指向孩子结点的分支数目

5、是（A）A.n-1B.nC.n+1（指针域为NULL）D.2n（指针域）9.对一棵有100个结点的完全二叉树按层序编号，则编号为49的结点，它的左孩子的编号为（B）1.若，m*2>n,则无左孩子2.若，m*2+1>n,则无右孩子。若有n个结点的完全二叉树；1.已知编号m2.其左孩子为m*23.其右孩子为m*2+1A.99B.98（49*2）C.97D.5010.有m个叶子结点的哈夫曼树，其结点总数是（A）A.2m-1B.2mC.2m+1D.2（m+1）11.有n个结点的无向图的边数最多为（B）A.n

6、+1B.C.n（n+1）D.2n（n+1）注：有向图为：n*（n—1）01210323012.设图的邻接矩阵为，则该图为（A）A.有向图（杂乱矩阵）B.无向图（为对称矩阵）如：C.强连通图D.完全图13.二分查找算法的时间复杂度是（D）A.O（n2）（冒泡排序（平均复杂时间程度））B.O（nlog2n）（快速排序）C.O（n）（冒泡排序（最好情况下时间复杂程度））D.O（log2n）14.已知8个元素（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则该树

7、的深度为（B）A.4B.5注：1.二次排序树的规则：C.6D.7左小又大，连续一致原则规律：1.左面的总小于右面的2.差值最小原则1234515.采用排序算法对n个元素进行排序，其排序趟数肯定为n-1趟的排序方法是（C）A.插入和快速B.冒泡和快速C.选择和插入D.选择和冒泡二、填空题（本大题共13小题，每小题2分，共26分）请在每小题的空格中填上正确答案。错填、不填均无分。16.在数据结构中，数据的存储结构有顺序存储方式、链式存储方式、_索引存储方式_____和散列存储方式等四种。17.作为一个算

8、法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为_算法输入的规模或问题的规模____。18.在双链表中，存储一个结点有三个域，一个是数据域，另两个是指针域，分别指向_直接前趋_和__直接后继__。19.在有n个元素的链队列中，入队和出队操作的时间复杂度分别为__O（1）______和___O（n）____。20.在栈结构中，允许插入的一端称为_栈顶_____；在队列结构中，允许插入的一端称为___队尾______。21.在循环队列中，存储空间为0~n-1