2004年1月自考数据结构导论试题真题.docVIP

全国2004年1月高等教育自学考试 数据结构导论试题 课程代码：02142 一、单项选择题（本大题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列数据组织形式中，（　　　）的各个结点可以任意邻接。 A．集合 B．树形结构 C．线性结构 D．图状结构 2．设某二维数组A［1..n，1..nlog2n） B．O(n) C．O(nlog2n) D．O(n2) 3．在线性表的下列存储结构中，读取元素花费时间最少的是（　　　） A．单链表 B．双链表 C．循环链表 D．顺序表 4．将一个头指针为p的单链表中的元素按与原单链表相反的次序存放，则下列算法段中的空白处应为 q=NULL; while (p!=NULL) { （　　　） } p=q; A．r=q; q=p; p=p - next; q - next=r; B．q=p; r=q; p=p - next; q - next=r; C．r=q; p=p - next; q=p; q - next=r; D．q=p; p=p - next; r=q; q - next=r; 5．数组通常具有两种基本运算，即（　　　） A．创建和删除 B．索引和修改 C．读和写 D．排序和查找 6．除根结点外，树上每个结点（　　　） A．可有任意多个孩子、任意多个双亲 B．可有任意多个孩子、一个双亲 C．可有一个孩子、任意多个双亲 D．只有一个孩子、一个双亲 7．具有100个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、右孩子，其余（　　　）个指针域为空。 A．50 B．99 C．100 D．101 8．邻接表是图的一种（　　　） A．顺序存储结构 B．链式存储结构 C．索引存储结构 D．散列存储结构 9．如果无向图G必须进行二次广度优先有哪些信誉好的足球投注网站才能访问其所有顶点，则下列说法中不正确的是（　　　） A．G肯定不是完全图 B．G一定不是连通图 C．G中一定有回路 D．G有2个连通分量 10．若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过（　　　） A．n/2 B．n C．(n+1)/2 D．n+1 11．若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至（　　　） A．该中间位置 B．该中间位置－1 C．该中间位置＋1 D．该中间位置／2 12．散列文件不能（　　　） A．随机存取 B．索引存取 C．按关键字存取 D．直接存取 13．若检索顺序文件各个记录的概率相同，设文件占用的页块数为n，则按关键字存取时的平均访问外存次数为（　　　） A．n/2 B．n C．n/4 D．log n 14．下列关键码序列中，属于堆的是（　　　） A．（15，30，22，93，52，71） B．（15，71，30，22，93，52） C．（15，52，22，93，30，71） D．（93，30，52，22，15，71） 15．已知10个数据元素为（54，28，16，34，73，62，95，60，26，43），对该数列按从小到大排序，经过一趟冒泡排序后的序列为（　　　） A．16，28，34，54，73，62，60，26，43，95 B．28，16，34，54，62，73，60，26，43，95 C．28，16，34，54，62，60，73，26，43，95 D．16，28，34，54，62，60，73，26，43，95 二、填空题（本大题共13小题，每小题2分，共26分） 请在每小题的空格中填上正确答案。错填、不填均无分。 16．下列程序段的时间复杂性量级是_____________。for (i=1;in; i++) for (j=1; ji; j++) t=t+1; 17．在顺序存储的线性表（a1,a2…，an）中的第i (1≤i≤n)个元素之前插入一个元素，则需向后移动_____________个元素。 18．在栈的顺序实现中，若栈不满，则进栈操作可以用下列算法片断实现： _____________； sq - data[sq - top]=x； 19．链队列实际上是一个同时带有头指针和尾指针的单链表，尾指针指向该单链表的_____________。 20．设有k个结点，在用哈夫曼算法构造哈夫曼树的过程中，若第i次合并时已找到权最小的结点x和权次小的结点y，用T［x］.wt表示结点x的权值，已知