全国2004年1月高等教育自学考试数据结构导论试题课程代码：02142一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1．下列数据组织形式中，（）的各个结点可以任意邻接。A．集合B．树形结构C．线性结构D．图状结构2．设某二维数组A［1..n，1..n］，则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为（）A．O（log2n）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．50B．99C．100D．1018．邻接表是图的一种（）A．顺序存储结构B．链式存储结构C．索引存储结构D．散列存储结构9．如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是（）A．G肯定不是完全图B．G一定不是连通图C．G中一定有回路D．G有2个连通分量10．若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过（）A．n/2B．nC．(n+1)/2D．n+111．若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至（）A．该中间位置B．该中间位置－1C．该中间位置＋1D．该中间位置／212．散列文件不能（）A．随机存取B．索引存取C．按关键字存取D．直接存取13．若检索顺序文件各个记录的概率相同，设文件占用的页块数为n，则按关键字存取时的平均访问外存次数为（）A．n/2B．nC．n/4D．logn14．下列关键码序列中，属于堆的是（）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，95B．28，16，34，54，62，73，60，26，43，95C．28，16，34，54，62，60，73，26，43，95D．16，28，34，54，62，60，73，26，43，95二、填空题（本大题共13小题，每小题2分，共26分）请在每小题的空格中填上正确答案。错填、不填均无分。16．下列程序段的时间复杂性量级是_____________。for(i=1;idata[sq->top]=x；19．链队列实际上是一个同时带有头指针和尾指针的单链表，尾指针指向该单链表的_____________。20．设有k个结点，在用哈夫曼算法构造哈夫曼树的过程中，若第i次合并时已找到权最小的结点x和权次小的结点y，用T［x］.wt表示结点x的权值，已知T［x］.wt=m,T［y］.wt=n，则合并成新的二叉树后给新根结点的权值赋值的语句为_____________。21．在下列树中，结点H的祖先为_____________。22．顶点数为n、边数为n(n-1)/2的无向图称为_____________。23．动态查找表在开散列表上通常采用_____________来解决冲突问题。24．对于有10个元素的有序表采用二分查找，需要比较3次方可找到其对应的键值，则该元素在有序表中的位置可能是______________。25．查找表的逻辑结构与线性结构、树型结构等相比，根本区别在于_________...
