全国2009年1月高等教育自学考试
数据结构导论试题 课程代码：02142
一、单项选择题（本大题共15小题，每小题2分，共30分）
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1.数据的不可分割的最小标识单位是（ A ） A.数据项 B.数据记录 C.数据元素(数据和运算基本单位) D.数据变量
2. for（i=0；i for（j=0；j c［i］［j］=0； for（i=0；i for（j=0；j for（k=0；k 上列程序的时间复杂度为（ C ） A.O（m+n×t） B.O（m+n+t） C.O（m×n×t） D.O（m×t+n） 3.若线性表最常用的操作是存取第i个元素及其前趋的值，那么最节省操作时间的存储方式是（ B ） A.单链表 B.双链表 C.单循环链表 D.顺序表 4.设单链表中指针p指向结点A，要删除A之后的结点（若存在），则修改指针的操作为（ A ） A.p—>next=p—>next—>next（下一个，下一个原则） B.p=p—>next C.p=p—>next—>next D.p—>next=p Hs S 5.向一个栈顶指针为hs的链栈中插入一个*s结点时，应执行的操作为（ B ） Hs 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 ） A.Q［4］ B.Q［5］ C.Q［14］ D.Q［15］ 30-25-1=4 7.定义二维数组A［1‥8，0‥10］，起始地址为LOC，每个元素占2L个存储单元，在以行序为主序的存储方式下，某数据元素的地址为LOC+50L，则在以列序为主序的存储方式下，该元素的存储地址为（ D ） A.LOC+28L B.LOC+36L 具有n个结点的二叉树 C.LOC+50L D.LOC+52L 1. 有n-1个孩子 8.具有n个结点的二叉树，拥有指向孩子结点的分支数目是（ A ） 2. 有n+1空指域NULL A.n-1 B.n 3. 有2n个指针域 C.n+1（指针域为NULL） D.2n（指针域） 9.对一棵有100个结点的完全二叉树按层序编号，则编号为49的结点，它的左孩子的编号为（ B ） A.99 B.98 （49*2） 若有n个结点的完全二叉树； 1. 若，m*2>n,则C.97 D.50 1. 已知编号m 无左孩子 10.有m个叶子结点的哈夫曼树，其结点总数是（ A ） 2. 其左孩子为m*2 2. 若，m*2+1>n,A.2m-1 B.2m 3. 其右孩子为m*2+1 则无右孩子。 C.2m+1 D.2（m+1） 11.有n个结点的无向图的边数最多为（ B ） A.n+1 C.n（n+1） n(n-1) 2D.2n（n+1） 注：有向图为：n*（n—1） B. ?011??00112.设图的邻接矩阵为???，则该图为（ A ） ??010??0 1 2 1 0 3 A.有向图（杂乱矩阵） B.无向图 （为对称矩阵）如： 2 3 0 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），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为（ B ） A.4 B.5 注：1.二次排序树的规则： C.6 D.7 左小又大，连续一致原则 ○34 1 ○18 ○76 2 ○26 ○45 ○92 3 54 4 ○规律： 1. 左面的总小于右面的 2. 差值最小原则 ○65 5 15.采用排序算法对n个元素进行排序，其排序趟数肯定为n-1趟的排序方法是（ C ） A.插入和快速 B.冒泡和快速 C.选择和插入 D.选择和冒泡 二、填空题（本大题共13小题，每小题2分，共26分） 请在每小题的空格中填上正确答案。错填、不填均无分。 16.在数据结构中，数据的存储结构有顺序存储方式、链式存储方式、_索引存储方式 _____和散列存储方式等四种。 17. 作为一个算法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为 _算法输入的规模或问题的规模____。 18.在双链表中，存储一个结点有三个域，一个是数据域，另两个是指针域，分别指向 _直接前趋_和 __直接后继__。 19.在有n个元素的链队列中，入队和出队操作的时间复杂度分别为__O（1）______和___O（n）____。 20.在栈结构中，允许插入的一端称为 _栈顶_____；在队列结构中，允许插入的一端称为 ___队尾______。 21.在循环队列中，存储空间为0~n-1。设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么其队空标志为rear=front，队满标志为 _（rear+1）%maxsize=front__。 22.深度为k的二叉树至多有 _____2k -1 __个结点，最少有 ____2 k-1 _____个结点。 23.设有一稠密图G，则G采用 __邻接矩阵_存储结构较省空间。设有一稀疏图G，则G采用 __邻接表__存储结构较省空间。 24.在一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较_（n+1）/2__个元素结点。 25.假定对线性表R［0…59］进行分块检索，共分为10块，每块长度等于6。若检索索引表和块均用顺序检索的方法，则检索每一个元素的平均检索长 度为___9_____。 分块查找的平均查找长度为：ASLbs=1/2*(s/n+s)+1 ,其中，S表示为元素个总数。n，表示为每个块中的元素。 1/2(60/6+6)+1=9 26.文件在外存储器上的组织结构主要有三种：顺序文件、散列文件和索引文件，其中 __顺序__特别适应磁带存储器，也适应磁盘存储器。 27.在插入排序、冒泡排序、快速排序、归并排序等排序算法中，占用辅助空间最多的是 _归并排序________。 28.冒泡排序最好的时间复杂度为 __O（n）____，平均时间复杂度为 ___O（n2）______，是一种稳定的排序算法。 注：1.快速排序是不稳定的，时间复杂度为：O（nlog2n）但在最坏情况下，近似于O（n2） 2.二分法的时间复杂程度为：O（log2n）
全国2009年1月自考数据结构导论考试试题,答案,笔记汇编
