2009年1月全国自学考试《数据结构导论》试题.docVIP

2009年1月全国自学考试《数据结构导论》试题 一、单项选择题（本大题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.数据的不可分割的最小标识单位是（ ） A.数据项 B.数据记录 C.数据元素 D.数据变量 2. for（i=0；im；i++） for（j=0；jt；j++） c［i］［j］=0； for（i=0；im；i++） for（j=0；jt；j++） for（k=0；kn；k++） c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］； 上列程序的时间复杂度为（ ） A.O（（（（ C.单循环链表 D.顺序表 4.设单链表中指针p指向结点A，要删除A之后的结点（若存在），则修改指针的操作为（ ） A.p—next=p—next—next B.p=p—next C.p=p—next—next D.p—next=p 5.向一个栈顶指针为hs的链栈中插入一个*s结点时，应执行的操作为（ ） 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，则rear应指向的元素是（ ） A.Q［4］ B.Q［5］ C.Q［14］ D.Q［15］ 7.定义二维数组A［1‥8，0‥10］，起始地址为LOC，每个元素占2L个存储单元，在以行序为主序的存储方式下，某数据元素的地址为LOC+50L，则在以列序为主序的存储方式下，该元素的存储地址为（ ） A.LOC+28L B.LOC+36L C.LOC+50L D.LOC+52L 8.具有n个结点的二叉树，拥有指向孩子结点的分支数目是（ ） A.n-1 B.n C.n+1 D.2n 9.对一棵有100个结点的完全二叉树按层序编号，则编号为49的结点，它的左孩子的编号为（ ） A.99 B.98 C.97 D.50 10.有m个叶子结点的哈夫曼树，其结点总数是（ ） A.2m-1 B.2m C.2m+1 D.2（m+1） 11.有n个结点的无向图的边数最多为（ ） A.n+1 B. C.n（n+1） D.2n（n+1） 12.设图的邻接矩阵为，则该图为（ ） A.有向图 B.无向图 C.强连通图 D.完全图 13.二分查找算法的时间复杂度是（ ） A.O（n2） B.O（nlog2n） C.O（n） D.O（log2n） 14.已知8个元素（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为（ ） A.4 B.5 C.6 D.7 15.采用排序算法对n个元素进行排序，其排序趟数肯定为n-1趟的排序方法是（ ） A.插入和快速 B.冒泡和快速 C.选择和插入 D.选择和冒泡 二、填空题（本大题共13小题，每小题2分，共26分） 请在每小题的空格中填上正确答案。错填、不填均无分。 16.在数据结构中，数据的存储结构有顺序存储方式、链式存储方式、_________和散列存储方式等四种。 17. 作为一个算法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为_________。 18.在双链表中，存储一个结点有三个域，一个是数据域，另两个是指针域，分别指向 _________和 _________。 19.在有n个元素的链队列中，入队和出队操作的时间复杂度分别为_________和_________。 20.在栈结构中，允许插入的一端称为 _________；在队列结构中，允许插入的一端称为 _________。 21.在循环队列中，存储空间为0~n-1。设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么其队空标志为rear=front，队满标志为 _________。 22.深度为k的二叉树至多有 _________个结点，最少有 _________个结点。 23.设有一稠密图G，则G采用 _________存储结构较省空间。设有一稀疏图G，则G采用 _________存储结构较省空间。 24.在一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较_________个元素结点。 25.假定对线