全国自考2010年10月《数据结构导论》试题及答案

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

1、全国高等教育自学考试全国统一命题考试2010年10月《数据结构导论》试题及答案一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1．下列描述中正确的是(C)A．数据元素是数据的最小单位B．数据结构是具有结构的数据对象C．数据结构是指相互之间存在一种或多种特定关系的数据元素的集合D．算法和程序原则上没有区别，在讨论数据结构时两者是通用的2．归并排序的时间复杂度是(B)A．O（n2）B．O（nlog2n）C．O（n）D．O（log2n）3

2、．二分查找的时间复杂度是(D)A．O（n2）B．O（nlog2n）C．O（n）D．O（log2n）4．顺序存储的表中有90000个元素，已按关键字值升序排列，假设对每个元素进行查找的概率相同，且每个元素的关键字值皆不相同，用顺序查找法查找时，需平均比较的次数为(C)A．25000B．30000C．45000D．900005．散列文件是一种(D)A．顺序文件B．索引文件C．链接文件D．计算寻址文件6．两个矩阵A：m×n，B：n×p相乘，其时间复杂度为(B)A．O(n)B．O(mnp)C．O(n2)D．O（mp）7．常用于函数调用的数据结构是(A)

3、A．栈B．队列C．链表D．数组8．二维数组A［n］［m］以列优先顺序存储，数组A中每个元素占用1个字节，A［1］［1］为首元素，其地址为0，则元素A［i］［j］的地址为(B)A．（i-1）×m+(j-1)B．(j-1)×n+(i-1)C．(j-1)×n+iD．j×n+i9．图的广度优先搜索使用的数据结构是(A)A．队列B．树C．栈D．集合10．序列（21,19,37,5,2）经冒泡排序法由小到大排序，在第一次执行交换后所得结果为(A)A．(19，21，37，5，2)B．(21，19，5，37，2)C．(21，19，37，2，5)D．(2，21，

4、19，37，5)11．数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为(D)A．索引存储方法B．顺序存储方法C．链式存储方法D．散列存储方法12．在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点的(B)A．直接前趋B．直接后继C．开始结点D．终端结点13．在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的时间复杂度为(C)A．O（1）B．O（log2n）C．O（n）D．O（n2）14．在链队列中执行入队操作，(D)A．需判别队是否空B．需判别队是否满C．限制在链表头p

5、进行D．限制在链表尾p进行15．一整数序列26，59，77，31，51，11，19，42，以二路归并排序从小到大排序，第一阶段的归并结果为(B)A．31，51，11，42，26，77，59，19B．26，59，31，77，11，51，19，42当前第1页，共3页C．11，19，26，31，42，59，51，77D．26，11，19，31，51，59，77，42二、填空题(本大题共13小题，每小题2分，共26分)请在每小题的空格中填上正确答案。错填、不填均无分。16．下列程序段的时间复杂度为__O(n)_____。i=0；s=0；while（s<

6、n）{i++；s=s+i；}17．数据的存储结构被分为顺序存储结构、_链式存储结构_、散列存储结构和索引存储结构4种。18．从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动_n-i_个元素。19．在单链表中，插入一个新结点需修改__2__个指针。20．在队列结构中，允许插入的一端称为__队尾__。21．稀疏矩阵采用的压缩存储方法是_三元组表_。22．向一个栈顶指针为top的链栈中插入一个新结点*p时，应执行p->next=top和_top=p_操作。23．有m个叶结点的哈夫曼树所具有的结点数为__2m-1__。24．在一棵具有

7、n个结点的完全二叉树中，从树根起，自上而下、自左至右地给所有结点编号。设根结点编号为1。若编号为i的结点有右孩子，那么其右孩子的编号为__2i+1__。25．在一棵树中，_根_结点没有前驱结点。26．一个具有n个顶点的有向完全图的弧数是_n(n-1)_。27．n个顶点的无向图G用邻接矩阵A［n］［n］存储，其中第i列的所有元素之和等于顶点Vi的_度_。28．选择排序的平均时间复杂度为__O（n2）_。三、应用题(本大题共5小题，每小题6分，共30分)29．在栈的输入端元素的输入顺序为1，2，3，4，5，6，进栈过程中可以退栈，则退栈时能否排成序

8、列3，2，5，6，4，1和1，5，4，6，2，3，若能，写出进栈、退栈过程，若不能，简述理由。（用push（x）表示x进栈，pop(x)表示x退栈）(